Average behaviour of compound nonlinear congruential pseudorandom numbers (Q1908799)

Let \(p_1, \dots, p_r\geq 5\) be distinct primes. For \(1\leq i\leq r\) we identify \(\mathbb{Z}_{p_i}= \{0, 1, \dots, p_i-1\}\) with the finite field of order \(p_i\). Let \(\gamma_i\in \mathbb{Z}^*_{p_i}= \mathbb{Z}_{p_i} \setminus \{0\}\) and \(g_i: \mathbb{Z}\to \mathbb{Z}_{p_i}\) be a monic permutation polynomial of \(\mathbb{Z}_{p_i}\) with degree \(d_i\) as a polynomial over \(\mathbb{Z}_{p_i}\), where \(3\leq d_i\leq p_i-2\). For every \(i\) \((1\leq i\leq r)\) define \(y_n^{(i)}\in \mathbb{Z}_{p_i}\) by \(y_n^{(i)} \equiv \gamma_i g_i (n) \pmod {p_i}\), \(n\geq 0\) and let \(x_n^{(i)}= y_n^{(i)}/ p_i\), \(n\geq 0\). We define compound nonlinear congruential pseudorandom numbers \(x_n\) \((n= 1, 2,\dots)\) in the interval \([0,1)\) by \(x_n \equiv x_n^{(1)}+ \cdots+ x_n^{(r)} \pmod 1\), \(n\geq 0\). Put \({\mathbf x}_n= (x_{sn}, x_{sn+1}, \dots, x_{sn+ s-1})\in [0,1)^s\), \(n\geq 0\), and let \(m= p_1\dots p_r\), the period length of the sequence \((x_n )_{n\geq 0}\). Denote the discrepancy of the point set \(\{{\mathbf x}_0, \dots, {\mathbf x}_{N-1} \}\) by \(D^{(s)}_{N; \gamma_1, \dots, \gamma_r}\). The authors prove that for \(s\leq \min\{ d_1, \dots, d_r\}\) and \(1\leq N\leq m\), the average value of the discrepancy \(D^{(s)}_{N; \gamma_1, \dots, \gamma_r}\) over \((\gamma_1, \dots, \gamma_r)\in \mathbb{Z}^*_{p_1} \times \dots\times \mathbb{Z}^*_{p_r}\) is less than \[ \prod^r_{i=1} (\sqrt {d_i+ 1.25}+ 0.5) N^{-1/2} \bigl( {\textstyle {2\over \pi}} \log m+ {\textstyle {7\over 5}} \bigr)^s. \] Furthermore, they also prove for any permutation polynomial \(g_1, ... , g_r\) that if \(s\leq \min\{ d_1, ... , d_r\}\), then only an arbitrarily small percentage of the parameters \(\gamma_1, \dots, \gamma_r\) may give a discrepancy \(D^{(s)}_{N; \gamma_1, \dots, \gamma_r}\) with an order of magnitude greater than \(N^{-1/2} (\log m)^s\); and if \(s< \min\{ p_1, \dots, p_r\}\), then there exist parameters \(\gamma_1, \dots, \gamma_r\) such that the discrepancy \(D^{(s)}_{N; \gamma_1, \dots, \gamma_r}\) is of an order of magnitude at least \(N^{-1/2}\) for \(N\) not too large.