Correlation of the two-prime Sidel'nikov sequence (Q2430705)

Let \(p\) and \(q\) be different odd primes and \(g\) a primitive element both modulo \(p\) and modulo \(q\). Let \(d=\gcd(p-1, q-1)\) and \(t=(p-1)(q-1)/d\) and set \(P=\{p, 2p, \ldots,(q-1)p\}\) and \(Q_0=\{0,q, 2q,\ldots,(p-1)q\}\). The authors generalise the Sidelnikov sequence and the two-prime generator by defining the sequence \[ s_{n}=\begin{cases} 0 & \text{if}\, (g^n+1)\bmod pq\,\, {\text{is in}}\, Q_0\\ 1 & \text{if}\, (g^n+1)\bmod pq\,\, {\text{is in}}\, P\\ {1\over2}\left(1-\left({g^n+1\over p}\right)\left({g^n+1\over q}\right)\right) & \text{if}\, \gcd(g^n+1, pq)=1\end{cases} \] where \(({\cdot\over p})\) and \(({\cdot\over q})\) are Legendre symbols. The sequence \((s_n)\) has period \(t\) and the authors estimate various measures of randomness. For example, the excess of 1's over 0's in a period is \({q-p\over d}+O(p^{1/2}q^{1/2})\) and estimates of the auto-correlation, correlation measure and linear complexity profile are obtained with similar error terms. The general inequality behind the estimates is \[ \left|\sum_{n=0}^{N-1}\left({f(g^n)\over p}\right) \left({f(g^n)\over q}\right)\right| = O(D^2p^{1/2}q^{1/2}\log t), \] when \(f\) is a monic polynomial with integer coefficients of degree \(D\geq 1\) which is not a square in \({\mathbb F}_p[X]\) or in \({\mathbb F}_q[X]\), \(f(0)\neq 0\) and \(1\leq N\leq t\). This in turn follows from Weil's theorem.