Skip to content

Erdős Problem #402

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

Take a finite set \(A\) of positive integers. Can one always find two members \(a,b\) of \(A\) for which the common divisor \(gcd(a,b)\) is small compared with \(a\) and the number of available choices? Erdős Problem #402 asks for the precise inequality

\[ \gcd(a,b) \leq \frac{a}{\lvert A\rvert}. \]

The two entries in the pair need not be different, although a diagonal pair is useful only in very small cases. Equivalently, after multiplying by \(lvert A\rvert\) and dividing by the gcd, the question asks whether some ratio \(a/\gcd(a,b)\) is at least the size of the set. The asymmetry matters: the numerator is the first chosen element, so the order of the pair is part of the witness.

The problem arose as a conjecture of R. L. Graham. A related sharper question classifies the sets for which the largest such ratio is exactly \(lvert A\rvert\). This is the source of the reciprocal-set examples and of the exceptional set \({2,3,4,6}\).

A small example

Consider \(A=\{2,3,4,6\}\). It has four elements. The exact pair check over all sixteen ordered pairs gives the unique qualifying witness \((a,b)=(4,3)\):

\[ \gcd(4,3)=1=\frac{4}{4}, \qquad \frac{4}{\gcd(4,3)}=4. \]

This was verified with integer gcds and rational arithmetic, not floating-point rounding: the complete enumeration returned the witness list \([(4,3,1,1,4)]\), where the entries record \(a\), \(b\), \(gcd(a,b)\), \(a/\lvert A\rvert\), and \(a/\gcd(a,b)\). Thus the bound is attained exactly for this ordered pair, and the maximum ratio in the enumeration is \(4\).

The calculation illustrates the theorem's finite meaning and why this set appears in the equality discussion. It does not prove the assertion for arbitrary finite sets, does not establish the equality classification, and does not replace the published argument. It also does not show that a finite computer check has searched beyond this one set.

What is known

The maintained Erdős Problems #402 entry, accessed 2026-10-13, gives the statement above and records: Graham's original conjecture; independent sufficiently-large-set results of Mario Szegedy and Alexandru Zaharescu; and an all-sets result of R. Balasubramanian and K. Soundararajan. The live page says it was last edited 2026-04-08 and has no proof exposition or proof claim. Its bibliography identifies Szegedy, The solution of Graham's greatest common divisor problem, Combinatorica 6 (1986), 67–71, DOI 10.1007/BF02579410, and Zaharescu, On a conjecture of Graham, Journal of Number Theory 27 (1987), 33–40, DOI 10.1016/0022-314X(87)90048-5.

The all-sets primary source is Balasubramanian and Soundararajan, On a conjecture of R. L. Graham, Acta Arithmetica 75 (1996), 1–38, the accessible article PDF, DOI 10.4064/aa-75-1-1-38. On printed page 2, Theorem 1.1 states that for \(N\geq 5\), if \(A=\{a_1,\ldots,a_N\}\) has increasing positive entries and total gcd \(1\), then some \(i,j\) satisfy

\[ \frac{a_i}{\gcd(a_i,a_j)} \geq N. \]

The theorem further says the inequality is strict when both \(A\) and its reciprocal set differ from \({1,\ldots,N}\). The paper notes that \(N\leq4\) is trivial. Dividing an arbitrary positive set by its total gcd preserves all ratios, so this normalized theorem supplies the registered statement for general finite positive sets. The paper's PDF was read from the cited source; its SHA-256 is a76ef9443c21380e1b4fe07170577cb8d6a755870afd18bf95599dc449bf25f7.

GCL's current state

The original MATH-PROGRAMME issue #1672 is the source-audit record for this article. Its frozen catalogue packet is teorth/erdosproblems data/problems.yaml, commit 536408716724a2402bdfa7c1d764bf83d64a8c89, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. Entry 402 says informal status proved, last updated 2025-08-31; formal status unformalized; and statement formalized yes.

The pinned formal statement is FormalConjectures/ErdosProblems/402.lean at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob 266527f17a01546d5091c0b5983aeebd4a2e6138. Its main theorem uses a finite set of naturals, excludes \(0\), assumes nonemptiness, and states the gcd inequality over members of the set. The file also states the equality variant and a Szegedy–Zaharescu asymptotic variant. Every theorem body is by sorry: this is a formal theorem interface, not a checked Lean proof. The source audit therefore supports “externally proved, statement formalized, formal proof unavailable in this file,” not “proved by Lean.” V2 ledger status, rather than this article alone, decides accepted coverage.

What remains

The next useful bounded step is a semantic/formalization audit of the all-sets theorem. Its input should be the exact pinned Lean file, the printed-page-2 theorem, and the finite-set normalization by the common gcd. The target should be a line-by-line proof-obligation map: positivity versus 0 ∉ A, nonemptiness versus \(N\geq5\), ordered-pair quantifiers, rational coercions, and the equality-variant reciprocal construction. Acceptance would require every hypothesis and conclusion to be matched or explicitly weakened/strengthened; falsification would be a concrete counterexample to an asserted equivalence or a missing case in the reduction. The stopping rule is to stop after the statement map and one finite regression suite; no full Lean build or new mathematical proof is implied.

Sources and claim boundaries

This article relies on the live problem page, the frozen catalogue and formal-source hashes above, and the primary 1996 paper. Szegedy and Zaharescu are cited as the live page's primary references; their results were not re-derived here. The finite calculation is an exact check, not a general proof. The sorry declarations are not proof evidence. No GCL mathematical certification, publication decision, award claim, or novelty claim is supplied. The original SOURCE RESULT/1 citation is authenticated original RESULT/1; no future issue comment or link is invented.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1672 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • 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.

Back to catalogue · Compendium introduction