Character sums and nonlinear recurrence sequences
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].
- Multiplicative Character Sums of Recurring Sequences with Rédei Functions
- Character sums for sequences of iterations of Dickson polynomials
- Multiplicative character sums for nonlinear recurring sequences
- The discrete Fourier transform of a recurrent sequence
- Multiplicative character sums of a class of nonlinear recurrence vector sequences
- The Sidel'nikov method for estimating the number of signs on segments of linear recurrence sequences over Galois rings
- An average bound for character sums with some counter-dependent recurrence sequences
- Topics related to character sums
- Characteristic digit-sum sequences
- On some particular character and exponential sums
- scientific article; zbMATH DE number 1973372 (Why is no real title available?)
- scientific article; zbMATH DE number 1790427 (Why is no real title available?)
- Multiplicative character sums for nonlinear recurring sequences
- ON THE DISTRIBUTION OF POWER RESIDUES AND PRIMITIVE ELEMENTS IN SOME NONLINEAR RECURRING SEQUENCES
- Investigating the discrepancy property of de Bruijn sequences
- A note on Weil's multiplicative character sum
- Exponential sums for nonlinear recurring sequences
- Multiplicative character sums of a class of nonlinear recurrence vector sequences
- CHARACTERIZATIONS ON CHAIN RECURRENCES
- Two remarks on a paper by Moreno and Kumar [binary Reed-Muller codes]
- The discrepancy of the lex-least de Bruijn sequence
This page was built for publication: Character sums and nonlinear recurrence sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2497490)
