Period Math Hung (2015) 71:64–77 DOI 10.1007/s10998-015-0085-0

Pseudorandomness of binary sequences derived from linear recursions László Mérai1,2

Published online: 28 May 2015 © Akadémiai Kiadó, Budapest, Hungary 2015

Abstract In this paper we study the pseudorandomness of finite binary sequences derived from linear recursions. We show, that the well-distribution measures of these sequences are small. Furthermore we also show that the correlation measures of these sequences are small for small correlation orders, but if the order of the correlation is greater than the order of the linear recursion, then the correlation can be large. Keywords

Pseudorandomness · Pseudorandom measures · Linear recursion

Mathematics Subject Classification

Primary 11K45

1 Introduction In order to study the pseudorandomness of finite binary sequences Mauduit and Sárközy [6] introduced the following measures of pseudorandomness: For a given binary sequence E N = (e1 , . . . , e N ) ∈ {−1, +1} N write U (E N , t, a, b) =

t−1 

ea+ jb ,

j=0

B

László Mérai [email protected]

1

Department of Computer Algebra, Eötvös Loránd University, Pázmány Péter sétány 1/C, Budapest 1117, Hungary

2

Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenberger Strasse 69, 4040 Linz, Austria

123

Pseudorandomness of binary sequences

65

and for D = (d1 , . . . , d ) with non-negative integers 0 ≤ d1 < · · · < d write V (E N , M, D) =

M 

en+d1 en+d2 . . . en+d .

n=1

Then the well-distribution measure of E N is defined by

     t−1  ea+ jb  , W (E N ) = max |U (E N , t, a, b)| = max  a,b,t a,b,t   j=0

where the maximum is taken over all a, b, t ∈ N such that 1 ≤ a ≤ a + (t − 1)b ≤ N , and the correlation measure of order  of E N is defined as M      en+d1 en+d2 . . . en+d  , C (E N ) = max |V (E N , M, D)| = max   M,D M,D  n=1

where the maximum is taken over all D and M such that d + M ≤ N . The sequence E N possesses good pseudorandom properties, if both these measures W (E N ) and C (E N ) (at least for small ) are “small” in terms of N (in particular, both are o(N ) as N → ∞). This terminology is justified since for a truly random sequence E N √ each of these measures is  N log N . (For a more precise version of this result see [1]). Let q = p m be an odd prime power and Fq be the finite field with q elements. Let h be a positive integer and c1 , c2 , . . . , ch ∈ Fq be fixed elements. For initial values x1 , . . . , x h ∈ Fq consider the sequence (xn ) defined by the linear recursion xn = c1 xn−1 + · · · + ch xn−h , n > h.

(1.1)

In this paper we study the pseudorandomness of finite binary sequences derived from the sequences (xn ). If q = p is a prime number, Gyarmati, Peth˝o and Sárközy [4] studied the binary sequence obtained from (xn ) by using the Legendre symbol while if q is a power of 2 Folláth [2] studied the binary sequence obtained from (xn ) by using additive characters (see also [3]). In general, it is hard to control the pseudorandom measures of the binary sequences derived from (xn ). However we can give a large class of sequences whose pseudorandom measures can be estimated. Namely, as in [4], suppose that the roots of the characteristic polynomial have h distinct roots in Fq∗ : ϑ1 , . . . , ϑh . Then there exist a1 , . . . , ah ∈ Fq such that xn = a1 ϑ1n + · · · + ah ϑhn , n ∈ N. Choosing ϑ ∈ Fq such that each root ϑi can be written as a power of ϑ: ϑi = ϑ ki (ki ∈ N) (for example ϑ can be chosen as a primitive root), the sequence (x n ) can be written as xn = a1 ϑ k1 n + · · · + ah ϑ kh n = f (ϑ n ), n ∈ N,

(1.2)

f (x) = a1 x k1 + · · · + ah x kh .

(1.3)

where On the other hand if we have a polynomial f (x) of the form (1.3), then the sequence defined by (1.2) satisfies a linear recursion of the form (1.1) (see [4]). Thus underlining the condition about the roots of the characteristic polynomial of the recursion (1.1), throughout this paper we define the sequence (xn ) by (1.2) where f (x) ∈ Fq [x], ϑ ∈ Fq∗ . If T ∈ N is the order of ϑ, then the sequence (xn ) will be a purely periodic sequence with period T , and thus we will consider just the first T elements of (xn ).

123

66

L. Mérai

Gyarmati, Peth˝o and Sárközy in [4] define a binary sequence E T = {e1 , e2 , . . . , eT } by  n  f (ϑ ) if p  f (ϑ n ) p en = (1.4) 1 otherwise,   where p· is the Legendre symbol. They proved Theorem 1.1 Suppose that f (x) is not of the form cx α (g(x))2 with c ∈ F p , α ∈ N, g(x) ∈ F p [x]. Then W (E T ) < 5 deg f p 1/2 log p. Furhtermore, let β ∈ N be the largest integer with x β | f (x) (thus x β+1  f (x)). Suppose that at least one of the following conditions holds 1.  = 2 and f (x)/x β is not of the form g(x σ ) or cx α (g(x))2 with σ, α ∈ N, (σ, T ) ≥ 2, c ∈ F p and g(x) ∈ F p [x]. 2. f (x)/x β is not of the form cx α (g(x))2 with α ∈ N, c ∈ F p and g(x) ∈ F p [x], T is a prime and either min{(4 deg f ) , (4)deg f } ≤ T or 2 is a primitive root modulo T . 3. deg f − β (the degree of the polinomial f (x)/x β ) and  is odd. Then C (E T ) ≤ 5 deg f p 1/2 log p. (We remark that a fourth, quite technical condition was given in the theorem as well, which depends on the factorization of the polynomial f (x)). Later Folláth in [2] defined the additive analogue of sequence (1.4) over a binar field: let α ∈ F∗2k be of order T , f (x) ∈ F2k [x], ψ an additive character and define the sequence E T = {e1 , e2 , . . . , eT } by (1.5) en = ψ( f (α n )). He proved Theorem 1.2 Let Fq be a finite field of characteristic 2 whose multiplicative group has prime order. Let ψ be a non-trivial additive character and α ∈ Fq a primitive root. Let f (x) ∈ Fq [x] be a polynomial of degree d ≥ log q and let the coefficients of its terms be zero if and only if the term has an even exponent. If the sequence E q−1 = {e1 , e2 , . . . , eq−1 } is defined by (1.5), then we have W (E q−1 ) ≤ 9dq 1/2 log q. Furthermore, if  ≤ d + 1, then c (E q−1 ) ≤ 9dq 1/2 log q. In this paper we study the pseudorandom properties of the analogue of the sequence (1.5), where the characterisitc of the finite field is odd. Let us fix a basis β1 , . . . , βm in Fq over F p (whose elements we identify with the field of the modulo p residue classes) and define the boxes B j , j = 1, . . . , m by ⎧ ⎫ m ⎨ ⎬ p−1 , u j+1 , . . . , u m ∈ F p u i βi : 0 < u j ≤ Bj = ⎩ ⎭ 2 i= j

123

Pseudorandomness of binary sequences

and let B =

m j=1

67

B j . Then define the binary sequence (en ) by  en =

+1 if f (ϑ n ) ∈ B ∪ {0} −1 otherwise,

(1.6)

where f (x) ∈ Fq [x], ϑ ∈ Fq∗ . First we estimate the well-distribution measure of E T . This estimate will be non-trivial if the order T of ϑ is large and the degree of f (x) is not so large. Theorem 1.3 Let f (x) ∈ Fq [x] such that  q−1  f cx T  = A p (x) − A(x) + b, for c, b ∈ Fq , A(x) ∈ Fq .

(1.7)

Then W (E T )  m deg f

√ q log p log T.

As in the case when the finite field has characteristic 2, we work with the restriction of the polynomial f (x) to get a small correlation measure, however the restrictions can be formulated in terms of the indices of the non-zero coefficients of the polynomial. Theorem 1.4 For the polynomial f (x) =

deg f i=0

f i x i define s = s f by

s = max{l ∈ N : ∀x1 , . . . , xl ∈ Fq∗ , xi  = x j , i  = j, rank{(x1r , . . . , , xlr ) : deg f / p < r ≤ deg f, fr  = 0, p  r } = l}. If  < s, then

C (E T )  deg f

√ q log p log T.

(1.8)

Clearly s is not greater than the number of non-zero coefficients of f but s can reach this bound, for example if the indices of the non-zero coefficients of f (x) which are greater than deg f / p, are not divisible by p and they form an arithmetic progression. Corollary 1.5 Let f (x) ∈ Fq [x] be of degree deg f < p with non-zero coefficients. Then (1.8) holds with  < deg f . On the other hand higher order correlation measures can be large. Theorem 1.6 For any integer k there exists a constant c = c(k) > 0 such that if the characteristic p of Fq is large enough, f (x) ∈ Fq is a polynomial of degree k such that f (0) = 0 and the number of the non-zero coefficients is s = 2t − 1, ϑ ∈ Fq is a primitive root, then Cs+1 (E q−1 ) c · q.

2 Auxiliary lemmas Throughout the paper for α ∈ R let e(α) = exp(2πiα) and for r ∈ N let er (x) = e(x/r ). The following lemma is the additive analogue of Lemma 1 in [4].

123

68

L. Mérai

Lemma 2.1 Let Fq be a finite field of characteristic p, ψ a non-trivial additive character of Fq , ϑ ∈ Fq∗ of order T , f (x) ∈ Fq [x] such that  q−1  f x T  = A p (x) − A(x) + b, for , b ∈ Fq , A(x) ∈ Fq . Then for K ≤ T we have

  K   √  n  ψ( f (ϑ )) ≤ 4 deg f q log T.    n=1

The proof is based on the following hybrid character sum estimate, see [8]. Lemma 2.2 Let Fq be a finite field of character p, ψ be a non-trivial additive character, χ a multiplicative character of order d ≥ 2. Let f (x), g(x) ∈ Fq [x] be polynomials such that f (x)  = A p (x) − A(x) + b, for A(x) ∈ Fq , b ∈ Fq or g(x)  = c · B d (x), for B(x) ∈ Fq , c ∈ Fq . Then

      ∗  ≤ 2 (deg f + z)√q,  ψ( f (x))χ(g(x))    x∈Fq

where the summation is taken over all elements of Fq except for the roots of g(x), and z is the number of the distinct roots of g(x). We also need the following lemma (Lemma 7 in [7]). Lemma 2.3 If ϑ ∈ Fq∗ is of order T , χ is a multiplicative character of order T , then T −1  y=1

1 < T log T. |1 − χ(ϑ y )|

Proof of Lemma 2.1 Since the order of ϑ is T | q − 1, there exists a multiplicative character χ of order T such that χ(ϑ) = e(1/T ). (2.1) Moreover, for n = 1, . . . , T , ϑ n runs over all the T different and for a fixed ϑ and n the equation ϑn = x has exactly

q−1 T -th

powers (except for 0)

q−1 T

q−1 T

solutions in x. Thus for a fixed γ (0 ≤ γ < q − 1) we have    T         q−1 q−1 T   n γn γ   T T ψ( f (ϑ ))χ(ϑ ) = ψ( f (x ))χ(x )    q − 1  ∗  n=1

x∈Fq

T q −1 √ √ ≤2 deg f q = 2 deg f q q −1 T by Lemma 2.2.

123

(2.2)

Pseudorandomness of binary sequences

69

By (2.1) we have T −1 

χ(ϑ γ (n−y) ) =

γ =0



T, if T | n − y, 0, otherwise,

thus by (2.2) and by Lemma 2.3 we have    T  K  K T −1       1   ψ( f (ϑ n )) =  ψ( f (ϑ n )) χ(ϑ γ (n−y) )     T  n=1 n=1 y=1 γ =0      T −1 K T    1   −γ y   n γn  ≤ χ(ϑ ) ψ( f (ϑ ))χ(ϑ )      T  n=1 γ =0  y=1  T −1  1   1 − χ(ϑ −γ K )  √ √ ≤ 2 deg f q · + 2 deg f q   −γ T 1 − χ(ϑ )

(2.3)

γ =1

T −1 1 1  √ q· T |1 − χ(ϑ −γ )| γ =1 √ ≤ 4 deg f q log T.

≤ 4 deg f

  In order to express the terms of the sequence E T with a character sum representation, we will need the following extension of Lemma 2 in [5]. Lemma 2.4 For any a ∈ Fq we have

 1  +1 if a ∈ B ∪ {0} v(h)ψ(ha) = −1 otherwise, q h∈Fq

where ψ(x) = e p (Tr(x)) is an additive character and Tr(x) is the absolute trace of Fq . Here v(0) = 1. Moreover, for r = 1, . . . , m let Mr = {h ∈ Fq : Tr(hβ1 )  = 0, . . . , Tr(hβr )  = 0, Tr(hβr +1 ) = · · · = Tr(hβm ) = 0}. Then, for h ∈ Mr , we have

  r) (−1)Tr(hβr ) − cos π T r (hβ p   v(h) = 1 + i p m−r T r (hβr ) sin π p

and for h ∈ / rm=1 Mr ∪ 0, v(h) = 0. Furthermore, if we represent the elements of F p by the absolute least residues of integers modulo p: F p = {a ∈ Z : |a| < p/2}, then for h ∈ Mr  m−r O(  pm−r+1) if Tr(hβr ) is even, v(h) = (2.4) p O Tr(hβr ) if Tr(hβr ) is odd and for a fixed B ∈ R and large enough p, if 1 ≤ | Tr(hβr )| < B and Tr(hβr ) is odd, we have   2i πi Tr(hβr ) m−r −1 v(h) = 1 − (2.5) + O B 3 p m−r −3 . p m−r +1 + p π Tr(hβr ) 6

123

70

L. Mérai

Proof Since for a, b ∈ Fq

 1  1 if a = b ψ(h(a − b)) = 0 otherwise, q h∈Fq

we have 1  q

 1−

h∈Fq







ψ(hb) − ψ(−hb) ψ(ha) =

b∈B

+1 if a ∈ B ∪ {0} −1 otherwise,

Then v(h) =1−



ψ(hb) − ψ(−hb) = 1 −

b∈B

=1−

m  

m 



⎛



ψ ⎝h

j=1 1≤u j < p/2 u j+1 ,...,u m ∈F p

=1−

m  j=1

ψ(hb) − ψ(−hb)

j=1 b∈B j

⎛ ⎝



m 

⎞

⎛

u l βl ⎠ − ψ ⎝−h

l= j

⎞ ⎛

ψ(hu j β j ) − ψ(−hu j β j )⎠ · ⎝

1≤u j < p/2

m 

⎞ u l βl ⎠

l= j



u j+1 ,...,u m ∈F p

⎛

m 

ψ ⎝h

⎞⎞ u l βl⎠⎠ .

l= j+1

(2.6) The first factor of the sum is  ψ(hu j β j ) − ψ(−hu j β j ) = 1≤u j < p/2



e p (u j Tr(hβ j )) − e p (−u j Tr(hβ j )).

1≤u j < p/2

(2.7) If Tr(hβ j )  = 0, then (2.6) is a geometric series. Summing, similarly to [5], we get that (2.7) is   r) (−1)Tr(hβr ) − cos π T r (hβ p   −i . r) sin π T r (hβ p The second factor of the sum in (2.6) is ⎛ ⎞ m m     ψ ⎝h u l βl ⎠ = e p (u i Tr(hβi )). u j+1 ,...,u m ∈F p

l= j+1

(2.8)

i= j+1 u i ∈F p

If each sum is trivial (i.e. Tr(hβ j ) = 0), then (3.5) is p m− j . Otherwise, if there is a term where Tr(hβi )  = 0, then  1 − e p ( p Tr(hβi )) e p (u i Tr(hβi )) = = 0. 1 − e p (Tr(hβi )) u i ∈F p

Finally, (2.4) and (2.5) follow from the expansion −2 x −1 − cos(x) = + + O(x 3 ), as x → 0. sin(x) x 6  

123

Pseudorandomness of binary sequences

71

We will need the notion of Hasse derivation. Lemma 2.5 Let f (x) =

n

i=0 f i x

∈ Fq [x] and r ∈ N. Define

i

D (r ) f =

n    i i=r

r

f i x i−r ∈ Fq [x].

The Hasse derivation D (r ) : Fq [x] → Fq [x] satisfies the following properties (a) For f, g ∈ Fq [x] and λ ∈ Fq : D (r ) ( f + g) = D (r ) f + D (r ) g and D (r ) (λ f ) = λD (r ) f ; (b) For f ∈ Fq [x] and λ ∈ Fq : 

deg f

f (x) =

(D (i) f )(λ)(x − λ)i ;

i=0

(c) If we have (D (i) f )(λ) = 0 for all i ≥ 0, then f = 0.

3 Proofs of Theorems 1.3 and 1.4 Proof of Theorem 1.3 For fixed integers a, b, t ∈ N where 1 ≤ a ≤ a + (t − 1)b ≤ T , by Lemma 2.4 we have U (E T , t, a, b) =

t−1 

ea+ jb =

j=0

=

t−1  1  v(h)ψ(h f (ϑ a+ jb )) q h∈Fq

j=0

1  v(h) q ∗ h∈Fq

t−1 

ψ(h f (ϑ a+ jb )) +

j=0

t v(0). q

(3.1)

If h  = 0, then the inner sum is non-trivial, thus by Lemmas 2.1 and 2.4 we have    t−1      1 |v(h)|  ψ(h f (ϑ a+ jb )) + |v(0)| |U (E T , t, a, b)| ≤ q   ∗ h∈Fq

 deg f

j=0

m  1  p m−r +1 √ . q log T q Tr(hβr ) r =1

(3.2)

h∈Mr

As h runs over Mr , Tr(hβr ) takes on each value of F∗p , pr −1 times. Thus (3.2) is  deg f

m   1 √ √ q log T  m deg f q log T log p a ∗ r =1 a∈F p

which proves the theorem.

 

Proof of Theorem 1.4 Let  ≤ s and M, d1 , . . . , d ∈ N such that d1 < · · · < d ≤ T − M. Then by Lemma 2.4 we have

123

72

L. Mérai

V (E T , M, D) =

M 

en+d1 . . . en+d

n=1



1 =  q

v(h 1 ) . . . v(h  )

h 1 ,...,h  ∈Fq

M  n=1

ψ

  

 h i f (ϑ

n+di

) .

(3.3)

i=1

If h 1 = · · · = h  = 0, then the sum is trivial. On the other hand we show that if (h 1 , . . . , h  )  = (0, . . . , 0), the polynomial in the argument is  

h i f (ϑ di x

q−1 T

)  = A(x) p − A(x), for A(x) ∈ Fq [x], b ∈ Fq .

(3.4)

i=1

Indeed, let deg f q−1 p T

A(x) =



ajx j

j=0

and consider the equation  

h i f (ϑ di x

q−1 T

) = A p (x) − A(x) + b.

(3.5)

i=1

For r > deg f / p, p  r , the r ·  

q−1 T -th

Hasse derivation of (3.5) in x = 0 is

  q−1 h i D (r (q−1)/T ) f (ϑ di x T ) (0) = 0

i=1

i.e.

 

h i fr ϑ r di = 0.

(3.6)

i=1

For those r ∈ N which fr  = 0, (3.6) is a system of linear equations in h 1 , . . . , h   

h i ϑ r di = 0, deg f / p < r ≤ deg f : p  r, fr  = 0.

(3.7)

i=1

Since  ≤ s, the coefficient matrix of the system of linear equations (3.7) has rank , so it only has the trivial solution (h 1 , . . . , h  ) = (0, . . . , 0). By (3.3), (3.4) and Lemmas 2.1, 2.4 we have M        1   n+di |v(h 1 )| . . . |v(h  )|  ψ h i f (ϑ )  |V (E T , M, D)| ≤    q h 1 ,...,h  ∈Fq (h 1 ,...,h  ) =(0,...,0)

+ |v(0)| 1 √  deg f q log T  q

123

n=1

 h 1 ,...,h  ∈Fq (h 1 ,...,h  ) =(0,...,0)

i=1

|v(h 1 )| . . . |v(h  )|

Pseudorandomness of binary sequences

73

⎛ ⎞ 1 ⎝ √  deg f q log T  |v(h)|⎠ q h∈Fq

√  deg f q log T (log p)

(3.8)  

which proves the theorem.

4 Proof of Theorem 1.6 In this section let us represent the elements of F p by the absolute least residues of integers modulo p: F p = {a ∈ Z : |a| < p/2}. Moreover, for an integer n ∈ Z, let r p (n) denote the unique integer |r | < p/2 such that r ≡ n (mod p). Proof For a fixed z ≤ k and 1 ≤ j1 < · · · < jz = k consider the Vandermonde matrix ⎛

1 ⎜1 ⎜ L = L(z, j1 , . . . , jz ) = ⎜ . ⎝ .. 1

3 j1 3 j2 .. . 3 jz

··· ··· .. . ···

⎞ 3z j1 z j 3 2⎟ ⎟ z×z+1 . .. ⎟ ∈ Z . ⎠ 3 z jz

Then there exists a z + 1-tuple (u 1 , . . . , u z+1 ) ∈ Z such that u 1 · · · u z+1  = 0, gcd(u 1 , . . . , u z+1 ) = 1 and all the solutions of ⎞ ⎛ ⎞ ⎛ 0 y1 ⎜ .. ⎟ ⎜ .. ⎟ L⎝ . ⎠=⎝.⎠ 0 yz+1 in Qz+1 are of the form (λu 1 , . . . , λu z+1 ) with λ ∈ Q. We remark that the possible z+1-tuples depend only on k. Let f (x) ∈ Fq [x] be a polynomial of degree k with s many non-zero coefficients such that the constant term of f (x) is 0. Let f i1 , … f is be the non-zero coefficients of f (x): f (x) =

s 

f il x il .

l=1

If p is sufficiently large, then the coordinates of (u 1 , . . . , u z+1 ) belonging to the matrix L(s, i 1 , . . . , i z+1 ) are non-zero modulo p. In order to prove the theorem, we have to show that there exist integers 0 ≤ d1 < . . . < ds+1 and M such that V (E T , M, D) is large. By the same argument as in the proof of Theorem 1.4, V (E T , M, D) can be large, if there are elements h 1 , . . . , h s+1 ∈ Fq not all of them are zero, such that the polynomial h 1 f (ϑ d1 x) + · · · + h s+1 f (ϑ ds+1 x)

(4.1)

is of the form A p (x) − A(x) + b for A(x) ∈ Fq [x] and b ∈ F i.e. the polynomial (4.1) is the constant zero polynomial. We also saw that the elements h 1 , . . . , h s+1 ∈ Fq for which the polynomial (4.1) is the zero polynomial are the solutions of

123

74

L. Mérai

⎛

ϑ d1 i 1 ⎜ ϑ d1 i 2 ⎜ ⎜ . ⎝ .. ϑ d1 i s

ϑ d2 i 1 ϑ d2 i 2 .. . ϑ d2 i s

··· ··· .. . ···

⎞⎛ ⎞ ⎛ ⎞ ϑ ds+1 i1 0 h1 d i ⎜ h2 ⎟ ⎜ 0 ⎟ ϑ s+1 2 ⎟ ⎟⎜ ⎟ ⎜ ⎟ .. ⎟ ⎜ .. ⎟ = ⎜ .. ⎟ ⎠ ⎝ . ⎠ ⎝.⎠ . d i s s+1 0 h s+1 ϑ

(4.2)

over Fq . Choosing di = (i − 1) logϑ 3 for i = 1, . . . , s + 1, the coefficient matrix of the system of linear equations (4.2) is L(s, i 1 , . . . , i s ) whence the solutions of (4.2) form a one dimensional linear space over Fq . Let γ1 , . . . , γm ∈ Fq be a basis over F p such that Tr(γi βi ) = 1 for i = 1, . . . , m and Tr(γi β j ) = 0 for i  = j. Then the solutions of (4.2) are ⎫ ⎧ m ⎬ ⎨ a j · (u 1 γ j , . . . , u s+1 γ j ) : a1 , . . . , am ∈ F p ≤ Fqs+1 . H= ⎭ ⎩ j=1

For r = 1, . . . , m let ⎧ ⎫ r ⎨ ⎬ a j · (u 1 γ j , . . . , u s+1 γ j ) : a1 , . . . , ar ∈ F∗p ⊆ Mrs+1 ⊆ Fqs+1 Hr = ⎩ ⎭ j=1

and let H  = H \ rm=1 Hr ∪ (0, . . . , 0). Let M ∈ N, then we have 

1

V (E T , M, D) =

q s+1

v(h 1 ) . . . v(h s+1 )

h 1 ,...,h s+1 ∈Fq

M 

ψ

 s+1 

n=1

 h i f (ϑ

n+di

) .

(4.3)

i=1

If (h 1 . . . , h s+1 ) ∈ / H , then the polynomial (4.1) is not constant and thus the character sum can be estimated non-trivially. We get V (E T , M, D) =



1 q s+1

v(h 1 ) . . . v(h s+1 )

(h 1 ,...,h s+1 )∈H

M 

ψ

 s+1 

n=1

 h i f (ϑ

n+di

)

i=1

√ + O(deg f q log q logs+1 p)  M √ v(h 1 ) . . . v(h s+1 ) + O(deg f q log q logs+1 p). = s+1 q

(4.4)

(h 1 ,...,h s+1 )∈H

If (h 1 . . . , h s+1 ) ∈ H  , then one of the coordinates h i ∈ / whence the main term of (4.4) is 

M q s+1

(h 1 ,...,h s+1 )∈H

v(h 1 ) . . . v(h s+1 ) =

m M 

q s+1

m

r =1



Hr , and thus v(h i ) = 0,

v(h 1 ) . . . v(h s+1 ). (4.5)

r =1 (h 1 ,...,h s+1 )∈Hr

Let 1 ≤ A < p be a parameter to be fixed later. For r = 1, . . . , m let ⎧ ⎫ r ⎨ ⎬ a j · (u 1 γ j , . . . , u s+1 γ j ) : a1 , . . . , ar −1 ∈ F∗p , 1 ≤ |ar | < A . HrA = ⎩ ⎭ j=1

123

Pseudorandomness of binary sequences

75

Let us consider the contribution of the s + 1-tuples (h 1 , . . . , h s+1 ) ∈ Hr \ HrA (where now A ≤ |ar | < p/2). If there is an index l0 such that u l0 = 1, then |v(h l0 )| 

p m−r +1 p m−r +1 p m−r +1 = < . | Tr(h l0 βr )| |ak | A

Thus by Lemma 2.4 and the Hölder inequality we have 

1 q s+1

v(h 1 ) . . . v(h s+1 ) 

(h 1 ,...,h s+1 )∈Hr \HrA

p m−r +1 = Aq s+1

p m−r +1 Aq s+1





|v(h l )|

(h 1 ,...,h s+1 )∈Hr \HrA l =l0

 ⎛ ⎞   r    v ⎝ ⎠ a j u l γ j    A≤|ar |< p/2 a1 ,...,ar−1 ∈F p l=l0  j=1 





p (s+1)(m−r +1 ) Aq s+1



1 |r p (ar u l )| A≤|ar |< p/2 l=l0 ⎛ ⎞1/s 1 p (s+1)(m−r +1 )  ⎝  ⎠ . ≤ Aq s+1 |r p (ar u l )|s



l=l0

(4.6)

|ar |< p/2

If ar runs in Fq∗ , then |r p (ar u l )| also takes on each value of Fq∗ , thus we have that the left hand side of (4.5) is p (s+1)(m−r +1 ) Aq s+1

 1<|a|< p/2

1 1  . s (s+1)(r −1) |a| Ap

(4.7)

By (4.4), (4.5), (4.6), (4.7) we have V (E T , M, D) m  M  = s+1 v(h 1 ) . . . v(h s+1 ) q r =1 (h 1 ,...,h s+1 )∈HrA   M √ +O m + O(deg f q log q logs+1 p). A

(4.8)

For r = 1, . . . , m, let ⎧ ⎫ r ⎨ ⎬ a j · (u 1 γ j , . . . , u s+1 γ j ) : a1 , . . . , ar −1 ∈ F∗p , 1 ≤ |ar | < A, ar is even . Hre = ⎩ ⎭ j=1

Consider the contribution of the s + 1-tuples (h 1 , . . . , h s+1 ) ∈ Hre in (4.8). Since Tr(h l βr ) = ar u l is even, by Lemma 2.4 we have m M 

q s+1



r =1 (h 1 ,...,h s+1 )∈Hre

v(h 1 ) . . . v(h s+1 ) 

m M p (s+1)(m−r )  e MA |Hr |  m s+1 . s+1 q p

(4.9)

r =1

We remark that if there is an even u r0 , then, by the same argument, the r0 -th term of (4.8) will also be small. By (4.8) and (4.9) we have

123

76

L. Mérai

V (E T , M, D) m  M  = s+1 v(h 1 ) . . . v(h s+1 ) q r =1 (h 1 ,...,h s+1 )∈HrA \Hre     MA M √ + O m s+1 + O(deg f q log q logs+1 p). +O m p p

(4.10)

Let us assume that all of the u r ’s are odd, and one of them is 1. Then consider the r -th term in the sum in (4.10). If r = 1, then  1 v(h 1 ) . . . v(h s+1 ) q s+1 e A (h 1 ,...,h s+1 )∈H1 \H1

=

q s+1 

=



1

s+1 

(h 1 ,...,h s+1 )∈H1A \H1e l=1

−2i π

s+1 s+1  l=1

1 ul

 1≤|a|
 −2i p m πi Tr(hβ1 ) m + p + O(A3 p m−4 ) (4.11) π Tr(h l β1 ) 6

1 + O(1). |a|s+1

Since s ≤ k, and the possible values of u l depend on k, we have that the first term is c(k). For 1 < r ≤ m the r -th term in the sum in (4.10) is  1 v(h 1 ) . . . v(h s+1 ) s+1 q A e (h 1 ,...,h s+1 )∈Hr \Hr





pr −1 q s+1

 s+1  p m−r +1  s+1  1 1  s(r −1) |r p (ar u l )| |r p (ar u l )| p ∗

1 p s(r −1)

(4.12)

a∈Fq l=1

1<|a|
 s+1  1  1 1 = O( p −s(r −1) ).  s(r −1) s+1 |a| |a| p ∗ ∗

a∈Fq l=1

a∈Fq

Then if all of the u r ’s are odd, and one of them is 1, then by (4.10), (4.11) and (4.12) we have     AM M V (E T , M, D) c(k)M + O m + O m s+1 A p √ m(s+1) p). (4.13) + O(deg f q log q log If M q and A is large enough (independently of p), then the main term dominates the error terms. By using the following lemma we show that all of the u r ’s are odd, and one of them is 1. Lemma 4.1 For f (x) ∈ Fq [x] and a ∈ Fq with ord(a) > deg f let : Fq [x] → Fq [x] be the following operator: f (x) = f (ax) − a deg f f (x), and write 1 = , r = ◦ r −1 . The r operators satisfy the following properties (1) If the number of non-zero coefficients of f (x) is s, then the number of non-zero terms of r ( f (x)) is at most s − r .

123

Pseudorandomness of binary sequences

(2) If f (x) =

s j=1

77

f j x α j , f j ∈ Fq∗ j = 1, . . . , s, then

r f (x) =



r  (−1) j f (a r − j x)



a αi .

I ⊂{s−r +1,...,s} i∈I |I |= j

j=0

Proof The statements can be verified by straightforward calculation.

 

Apply the lemma with a = 3. If p is large enough, the order of 3 is larger than k. Since the number of non-zero coefficients of f (x) is s, then s f (x) =

s 

(−1) j f (a s− j x)

u j+1 = (−1) j



a αi

I ⊂{1,2,...,s} i∈I |I |= j

j=0

is the zero polynomial. Then we get







3αi .

I ⊂{1,2,...,s} i∈I |I |= j

Here if p is large enough, each term is odd, and the number of the terms      t  s s 2 −1 = = s −i i i is also odd. Moreover u 1 = 1.

 

Acknowledgments Research partially supported by Hungarian National Foundation for Scientific Research, Grant No. K100291 and by the Momentum (Lendület) fund of the Hungarian Academy of Sciences

References 1. N. Alon, Y. Kohayakawa, C. Mauduit, C.G. Moreira, V. Rödl, Measures of pseudorandomness for finite sequences: typical values. Proc. Lond. Math. Soc. 95, 778–812 (2007) 2. J. Folláth, Construction of pseudorandom binary sequences using additive characters over G F(2k ). Period. Math. Hung. 57(1), 73–81 (2008) 3. J. Folláth, Construction of pseudorandom binary sequences using additive characters over G F(2k ) II. Period. Math. Hung. 60(2), 127–135 (2010) 4. K. Gyarmati, A. Peth˝o, A. Sárközy, On linear recursion and pseudorandomness. Acta Arith. 118(4), 359– 374 (2005) 5. C. Mauduit, J. Rivat, A. Sárközy, Construction of pseudorandom binary sequences using additive characters. Monatshefte Math. 141(3), 197–208 (2004) 6. C. Mauduit, A. Sárközy, On finite pseudorandom binary sequences I: measures of pseudorandomness, the Legendre symbol. Acta Arith. 82, 365–377 (1997) 7. L. Mérai, Construction of pseudorandom binary lattices based on multiplicative characters. Period. Math. Hung. 59, 43–51 (2009) 8. G. I. Perel’muter, On certain character sums. Uspehi Mat. Nauk 18 no. 2 (110), 145–149 (1963)

123