1 . r(log p)7

2. Some estimates for prime power moduli Let (2.0)

f (x) = a1 xk1 + · · · + ar xkr ∈ Z[X];

1 ≤ k1 < · · · < kr = d.

Let p be a prime and (2.1)

(a1 , . . . , ar , p) = 1.

Recall Steˇckin’s estimate [St]. Proposition 6: Let m ∈ Z, m ≥ 2. Then pm X
1 (2.2) epm f (x) < Cpm(1− d ) x=1

for some absolute constant C, provided f is nonconstant (mod p).

Vol. 176, 2010 ESTIMATES ON POLYNOMIAL EXPONENTIAL SUMS

227

It was shown in [C-Zh] that the constant C in (2.2) may be taken as C = 4.41 in fact. The next estimate will be useful provided m is large compared with r. Proposition 7: Let f (x) be as in (2.1), p a prime and m ∈ Z+ s.t. (2.3)

(a1 , . . . , ar , p) = 1,

(2.4)

m > 20r2 , Y (ki − kj ) 6= 0

(2.5)

m

(modp[ 10r ] ).

i6=j

Then

(2.6)

X

epm

1≤x

1 f (x) < Cpm(1− 10r2 ) .

Proof. Choose n ∈ Z+ s.t.

  n r + 1/2 < m < n(r + 1)

(2.7)

which is possible by our assumption (2.4). Hence, for x, y ∈ Z, r X 1 (s) (2.8) f (x + pn y) = f (x) psn y s s! s=0 We estimate X
(2.9) epm f (x) ≤ 1≤x
X

1≤x
(mod pm ).

r  X 1 (s) sn s f (x)p y . epm s! m−n s=1

X

0≤y
Fix x and consider the polynomial (2.10)

g(y) =

r1 r X X 1 (s) f (x)psn y s = pu bs y s , s! s=1 s=1

where and (2.11)

r1 ≤ r

and (b1 , . . . , br1 , p) = 1 n ≤ u ≤ rn + v

with (2.12) v = v(x) = max{w ∈ Z, w ≥ 0| f (s) (x) = 0(mod pw ) for all 1 ≤ s ≤ r}.

228

J. BOURGAIN

Isr. J. Math.

Assume n 4 implying, by (2.7), (2.11) that m − u > n4 . It follows from Proposition 6 that X  r1 X (m−u)(1− r1 ) 1 . m−u e b y s s < Cp p (2.13)

v<

s=1

0≤y
Therefore (2.14)



X

epm

X r s=1

0≤y
 n 1 (s) f (x)psn y s < Cpm−n p− 4r . s!

It remains to analyze condition (2.13). Assume for s = 1, . . . , r (2.15)

f (s) (x) =

r X j=1

aj kj (kj − 1) · · · (kj − s + 1)xkj −s ≡ 0

(mod pw ).

Since (a1 , . . . , ar , p) = 1, (x, p) = 1, it follows from (2.15) and Cramer’s rule that (2.16)

det [kj (kj − 1) · · · (kj − s + 1)]1≤j,s≤r ≡ 0

(mod pw ).

Hence (2.17)

Y

j1 6=j2

(kj1 − kj2 ) ≡ 0 (mod pw ).

Recalling (2.5), it follows that w<

m 10r

so that (2.13) always holds. The desired estimate (2.6) then follows from (2.14). Remark: Proposition 7 should be compared with Lemma 5 in [Sh] providing a similar estimate, in fact with a saving 1/r in (2.6) rather than 1/r2 . On the other hand, the constant C in (2.6) does not depend on the number of monomials. The next two estimates will take care of smaller values of m ≥ 2. Let f (x) ∈ Z[X] be as above. If the number of monomials is bounded, we use the following:

Vol. 176, 2010 ESTIMATES ON POLYNOMIAL EXPONENTIAL SUMS

229

Proposition 8: Let m ≥ 2 and p > C(r, ε), where ε > 0 is an arbitrary small given number. Assume the exponents k1 < · · · < kr satisfy the following conditions (2.18)

(kj , pm ) < pm/3

(2.19)

(kj , p − 1) < p1−ε

(2.20)

(ki − kj , p − 1) < p1−ε

for 1 ≤ j ≤ r, for 1 ≤ j ≤ r, for 1 ≤ i 6= j ≤ r.

Then, for some δ = δ(r, ε) > 0, we have X
< pm−δ . m (2.21) e f (x) p 1≤x
Proof. Set (2.22)

n=

 m 2

 m+1 2

and write (2.23)

X


1 epm f (x) = n p m

1≤x

if m is even if m is odd

X

X

1≤x

epm f (x + pn y)

where, by (2.22), f (x + pn y) = f (x) + pn f 0 (x)y

(mod pm ).

Hence |(2.23)| ≤ p (2.24)

−n

X

1≤x
X
0 epm−n f (x)y 1≤y
= |{1 ≤ x < pm |(x, p) = 1 and f 0 (x) ≡ 0(mod pm−n )}|.

Here (2.25)

f 0 (x) =

r X j=1

aj kj xkj −1 = pu

r X j=1

with (2.26)

(b1 , . . . , br , p) = 1

bj xkj −1

230

J. BOURGAIN

Isr. J. Math.

and, by (2.18), m . 3 Taking into account (2.22) and (2.27), estimate (2.24) becomes X (2.24) ≤ pm−1 {1 ≤ x < p bj xkj ≡ 0(mod p)} (2.27)

(2.28)

u<

 p−1 p−1   X X X kj zb x ≤ pm−2 p − 1 + e j p z=1 x=1

where, invoking Proposition 3, we have, for 1 ≤ z < p, p−1   X X kj 1−δ (2.29) zb x e j p

with δ = δ(r, ε) given by Proposition 3. Since p > C(r, ε), it follows that

|(2.23)| < pm−δ/2 ,

(2.30) proving Proposition 8.

Remark: In view of the comment following Proposition 3, if we let in the assumptions of Proposition 8 (2.31)

ε=

C(r) log log p

with a sufficiently large constant C(r), we may still retrieve an estimate of the form X √
m − log p m f (x) < p e e (2.32) p 1≤x
for sufficiently large p. When r is large, use Proposition 5 instead of Proposition 3 in the previous argument. This gives Proposition 9: Let f (x) ∈ Z[X] be as in (2.0), p > p0 , m ≥ 2 and the exponents k1 < · · · < kr satisfying (2.33) (2.34)

(kj , pm ) < pm/3 (kj , p − 1) <

for 1 ≤ j ≤ r,

p r(log p)2

for 1 ≤ j ≤ r,

Vol. 176, 2010 ESTIMATES ON POLYNOMIAL EXPONENTIAL SUMS

(2.35)

231

ki − kj 6≡ 0(mod p − 1) if i 6= j.

Then (2.36)



X

e


f (x) < pm 1 −

pm

1≤x
 1 . 2(log p)7 r

Pr Pr kj = pu j=1 bj xkj satisfying (2.26) and Proof. Write xf 0 (x) = j=1 kj aj x (2.27). Pr kj In order to apply Proposition 5, we need to reduce (mod p), j=1 bj x writing r X

(2.37)

bj xkj

j=1

≡

(modp)

kj0

r1 X j=1

0

b0j xkj ∈ Fp [X]

kj0

with r1 ≥ 1, 1 ≤ < p − 1, kj ≡ (mod p − 1) and (b0j , p) = 1 (we use here the assumption (2.35)). Condition (1.15) follows then from (2.34), and (1.16) gives  o  n  1 1 m 1 − < p , (2.38) (2.28) < pm−2 p + p(p − 1) 1 − r(log p)7 2r(log p)7 which is (2.36). If p > d3 , use Weil’s bound (Proposition 4) instead of Proposition 5. Hence Proposition 10: Under the assumptions of Proposition 9, if p > d3 , we have, for m ≥ 2, X (2.39) epm f (x) < pm−1/6 . 1≤x
3. Exponential sum estimates over the multiplicative group Denote for q ∈ Z+ (3.1)

X∗

It is well-known that if q = as (3.2)

X

eq f (x) . eq f (x) = 1≤x
Q

(3.1) =

pmp is the prime factorization, then (3.1) factors Y h X∗ p


i epmp ap f (x) ,

232

J. BOURGAIN

Isr. J. Math.

where q = Qp pmp and ap Qp ≡ 1(mod pmp ). Using the bounds from §1 and §2, we establish Proposition 11 (r fixed): Given τ > 0, there is δ = δ(r, τ ) > 0 s.t. X∗ (3.3) eq (a1 xk1 + · · · + ar xkr ) < 2q 1−δ provided (a1 , . . . , ar , q) = 1 and

log q > Cr,τ dτ .

(3.4) For large values of r we have

Proposition 12: There is an estimate X∗
eq f (x) < 2q 1−δ (3.5) with

(3.6)

2

δ = cr−4 d− log log d .

Proof of Proposition 11. We start by introducing the following sets of exceptional primes o n  Y  1 kj > p 3 mp (3.7) P 1 = p p mp , and

(3.8)

    Y mp ] 2 mp [ 10r P2 = p mp > C1 r and p , (ki − kj ) > p i6=j

with C1 a sufficiently large constant. Letting ε > 0 be a fixed small number, set also n P3 = p ∈ / P1 mp ≤ C1 r2 and either (kj , p − 1) > p1−ε for some 1 ≤ j ≤ r o (3.9) or(ki − kj , p − 1) > p1−ε for some 1 ≤ i 6= j ≤ r . Let P = P1 ∪ P2 ∪ P3 (which are disjoint) and denote for i = 1, 2, 3 Y (3.10) qi = p mp . p∈Pi

Clearly (3.11)

q1 < d3r

Vol. 176, 2010 ESTIMATES ON POLYNOMIAL EXPONENTIAL SUMS

233

and 3

q2 < d20r .

(3.12)

If p ∈ P3 , then p < d2 and p − 1 is the form p − 1 = α.β with α dividing some kj or some ki − kj and β < pε . Hence, using a divisor function estimate, we certainly have 1

|P3 | < r2 d log log d +2ε

(3.13) and

  1 q3 < exp C1 r4 d2(ε+ log log d )

(3.14)

(note that we obviously may assume d large). Write Y h X∗
i epmp ap f (x) p6∈P

=

Y

Y

Y

p6∈P p6∈P p6∈P 2 mp =1 2≤mp ≤C1 r mp >C1 r 2

=

h X∗

X

∗


epmp ap f (x)




ih X∗
ih X∗
i eq4 A4 f (x) eq5 A5 f (x) eq6 A6 f (x)

where Ai qqi ≡ 1(mod qi ), 1 ≤ i ≤ 6. Since p 6∈ P3 , Proposition 3 implies, for p > C(r, ε), X
ep ap f (x) < p1−δ

for some δ = δ(r, ε) and hence X∗  q −δ
4 . (3.15) eq4 A4 f (x) < q4 Cr,ε

Next, let p 6∈ P1 ∪ P3 , p > C(r, ε) and 2 ≤ mp < C1 r2 . By Proposition 8 X∗
mp (1− C δr2 ) 1 . epmp ap f (x) < pmp −δ < p (3.16) Therefore (3.17)

X∗  q − δ 2
C1 r 5 eq5 A5 f (x) < q5 . Cr,ε

Choosing C1 appropriately, Proposition 7 clearly implies that X∗
1− 1 (3.18) eq6 A6 f (x) < q6 20r2 .

234

J. BOURGAIN

Isr. J. Math.

From the preceding, we conclude that X∗  q −δ0
f (x) < q. e (3.19) q Q with   1 (3.20) Q < Cr,ε q1 q2 q3 < Cr,ε exp c1 r4 d2(ε+ log log d ) and δ 0 = δ 0 (r, ε). Taking ε = τ3 and assuming d large, Proposition 11 follows.

Proof of Proposition 12. We use the same notations as above and proceed similarly, but replacing P3 by n p P30 = p|mp ≤ C1 r2 and (kj , p − 1) > for some 1 ≤ j ≤ r r(log p)2 o (3.21) or ki ≡ kj (mod p − 1) for some i 6= j . Q If q30 = p∈P 0 pmp , we obtain 3

(3.22)

1

q30 < exp(C1 r4 (log d)3 d log log d ).

It follows from Proposition 5 that if mp = 1 and p ∈ / P30 , then X   1 p
1 1−

Distinguishing the cases p ≤ d3 , p > d3 and invoking Weil’s inequality if p > d3 , we certainly have for p 6∈ P30 p X c
1− (3.24) ep ap f (x) < p r(log d)8 . x=1

Therefore (3.25)

X∗ c 1−
8 eq4 A4 f (x) < q4 r(log d) .

Also, for p 6∈ P1 ∪ P30 and 2 ≤ mp < C1 r2 , it follows from Propositions 9 and 10 (since we may assume p > p0 ) that X∗ c
m(1− r3 (log ) d)8 , (3.26) epm ap f (x) < p implying (3.27)

X∗ 1− 3 c 8
eq5 A5 f (x) < q5 r (log d) .

The estimate (3.18) remains valid.

Vol. 176, 2010 ESTIMATES ON POLYNOMIAL EXPONENTIAL SUMS

235

In view of (3.22), the estimate (3.5), (3.6) clearly holds. This proves Proposition 12. Remarks: 1. Using the comments following Propositions 5 and 8, one may check the fine line of Proposition 11, letting τ → 0. One may show in particular that X∗ cr 1− √log d (3.28) eq (a1 xk1 + · · · + ar xkr ) < q

provided (a1 , . . . , ar , q) = 1, q large enough, and d = max(k1 , . . . , kr ) satisfying (3.29)

d < (log q)cr log log log q .

√ The denominator log d in (3.28) may be further reduced to (log d)κ for any given κ > 0, provided in assumption (3.29) we decrease cr suitably. As pointed out in the Introduction, it turns out that even for r = 1, condition (3.29) is essentially optimal, as a restriction on the degree, to allow a nontrivial bound. 2. Related to Proposition 12, if we restrict ourselves to square free moduli q, one has the following estimate. Let f (x) ∈ Z[X] be nonconstant with r monomials and of degree d. Assume q square-free, (3.30)

2

log q > Cr2 d log log d

and the content of f (x) relative prime to q. Then X
eq f (x) < q 1−δ (3.31) 1≤x≤q

with

1 r(log d)8
P∗ eq f (x) . (the same estimate holds for This follows easily from Propositions 4 and 5 and the previous arguments. On the other hand, there is the following example, showing that (3.30) is in some sense nearly optimal. Take Y (3.33) q= p hence log q ∼ d. (3.32)

δ∼

p
236

J. BOURGAIN

Isr. J. Math.

√ Let S ⊂ {1, . . . , d} be a set of ∼ d elements such that S − S ⊃ {1, . . . , d}. In particular, for each prime p < d, there are elements kp , kp0 ∈ S s.t. kp − kp0 = p − 1.

(3.34) Consider the polynomial (3.35)

f (x) =

X  Q p
 0 p’ (xkp − xkp ) ∈ Z[X]

1
of degree < d and which content is relatively prime to q. Obviously, by (3.34), f (x) = 0

(mod q) √ while the number r = |S| of monomials is ∼ d. 4. Exponential sum estimates over the full residue set Our aim is to establish the following special case of Steˇckin’s problem (see the Question discussed in the Introduction). Proposition 13: Let f (x) = a1 xk1 +· · ·+ar xkr ∈ Z[X] of degree d and q ∈ Z+ such that (a1 , . . . , ar , q) = 1. Assume further that the number r of monomials satisfies 1

r < d 4 −τ

(4.1)

for some τ > 0. Then we have an estimate X q
(4.2) eq f (x) < Cτ q 1−1/d , x=1

where Cε is a constant.

Remarks: 1. It was shown in [CPR1] that if we fix the number of monomials of f (x), there is an estimate of the form q X
(4.3) eq f (x) < C(r)q 1−1/d , x=1

assuming the content of f relatively prime to q. Proposition 13 is obviously more general, as we consider a notion of ‘sparse polynomial’ relative to its degree (rather than specifying r). Recall that the exponent in (4.3) is optimal, already for r = 1.

Vol. 176, 2010 ESTIMATES ON POLYNOMIAL EXPONENTIAL SUMS

237

2. Considering general nonconstant polynomials f (x) ∈ Z[X] of degree d with content relatively prime to q, it was shown by Steˇckin [St] that X q
< ed+O(d/ log d) q 1−1/d . (4.4) f (x) e q x=1

We don’t review here the various contributions to this type of inequality, referring the reader to the introduction of [CPR1], for instance. We just note that in view of (4.4), we may assume the degree d large in proving Proposition 13. Also, by (4.4), we retrieve (4.3) from Proposition 13 with log C(r) = r4+o(1) , which is also essentially the bound obtained in [CPR2]. However, no special effort was made, neither in [CPR1] nor here, to optimize the argument. Q Proof of Proposition 13. Writing q = mp ≥1 pmp , there is again a factorization  X  X

Y (4.5) epmp ap f (x) . eq f (x) = 1≤x≤q

Recalling that X (4.6)

epm

1≤x≤pm

p

1≤x≤pm

ap f (x)) ≤ pm(1−1/d)

2d

for p ≥ (d − 1) d−2 and m ≥ 1

(see, for instance, [Ne], Lemma 8), we may assume that all prime factors p of q satisfy p < d3

(4.7)

(letting d be sufficiently large). We will derive Proposition 13 from Proposition 12. For each prime p with mp ≥ 1, introduce m∗p ∈ Z+ ∪ {0} and σp ∈] − 1, 1[ by the condition 0 ≤ m∗p =

(4.8)

mp + σp d

where (4.9)

−

1 1 < σp ≤ 1 − . 2 p(log p)(log d) p(log p)(log d)2

Let (4.10)

P = {p|m∗p ≥ 1}

238

J. BOURGAIN

Isr. J. Math.

and denote, for S ⊂ P, qS =

(4.11)

Y

p mp ,

Y

pmp −1

p∈S

q˜S =

(4.12)

∗

p∈S

(setting qφ = q˜φ = 1). Let further (4.13) ∗ ∗ ΓS = {1 ≤ x ≤ q (x, pmp ) ≥ pmp if p 6∈ S and (x, pmp ) ≤ pmp −1 if p ∈ S}. Hence

X

X X eq f (x) eq f (x) ≤ x∈ΓS

S⊂P

(4.14)

≤

X Y

S⊂P p6∈S

AS qqS

∗

pmp −mp

X 1 X∗
eqS AS f (Qx) Q

Q|˜ qS

≡ 1(mod qS ). where Fix S ⊂ P, S 6= φ and Q|˜ qS . Write X∗
ϕ(qS ) X∗
eqS AS f (Qx) = (4.15) eqS0 g(x) . ϕ(qS0 )

where the content of g(x) ∈ Z[X] is a relative prime with qS and qS0 |qS satisfies

qS |qS0 .Qd .
P∗ Applying Proposition 12 to the sum eqS0 g(x) , we certainly have a bound X∗
(4.17) eqS0 g(x) < 2(qS0 )1−δ (4.16)

with

2

δ = cr−4 d− log log d .

(4.18)

Therefore, by (4.15) and (4.16) X∗  q −δ
S . eqS AS f (Qx) < 2qS · (qS0 )−δ < 2qS (4.19) Qd

Substituting (4.19) in (4.14) gives the estimate X Y X Y ∗ X ∗ qS1−δ Qdδ−1 < 5 pmp −mp (4.20) 2 pmp −mp qS1−δ (˜ qS )dδ−1 S⊂P p6∈S

Q|˜ qS

S⊂P p6∈S

Vol. 176, 2010 ESTIMATES ON POLYNOMIAL EXPONENTIAL SUMS

239

where we assume 2(log d)2 3 > . d d (4.21) follows indeed from (4.1), (4.18) for d large enough. Substituting (4.8), (4.12) in (4.20) gives Y Y X Y mp p(1−1/d)mp −σp p(1−δ)mp +(dδ−1)( d +σp −1) p mp . (4.21)

δ>

=

Y

p

p6∈P

(4.22) ≤ q

p∈S

S⊂P p∈P\S

p6∈P

mp

 Y

p∈P

1−1/d

Y

p

mp

m∗p

Y

p

−σp

p

−(dδ−1)(1−σp )

p∈S

S⊂P p∈P\S

1/d Y

Y

1

[p−σp + p− 2 dδ(1−σp ) ].

p∈P

p6∈P

If p 6∈ P, then

p

mp

1−1/d  X

= 0 and (4.9) implies

(4.23)

d . p(log p)(log d)2

mp = −dσp <

Hence  Y

(4.24)

p mp

p6∈P p
1/d

<

1

Y

p p(log)(log d)2 < e

log d c log (log d)2

.

p
It remains to estimate the last factor in (4.22). Thus  Y  Y 1 1 −(log d)2 1+ (4.25) , + p (p−σp + p− 2 dδ(1−σp ) ) < p(log d)2 3 3 p
p
Y

(4.26)

p0,1−σp > (log4d)2

Y

(4.27) 4 (log d)2



1+

1 , p2

p
1 p

1+

 1 4 log p  − p(log p) , + p (log d)2

using (4.9), (4.21). Clearly (4.25) < e

log d c log (log d)2

(4.26) < C

,



240

J. BOURGAIN

and (4.27) <

Y 

p
1+

Isr. J. Math.

log log d 4 log p  1 + < ec log d . 2 p p(log d)2

This completes the proof. References [B1] [B2] [BGK]

[CPR1]

[CPR2] [C-Zh] [EPS] [H] [Kon1]

[Kon2] [MVW]

[Ne]

[Sh] [St]

J. Bourgain, Mordell’s exponential sum estimate revisited, Journal of the American Mathematical Society 18 (2005), 477–499. J. Bourgain, Multilinear exponential sums in prime fields under optimal entropy condition on the sources, Geometric and Functional Analysis, to appear. J. Bourgain, A. Glibichuk and S. Konyagin, Estimates for the number of sums and products and for exponential sums in fields of prime order, Journal of the London Mathematical Society. Second Series. 73 (2006), 380–398. T. Cochrane, C. Pinner and J. Rosenhouse, Bounds on exponential sums and the polynomial Waring’s problem mod p, Journal of the London Mathematical Society. Second Series. 67 (2003), 319–336. T. Cochrane, C. Pinner and J. Rosenhouse Sparse polynomial exponential sums, Acta Arithmetica 108 (2003), 37–52. T. Cochrane and Z. Y. Zheng, On upper bounds of Chalk and Hua for exponential sums, Proceedings of the American Mathematical Society 129 (2001), 2505–2516. P. Erdos, C. Pomerance and E. Schmutz, Carmichael’s lambda function, Acta Arithmetica 58 (1991), 363–385. L. K. Hua, On exponential sums, J. Chinese Math. Soc. 20 (1940), 301–312. S. Konyagin, On estimates of Gaussian sums and Waring’s problem for a prime modulus, Trudy Matematicheskogo Instituta Imeni V.A Steklova 198 (1992), 111– 124 (Russian); Proceedings of the Steklov Institute of Mathematics (1994), 105–107. S. Konyagin, Good distribution of values of sparse polynomial modulo a prime, Analytic Number Theory, Cambridge UP, 2009, 189–296. H. Montgomery, R. Vaughan and T. Wooley, Some remarks on Gauss sums associated with w-th powers, Mathematical Proceedings of the Cambridge Philosophical Society 118 (1995), 21–33. V. I. Neˇ caev, An estimate of a complete rational trigonometric sum, Rossiiskaya Akademiya Nauk. Matematicheskie Zametki 17 (1975), 839–849; English translation; Mathematical Notes 17 (1975) I. Shparlinski, On exponential sums with sparse polynomials and rational functions, Journal of Number Theory 60 (1996), 233–255. S. B. Steˇ ckin, An estimate of a complete rational trigonometric sum, Proceedings of the Steklov Institute of Mathematics 143 (1977), 188–207, 211; English translation; Americam Mathematical Society Issue 1 (1980), 201–220.