Exact Solution Found for Erdős #272 on Integer Families with Arithmetic Progression Intersections
A new paper on arXiv (2607.23004) presents exact values for t(N), the maximum size of a family of distinct subsets of {1,…,N} where every pairwise intersection is a nonempty arithmetic progression, solving Erdős Problem #272 for small N. The authors determine t(N) exactly for all 3 ≤ N ≤ 12 through exhaustive computation, confirming that Szabó's lower bound is tight in this range. They conjecture that t(N) = C(N,2) + 1 + floor((N-1)/4) for all N. Additionally, they prove that Szabó's bound is the exact maximum for families with a common element (starred families). This work builds on prior results by Simonovits and Sós (who proved t(N)=O(N^2) and conjectured the optimal value), and Szabó (who improved the lower bound and established asymptotics). The kernel question—whether some element lies in all sets of any extremal family—remains open.
Key facts
- Paper on arXiv:2607.23004 addresses Erdős Problem #272.
- t(N) is the largest t for which distinct sets A1,...,At ⊆ {1,…,N} exist with nonempty arithmetic progression intersections.
- Simonovits and Sós proved t(N)=O(N^2) and conjectured C(N,2)+1 is best possible.
- Szabó disproved the conjecture with a construction giving t(N) ≥ C(N,2)+1+floor((N-1)/4).
- Szabó proved asymptotics t(N)=N^2/2+O(N^{5/3}(log N)^3).
- Szabó asked whether t(N)=C(N,2)+O(N) and the kernel question.
- Exact values for N=3 to 12 are determined by exhaustive computation.
- In this range, Szabó's lower bound is exact.
- Authors conjecture t(N)=C(N,2)+1+floor((N-1)/4) for all N.
- Upper bound proved for families with a common element (starred families).
Entities
Institutions
- arXiv