Exact values and exact upper bounds for families of integers with arithmetic progression intersections (Erd\H{o}s Problem #272)

Technical Summary: Exact Values and Exact Upper Bounds for Families of Integers with Arithmetic Progression Intersections

Problem Statement
The paper addresses Erdős Problem #272, which seeks to determine the function $t(N)$, defined as the maximum number of distinct subsets $A_1, \dots, A_t \subseteq \{1, \dots, N\}$ such that the intersection of any two distinct sets $A_i \cap A_j$ is a nonempty arithmetic progression (AP).

Historically, Simonovits and Sós established that $t(N) = O(N^2)$ and conjectured that the maximum is achieved by the family of all subsets of size at most 3 containing a fixed element, yielding a bound of $\binom{N}{2} + 1$. Szabó later disproved this exactness conjecture by constructing a family achieving $t(N) \ge \binom{N}{2} + 1 + \lfloor (N-1)/4 \rfloor$. Szabó further established the asymptotic behavior $t(N) = N^2/2 + O(N^{5/3}(\log N)^3)$ and posed two critical questions: (i) whether $t(N) = \binom{N}{2} + O(N)$, and (ii) the "kernel question," asking if every extremal family (one attaining the maximum size) must contain a common element shared by all its sets.

Methodology
The authors employ a hybrid approach combining exhaustive computational verification, structural combinatorics, and analytic bounding techniques:

1. Exact Computation: For small $N$ ($N \le 12$), the problem is modeled as finding the maximum clique in a graph where vertices are nonempty subsets of $[N]$ and edges connect sets with nonempty AP intersections.
   • For $N \le 10$, a bit-parallel branch-and-bound solver with greedy coloring bounds was used.
   • For $N=11$ and $12$, a decision search utilizing root decomposition, degeneracy ordering, core peeling, and a rigorous "star pruning" step was employed to prove the non-existence of larger families.
2. Structural Decomposition: The proof for the general upper bound relies on decomposing a "starred" family (one with a common element $m$) into subsets of size $\le 2$, size $3$, and size $\ge 4$.
3. Defect-One Counting Inequality: A central technical tool is a counting inequality for "staircase regions" (families of integer intervals containing 0). The authors prove that for any such family, the number of members is bounded by the number of "bad pairs" (pairs $\{u,v\}$ such that $\{0,u,v\}$ is not an AP) they cover, plus a small defect term. This is verified via an exact dynamic program for parameters up to 500 and an asymptotic argument using positive-definite quadratic forms for larger parameters.
4. Private-Pair Theorem: A structural theorem is established showing that every "crooked" member (a set of size $\ge 4$ that is not an AP) in a well-intersecting family contains a "private bad pair"—a pair of elements not contained in any other member of the family. This prevents the sharing of "kills" (bad pairs) among non-AP members, allowing for a tight counting bound.

Key Contributions and Results

• Exact Values for Small $N$: The paper determines $t(N)$ exactly for $N = 3, \dots, 12$. The values are $4, 7, 12, 17, 23, 30, 39, 48, 58, 69$. In this entire range, Szabó's lower bound is exact. The sequence does not currently appear in the OEIS.
• Sharpened Conjecture: Based on the computational evidence, the authors conjecture that for all $N \ge 1$:
  $$t(N) = \binom{N}{2} + 1 + \left\lfloor \frac{N-1}{4} \right\rfloor$$
  This refines Szabó's asymptotic question to an exact formula.
• Exact Upper Bound for Starred Families: The main theoretical result (Theorem 1.4) proves that for any starred family (where all sets share a common element), the size is bounded by Szabó's lower bound. This is the first exact upper bound of this kind known for any $N \ge 5$.
  • The proof combines the "defect-one" counting inequality with the "private-pair theorem" to handle non-AP members.
• Reduction to the Kernel Question: The authors demonstrate that the sharpened conjecture (that the formula holds for all $N$) follows immediately if Szabó's kernel conjecture is true (i.e., if every extremal family is starred). Thus, the problem of determining $t(N)$ exactly is reduced to proving that extremal families must have a common element.
• Structural Constraints on Counterexamples: The paper analyzes the hypothetical structure of a non-starred extremal family (a counterexample to the kernel conjecture). It proves that if such a family exists, its triples must share a common element, and any members avoiding this element must be long arithmetic progressions with small differences. The authors argue that such configurations are "self-limiting" and unlikely to reach the conjectured bound, though a full proof remains open.

Significance
The paper claims to provide the first exact determination of $t(N)$ for any $N \ge 5$ (specifically $N \le 12$) and establishes the first exact upper bound for the restricted class of starred families. By proving that the lower bound is exact for all starred families, the work isolates the "kernel property" as the sole remaining obstacle to solving Erdős Problem #272 completely. The authors note that their results confirm Szabó's construction is optimal within the class of families sharing a common element, and they provide the first rigorous structural constraints on what a potential non-starred counterexample would look like. The work also introduces new combinatorial techniques, specifically the defect-one counting inequality and the private-pair theorem, which may be applicable to other intersection problems.