Character sums and nonlinear recurrence sequences (Q2497490)

Let \(F(X_1,\ldots,X_d)\) be a function in \(d\) variables over a finite ring \({\mathcal R}\) with identity of \(m\) elements. The authors consider nonlinear recurrence sequences \((a_n)\) over \({\mathcal R}\) defined by \[ a_{n+d}=F(a_{d+n-1},\ldots,a_n),\quad n=0,1,\ldots, \] with some initial values \(a_0,\ldots,a_{d-1}\in {\mathcal R}\). For positive integers \(h\) and \(N\) they study additive character sums \[ S(u_0,\ldots,u_h;N)=\sum_{n=0}^{N-1} \chi(u_0a_n+\ldots+u_h a_{n+h}), \] where \(\chi\) is a nontrivial additive character of \({\mathcal R}\) and not all \(u_i\in {\mathcal R}\) are zero. The main result of the paper is an upper bound on the absolute value of these sums. When \(u_0=-1\), \(u_1=\ldots=u_{h-1}=0\) and \(u_h=1\) the sum is the aperiodic autocorrelation (with shift \(h\) and length \(N\)) of the sequence. Reviewer's comments. Theorems 1 and 3 do not hold true in full generality (but they do for finite fields, which is the main case of interest). An erratum to the paper was written by the authors. The correction should appear in the same journal soon. Some references are somewhat misleading since they give the impression that the paper deals with multiplicative character sums. Some references corresponding to additive character sums (exponential sums) are (1) \textit{E. D. El-Mahassni, I. E. Shparlinski} and \textit{A. Winterhof}, ``Distribution of nonlinear congruential pseudorandom numbers modulo almost squarefree integers.'' [Monatsh. Math. 148, No. 4, 297--307 (2006; Zbl 1105.11023)]. (2) \textit{E. D. El-Mahassni} and \textit{A. Winterhof}, ``On the distribution of nonlinear congruential pseudorandom numbers in residue rings.'' [Int. J. Number Theory 2, No. 1, 163--168 (2006; Zbl 1125.11044)]. (3) \textit{F. Griffin, H. Niederreiter} and \textit{I. E. Shparlinski}, ``On the distribution of nonlinear recursive congruential pseudorandom numbers of higher orders.'' [Applied algebra, algebraic algorithms and error correcting codes. 13th international symposium, AAECC-13, Honolulu, HI, USA, November 15--19, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1719, 87--93 (1999; Zbl 0958.11052)]. (4) \textit{J. Gutierrez} and \textit{D. Gomez-Perez}, ``Iterations of multivariate polynomials and discrepancy of pseudorandom numbers.'' [Applied algebra, algebraic algorithms and error-correcting codes. 14th international symposium, AAECC-14, Melbourne, Australia, November 26--30, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2227, 192--199 (2001; Zbl 1053.11068)]. (5) \textit{H. Niederreiter} and \textit{I. E. Shparlinski}, ``On the distribution and lattice structure of nonlinear congruential pseudorandom numbers.'' [Finite Fields Appl. 5, No. 3, 246--253 (1999; Zbl 0942.11037)]. (6) \textit{H. Niederreiter} and \textit{A. Winterhof}, ``Exponential sums for nonlinear recurring sequences.'' [Finite Fields Appl., to appear].