ON THE DISTRIBUTION OF POWER RESIDUES AND PRIMITIVE ELEMENTS IN SOME NONLINEAR RECURRING SEQUENCES (Q4418952)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1957448
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | ON THE DISTRIBUTION OF POWER RESIDUES AND PRIMITIVE ELEMENTS IN SOME NONLINEAR RECURRING SEQUENCES |
scientific article; zbMATH DE number 1957448 |
Statements
ON THE DISTRIBUTION OF POWER RESIDUES AND PRIMITIVE ELEMENTS IN SOME NONLINEAR RECURRING SEQUENCES (English)
0 references
2003
0 references
finite fields
0 references
character sums with nonlinear recurring sequences
0 references
distribution of \(s\)-power and primitive elements in recurring sequences
0 references
0.8764273524284363
0 references
0.8607580065727234
0 references
0.8160490393638611
0 references
0.8033014535903931
0 references
0.7904192209243774
0 references
Let \(\mathbb{F}_{q}\) be a finite field with \(q\) elements, and \( \chi\) a nontrivial multiplicative character of \(\mathbb{F}_{q}\). Given \(a,b \in F_{q}\), \(a \neq 0\), let \( \psi\) be the permutation of \(\mathbb{F}_{q}\) defined by \[ \psi(w) = \begin{cases} aw^{-1}+b & \text{if~} w \neq 0,\\ b& \text{if~} w = 0, \end{cases} \] and \(u= \{u_{0}, u_{1}, u_{2}, \ldots \}\) the sequence of elements of \(\mathbb{F}_{q}\) obtained by the recurrence relation \[ u_{n+1}= \psi(u_{n}), \qquad n=0,1,2, \ldots , \] where \(u_{0}\) is the initial value. This sequence is purely periodic with least period \(t \leq q\). The authors consider the character sum \[ S_{ \chi}(N)= \sum_{n=0}^{N} \chi(u_{n}) \] and prove that \[ | S_{ \chi}(N)| < 2.2\, N^{1/2}q^{1/4} \qquad \text{for} \quad 1 \leq N \leq t. \] This result is used to study the distribution of \(s\)-power and primitive elements in the sequence \(u\). If \(s\) is a positive divisor of \(q-1\), and \(R_{s}(N)\) the number of \(s\)-power elements of the field \(\mathbb{F}_{q}\) among \(u_{0}, u_{1}. \ldots ,u_{N-1}\), the authors show that \[ | R_{s}(N)-N/s| < 2.2\, N^{1/2}q^{1/4} \qquad \text{for} \quad 1 \leq N \leq t. \] Similarly, if \(Q(N)\) is the number of primitive elements of \(\mathbb{F}_{q}\) among \(u_{0},u_{1}, \ldots ,u_{N-1}\), the authors show that \[ \biggl| Q(N)- \frac{ \varphi(q-1)}{q-1}N \biggr| < 2.2 \cdot 2^{ \nu(q-1)}N^{1/2}q^{1/4} \qquad \text{for} \quad 1 \leq N \leq t, \] where \( \varphi(m)\) and \( \nu(m)\) denote the Euler function of \(m\) and the number of distinct prime divisors of \(m\), respectively.
0 references