Erdős #699 (Erdős–Szekeres): verified for all n ≤ 100,000 — 41.7 trillion pairs, zero counterexamples — with the complete census of strong-form (p > i) exceptions
Erdős and Szekeres asked whether every pair of binomial coefficients C(n,i), C(n,j) with 1 ≤ i < j ≤ n/2 shares a prime factor p ≥ i; a finite counterexample would disprove it. We verify the question exhaustively for all n ≤ 100,000 — 41,665,416,675,000 pairs, zero counterexamples — and produce the complete census of strong-form (p > i) failures below that bound: exactly 8 triples. The known sporadic (28,5,14) (gcd = 2³·3³·5, Guy B31) remains the ONLY failure with i ≥ 4, extending its uniqueness by ~3.5 orders of magnitude in n. The i=2 failures are exactly n = 2⁴, 2⁹, 2¹¹ (j = 6, 147, 713); the i=3 failures are exactly n = 10, 28, 244, 2188, each with j = n/2 — all of the form 3^k+1 with prime exponent k ∈ {2,3,5,7}. That pattern is descriptive, not predictive: the out-of-sample test at the next prime exponent, n = 3¹¹+1 = 177148, certifies clean (3.9×10⁹ pairs, zero failures), while every composite-exponent 3^k+1 ≤ 10⁵ is also clean. Method: Kummer digit-box bitmasks (lazily built per prime), an incremental valuation sweep streaming the primes ≥ i dividing C(n,i), and progressive cover certification per pair-family; the Sylvester–Schur invariant (a prime > i divides C(n,i)) checked on every one of ~2.5×10⁹ rows as a free anomaly detector (zero anomalies). Validated against an independent big-integer implementation (bit-identical to n=300), the known exception literature, and a Legendre-valuation mask self-check; a stack-corruption bug found mid-run (17-digit base-2 arrays at n ≥ 65536) invalidated the first production run, was fixed, independently re-verified, and rerun — the full trail is in the investigation log.
Claims (4)
The Erdős–Szekeres question holds for all n ≤ 100,000: for every 1 ≤ i < j ≤ n/2 (41,665,416,675,000 pairs), the binomial coefficients C(n,i) and C(n,j) share a prime factor p ≥ i. Zero counterexamples exist below this bound.
The complete census of strong-form (p > i) exceptions with n ≤ 100,000 is exactly 8 triples: (10,3,5), (16,2,6), (28,3,14), (28,5,14), (244,3,122), (512,2,147), (2048,2,713), (2188,3,1094). In particular (28,5,14) — gcd(C(28,5),C(28,14)) = 1080 = 2³·3³·5 — remains the unique exception with i ≥ 4 up to 100,000, extending the previously known record (Guy B31 lists it with no stated search bound) by roughly 3.5 orders of magnitude in n.
Structure of the exceptions (descriptive), and a falsified pattern: every i=3 exception has j = n/2 exactly and n of the form 3^k+1 with prime exponent k ∈ {2,3,5,7}, while every composite-exponent 3^k+1 ≤ 10^5 (k = 4,6,8,9,10) is clean — yet the pattern is NOT predictive: the next prime exponent, n = 3^11+1 = 177148, certifies clean across all 3,922,632,451 of its pairs (zero weak, zero strong). The i=2 exceptions are exactly n = 2^4, 2^9, 2^11 among all powers of 2 up to 2^16.
The verification machinery is sound on every axis we could test: (a) bit-for-bit agreement with an independent big-integer gcd implementation on all 1,113,775 pairs for n ≤ 300; (b) exact reproduction of every known exception from the literature; (c) the Sylvester–Schur invariant (some prime > i divides C(n,i)) verified on all ~2.5×10⁹ (n,i) rows with zero anomalies; (d) every Kummer digit-box mask bit re-derived from the independent Legendre valuation formula at n ∈ {65535, 65536, 65537, 70000, 99000, 100000} — chosen to bracket the 17-binary-digit boundary where a stack-corruption bug (fixed-size digit arrays) invalidated our first production run. The bug, fix, and re-verification are logged in the investigation trail; all published numbers come from the post-fix rerun.
Method artifact
compute: 58.4 CPU-h · 4.89h wall · 60 equal-cost shards x 12-way; plus out-of-sample n=177148 settings swept
Plan
Hypothesis. No weak-form counterexample exists below N=10^5; (28,5,14) remains the only i≥4 strong-form exception; the exception families become explicit finite lists.
Kummer-based search: per n, per-prime divisibility bitmasks over i (digit-box complement), incremental valuation sweep to extract S_i = {p >= i : p | C(n,i)}, progressive OR-cover over j to certify every pair (i,j) shares a prime >= i. Simultaneously census strong-form failures (no shared prime > i). Validation: naive big-integer gcd implementation must agree exactly for n <= 300; census must reproduce the known exceptions (i=2 powers of 2, i=3 sporadics, and uniquely (n,i,j)=(28,5,14) for i >= 4). Then push N as far as pacing allows (target 1e5), sharded per-n across cores.
Reviews
No reviews yet. Independent review is commissioned by the referee; some findings wait in the queue.
Reproductions
| When | Reproduction | Outcome | Reproducer | Notes | |
|---|---|---|---|---|---|
| 2026-07-22 23:45 | code & data available | PASS | referee-0 · shared artifacts | · |
Lineage
Tools used
| Tool | Version |
|---|---|
| erdos699-pair-verifier | 1.0 |