Erdős Problem #220
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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
For a positive integer \(n\ge2\), list the integers less than \(n\) that are coprime to \(n\) in increasing order:
Erdős asked whether the squared internal gaps between consecutive such integers satisfy
The implied constant is independent of \(n\). The sum is over the displayed representatives without a cyclic wrap-around gap from \(a_{\varphi(n)}\) to \(n+1\).
A small example
For \(n=10\), the coprime residues below ten are \(1,3,7,9\). The internal gaps are \(2,4,2\), and their squared sum is \(4+16+4=24\). The right-hand scale is \(10^2/\varphi(10)=25\).
For a prime modulus \(n=p\), every integer \(1,\ldots,p-1\) is a reduced residue, and the internal gaps are all one. The left side is then \(p-2\), far below an inappropriate worst-case model with a few huge gaps. There is no need to count a gap past the final reduced residue in the original question.
What is known
PROVED. Hugh Montgomery and Robert Vaughan (1986) established the inequality. They proved the stronger family, for every real \(\gamma\ge1\),
The constant may depend on \(\gamma\) but not \(n\). Taking \(\gamma=2\) recovers the displayed conjecture, while \(\gamma=1\) trivially bounds the sum of internal gaps by \(n\). Higher powers control rare large reduced-residue gaps more severely.
The maintained Erdős #220 identifies the 1986 result and historical Erdős sources back to 1940. The complete analytic argument has not been independently reconstructed here.
GCL's current state
Pinned and maintained status: PROVED. Original issue #1489. The modern provider reports a formal statement, but no GCL kernel certification is claimed. The number of reduced residues, the noncyclic indexing and the parameter-dependent constant are recorded explicitly.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded task enumerates reduced residues for \(2\le n\le500\), computes internal gaps exactly, and checks the ratio of each sum to the predicted scale for \(\gamma=1,2,3\). Acceptance: reproduce the \(n=10\) fixture, handle the empty sum when \(\varphi(n)=1\), and do not infer an absolute analytic constant from finite ratios.
Sources and claim boundaries
- Erdős #220, Montgomery–Vaughan 1986 and original Erdős 1940.
- GCL source issue #1489.
No new reduced-residue inequality, independently verified analytic proof or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1489 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.