Erdős Problem #445
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
Fix a prime \(p\) and consider the residues of integers in a short interval \((n,n+L)\). Erdős Problem 445 asks whether this interval always contains two numbers \(a,b\) that are multiplicative inverses modulo \(p\) once its length is just a little larger than \(\sqrt p\). Precisely, for every real \(c>1/2\), does every sufficiently large prime \(p\) have the property that for every integer shift \(n\geq0\) one can find
The modulus is a prime and the interval is open at both endpoints. The quantifier order matters: a threshold on \(p\) may depend on \(c\), but the conclusion must hold for all shifts \(n\), not merely for some conveniently chosen interval. The two numbers need not be distinct in the stated problem, although a distinct-pair example can be used for illustration.
The threshold \(1/2\) is natural because multiplying two sets of about \(\sqrt p\) residues produces about \(p\) ordered pairs, but counting heuristics are not proof that a particular residue is represented in every translated short interval.
A small example
Take \(p=7\), \(n=7\) and \(c=4/5\). Since \(7^{4/5}>4\), the open interval \((7,7+7^{4/5})\) contains the integers \(8,9,10,11\). Choosing \(a=9\) and \(b=11\) yields \(ab=99\equiv1\pmod7\), so this short interval has a valid pair of distinct inverses. Both inequalities can be checked exactly after comparing \(7^{4/5}\) with the integer \(4\).
Another elementary example is \(p=5,c=1,n=1\): the open interval \((1,6)\) contains \(2,3\), and \(2\cdot3=6\equiv1\pmod5\). These are exact finite witnesses. They do not test the hard universal quantifier for every \(n\) at every sufficiently large prime.
The inverse condition can be checked either by multiplying the residues or by computing \(a^{-1}\pmod p\). It is important that \(a\) and \(b\) themselves are integers in the translated interval, rather than unrestricted representatives of their residue classes.
What is known
The question appears in Erdős and Graham's Old and New Problems and Results in Combinatorial Number Theory (1980), printed page 89. Heilbronn established an unpublished partial result for exponents sufficiently close to \(1\). Heath-Brown's Arithmetic applications of Kloosterman sums, published in 2000, improved the range: the desired interval-inverse property holds for every fixed \(c>3/4\) and all sufficiently large primes, uniformly in the starting position \(n\).
The full range \(c>1/2\) remains OPEN on the maintained Erdős Problem #445 page. Kloosterman sums detect cancellation in bilinear modular inverses and can force solutions in intervals that are longer than the conjectured threshold. The existing analytic bounds do not automatically extend to the square-root barrier. In particular, a theorem for \(c>3/4\) cannot be restated as a theorem for \(c>1/2\) by changing notation or relying on numerical evidence.
Related MathOverflow discussion concerns small residue classes and their reciprocals. That community discussion is context, not an unconditional proof of the remaining exponent range.
GCL's current state
The original GCL source issue #1715 pins teorth/erdosproblems to commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml blob 4e60263a80af6207aca494d2e1388e44fa372889. The frozen status is open, consistent with the remaining \(c>1/2\) question. The admitted FormalConjectures 445.lean, Git blob 63cff193fb5f2fa13cb61e4f595721e416eb7aec, separates the open main conjecture from the solved Heath-Brown \(c>3/4\) variant.
The pinned file's principal theorem bodies still contain sorry placeholders, despite a separately proved small arithmetic test in the same file. A passing finite Lean example would not certify the global analytic theorem. The authenticated source audit is https://github.com/grandchallenge/MATH-PROGRAMME/issues/1715#issuecomment-6158631701. Editorial admission and full formal verification remain separate.
What remains
A bounded experiment can fix small primes and rational exponents, enumerate starting positions modulo \(p\), and find the shortest translated interval containing a reciprocal pair. The property repeats modulo \(p\), so examining \(0\leq n<p\) is enough for a fixed prime and integer interval length, although real endpoint conventions still need care. The fixture should include the distinct witness \((9,11)\) for \(p=7\), \(n=7\), \(c=4/5\).
The mathematical source task should map Heath-Brown's theorem into the pinned \(c>3/4\) formal statement, checking all quantifier orders and whether the interval endpoints are strict. Success is exact computational agreement and primary-source fidelity; failure includes allowing integers only congruent to interval members, choosing \(n\) after seeing a witness, or promoting \(c>3/4\) to \(c>1/2\). Stop after the finite and statement check, retaining the main question as open.
Sources and claim boundaries
Historical Erdős–Graham (1980), p.89. Main published partial result: Heath-Brown (2000), Erdős Problem #445. Frozen source issue #1715, teorth catalogue, and pinned FormalConjectures statement. The finite reciprocal examples are exact; the analytic range is externally proved. No new theorem, GCL-certified Lean proof or V2 admission is claimed.
The central unresolved difficulty is uniformity in the translate: an argument that produces one favorable interval for each prime does not satisfy the requirement for every \(n\). Likewise, a finite check of all residue shifts for one small prime, though exact, cannot establish that the prime threshold works for all sufficiently large primes.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1715 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.