# Exact values and exact upper bounds for families of integers with arithmetic progression intersections (ErdHos Problem #272)

arXiv: https://arxiv.org/abs/2607.23004 · HTML: https://mlsanity.com/paper/2607.23004/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 6 references that are in the map.
- First posted on arXiv 25 Jul 2026.

## Abstract (arXiv)

Let t(N) be the largest t for which there exist distinct sets A1,dots,At subseteq 1,dots,N such that Ai cap Aj is a nonempty arithmetic progression for all i neq j (Erdos Problem #272). Simonovits and Sos proved t(N)=O(N2) and conjectured binomN2+1 is best possible; Szabo disproved this by a construction giving t(N) ≥ binomN2+1+lfloor(N-1)/4rfloor, proved the asymptotics t(N)=N2/2+O(N5/3(log N)3), and asked whether t(N)=binomN2+O(N) and whether some element lies in all sets of any extremal family (the kernel question). We determine t(N) exactly for all 3 ≤ N ≤ 12 by exhaustive computation: in this entire range Szabo's lower bound is exact, and we conjecture that t(N)=binomN2+1+lfloor(N-1)/4rfloor for every N. Towards the matching upper bound we prove, for every N, that Szabo's bound is the exact maximum over all families with a common element (starred families). The proof combines a self-contained ``defect-one'' counting inequality for staircase regions with a new structural theorem: every non-progression member of such a family contains a bad pair that no other member can share. Consequently the sharpened conjecture reduces to a single remaining statement, namely Szabo's kernel conjecture that some element lies in all sets of an extremal family, and we prove first structural constraints on putative non-starred extremal families.