On the pseudorandom properties of \(k\)-ary Sidel'nikov sequences (Q6163786)

Let \(q\) be an odd prime power, \({\mathbb F}_q\) be the finite field with \(q\) elements, \(g\) be a primitive element in \({\mathbb F}_q\) and \(k>1\) be a divisor of \(q-1\). Define \[ D_0=\left\{g^{lk}: 0\le l\le \frac{q-1}{k}-1\right\}\qquad {\text{ and}}\qquad D_i=g^iD_0,\qquad 1\le i\le k-1. \] Note that \(D_0,\ldots,D_{k-1}\) form a partition of \({\mathbb F}_q^*\). Sidelnikov introduced that \(k\)-ary sequence \(\mathbf{S}_{q-1}=\{s_1,s_2,\ldots,s_{q-1}\}\), where \(s_n=i\) if \(g^n+1\in D_i\) and \(s_n=0\) if \(n=(q-1)/2\). For a \(k\)-ary sequence \(E_N=\{e_1,e_2,\ldots,e_N\}\) (\(e_i\) elements of a set \({\mathcal A}\) with \(k\)-elements) one denotes \[ x(E_N,a,M,u,v)=|\{0\le j\le M-1, e_{u+jv}=a\}| \] and for a word \(w\) with letters in \({\mathcal A}\) of length \(l\) and a vector \(D=(d_1,\ldots,d_l)\) with non-negative integer components \(d_1<\cdots<d_l\), one denotes \[ g(E_N,w,M,D)=|\{1\le n\le M, (e_{n+d_1},\ldots,e_{n+d_l})=w\}|. \] Following \textit{C. Mauduit} and \textit{A. Sárközy} [Indag. Math., New Ser. 13, No. 1, 89--101 (2002; Zbl 1049.11090)] one defines the \(f\)-well-distribution and \(f\)-correlation measure of order \(l\) as \[ \delta(E_N)=\max_{a,M,u,v} \left|x(E_N,a,M,u,v)-\frac{M}{k}\right|, \gamma_l(E_N)=\max_{w,M,D} \left|g(E_N,w,M,D)-\frac{M}{k^l}\right|, \] respectively, where the maxima are over all the allowable choices \(a\in {\mathcal A}\), \(u,v,M\) with \(1\le u\le u+(M-1)v\le N\), \(w\) word of length \(l\) and \(D=(d_1,\ldots,d_l)\) such that \(0\le d_1<\cdots<d_l\le N-M\). The first theorem of the paper gives the bounds \[ \delta(\mathbf{S}_{q-1})\le \frac{4}{\pi^2} q^{1/2}\log(q+2)\qquad {\text{and}}\qquad \gamma_l(\mathbf{S}_{q-1})\le \frac{4l}{\pi^2}\log(q+4). \] The second theorem of the paper looks at the \(\phi(q-1)\) sequences \(\mathbf{S}_{q-1}\) obtained by varying the primitive element \(g\) and gives lower bounds on the number of distinct such sequences. The proofs use bounds for character sums.