Information Technology Reference
In-Depth Information
Multiplicative Character Sums of Recurring
Sequences with Redei Functions
Domingo Gomez
1
and Arne Winterhof
2
1
Faculty of Sciences, University of Cantabria, E-39071 Santander, Spain
domingo.gomez@unican.es
2
Johann Radon Institute for Computational and Applied Mathematics (RICAM)
Austrian Academy of Sciences, Altenbergerstr. 69, 4040 Linz, Austria
arne.winterhof@oeaw.ac.at
Abstract.
We prove a new bound for multiplicative character sums of
nonlinear recurring sequences with Redei functions over a finite field
of prime order. This result is motivated by earlier results on nonlinear
recurring sequences and their application to the distribution of powers
and primitive elements. The new bound is much stronger than the bound
known for general nonlinear recurring sequences.
1
Introduction
Let
p
be a prime, IF
p
the finite field of
p
elements, and
F
(
X
) a rational function
over IF
p
.Let(
u
n
) be the sequence of elements of IF
p
obtained by the recurrence
relation
u
n
+1
=
F
(
u
n
)
,
n
≥
0
,
(1)
with some initial value
u
0
∈
IF
p
. Obviously, this sequence eventually becomes
periodic with least period
T
p
, but we may restrict ourselves to the case where
(
u
n
) is purely periodic since otherwise we can consider a shift of the sequence.
Let
χ
be a nontrivial multiplicative character of IF
p
. We consider character
sums
≤
T
−
1
S
χ
=
χ
(
u
n
)
.
n
=0
Bounds on
S
χ
can be applied to obtain results on the distribution of powers and
primitive roots modulo
p
in the sequence (
u
n
) in a standard way, see e.g. [8].
In the special case of
linear recurring sequences
these sums are well-studied,
see [3,4,11].
When
F
(
X
)
IF
p
[
X
] is a polynomial of degree at least 2, in [8] under some
natural restrictions on
F
(
X
) the general but rather weak upper bound
S
χ
=
O
T
1
/
2
p
1
/
2
(log
p
)
−
1
/
2
∈
and an analog for sums over parts of the period were given which are nontriv-
ial whenever
T>p
(log
p
)
−
1
. Here the implied constant depends only on the
