Largest family of subsets of $\{1,\ldots,N\}$ whose pairwise intersections are nonempty APs (Erdős #272)
Statement
Let $N\geq 1$. What is the largest $t$ such that there are distinct sets $A_1,\ldots,A_t\subseteq\{1,\ldots,N\}$ with $A_i\cap A_j$ a non-empty arithmetic progression for all $i\neq j$? (Here sets of size one or two count as arithmetic progressions, as is standard in this problem's literature.)
Acceptance. FULLY RESOLVES: a proof — machine-checkable (Lean/Coq) preferred, else a complete written proof — determining the maximum $t$ exactly (or up to an explicitly bounded additive error $O(1)$) for all sufficiently large $N$, with the extremal families characterised. ADVANCES: an explicit construction giving, for infinitely many $N$ (e.g. via a formula), families strictly larger than Szabó's lower bound stated in the background — delivered as a description plus verification code checking every pairwise intersection is a nonempty AP; a proof strictly improving Szabó's error term $O(N^{5/3}(\log N)^3)$ stated in the background; a proof or disproof of Szabó's conjectures ($t=\binom{N}{2}+O(N)$; common element in every extremal family); or exact values of $t(N)$ for an initial range of $N$ via exhaustive search, with witness families and reproducible code plus an exhaustiveness argument or certificate. Deliver the proof file, or the witness families + verification/search code + certificates.
Background
Posed by Erdős and Graham [ErGr80, p.20]; listed as open on erdosproblems.com/272 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics | arithmetic progressions'). Simonovits and Sós [SiSo81] proved $t\ll N^2$. Erdős and Graham asked whether the maximum is attained by taking all arithmetic progressions in $\{1,\ldots,N\}$ through a fixed element ('presumably the integer $\lfloor N/2\rfloor$'); Simonovits–Sós [SiSo81] disproved this, observing that all sets of size at most $3$ containing a fixed element give $\binom{N}{2}+1$ valid sets, asymptotically more than the $\sim\frac{\pi^2}{24}N^2$ progressions through a fixed element. If the non-emptiness requirement is dropped, Graham, Simonovits, and Sós [GSS80] proved the sharp bound $t\leq\binom{N}{3}+\binom{N}{2}+\binom{N}{1}+1$. For the stated problem, Szabó [Sz99] resolved the leading-order asymptotics: the maximum $t$ equals $$\frac{N^2}{2}+O(N^{5/3}(\log N)^3).$$ Szabó also disproved the Simonovits–Sós conjecture that $\binom{N}{2}+1$ is exactly optimal, constructing families with $t\geq\binom{N}{2}+\lfloor\frac{N-1}{4}\rfloor+1$, and conjectured that $t=\binom{N}{2}+O(N)$ and that every extremal family has an element common to all sets. What remains open is thus the second-order behaviour and the exact extremal structure. A Lean formalisation of the statement exists in google-deepmind/formal-conjectures. The attacker's tool: improved explicit constructions beating Szabó's $\binom{N}{2}+\lfloor(N-1)/4\rfloor+1$ record (a machine-checkable witness for each $N$), and exact computation of $t(N)$ for small $N$ by symmetry-reduced exhaustive/SAT search to test Szabó's structure conjecture; tightening the upper-bound error term is proof-shaped.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #272 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős Problem #272 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.