New estimates of double trigonometric sums with exponential functions

M. Z. Garaev Instituto de Matemáticas, Universidad Nacional Autónoma de México Campus Morelia, Apartado Postal 61-3 (Xangari) C.P. 58089, Morelia, Michoacán, México garaev@matmor.unam.mx

A. A. Karatsuba Steklov Institute of Mathematics Russian Academy of Sciences GSP-1, ul. Gubkina 8 Moscow, Russia karatsuba@mi.ras.ru

Abstract
We establish a new bound for the exponential sum 1
∑ x ∈ X | ∑ y ∈ Y γ ( y ) exp ( 2 π i a λ x y / p ) | ,
where λ   is an element of the residue ring modulo a large prime number p ,   X   and Y   are arbitrary subsets of the residue ring modulo p − 1   and γ ( n )   are any complex numbers with | γ ( n ) | ≤ 1 .   In particular, we improve several previously known bounds.
2000 Mathematics Subject Classification: 11L07, 11L26, 11T23.

1 Introduction

Let p   be a large prime number, T   be a divisor of p − 1 .   For a positive integer m   we denote by Z m = { 0 , 1 , . . . , m − 1 }   the residue ring modulo m .   Let λ   be an element of Z p   of multiplicative order T ,   i.e. λ = g ( p − 1 ) / T   for some primitive root g   modulo p .   Let γ ( n )   be any complex coefficients with | γ ( n ) | ≤ 1 .   Denote e m ( z ) = exp ( 2 π i z / m ) .   In this paper we investigate the sum W a ( γ ; T ; X , Y ) = ∑ x ∈ X | ∑ y ∈ Y γ ( y ) e p ( a λ x y ) | ,   where a   is an integer coprime to p ,   X   and Y   are arbitrary subsets of the residue ring Z p − 1   with | X |   and | Y |   elements correspondingly. This sum is well known and proved to be very important in many applications, see the recent works [1] –[11] , [13] and therein references.
Recently in [10] a new approach was suggested to estimate W a ( γ ; T ; X , Y ) .   One of the advantages of the new approach compared to the previously known ones is that it finds its applications also to bound similar sums taken over points on an elliptic curve, or to bound the corresponding multiplicative character sums, see [3] for the details. The aim of the present paper is to introduce a new ingredient to the argument of [10] which leads to a new estimate for W a ( γ ; T ; X , Y )   and which, in particular cases, improves several previously known bounds. Moreover, the new argument in prospective can also find its applications to modify the corresponding estimates of [3] .
The following statement is the result of our paper.
Theorem 1. For any given positive integer k ,   the following estimate holds:
W a ( γ ; T ; X , Y ) ≪ | X | 1 − 1 2 k | Y | 1 − 1 2 k + 2 p 1 2 k + 3 4 k + 4 + o ( 1 ) T 1 2 k + 2 .  
Throughout the paper the implied constants in the Landau ` O   ' and ` o   ' symbols as well as in the Vinogradov symbols ` ≪   ' and ` ≫   ' may depend on the small positive quantity ɛ   and on the fixed positive integer k   . We use g   to denote a primitive root modulo p .  

2 Corollaries

J. B. Friedlander and I. E. Shparlinski [7] for the sum W a ( X , Y ) = ∑ x ∈ X | ∑ y ∈ Y e p ( a g x y ) |   proved the estimate W a ( X , Y ) ≪ | X | 1 / 2 | Y | 5 / 6 p 5 / 8 + o ( 1 ) .   If | X | ≥ | Y | ≥ p 15 / 16 + ɛ ,   then this estimate provides a nontrivial upper bound for S a ( X , Y ) .   In [10] the above bound has been improved to W a ( γ ; p − 1 ; X , Y ) ≪ | X | 1 / 2 | Y | 1 / 2 p 7 / 8 + o ( 1 )   which is nontrivial when | X | ≥ | Y | ≥ p 7 / 8 + ɛ .   Theorem  1 improves this bound further to the following statement.
Corollary 2. The estimate W a ( γ ; p − 1 ; X , Y ) ≪ | X | 1 − 1 2 k | Y | 1 − 1 2 k + 2 p 1 2 k + 1 4 k + 4 + o ( 1 )   holds.
In particular, taking k   to be sufficiently large, we see that our estimate is nontrivial when | X | ≥ | Y | ≥ p 3 / 4 + ɛ .   Let X T , Y T ⊂ Z T   and let W a ( T ; X T , Y T ) = ∑ x ∈ X T | ∑ y ∈ Y T e p ( a λ x y ) | .   In [7] it is shown that | W a ( T ; X T , Y T ) | ≪ T 11 / 6 p 1 / 8 .   In [10] this bound has been improved to
W a ( γ ; T ; X T , Y T ) ≪ | X T | 1 / 2 | Y T | 1 / 2 T 3 / 4 p 1 / 8 + o ( 1 ) . (1)
From Theorem  1 we have the following consequence.
Corollary 3. For any sets X T ⊂ Z T   and Y T ⊂ Z T ,   the estimate
W a ( γ ; T ; X T , Y T ) ≪ | X T | 1 − 1 2 k | Y T | 1 − 1 2 k + 2 T 1 2 k p 1 4 k + 4 + o ( 1 ) .
holds.
In particular, if Y T   is not sufficiently dense in Z T ,   then Corollary  3 with k = 1   improves the estimate  1 .
To prove Corollary  3 , we note that in Theorem  1 the sets X   and Y   are arbitrary subsets of Z p − 1 .   We shift the set X T   by r T   with 1 ≤ r ≤ p − 1 T   and take X   to be the union of these sets. Analogously we define Y .   Then | X | = ( p − 1 ) | X T | T , | Y | = ( p − 1 ) | Y T | T .   Therefore, the estimate of Theorem  1 takes the form
p 2 T 2 W a ( γ ; T ; X T , Y T ) ≪ ( p T ) 2 − 1 2 k − 1 2 k + 2 | X T | 1 − 1 2 k | Y T | 1 − 1 2 k + 2 p 1 2 k + 3 4 k + 4 + o ( 1 ) T 1 2 k + 2 ,
whence Corollary  3 .
It is to be remarked that from Theorem  1 as a consequence one derives the bound W a ( γ ; T ; X , Y ) ≪ | X | 1 / 2 | Y | 3 / 4 p 7 / 8 + o ( 1 ) T 1 / 4 .   This bound has been proved in [11] in the case when Y   is an interval. Also note that this bound includes the best previously known one (see [10] ) and improves it for any thin set Y ,   i.e., when | Y | ≤ p 1 − c   for some c > 0 .  

3 The main statement

For a given divisor d   of p − 1 ,   let ℒ d   be any subset of Z ( p − 1 ) / d   such that the elements of ℒ d   are relatively prime to ( p − 1 ) / d .   The following Lemma is crucial in proving Theorem  1 .
Lemma 4. If d < T p − 1 2 ( log p ) − 4 k   then the inequality ∑ x ∈ X | ∑ y ∈ ℒ d γ ( d y ) e p ( a g t d x y ) | ≪ | X | 1 − 1 2 k | ℒ d | 1 − 1 2 k + 2 p 1 2 k + 3 4 k + 4 log p T 1 2 k + 2 .   holds.
  • Proof. We recall that the constant implicit in the symbol ≪   may depend on the fixed positive integer k .   Therefore, we may suppose that p > k .   Let ℓ   be an integer to be chosen later and satisfying the condition log p < ℓ < p 2 k + 1 2 k + 2 .   Denote by V   the set of the first ℓ   prime numbers coprime to p − 1 d .   Since for any positive integer m   there are O ( log m )   (even O ( log m / log log m )   ) different prime divisors of m ,   then from Chebyshev's theorem it is immediate that for any v ∈ V   we have v ≪ ( | V | + log p ) log p ≪ | V | log p ,   where | V | = ℓ   denotes the cardinality of V .   For a given divisor d | p − 1   denote by U d   the set of all elements of the ring Z ( p − 1 ) / d   relatively prime to ( p − 1 ) / d ,   that is U d = Z ( p − 1 ) / d * .   For a given integer y   with ( y , ( p − 1 ) / d ) = 1   consider the congruence
    u v ≡ y ( m o d ( ( p − 1 ) / d ) ) , u ∈ U d , v ∈ V . (2)
    The number of solutions of this congruence is exactly equal to | V | .   This follows from the fact that once v   is fixed then u   is determined uniquely. We replace λ   by g t ,   where t = ( p − 1 ) / T ,   and consider the sum ∑ y ∈ ℒ d γ ( d y ) e p ( a g t d x y ) .   Let δ ( y ) : = δ ( ℒ d ; y )   be the characteristic function of the set ℒ d   in the ring Z ( p − 1 ) / d .   Since the number of solutions of the congruence ( 2 ) is equal to | V |   for any fixed y ∈ ℒ d ,   then ∑ y ∈ ℒ d γ ( d y ) e p ( a g t d x y ) = 1 | V | ∑ u ∈ U d ∑ v ∈ V γ ( d u v ) δ ( u v ) e p ( a g t d x u v ) .   Therefore, setting
    ℛ a ( γ ; d , X , ℒ d ) = ∑ x ∈ X | ∑ y ∈ ℒ d γ ( d y ) e p ( a g t d x y ) | (3)
    we see that ℛ a ( γ ; d , X , ℒ d ) = 1 | V | ∑ x ∈ X | ∑ u ∈ U d ∑ v ∈ V γ ( d u v ) δ ( u v ) e p ( a g t d x u v ) | ,   whence ℛ a ( γ ; d , X , ℒ d ) ≤ 1 | V | ∑ u ∈ U d ∑ x ∈ X | ∑ v ∈ V γ ( d u v ) δ ( u v ) e p ( a g t d x u v ) | .   Application of Hölder's inequality to the sum over x   yields ℛ a ( γ ; d , X , ℒ d ) ≤ | X | 1 − 1 2 k | V | ∑ u ∈ U d ( ∑ x = 1 p − 1 | ∑ v ∈ V γ ( d u v ) δ ( u v ) e p ( a g t d x u v ) | 2 k ) 1 / 2 k .   If ( n , p − 1 ) = d ,   if x   runs through Z p − 1   and if z   runs through the reduced residue system modulo p ,   then g n x   and z d   run the same system of residues modulo p   (including the multiplicities). Since ( d u , p − 1 ) = d ,   then
    ℛ a ( γ ; d , X , ℒ d ) ≤ | X | 1 − 1 2 k | V | ∑ u ∈ U d M u 1 / 2 k , (4)
    where M u = ∑ z = 1 p − 1 | ∑ v ∈ V γ ( d u v ) δ ( u v ) e p ( a z t d v ) | 2 k .   In order to estimate M u ,   we observe that M u = ∑ v 1 ∈ V … ∑ v 2 k ∈ V ( k ∏ j = 1 2 k ∏ s = k + 1 γ ( d u v j ) γ ( d u v s ) ¯ δ ( u v j ) δ ( u v s ) ) S ( v 1 , … , v 2 k ) ,   where S ( v 1 , … , v 2 k ) = ∑ z = 1 p − 1 e p ( a z t d v 1 + … + a z t d v k − a z t d v k + 1 − … − a z t d v 2 k ) .   Note that if the set of values v 1 , … , v k   is a permutation of the set of values v k + 1 , … , v 2 k ,   then S ( v 1 , … , v 2 k ) = p − 1 .   Otherwise, we have a z t d v 1 + … + a z t d v k − a z t d v k + 1 − … − a z t d v 2 k = a ( a 1 z + a 2 z 2 + … + a r z r ) ,   where a i , 1 ≤ i ≤ r ,   are integers and for some j   we have ( a a j , p ) = 1   (here we use that p > k   ). Hence, in this case we can apply the classical Weil bound (see Chapter 5 of [12] ) to obtain S ( v 1 , … , v 2 k ) ≤ ( t d max 1 ≤ i ≤ 2 k v i ) p 1 / 2 ≪ t d | V | p 1 / 2 log p .   Therefore, putting all together and using the condition | γ ( n ) | ≤ 1 ,   we deduce the bound M u ≪ ∑ v 1 ∈ V … ∑ v k ∈ V ( k ∏ j = 1 δ ( u v j ) ) p + ∑ v 1 ∈ V … ∑ v 2 k ∈ V ( 2 k ∏ j = 1 δ ( u v j ) ) t d | V | p 1 / 2 log p ,   whence M u ≪ ( ∑ v ∈ V δ ( u v ) ) k p + ( ∑ v ∈ V δ ( u v ) ) 2 k t d | V | p 1 / 2 log p .   Combining this estimate with  4 , we derive
    ℛ a ( γ ; d , X , ℒ d ) ≪ | X | 1 − 1 2 k p 1 / 2 k | V | ∑ u ∈ U d ( ∑ v ∈ V δ ( u v ) ) 1 / 2 +
    | X | 1 − 1 2 k | V | ( t d | V | p 1 / 2 log p ) 1 / 2 k ∑ u ∈ U d ∑ v ∈ V δ ( u v )
    Since the number of solutions of congruence ( 2 ) is equal to | V |   for any y ∈ ℒ d ,   then ∑ u ∈ U d ∑ v ∈ V δ ( u v ) = | V | | ℒ d | .   Besides, applying the Cauchy inequality we obtain that ∑ u ∈ U d ( ∑ v ∈ V δ ( u v ) ) 1 / 2 ≤ | U d | 1 / 2 ( ∑ u ∈ U d ∑ v ∈ V δ ( u v ) ) 1 / 2 ≤ ( p / d ) 1 / 2 | V | 1 / 2 | ℒ d | 1 / 2 .   Therefore,
    ℛ a ( γ ; d , X , ℒ d ) ≪ | X | 1 − 1 2 k p 1 / 2 k p 1 / 2 | ℒ d | 1 / 2 | V | 1 / 2 d 1 / 2 + | X | 1 − 1 2 k ( t d | V | p 1 / 2 log p ) 1 / 2 k | ℒ d | . (5)
    Let us define the number of elements of V .   Since | ℒ d | ≤ p / d ,   from the condition of the Lemma we see that ( log p ) 3 / 2 < p 2 k + 1 2 k + 2 d | ℒ d | k k + 1 t 1 k + 1 ( log p ) 1 k + 1 < p 2 k + 1 2 k + 2 .   Hence, we can define the number of elements of V   by taking ℓ = | V | = [ p 2 k + 1 2 k + 2 d | ℒ d | k k + 1 t 1 k + 1 ( log p ) 1 k + 1 ] .   Inserting this into  5 , we obtain ℛ a ( γ ; d , X , ℒ d ) ≪ | X | 1 − 1 2 k p 1 2 k + 3 4 k + 4 | ℒ d | 1 − 1 2 k + 2 log p T 1 2 k + 2 .   Lemma  4 is proved.

4 Proof of Theorem  1 

If T 2 k + 1 2 k + 2 ≤ | X | 1 / 2 k | Y | − 1 + 1 2 k + 2 p 3 2 − 1 2 k − 3 4 k + 4 ,   then one can easily check that | X | 1 − 1 2 k | Y | 1 − 1 2 k + 2 p 1 2 k + 3 4 k + 4 T 1 2 k + 2 ≥ | X | 1 − k + 1 k ( 2 k + 1 ) | Y | p k + 1 k ( 2 k + 1 ) ≥ | X | | Y | .   Hence, in this case the estimate of Theorem  1 becomes trivial. Therefore, we may suppose that
T 2 k + 1 2 k + 2 ≥ | X | 1 / 2 k | Y | − 1 + 1 2 k + 2 p 3 2 − 1 2 k − 3 4 k + 4 . (6)
Similarly, we may assume that T > p 1 / 2 ( log p ) 10 k .   For a given divisor d | p − 1   we denote by ℒ d   the set of integers y   such that d y ∈ Y   and ( d y , p − 1 ) = d .   Then
W a ( γ ; T ; X , Y ) ≤ ∑ d | p − 1 ℛ a ( γ ; d , X , ℒ d ) , (7)
where ℛ a ( γ ; d , X , ℒ d )   is defined by ( 3 ).
Note that | ℒ d | ≤ min { | Y | , p / d } .   For the divisors d | p − 1   with the condition d ≥ T p − 1 2 ( log p ) − 4 k   we use the trivial estimate ℛ a ( γ ; d , X , ℒ d ) ≤ | X | | ℒ d | ≤ | X | p T p − 1 2 ( log p ) − 4 k = | X | p 3 2 ( log p ) 4 k T .   For d < T p − 1 2 ( log p ) − 4 k   we apply the bound of Lemma  4 ;
ℛ a ( γ ; d , X , ℒ d ) ≪ | X | 1 − 1 2 k | Y | 1 − 1 2 k + 2 p 1 2 k + 3 4 k + 4 log p T 1 2 k + 2 .
Inserting these bounds into ( 7 ) and noting that τ ( p − 1 ) = p o ( 1 ) ,   we deduce the estimate W a ( γ ; T ; X , Y ) ≪ | X | 1 − 1 2 k | Y | 1 − 1 2 k + 2 p 1 2 k + 3 4 k + 4 + o ( 1 ) T 1 2 k + 2 + | X | p 3 2 + o ( 1 ) T ,   whence, due to the inequality  6 , we conclude that W a ( γ ; T ; X , Y ) ≪ | X | 1 − 1 2 k | Y | 1 − 1 2 k + 2 p 1 2 k + 3 4 k + 4 + o ( 1 ) T 1 2 k + 2 .   Theorem  1 is proved.
References

  1. W. D. Banks, J. B. Friedlander, M. Z. Garaev and I. E. Shparlinski, Exponential sums over smooth numbers, (Preprint).
  2. W. D. Banks, A. Conflitti, J. B. Friedlander and I. E. Shparlinski, Exponential sums over Mersenne numbers, Compos. Math. 140, no. 1, 15–30 (2004).
  3. W. D. Banks, J. B. Friedlander, M. Z. Garaev and I. E. Shparlinski, Double character sums over finite fields and elliptic curves and their applications, (Preprint).
  4. J. Bourgain, New bounds on exponential sums related to Diffie-Hellman distributions, C. R. Math. Acad. Sci. Paris, 338, no. 11, 825–830 (2004).
  5. R. Canetti, J. Friedlander and I. Shparlinski, On certain exponential sums and the distribution of Diffie-Hellman triples, J. London Math. Soc., 59, 799–812 (1999).
  6. R. Canetti, J. Friedlander, S. Konyagin, M. Larsen, D. Lieman and I. Shparlinski, On the statistical properties of Diffie-Hellman distribution, Isr. J. Math., 120, 23–46 (2000).
  7. J. B. Friedlander and I. E. Shparlinski Double exponential sums over thin sets, Proc. Amer. Math. Soc., 129, 1617–1621 (2001).
  8. J. B. Friedlander and I. E. Shparlinski, On the distribution of Diffie-Hellman triples with sparse exponents, SIAM J. Discrete Math. 14 , no. 2, 162–169 (2001).
  9. J. B. Friedlander, S. V. Konyagin and I. E. Shparlinski, Some doubly exponential sums over Z m   , Acta Arith., 105, 349–370 (2002).
  10. M. Z. Garaev, Double exponential sums related to Diffie-Hellman distributions, Int. Math. Res. Notices (to appear).
  11. M. Z. Garaev and A. A. Karatsuba, On a symmetric congruence and its applications, arXiv:math.NT/0503164.
  12. R. Lidl and H. Niederreiter, `Finite fields', Cambridge University Press, Cambridge, 1997.
  13. I. E. Shparlinski, On the distribution of the Diffie-Hellman pairs, Finite Fields Appl. 8, no. 2, 131–141 (2002).