Effective exponents in composite-modulus sum-product estimates and explicit bounds for Heilbronn exponential sums

For a finite set $A$ in the residue class ring $\mathbb{Z}_q$ (the integers modulo $q$), the sum-product theorem of Bourgain and Chang (2004) asserts that the sumset $A+A$ and the product set $A\cdot A$ cannot both be of size close to $|A|$ unless $A$ is large relative to $q$ or concentrates in residue classes modulo a divisor of $q$; the associated bounds for exponential sums over multiplicative subgroups of the unit group have the same shape. The 2004 result was restricted to moduli with few large prime factors and produced only unspecified savings $\delta(\varepsilon)>0$. Bourgain (2005-2008) removed the restriction on the modulus, so the structural question is closed; the quantitative questions remain open. This record states the surviving open core: (i) make the exponent functions in the composite-modulus sum-product theorem and subgroup exponential-sum estimates explicit and effective - currently no explicit value is known for any of them; and (ii) prove explicit power-saving bounds for the Heilbronn exponential sums $H_n=\max_{p^n\nmid y}|\sum_{x\in G_n}e_{p^n}(yx)|$, where $G_n$ is the group of $(p-1)$-th roots of unity modulo $p^n$, approaching the conjectured square-root cancellation $H_n\ll_\varepsilon p^{1/2+\varepsilon}$ - the best current bounds are $H_2\ll p^{5/6}\log^{1/6}p$, $H_3\ll p^{1-29/702+o(1)}$, and $H_n\ll p^{1-3.269(34/151)/n+o(1)}$ for $n\ge4$.

Background

Let $e_q(y)=\exp(2\pi i y/q)$ denote the standard additive character on the residue class ring $\mathbb{Z}_q=\mathbb{Z}/q\mathbb{Z}$; for a divisor $q_1$ of $q$, let $\pi_{q_1}$ be the reduction map from $\mathbb{Z}_q$ onto $\mathbb{Z}_{q_1}$, and let $\mathbb{Z}_q^*$ be the group of units (invertible elements) of $\mathbb{Z}_q$.

The sum-product phenomenon is the observation that a finite set of numbers cannot simultaneously have a small sumset $A+A=\{a+a':a,a'\in A\}$ and a small product set $A\cdot A=\{aa':a,a'\in A\}$. Over prime residue rings this was made into a quantitative theorem in the early 2000s, and the 2004 note of Bourgain and Chang extended the theory to composite moduli $q=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ with a bounded total number of prime-power factors, each prime factor $p_i$ larger than $q^{\varepsilon_0}$. Two obstructions are specific to composite moduli: additive subgroups (ideals), such as the kernel of $\pi_p$, have small sumsets and product sets, so a non-degeneracy condition on the projections $\pi_{q_1}(A)$ is unavoidable; and $\mathbb{Z}_q^*$ can contain large multiplicative subgroups with degenerate additive behavior.

Their Theorem 1.1 states that if $A\subset\mathbb{Z}_q$ satisfies $|A+A|+|A\cdot A|<|A|^{1+\varepsilon}$, then either $|A|>q^{1-\delta}$ or $|\pi_p(A)|<Cq^{\delta}$ for some prime divisor $p$ of $q$, where $\delta=\delta(\varepsilon)>0$ tends to $0$ as $\varepsilon\to0$ and is not explicitly determined - equivalently, $|A+A|+|A\cdot A|\ge c|A|^{1+\varepsilon}$ whenever $|A|\le q^{1-\delta}$ and $|\pi_p(A)|\ge Cq^{\delta}$ for every prime divisor $p$ of $q$. The journal version (Geom. Funct. Anal. 2006) proves the companion estimate for exponential sums: if $H$ is a multiplicative subgroup of $\mathbb{Z}_q^*$ with $|\pi_p(H)|>q^{\varepsilon}$ for every prime divisor $p$ of $q$, then $\max_{(a,q)=1}|\sum_{x\in H}e_q(ax)|<C|H|q^{-\delta}$, again with undetermined $\delta=\delta(\varepsilon)$.

A striking consequence concerns Heilbronn's exponential sum, a problem attributed to Davenport in work of Odoni (1985). For a prime $p$ and integer $n\ge1$, let $G_n=\{x\in\mathbb{Z}_{p^n}^*:x^{p-1}=1\}$ be the group of $(p-1)$-th roots of unity modulo $p^n$ (of order $p-1$), and let

$$H_n=\max_{p^n\nmid y}\left|\sum_{x\in G_n}e_{p^n}(yx)\right|=\max_{p^n\nmid y}\left|\sum_{x=1}^{p-1}e_{p^n}\left(yx^{p^{n-1}}\right)\right|.$$

The case $n=2$ is Heilbronn's original sum (up to one negligible summand). The sum has $p-1$ terms of modulus 1, so random-phase heuristics predict $H_n$ of size about $p^{1/2}$ - square-root cancellation - while the trivial bound is $p$. The 2004 note (Corollary 2.4) already gives $H_n\ll p^{1-\varepsilon_n}$ for each fixed $n\ge2$, with $\varepsilon_n>0$ undetermined. The history of explicit bounds: $H_2\ll p^{11/12}$ (Heath-Brown 1996) and $H_2\ll p^{7/8}$ (Heath-Brown and Konyagin 2000), both by Stepanov's method - the classical technique of constructing an auxiliary polynomial that vanishes to high multiplicity at the points of an auxiliary curve and deriving a contradiction unless the exponential sum is small; the first nontrivial bounds for $n\ge3$ are due to Malykhin (2006). The current records are $H_2\ll p^{5/6}\log^{1/6}p$ (Shkredov 2014), $H_3\ll p^{1-29/702+o(1)}$, and $H_n\ll p^{1-3.269(34/151)/n+o(1)}$ for $n\ge4$ (the latter two due to Cochrane-De Silva-Pinner 2017, the $H_3$ bound also obtained independently by Shteinikov 2015). These sums control the distribution of Fermat quotients $q_p(m)=(m^{p-1}-1)/p$ (the quantity measuring how far $m^{p-1}$ is from 1 modulo $p^2$), the Lind-Lehmer constants of the groups $\mathbb{Z}_{p^n}$ (an analogue of Lehmer's problem on how small a nonzero logarithmic Mahler measure - the average of $\log|f|$ over the unit torus - can be for an integer polynomial $f$), and the maximal gaps between $(p-1)$-th roots of unity modulo $p^n$.

Between 2005 and 2008 Bourgain removed the restriction on the modulus: exponential sums over subgroups of $\mathbb{Z}_q^*$ for arbitrary $q$ (J. Anal. Math. 2005), the square-free case of the sum-product theorem (with Gamburd and Sarnak, 2006), a general framework for finite commutative rings (J. Anal. Math. 2007), and the sum-product theorem for arbitrary modulus (2007 announcement; full version J. Anal. Math. 2008): given $\delta_1,\delta_2>0$ there are $\varepsilon,\delta_3>0$ such that every $A\subset\mathbb{Z}_q$ with $|A|<q^{1-\delta_1}$ and $|\pi_{q_1}(A)|>q_1^{\delta_2}$ for all divisors $q_1>q^{\varepsilon}$ of $q$ satisfies $|A+A|+|A\cdot A|>q^{\delta_3}|A|$. All of these results are non-effective: the exponents exist, but no explicit values are produced, because the proofs iterate sum-product estimates along a combinatorial 'tree' decomposition of the divisor lattice of $q$ in which each level loses an unspecified amount. The nearest effective-constant results in this circle of ideas concern a different problem, the equidistribution of orbit averages for dilations of the circle (Bourgain-Lindenstrauss-Michel-Venkatesh 2009).

Problem Statement

Two linked quantitative questions, both implicit in the 2004 note of Bourgain and Chang and neither settled by the subsequent literature.

(1) Effective exponents. In the sum-product theorem for the residue class ring $\mathbb{Z}_q$ in its final form for arbitrary modulus $q$ (Bourgain 2007/2008) - given $\delta_1,\delta_2>0$ there exist $\varepsilon,\delta_3>0$ such that every $A\subset\mathbb{Z}_q$ with $|A|<q^{1-\delta_1}$ and $|\pi_{q_1}(A)|>q_1^{\delta_2}$ for all divisors $q_1>q^{\varepsilon}$ of $q$ satisfies $|A+A|+|A\cdot A|>q^{\delta_3}|A|$ - and in the associated subgroup exponential-sum estimate $\max_{(a,q)=1}|\sum_{x\in H}e_q(ax)|\ll|H|q^{-\delta}$ for multiplicative subgroups $H<\mathbb{Z}_q^*$ with $|\pi_p(H)|>q^{\varepsilon}$ for every prime divisor $p$ of $q$, determine explicit, effectively computable exponents - a function $\delta_3(\delta_1,\delta_2)>0$ together with $\varepsilon(\delta_1,\delta_2)$ for the sum-product theorem, and $\delta(\varepsilon)>0$ for the subgroup estimate - for which such estimates hold. Any explicit, provably positive decay qualifies; no explicit value is currently known for any of these exponents. The exponents for the sum-product statement are asked for the non-vacuous range $\delta_1+\delta_2<1$: because the projection condition is imposed at $q_1=q$, where $\pi_q$ is the identity and $|\pi_q(A)|=|A|$, it says $|A|>q^{\delta_2}$, which is incompatible with $|A|<q^{1-\delta_1}$ once $\delta_1+\delta_2\ge1$; there the hypotheses are empty and the estimate is vacuously true, so no explicit exponent is needed on that range.

(2) Heilbronn exponential sums. For a prime $p$, let $G_n=\{x\in\mathbb{Z}_{p^n}^*:x^{p-1}=1\}$ and

$$H_n=\max_{p^n\nmid y}\left|\sum_{x\in G_n}e_{p^n}(yx)\right|.$$

Obtain explicit power-saving bounds $H_n\ll p^{1-c_n}$ with $c_n$ as large as possible, toward the conjectured square-root cancellation $H_n\ll_\varepsilon p^{1/2+\varepsilon}$. The current best bounds are $H_2\ll p^{5/6}\log^{1/6}p$, $H_3\ll p^{1-29/702+o(1)}$, and $H_n\ll p^{1-3.269(34/151)/n+o(1)}$ for $n\ge4$.

References

1. J. Bourgain, M.-C. Chang, Sum-product theorem and exponential sum estimates in residue classes with modulus involving few prime factors, C. R. Math. Acad. Sci. Paris 339 (2004) 463-466. DOI 10.1016/j.crma.2004.08.007, https://doi.org/10.1016/j.crma.2004.08.007
2. J. Bourgain, M.-C. Chang, Exponential sum estimates over subgroups and almost subgroups of $\mathbb{Z}_Q^*$, where $Q$ is composite with few prime factors, Geom. Funct. Anal. 16 (2006) 327-366. DOI 10.1007/s00039-006-0558-7, https://doi.org/10.1007/s00039-006-0558-7
3. J. Bourgain, Exponential sum estimates over subgroups of $\mathbb{Z}_q^*$, $q$ arbitrary, J. Anal. Math. 97 (2005) 317-355. DOI 10.1007/BF02807410, https://doi.org/10.1007/BF02807410
4. J. Bourgain, A. Gamburd, P. Sarnak, Sieving and expanders, C. R. Math. Acad. Sci. Paris 343 (2006) 155-159. DOI 10.1016/j.crma.2006.05.023, https://doi.org/10.1016/j.crma.2006.05.023
5. J. Bourgain, Exponential sum estimates in finite commutative rings and applications, J. Anal. Math. 101 (2007) 325-355. DOI 10.1007/S11854-007-0012-2, https://doi.org/10.1007/S11854-007-0012-2
6. J. Bourgain, Sum-product theorems and exponential sum bounds in residue classes for general modulus, C. R. Math. Acad. Sci. Paris 344 (2007) 349-352. DOI 10.1016/j.crma.2007.01.019, https://doi.org/10.1016/j.crma.2007.01.019
7. J. Bourgain, The sum-product theorem in $\mathbb{Z}_q$ with $q$ arbitrary, J. Anal. Math. 106 (2008) 1-93. DOI 10.1007/S11854-008-0044-2, https://doi.org/10.1007/S11854-008-0044-2
8. D. R. Heath-Brown, An estimate for Heilbronn's exponential sum, in: Analytic Number Theory (Proc. Conf. in honor of H. Halberstam), Progress in Mathematics 139, Vol. 2, Birkhauser Boston, 1996, pp. 451-463. ISBN 0-8176-3933-0, Zbl 0857.11041, https://zbmath.org/0857.11041
9. D. R. Heath-Brown, S. Konyagin, New bounds for Gauss sums derived from kth powers, and for Heilbronn's exponential sum, Quart. J. Math. 51 (2000) 221-235. DOI 10.1093/qjmath/51.2.221, https://doi.org/10.1093/qjmath/51.2.221
10. R. W. K. Odoni, Trigonometric sums of Heilbronn's type, Math. Proc. Cambridge Philos. Soc. 98 (1985) 389-396. DOI 10.1017/s0305004100063593, https://doi.org/10.1017/S0305004100063593
11. Yu. V. Malykhin, Estimates of trigonometric sums modulo $p^r$, Math. Notes 80 (2006) 748-752. DOI 10.1007/S11006-006-0197-1, https://doi.org/10.1007/S11006-006-0197-1
12. Yu. V. Malykhin, Bounds for exponential sums modulo $p^2$, J. Math. Sci. (New York) 146 (2007) 5686-5696. DOI 10.1007/s10958-007-0385-x, https://doi.org/10.1007/s10958-007-0385-x
13. I. D. Shkredov, On Heilbronn's exponential sum, Quart. J. Math. 64 (2013) 1221-1230. DOI 10.1093/qmath/has037 (arXiv:1208.6124), https://doi.org/10.1093/qmath/has037
14. I. D. Shkredov, On exponential sums over multiplicative subgroups of medium size, Finite Fields Appl. 30 (2014) 72-87. DOI 10.1016/j.ffa.2014.06.002 (arXiv:1311.5726), https://doi.org/10.1016/j.ffa.2014.06.002
15. I. D. Shkredov, E. V. Solodkova, I. V. Vyugin, Intersections of multiplicative subgroups and Heilbronn's exponential sum, preprint arXiv:1302.3839 (2013), https://arxiv.org/abs/1302.3839
16. Yu. N. Shteinikov, Estimates of trigonometric sums over subgroups and some of their applications, Math. Notes 98 (2015) 667-684. DOI 10.1134/S0001434615090333, https://doi.org/10.1134/S0001434615090333
17. T. Cochrane, D. De Silva, C. Pinner, $(p-1)$th roots of unity mod $p^n$, generalized Heilbronn sums, Lind-Lehmer constants, and Fermat quotients, Michigan Math. J. 66 (2017) 203-219. DOI 10.1307/mmj/1488510033, https://doi.org/10.1307/mmj/1488510033
18. I. V. V’yugin, E. V. Solodkova, I. D. Shkredov, On the additive energy of the Heilbronn subgroup, Math. Notes 101 (2017) 58-70. DOI 10.1134/S0001434617010060, https://doi.org/10.1134/S0001434617010060
19. T. Tao, The sum-product phenomenon in arbitrary rings, preprint arXiv:0806.2497 (2008), https://arxiv.org/abs/0806.2497
20. J. Bourgain, E. Lindenstrauss, P. Michel, A. Venkatesh, Some effective results for $\times a\times b$, Ergodic Theory Dynam. Systems 29 (2009) 1705-1722. DOI 10.1017/S0143385708000898, https://doi.org/10.1017/S0143385708000898