682 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 59, NO. 1, JANUARY 201 3
Remark 5:
1) If
is a distinguishab le pai r, then it is necessary that
is an odd n um ber. This is because if is an even number,
then both
and are even numbers,
and so
.
2) If
is a d istinguishable pair, then is a typical
primitive pair, but the reverse is not true. F or example, it
can be verified that
is a typical primitive p air, but
not a distinguishable pair.
3) Experimental data sho w that the p ro portio n of distinguish-
able pairs
is about when runs thro ugh
all possible values between 1 and
and runs
through all odd integers between 3 and 19.
Finally, we recall the estimates of some classical exponential
sums over integer residue rings. Let
beapositiveinteger
greater than 1, and let
be the canonical additive character
over
given by ,where is an integer.
First, it is well known that the complete sum
holds for any integer . Second, the following estimates are
proved in [24].
Lemma 6 (see [24, Lemma 8.80]): For any positive integ er
,wehave
where is the natural logarithm. In particular, we have
III. DIST RIB UTION PROPERTIES O F PRIMITIVE
SEQUENCES OVER
Let be a periodic sequence over with period .For
any given element
, we say that th e element occurs
in the sequence
if there exists an integer
such that .Let denote the number of element
occurring in a complete period of the sequence ,thatis
In this section, we discuss two distribution problems of prim-
itive sequences over
, which will be shown to be useful
in Section IV . The first problem is to determine whether every
element of
occurs in a complete period of a primitive
sequence of order
over .InSectionIII-A,weshall
show that the answer is positive for sufficiently large
.Itis
clear that the answer is negative for
. The second problem
is to determine whether there exists an even element of
occurring in a complete period of a primitive sequen ce of ord er
1over
. In Section III-B, we sha ll show that the answer
to this problem is po s itive for almost all
s. The main results
of this section are based on the estimates of exponential su ms
over integer residue rings. We note that many signifi cant results
have been given on the estimate of primitive sequences over
primary residue rings and Galois rings, such as [26]–[29]. How-
ever, those results cannot be generalized to obtain the results in
this section.
A. Estimates for the Number of Given Element Occurring in a
Primitive Sequen ce Over
Lemma 7 is a well-known result of Korobov; see [25, The -
orem 13].
Lemma 7 (see [25, Theorem 13]): For any integer
,let
be a primitive sequence of order over with period
. Then, we have the estimates
Lemma 8: Let be a prime numb er and aprimitivese-
quence of order
over . Then, for any integer we have
(3)
Proof: Since the exponential sum
counts the number of the element occurring in a com-
plete period of
, (3) immediately follows from the element dis-
tribution properties of
-sequences over finite fields.
Let be a prim itive sequen c e of order over ,andlet
Given an element , it can be seen that