Lower bounds for the discrepancy of triples of inversive congruential pseudorandom numbers with power of two modulus

Let \(m= 2^\omega\) with some integer \(\omega\geq 4\), and for integers \(n\geq 1\) let \(\mathbb{Z}^*_n\) be the set of all odd integers among \(0,1,\dots,n- 1\). For \(y_0\in \mathbb{Z}^*_m\) and parameters \(a,c\in \mathbb{Z}^*_m\) with \(a\equiv 1\pmod 4\), define \[ y_{n+ 1}\equiv ac^2 y^{-1}_n+ 2c\pmod m, \] where \(z^{-1}\) means the multiplicative inverse \(\text{mod }m\) of \(z\in \mathbb{Z}^*_m\). Let \(x_n= y_n/m\) for \(n\geq 0\). Thus, we obtain a sequence \((x_n)_{n\geq 0}\) of inversive congruential pseudorandom numbers in \([0,1)\). It is purely periodic with the maximum possible period length \(m/2\). The authors consider triples \(\vec x_n= (x_n,x_{n+ 1},x_{n+ 2})\in [0,1)^3\) \((n= 0,1,2,\dots)\), and prove that for any parameters \(a,c\in\mathbb{Z}^*_m\) as above the discrepancy of the points \(\vec x_0,\vec x_1,\dots,\vec x_{(m/2)- 1}\) is of an order of magnitude at least \(m^{-1/3}\). Of course, this lower bound remains valid for the discrepancy of \(k\)-tuples with \(k\geq 4\). The proof of this result is based on a detailed discussion of certain rational exponential sums.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Lower bounds for the discrepancy of triples of inversive congruential pseudorandom numbers with power of two modulus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1386385)