For $c>1/2$ and large $p$, does every interval $(n,n+p^c)$ contain $a,b$ with $ab\equiv1\pmod p$? (Erdős #445)
Statement
Is it true that for every $c>1/2$ there is a bound $P$ such that for every prime $p>P$ and every integer $n\ge 0$ there exist $a,b\in(n,\,n+p^{c})$ with $ab\equiv 1\pmod p$? Equivalently: for $c>1/2$ and all sufficiently large $p$, does every interval of length $p^{c}$ contain an integer whose multiplicative inverse modulo $p$ also lies in that same interval?
Acceptance. FULLY RESOLVES: a proof of the statement for every $c>1/2$ (machine-checkable or fully written), OR a disproof — a proof that for some $c>1/2$ there are infinitely many primes $p$, each admitting an interval $(n,n+p^{c})$ containing no reciprocal pair. ADVANCES (each independently checkable): (a) prove the statement for every $c>c_0$ with a constant $c_0$ strictly smaller than the best exponent stated in the background (currently $3/4$, Heath-Brown), with a complete proof; (b) a conditional result under a clearly stated hypothesis (e.g. GRH) that extends the unconditional range, with the hypotheses made explicit. Deliver the proof, together with the exact hypotheses used for any conditional result.
Background
Posed by Erdős–Graham [ErGr80, p.89]. Listed as open on erdosproblems.com/445 (fetched 2026-07-13, status 'open', tagged 'number theory'). Known: Heilbronn (unpublished) proved the statement for $c$ sufficiently close to $1$; Heath-Brown [He00] used Kloosterman-sum estimates to prove it for all $c>3/4$. The conjectured threshold is $c>1/2$, which would be essentially best possible since intervals of length about $p^{1/2}$ are the natural barrier; the range $1/2<c\le 3/4$ remains open. The problem is discussed on MathOverflow ('Small residue classes with small reciprocal'), and a Lean 4 formalisation exists in DeepMind's formal-conjectures repository. The attacker's tool is primarily analytic — bounding incomplete Kloosterman sums (or bringing spectral / additive-combinatorial input to bear) to push the admissible exponent below $3/4$; computationally, one can test for many primes $p$ whether every window of length $p^{c}$ near the $1/2$ barrier contains a reciprocal pair, to probe where the true threshold lies and to hunt for obstructions.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #445 (T. F. Bloom) | website |
| REF-02 | MathOverflow — Small residue classes with small reciprocal | website |
| REF-03 | Lean 4 formalisation of Erdős #445 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.