On the average discrepancy of successive tuples of pseudo-random numbers over parts of the period (Q1291097)

Let \(p\) be prime and \(g\in \mathbb{Z}_p[x]\) be a permutation polynomial of \(\mathbb{Z}_p\) with \(1\leq \deg(g)\leq p-2\). Define a sequence \((y_n)_{n\in \mathbb{Z}_p}\) by \(y_n= g(n)\) for all \(n\in \mathbb{Z}_p\) and set \(x_n= y_n/p\). We also define the nonoverlapping \(s\)-tuples \(x_n= (x_{sn}, x_{sn+1},\dots, x_{sn+s-1})\in [0,1)^s\) and the overlapping \(s\)-tuples \(x_n'= (x_n, x_{n+1},\dots, x_{n+s-1})\in [0,1)^s\). \textit{H. Niederreiter} [Monatsh. Math. 106, 149-159 (1988; Zbl 0652.65007)] gave an upper bound for the discrepancy of the first \(N\) \(s\)-tuples \(x_n'\) \((n=0,\dots, N-1)\) for any \(g\) of degree \(d\geq s+1\) and all \(N\) with \(1\leq N< p\). In this paper the authors consider the average value over the set \(P\) of all permutation polynomials of \(\mathbb{Z}_p\) of the discrepancy \(D_N^{(s)}(g)\) of non-overlapping \(s\)-tuples \(x_n\) \((n=0,\dots, N-1)\). They prove that if \(2\leq s<p/2\) and \(1\leq N\leq p\), then \[ \frac{1}{30} N^{-1/2}< \frac{1}{p!} \sum_{g\in P} D_N^{(s)}(g)< N^{-1/2} \biggl(\frac{2}{\pi} \log p+ \frac{7}{5} \biggr)^2\cdot \sqrt{\frac{p}{p-2s+1}}+ \frac{s}{p}. \] These estimates are also sharp up to logarithmic factors even for rather small parts of the period.