Skip to content

Erdős Problem #272

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: additive combinatorics, arithmetic progressions.

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\), write \([N]=\{1,\ldots,N\}\). We seek the largest size \(t(N)\) of a family of distinct subsets \(A_1,\ldots,A_{t(N)}\) of \([N]\) such that every two different members meet in a nonempty arithmetic progression:

\[ t(N)=\max\left\{t:\ \exists\text{ distinct }A_1,\ldots,A_t\subseteq[N],\ \forall i\ne j,\ A_i\cap A_j\text{ is a nonempty arithmetic progression}\right\}. \]

Here a one- or two-element set counts as an arithmetic progression. A larger one has the form \(\{a,a+d,\ldots,a+(\ell-1)d\}\) with \(d\geq1\). The word “nonempty” is essential: the empty intersection is forbidden, but there is no requirement that all intersections have the same length or common difference. The quantifier \(\forall i\ne j\) ranges over pairs of members, and each pair may have its own progression.

The problem is to determine \(t(N)\), ideally by an exact formula valid for every \(N\). The original Erdős–Graham source, p.20, is less explicit about modern distinct-family conventions; this article uses the normalization stated explicitly in Szabó’s Definition 1 and represented by the pinned formal model. The maintained Erdős entry for #272 records the same question and currently labels it open.

A small example

An exact finite witness can be checked at \(N=7\). Take the common element \(m=4\). Include \(\{4\}\) and all six pairs \(\{4,x\}\) with \(x\in[7]\setminus\{4\}\). Include every three-element set containing \(4\) except

\[ \{2,4,5\}\quad\text{and}\quad\{3,4,6\}, \]

and add the three arithmetic progressions

\[ \{2,3,4,5,6\},\qquad \{2,3,4,5\},\qquad \{3,4,5,6\}. \]

There are \(1+6+(\binom{6}{2}-2)+3=23\) distinct sets. Every member contains \(4\), so intersections are nonempty. Intersections involving a singleton or pair have at most two elements. The only less immediate check is a triple against one of the added progressions. Inside the five-term window, the six triples through \(4\) include four progressions and exactly the two excluded triples above; hence a three-element intersection is also a progression.

The following short exact-integer verifier checks all \(\binom{23}{2}\) intersections and prints the claimed count; it uses no floating-point arithmetic.

from itertools import combinations

N, m = 7, 4
def ap(s):
    s = sorted(s)
    if not s: return False
    if len(s) <= 2: return True
    d = s[1] - s[0]
    return d > 0 and all(s[i] - s[i-1] == d for i in range(2, len(s)))

family = [{m}] + [{m, x} for x in range(1, N+1) if x != m]
blocked = [{2, 4, 5}, {3, 4, 6}]
family += [{m, u, v} for u, v in combinations(
    [x for x in range(1, N+1) if x != m], 2)
    if {m, u, v} not in blocked]
family += [{2,3,4,5,6}, {2,3,4,5}, {3,4,5,6}]
bad = [(a, b) for a, b in combinations(family, 2) if not ap(a & b)]
print(len(family), len(bad))

The reproducible output is 23 0, and the formula below also gives \(\binom{7}{2}+1+\lfloor6/4\rfloor=23\). This is a lower-bound example, not a proof of optimality for \(N=7\) or a solution for all \(N\).

What is known

Graham, Simonovits, and Sós proved in Proposition 4 of their 1980 paper, pp.108–109, that if empty intersections are allowed then the maximum is

\[ \binom{N}{3}+\binom{N}{2}+N+1, \]

with the extremal family consisting of all sets of size at most three. That result is a useful boundary case, not a solution here, because #272 requires every pairwise intersection to be nonempty. Simonovits and Sós, Intersection Properties of Subsets of Integers, Theorem 3 p.365 and Problem 1 pp.371–372, gave an upper-bound framework and left the sharp nonempty case unresolved.

For the nonempty problem, their natural conjecture \(t(N)=\binom{N}{2}+1\) was disproved by Szabó. His explicit construction and Theorem 2.1 give the unconditional bounds

\[ \binom{N}{2}+1+\left\lfloor\frac{N-1}{4}\right\rfloor \leq t(N) =\frac{N^2}{2}+O\!\left(N^{5/3}(\log N)^3\right). \]

The asymptotic statement determines the leading term but not the exact integer value. Yang’s arXiv v1 preprint (submitted 25 July 2026) reports, as Theorem 1.1, \(t(3),\ldots,t(12)=4,7,12,17,23,30,39,48,58,69\). It also proves an exact upper bound matching Szabó’s construction for every starred family, meaning a family whose members all contain one common element (Theorem 1.4). The unrestricted upper bound still depends on the kernel question: must every extremal family be starred?

GCL's current state

The authenticated GitHub identity used for the source audit is fyremael. The original MATH-PROGRAMME issue #1542 is the issue-bound source record; its exact RESULT/1 source-audit comment has disposition PARTIAL. That return confirms the distinct-family normalization, reproduces the \(N=7\) witness, and preserves the unavailable-source exception: the linked Yang computation repository was not accessible through the authenticated GitHub API during the audit, so no external replay, repository CI, or self-reporting computation is claimed here.

The programme fixed registry binds problem 272 to issue 1542 with issue-body SHA-256 341993021372c88a8ae13a06e3078f07d762805d6f366f8a08d0c96e49e59033. The pinned catalogue packet is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, entry blob 4e60263a80af6207aca494d2e1388e44fa372889. It records informal status open, last update 2025-08-31, formal status unformalized, and statement metadata formalized: yes. These are snapshot fields, not mathematical certification. The pinned statement file is google-deepmind/formal-conjectures commit 85f863718beeec7b58a3a1926ee92e3472bc2020, FormalConjectures/ErdosProblems/272.lean, blob fbb4ff8cd1d53580625e41ea384c2fc5aebeb4b2. Its declarations contain sorry; they record a formal interface and related asymptotic targets, not checked proofs or semantic certification. The definition itself has no explicit \(N\geq1\) hypothesis; that restriction appears only in its documentation, so the boundary needs separate semantic review.

Accordingly, the status of the original exact-value problem is open. A narrower historical conjecture is disproved, and substantial asymptotic and finite results are known. Neither the pinned Lean file, an external proof repository, nor a self-reporting CI result upgrades those statements to GCL mathematical certification.

What remains

The central residual question is whether a largest unrestricted family must have a common element. If so, Yang’s starred-family theorem would give the exact formula

\[ t(N)=\binom{N}{2}+1+\left\lfloor\frac{N-1}{4}\right\rfloor. \]

Without that kernel statement, a non-starred family could in principle exceed the bound. The reported values through \(N=12\) are important finite evidence, but they do not settle arbitrary \(N\) and were not independently replayed in this audit. A bounded next step is an independently verifiable exact upper-bound certificate for \(N=13\), where Szabó’s construction has size \(\binom{13}{2}+1+\lfloor12/4\rfloor=82\). Such a certificate would resolve only \(t(13)\), not the infinite problem.

Any formal successor must first reconcile one-based indexing, the exact arithmetic-progression predicate, distinctness, and the \(N\geq1\) boundary. It must compile without sorry and be checked independently; a formalized statement or an external proof artifact alone is insufficient. The unresolved source and semantic exceptions in the PARTIAL return should remain attached to any such work.

Sources and claim boundaries

The cited source-copy hashes retained by the audit are Erdős–Graham 0cbf0c32f0ab1e1c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3; Graham–Simonovits–Sós cf551165c8272296396e378b432ecfdc47f216cc8dc36621247f4f6289779c4f; Simonovits–Sós 8437021246bc7a870450c434abe7becc58ebde65136cd980bd5aad02c90c55f1; Szabó bf837ef30c3538b2b44aea5d335cad9f75959066ccc119f01d89e79490dfdd78; and Yang 36f7c03a83a6b1673d525f9e1c460c2631f19745ff7c75e51367351852747dc7. The protected GCL V2 ledger determines editorial acceptance status; this manuscript makes no mathematical certification or claim upgrade.

Catalogue and evidence provenance

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