On the nonlinearity of linear recurrence sequences (Q2488716)

Let \(p\) be a prime number and \({\mathbb F}_p\) the finite field of \(p\) elements identified with the set \(\{0,1,\ldots, p-1\}\). Let \((s_k)_{k=0}^\infty \) be a linear recurrence of order \(n\) over \({\mathbb F}_p\) and suppose its characteristic polynomial is irreducible. Let \({\mathcal B}\) denote the \(n\)-dimensonal cube \({\mathbb F}_p^n\) and introduce the inner product \(\langle h,r\rangle=h_1r_1+\cdots+h_nr_n\) for \(h=(h_1,\ldots,h_n)\) and \(r=(r_1,\ldots,r_n)\) in \(\mathcal B\). The main result of the paper is an estimate for the exponential sum \[ T(b)=\sum_{k=0}^{t-1} e_p(s_k+\langle b,k\rangle) \] related to the discrete Fourier transform, where \(e_p(z)=e^{2\pi iz/p}\). Under the hypotheses stated above, the authors show that \[ \max_{b\text{\;in\;}{\mathcal B}} | T(b)| =O_p(t^{3/4}p^{n/8}n^{1/4}) \] with an implied constant depending only on \(p\). The proof proceeds by splitting \(k\) in \(\mathcal B\) as \(k=u+vp^\nu\) where \(0\leq u<p^\nu\) and \(0\leq v<p^{n-\nu}\) so that \(\langle b,k\rangle =\langle d,u\rangle + \langle e,v\rangle\) where \(d=(b_0,\ldots,b_{\nu-1})\) and \(e=(b_\nu,\ldots,b_{n-1})\). This leads to \[ | T(b)| =\left| \sum_{u=0}^{p^\nu-1} e_p(\langle d,u\rangle) \sum_{v=0}^{V-1} e_p(s_{u+vp^\nu}+\langle e,v\rangle)\right| +O(p^\nu) \] where \(V=\lfloor tp^{-\nu}\rfloor\). After an application of Cauchy's inequality, the inner sum is again formed from a linear recurrence \((a_n)\) over \({\mathbb F}_p\) of degree \(n\) and period \(t\) and with an irreducible characteristic polynomial. This sum can be estimated by means of the Korobov bound: for \(1\leq U\leq t\) \[ \sum_{u=0}^U e_p(a_n) = O(p^{n/2}\log t). \] The case \(p=2\) has cryptographic significance since \(T(b)\) is essentially the non-linearity of the sequence \((s_k)\). However, the estimate in this case is not as strong as the best known bounds for the non-linearity of specially constructed sequences.