Acta Math. Hungar., 156 (1) (2018), 204–219 Acta Math. Hungar. https://doi.org/10.1007/s10474-018-0834-7 DOI: 0 First published online May 25, 2018

LARGE FAMILIES OF SUBSETS ARISING FROM WOODS PROBLEM AND THEIR PSEUDORANDOMNESS Y. CAO and H. LIU∗ School of Mathematics, Northwest University, Xi’an 710127, Shaanxi, P. R. China e-mails: [email protected], [email protected] (Received February 2, 2018; revised March 17, 2018; accepted March 19, 2018)

Abstract. We introduce large families of subsets arising from Woods problem and study their cardinalities. Estimates of character sums over the subsets are given. We study the pesudorandom properties of the subsets and show that their well-distribution measures are very high.

1. Introduction Let q > 2 be an integer. For any integer a with (a, q) = 1, there exists unique integer a such that 1 ≤ a ≤ q and aa ≡ 1 (mod q). Let φ(q) be the Euler function, and let δ be a real constant with 0 < δ ≤ 1. In 1994 A. C. Woods asked whether the limit    {a ∈ Z : 1 ≤ a ≤ q, (a, q) = 1, |a − a| < δq} lim n→∞ φ(q) exists as q → ∞?   Define A(δ, q) = a ∈ Z : 1 ≤ a ≤ q, (a, q) = 1, |a − a| < δq . W. Zhang [11] proved the asymptotic formula   1  1 = φ(q)δ(2 − δ) + O q 2 d2 (q) log2 q , a∈A(δ,q)

∗ Corresponding

author. This work is supported by National Natural Science Foundation of China under Grant No. 11571277, and the Science and Technology Program of Shaanxi Province of China under Grant No. 2016GY-080 and 2016GY-077. Key words and phrases: Woods problem, subset, pseudorandomness, exponential sum, character sum. Mathematics Subject Classification: 11K45, 11A07, 11L07. c 2018 0236-5294/$ 20.00 © � 0 Akad´ emiai Kiad´ o, Budapest 0236-5294/$20.00 Akade ´miai Kiado ´, Budapest, Hungary

2

LARGEY.FAMILIES SUBSETS CAO and OF H. LIU

205

where d(q) is the divisor function. Let l ≥ 0 be a real number. W. Zhang [12] obtained the mean value formula 

|a − a|l = 2φ(q)q l

a∈A(δ,q)

 δ l+1

l+1

−

  1 δ l+2  + O q l+ 2 d2 (q) log2 q . l+2

Let χ be a non-principal Dirichlet character modulo q. P. Xi and Y. Yi [9] studied the character sums over A(δ, q), and showed that  1 χ(n) ≪ q 2 d2 (q) log(δq). n∈A(δ,q)

Let λ, δ be real numbers with 0< λ, δ ≤ 1, and let m, q be integers such that m ≥ 2 and q > max [ λ1 ], [ 1δ ] . Denote by Rq (x) the least non-negative residue of x modulo q, and define   Aλ,δ,m,q = a ∈ Z : 1 ≤ a ≤ λq, (a, q) = 1, |a − Rq (am )| ≤ δq . Z. Xu [10] studied the distribution of the difference of an integer and its m-th power mod q over incomplete intervals, and proved that  |a − Rq (am )|k a∈Aλ,δ,m,q

= φ(q)q k



P



[0,1]2

  1 1 |x − y|k dx dy + Oδ,λ,k mω(q)+ 2 q k+ 2 d(q)(log q)3 ,

where ω(q) denotes the number of different prime factors of q, and P is the parallelogram with vertices (0, −δ), (λ, λ − δ), (λ, λ + δ) and (0, δ). The first purpose of this paper is to give generalizations on the above results. Theorem 1.1. Assume that p is a prime number, χ is a non-principal Dirichlet character modulo p, δ is a fixed real number with 0 < δ ≤ 1, f (x), g(x) ∈ Fp [x] with deg(f ) ≥ 2 and deg(g) ≥ 1. Define Vf = {a ∈ Z : 1 ≤ a ≤ p, |a − Rp (f (a))| < δp}, Vg = {a ∈ Z : 1 ≤ a ≤ p, (g(a), p) = 1, |a − g(a)| < δp}. Then we have

(1.1) (1.2)

  1 |Vf | = δ(2 − δ)p + O deg(f )p 2 (log p)2 ,   1 |Vg | = δ(2 − δ)p + O deg(g)p 2 (log p)2 ,

Acta Mathematica Hungarica

Acta Mathematica Hungarica 156, 2018

206

(1.3)

CAO and OF H. LIU LARGEY.FAMILIES SUBSETS

3

1



χ(n) ≪ deg(f )p 2 (log p)2 ,



χ(n) ≪ deg(g)p 2 (log p)2 .

n∈Vf

(1.4)

1

n∈Vg

According to (1.3) and (1.4), it is natural to expect that Vf and Vg behave like a random subset of {1, 2, . . . , p}. In a series of papers C. Dartyge and A. S´ark¨ozy studied pseudorandom measures of subsets. For details, let R ⊂ {1, 2, . . . , N } and define the sequence  |R| N |R| ,− EN = EN (R) = {e1 , e2 , . . . , eN } ∈ 1 − N N by

 1 − |R| N , en = |R| −N,

for n ∈ R, for n ∈ � R.

C. Dartyge and A. S´ark¨ ozy [3] introduced the measures of pseudo-randomness: The well-distribution measure of the subset R is defined by    t−1   ea+jb , W (R, N ) = max  a,b,t

j=0

where the maximum is taken over all a, b, t ∈ N with 1 ≤ a ≤ a + (t − 1)b ≤ N . The correlation measure of order k of the subset R is defined by     M en+d1 · · · en+dk , Ck (R, N ) = max  M,D n=1

where the maximum is taken over all D = (d1, . . . , dk ) and M with 0 ≤ d1 < · · · < dk ≤ N − M . The subset R is considered as a pseudorandom subset if both W (R, N ) and Ck (R, N ) (at least for small k) are “small” in terms of N (ideally O(N 1/2+ε )). Later many pseudorandom subsets were given and studied (see [1,2,4–7] for details). The main purpose of the paper is to study the pesudorandom properties of Vf and Vg . Theorem 1.2. Assume that p is a prime number, f (x), g(x) ∈ Fp [x] with deg(f ) ≥ 2 and deg(g) ≥ 1. Define  1  Vf = a ∈ Z : 1 ≤ a ≤ p, |a − Rp (f (a))| < p , 2 Acta Mathematica Hungarica 156, 2018

Acta Mathematica Hungarica

4

207

LARGEY.FAMILIES SUBSETS CAO and OF H. LIU

 1  Vg = a ∈ Z : 1 ≤ a ≤ p, (g(a), p) = 1, |a − g(a)| < p . 2

Then for any positive integer M with M = o(p), we have

(1.5)

W (Vf , p) ≫ M,

(1.6)

W (Vg , p) ≫ M.

Remark 1.3. The subsets Vf and Vg are not pseudorandom since their well-distribution measures are very high. 2. Exponential sums We need the following estimate for exponential sums over a finite field. Lemma 2.1 (A. Weil [8]). Let Ψ be a nontrivial additive character and χ a multiplicative character on a finite field Fq of characteristic p. Let f , g be rational functions in Fq (x) and  G(Ψ, f ; χ, g) = χ(g(x))Ψ(f (x)), x∈Fq \S

where S denotes the set of poles of f and g . For f = f1 /f2 we define deg(f ) = deg(f1 ) − deg(f2 ). If G(Ψ, f ; χ, g) is a non-degenerate sum with f and g , we have 1

|G(Ψ, f ; χ, g)| ≤ (deg(f ) + l − 1)q 2 , where l is the number of distinct zeros and (non-infinite) poles of g in Fp .

By Lemma 2.1 we can get the following estimates for mixed exponential sums. Lemma 2.2. Let p > 2 be a prime, f (x), g(x) ∈ Fp [x] with deg(f ) ≥ 2 and deg(g) ≥ 1. Let χ be a non-principal Dirichlet character modulo p, and let r , s be integers with (s, p) = 1. Then we have p  rn + sf (n)   1 ≪ deg(f )p 2 , e p

p 

n=1

p 

n=1 (g(n),p)=1 Acta Mathematica Hungarica

e

χ(n)e

n=1

 rn + sg(n)  p

 rn + sf (n)  p

1

≪ deg(f )p 2 ,

1

≪ deg(g)p 2 ,

Acta Mathematica Hungarica 156, 2018

208

5

CAO and OF H. LIU LARGEY.FAMILIES SUBSETS

p 

χ(n)e

n=1 (g(n),p)=1

 rn + sg(n)  p

1

≪ deg(g)p 2 .

We also have the following estimates for mixed exponential sums over incomplete intervals. Lemma 2.3. Let p > 2 be a prime, f (x), g(x) ∈ Fp [x] with deg(f ) ≥ 2 and deg(g) ≥ 1. Let r , s, M , N be integers with (s, p) = 1 and 1 ≤ M < N ≤ p. Then we have  rn + sf (n)   1 ≪ deg(f )p 2 log p, e p M ≤n≤N



e

M ≤n≤N (g(n),p)=1

 rn + sg(n)  p

1

≪ deg(g)p 2 log p.

3. The cardinalities and character sums By the trigonometric sum identity 1   am  = e n n a mod n

 1, 0,

if n | m, if n ∤ m,

we get p 

|Vf | =

(3.1)

1=

a=1 |a−Rp (f (a))|<δp

1 = 2 p

[δp] p  p p    

m=−[δp] c=1 d=1 a=1 |r|≤ p−1 2 c−d=m

1   = 2 p p−1 p−1 |r|≤

1 = p

2

|s|≤

2

[δp] p p   

m=−[δp] c=1 d=1 c−d=m

[δp] 

m=−[δp]

e

p 

a=1 a−Rp (f (a))=m

 r(a − c)   p

1

e

|s|≤ p−1 2

 s(f (a) − d)  p

[δp] p p p   ra + sf (a)   −rc − sd     e e p p

m=−[δp] c=1 d=1 c−d=m

1  1+ 2 p p−1

a=1

[δp] p p p   −rc    ra    e e p p

|r|≤ 2 m=−[δp] c=1 d=1 c−d=m r�=0

Acta Mathematica Hungarica 156, 2018

a=1

Acta Mathematica Hungarica

6

209

LARGEY.FAMILIES SUBSETS CAO and OF H. LIU

+

[δp] p p p   −sd    sf (a)    e e p p

1  p2 p−1

|s|≤ 2 m=−[δp] c=1 d=1 c−d=m s�=0

a=1

[δp] p p p   ra + sf (a)   −rc − sd     e e p p c=1 a=1

1   + 2 p p−1 p−1

d=1 |r|≤ 2 |s|≤ 2 m=−[δp] c−d=m r�=0 s�=0

=: E1 (p, δ; f ) + E2 (p, δ; f ) + E3 (p, δ; f ) + E4 (p, δ; f ). It is easy to show that 1 E1 (p, δ; f ) = p

(3.2)

[δp] p p   

m=−[δp] c=1 d=1 c−d=m

[δp] p p 2   1= 1+1 p m=1 c=1 d=1 c−d=m

[δp] 2 = (p − m) + 1 = δ(2 − δ)p + O(1), p m=1

and (3.3)

E2 (p, δ; f ) = 0.

Noting that [δp] p p   −sd    = e p

(3.4)

m=−[δp] c=1 d=1 c−d=m

=

[δp] 

m=−[δp]

=

0 

m=−[δp]

=

e

[δp] p p   sm − sc    e p

m=−[δp] c=1 d=1 c−d=m

p p  sc    sm   e − 1 p p c=1

d=1 d=c−m

[δp]  p  sm  p+m   sc   sm    sc  + e e − e e − p p p p

e(− ps ) 1 − e(− ps )

c=1

m=1

c=m+1

[δp]  0    sm   sm   e(− ps )  −1 + e 1 − e p 1 − e(− ps ) m=1 p

m=−[δp]

Acta Mathematica Hungarica

Acta Mathematica Hungarica 156, 2018

210

7

CAO and OF H. LIU LARGEY.FAMILIES SUBSETS

=

[δp]   sm    sm  − e e − 1 − e(− ps ) p p

e(− ps )

m=1

=

1

 e(− ps ) e(− ps )(1 − e(− s[δp] p )) s s − e(− p ) 1 − e(− p )

−

e( ps )(1 − e( s[δp] p )) 1−

e( ps )



≪

1

, � ps �2

where �x� = min(x − [x], 1 − (x − [x])). Then from Lemma 2.2 we get

(3.5)

 [δp]   p  p p 1       −sd     sf (a)  E3 (p, δ; f ) ≪ 2 · e e   p p   p p−1 m=−[δp] c=1 d=1 c−d=m

|s|≤ 2 s�=0

≪

a=1

1 1 1  1 2 2 s 2 · deg(f )p ≪ deg(f )p . � p2 � p−1 p

|s|≤ 2 s�=0

Furthermore, we have [δp] p p   −rc − sd    = e p

m=−[δp] c=1 d=1 c−d=m

[δp] 

=

e

m=−[δp]

=

0 

m=−[δp]

[δp] p p   −rc − s(c − m)    e p

m=−[δp] c=1 d=1 c−d=m

p p  sm    (r + s)c   e − 1 p p c=1

d=1 d=c−m

[δp]  p  sm  p+m   (r + s)c   sm    (r + s)c  + . e − e e − e p p p p c=1

m=1

c=m+1

For p | r + s, we get [δp] p p   −rc − sd    e p

(3.6)

m=−[δp] c=1 d=1 c−d=m

=

0 

(p + m)e

m=−[δp]

 sm  p

Acta Mathematica Hungarica 156, 2018

+

[δp] 

m=1

(p − m)e

 sm  p

≪p·

1 � ps �

.

Acta Mathematica Hungarica

8

211

LARGEY.FAMILIES SUBSETS CAO and OF H. LIU

While for p ∤ r + s, we have (3.7) [δp] p p   −rc − sd    e(− r+s p ) = e p 1 − e(− r+s p ) c=1 d=1 m=−[δp]

0  rm    sm   −e − e p p

m=−[δp]

c−d=m

  [δp]    sm   1 1 rm  1 + −e ≪ r+s + e − . p p 1 − e(− r+s � p � � ps � � pr � p ) m=1 e(− r+s p )

Then from Lemma 2.2 we get (3.8)

E4 (p, δ; f )

 [δp]   p  p p 1        −rc − sd     ra + sf (a)  e e ≪ 2  ·  p p p p−1 p−1 m=−[δp] c=1 d=1 c−d=m

|r|≤ 2 |s|≤ 2 r�=0 s�=0

≪

a=1

1 1   p 2 s · deg(f )p 2 p �p� p−1 p−1

|r|≤ 2 |s|≤ 2 r�=0 s�=0 p|r+s

+

  1 1 1   1 1 + · deg(f )p 2 s r r+s p2 � � � � � � p−1 p−1 p p p |r|≤ 2 |s|≤ 2 r�=0 s�=0 p∤r+s 1



≪ deg(f )p− 2

|s|≤ p−1 2 s�=0

3

+ deg(f )p− 2



1

3

� ps �



+ deg(f )p− 2



|r|≤ p−1 |s|≤ p−1 2 2 r�=0 s�=0 p∤r+s



|s|≤ p−1 |r|≤ p−1 2 2 r�=0 s�=0 p∤r+s

1 � r+s p �

·

1 � pr �

1 � r+s p �

·

1 � ps �

1

≪ deg(f )p 2 (log p)2.

Now combining (3.1)–(3.3), (3.5) and (3.8) we immediately get   1 (3.9) |Vf | = δ(2 − δ)p + O deg(f )p 2 (log p)2 . This proves (1.1).

Acta Mathematica Hungarica

Acta Mathematica Hungarica 156, 2018

212

9

CAO and OF H. LIU LARGEY.FAMILIES SUBSETS

For p ∤ r, we get [δp] p p   −rc    = e p

(3.10)

m=−[δp] c=1 d=1 c−d=m 0 

=

p+m 

m=−[δp] c=1

=

e(− pr ) 1 − e(− pr )

m=−[δp] c=1

d=1 d=c−m

[δp] p  rc   rc    + e − e − p p m=1 c=m+1

  0  m=−[δp]

[δp] p p  −rc     e 1 p

[δp]  rm     rm  + −1 e − 1−e − p p



m=1

[δp]    rm   rm  −e = e − 1 − e(− pr ) m=1 p p

e(− pr )

=

e(− pr ) 1 − e(− pr )



e(− pr )(1 − e(− r[δp] p )) 1 − e(− pr )

−

e( pr )(1 − e( r[δp] p )) 1 − e( pr )



≪

1 . � pr �2

Let χ be a non-principal Dirichlet character modulo p. From Lemma 2.2, (3.4), (3.6), (3.10) and (3.7) we have



χ(n) =

χ(n) =

n=1 |n−Rp (f (n))|<δp

n∈Vf

1 = 2 p

p 

[δp] p  p p   

χ(n)

m=−[δp] c=1 d=1 n=1 c−d=m

1   = 2 p p−1 p−1 |r|≤

2

|s|≤

2



|r|≤ p−1 2

[δp] 

m=−[δp]

e

p 

 r(n − c)   p

χ(n)

n=1 n−Rp (f (n))=m

|s|≤ p−1 2

e

 s(f (n) − d)  p

[δp] p p p   rn + sf (n)   −rc − sd     χ(n)e e p p c=1 n=1

m=−[δp]

=

1 p2

d=1 c−d=m

[δp] p  p p   

χ(n)

m=−[δp] c=1 d=1 n=1 c−d=m

Acta Mathematica Hungarica 156, 2018

Acta Mathematica Hungarica

10

213

LARGEY.FAMILIES SUBSETS CAO and OF H. LIU

+

[δp] p p p   −rc    rn    e χ(n)e p p

1  p2 p−1

|r|≤ 2 m=−[δp] c=1 d=1 c−d=m r�=0

n=1

[δp] p p p   sf (n)   −sd     χ(n)e e p p c=1 n=1

1  + 2 p p−1

d=1 |s|≤ 2 m=−[δp] c−d=m s�=0

+

[δp] p p p   −rc − sd    rn + sf (n)    e χ(n)e p p

1   p2 p−1 p−1

|r|≤ 2 |s|≤ 2 m=−[δp] c=1 d=1 c−d=m r�=0 s�=0

≪0+

n=1

1 1 1  1  1 1 2 + 2 · p r 2 s 2 · deg(f )p 2 2 p �p� p �p� p−1 p−1

|r|≤ 2 r�=0

+

|s|≤ 2 s�=0

1 1   p 2 s · deg(f )p 2 p �p� p−1 p−1

|r|≤ 2 |s|≤ 2 r�=0 s�=0 p|r+s

  1 1 1 1   1 1 + 2 · deg(f )p 2 ≪ deg(f )p 2 (log p)2 . s + r r+s p � p � �p� �p� p−1 p−1 |r|≤ 2 |s|≤ 2 r�=0 s�=0 p∤r+s

This completes the proof of (1.3). Similarly, from (3.2), (3.4), (3.6), (3.7), (3.10) and Lemma 2.2 we have p 

|Vg | =

1=

a=1 (g(a),p)=1

[δp] 

m=−[δp]

[δp] p−1 p   

p 



a=1 m=−[δp] c=1 d=1 |r|≤ p−1 2 c−d=m (g(a),p)=1

1   = 2 p p−1 p−1 |r|≤

2

|s|≤

2

Acta Mathematica Hungarica

e

 r(a − c)   p

[δp] p−1  p    −rc − sd  e p c=1

m=−[δp]

d=1 c−d=m

1

a=1 (g(a),p)=1 a−g(a)=m

|a−g(a)|<δp

1 = 2 p

p 

e

|s|≤ p−1 2 p 

a=1 (g(a),p)=1

 s(g(a) − d) 

e

p

 ra + sg(a)  p

Acta Mathematica Hungarica 156, 2018

214

11

CAO and OF H. LIU LARGEY.FAMILIES SUBSETS

1 p2

=

[δp] p−1 p   

p 

a=1 m=−[δp] c=1 d=1 c−d=m (g(a),p)=1

[δp] p−1  p    −rc  e p

1  + 2 p p−1

|r|≤ 2 m=−[δp] c=1 d=1 c−d=m r�=0

+

[δp] p−1  p    −sd  e p

1  p2 p−1

|s|≤ 2 m=−[δp] c=1 d=1 c−d=m s�=0

1   + 2 p p−1 p−1



p 

a=1 (g(a),p)=1 p 

[δp] p−1  p    −rc − sd  e p c=1

[δp] p−1 p    

m=−[δp] c=1 d=1 c−d=m

e

e

a=1 (g(a),p)=1

d=1 |r|≤ 2 |s|≤ 2 m=−[δp] c−d=m r�=0 s�=0

1 = 2 p

1



 ra  p

 sg(a) 

p 

a=1 (g(a),p)=1

p

e

 ra + sg(a)  p

 1  1 p + O(deg(g)) + O 2 · deg(g) p � pr �2 p−1 

|r|≤ 2 r�=0

   1 1 1  1 1   p +O 2 · deg(g)p 2 · deg(g)p 2 + O 2 p � ps �2 p � ps � p−1 p−1 p−1 |r|≤ 2 |s|≤ 2 r�=0 s�=0 p|r+s

|s|≤ 2 s�=0



   1 1   1 1 1 2 +O 2 + · deg(g)p p � ps � � pr � � r+s p−1 p−1 p � |r|≤ 2 |s|≤ 2 r�=0 s�=0 p∤r+s

  1 = δ(2 − δ)p + O deg(g)p 2 (log p)2 ,

and 

n∈Vg

χ(n) =

p 

n=1 (g(n),p)=1 |n−g(n)|<δp

Acta Mathematica Hungarica 156, 2018

χ(n) =

[δp] 

p 

χ(n)

n=1 m=−[δp] (g(n),p)=1 n−g(n)=m

Acta Mathematica Hungarica

12

=

215

LARGEY.FAMILIES SUBSETS CAO and OF H. LIU

1 p2

[δp] p−1 p   

p 

n=1 m=−[δp] c=1 d=1 c−d=m (g(n),p)=1

1   = 2 p p−1 p−1 |r|≤

2

|s|≤

2



χ(n)

e

|r|≤ p−1 2

 r(n − c)  

[δp] p−1  p    −rc − sd  e p

m=−[δp] c=1 d=1 c−d=m

=

1 p2

[δp] p−1 p   

|s|≤ 2 s�=0

[δp] p−1  p    −sd  e p

m=−[δp] c=1 d=1 c−d=m

d=1 |r|≤ 2 |s|≤ 2 m=−[δp] c−d=m r�=0 s�=0

+

χ(n)e

n=1 (g(n),p)=1

p

 rn + sg(n)  p

χ(n)

p 

[δp] p−1 p   

deg(g) +

m=−[δp] c=1 d=1 c−d=m

χ(n)e

n=1 (g(n),p)=1 p 

χ(n)e

n=1 (g(n),p)=1

[δp] p−1  p    −rc − sd  e p c=1

1   + 2 p p−1 p−1

p 

 s(g(n) − d) 

n=1 m=−[δp] c=1 d=1 c−d=m (g(n),p)=1

d=1 |r|≤ 2 m=−[δp] c−d=m r�=0

1  + 2 p p−1

|s|≤ p−1 2

p 

[δp] p−1  p    −rc  e p c=1

1  + 2 p p−1

1 ≪ 2 p

p

e

p 

 rn 



p

sg(n) p

χ(n)e

n=1 (g(n),p)=1



 rn + sg(n)  p

1 1  1 2 r 2 ·p 2 p �p� p−1

|r|≤ 2 r�=0

1 1 1  1   p 1 2 + 2 · deg(g)p s s · deg(g)p 2 2 p2 � p � � � p−1 p−1 p−1 p p

|s|≤ 2 s�=0

|r|≤ 2 |s|≤ 2 r�=0 s�=0 p|r+s

  1 1 1 1   1 1 + 2 · deg(g)p 2 ≪ deg(g)p 2 (log p)2 . s + r r+s p � p � �p� �p� p−1 p−1 |r|≤ 2 |s|≤ 2 r�=0 s�=0 p∤r+s

This completes the proof of Theorem 1.1. Acta Mathematica Hungarica

Acta Mathematica Hungarica 156, 2018

216

13

CAO and OF H. LIU LARGEY.FAMILIES SUBSETS

4. The well-distribution measure Define the sequences  |Vf | |Vf | p ,− , Ep′ = Ep′ (Vf ) = {e′1 , e′2 , . . . , e′p } ∈ 1 − p p  |Vg | |Vg | p ,− Ep′′ = Ep′′ (Vg ) = {e′′1 , e′′2 , . . . , e′′p } ∈ 1 − p p by e′n



=

|Vf | p , |Vf | − p ,

for n ∈ Vf ,

1−

e′′n

for n �∈ Vf ,

=

|Vg | p , |Vg | − p ,

 1−

for n ∈ Vg , for n �∈ Vg ,

respectively. Assume that δ = 12 . For positive integer M with M = o(p), by (1.1) we have M 

e′n

n=1

M M M  |Vf |  |Vf | |Vf |   1− 1= 1−M = 1− p p n=1 p n=1 n=1



=

n∈Vf

M 

n=1 n∈Vf

n�∈Vf

n∈Vf

1 3 1 − M + O ( deg(f )p 2 (log p)2 ). 4

By the trigonometric sum identity we get M 

1=

n=1 n∈Vf p−1

1 = 2 p

2 

p−1

M 

1=

n=1 |n−Rp (f (n))|< 12 p p  p  M  

c=1 d=1 n=1 |r|≤ p−1 m=− p−1 2 2 c−d=m

e

2 

m=−

p−1 2

M 

n=1 n−Rp (f (n))=m

 r(n − c)   p

1

|s|≤ p−1 2

e

 s(f (n) − d)  p

p−1

1   = 2 p p−1 p−1 |r|≤

2

|s|≤

2

p p  M   −rc − sd    rn + sf (n)  e e p p p−1 c=1 n=1

2 

m=−

2

Acta Mathematica Hungarica 156, 2018

d=1 c−d=m

Acta Mathematica Hungarica

14

217

LARGEY.FAMILIES SUBSETS CAO and OF H. LIU p−1

M = 2 p

p p  

2 

c=1 d=1 m=− p−1 2 c−d=m

p−1

p p  M   −rc    rn  e e p p p−1

2 

1  1+ 2 p p−1

|r|≤ 2 m=− r�=0

n=1

c=1 d=1 c−d=m

2

p−1

1  + 2 p p−1

p p  M   −sd    sf (n)  e e p p p−1

2 

|s|≤ 2 m=− s�=0

n=1

c=1 d=1 c−d=m

2

p−1

1   + 2 p p−1 p−1

p p  M   −rc − sd    rn + sf (n)  e e p p p−1 c=1 n=1

2 

|r|≤ 2 |s|≤ 2 m=− r�=0 s�=0

d=1 c−d=m

2

=: Ω1 (p, f, M ) + Ω2 (p, f, M ) + Ω3 (p, f, M ) + Ω4 (p, f, M ). Then from (3.2), (3.4), (3.6), (3.7) and Lemma 2.3 we have 3 Ω1 (p, f, M ) = M + O(1), 4

1

Ω3 (p, f, M ) ≪ deg(f )p 2 log p, 1

Ω4 (p, f, M ) ≪ deg(f )p 2 (log p)3 . Therefore M 

(4.1)

n=1

  1 e′n = Ω2 (p, f, M ) + O deg(f )p 2 (log p)3 .

On the other hand, by (3.10) we know that for r �= 0 we have p−1

p p   −rc   e p p−1 c=1

2 

m=−

=

e(− pr ) 1 − e(− pr )



2

d=1 c−d=m

r )) e(− pr )(1 − (−1)r e( 2p

1 − e(− pr )

−

r e( pr )(1 − (−1)r e(− 2p ))

1 − e( pr )

 .

Computing the geometric sums we have e(− pr )

πr 1 i cos p ip + O(1), r =− − πr = − 1 − e(− p ) 2 2 sin p 2πr Acta Mathematica Hungarica

Acta Mathematica Hungarica 156, 2018

218

15

CAO and OF H. LIU LARGEY.FAMILIES SUBSETS

and r e(− pr )(1 − (−1)r e( 2p ))

1 − e(− pr ) =i

(−1)r − cos πr p sin πr p

−

r e( pr )(1 − (−1)r e(− 2p ))

1 − e( pr )

 2p −i πr + O(1), if 2 ∤ r, = O(1), if 2 | r.

Then p−1

(4.2)

m=−

 p2 p − π2 r2 + O( |r| ), if 2 ∤ r,

p p   −rc   = e p p−1 c=1

2 

2

p O( |r| ),

d=1 c−d=m

if 2 | r.

So we get (4.3)

M 

n=1

e′n

M   1 1  1   rn  + O deg(f )p 2 (log p)3 . =− 2 e 2 π r p p−1 n=1

|r|≤ 2 r�=0

Let A be a real number with 1 ≤ A ≤ (4.4)

M 

e′n = −

n=1

p 8M .

We have

M M  1  1   rn  + O . e π2 r 2 n=1 p A |r|≤A r�=0

Note that for |r| ≤ A, r �= 0 we have

rn p

≤

AM p

≤ 18 . Hence,

 M     rn  Re  ≫ M. e  p  n=1

Thus the order of magnitude of the first term on the left hand side of (4.4) is at least as large as the order of magnitude of the second term. Thus it follows from (4.4) that   M  1  ′  M  ≫ M. + en  ≫ M  r2 A n=1

|r|≤A r�=0

Therefore W (Vf , p) ≫ M . This completes the proof of (1.5). Similarly we can get (1.6). Acta Mathematica Hungarica 156, 2018

Acta Mathematica Hungarica

16

LARGE FAMILIES OF SUBSETS Y. CAO and H. LIU: LARGE FAMILIES OF SUBSETS

219

References [1] Z. Chen, Large families of pseudo-random subsets formed by generalized cyclotomic classes, Monatsh. Math., 161 (2010), 161–172. [2] C. Dartyge, E. Mosaki and A. S´ ark¨ ozy, On large families of subsets of the set of the integers not exceeding N , Ramanujan J., 18 (2009), 209–229. [3] C. Dartyge and A. S´ ark¨ ozy, On pseudo-random subsets of the set of the integers not exceeding N , Periodica Math. Hungar., 54 (2007), 183–200. [4] C. Dartyge and A. S´ ark¨ ozy, Large families of pseudorandom subsets formed by power residues, Unif. Distrib. Theory, 2 (2007), 73–88. [5] C. Dartyge, A. S´ ark¨ ozy and M. Szalay, On the pseudo-randomness of subsets related to primitive roots, Combinatorica, 30 (2010), 139–162. [6] H. Liu, Large family of pseudorandom subsets of the set of the integers not exceeding N , Int. J. Number Theory, 10 (2014), 1121–1141. [7] H. Liu and E. Song, A note on pseudorandom subsets formed by generalized cyclotomic classes, Publ. Math. Debrecen, 85 (2014), 257–271. [8] A. Weil, On some exponential sums, Proc. Nat. Acad. Sci., 34 (1948), 204–207. [9] P. Xi and Y. Yi, On character sums over flat numbers, J. Number Theory, 130 (2010), 1234–1240. [10] Z. Xu, Distribution of the difference of an integer and its m-th power mod n over incomplete intervals, J. Number Theory, 133 (2013), 4200–4223. [11] W. Zhang, On a problem of A. C. Woods, Adv. Math. (China), 23 (1994), 284–285. [12] W. Zhang, Some estimates of trigonometric sums and their application, Acta Math. Hungar., 76 (1997), 17–30.

Acta Mathematica Hungarica

Acta Mathematica Hungarica 156, 2018