Sharpening the Bourgain–Garaev–Konyagin–Shparlinski bounds for congruences with products of variables from short intervals: the admissible-range exponent, the subpolynomial factor, and the application thresholds

For a prime $p$, an integer $h\ge3$, a fixed $\nu\ge3$, and a shift $s\in\mathbb{F}_p$, let $K_\nu(p,h,s)$ be the number of solutions of $(x_1+s)\cdots(x_\nu+s)\equiv(y_1+s)\cdots(y_\nu+s)\not\equiv0\pmod p$ with $1\le x_i,y_i\le h$. Bourgain, Garaev, Konyagin and Shparlinski (2013) proved $K_\nu(p,h,s)\le(h^\nu/p^{\nu/e_\nu}+1)\,h^\nu\exp(c(\nu)\log h/\log\log h)$ with $e_\nu=\max\{\nu^2-2\nu-2,\ \nu^2-3\nu+4\}$, together with companion bounds for product sets of shifted intervals, for energies of subsets of intervals, for point counts on exponential curves modulo $p$, and for character sums twisted by the divisor function; more than a decade later these remain the state of the art. This record asks, in the same uniform setting, for any of: (i) improving the admissible-range exponent $e_\nu$ — the authors themselves sketched a refinement for $\nu\ge7$ that has never been carried out; (ii) replacing the subpolynomial factor $\exp(c(\nu)\log h/\log\log h)$ by a constant depending only on $\nu$, or otherwise determining the true order of $K_\nu$; and (iii) extending, or proving optimal, the application thresholds — interval lengths $h\le p^{2/5}$ in the exponential-curve bound, the range $N\ge p^{1/3+\varepsilon}$ in the divisor-twisted character-sum bound, and the exponent $9/20$ in the double character-sum bound for sets contained in short intervals.

Background

Let $p$ be a prime and $\mathbb{F}_p$ the field of residues modulo $p$. A classical theme in analytic and combinatorial number theory is the estimation of the number of solutions of congruences whose variables range over a short interval $\{1,\dots,h\}$ with $h$ much smaller than $p$. For $h$ comparable to $p$, or $h>p^{1/2}$, complete exponential-sum machinery yields asymptotics — Kloosterman sums (the complete exponential sums $\sum_{x\in\mathbb{F}_p^*}e^{2\pi i(ax+b/x)/p}$, where $1/x$ is the multiplicative inverse of $x$ modulo $p$) and the Burgess bound (the standard power-saving estimate for multiplicative character sums over short intervals); for genuinely small $h$ these tools are powerless, and the behavior reflects the interplay between the additive structure of intervals and the multiplicative structure of the congruence — a relative of the sum-product phenomenon of Erdős–Szemerédi and Bourgain (the principle that a finite set of integers cannot simultaneously have few pairwise sums and few pairwise products).

For a shift $s\in\mathbb{F}_p$ and a fixed integer $\nu\ge3$, Bourgain, Garaev, Konyagin and Shparlinski [BGKS 2013] studied the counting function

$$K_\nu(p,h,s)=\#\{(x_1,\dots,x_\nu,y_1,\dots,y_\nu)\in[1,h]^{2\nu}:\ (x_1+s)\cdots(x_\nu+s)\equiv(y_1+s)\cdots(y_\nu+s)\not\equiv0\pmod p\}.$$

For $\nu=2$ this is, up to the shift, the multiplicative energy of an interval (the number of multiplicative collisions among its elements), the object that controls mean values of multiplicative character sums — a multiplicative character is a group homomorphism $\chi:\mathbb{F}_p^*\to\mathbb{C}^*$ extended by $\chi(0)=0$ — ever since Ayyad, Cochrane and Zheng. The case $\nu\ge3$ controls higher moments and the one-sided representation counts $J_\nu(p,h,s;\lambda)$, the number of $x\in[1,h]^\nu$ with $\prod_i(x_i+s)\equiv\lambda\pmod p$, which enter the analysis of the hidden shifted power problem of the same authors [BGKS 2012] (the algorithmic task of recovering a hidden element $s\in\mathbb{F}_p$ from oracle queries that return $(x+s)^e$ for a fixed divisor $e$ of $p-1$). Since the diagonal tuples $x=y$ already give $K_\nu\ge h^\nu$, while a random model predicts about $h^{2\nu}/p$ further collisions, the expected order is $K_\nu\asymp h^\nu+h^{2\nu}/p$; the challenge is to approach this order with explicit estimates uniform in $s$ over a wide range of $h$.

The BGKS method is a novel application of the geometry of numbers to such congruences. To each non-diagonal solution one attaches the integer polynomial $R(Z)=\prod_i(x_i+Z)-\prod_j(y_j+Z)$, of degree at most $\nu-1$ with coefficients bounded by powers of $h$, which vanishes at $s$ modulo $p$. Counting such polynomials reduces, via the successive minima $\lambda_i(D,\Gamma)$ of an auxiliary lattice $\Gamma$ relative to a convex body $D$ (the successive minima are the scaling factors by which $D$ must be dilated to contain $i$ linearly independent lattice vectors; Minkowski's second theorem bounds their product by the volume ratio, and a lattice-point counting lemma of Betke–Henk–Wills type controls lattice points in dilates), to producing one polynomial of very small height, that is, with all coefficients small, vanishing at $s\bmod p$, hence to an exact integer equation; the solutions of that equation are bounded by the classical divisor-function estimate $\tau(n)=\exp(O(\log n/\log\log n))$ for the number $\tau(n)$ of positive divisors of $n$, and an induction on $\nu$ assembles the result. The main theorem (Theorem 19 of the arXiv version) gives, uniformly over $s\in\mathbb{F}_p$,

$$K_\nu(p,h,s)\le\left(\frac{h^\nu}{p^{\nu/e_\nu}}+1\right)h^\nu\exp\!\left(c(\nu)\frac{\log h}{\log\log h}\right),\qquad e_\nu=\max\{\nu^2-2\nu-2,\ \nu^2-3\nu+4\};$$

inside the range $h<p^{1/e_\nu}$ (for example $e_3=4$ and $e_7=33$) this reads $K_\nu\le h^{\nu+o(1)}$, extending the range $h<p^{1/(\nu^2-1)}$ available from the earlier hidden-shifted-power bounds on $J_\nu$. Consequently (Corollary 20 there) the product set $A^{(\nu)}=\{a_1\cdots a_\nu:\ a_i\in A\}$ of the shifted interval $A=\{x+s:1\le x\le h\}$ satisfies $\#A^{(\nu)}>\exp(-c(\nu)\log h/\log\log h)\,h^\nu$ in the same range, and an analogous energy bound holds for arbitrary subsets $X\subseteq[1,h]$ with $h^3/\#X$ at most an absolute constant times $p$ (Lemma 6 there states it for $h^3/\#X<0.002\,p$). The subpolynomial factor $\exp(c(\nu)\log h/\log\log h)=h^{o(1)}$ entering all of these bounds originates in the divisor-function majorization of the auxiliary integer equation, and no uniform polynomial bound for the divisor function exists; whether the specific structure of these equations permits avoiding that loss is open. The authors' remark after the range lemma (arXiv Remark 18) records an unexecuted refinement of this range for $\nu\ge7$: a finer treatment of the successive minima of the auxiliary lattice, in the configuration $\lambda_{\nu-2}\le h^{-1}2^{-\nu}$, $\lambda_{\nu-1}>1$, would slightly improve the restriction on $h$.

The same circle of ideas yields applications. (a) Exponential curves: if $g$ has multiplicative order $t$ modulo $p$, $\gcd(a,p)=1$, and $I_1,I_2$ are intervals of lengths $h_1,h_2$ with $h_2\le t$, then the number $R_{a,g,p}(I_1,I_2)$ of solutions of $x\equiv ag^z\pmod p$, $(x,z)\in I_1\times I_2$, satisfies $R_{a,g,p}(I_1,I_2)<(h_1p^{-2/5}+1)h_2^{1/2+o(1)}$, which for $h_1=h_2=h$ gives $R\ll h^{1/2+o(1)}$ for $h\le p^{2/5}$, extending the previous range $h\le p^{1/3}$ of Cilleruelo–Garaev. (b) Double character sums: for the sum $S_\chi(A,B)=\sum_{a\in A}\sum_{b\in B}\chi(a+b)$, when $A=B$ is contained in an interval of length $\le p^{1/2}$ with $\#A>p^{9/20+\varepsilon}$, one has $S_\chi(A,A)\ll(\#A)^2p^{-\delta}$, improving the threshold $p^{11/24}$ of Friedlander–Iwaniec. (c) Character sums twisted by the divisor function $\tau$: for $S_a(N)=\sum_{n\le N}\tau(n)\chi(a+n)$ one has $S_a(N)\ll Np^{-\delta}$ for $N\ge p^{1/3+\varepsilon}$, uniformly over $\gcd(a,p)=1$ — removing Karatsuba's restriction $|a|\le p^{1/2}$ on this range and improving Chang's exponent $\rho=(7-\sqrt{17})/8\approx0.359$ to $1/3$.

The subsequent literature developed the average-case theory and neighboring axes but left the uniform core untouched: the 2014 companion paper of the same authors proves stronger bounds for almost all primes (uniformly in $s$) and, for fixed $p$, for almost all $s$ — even there the subpolynomial factor persists; Shparlinski (2016) extends to systems of congruences; Cilleruelo–Garaev (2016) and Munsch–Shparlinski (2015) treat sets with small multiplicative doubling and subgroups; Garaev (2018) and Garaev–Pardo–Shparlinski (2025) pursue the solvability/representation axis; Díaz–Garaev–Hernández (2020) extend the $\nu=4$ bound to arbitrary subsets of $[1,h]$ with the same losses; Macourt (2018) applies the exponential-curve bounds to visible points; Shkredov–Shparlinski (2018) improve the different interval-by-arbitrary-set bilinear line; Kerr–Shkredov–Shparlinski–Zaharescu (2025) and Bagshaw–Kerr (2025) transplant the lattice method to modular-root energies and to function fields, the latter recording the analogous range question as a significant open problem; Fouvry–Shparlinski–Xi (2025) still quote the 2013 divisor-sum and double-sum thresholds as the state of the art.

Problem Statement

Let $p$ be a prime, $\nu\ge3$ a fixed integer, $s\in\mathbb{F}_p$, and

$$K_\nu(p,h,s)=\#\{(x_1,\dots,x_\nu,y_1,\dots,y_\nu)\in[1,h]^{2\nu}:\ (x_1+s)\cdots(x_\nu+s)\equiv(y_1+s)\cdots(y_\nu+s)\not\equiv0\pmod p\}.$$

The state of the art, due to Bourgain–Garaev–Konyagin–Shparlinski (2013), is

$$K_\nu(p,h,s)\le\left(\frac{h^\nu}{p^{\nu/e_\nu}}+1\right)h^\nu\exp\!\left(c(\nu)\frac{\log h}{\log\log h}\right),\qquad e_\nu=\max\{\nu^2-2\nu-2,\ \nu^2-3\nu+4\},$$

together with the companion bounds: $\#A^{(\nu)}>\exp(-c(\nu)\log h/\log\log h)\,h^\nu$ for the product set $A^{(\nu)}=\{a_1\cdots a_\nu:\ a_i\in A\}$ of the shifted interval $A=\{x+s:1\le x\le h\}$ with $h<p^{1/e_\nu}$; $L(p,X;s)\le(\#X)^2\exp(C\log h/\log\log h)$ for the number $L(p,X;s)$ of solutions of the same congruence at $\nu=2$ with all four variables in a set $X\subseteq[1,h]$ with $h^3/\#X$ at most an absolute constant times $p$ (the source proves $h^3/\#X<0.002\,p$); $R_{a,g,p}(I_1,I_2)<(h_1p^{-2/5}+1)h_2^{1/2+o(1)}$ for the number of solutions of $x\equiv ag^z\pmod p$ with $(x,z)$ in intervals of lengths $h_1,h_2$ and $h_2\le\mathrm{ord}_p(g)$; and $S_a(N)=\sum_{n\le N}\tau(n)\chi(a+n)\ll Np^{-\delta}$, where $\chi$ is a non-principal multiplicative character modulo $p$ and $\tau$ is the divisor function, for $N\ge p^{1/3+\varepsilon}$, uniformly over $\gcd(a,p)=1$.

The problem is to sharpen these results, in the same uniform setting, on any of the following three interacting components.

(i) Admissible-range exponent. Improve $e_\nu$: prove, for some $\nu\ge3$, a bound $K_\nu(p,h,s)\le(h^\nu/p^{\nu/f(\nu)}+1)h^\nu h^{o(1)}$ uniform over $s\in\mathbb{F}_p$ with $f(\nu)<e_\nu$. The larger goal is the true admissible range: the diagonal gives $K_\nu\ge h^\nu$ always and the expected order is $K_\nu\asymp h^\nu+h^{2\nu}/p$, so $K_\nu\ll_\nu h^\nu$ should plausibly hold well beyond $h<p^{1/e_\nu}$ — at least up to $h\le p^{1/\nu}$, where the collision term begins to dominate — and the gap between $p^{1/e_\nu}$ and the plausible range is large for every $\nu\ge3$ (at $\nu=3$ the admissible exponent denominator is $e_3=4$ against the plausible $3$; at $\nu=7$ it is $e_7=33$ against $7$).

(ii) Subpolynomial factor. Determine whether the factor $\exp(c(\nu)\log h/\log\log h)$ can be replaced by a constant depending only on $\nu$ — in any one of the $K_\nu$ bound, the product-set bound ($\#A^{(\nu)}\gg_\nu h^\nu$), and the subset-energy bound ($L(p,X;s)\ll_\nu(\#X)^2$), within the same ranges — or determine the correct order of these quantities as $h\to\infty$. The factor originates in the divisor-function majorization of the auxiliary integer equation (and its algebraic-number-field analogue), and no uniform polynomial divisor bound exists; the question is whether the specific shifted-product structure of these equations admits sharper counting.

(iii) Application thresholds. Any one of (a), (b), (c) resolved in full answers this component. In (a)–(c), the threshold is called a barrier when its range of validity cannot be enlarged, that is, when an explicit family of parameters shows the corresponding bound failing just outside the stated range. (a) Exponential curves: extend the range $h\le p^{2/5}$ in which $R_{a,g,p}\ll h^{1/2+o(1)}$ for intervals of equal length $h$, or improve the shape of the two-parameter bound, or prove that $p^{2/5}$ is a barrier. (b) Divisor-twisted character sums: lower the threshold $1/3$ in the uniform bound $S_a(N)\ll Np^{-\delta}$ ($N\ge p^{1/3+\varepsilon}$), or prove that $1/3$ is a barrier; note that Fouvry–Shparlinski–Xi (2025) still quote this threshold as the state of the art and prove only a two-variable analogue at threshold $1/4$. (c) Double character sums: lower the threshold exponent $9/20$ in the source's bound $S_\chi(A,A)\ll(\#A)^2p^{-\delta}$, where $S_\chi(A,B)=\sum_{a\in A}\sum_{b\in B}\chi(a+b)$ and $A$ runs over sets contained in an interval of length at most $p^{1/2}$ with $\#A>p^{9/20+\varepsilon}$, or prove that $9/20$ is a barrier for interval-contained sets; the interval-by-arbitrary-set bounds of Shkredov–Shparlinski (2018) are a neighboring axis of the same threshold landscape.

Any answer must preserve the uniformity of the corresponding 2013 statement — in $s\in\mathbb{F}_p$ for the core bounds, and in $a$ (with $\gcd(a,p)=1$) and $g$ for the applications; average-case results (almost all primes, or almost all shifts) do not resolve the question.

References

1. J. Bourgain, M. Z. Garaev, S. V. Konyagin, I. E. Shparlinski, On congruences with products of variables from short intervals and applications, Proceedings of the Steklov Institute of Mathematics 280 (2013), 61–90. DOI: 10.1134/S0081543813010057, https://doi.org/10.1134/S0081543813010057. Preprint arXiv:1203.0017, https://arxiv.org/abs/1203.0017.
2. J. Bourgain, M. Z. Garaev, S. V. Konyagin, I. E. Shparlinski, On the hidden shifted power problem, SIAM Journal on Computing 41 (2012), 1524–1557. DOI: 10.1137/110850414, https://doi.org/10.1137/110850414. Preprint arXiv:1110.0812, https://arxiv.org/abs/1110.0812.
3. J. Bourgain, M. Z. Garaev, S. V. Konyagin, I. E. Shparlinski, Multiplicative congruences with variables from short intervals, Journal d'Analyse Mathématique 124 (2014), 117–147. DOI: 10.1007/s11854-014-0029-2, https://doi.org/10.1007/s11854-014-0029-2. Preprint arXiv:1210.6429, https://arxiv.org/abs/1210.6429.
4. A. Ayyad, T. Cochrane, Z. Zheng, The congruence x1x2 ≡ x3x4 (mod p), the equation x1x2 = x3x4, and mean values of character sums, Journal of Number Theory 59 (1996), 398–413. DOI: 10.1006/jnth.1996.0105, https://doi.org/10.1006/jnth.1996.0105.
5. J. Cilleruelo, M. Z. Garaev, Concentration of points on two and three dimensional modular hyperbolas and applications, Geometric and Functional Analysis 21 (2011), 892–904. DOI: 10.1007/s00039-011-0127-6, https://doi.org/10.1007/s00039-011-0127-6.
6. J. Cilleruelo, M. Z. Garaev, Congruences involving product of intervals and sets with small multiplicative doubling modulo a prime and applications, Mathematical Proceedings of the Cambridge Philosophical Society 160 (2016), 477–494. DOI: 10.1017/S0305004115000808, https://doi.org/10.1017/S0305004115000808.
7. J. B. Friedlander, H. Iwaniec, Estimates for character sums, Proceedings of the American Mathematical Society 119 (1993), 365–372. DOI: 10.1090/S0002-9939-1993-1152276-X, https://doi.org/10.1090/S0002-9939-1993-1152276-X.
8. A. A. Karatsuba, Weighted character sums, Izvestiya: Mathematics 64 (2000), no. 2, 249–263. DOI: 10.1070/im2000v064n02abeh000283, https://doi.org/10.1070/im2000v064n02abeh000283.
9. M.-C. Chang, Character sums in finite fields, in: Finite Fields: Theory and Applications, Contemporary Mathematics 518, American Mathematical Society, Providence, RI, 2010, pp. 83–98. DOI: 10.1090/conm/518/10198, https://doi.org/10.1090/conm/518/10198.
10. I. E. Shparlinski, Systems of congruences with products of variables from short intervals, Bulletin of the Australian Mathematical Society 93 (2016), 364–371. DOI: 10.1017/S0004972715001240, https://doi.org/10.1017/S0004972715001240.
11. M. Munsch, I. E. Shparlinski, Congruences with intervals and subgroups modulo a prime, Michigan Mathematical Journal 64 (2015), no. 3. DOI: 10.1307/mmj/1441116662, https://doi.org/10.1307/mmj/1441116662. Preprint arXiv:1412.0440, https://arxiv.org/abs/1412.0440.
12. M. Z. Garaev, On congruences involving products of variables from short intervals, The Quarterly Journal of Mathematics 69 (2018), 769–778. DOI: 10.1093/qmath/hax061, https://doi.org/10.1093/qmath/hax061. Preprint arXiv:1701.07119, https://arxiv.org/abs/1701.07119 (the preprint version's title reads 'product' rather than 'products').
13. C. A. Díaz, M. Z. Garaev, J. Hernández, Product of subsets of small intervals and points on exponential curves modulo a prime, Acta Arithmetica 193 (2020), 309–319. DOI: 10.4064/aa181127-10-8, https://doi.org/10.4064/aa181127-10-8.
14. S. Macourt, Visible points on exponential curves, Bulletin of the Australian Mathematical Society 97 (2018), 353–359. DOI: 10.1017/S0004972717001186, https://doi.org/10.1017/S0004972717001186. Preprint arXiv:1710.05428, https://arxiv.org/abs/1710.05428.
15. I. D. Shkredov, I. E. Shparlinski, Double character sums with intervals and arbitrary sets in finite fields, Proceedings of the Steklov Institute of Mathematics 303 (2018), 239–258. DOI: 10.1134/S0081543818080199, https://doi.org/10.1134/S0081543818080199. Preprint arXiv:1803.08699, https://arxiv.org/abs/1803.08699.
16. B. Kerr, I. D. Shkredov, I. E. Shparlinski, A. Zaharescu, Energy bounds for modular roots and their applications, Journal of the Institute of Mathematics of Jussieu 24 (2025), no. 5, 1765–1806. DOI: 10.1017/S1474748023000397, https://doi.org/10.1017/S1474748023000397. Preprint arXiv:2103.09405, https://arxiv.org/abs/2103.09405.
17. C. Bagshaw, B. Kerr, Lattices in function fields and applications, Mathematika 71 (2025), no. 2. DOI: 10.1112/mtk.70010, https://doi.org/10.1112/mtk.70010. Preprint arXiv:2304.05009, https://arxiv.org/abs/2304.05009.
18. É. Fouvry, I. E. Shparlinski, P. Xi, Estimates for trilinear and quadrilinear character sums, Revista Matemática Iberoamericana 41 (2025), 1925–1956. DOI: 10.4171/RMI/1530, https://doi.org/10.4171/RMI/1530. Preprint arXiv:2404.09295, https://arxiv.org/abs/2404.09295.
19. M. Z. Garaev, J. C. Pardo, I. E. Shparlinski, Binary and ternary congruences involving intervals and sets modulo a prime, Bulletin of the Australian Mathematical Society 112 (2025), 237–247. DOI: 10.1017/S0004972725000152, https://doi.org/10.1017/S0004972725000152.