Congruences with intervals and arbitrary sets

Igor Shparlinski; William Banks

arxiv: 1907.03943 · v1 · pith:ZGZMBK7Onew · submitted 2019-07-09 · 🧮 math.NT

Congruences with intervals and arbitrary sets

William Banks , Igor Shparlinski This is my paper

Pith reviewed 2026-05-25 00:38 UTC · model grok-4.3

classification 🧮 math.NT

keywords congruencesarbitrary setsfinite fieldscharacter sumsKloosterman sumstrilinear sumsnumber theory

0 comments

The pith

The number of solutions to xm ≡ yn mod p is bounded solely in terms of p, H and the cardinality of arbitrary M.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes an upper bound for J(H, M), the number of solutions to xm ≡ yn mod p where x and y range over an interval of length H and m, n are taken from an arbitrary subset M of the multiplicative group modulo a prime p. The bound depends only on p, H and |M| and is shown to be optimal across a wide range of parameters. This uniformity matters because it removes the need for any structural assumptions on M, such as being an interval or having additive properties, that limited many earlier estimates. The resulting bounds are applied to obtain new estimates for trilinear character sums and for bilinear sums that involve Kloosterman sums.

Core claim

J(H, M) admits an upper bound depending only on the prime p, the interval length H, and the cardinality of M, and this bound is optimal for many choices of the parameters.

What carries the argument

J(H, M), the number of solutions to the congruence xm ≡ yn mod p with x, y in [1, H] and m, n in M.

If this is right

The bound yields new estimates for trilinear character sums.
It yields bounds for bilinear sums involving Kloosterman sums.
These estimates complement recent results on similar character sums.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The uniformity over arbitrary sets suggests the same method may apply to other modular equations without requiring additive or multiplicative structure on the sets.
Optimal bounds of this type could tighten error terms in problems that count products or ratios inside finite fields.

Load-bearing premise

The upper bound on J(H, M) remains valid no matter how the arbitrary set M is chosen inside the multiplicative group modulo p.

What would settle it

Explicit values of p, H and M for which the observed count J(H, M) exceeds the derived upper bound by more than a constant factor.

read the original abstract

Given a prime $p$, an integer $H\in[1,p)$, and an arbitrary set $\cal M\subseteq \mathbb F_p^*$, where $\mathbb F_p$ is the finite field with $p$ elements, let $J(H,\cal M)$ denote the number of solutions to the congruence $$ xm\equiv yn\bmod p $$ for which $x,y\in[1,H]$ and $m,n\in\cal M$. In this paper, we bound $J(H,\cal M)$ in terms of $p$, $H$ and the cardinality of $\cal M$. In a wide range of parameters, this bound is optimal. We give two applications of this bound: to new estimates of trilinear character sums and to bilinear sums with Kloosterman sums, complementing some recent results of Kowalski, Michel and Sawin (2018).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Banks and Shparlinski give a uniform bound on J(H,M) that holds for arbitrary M and is optimal in many regimes, with direct applications to character and Kloosterman sums.

read the letter

The key point is that this paper bounds the number of solutions J(H, M) to xm ≡ yn mod p with x, y in [1, H] and m, n in an arbitrary subset M of F_p^*, and the bound depends only on p, H and |M|. They state that the bound is optimal in a wide range of parameters and use it for two applications. What the work does well is remove any structural assumptions on M. Earlier bounds often required M to be an interval or to satisfy some additive condition, but the result here applies uniformly to every possible subset. That flexibility feeds directly into the new estimates for trilinear character sums and bilinear Kloosterman sums, which sit alongside the 2018 Kowalski-Michel-Sawin results without overlapping them. The statement itself is clean and the citation pattern points to the right prior work. The main soft spot is that the abstract does not display the explicit form of the bound or the error terms, so it is hard to judge how tight the constants are or exactly where the optimality holds without the full proof. If the derivation contains no hidden dependence on the choice of M and the lower-bound constructions are explicit, the claim should stand. This paper is for analytic number theorists who need to control solution counts to linear congruences when the set is unstructured. A reader who works with exponential sums over finite fields will find the main theorem and the two applications immediately usable. It deserves a serious referee because the result is stated precisely enough for technical checking and the applications are concrete.

Referee Report

0 major / 2 minor

Summary. The paper defines J(H, M) as the number of solutions to the congruence xm ≡ yn (mod p) with x, y ∈ [1, H] and m, n ∈ M, where M is an arbitrary subset of F_p^*. It establishes an upper bound on J(H, M) depending only on p, H and |M|, and asserts that this bound is optimal for a wide range of parameters. Two applications are given: new estimates for trilinear character sums and for bilinear sums involving Kloosterman sums, complementing results of Kowalski, Michel and Sawin.

Significance. If the claimed uniform upper bound holds for every arbitrary M ⊆ F_p^* and the optimality statement is supported by matching constructions, the result supplies a flexible tool for counting problems over intervals and unstructured sets. The parameter-free nature of the bound (depending solely on p, H and |M|) and the explicit applications to character-sum estimates are concrete strengths that would be useful in analytic number theory.

minor comments (2)

[Abstract] Abstract: the phrase 'in a wide range of parameters' is imprecise; the main theorem statement (likely Theorem 1 or 2) should list the explicit conditions on H and |M| under which optimality holds.
The applications section would benefit from a short comparison table or explicit numerical ranges showing improvement over the Kowalski–Michel–Sawin bounds.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the paper, the assessment of its significance, and the recommendation of minor revision. No major comments appear in the report, so there are no specific points requiring a point-by-point response.

Circularity Check

0 steps flagged

No significant circularity; bound derived uniformly from definition

full rationale

The paper defines the counting function J(H, M) directly from the congruence xm ≡ yn mod p with the stated ranges and arbitrary M ⊆ F_p^*, then derives an upper bound depending only on p, H and |M|. This is a standard derivation of an estimate for a well-defined combinatorial quantity; the bound is stated to hold uniformly for every such M and is claimed optimal in ranges of parameters, without any reduction to fitted inputs, self-referential definitions, or load-bearing self-citations. The applications to character sums are presented as consequences rather than premises. No step in the given abstract or description reduces the claimed result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities beyond the standard definition of the finite field F_p and the counting function J.

axioms (2)

standard math p is a prime number
Used to define the finite field F_p in which the congruence is taken.
domain assumption M is an arbitrary subset of F_p^*
The bound is asserted to hold for every such M.

pith-pipeline@v0.9.0 · 5669 in / 1164 out tokens · 21121 ms · 2026-05-25T00:38:17.412718+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

J(H, M) denote the number of solutions to the congruence xm ≡ yn mod p ... bound J(H, M) in terms of p, H and the cardinality of M
IndisputableMonolith/Foundation/AbsoluteFloorClosure absolute_floor_iff_bare_distinguishability unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

J(H, M) = H²M²/p + O(HM^{3/2} log p) ... stronger conditional estimate ... unconditional variant

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

Ayyad, T

A. Ayyad, T. Cochrane and Z. Zheng, The congruence x1x2 ≡ x3x4 mod p, the equation x1x2 = x3x4 , and mean values of character sums. J. Number Theory 59 (1996), 398–413. 1, 5

work page 1996
[2]

Blomer, ´E

V. Blomer, ´E. Fouvry, E. Kowalski, P. Michel and D. Mili´ cevi´ c, On moments oftwisted L -functions. Amer. J. Math. 139 (2017), 707–768. 4

work page 2017
[3]

Blomer, ´E

V. Blomer, ´E. Fouvry, E. Kowalski, P. Michel and D. Mili´ cevi´ c, Some applicatio ns of smooth bilinear forms with Kloosterman sums. Trudy Matem. Instituta Steklov 296 (2017), 24–35; translation in Transl. as Proc. Steklov Math. Inst. 296 (2017), 18–29. 4

work page 2017
[4]

Bourgain, S

J. Bourgain, S. V. Konyagin and I. E. Shparlinski, Character sum s and deterministic polynomial root ﬁnding in ﬁnite ﬁelds. Math. Comp. 84 (2015), 2969–2977. 3

work page 2015
[5]

Chang, On a question of Davenport and Lewis and new chara cter sum bounds in ﬁnite ﬁelds

M.-C. Chang, On a question of Davenport and Lewis and new chara cter sum bounds in ﬁnite ﬁelds. Duke Math. J. 145 (2008), 409–442. 3

work page 2008
[6]

Fouvry, E

´E. Fouvry, E. Kowalski and P. Michel, Algebraic trace functions ove r the primes. Duke Math. J. 163 (2014), 1683–1736. 4 12 W. D. BANKS AND I. E. SHPARLINSKI

work page 2014
[7]

Fouvry and P

´E. Fouvry and P. Michel Sur certaines sommes d’exponentielles sur le s nombres premiers. Ann. Sci. ´Ecole Norm. Sup. 31 (1998), 93–130. 10

work page 1998
[8]

M. Z. Garaev, On congruences involving product of variables fro m short intervals. Quart. J. Math. , 69 (2018), 769–778. 2

work page 2018
[9]

D. R. Heath-Brown, The density of rational points on curves an d surfaces. Ann. of Math. 155 (2002), 553–595. 6

work page 2002
[10]

D. R. Heath-Brown, The diﬀerences between consecutive smo oth numbers. Acta Arith. 184 (2018), 267–285. 2, 11

work page 2018
[11]

Iwaniec and E

H. Iwaniec and E. Kowalski, Analytic number theory , Amer. Math. Soc., Providence, RI, 2004. 3, 4, 5, 6, 8

work page 2004
[12]

Iwaniec and A

H. Iwaniec and A. S´ ark¨ ozy, On a multiplicative hybrid problem. J. Number Theory 26 (1987), 89–95. 11

work page 1987
[13]

A. A. Karatsuba, The distribution of values of Dirichlet charact ers on additive se- quences. Doklady Acad. Sci. USSR 319 (1991), 543–545. 3

work page 1991
[14]

Kowalski, P

E. Kowalski, P. Michel and W. Sawin, Bilinear forms with Kloosterma n sums and applications. Annals Math. 186 (2017), 413–500. 4, 5

work page 2017
[15]

Kowalski, P

E. Kowalski, P. Michel and W. Sawin, Stratiﬁcation and averaging for exponen- tial sums: Bilinear forms with generalized Kloosterman sums. Preprint, 2018 (see http://arxiv.org/abs/1802.09849). 2, 4, 5, 10, 11

work page arXiv 2018
[16]

Munsch and I

M. Munsch and I. E. Shparlinski, Congruences with intervals and subgroups modulo a prime. Michigan Math. J. 64 (2015), 655–672. 2

work page 2015
[17]

I. D. Shkredov, Modular hyperbolas and bilinear forms of Kloost erman sums. Preprint, 2019 (see http://arxiv.org/abs/1905.0029). 4

work page arXiv 2019
[18]

I. D. Shkredov and I. E. Shparlinski, Double character sums wit h intervals and arbitrary sets in ﬁnite ﬁelds. Proc. Steklov Math. Inst. , 303 (2018), 239–258. 3

work page 2018
[19]

I. E. Shparlinski, Bilinear forms with Kloosterman and Gauss sums . Trans. Amer. Math. Soc., 371 (2019), 8679–8697. 4

work page 2019
[20]

I. E. Shparlinski and T. P. Zhang, Cancellations amongst Kloost erman sums. Acta Arith. 176 (2016), 201–210. 4 Department of Mathematics, University of Missouri, Columb ia, MO 65211 USA E-mail address : bankswd@missouri.edu Department of Pure Mathematics, University of New South W al es, Sydney, NSW 2052 Australia E-mail address : igor.shparlinski@unsw.edu.au

work page 2016

[1] [1]

Ayyad, T

A. Ayyad, T. Cochrane and Z. Zheng, The congruence x1x2 ≡ x3x4 mod p, the equation x1x2 = x3x4 , and mean values of character sums. J. Number Theory 59 (1996), 398–413. 1, 5

work page 1996

[2] [2]

Blomer, ´E

V. Blomer, ´E. Fouvry, E. Kowalski, P. Michel and D. Mili´ cevi´ c, On moments oftwisted L -functions. Amer. J. Math. 139 (2017), 707–768. 4

work page 2017

[3] [3]

Blomer, ´E

V. Blomer, ´E. Fouvry, E. Kowalski, P. Michel and D. Mili´ cevi´ c, Some applicatio ns of smooth bilinear forms with Kloosterman sums. Trudy Matem. Instituta Steklov 296 (2017), 24–35; translation in Transl. as Proc. Steklov Math. Inst. 296 (2017), 18–29. 4

work page 2017

[4] [4]

Bourgain, S

J. Bourgain, S. V. Konyagin and I. E. Shparlinski, Character sum s and deterministic polynomial root ﬁnding in ﬁnite ﬁelds. Math. Comp. 84 (2015), 2969–2977. 3

work page 2015

[5] [5]

Chang, On a question of Davenport and Lewis and new chara cter sum bounds in ﬁnite ﬁelds

M.-C. Chang, On a question of Davenport and Lewis and new chara cter sum bounds in ﬁnite ﬁelds. Duke Math. J. 145 (2008), 409–442. 3

work page 2008

[6] [6]

Fouvry, E

´E. Fouvry, E. Kowalski and P. Michel, Algebraic trace functions ove r the primes. Duke Math. J. 163 (2014), 1683–1736. 4 12 W. D. BANKS AND I. E. SHPARLINSKI

work page 2014

[7] [7]

Fouvry and P

´E. Fouvry and P. Michel Sur certaines sommes d’exponentielles sur le s nombres premiers. Ann. Sci. ´Ecole Norm. Sup. 31 (1998), 93–130. 10

work page 1998

[8] [8]

M. Z. Garaev, On congruences involving product of variables fro m short intervals. Quart. J. Math. , 69 (2018), 769–778. 2

work page 2018

[9] [9]

D. R. Heath-Brown, The density of rational points on curves an d surfaces. Ann. of Math. 155 (2002), 553–595. 6

work page 2002

[10] [10]

D. R. Heath-Brown, The diﬀerences between consecutive smo oth numbers. Acta Arith. 184 (2018), 267–285. 2, 11

work page 2018

[11] [11]

Iwaniec and E

H. Iwaniec and E. Kowalski, Analytic number theory , Amer. Math. Soc., Providence, RI, 2004. 3, 4, 5, 6, 8

work page 2004

[12] [12]

Iwaniec and A

H. Iwaniec and A. S´ ark¨ ozy, On a multiplicative hybrid problem. J. Number Theory 26 (1987), 89–95. 11

work page 1987

[13] [13]

A. A. Karatsuba, The distribution of values of Dirichlet charact ers on additive se- quences. Doklady Acad. Sci. USSR 319 (1991), 543–545. 3

work page 1991

[14] [14]

Kowalski, P

E. Kowalski, P. Michel and W. Sawin, Bilinear forms with Kloosterma n sums and applications. Annals Math. 186 (2017), 413–500. 4, 5

work page 2017

[15] [15]

Kowalski, P

E. Kowalski, P. Michel and W. Sawin, Stratiﬁcation and averaging for exponen- tial sums: Bilinear forms with generalized Kloosterman sums. Preprint, 2018 (see http://arxiv.org/abs/1802.09849). 2, 4, 5, 10, 11

work page arXiv 2018

[16] [16]

Munsch and I

M. Munsch and I. E. Shparlinski, Congruences with intervals and subgroups modulo a prime. Michigan Math. J. 64 (2015), 655–672. 2

work page 2015

[17] [17]

I. D. Shkredov, Modular hyperbolas and bilinear forms of Kloost erman sums. Preprint, 2019 (see http://arxiv.org/abs/1905.0029). 4

work page arXiv 2019

[18] [18]

I. D. Shkredov and I. E. Shparlinski, Double character sums wit h intervals and arbitrary sets in ﬁnite ﬁelds. Proc. Steklov Math. Inst. , 303 (2018), 239–258. 3

work page 2018

[19] [19]

I. E. Shparlinski, Bilinear forms with Kloosterman and Gauss sums . Trans. Amer. Math. Soc., 371 (2019), 8679–8697. 4

work page 2019

[20] [20]

I. E. Shparlinski and T. P. Zhang, Cancellations amongst Kloost erman sums. Acta Arith. 176 (2016), 201–210. 4 Department of Mathematics, University of Missouri, Columb ia, MO 65211 USA E-mail address : bankswd@missouri.edu Department of Pure Mathematics, University of New South W al es, Sydney, NSW 2052 Australia E-mail address : igor.shparlinski@unsw.edu.au

work page 2016