Paper deep dive
Exact values and exact upper bounds for families of integers with arithmetic progression intersections (Erdős Problem #272)
Zhanfu Yang
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Let $t(N)$ be the largest $t$ for which there exist distinct sets $A_1,\dots,A_t \subseteq \{1,\dots,N\}$ such that $A_i \cap 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 $\binom{N}{2}+1$ is best possible; Szabo disproved this by a construction giving $t(N) \geq \binom{N}{2}+1+\lfloor(N-1)/4\rfloor$, proved the asymptotics $t(N)=N^2/2+O(N^{5/3}(\log N)^3)$, and asked whether $t(N)=\binom{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)=\binom{N}{2}+1+\lfloor(N-1)/4\rfloor$ 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.
Tags
Links
- Source: https://arxiv.org/abs/2607.23004v1
- Canonical: https://arxiv.org/abs/2607.23004v1
Trouble viewing inline? Open PDF directly →
Full Text
47,235 characters extracted from source content.
Expand or collapse full text
Exact values and exact upper bounds for families of integers with arithmetic progression intersections (Erdős Problem #272) Zhanfu Yang Email: yangzhanfu111@gmail.com. Code for all computations is available at https://github.com/peter-rich/erdos272. See the Acknowledgements for a note on AI assistance. (July 2026) Abstract Let t(N)t(N) be the largest t for which there exist distinct sets A1,…,At⊆1,…,NA_1,…,A_t \1,…,N\ such that Ai∩AjA_i∩ A_j is a nonempty arithmetic progression for all i≠ji≠ j (Erdős Problem #272). Simonovits and Sós proved t(N)=O(N2)t(N)=O(N^2) and conjectured that (N2)+1 N2+1 is best possible; Szabó disproved this by a construction giving t(N)≥(N2)+1+⌊(N−1)/4⌋t(N)≥ N2+1+ (N-1)/4 , proved the asymptotics t(N)=N2/2+O(N5/3(logN)3)t(N)=N^2/2+O(N^5/3( N)^3), and asked whether t(N)=(N2)+O(N)t(N)= N2+O(N) and whether some element lies in all sets of any extremal family (the kernel question). We determine t(N)t(N) exactly for all N≤12N≤ 12 by exhaustive computation: in this entire range Szabó’s lower bound is exact, and we conjecture that t(N)=(N2)+1+⌊(N−1)/4⌋t(N)= N2+1+ (N-1)/4 for every N, a sharpening of Szabó’s conjecture. Towards the matching upper bound we prove, for every N, that Szabó’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 — established in full by an exact dynamic program over all staircase profiles with parameters up to 500500 together with an asymptotic argument based on a positive-definite quadratic form — 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 Szabó’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. We also verify the conjectured value within broader regimes (all starred families for N≤13N≤ 13; a structured class for N≤61N≤ 61) and report the sequence t(3),…,t(12)=4,7,12,17,23,30,39,48,58,69t(3),…,t(12)=4,7,12,17,23,30,39,48,58,69, which does not yet appear in the OEIS. 1 Introduction Throughout, [N]=1,…,N[N]=\1,…,N\, and an arithmetic progression (AP) is any set of the form a,a+d,…,a+(k−1)d\a,a+d,…,a+(k-1)d\ with k≥1k≥ 1; in particular every set of size 11 or 22 is an AP. Define t(N)=maxt:∃distinct A1,…,At⊆[N] with Ai∩Aj a nonempty AP for all i≠j.t(N)\;=\; \t:∃\,distinct A_1,…,A_t [N] with A_i∩ A_j a nonempty AP for all i≠ j \. This is Problem #272 in the Erdős problems database [6]; it originates with Simonovits and Sós [3], and appears in Erdős and Graham [1]. Simonovits and Sós proved t(N)≪N2t(N) N^2 [3]. Erdős and Graham asked whether the maximum is attained by all APs containing a fixed element (“presumably ⌊N/2⌋ N/2 ”), of size ∼π224N2 π^224N^2; Simonovits and Sós observed that all sets of size at most 33 containing a fixed element do better, giving t(N)≥(N2)+1t(N)≥ N2+1, and conjectured this to be best possible [3, 6]. If empty intersections are allowed, Graham, Simonovits and Sós [2] showed the maximum is exactly (N3)+(N2)+(N1)+1 N3+ N2+ N1+1. Simonovits and Sós [3] proved the upper bound t(N)≤(π2/24+1/2+o(1))N2t(N)≤(π^2/24+1/2+o(1))N^2. The deepest results to date are due to Szabó [4]: he identified the leading term, proving the asymptotics t(N)=N22+O(N5/3(logN)3),t(N)= N^22+O (N^5/3( N)^3 ), disproved the Simonovits–Sós exactness conjecture by a construction achieving t(N)≥(N2)+1+⌊N−14⌋,t(N)\ ≥\ N2+1+ N-14 , (1) and raised two precise questions [4, §6], referred to at [6] as Szabó’s conjectures: (i) is t(N)=(N2)+O(N)t(N)= N2+O(N), and (i) the kernel property: does every extremal family have an integer contained in all its sets? He also exhibited several inequivalent families attaining (1), so extremal families are in any case not unique. The exact value of t(N)t(N) has remained open for every N≥5N≥ 5; indeed [4, §6] poses the determination of t(N)t(N) and of the extremal systems as an open problem. Our first result determines the exact values for small N. Theorem 1.1 (Exact values). For N=3,4,…,12N=3,4,…,12, t(N)= 4, 7, 12, 17, 23, 30, 39, 48, 58, 69.t(N)\;=\;4,\ 7,\ 12,\ 17,\ 23,\ 30,\ 39,\ 48,\ 58,\ 69. In particular, Szabó’s lower bound (1) is exact for every 3≤N≤123≤ N≤ 12. The values for 3≤N≤93≤ N≤ 9 have also been reported in the discussion thread of [6]; to our knowledge the values t(10)=48t(10)=48, t(11)=58t(11)=58 and t(12)=69t(12)=69 are new, as is the verification, for N=11,12N=11,12, that no larger family exists over the full unrestricted search space. Theorem 1.1 is computer-assisted: t(N)t(N) is the clique number of the graph on the 2N−12^N-1 nonempty subsets of [N][N] with adjacency A∼BA B iff A∩BA∩ B is a nonempty AP. For N≤10N≤ 10 this was computed by a bit-parallel branch-and-bound solver (cross-validated by an independent implementation); for N=11,12N=11,12 a decision search based on a root decomposition, degeneracy-style ordering, core peeling and a rigorous “star pruning” step (Section 6) proved that no family of size 5959 (resp. 7070) exists, matching the construction below. The sequence does not appear in the OEIS. All ten values equal Szabó’s lower bound (1). In Section 2 we give a short self-contained account of Szabó’s construction achieving (1), with a validity proof of a few lines (we rediscovered it independently before locating the attribution). Theorem 1.2 (Szabó [4]; see Section 2 for a self-contained proof). For all N≥1N≥ 1, t(N)≥(N2)+1+⌊N−14⌋.t(N)\ ≥\ N2+1+ N-14 . Conjecture 1.3 (Sharpening of Szabó’s conjecture). Equality holds in Theorem 1.2 for every N≥1N≥ 1. Conjecture 1.3 implies both parts of Szabó’s conjecture: it gives t(N)=(N2)+O(N)t(N)= N2+O(N) in the strongest form t(N)=N2/2−N/4+O(1)t(N)=N^2/2-N/4+O(1), and our verification below is consistent with the kernel property. In particular the classical family of all ≤3≤ 3-element sets through a fixed point is not optimal for any N≥5N≥ 5 (as Szabó’s construction already shows), and the family of all APs through a fixed point is optimal only for N∈5,9N∈\5,9\, where its count coincides with (1). The extremal families interpolate between the two classical candidates; see Section 2. Our main new theorem is an exact matching upper bound valid for every N over all starred families; to our knowledge no exact upper bound of this kind was previously known for any N≥5N≥ 5. Call a family starred if all its members contain a common element. Theorem 1.4 (Exact upper bound for starred families). Let F be any starred family of distinct subsets of [N][N] with pairwise nonempty AP intersections. Then |F|≤(N2)+1+⌊(N−1)/4⌋|F|≤ N2+1+ (N-1)/4 . In particular, by Theorem 1.2, the maximum size of a starred family equals (N2)+1+⌊(N−1)/4⌋ N2+1+ (N-1)/4 for every N≥1N≥ 1. Theorem 1.4 rests on two ingredients proved here: a self-contained “defect-one” counting inequality for staircase regions (Lemma 3.3), whose proof is partly computer-assisted, via an exact dynamic program covering all parameter profiles up to 500500 and an explicit analytic tail argument beyond; and a structural private-pair theorem (Theorem 5.2) handling non-progression members. Consequently Conjecture 1.3 would follow in full from a single further statement, Szabó’s kernel conjecture that extremal families are starred (Problem 7.1); see Corollary 5.4. For N≤12N≤ 12 no starredness assumption is needed: the extremal value itself is confirmed unconditionally. Remark 1.5. We have consulted [4] directly. The construction of Section 2 coincides with the family C of [4, §5] (we had rediscovered it independently before locating the attribution). No exact values of t(N)t(N) and no exact upper bounds in any regime appear in [4] or, to our knowledge, elsewhere; Theorem 1.1, the sharpened Conjecture 1.3, Theorem 1.4 and the reduction of the conjecture to the kernel question alone appear to be new. Theorem 1.4 may be read as the exact complement of Szabó’s kernel question: it determines the extremal size given a common element, for every N. 2 A construction achieving Szabó’s bound Let m=⌈N/2⌉m= N/2 , so min(m−1,N−m)=⌊(N−1)/2⌋ (m-1,N-m)= (N-1)/2 , and set k=⌊(N−1)/4⌋k= (N-1)/4 ; then m±2d∈[N]m± 2d∈[N] for all 1≤d≤k1≤ d≤ k. Define F to consist of: (i) m\m\ and all pairs m,x\m,x\, x≠mx≠ m (N sets); (i) all 33-sets m,u,v\m,u,v\ except the 2k2k blocked triples Bd=m−2d,m,m+d,Bd′=m−d,m,m+2d(1≤d≤k);B_d=\m-2d,\ m,\ m+d\, B _d=\m-d,\ m,\ m+2d\ (1≤ d≤ k); (i) for each 1≤d≤k1≤ d≤ k, three APs: the five-term window Pd=m−2d,m−d,m,m+d,m+2dP_d=\m-2d,\,m-d,\,m,\,m+d,\,m+2d\ and its two four-term sub-APs containing m, namely Pd∖m+2dP_d \m+2d\ and Pd∖m−2dP_d \m-2d\. The gap pattern d,2d\d,2d\ determines d, so the sets Bd,Bd′B_d,B _d are pairwise distinct, and none of them is an AP; hence |F|=N+[(N−12)−2k]+3k=(N2)+1+k.|F|=N+ [ N-12-2k ]+3k= N2+1+k. Proof of validity. Every member contains m, so all pairwise intersections are nonempty. The intersection of two APs is an AP; the intersection of two distinct 33-sets through m has at most two elements and contains m; and the intersection of a member of size ≤2≤ 2 with anything is a subset of a 22-set. The only case needing care is a triple T of type (i) against an AP P of type (i). If |T∩P|≤2|T∩ P|≤ 2 the intersection is an AP. If |T∩P|=3|T∩ P|=3 then T⊆P⊆PdT P P_d for some d≤kd≤ k. Among the (42)=6 42=6 triples through m inside PdP_d, exactly four are APs, and the two non-APs are precisely BdB_d and Bd′B _d, which are excluded from F. Hence T is an AP and T∩P=T∩ P=T is an AP. ∎ The construction has been machine-verified (full pairwise check) for all N≤40N≤ 40. 3 Reduction of the upper bound Fix m∈[N]m∈[N] and let F be a starred family through m; write λ=m−1λ=m-1, ρ=N−mρ=N-m. Split F=X∪Y∪ZF=X∪ Y∪ Z into members of size ≤2≤ 2, exactly 33, and ≥4≥ 4. Call a pair u,v⊆[N]∖m\u,v\ [N] \m\ bad if m,u,v\m,u,v\ is not an AP, and let kill(Z)kill(Z) be the number of bad pairs contained in at least one member of Z. Proposition 3.1. |F|≤N+(N−12)+(|Z|−kill(Z))|F|\ ≤\ N+ N-12+ (|Z|-kill(Z) ). Proof. Clearly |X|≤N|X|≤ N. If a bad pair u,v\u,v\ lies inside some z∈Zz∈ Z, then T=m,u,vT=\m,u,v\ satisfies T⊆zT z, so T∩z=T∩ z=T would have to be an AP; hence T∉FT∉ F. Thus the triples of Y avoid all killed bad pairs and |Y|≤(N−12)−kill(Z)|Y|≤ N-12-kill(Z). ∎ Passing to relative coordinates x↦x−mx x-m, consider the relation R=(x,y):y∈−x, 2x,x/2R=\(x,y):y∈\-x,\,2x,\,x/2\\ on ℤ∖0Z \0\; a pair is bad iff it is not an R-edge. Lemma 3.2 (Triangle-freeness). R contains no triangle. Consequently every z with |z|≥4|z|≥ 4 contains a bad pair, so a single member has |z|−kill(z)≤0|\z\|-kill(\z\)≤ 0. Proof. Suppose a,b,c∈ℤ∖0a,b,c \0\ are pairwise R-related. If b=−ab=-a then c∈−a,2a,a/2∩a,−2a,−a/2=∅c∈\-a,2a,a/2\∩\a,-2a,-a/2\= . If b=2ab=2a then c∈−a,2a,a/2∩−2a,4a,a=∅c∈\-a,2a,a/2\∩\-2a,4a,a\= . The case b=a/2b=a/2 is symmetric. ∎ Now suppose all members of Z are APs. A member with common difference d is, in relative coordinates, an interval [−l,r]⋅d[-l,r]· d on “line d” containing 0, with l+r≥3l+r≥ 3, ld≤λld≤λ, rd≤ρrd≤ρ. Call a pair a,b\a,b\ of line-d coordinates primitive if gcd(|a|,|b|)=1 (|a|,|b|)=1. A primitive bad pair of line d has gcd exactly d in absolute coordinates, so: the primitive bad pairs of distinct lines are pairwise disjoint families of killed pairs. Moreover, writing εd=1 _d=1 if ⌊λ/d⌋≥2 λ/d ≥ 2 and ⌊ρ/d⌋≥2 ρ/d ≥ 2, and εd=0 _d=0 otherwise, ∑d≥1εd=#d:d≤λ/2,d≤ρ/2=⌊min(λ,ρ)2⌋. _d≥ 1 _d\;=\;\#\d:\ d≤λ/2,\ d≤ρ/2\\;=\; (λ,ρ)2 . (2) Note also that badness is scale-invariant: m,m+ad,m+bd\m,m+ad,m+bd\ is an AP iff b∈−a,2a,a/2b∈\-a,2a,a/2\, so bad pairs in line coordinates correspond exactly to bad pairs in absolute coordinates. Writing SdS_d for the members of Z of difference d and PdP_d for the number of line-primitive bad pairs covered by SdS_d, the displayed disjointness gives ∑dPd≤kill(Z) _dP_d (Z), while |Z|=∑d|Sd||Z|= _d|S_d|. Hence the AP case of the required bound, |Z|−kill(Z)≤∑d(|Sd|−Pd)≤∑dεd=⌊min(λ,ρ)2⌋,|Z|-kill(Z)\ ≤\ _d (|S_d|-P_d )\ ≤\ _d _d\ =\ (λ,ρ)2 , follows, line by line, from the following self-contained statement, applied on line d with Λ=⌊λ/d⌋ = λ/d , P=⌊ρ/d⌋P= ρ/d . Lemma 3.3 (Defect-one counting inequality). Let S be any family of integer intervals [−l,r]∋0[-l,r] 0 with l+r≥3l+r≥ 3, 0≤l≤Λ0≤ l≤ , 0≤r≤P0≤ r , and let P(S)P(S) denote the number of pairs a,b⊆[−Λ,P]∖0\a,b\ [- ,P] \0\ with gcd(|a|,|b|)=1 (|a|,|b|)=1 and b∉−a,2a,a/2b∉\-a,2a,a/2\ that are contained in at least one member of S. Then |S|≤P(S)+ε,ε=1,min(Λ,P)≥2,0,otherwise.|S|\ ≤\ P(S)+ , = cases1,& ( ,P)≥ 2,\\ 0,&otherwise. cases Combining Proposition 3.1, Lemma 3.3, the disjointness of primitive witnesses, and (2) establishes the required bound |Z|−kill(Z)≤⌊min(λ,ρ)/2⌋|Z|-kill(Z)≤ (λ,ρ)/2 when all members of Z are APs. Section 5 removes this restriction, completing the proof of Theorem 1.4. 4 Proof of Lemma 3.3 Since coverage is monotone under taking subsets of members, the extremal S is the full down-set of an antichain; equivalently S is described by a nonincreasing staircase profile L(0)≥L(1)≥⋯≥L(P)≥0L(0)≥ L(1)≥·s≥ L(P)≥ 0 with L(0)≤ΛL(0)≤ , the members being all cells (l,r)(l,r) with 0≤l≤L(r)0≤ l≤ L(r) and l+r≥3l+r≥ 3. The witnesses in Lemma 3.3 need only be covered, not matched into their own members, so the lemma is a pure counting inequality about staircase regions: writing D for the number of demand cells and P for the number of covered primitive bad pairs, we must show D≤P+εD≤ P+ . 4.1 The case min(Λ,P)≤1 ( ,P)≤ 1 Here every member has min(l,r)≤1 (l,r)≤ 1 and we exhibit an explicit injection into primitive bad pairs contained in the corresponding member: (l,1)↦−l,1(l≥2),(l,0)↦−l,−1(l≥3),(1,r)↦−1,r(r≥2),(0,r)↦1,r(r≥3).(l,1) \-l,1\\ (l≥ 2), (l,0) \-l,-1\\ (l≥ 3), (1,r) \-1,r\\ (r≥ 2), (0,r) \1,r\\ (r≥ 3). If P≤1P≤ 1 only the first two rules can apply, and if Λ≤1 ≤ 1 only the last two; if both hold there is no member at all, since l+r≥3l+r≥ 3 then fails. Each image is primitive, bad (e.g. 1,r\1,r\ is bad iff r≠2r≠ 2, which holds as r≥3r≥ 3), contained in its member, and within either applicable pair of rules the images have distinct sign patterns, so the map is injective. Hence |S|≤P(S)|S|≤ P(S) and ε=0 =0 suffices. 4.2 Column decomposition and exact dynamic programming for Λ,P≤500 ,P≤ 500 The supply decomposes by columns. A mixed pair −a,b\-a,b\ (a,b≥1a,b≥ 1, gcd(a,b)=1 (a,b)=1, a≠ba≠ b) is covered iff a≤L(b)a≤ L(b); a right pair b′,b\b ,b\ (1≤b′<b1≤ b <b, gcd=1 =1, b≠2b′b≠ 2b ) is covered iff b≤Pb , and there are exactly φ(b) (b) of them for b≥3b≥ 3 and none for b≤2b≤ 2; a left pair −a,−a′\-a,-a \ (1≤a′<a1≤ a <a, gcd=1 =1, a≠2a′a≠ 2a ) is covered iff a≤L(0)a≤ L(0), since the cell (a,0)(a,0) is then a member, so the left pairs number ∑a=3L(0)φ(a) _a=3^L(0) (a). Consequently D−PD-P is, up to the left-pair term determined by L(0)L(0), a sum of per-column scores depending only on (r,L(r))(r,L(r)), and maxstaircases(D−P) _staircases\,(D-P) is computable exactly by a dynamic program over the profile, with suffix maxima giving an O(ΛP)O( ) algorithm. Running this program over all staircase profiles with Λ,P≤500 ,P≤ 500 gives max(D−P)= 1, (D-P)\;=\;1, attained, e.g., at the (2,2)(2,2) window, i.e. the configuration of the construction in Section 2. We emphasize why a single run certifies every window with Λ,P≤500 ,P≤ 500: the program computes the left-pair supply from the profile’s attained maximum L(0)L(0) rather than from the grid bound Λ (no such correction is needed on the right, where the supply is Φ(P)−2 (P)-2 unconditionally, since (0,b)(0,b) is a member for every 3≤b≤P3≤ b ), so each profile is scored exactly as an instance of its own attained window; profiles with L(0)<ΛL(0)< are therefore handled correctly, and the reported maximum is the true maximum over all instances with parameters up to 500500. (This covers, exactly, a class of roughly (1000500) 1000500 down-set families.) 4.3 The tail max(Λ,P)>500 ( ,P)>500 We first reduce to the case in which the left parameter is attained. On the right no reduction is needed: for every 3≤b≤P3≤ b the cell (0,b)(0,b) satisfies l+r=b≥3l+r=b≥ 3 and is therefore a member, so all Φ(P)−2 (P)-2 right pairs are covered unconditionally. On the left, given any family S put Λ′=L(0)≤Λ =L(0)≤ ; then S is an instance of the (Λ′,P)( ,P)-problem with the same D and P, and ε(Λ′,P)≤ε(Λ,P) ( ,P)≤ ( ,P) since ε is monotone in Λ . If max(Λ′,P)≤500 ( ,P)≤ 500 the claim follows from §4.2, and if min(Λ′,P)≤1 ( ,P)≤ 1 from §4.1; so we may, and do, assume that Λ=L(0) =L(0) — the supply term Φ(Λ)−2 ( )-2 below relies on this attainment — and that min(Λ,P)≥2 ( ,P)≥ 2. Write Φ(x)=∑n≤xφ(n) (x)= _n≤ x (n) and C(l,r)=#1≤a≤l:gcd(a,r)=1,a≠rC(l,r)=\#\1≤ a≤ l: (a,r)=1,\ a≠ r\. We use four elementary estimates, valid for all arguments ≥1≥ 1: (E1) C(l,r)≥lφ(r)/r−2ω(r)−1C(l,r)\ ≥\ l\, (r)/r-2^ω(r)-1. Proof: #a≤l:gcd(a,r)=1=∑d∣rad(r)μ(d)⌊l/d⌋\#\a≤ l: (a,r)=1\= _d (r)μ(d) l/d and |⌊l/d⌋−l/d|<1| l/d -l/d|<1, with 2ω(r)2^ω(r) squarefree divisors; subtract 11 for the possible exclusion a=ra=r. (E2) ∑r≤Pφ(r)/r≥(6/π2)P−lnP−2 _r (r)/r\ ≥\ (6/π^2)P- -2. Proof: ∑r≤Pφ(r)/r=∑d≤Pμ(d)d⌊P/d⌋≥P∑d≤Pμ(d)/d2−∑d≤P1/d _r (r)/r= _d μ(d)d /d _d μ(d)/d^2- _d 1/d, and ∑d≤Pμ(d)/d2≥6/π2−1/P _d μ(d)/d^2≥ 6/π^2-1/P. (E3) ∑r≤P2ω(r)≤P(lnP+1) _r 2^ω(r)\ ≤\ P( +1), since 2ω(r)≤d(r)2^ω(r)≤ d(r) and ∑r≤Pd(r)=∑d≤P⌊P/d⌋ _r d(r)= _d /d . (E4) Φ(x)≥(3/π2)x2−12xlnx−2x (x)\ ≥\ (3/π^2)x^2- 12x x-2x. Proof: Φ(x)=12∑d≤xμ(d)⌊x/d⌋(⌊x/d⌋+1) (x)= 12 _d≤ xμ(d) x/d ( x/d +1) and (t−1)t≤⌊t⌋(⌊t⌋+1)≤t(t+1)(t-1)t≤ t ( t +1)≤ t(t+1) give μ(d)⌊t⌋(⌊t⌋+1)≥μ(d)t2−tμ(d) t ( t +1)≥μ(d)t^2-t for t=x/dt=x/d; sum and use ∑d≤xμ(d)/d2≥6/π2−1/x _d≤ xμ(d)/d^2≥ 6/π^2-1/x. Bounding the demand by D≤(Λ+1)+∑r=1P(L(r)+1)D≤( +1)+ _r=1^P(L(r)+1) and the supply from below by the three pair types (mixed: ∑rC(L(r),r) _rC(L(r),r); right: Φ(P)−2 (P)-2; left: Φ(Λ)−2 ( )-2), we obtain D−P≤(Λ+1)+∑r=1P[L(r)+1−C(L(r),r)]−Φ(P)−Φ(Λ)+4.D-P\ ≤\ ( +1)+ _r=1^P [L(r)+1-C(L(r),r) ]- (P)- ( )+4. By (E1), and since L(r)≤ΛL(r)≤ and 1−φ(r)/r≥01- (r)/r≥ 0, each column satisfies L(r)+1−C(L(r),r)≤Λ(1−φ(r)/r)+2ω(r)+2L(r)+1-C(L(r),r)≤ (1- (r)/r)+2^ω(r)+2; summing over r≤Pr and inserting (E2)–(E4) gives D−P≤G(Λ,P):=−q(Λ,P)+ΛlnP+32PlnP+12ΛlnΛ+5(Λ+P)+6,D-P\ ≤\ G( ,P)\ :=\ -q( ,P)+ + 32\,P + 12\, +5( +P)+6, (3) where q(Λ,P)=(3/π2)(Λ2+P2)−(1−6/π2)ΛPq( ,P)=(3/π^2)( ^2+P^2)-(1-6/π^2) . Since ΛP≤(Λ2+P2)/2 ≤( ^2+P^2)/2, q≥(6π2−12)(Λ2+P2)≥ 0.107(Λ2+P2)≥ 0.107M2,M:=max(Λ,P),q\ ≥\ ( 6π^2- 12 )( ^2+P^2)\ ≥\ 0.107\,( ^2+P^2)\ ≥\ 0.107\,M^2, M:= ( ,P), while the remaining terms of (3) are at most 3MlnM+10M+63M M+10M+6. The single-variable function f(M)=−0.107M2+3MlnM+10M+6f(M)=-0.107M^2+3M M+10M+6 satisfies f′(M)=−0.214M+3lnM+13<0f (M)=-0.214M+3 M+13<0 for M≥135M≥ 135 (indeed f′(135)<−1f (135)<-1), and f(250)<−40f(250)<-40; hence f(M)<0f(M)<0 for all M≥250M≥ 250. Hence D−P≤G<0≤εD-P≤ G<0≤ whenever max(Λ,P)≥250 ( ,P)≥ 250, and the range max(Λ,P)≤500 ( ,P)≤ 500 is covered exactly by §4.2. This completes the proof of Lemma 3.3. ∎ All four estimates (E1)–(E4), and the assembled bound (3), were additionally verified numerically over large finite ranges as a safeguard. 5 Crooked members: completion of the proof of Theorem 1.4 Throughout this section a member is a set z∋0z 0 with |z|≥4|z|≥ 4, z⊆[−λ,ρ]z [-λ,ρ], and Z is a family of distinct members with pairwise intersections APs (each intersection contains 0, hence is an AP through 0). Call z crooked if it is not an arithmetic progression. Recall that a pair u,v⊆z∖0\u,v\ z \0\ is bad if 0,u,v\0,u,v\ is not an AP. Lemma 5.1 (Spanning lemma). Suppose distinct members z,z′z,z both contain a bad pair u,v\u,v\. Then z∩z′z∩ z is an AP through 0 whose difference δ divides gcd(|u|,|v|) (|u|,|v|), and both z and z′z contain every multiple of δ in [min(0,u,v),max(0,u,v)][ (0,u,v), (0,u,v)]. Proof. z∩z′z∩ z is an AP containing 0,u,v0,u,v; its difference δ divides u and v, and an AP containing 0,u,v0,u,v contains every multiple of δ between its least and greatest elements. Both members contain z∩z′z∩ z . ∎ Accordingly, say a bad pair u,v⊆z\u,v\ z is spanned in z if there exists δ∣gcd(|u|,|v|)δ (|u|,|v|) such that z contains every multiple of δ in [min(0,u,v),max(0,u,v)][ (0,u,v), (0,u,v)]; otherwise the pair is private to z. By Lemma 5.1, a pair private to z is contained in no other member of Z. Theorem 5.2 (Private-pair theorem). Every crooked member contains a private bad pair. Proof. Since |z∖0|≥3|z \0\|≥ 3 and the relation R is triangle-free (Lemma 3.2), z contains a bad pair. Assume for contradiction that every bad pair of z is spanned in z; we show z is an AP. Let δ0 _0 be the least positive integer that spans some bad pair of z, say p0=δ0a,δ0bp_0=\ _0a, _0b\ with gcd -condition δ0∣gcd _0 , and let P0⊆zP_0 z be the corresponding progression: all multiples of δ0 _0 in I0=[min(0,δ0a,δ0b),max(0,δ0a,δ0b)]I_0=[ (0, _0a, _0b), (0, _0a, _0b)]. Since a,b\a,b\ is not an R-pair we cannot have |a|=|b|=1|a|=|b|=1, so max(|a|,|b|)≥2 (|a|,|b|)≥ 2; hence P0P_0 contains 2tδ02t _0 for some sign t∈+,−t∈\+,-\, and P0P_0 contains sδ0s _0 for some sign s. Step 1: z⊆δ0ℤz _0Z. Let w∈zw∈ z with δ0∤w _0 w. The R-partners of sδ0s _0 are −sδ0-s _0, 2sδ02s _0 and sδ0/2s _0/2; the first two are multiples of δ0 _0. If w≠sδ0/2w≠ s _0/2, the pair sδ0,w\s _0,w\ is therefore bad, and g:=gcd(δ0,|w|)g:= ( _0,|w|) is a proper divisor of δ0 _0; by assumption this pair is spanned at some δ∣g<δ0δ g< _0, contradicting the minimality of δ0 _0. If w=sδ0/2w=s _0/2, consider instead the pair sδ0/2, 2tδ0\s _0/2,\,2t _0\: the R-partners of sδ0/2s _0/2 are −sδ0/2-s _0/2, sδ0s _0 and sδ0/4s _0/4, none of which equals ±2δ0± 2 _0, so the pair is bad, with gcd equal to δ0/2<δ0 _0/2< _0 — the same contradiction. Hence z⊆δ0ℤz _0Z. Step 2: z is an AP. Badness, R-edges and spanning are invariant under x↦x/δ0x x/ _0 on δ0ℤ _0Z, so we may assume δ0=1 _0=1; then P0P_0 is an integer interval around 0 of length at least 33, so 1∈z1∈ z or −1∈z-1∈ z. Suppose first 1∈z1∈ z. For w∈zw∈ z with w≥3w≥ 3: the pair 1,w\1,w\ is bad (w∉−1,2,12w∉\-1,2, 12\) with gcd equal to 11, so its only possible spanning step is δ=1δ=1, forcing [0,w]∩ℤ⊆z[0,w] z. For w∈zw∈ z with w≤−2w≤-2: likewise 1,w\1,w\ is bad and [w,1]∩ℤ⊆z[w,1] z. The remaining elements w∈−1,2w∈\-1,2\ impose nothing, but [−1,0][-1,0] and [0,2][0,2] lie in z automatically whenever those elements are present. Hence z=[minz,maxz]∩ℤz=[ z, z] , an AP. If instead only −1∈z-1∈ z: for any w∈zw∈ z with w≥2w≥ 2 the pair −1,w\-1,w\ is bad (w∉1,−2,−12w∉\1,-2,- 12\) with gcd equal to 11, forcing [−1,w]∩ℤ⊆z[-1,w] z and in particular 1∈z1∈ z, returning us to the previous case; if maxz≤1 z≤ 1 then either 1∈z1∈ z (previous case) or maxz=0 z=0, and the mirror argument with pairs −1,w\-1,w\, w≤−3w≤-3, gives z=[minz,0]∩ℤz=[ z,0] . In every case z is an AP, contradicting crookedness. ∎ We verified Theorem 5.2 by brute force over all crooked members contained in the windows [−6,6][-6,6], [−4,8][-4,8], [−3,9][-3,9], [−2,10][-2,10] and [−7,7][-7,7] (about 26,00026,000 members): none lacks a private bad pair. Theorem 5.3 (The crooked-member bound). For every family Z as above, |Z|−kill(Z)≤⌊min(λ,ρ)/2⌋|Z|-kill(Z)≤ (λ,ρ)/2 . Proof. Split Z into the AP members, grouped by difference d into families SdS_d, and the crooked members C. By Lemma 3.3 applied on line d (Section 3), |Sd|≤Pd+εd|S_d|≤ P_d+ _d, where PdP_d counts the line-d-primitive bad pairs covered by SdS_d; these pairs are killed, and the pools for distinct d are disjoint. By Theorem 5.2 each z∈Cz∈ C contains a private bad pair w(z)w(z); by Lemma 5.1 the pair w(z)w(z) lies in no other member of Z — in particular the pairs w(z)w(z) are pairwise distinct, and none of them is covered by any AP member, so they are disjoint from all the pools above. Hence kill(Z)≥∑dPd+|C|,while|Z|=∑d|Sd|+|C|≤∑dPd+∑dεd+|C|,kill(Z)\ ≥\ _dP_d+|C|, |Z|= _d|S_d|+|C|\ ≤\ _dP_d+ _d _d+|C|, and ∑dεd=⌊min(λ,ρ)/2⌋ _d _d= (λ,ρ)/2 by (2). ∎ Proof of Theorem 1.4. Let F be starred through m. By Proposition 3.1 and Theorem 5.3, |F|≤N+(N−12)+⌊min(m−1,N−m)/2⌋|F|≤ N+ N-12+ (m-1,N-m)/2 , and the maximum of the last term over m is ⌊(N−1)/4⌋ (N-1)/4 . ∎ Corollary 5.4. Szabó’s kernel conjecture implies Conjecture 1.3: if for every N some maximum family is starred, then t(N)=(N2)+1+⌊(N−1)/4⌋t(N)= N2+1+ (N-1)/4 for all N. 6 Computations Exact values (Theorem 1.1). For N≤10N≤ 10, exact maximum clique on the (2N−1)(2^N-1)-vertex graph via bit-parallel branch and bound with greedy-colouring bounds; independently cross-checked for N≤6N≤ 6; every extremal family re-verified pair by pair. For N=11,12N=11,12 we ran a decision search for a clique of size 5959 (resp. 7070): any clique has a minimum vertex in a fixed order, giving independent subproblems; we use ascending-degree order, iterated core peeling (a (T+1)(T+1)-clique needs internal degree ≥T≥ T), and, for N=12N=12, the following rigorous star pruning. First, exhaustive search over each possible common element m (with reflection symmetry) established that every starred family in [12][12] has size at most 6969. Consequently, during the search for a 7070-clique, any branch in which the bitwise AND of the current members and all remaining candidates is nonzero can be pruned, because every completion of that branch is starred. The searches terminated with no clique of size 5959 (resp. 7070), so t(11)=58t(11)=58 and t(12)=69t(12)=69 unconditionally. Starred and structured regimes. Exhaustive starred computations give the conjectured value for N≤13N≤ 13 for every choice of the common element. Within the “ansatz” class (members through m that are APs or non-AP triples), exact optimization by clique search (N≤25N≤ 25) and integer programming (N≤61N≤ 61, all central m, plus non-central spot checks) always returns (N2)+1+⌊(N−1)/4⌋ N2+1+ (N-1)/4 , and in every tested case the line-selection optimum equals ⌊min(m−1,N−m)/2⌋ (m-1,N-m)/2 . Tests of Theorem 5.3. As an independent check, the crooked-member bound was verified exactly by integer programming on the windows (λ,ρ)∈(2,4),(2,5),(3,3),(3,4),(4,4)(λ,ρ)∈\(2,4),(2,5),(3,3),(3,4),(4,4)\, in each case with maximum exactly ⌊min(λ,ρ)/2⌋ (λ,ρ)/2 ; and Theorem 5.2 was verified by brute force over roughly 26,00026,000 crooked members as reported in Section 5. All code (C solvers, the dynamic program of §4.2, ILP models, verification scripts) is available at https://github.com/peter-rich/erdos272; the dynamic program documents in source how the left- and right-pair supply is computed from attained profile maxima. 7 Open problems By Corollary 5.4, Conjecture 1.3 now rests on a single statement. Problem 7.1 (Szabó’s kernel conjecture [4, 6]). Show that for every N, some (equivalently, by our computations for N≤12N≤ 12, every maximum) extremal family has a common element. A model may be the uniqueness analysis of Graham, Simonovits and Sós [2] in the empty-intersection-allowed setting, or the machinery of [3, 4]: in particular [3, Theorem 4] already bounds well-intersecting families of bounded-size non-progression members with empty total intersection, and the δ-triplet techniques of [4] quantify how families deviating from a common centre pay in determining triples. Sharpening those O(N5/3)O(N^5/3)-type losses to exact losses is precisely what Problem 7.1 requires. We record one instructive caveat encountered en route to Theorem 5.3. Partial results towards Problem 7.1 Write B(N)=(N2)+1+⌊(N−1)/4⌋B(N)= N2+1+ (N-1)/4 . A putative counterexample to Conjecture 1.3 is a family F with |F|>B(N)|F|>B(N); by Theorem 1.4 such a family is non-starred. We prove several unconditional structural results about such families, culminating in Theorem 7.5: in a putative counterexample whose members of size at least 44 are progressions, all triples pass through a common element. Lemma 7.2 (Global private triple). Let F be any well-intersecting family and let z∈Fz∈ F with |z|≥4|z|≥ 4 not an arithmetic progression. Then z contains a triple lying in no other member of F. Proof. Write z=a1<⋯<amz=\a_1<…<a_m\. If every three consecutive elements were in arithmetic progression, all gaps would be equal and z would be an AP; so some consecutive triple T=ai−1,ai,ai+1T=\a_i-1,a_i,a_i+1\ has unequal gaps. The shortest AP P(T)P(T) containing T has difference dividing both gaps, hence strictly smaller than the larger gap, so P(T)P(T) contains a point of the open interval (ai−1,ai+1)(a_i-1,a_i+1) other than aia_i; since z has no such point, P(T)⊈zP(T) z. If another member z′z contained T, then z∩z′z∩ z would be an AP containing T, hence would contain P(T)P(T), forcing P(T)⊆zP(T) z — a contradiction. ∎ Lemma 7.3 (Triples are intersecting; Hilton–Milner dichotomy). The 33-element members of any well-intersecting family form an intersecting 33-uniform family. Consequently, for N≥7N≥ 7, by the Hilton–Milner theorem [5] either all 33-element members contain a common element, or there are at most 3N−83N-8 of them. Proof. Two distinct triples intersect in at most two elements, and any nonempty set of size at most 22 is an AP; the well-intersecting condition thus reduces exactly to nonempty intersection. ∎ Proposition 7.4 (Progression members without a common centre). Let A be the set of members of F that are APs of size at least 44, and for d≥1d≥ 1 let dA_d be those of difference d. Then, following [4, Corollary 2.4], all members of dA_d lie in one residue class modulo d and pairwise intersect, so by Helly’s theorem for intervals they share a common element; consequently |d|≤N24d2+4Nd|A_d|≤ N^24d^2+ 4Nd and, summing over d and using ∑d≥1d−2=π2/6 _d≥ 1d^-2=π^2/6 together with ∑d≤Nd−1≤lnN+1 _d≤ Nd^-1≤ N+1, ||≤π224N2+4NlnN+4N.|A|\ ≤\ π^224N^2+4N N+4N. Theorem 7.5 (Triples of a large AP-flavoured family have a kernel). Let N0=104N_0=10^4. For every N≥N0N≥ N_0 the following holds. Let F be well-intersecting with |F|>B(N)|F|>B(N), and suppose every member of size at least 44 is an arithmetic progression. Then all 33-element members of F contain a common element c; moreover F then contains members avoiding c, all of which are 22-element members or progressions of size at least 44, and every triple c,u,v∈F\c,u,v\∈ F satisfies u,v∩A≠∅\u,v\∩ A≠ for each such member A. Proof. Since |F|>B(N)|F|>B(N), F is non-starred by Theorem 1.4, so by Lemma 7.8 below it has no singleton, and its 22-element members form an intersecting family of pairs, i.e. a star or a triangle: at most N−1N-1 members. If the triples did not share a common element then by Lemma 7.3 there are at most 3N−83N-8 of them, whence by Proposition 7.4 |F|≤(N−1)+(3N−8)+π224N2+4NlnN+4N<N22−N2≤B(N),|F|\ ≤\ (N-1)+(3N-8)+ π^224N^2+4N N+4N\ <\ N^22- N2\ ≤\ B(N), the last inequality because B(N)=(N2)+1+⌊(N−1)/4⌋B(N)= N2+1+ (N-1)/4 and (N2)=N22−N2 N2= N^22- N2; the strict inequality holds for all N≥400N≥ 400, since it amounts to (12−π224)N>4lnN+8.5 ( 12- π^224 )N>4 N+8.5 with 12−π224>0.0887 12- π^224>0.0887 — a contradiction. Hence all triples contain a common c. If every member contained c the family would be starred; so some member A avoids c, and A is not a singleton and not a triple, leaving the stated forms. The final claim is the intersection condition c,u,v∩A≠∅\c,u,v\∩ A≠ with c∉Ac∉ A. ∎ In the setting of Theorem 7.5 much more can be said about the members avoiding c. Proposition 7.6 (Avoiders are long progressions). In the setting and conclusion of Theorem 7.5 (so N≥N0N≥ N_0), let Fc¯F_ c denote the members of F avoiding c. Then: (i) Fc¯F_ c contains no 22-element member; hence every member of Fc¯F_ c is an arithmetic progression with at least 44 elements. (i) Every member of Fc¯F_ c has more than N/12N/12 elements; consequently its difference is at most 1212. Proof. (i) Suppose u,v∈F\u,v\∈ F with c∉u,vc∉\u,v\. Every triple of F has the form c,x,y\c,x,y\ and must intersect u,v\u,v\, so its link pair x,y\x,y\ meets u,v\u,v\; the number of pairs meeting a fixed pair is at most 2(N−2)+12(N-2)+1, so F has at most 2N−32N-3 triples. Then, using Proposition 7.4 for all members of size at least 44 (which are APs by hypothesis, wherever located) and at most N−1N-1 members of size ≤2≤ 2, |F|≤(N−1)+(2N−3)+π224N2+4NlnN+4N<N22−N2≤B(N)|F|\ ≤\ (N-1)+(2N-3)+ π^224N^2+4N N+4N\ <\ N^22- N2\ ≤\ B(N) for N≥N0N≥ N_0 (indeed for N≥400N≥ 400, as in the proof of Theorem 7.5), a contradiction. (i) Let A∈Fc¯A∈ F_ c with a=|A|a=|A| elements. Every triple of F is c,x,y\c,x,y\ with x,y\x,y\ meeting A, and distinct triples have distinct link pairs, so the number of triples is at most a(N−1)−(a2)≤aNa(N-1)- a2≤ aN. Hence |F|≤(N−1)+aN+π224N2+4NlnN+4N.|F|\ ≤\ (N-1)+aN+ π^224N^2+4N N+4N. If a≤N/12a≤ N/12 the right-hand side is at most (112+π224)N2+4NlnN+5N<N22−N2≤B(N) ( 112+ π^224 )N^2+4N N+5N< N^22- N2≤ B(N) for N≥N0N≥ N_0: since 112+π224<0.49457 112+ π^224<0.49457, the required inequality amounts to 0.00543N>4lnN+5.50.00543\,N>4 N+5.5, which holds for all N≥8000N≥ 8000 — a contradiction. (This is the binding constraint behind the choice N0=104N_0=10^4; the other steps need only N≥400N≥ 400.) Finally, a progression with more than N/12N/12 elements inside [N][N] has difference less than 12N/(N−12)12N/(N-12), which is smaller than 1313, hence at most 1212, once N≥157N≥ 157. ∎ Theorem 7.5 and Proposition 7.6 localize a putative AP-flavoured counterexample severely: its quadratic bulk of triples is a star at some c, while the members avoiding c are progressions of more than N/12N/12 elements and difference at most 1212, each missing the element c, pairwise intersecting in progressions, and meeting the link pair of every triple. The remaining endgame — ruling this configuration out exactly, and removing the AP-flavour hypothesis using Lemma 7.2 — is what now separates us from Szabó’s kernel question in full. Remark 7.7 (The endgame configurations appear self-limiting). We describe, without complete proofs, why the localized configuration seems unable to reach B(N)B(N). Suppose first that the avoiders of difference 11 all pass through a common point p (as Helly’s theorem forces) and have length at least L. A link pair whose two elements straddle p at distance more than about L contains a length-L interval through p strictly between its elements, hence fails to meet that avoider; so the straddling link pairs are confined to a band of about L2/2L^2/2 pairs around p, while one-sided pairs miss the extreme avoiders altogether. On the other hand the number of intervals through p of length at least L is smaller than the number of all intervals through p by essentially the same quantity L2/2L^2/2: the gain in link pairs and the loss in avoiders cancel, and the configuration tops out near N2/4N^2/4 members. Larger differences d≤12d≤ 12 confine link pairs to residue classes and only lower the total, and a central c forces the interval avoiders to one side of c, shrinking both counts further. Turning these cancellations into an exact proof — uniformly in the position of c, the twelve possible differences, and the per-difference Helly points, and then removing the AP-flavour hypothesis via Lemma 7.2 and an exact analogue of the non-progression bounds of [3] — is, in our assessment, the entire remaining content of Szabó’s kernel question. We record next what can be said with no assumption on the large members. Lemma 7.8. A family containing a singleton is starred. Hence every non-starred family has all members of size at least 22. Proof. If x∈F\x\∈ F then every member meets x\x\, i.e. contains x. ∎ Lemma 7.9 (Cross-intersecting pairs). Let n≥3n≥ 3 and let ,ℬA,B be nonempty families of 22-subsets of an n-set such that every member of A meets every member of ℬB. Then ||+|ℬ|≤2n+1|A|+|B|≤ 2n+1. Proof. If A contains two disjoint pairs e,fe,f, then every b∈ℬb has one endpoint in e and one in f, so |ℬ|≤4|B|≤ 4; fixing b0∈ℬb_0 , every a∈a meets b0b_0, so ||≤2(n−2)+1|A|≤ 2(n-2)+1; the total is at most 2n+12n+1. Otherwise A is an intersecting family of 22-sets, hence a star or a triangle. If A is a star at p with ||≥3|A|≥ 3, a pair avoiding p meets at most two star pairs, so ℬB is contained in the star at p and the total is at most 2(n−1)2(n-1). If A is a triangle, ℬB consists of pairs on its three vertices and the total is at most 66. If ||≤2|A|≤ 2, then |ℬ|≤2(n−2)+1|B|≤ 2(n-2)+1 and the total is at most 2n+12n+1. ∎ Proposition 7.10 (Two-star deduction). Let F be non-starred with x,y∈F\x,y\∈ F. Then every member of F contains x or y. Moreover, for every member B∈FB∈ F with y∈By∈ B, x∉Bx∉ B, writing Fx=A∈F:x∈AF_x=\A∈ F:x∈ A\, QBQ_B for the set of pairs u,v⊆[N]∖(x∪B)\u,v\ [N] (\x\∪ B), and KxK_x for the set of bad pairs (with respect to the centre x) covered by the members of FxF_x of size at least 44, |Fx|≤B(N)−|QB∖Kx|.|F_x|\ ≤\ B(N)\ -\ |Q_B K_x|. Proof. Every member meets x,y\x,y\, giving the covering statement. For the deduction, refine Proposition 3.1 at the centre x: a triple T=x,u,v∈FxT=\x,u,v\∈ F_x must satisfy that T∩BT∩ B is a nonempty AP; since x∉Bx∉ B, this forces u,v∩B≠∅\u,v\∩ B≠ , so no triple of FxF_x uses a pair from QBQ_B (pairs containing y meet B and are unaffected). Hence the triples of FxF_x number at most (N−12)−|Kx|−|QB∖Kx| N-12-|K_x|-|Q_B K_x|, while the members of size at most 22 number at most N and, by Theorem 5.3, the members of size at least 44 number at most |Kx|+⌊(N−1)/4⌋|K_x|+ (N-1)/4 . Summing gives the claim. ∎ Corollary 7.11. If F is non-starred with a 22-element member x,y\x,y\ and |F|>B(N)|F|>B(N), then for every y-only member B the number of y-only members exceeds |QB∖Kx|≥(N−1−|B|2)−|Kx||Q_B K_x|\ ≥\ N-1-|B|2-|K_x|, and symmetrically with x,yx,y exchanged. In particular either every y-only member is large, or the y-only members are numerous — yet by Lemma 7.9 the x-only and y-only triples of F together number at most 2N+12N+1 whenever both kinds occur, so the numerous side must consist almost entirely of members of size at least 44, which are in turn throttled by Theorem 5.3 at their own centre. Thus a counterexample passing through a 22-element member is forced into a narrow regime of large, mutually near-progression members; the remaining open regimes for Problem 7.1 are this large-member regime and the families whose minimum member size is 33 or more. Remark 7.12 (Primitive counting does not generalize). One might hope to prove Theorem 5.3 by generalizing Lemma 3.3 verbatim, counting only primitive covered bad pairs. That statement is false: take the three window intervals −2,…,2\-2,…,2\, −2,…,1\-2,…,1\, −1,…,2\-1,…,2\ (adjoining 0) together with z=0,6,10,15z=\0,6,10,15\. All pairwise intersections are APs and |S|=4|S|=4, yet only two primitive bad pairs (−2,1\-2,1\ and −1,2\-1,2\) are covered, since the three bad pairs of z have gcds 2,3,52,3,5. The full count is safe — indeed all three pairs of z are private, illustrating Theorem 5.2 — and this is why crooked members must be credited their imprimitive kills, as the proof of Theorem 5.3 does. We also note that the sequence t(3),…,t(12)t(3),…,t(12) is not currently in the OEIS, and that the database entry [6] explicitly requests an associated integer sequence; we intend to submit it. Finally, it would be interesting to carry out the analogous exact analysis for the variants of [3] in which all pairwise intersections must be APs of at least k terms, k≥2k≥ 2; there even the qualitative question of [3, 4], whether the extremal systems consist of arithmetic progressions only, remains open. Acknowledgements The author used Claude (Anthropic) as an assistive tool for some computations and drafting. All proofs and computational claims have been checked by the author, who takes full responsibility for their correctness; where a result relies on computer verification, sufficient detail is given in Section 6 to allow independent replication. References [1] P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de L’Enseignement Mathématique 28, Genève, 1980. [2] R. L. Graham, M. Simonovits and V. T. Sós, A note on the intersection properties of subsets of integers, J. Combin. Theory Ser. A 28 (1980), 106–110. [3] M. Simonovits and V. T. Sós, Intersection properties of subsets of integers, European J. Combin. 2 (1981), 363–372. [4] T. Szabó, Intersection properties of subsets of integers, European J. Combin. 20 (1999), no. 5, 429–444. [5] A. J. W. Hilton and E. C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2) 18 (1967), 369–384. [6] T. F. Bloom, Erdős Problem #272, https://w.erdosproblems.com/272 (problem page and discussion thread), accessed July 2026.