Estimates on exponential sums related to the Diffie-Hellman distributions
This important paper investigates the structure of sets in \( \mathbb F_p \) and \( \mathbb F_p \times \mathbb F_p \) with small product set, where ``small is meant in the not too restrictive sense \(| H \cdot H| < | H| ^{1+\tau }\) with a suitably small \(\tau \). While previous works focused mainly on the size of the product set and the sumset, here concentration estimates are given for representations by several summands, which leads to sharp estimates for the size of the iterated sumset \(kH\) and for high moments of the related Fourier series. Let \(\nu ^k(x)\) denote the number of representations of an \(x\in \mathbb F_p\) as a sum of \(k\) elements of \(H\) divided by \(| H| ^k\). Theorem 1 asserts that given a positive integer \(Q\) there is another positive integer \(k\) and a \(\tau >0\) such that for every \(H\subset \mathbb F_p \) satisfying \(| H \cdot H| < | H| ^{1+\tau }\) we have \( \nu ^k(x) <C | H| ^{-Q} + p^{-1+1/Q} \) with \(C\) depending on \(Q\). This implies a bound \( | kH| \gg | H| ^Q\), where under suitable restricions \(Q\) can be made arbitrary large, a bound previously not available by other means as far as the reviewer knows. It also immediately yields a boound for the \(L_k\) norm of the associated Fourier series \( \sum _{x\in H} e^{2\pi iax/p}\). Theorem 3 extends this result to \( \mathbb F_p \times \mathbb F_p \). Here an extra assumption is needed to exclude sets contained in a few cosets of a subring. This is formulated in the form of an a priori estimate \(\nu ^{2Q}(0)< p^{-1-1/Q'}\), and then the conclusion is \(\nu ^k(0)<p^{-2+1/Q}\) for suitably large \(k\) (depending on \(Q,Q'\) and the exponent \(\tau \) in the product condition). Theorem 4 estimates a sum of the type \[ W_{ac} = \sum _{s'=1}^t \left| \sum _{s=1}^t e_p(a\vartheta ^s + c\vartheta ^{ss'}) \right| , \] where \(t\) is the multiplicative order of a \(\vartheta \in \mathbb F_p ^*\). On the assumption that \(t>p^\rho \) with a given \(\rho >0\) the estimate is \( W_{ac} < t^{2-\rho '}\) with \(\rho '\) depending on \(\rho \). With \(\vartheta ,t\) as above, Theorem 6 estimates a sum \( \sum _{n\leq N} \Lambda (n) e_p(a\vartheta ^n)\). Under the assumptions \(t>p^\rho \) and \(N>t^{2+\rho }\) this is bounded by \(Np^{-\sigma }\) with \(\sigma \) depending on \(\rho \). Applications are given to hyperelliptic curves and to estimating the number of solutions of a congruence in 0,1 valued unknowns.
- ESTIMATES FOR THE NUMBER OF SUMS AND PRODUCTS AND FOR EXPONENTIAL SUMS IN FIELDS OF PRIME ORDER
- New bounds on exponential sums related to the Diffie-Hellman distributions
- Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order.
- On an exponential sum related to the Diffie-Hellman cryptosystem
- scientific article; zbMATH DE number 2188811
- The sum-product theorem in Z_q with q arbitrary
- On the exponential sum-product problem
- Improved constructions of quantum automata
- Some consequences of the polynomial Freiman-Ruzsa conjecture
- Exponential sums and prime divisors of sparse integers
- On the digital representation of integers with bounded prime factors
- New bounds on exponential sums related to the Diffie-Hellman distributions
- Mordell type exponential sum estimates in fields of prime order
- The finite Littlewood problem in \(\mathbb{F}_p\)
- On popular sums and differences for sets with small multiplicative doubling
- On the dynamical system generated by the Möbius transformation at prime times
- Sums of algebraic trace functions twisted by arithmetic functions
- Disjointness of the Möbius transformation and Möbius function
- Sparse univariate polynomials with many roots over finite fields
- Product set estimates for non-commutative groups
- Quantum period reconstruction of approximate sequences
- Some remarks on the asymmetric sum-product phenomenon
- On the Odlyzko-Stanley enumeration problem and Waring's problem over finite fields
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- Some new results on higher energies
- ALMOST ALL PRIMES HAVE A MULTIPLE OF SMALL HAMMING WEIGHT
- Local monotonicity and mean value formulas for evolving Riemannian manifolds
- On a variant of sum-product estimates and explicit exponential sum bounds in prime fields
- Bilinear sums with exponential functions
- On the distribution of sparse sequences in prime fields and applications
- On asymptotic formulae in some sum-product questions
- Mordell’s exponential sum estimate revisited
- Littlewood's problem for sets with multidimensional structure
- Estimations on some hybrid exponential sums related to Kloosterman sums
- Prescribing the binary digits of squarefree numbers and quadratic residues
- UNIFORM DISTRIBUTION, EXPONENTIAL SUMS, AND CRYPTOGRAPHY
- Improved Constructions of Quantum Automata
- On the Origins, Nature, and Impact of Bourgain’s Discretized Sum-Product Theorem
- Sum-product theorems and exponential sum bounds in residue classes for general modulus
- Cancellation in a short exponential sum
This page was built for publication: Estimates on exponential sums related to the Diffie-Hellman distributions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2575142)
