Erdős Problem #56
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: number theory, intersecting family.
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
Erdős asked for the largest subset \(A\subseteq\{1,\ldots,N\}\) from which one cannot choose \(k+1\) pairwise coprime integers. The natural candidate is the set of integers divisible by at least one of the first \(k\) primes:
It cannot contain \(k+1\) pairwise coprime integers: every selected number would need a different witness among the first \(k\) primes. Erdős conjectured that this construction is always extremal.
The formulation appears explicitly in Erdős’s 1965 paper, §3, p. 183, and is equivalent to the registered problem after imposing \(N\ge p_k\).
A small example
Take \(t=209\), so \(k=t+3=212\), and list the relevant primes:
Choose
because
Define \(B\) to be the integers at most \(N\) divisible by one of \(p_1,\ldots,p_{208}\), and define
There are
such products, and the upper endpoint ensures they all lie below \(N\).
Set \(A=B\cup C\). This is the competing family.
A pairwise coprime subfamily of \(B\) has size at most \(208\): each member contains a prime among \(p_1,\ldots,p_{208}\), and no such prime can divide two selected members.
Each member of \(C\) is supported on two of the nine primes \(p_{209},\ldots,p_{217}\). Pairwise coprime products must have disjoint supports, so at most
members of \(C\) can be selected pairwise coprimely.
Consequently every pairwise coprime subfamily of \(A\) has size at most
Thus \(A\) satisfies the original forbidden-configuration condition for \(k=212\).
The Erdős set contains \(B\), plus the multiples of \(p_{209},p_{210},p_{211},p_{212}\) that are not already in \(B\).
Within the chosen interval, these additional elements are:
- the four primes;
- their four squares;
- \(8+7+6+5\) admissible products with the later primes.
Hence the non‑\(B\) portion has size
The competitor has \(36\) elements in its corresponding exceptional part. Therefore
So the universal conjecture is false, and in fact
What is known
The 1994 paper of Ahlswede and Khachatrian introduces
as the largest size of a subset of integers avoiding \(k+1\) pairwise coprime members. For \(s=1\), their \(E(n,k,1)\) is exactly the multiples of the first \(k\) primes.
They identify this as Erdős’s conjecture and state it for all \(n,k\in\mathbb N\). Thus the later catalogue condition \(N\ge p_k\) is a nontrivial-domain normalization, not a change to the extremal mechanism.
The direct 1962 Hungarian source is bibliographically identified as Remarks on Number Theory IV: Extremal Problems in Number Theory I, Mat. Lapok 13 (1962), 228–255. The English 1965 exposition is the directly inspected primary statement source.
The 1995 Ahlswede–Khachatrian paper proves a complementary result: for every fixed \(k\), there is a threshold \(n(k)\) such that for all \(N>n(k)\), the Erdős set is uniquely optimal. This does not repair the original universal conjecture; it says that the counterexamples occur only below a \(k\)‑dependent threshold.
The distinction is essential:
while
is proved in the primary 1995 source.
A bounded formalization should first encode the explicit \(k=212\) construction. The key reusable ingredients are the support-packing argument for products of two primes and the finite decomposition of \(E(N,212)\). The protected Lean file records a formal statement and reported proof status, but that metadata is not itself mathematical certification.
GCL's current state
As of 2026-10-12, the maintained catalogue status is DISPROVED. GCL source assignment and evidence (source report pending posting). This is an editorial source audit, not GCL proof certification or mathematical acceptance.
Prerequisites: semantic review against Erdős 1965 §3 and Ahlswede–Khachatrian 1994 §5; comparison with the pinned Lean statement; explicit prime certificates.
No blocker for the source audit. The full text of the original 1962 Hungarian source was not independently transcribed in this run; its provenance is corroborated by Erdős’s 1965 primary exposition and Ahlswede–Khachatrian’s 1994 citation. This does not affect the verified counterexample.
The original issue contains the authenticated RESULT/1 source report. This is source evidence, not independent mathematical certification or editorial admission.
What remains
Input: the formal definitions of weak divisibility, \(E(N,k)\), and pairwise coprimality; the certified prime list above; \(N=1{,}752{,}967\).
Target: formalize the concrete theorem
Method: prove the prime-order and product inequalities; define \(B,C,A\); prove \(A\subseteq[1,N]\), \(|C|=36\), the \(208+4\) packing bound, and the \(34\)‑element decomposition of \(E\setminus B\).
Acceptance test: a kernel-checked proof of the displayed inequality with no imported unverified theorem. Falsification hook: a discovered \(213\)‑element pairwise coprime subfamily of \(A\), or any failure of the \(34\)‑element count.
Stopping rule: stop after the explicit \(k=212\) counterexample is formalized; do not attempt to formalize the full 1995 eventual-optimality theorem in this bounded task.
Sources and claim boundaries
Maintained problem #56; pinned catalogue revision 536408716724a2402bdfa7c1d764bf83d64a8c89.
The original source is Erdős, Extremal Problems in Number Theory, §3, p. 183 (1965), which states the conjecture in terms of the maximum number of integers from which one cannot select \(k+1\) pairwise relatively prime integers and the multiples of the first \(k\) primes: primary PDF.
Ahlswede and Khachatrian, On extremal sets without coprimes, Acta Arith. 66 (1994), 89–99, state the formal conjecture in §1 and prove in Proposition 1 / §5 an explicit counterexample for \(k=212\): primary author PDF, journal record.
For \(t=209\), they use
Since
every \(N\) in
satisfies \(f(N,212)\ge |E(N,212)|+2\).
Ahlswede and Khachatrian, Maximal sets of numbers not containing \(k+1\) pairwise coprime integers, Acta Arith. 72 (1995), 77–100, Theorem 1, prove that for every fixed \(k\) there exists \(n(k)\) such that for every \(N>n(k)\), \(f(N,k)=|E(N,k)|\), uniquely: primary author PDF, journal record.
The pinned catalogue classified the problem as disproved, with last update 2025-11-26. The supplied live page was edited 2026-04-08 and retains the same mathematical status and the \(k=212\) counterexample. The queue issue remains open as an editorial/source-audit task; that is not a mathematical claim.
The protected Lean source is evidence of statement formalization and reported Lean availability, not independently checked certification. Its current quantifiers correspond to \(k>0\) and \(N\ge p_k\), with the universal equality marked false.
Reused evidence: the supplied issue.json, supplied live.html, the pinned catalogue metadata, and the protected formal-source pointer. No sibling returns were inspected.
Primary mathematical verification comes from Erdős 1965 and Ahlswede–Khachatrian 1994/1995. I claim neither formal certification nor independent verification of the complete 1995 proof. The correct status is: the original universal conjecture is disproved, while the fixed‑\(k\), sufficiently-large‑\(N\) version is proved.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1325 — 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.