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

arXiv:2607.23004v1 Announce Type: cross Abstract: Let t(N) be the largest t for which there exist distinct sets A_1,ots,A_t subseteq {1,ots,N} such that A_i ap A_j is a nonempty arithmetic progression for all i neq j (Erdos Problem #272). Simonovits and Sos proved t(N)=O(N^2) and conjectured inom{N}{2}+1 is best possible; Szabo disproved this by a construction giving t(N) geq inom{N}{2}+1+lfloor(N-1)/4rfloor, proved the asymptotics t(N)=N^2/2+O(N^{5/3}(log N)^3), and asked whether t(N)=inom{N}{2}+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 leq N leq 12 by exhaustive computation: in this entire range Szabo's lower bound is exact, and we conjecture that t(N)=inom{N}{2}+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.

Source: arXiv cs.AI | 2026-07-28