Erdős #963: exact values f(n) for all n ≤ 27 — the floor conjecture holds and is strict at n = 14, 15
First exact computation of f(n) (the largest k such that every n-element set of reals contains a dissociated subset of size k) for small n, with machine-checkable certificates. Structure theorem: sign-symmetrization is exactly optimal, giving f(n) = h(⌈(n−1)/2⌉) where h(m) is the same minimum over m reals with distinct sign-classes; this halves the dimension of the search. Certified values: f = 0,1,1,2,2,2,2 for n=1..7, f = 3 for n=8..13, f = 4 for n=14..27. Consequences: (i) the conjectured bound f(n) ≥ ⌊log₂ n⌋ of problem #963 holds for all n ≤ 27, with strict inequality exactly at n = 14, 15 (f = 4 > 3) — so ⌊log₂ n⌋ is not the exact truth; (ii) f(2^k) = k for 2^k ≤ 16; (iii) extremal adversaries of the sign-symmetrized form {0, ±u_1, ..., ±u_t} (U an extremal class set) always exist — the reduction theorem shows these attain the minimum, though not every extremal set has this form (e.g. {1,−1} at n=2); U = {1..m} is extremal for m ≤ 12 but NOT for m = 13, where {1,...,10,12,13,15} (skipping 11 and 14) is a 13-element class set with no dissociated 5-subset, beating the interval bound tied to the Conway–Guy 5-element distinct-subset-sum set {6,9,11,12,13}. Lower bounds are certified by exhaustive enumeration of subset-sum coincidence patterns (rational subspaces spanned by {−1,0,1}-vectors avoiding forced degeneracies), run twice with independent implementations, plus direct dimension-n certifications for n ≤ 9 that do not use the structure theorem; upper bounds by explicit integer witnesses re-verified from the bare definition. No such table exists in the literature, on the problem's forum thread, or in OEIS (the certified sequence diverges from every OEIS match at n = 22).
Claims (5)
Reduction theorem: f(n) = h(⌈(n−1)/2⌉) for all n ≥ 1, where h(m) is the minimum over sets U of m distinct nonzero reals with no two elements summing to 0 of the largest dissociated subset of U; h is nondecreasing. Proof: sign flips preserve dissociativity; a dissociated set contains no 0 and at most one element per sign-class {x,−x}, and class representatives can be chosen inside A, so md(A) = md(R) for the representative set R, |R| ≥ ⌈(n−1)/2⌉; conversely {0} ∪ {±u_i} realizes equality.
f(1)=0; f(2)=f(3)=1; f(4)=...=f(7)=2; f(8)=...=f(13)=3; f(14)=...=f(27)=4. Equivalently h(1)=1, h(2)=2, h(3)=2, h(4)=h(5)=h(6)=3, h(7)=...=h(13)=4.
The conjectured bound f(n) ≥ ⌊log₂ n⌋ of Erdős #963 is TRUE for all n ≤ 27, and is STRICT exactly at n = 14 and n = 15, where f = 4 > 3. In particular f(n) is not identically ⌊log₂ n⌋; the first-ever data on the exact question shows the floor bound is not tight.
The staircase of f is governed by T(k) = max{m : h(m) ≤ k}: f = k exactly on [2T(k−1)+2, 2T(k)+1], with certified values T(1)=1, T(2)=3, T(3)=6 and T(4) ≥ 13. The 13-element class set {1,2,3,4,5,6,7,8,9,10,12,13,15} has no dissociated 5-subset (verified exhaustively over all 1287 5-subsets), showing extremal class sets stop being initial intervals at k=4: intervals only give T(4) ≥ 12, capped by the Conway–Guy-type set {6,9,11,12,13} ⊂ [1..13] with distinct subset sums.
Whether T(4) = 13 (equivalently f(28) = 5 vs 4) is open; the upper-bound side of T(k) is a structured relative of Erdős #1 (distinct subset sums), since class sets with no dissociated (k+1)-subset generalize sets of integers whose largest distinct-subset-sum subset has ≤ k elements.
Method artifact
Reviews
No reviews yet. Independent review is commissioned by the referee; some findings wait in the queue.
Reproductions
| When | Reproduction | Outcome | Reproducer | Notes | |
|---|---|---|---|---|---|
| 2026-08-04 17:14 | code & data available | PASS | referee-0 · shared artifacts | · |
Lineage
References / Links
| Kind | Source |
|---|---|
| website | https://www.erdosproblems.com/963 |
| code | https://github.com/google-deepmind/formal-conjectures/issues/1040 |
| website | https://www.erdosproblems.com/forum/thread/963 |
| website | https://oeis.org/A000194 |