On a symmetric congruence and its applications

M. Z. Garaev Instituto de Matemáticas, UNAM 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
For a large integer m ,   we obtain an asymptotic formula for the number of solutions of a certain congruence modulo m   with four variables, where the variables belong to special sets of residue classes modulo m .   This formula are applied to obtain a new bound for a double trigonometric sum with an exponential function and new information on the exceptional set of the multiplication table problem in a residue ring modulo m .   1

1 Introduction

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 ɛ .   By p   and q   we will always denote prime numbers.
Let m   be an integer parameter, V   be any subset of prime numbers coprime to m   and not exceeding m 1 / 2 ,   and let S   and L   be any integers with 0 < L ≤ m .   In this paper we obtain an asymptotic formula for the number of solutions of the congruence v 1 y 1 ≡ v 2 y 2 ( m o d m ) , v 1 , v 2 ∈ V , S + 1 ≤ y 1 , y 2 ≤ S + L   and give its applications.
Below | V |   stands for the number of elements in V .   By τ ( m )   we denote the classical divisor function.
Theorem 1. The following asymptotic formula holds:
J = | V | 2 L 2 m + | V | L − | V | L 2 m + O ( m 2 log 2 m φ ( m ) ) ,   where φ ( m )   is the Euler function.
Theorem  1 finds its application in estimating of double trigonometric sums with an exponential function. For a positive integer m   we denote by Z m = { 0 , 1 , . . . , m − 1 }   the residue ring modulo m .   Let p   be a large prime number, T   be a divisor of p − 1 ,   λ   be an element of Z p   of multiplicative order T ,   i.e. λ = g ( p − 1 ) / T   for some primitive root g   modulo p ,   γ ( n )   be any complex coefficients with | γ ( n ) | ≤ 1 .   Denote e m ( z ) = exp ( 2 π i z / m ) .  
Theorem 2. Let a   be any integer coprime to m .   For any integers K   and N   with 0 < K + 1 ≤ K + N ≤ p − 1 , N ≥ T p − 1 / 2 ( log p ) 3   and any set X ⊂ Z p − 1 ,   the inequality ∑ x ∈ X | ∑ y = K + 1 K + N γ ( y ) e p ( a λ x y ) | ≪ | X | 1 / 2 N 3 / 4 p 7 8 + o ( 1 ) T 1 / 4 .   holds, where | X |   denotes the cardinality of the set X .  
Corollary 3. Let a   be any integer coprime to m .   For any integers K , N , L , M   with 0 < K + 1 ≤ K + N ≤ p − 1 , 0 < L + 1 ≤ L + M ≤ p − 1   and any coefficients α x   and β y   with | α x | ≤ 1 ,   | β y | ≤ 1 ,   the following inequality holds:
| ∑ x = L + 1 L + M ∑ y = K + 1 K + N α x β y e p ( a g x y ) | ≪ ( N M ) 5 / 8 p 5 / 8 + o ( 1 ) .  
This estimate is nontrivial when N ≥ M ≥ p 5 / 6 + ɛ .   For more information on trigonometric sums with an exponential function and their applications, see [1] -[5] and therein references.
To prove Corollary  3 we observe that the statement is trivial if N ≤ p 2 / 3   or if M ≤ p 2 / 3 .   Assuming min { N , M } > p 2 / 3 ,   from Theorem  2 we derive, | ∑ x = L + 1 L + M ∑ y = K + 1 K + N α x β y e p ( a g x y ) | ≪ ∑ x = L + 1 L + M | ∑ y = K + 1 K + N β y e p ( a g x y ) | ≪ M 1 / 2 N 3 / 4 p 5 / 8 + o ( 1 ) ,   | ∑ x = L + 1 L + M ∑ y = K + 1 K + N α x β y e p ( a g x y ) | ≪ ∑ y = K + 1 K + N | ∑ x = L + 1 L + M α x e p ( a g x y ) | ≪ N 1 / 2 M 3 / 4 p 5 / 8 + o ( 1 ) .   The result now follows.
In passing, we remark that Theorem  2 and Corollary  3 remain true if e p ( a g x y )   is replaced by χ ( g x y + a ) ,   where χ   is any nonprincipal character modulo p .   Theorem  1 also finds its application in the problem of multiplication of intervals in a residue ring modulo m .  
Corollary 4. For any fixed ɛ > 0   the set { x y ( m o d m ) : 1 ≤ x ≤ m 1 / 2 , S + 1 ≤ y ≤ S + m 1 / 2 ( log m ) 2 + ɛ }   contains ( 1 + O ( ( log m ) − ɛ ) ) m   residue classes modulo m .  
The classical conjecture claims that for any prime number p   any nonzero residue class modulo p   can be represented in the form x y ( m o d p ) ,   where 1 ≤ x , y ≤ p 1 / 2 + o ( 1 ) .   A weaker version of this conjecture has been stated in [6] , namely, for any prime p   there are ( 1 + o ( 1 ) ) p   residue classes modulo p   of the form x y ( m o d p )   with 1 ≤ x , y ≤ p 1 / 2 + o ( 1 ) .   Furthermore, in [6] it has been proved that for almost all primes p   almost all residue classes modulo p   are representable in the form x y ( m o d p )   with 1 ≤ x , y ≤ p 1 / 2 ( log p ) 1 , 087 .   The following consequence of Corollary  4 confirms the validity of the weaker version of the classical conjecture and essentially improves one of our results from [8] .
Corollary 5. For any fixed ɛ > 0   and any prime number p   the set { x y ( m o d p ) : 1 ≤ x , y ≤ p 1 / 2 ( log p ) 2 + ɛ }   contains ( 1 + o ( 1 ) ) p   residue classes modulo p .  
The method of the proof of Theorem  1 combined with an argument similar to that of [7] allows to improve the exponent of the logarithmic factor in Corollaries  4 and  5 . More precisely, the following statement takes place.
Theorem 6. Let Δ = Δ ( m ) → ∞   as m → ∞ .   Then the set { q y ( m o d m ) : 1 ≤ q ≤ m 1 / 2 , S + 1 ≤ y ≤ S + Δ m 1 / 2 m / φ ( m ) log m }   contains ( 1 + O ( Δ − 1 ) ) m   residue classes modulo m .  
In particular we have
Corollary 7. Let Δ = Δ ( p ) → ∞   as p → ∞ .   Then the set { q y ( m o d p ) : 1 ≤ q ≤ p 1 / 2 , 1 ≤ y ≤ Δ p 1 / 2 log p }   contains ( 1 + O ( Δ − 1 ) ) p   residue classes modulo p .  
Since there are O ( p 1 / 2 ( log p ) − 1 )   primes not exceeding p 1 / 2 ,   we see that the set { q y : 1 ≤ x ≤ p 1 / 2 , S + 1 ≤ y ≤ S + Δ p 1 / 2 log p }   contains only O ( p Δ )   integers. This shows that the ranges of variables in Theorem  6 and Corollary  7 are sufficiently sharp.
We will also prove the corresponding result for the ratio of intervals modulo a prime which improves one of the results of [6] .
Theorem 8. Let Δ = Δ ( p ) → ∞   as p → ∞ .   Then the set { x y − 1 ( m o d p ) : N + 1 ≤ x ≤ N + Δ p 1 / 2 , S + 1 ≤ y ≤ S + Δ p 1 / 2 }   contains ( 1 + O ( Δ − 2 ) ) p   residue classes modulo p .  
Note however, that when N = S = 0   and Δ < p 1 / 2 / 2 ,   the set described in Theorem  8 misses ≫ p 1 / 2 Δ − 1   reside classes modulo p ,   see [6] .
For the detailed description on the multiplication table problem modulo a prime, see [6] and also [8] .
The proofs of the results of [6] and [8] are based on estimates of multiplicative character sums. The approach we use here is based on trigonometric sums.

2 Proof of Theorem  1 

Recall that J   denotes the number of solutions to the congruence v 1 y 1 ≡ v 2 y 2 ( m o d m ) , v 1 , v 2 ∈ V , S + 1 ≤ y 1 , y 2 ≤ S + L .   We express J   in terms of trigonometric sums. Since v 1 v 2 − 1 y 1 ≡ y 2 ( m o d m ) ,   then J = 1 m ∑ a = 0 m − 1 ∑ v 1 ∈ V ∑ v 2 ∈ V ∑ y 1 ∈ I ∑ y 2 ∈ I e m ( a ( v 1 v 2 − 1 y 1 − y 2 ) ) ,   where I   denotes the interval [ S + 1 , S + L ] .   Picking up the term corresponding to a = 0 ,   we obtain J = | V | 2 L 2 m + 1 m ∑ a = 1 m − 1 ∑ v 1 ∈ V ∑ v 2 ∈ V ∑ y 1 ∈ I ∑ y 2 ∈ I e m ( a ( v 1 v 2 − 1 y 1 − y 2 ) ) .   Furthermore,
1 m ∑ a = 1 m − 1 ∑ v 1 ∈ V ∑ v 2 ∈ V ∑ y 1 ∈ I ∑ y 2 ∈ I e m ( a ( v 1 v 2 − 1 y 1 − y 2 ) ) =
1 m ∑ a = 1 m − 1 ∑ v ∈ V ∑ y 1 ∈ I ∑ y 2 ∈ I e m ( a ( y 1 − y 2 ) ) +
1 m ∑ a = 1 m − 1 ∑ v 1 ∈ V ∑ v 2 ∈ V v 2 ≠ v 1 ∑ y 1 ∈ I ∑ y 2 ∈ I e m ( a ( v 1 v 2 − 1 y 1 − y 2 ) ) =
| V | L − | V | L 2 m + 1 m ∑ a = 1 m − 1 ∑ v 1 ∈ V ∑ v 2 ∈ V v 2 ≠ v 1 ∑ y 1 ∈ I ∑ y 2 ∈ I e m ( a ( v 1 v 2 − 1 y 1 − y 2 ) ) .
Therefore J = | V | 2 L 2 m + | V | L − | V | L 2 m + θ 1 m ∑ a = 1 m − 1 ∑ v 1 ∈ V ∑ v 2 ∈ V v 2 ≠ v 1 | ∑ y 1 ∈ I ∑ y 2 ∈ I e m ( a ( v 1 v 2 − 1 y 1 − y 2 ) ) | .   Here θ 1 ,   and θ j   everywhere below, denote some functions with | θ j | ≤ 1 .   For a given n   let r ( n )   be the number of solutions of the congruence v 1 v 2 − 1 ≡ n ( m o d m ) , v 1 , v 2 ∈ V , v 1 ≠ v 2 .   In particular r ( 1 ) = 0 ,   and if ( n , m ) > 1 ,   then r ( n ) = 0 .   Therefore, the above formula takes the form J = | V | 2 L 2 m + | V | L − | V | L 2 m + θ 1 m ∑ a = 1 m − 1 ∑ 1 ≤ n ≤ m ( n , m ) = 1 r ( n ) | ∑ y 1 ∈ I ∑ y 2 ∈ I e m ( a ( n y 1 − y 2 ) ) | .   It is important to note that v 2 ≤ m   for any v ∈ V .   For this reason we have r ( n ) ≤ 1   for any n , 1 ≤ n ≤ m .   Indeed, if v 1 v 2 − 1 ≡ v 3 v 4 − 1 ( m o d m )   for some v 1 , v 2 , v 3 , v 4 ∈ V   and if v 1 ≠ v 2 ,   then v 1 v 4 ≡ v 3 v 2 ( m o d m ) .   Since v 2 ≤ m   for any v ∈ V ,   then we derive that v 1 v 4 = v 3 v 2 .   But V   consists only on prime numbers and v 1 ≠ v 2 .   Hence, v 1 = v 3 , v 2 = v 4 .   Thus
J = | V | 2 L 2 m + | V | L − | V | L 2 m + θ 2 m ∑ a = 1 m − 1 ∑ 1 ≤ n ≤ m ( n , m ) = 1 | ∑ y 1 ∈ I ∑ y 2 ∈ I e m ( a ( n y 1 − y 2 ) ) | . (1)
It is now useful to recall the bound | ∑ y ∈ I e m ( b y ) | ≤ 1 | sin ( π b / m | ,   which, in application to  1 , yields
J = | V | 2 L 2 m + | V | L − | V | L 2 m + θ 3 m ∑ a = 1 m − 1 ∑ 1 ≤ n ≤ m ( n , m ) = 1 1 | sin ( π a n / m | 1 | sin ( π a / m | . (2)
For each divisor s | m   we collect together the values of a   with ( a , m ) = s .   Then
∑ a = 1 m − 1 ∑ 1 ≤ n ≤ m ( n , m ) = 1 1 | sin ( π a n / m | 1 | sin ( π a / m | =
∑ s | m ∑ 1 ≤ a ≤ m − 1 ( a , m ) = s ∑ 1 ≤ n ≤ m ( n , m ) = 1 1 | sin ( π a n / m | 1 | sin ( π a / m | ≤
∑ s | m s < m s ∑ 1 ≤ b ≤ m / s − 1 ( b , m / s ) = 1 ∑ 1 ≤ n ≤ m / s ( n , m / s ) = 1 1 | sin ( π b n / ( m / s ) | 1 | sin ( π b / ( m / s ) | ≤
∑ s | m s < m s ( ∑ 1 ≤ b ≤ m / s ( b , m / s ) = 1 1 | sin ( π b / ( m / s ) | ) 2 ≪
∑ s | m s < m s ( ∑ 1 ≤ b ≤ m / 2 s m b s ) 2 ≤ m 3 log 2 m φ ( m ) ,
where we have used the inequality ∑ s | m 1 s ≤ ∏ p | m 1 1 − p − 1 = m φ ( m ) .   Inserting this bound into  2 , we obtain the required estimate.

3 Proof of Theorem  2 

If | X | 1 / 2 N 1 / 4 T 1 / 4 p − 7 / 8 ≤ 10   then the estimate of Theorem  2 becomes trivial. Therefore, we can suppose that Q : = | X | 1 / 2 N 1 / 4 T 1 / 4 p − 7 / 8 ≥ 10 .   For a given divisor d | p − 1   let ℒ d   be the set of all integers y   such that d y ∈ [ K + 1 , K + N ]   and ( d y , p − 1 ) = d .   Then
W a ( γ ; T ; X ; K , N ) ≤ ∑ d | p − 1 ℛ a ( γ ; d , X , ℒ d ) , (3)
where ℛ a ( γ ; d , X , ℒ d )   is defined by ℛ a ( γ ; d , X , ℒ d ) = ∑ x ∈ X | ∑ y ∈ ℒ d γ ( d y ) e p ( a g t d x y ) |   Note that | ℒ d | ≤ N d − 1 + 1   and that the elements of ℒ d   are relatively prime to ( p − 1 ) / d .   For the divisors d | p − 1   with the condition d ≥ Q   we use the trivial estimate ℛ a ( γ ; d , X , ℒ d ) ≤ | X | | ℒ d | ≤ | X | N Q + | X | ≪ | X | 1 / 2 N 3 / 4 p 7 / 8 T 1 / 4 .   Therefore, in view of τ ( p − 1 ) ≤ p o ( 1 ) ,   from  3 we obtain
W a ( γ ; T ; X ; K , N ) ≪ ∑ d | p − 1 d ≤ Q ℛ a ( γ ; d , X , ℒ d ) + | X | 1 / 2 N 3 / 4 p 7 / 8 + o ( 1 ) T 1 / 4 . (4)
Below we suppose that d ≤ Q   (and therefore | ℒ d | ≤ 2 N d − 1   ) and our aim is to obtain a suitable upper bound for ℛ a ( γ ; d , X , ℒ d ) .   Observe that if p 1 / 4 T 1 / 2 N − 1 / 2 Q − 1 / 2 ≤ log p   then the estimate of Theorem  2 becomes trivial. Indeed, in this case we would have that p 1 / 4 T 1 / 2 N − 1 / 2 | X | − 1 / 4 N − 1 / 8 T − 1 / 8 p 7 / 16 ≤ log p .   Therefore, T 1 / 4 ≤ | X | 1 / 6 N 5 / 12 p − 11 / 24 + o ( 1 ) ,   whence | X | 1 / 2 N 3 / 4 p 7 / 8 + o ( 1 ) T 1 / 4 = | X | 1 / 3 N 1 / 3 p 4 / 3 + o ( 1 ) ≥ | X | N .   Hence, without loss of generality we may assume that
p 1 / 4 T 1 / 2 N − 1 / 2 Q − 1 / 2 ≥ log p . (5)
Denote by V   the set of the first [ p 1 / 4 T 1 / 2 N − 1 / 2 d − 1 / 2 ]   prime numbers which are not divisible by p − 1 .   Since any positive integer m   has only O ( log m )   (even O ( log m / log log m )   ) different prime divisors, then from  5 we deduce that for any v ∈ V   we have v ≪ ( | V | + log p ) log p ≪ | V | log p .   Here | V | ,   as before, denotes the cardinality of V ,   that is | V | = [ p 1 / 4 T 1 / 2 N − 1 / 2 d − 1 / 2 ] .   We observe that if T N ≤ p 3 / 2 ,   then the estimate of Theorem  2 again becomes trivial. Hence, we may suppose that
T N ≥ p 3 / 2 . (6)
Now we follow the idea of [5] in order to relate the problem of obtaining an upper bound for ℛ a ( γ ; d , X , ℒ d )   with Theorem  1 . 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 any 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 . (7)
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 ) .   Denote by δ ( y ) : = δ ( ℒ d ; y )   the characteristic function of the set ℒ d   in the ring Z ( p − 1 ) / d .   Since the number of solutions of the congruence ( 7 ) 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 , V , ℒ d ) = ∑ x ∈ X | ∑ y ∈ ℒ d γ ( d y ) e p ( a g t d x y ) |   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 ) | .   Application of the Cauchy inequality to the sums over x   and u   yields | ℛ a ( γ ; d , X , ℒ d ) | 2 ≤ | U d | | X | | V | 2 ∑ u ∈ U d ∑ x = 1 p − 1 | ∑ v ∈ V γ ( d u v ) δ ( u v ) e p ( a g t d x u v ) | 2 .   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 ) | 2 ≤ | U d | | X | | V | 2 ∑ u ∈ U d ∑ z = 1 p − 1 | ∑ v ∈ V γ ( d u v ) δ ( u v ) e p ( a z t d v ) | 2 ,   whence
| ℛ a ( γ ; d , X , ℒ d ) | 2 ≤
| U d | | X | | V | 2 ∑ u ∈ U d ∑ v 1 ∈ V ∑ v 2 ∈ V γ ( d u v 1 ) γ ( d u v 2 ) ¯ δ ( u v 1 ) δ ( u v 2 ) ∑ z = 1 p − 1 e p ( a ( z t d v 1 − z t d v 2 ) ) .
The rightmost sum is equal to p − 1   when v 1 = v 2   and, according to the Weil estimate, is bounded by ( max { v 1 , v 2 } ) t d p 1 / 2   when v 1 ≠ v 2 .   Recall that max { v 1 , v 2 } ≪ | V | log p ,   and | U d | = φ ( p − 1 d ) ≤ p d .   Therefore,
| ℛ a ( γ ; d , X , ℒ d ) | 2 (8)
≪ p 2 | X | d | V | 2 ∑ u ∈ U d ∑ v ∈ V δ 2 ( u v ) + p 3 / 2 | X | t log p | V | ∑ u ∈ U d ∑ v 1 ∈ V ∑ v 2 ∈ V δ ( u v 1 ) δ ( u v 2 ) . (9)
Next, from ( 7 ) we derive the formula
∑ u ∈ U d ∑ v ∈ V δ 2 ( u v ) = | V | | ℒ d | . (10)
Now set J = ∑ u ∈ U d ∑ v 1 ∈ V ∑ v 2 ∈ V δ ( u v 1 ) δ ( u v 2 )   and observe that J   is equal to the number of solutions of the system of congruences { u v 1 ≡ y 2 ( m o d p − 1 d ) u v 2 ≡ y 1 ( m o d p − 1 d )   subject to the conditions u ∈ U d , v 1 , v 2 ∈ V , y 1 , y 2 ∈ ℒ d .   It then follows that v 1 y 1 ≡ v 2 y 2 ( m o d p − 1 d ) .   Therefore, from  8 and  10 , we derive that | ℛ a ( γ ; d , X , ℒ d ) | 2 ≪ p 2 | X | d | V | 2 | V | | ℒ d | + p 5 / 2 | X | log p T | V | J ,   whence
| ℛ a ( γ ; d , X , ℒ d ) | 2 ≪ p 2 | X | N d 2 | V | + p 5 / 2 | X | log p T | V | J d , (11)
where J d   denotes the number of solutions of the congruence v 1 y 1 ≡ v 2 y 2 ( m o d p − 1 d ) , v 1 , v 2 ∈ V , K + 1 d ≤ y 1 , y 2 ≤ K + N d .   It is important to note that the condition of Theorem  2 yields, for any v ∈ V ,   the bound v 2 ≤ | V | 2 ( log p ) 2 + o ( 1 ) ≤ p 1 / 2 ( log p ) 2 + o ( 1 ) T N − 1 d − 1 ≤ p − 1 d .   Hence, we can apply Theorem  1 with m = ( p − 1 ) / d .   It gives J d ≪ | V | 2 N 2 ( p − 1 ) d + | V | N d + | V | N 2 p d + p ( log log p ) log 2 p d ,   whence, using | V | ≤ p 1 / 4 T 1 / 2 N − 1 / 2 ,   we obtain J d ≪ p − 1 / 2 + o ( 1 ) T N d ( 1 + p 3 / 4 T 1 / 2 N 1 / 2 + p 3 / 2 T N ) .   Taking into account  6 , we deduce J d ≪ p − 1 / 2 + o ( 1 ) T N d .   Combining this estimate with  11 , we conclude | ℛ a ( γ ; d , X , ℒ d ) | ≪ | V | 1 / 2 N 3 / 4 p 7 / 8 + o ( 1 ) d 1 / 4 T 1 / 4 .   The result now follows in view of  4 .

4 Proof of Theorem  6 

Without loss of generality we may suppose that Δ m 1 / 2 m / φ ( m ) log m < m ,   as otherwise the statement of Theorem  6 is trivial.
Denote by V   the set of prime numbers coprime to m   and not exceeding m 1 / 2 .   Let J   denote the number of solutions to the congruence v 1 ( y 1 + z 1 ) ≡ v 2 ( y 2 + z 2 ) ( m o d m )   subject to the conditions v 1 , v 2 ∈ V , y 1 , y 2 , z 1 , z 2 ∈ I ,   where I   denotes the set of integers x , [ S / 2 ] + 1 ≤ x ≤ [ S / 2 ] + L ,   and L = [ Δ m 1 / 2 m / φ ( m ) log m 2 ] .   Obviously that S + 1 ≤ y i + z i ≤ S + Δ m 1 / 2 log m , i = 1 , 2 .   Following the lines of the proof of Theorem  1 , we express J   in terms of trigonometric sums. Since v 1 v 2 − 1 ( y 1 + z 1 ) ≡ y 2 + z 2 ( m o d m ) ,   then J = 1 m ∑ a = 0 m − 1 ∑ v 1 ∈ V ∑ v 2 ∈ V ∑ y 1 , z 1 ∈ I ∑ y 2 , z 2 ∈ I e m ( a ( v 1 v 2 − 1 ( y 1 + z 1 ) − y 2 − z 2 ) ) .   Picking up the term corresponding to a = 0 ,   we obtain J = | V | 2 L 4 m + 1 m ∑ a = 1 m − 1 ∑ v 1 ∈ V ∑ v 2 ∈ V ∑ y 1 , z 1 ∈ I ∑ y 2 , z 2 ∈ I e m ( a ( v 1 v 2 − 1 ( y 1 + z 1 ) − y 2 − z 2 ) ) .   Since the number of solutions of the congruence y 1 + z 1 ≡ y 2 + z 2 ( m o d m ) , y 1 , z 1 , y 2 , z 2 ∈ I   is O ( L 3 ) ,   then we obtain
1 m | ∑ a = 1 m − 1 ∑ v ∈ V ∑ y 1 , z 1 ∈ I ∑ y 2 , z 2 ∈ I e m ( a ( y 1 + z 1 − y 2 − z 2 ) ) | ≤
| V | m ∑ a = 0 m − 1 | ∑ y ∈ I e m ( a y 1 ) | 4 ≪ | V | L 3 .
Therefore,
1 m ∑ a = 1 m − 1 ∑ v 1 ∈ V ∑ v 2 ∈ V ∑ y 1 , z 1 ∈ I ∑ y 2 , z 2 ∈ I e m ( a ( v 1 v 2 − 1 ( y 1 + z 1 ) − y 2 − z 2 ) ) =
O ( | V | L 3 ) + 1 m ∑ a = 1 m − 1 ∑ v 1 ∈ V ∑ v 2 ∈ V v 2 ≠ v 1 ∑ y 1 ∈ I ∑ y 2 ∈ I e m ( a ( v 1 v 2 − 1 ( y 1 + z 1 ) − y 2 − z 2 ) ) .
Using exactly the same argument that we used in the proof of Theorem  1 , we derive the formula J = | V | 2 L 4 m + O ( | V | L 3 ) + O ( R ) ,   where R = 1 m ∑ a = 1 m − 1 ∑ 1 ≤ n ≤ m ( n , m ) = 1 | ∑ y 1 , z 1 ∈ I ∑ y 2 , z 2 ∈ I e m ( a ( n ( y 1 + z 1 ) − y 2 − z 2 ) ) |   Next, introducing s = ( a , m ) ,   we obtain
R = 1 m ∑ s | m s < m ∑ b ≤ m / s − 1 ( b , m / s ) = 1 ∑ 1 ≤ n ≤ m ( n , m ) = 1 | ∑ y 1 , z 1 ∈ I ∑ y 2 , z 2 ∈ I e m / s ( b ( n ( y 1 + z 1 ) − y 2 − z 2 ) ) | ≤
1 m ∑ s | m s < m s ∑ b ≤ m / s − 1 ( b , m / s ) = 1 ∑ 1 ≤ n ≤ m / s ( n , m / s ) = 1 | ∑ y 1 , z 1 ∈ I ∑ y 2 , z 2 ∈ I e m / s ( b n ( y 1 + z 1 ) − b ( y 2 + z 2 ) ) | ≤
1 m ∑ s | m s < m s ( ∑ 1 ≤ n ≤ m / s ( n , m / s ) = 1 | ∑ y 1 , z 1 ∈ I e m / s ( n ( y 1 + z 1 ) ) | ) 2 =
1 m ∑ s | m s < m s ( ∑ 1 ≤ n ≤ m / s ( n , m / s ) = 1 | ∑ y ∈ I e m / s ( n y ) | 2 ) 2 .
Therefore,
J = | V | 2 L 4 m + O ( | V | L 3 ) + O ( R 1 ) + O ( R 2 ) , (12)
where
R 1 = 1 m ∑ s | m s < m / L s ( ∑ 1 ≤ n ≤ m / s ( n , m / s ) = 1 | ∑ y ∈ I e m / s ( n y ) | 2 ) 2 (13)
R 2 = 1 m ∑ s | m m / L ≤ s < m s ( ∑ 1 ≤ n ≤ m / s ( n , m / s ) = 1 | ∑ y ∈ I e m / s ( n y ) | 2 ) 2 (14)
If s < m / L   then m / s > L   and therefore, the congruence y 1 ≡ y 2 ( m o d m / s ) , y 1 , y 2 ∈ I   has L   solutions. Hence, ∑ 1 ≤ n ≤ m / s | ∑ y ∈ I e m / s ( n y ) | 2 = m L s ,   whence, using  13 ,
R 1 ≤ 1 m ∑ s | m s < m / L s ( ∑ 1 ≤ n ≤ m / s | ∑ y ∈ I e m / s ( n y ) | 2 ) 2 =
m L 2 ∑ s | m s < m / L s − 1 ≤ m L 2 ∑ s | m s − 1 ≤ m 2 L 2 φ ( m ) .
Inserting this bound into  12 , we deduce
J = | V | 2 L 4 m + O ( | V | L 3 ) + O ( m 2 L 2 / φ ( m ) ) + O ( R 2 ) . (15)
Now we proceed to estimate R 2 .   Note that in  14 we have ( n , m / s ) = 1 .   Therefore, for any integer K ,   ∑ y = K + 1 K + m / s e m / s ( n y ) = 0 ,   whence we deduce that there exist integers A   and B   with 0 < B ≤ m / s   such that ∑ y ∈ I e m / s ( n y ) = ∑ A < y ≤ A + B e m / s ( n y ) .   Hence
∑ 1 ≤ n ≤ m / s ( n , m / s ) = 1 | ∑ y ∈ I e m / s ( n y ) | 2 = ∑ 1 ≤ n ≤ m / s ( n , m / s ) = 1 | ∑ A < y ≤ A + B e m / s ( n y ) | 2 ≤
∑ n = 1 m / s | ∑ A < y ≤ A + B e m / s ( n y ) | 2 = m B / s ≤ m 2 / s 2 .
Taking this into account, from  14 we deduce R 2 ≤ 1 m ∑ s ≥ m / L s ( m 4 / s 4 ) ≪ m L 2 .   Therefore, in view of  15 , we obtain the asymptotic formula
J = | V | 2 L 4 m + O ( | V | L 3 ) + O ( m 2 L 2 / φ ( m ) ) =
| V | 2 L 4 m ( 1 + O ( m | V | L + m 3 φ ( m ) | V | 2 L 2 ) ) .
Recalling that | V | ≫ m 1 / 2 / log m   and L = [ Δ m 1 / 2 m / φ ( m ) log m 2 ] ,   we arrive at the formula J = | V | 2 L 4 m ( 1 + O ( Δ − 1 ) ) .   Next, define H = { q ( y + z ) ( m o d m ) , q ≤ m 1 / 2 , [ S / 2 ] + 1 ≤ y , z ≤ [ S / 2 ] + L } .   Obviously, S + 1 ≤ y + z ≤ S + Δ m 1 / 2 m / φ ( m ) log m .   For a given h ∈ H ,   by J ( h )   we denote the number of solutions of the congruence q ( y + z ) ≡ h ( m o d m ) , q ≤ m 1 / 2 , [ S / 2 ] + 1 ≤ y , z ≤ [ S / 2 ] + L .   Then J = ∑ h ∈ H J 2 ( h ) ≥ 1 | H | ( ∑ h ∈ H J ( h ) ) 2 = 1 | H | | V | 2 L 4 .   Therefore, | H | ≥ | V | 2 L 4 J ≥ m 1 + O ( Δ − 1 ) = ( 1 + O ( Δ − 1 ) ) m .   The result now follows in view of | H | ≤ m .  

5 Proof of Theorem  8 

Without loss of generality we may suppose that 0 < N < N + Δ p 1 / 2 < p , 0 < M < M + Δ p 1 / 2 < p .   Denote X = [ Δ p 1 / 2 / 2 ] ,   N 1 = [ N / 2 ] ,   S 1 = [ S / 2 ] ,   and let H *   be the set of all residue classes of the form ( x + t ) ( y + z ) − 1 ( m o d p ) ,   where N 1 + 1 ≤ x , t ≤ N 1 + X , S 1 + 1 ≤ y , z ≤ S 1 + X .   Obviously, N + 1 ≤ x + t ≤ N + Δ p 1 / 2 , S + 1 ≤ y + z ≤ S + Δ p 1 / 2 .   Next, let H 1 * = { h ( m o d p ) : h ∉ H * , h ≢ 0 ( m o d p ) } .   Then the congruence x + t − ( y + z ) h ≡ 0 ( m o d p )   has no solutions in variables h , x , t , y , z   subject to the condition h ∈ H 1 * , N 1 + 1 ≤ x , t ≤ N 1 + X , S 1 + 1 ≤ y , z ≤ S 1 + X .   Therefore, ∑ a = 0 p − 1 ∑ h ∈ H 1 * ∑ x , t ∈ I 1 ∑ y , z ∈ I 2 e 2 π i a ( x + t − h ( y + z ) ) p = 0 ,   where I 1   and I 2   denote the intervals [ N 1 + 1 , N 1 + X ]   and [ S 1 + 1 , S 1 + X ]   correspondingly.
Separating the term corresponding to a = 0   we deduce that | H 1 * | X 4 ≤ ∑ a = 1 p − 1 | ∑ x , t ∈ I 1 e 2 π i a ( x + t ) p | | ∑ y , z ∈ I 2 ∑ h ∈ H 1 * e 2 π i a h ( y + z ) p | .   On the other hand for ( a , p ) = 1   we have
| ∑ y , z ∈ I 2 ∑ h ∈ H 1 * e 2 π i a h ( y + z ) p | ≤ ∑ h ∈ H 1 * | ∑ y , z ∈ I 2 e 2 π i a h ( y + z ) p | ≤
∑ h = 1 p − 1 | ∑ y , z ∈ I 2 e 2 π i a h ( y + z ) p | ≤ ∑ h = 0 p − 1 | ∑ y , z ∈ I 2 e 2 π i h ( y + z ) p | = p X ,
and similarly, ∑ a = 1 p − 1 | ∑ x , t ∈ I 1 e 2 π i a ( x + t ) p | ≤ p X .   Hence | H 1 * | X 4 ≤ p 2 X 2 ,   whence | H 1 * | ≤ p 2 X 2 ≪ p Δ − 2 .   Since | H | = p − 1 − | H 1 * | ,   then the result follows.
References

  1. 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).
  2. W. D. Banks, J. B. Friedlander, M. Z. Garaev and I. E. Shparlinski, Exponential sums over smooth numbers, (Preprint).
  3. J. Bourgain, New bounds on exponential sums related to Diffie-Hellman distributions, C. R. Math. Acad. Sci. Paris, 338, no. 11, 825–830 (2004).
  4. J. B. Friedlander and I. E. Shparlinski Double exponential sums over thin sets, Proc. Amer. Math. Soc., 129, 1617–1621 (2001).
  5. M. Z. Garaev, Double exponential sums related to Diffie-Hellman distributions, Int. Math. Res. Notices (to appear).
  6. M. Z. Garaev, Character sums in short intervals and the multiplication table modulo a prime, Monatsh. Math. (to appear).
  7. M. Z. Garaev, On the logarithmic factor in error term estimates in certain additive congruence problems, Preprint.
  8. M. Z. Garaev and A. A. Karatsuba, On character sums and the exceptional set of a congruence problem, J. Number Theory, (to appear).