Estimates on exponential sums related to the Diffie-Hellman distributions (Q2575142): Difference between revisions

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.