Sum-intersecting families of integers: exact values through n=15, and the distinct-sum and k-sum variants
Abstract
A family F of subsets of [n]={1,…,n} is sum-intersecting if for all A,B ∈ F (the case A=B included) the intersection A ∩ B contains elements x,y,z, not necessarily distinct, with x+y=z; write f(n) for the largest size of such a family. Berger and Mani conjectured f(n)=2ⁿ⁻² and proved f(n) ≤ 0.32 · 2ⁿ. The partition method of Chung, Graham, Frankl and Shearer settles the conjecture only as far as the Schur number S(3)=13. We determine f(n) for every n ≤ 15; in particular f(14)=4096 and f(15)=8192, the first two values beyond the Schur wall. The proof runs the Delsarte linear programme of the source paper at a single ground set and exhibits an exact rational optimal certificate there; we prove that the programme's optimum c₀^(*)(n) equals 3 at n=14 and at n=15, that c₀^(*) is non-increasing in n, and that the whole conjecture reduces to the statement c₀^(*)(n)=3 for all n. We also show f(n) ≤ (5)/(16) · 2ⁿ for 9 ≤ n ≤ 160, improving the published constant on that range, and we close two routes to n=16: a natural half-splitting lift of certificates is impossible at every even step, and the cyclically consecutive partition bound of Faudree, Schelp and Sós collapses to a three-part partition and therefore cannot pass n=13. For the distinct-sum variant, where x,y,z must be pairwise different, we determine the maximum g(n)=2ⁿ⁻³ for every n ≤ 12 and prove g(n) ≤ 2ⁿ⁻² for every n ≤ 23. For the k-sum variant we show that any family beating 1/4 2ⁿ consists entirely of sets of at least three elements, that the extremal cores {d,kd} come in ⌊ n/k⌋ equally good versions, and we compute the maximum for k=3, n ≤ 12 and k=4, n ≤ 8. All statements are machine-checked.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 1 · current (opens in a new tab)
Source snapshot 2026-08-30 15:34 UTC
File fingerprint
c93d0a28ebd6085e9af1803d75577f166ce0e1ca76a37ae889232e7b4c2a6761
Claim ledger
Stated results
set-family-01known2026-08-17
Conventions (x,y,z need not be distinct; A = B allowed)
set-family-02known2026-08-17
(1/4)·2ⁿ construction
set-family-03known2026-08-17
d, 2d generalization of it
set-family-04routine2026-08-17
f(n) = 2ⁿ⁻² for n = 2..11
set-family-05known2026-08-17
The CGFS route: a sum-free k-partition of [n] gives f(n) ≤ 2ⁿ⁻ᵏ·g(k,2)
set-family-06known2026-08-17
f(n) = 2ⁿ⁻² for every n ≤ 13, one proof for all of them (Split.upperBound)
set-family-07routine2026-08-17
k = 3 is the only useful parameter, and the technique is exhausted at n = 13
This ledger entry is reported in prose and is not bound to a Lean theorem.set-family-08routine2026-08-17
f(n) ≤ (5/16)·2ⁿ for 9 ≤ n ≤ 160 — delivered, kernel-clean
set-family-09known2026-08-17
The same n ≤ 13 result, derived independently from the source paper's own LP
set-family-10routine2026-08-17
The source paper's own certificate shape cannot prove its conjecture: the LP ceiling is c₀ ≈ 2.810, not 3
This ledger entry is reported in prose and is not bound to a Lean theorem.set-family-11routine2026-08-17
f(n) ≤ ≈ 0.2625·2ⁿ at n = 14, 15, 16
This ledger entry is reported in prose and is not bound to a Lean theorem.set-family-12routine2026-08-17
Any n = 14 certificate needs ≥ 9 sets spanning ≥ 5 dimensions
This ledger entry is reported in prose and is not bound to a Lean theorem.set-family-13routine2026-08-17
c₀*(14) = 3 — SetFamily/Cert14.lean, kernel-clean
set-family-14routine2026-08-17
Optimal families number exactly ⌊n/2⌋, all of d,2d shape
set-family-15known2026-08-17
upperBoundₒf_coloring (partition bounds clique number)
set-family-16known2026-08-17
The question, and the (1/8)·2ⁿ threshold
This ledger entry is reported in prose and is not bound to a Lean theorem.set-family-17known2026-08-17
2 ^ (n-3) construction (all supersets of a, b, a+b)
This ledger entry is reported in prose and is not bound to a Lean theorem.set-family-18routine2026-08-17
g(n) = 2 ^ (n-3) for n = 3..8 (Lean), n = 9 (search)
set-family-19routine2026-08-17
g(9) = 64 and g(10) = 128, exactly
set-family-20routine2026-08-17
The j = 3 partition route is dead, and the obstruction is exact
This ledger entry is reported in prose and is not bound to a Lean theorem.set-family-21routine2026-08-17
g(n) ≤ 2ⁿ⁻² for every n ≤ 23 — delivered, kernel-clean
set-family-22routine2026-08-17
The coset argument needs only monotonicity of the solution predicate
set-family-23known2026-08-17
The question, and the (1/4)·2ⁿ threshold
set-family-24known2026-08-17
d, k·d construction, all k and all n
set-family-25routine2026-08-17
Any family beating (1/4)·2ⁿ consists entirely of sets of size ≥ 3
set-family-26routine2026-08-17
hₖ(n) = 2ⁿ⁻² for k = 3, n ≤ 14; k = 4, n ≤ 13
set-family-27routine2026-08-17
Maximum families are exactly the supersets of d, k·d — one of ⌊n/k⌋ equally good cores, not just 1,3
set-family-28routine2026-08-22
g(11) = 256 and g(12) = 512, exactly – the star split
set-family-29routine2026-08-22
Linear (Fano) colourings for g(n) = 2ⁿ⁻³ exist iff n <= 8
This ledger entry is reported in prose and is not bound to a Lean theorem.set-family-30known2026-08-22
Delsarte duality step: a certificate of mass c gives |F|·(1+c) ≤ 2ⁿ
set-family-31candidate2026-08-23
f(14) = 4096
set-family-32candidate2026-08-23
f(15) = 8192, and c₀*(15) = 3
set-family-33candidate2026-08-23
f(n) = 2ⁿ⁻² for every 2 ≤ n ≤ 15
set-family-34routine2026-08-22
Conjecture 1.2 reduced: (∀ n ≥ 2, 3 ∈ achievable n) → ∀ n ≥ 2, f(n) = 2ⁿ⁻²
set-family-35known data2026-08-22
|D(n)| = 607, 847, 1400, 1954 at n = 13, 14, 15, 16
set-family-36known2026-08-22
No two columns of D₁₄ (resp. D₁₅) have their symmetric difference a column
set-family-37routine2026-08-22
Half-split lift: a certificate supported on the liftable columns of [n] lifts to [n+1]
set-family-38routine2026-08-22
The half-split lift is dead at every even step: at n+1 = 2m a liftable certificate has mass ≤ 1
set-family-39known2026-08-22
Kleitman's diameter theorem at t = 1: g(l, l-1) = 2 for every l, and it is the constant in Gen.Split
set-family-40known2026-08-22
FSS 1986 Theorem 1 / Corollary 2 — the *cyclically consecutive* partition bound 2ⁿ⁻ᵏ, independent of the number of parts — read here for the first time; CGFS has only its singleton case (§III Theorem 5)
This ledger entry is reported in prose and is not bound to a Lean theorem.set-family-41routine2026-08-22
The FSS cyclic route collapses: a cyclic certificate at k = 2, for any l ≥ 3, is exactly a three-part CGFS split — both directions
set-family-42routine2026-08-22
The k ≥ 3 cyclic branch is closed: impossible for sums, and n ≤ 11 for distinct sums
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- Sum-intersecting families and variants (distinct-sum, k-sum)
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7