Erdős problem #963 · additive combinatorics
Write down a few numbers. Now add up every group of them you can form and ask whether any two of those totals come out the same. If they never do, the numbers are what mathematicians call dissociated: every subset has its own private total.
Most small collections of numbers fail this test badly. Take 1, 2, 3: the group {1, 2} and the group {3} both total 3, so those three numbers are not dissociated. But you can usually find a few numbers inside your collection that are. From 1, 2, 3, 4, 5, 6 you can pull out 1, 2, 4, whose eight totals are all different.
Erdős asked in 1965 how many you are always guaranteed. Given any n numbers, how big a dissociated group must hide inside them? He could prove you always get about log3 n of them, and guessed you always get log2 n, which is a lot more. Sixty years later, nobody knew the answer even for small n, and no exact value of the guaranteed size had been published at all.
The figure is the smallest hard case. Six numbers can be chosen so that every single group of four of them has a coincidence, so no four of them are dissociated. Seven numbers cannot.
Erdős's function f(n) is the guaranteed size: the largest k such that every n real numbers contain a dissociated subset of size k. Before this session the problem page carried an asymptotic lower bound and no exact values.
Everything below is the technical version. The staircase in section 4 is the fastest way to see what is now known and where it stops; the ladder in section 5 shows how far the remaining thresholds are from Erdős's guess.
A set B ⊂ ℝ is dissociated if its 2|B| subset sums are distinct. Erdős (1965; Erdős Problems #963, Vaughan's list 1.22) defined f(n) as the largest k such that every n-element A ⊂ ℝ contains a dissociated subset of size k, noted the greedy bound f(n) ≥ ⌊log3 n⌋, and asked whether f(n) ≥ ⌊log2 n⌋. An argument of KoishiChan on the problem page gives f(n) ≥ (1−o(1)) log2 n asymptotically; the inequality itself, and every exact value of f, were open.
This note (i) reduces f to sets of distinct positive reals, f(n) = g(⌈(n−1)/2⌉) (Lemma 1.1, proved), where g(m) is the same minimum over m distinct positive reals, so that the question is equivalent to g(2k−1) ≥ k for every k; (ii) decides the first open instance by an exact, machine-checked case analysis over the hyperplane arrangement of ±1 relations: every 7 distinct positive reals contain a dissociated 4-subset, and 6 do not always (Theorem 3.1, certified); hence f(n) is known exactly for all n ≤ 27, Erdős's inequality holds for all n ≤ 31, and it is strict at n = 14, 15; (iii) gives the structural lemma behind the searches, that every element of a set with no dissociated k-subset is a signed sum of any dissociated (k−1)-subset; and (iv) reports the upper-side records: a 24-element set with no dissociated 6-subset (certified), and the state of the k = 5 threshold, which is not decided here: 14 ≤ m5 ≤ 41.
For a finite B ⊂ ℝ, B is dissociated if all sums Σb∈S b, S ⊆ B, are distinct; equivalently, if no nonzero ε ∈ {−1, 0, 1}B has Σ εb b = 0 (take ε = 1S − 1T for two subsets with equal sums, and conversely). Write d(A) for the size of the largest dissociated subset of a finite A ⊂ ℝ, and
For every n ≥ 1, f(n) = g(⌈(n−1)/2⌉).
Proof. Let A ⊂ ℝ with |A| = n and let P = {|a| : a ∈ A, a ≠ 0}. (a) A dissociated set contains neither 0 (the empty set and {0} have equal sums) nor a pair {a, −a}. (b) Dissociation is invariant under changing the sign of any element, since Σ εb b = 0 iff Σ (εbsb)(sbb) = 0 and ε ↦ (εbsb) permutes the nonzero sign vectors. So a dissociated B ⊆ A has |B| distinct absolute values forming a dissociated subset of P, and conversely a dissociated subset of P lifts to one of A by choosing a preimage of each absolute value. Hence d(A) = d(P). Since A contains at most one zero and at most two elements of each absolute value, |P| ≥ ⌈(n−1)/2⌉, so d(A) ≥ g(⌈(n−1)/2⌉) by monotonicity. Equality is attained by A = {0} ∪ P ∪ (−P) for odd n and A = P ∪ (−P) for even n, with P extremal for g. ∎
The following are equivalent: (i) f(n) ≥ ⌊log2 n⌋ for all n ≥ 1; (ii) g(m) ≥ ⌊log2 m⌋ + 1 for all m ≥ 1; (iii) g(2k−1) ≥ k for all k ≥ 1; (iv) mk ≤ 2k−1 for all k ≥ 1.
For n = 2m+1 and n = 2m with m ≥ 1, Lemma 1.1 gives f(n) = g(m), while ⌊log2(2m+1)⌋ = ⌊log2(2m)⌋ = ⌊log2 m⌋ + 1, and f(1) = 0 = ⌊log2 1⌋; the rest is monotonicity of g and the definition of mk. So Erdős's question has one first open instance per k: for k = 3, whether every 4 distinct positive reals contain a dissociated triple; for k = 4, whether every 8 contain a dissociated 4-subset; for k = 5, whether every 16 contain a dissociated 5-subset. Nobody on the problem page had taken this step, and it is what makes the rest finite.
g(m) ≥ k whenever m ≥ (3k−1+1)/2, that is mk ≤ (3k−1+1)/2. In particular m3 ≤ 5, m4 ≤ 14, m5 ≤ 41, m6 ≤ 122.
Proof. Induction on k. If B ⊆ P is dissociated with |B| = k−1, then B ∪ {x} fails to be dissociated only if x is a signed sum Σb∈B εbb, because the coefficient of x in any relation must be nonzero while B itself carries no relation. The positive signed sums of B number at most (3k−1−1)/2, since nonzero signed sums come in pairs ±s, so if |P| ≥ (3k−1+1)/2 some x ∈ P extends B. ∎ This is Erdős's ⌊log3 n⌋ bound in the positive setting.
g(m) ≤ d({1, …, m}) = max{ k : F(k) ≤ m }, where F(k) is the least possible largest element of a k-element set of positive integers with distinct subset sums. Hence mk ≥ F(k).
A dissociated subset of {1, …, m} is exactly a set of positive integers with distinct subset sums and largest element at most m. Recomputed here from the definition, F(1..6) = 1, 2, 4, 7, 13, 24 and d({1..m}) = 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6 for m ≤ 24, so g(m) ≤ 3 for m ≤ 6, g(m) ≤ 4 for m ≤ 12 and g(m) ≤ 5 for m ≤ 23. The values F(7..9) = 44, 84, 161 are cited from OEIS A276661 (Lunnon, Grossman), a secondary source not independently recomputed here.
Let P ⊂ ℝ>0 have no dissociated k-subset and let T ⊆ P be a dissociated (k−1)-subset. Then every element of P is a signed sum Σt∈T εt t with ε ∈ {−1, 0, 1}T.
Proof. For x ∈ P ∖ T the set T ∪ {x} carries a relation whose coefficient on x is nonzero, since T carries none. ∎ Combined with Theorem 3.1 below, this says that every set of at least 7 positive reals with no dissociated 5-subset is a dissociated 4-set T together with a choice of signed sums of T: a four-parameter family, which is what makes the k = 5 searches of section 5 finite in a useful way.
One more bookkeeping fact drives every engine. For 0 < a1 < a2 < a3 < a4, a nonzero sign vector can satisfy Σ εiai = 0 only in six ways: a3 = a1+a2, a4 = a1+a2, a4 = a1+a3, a4 = a2+a3, a4 = a1+a2+a3, or a1+a4 = a2+a3. For five sorted positive reals there are 26 such patterns. Each engine regenerates these lists by an exact feasibility test rather than trusting a hand list, and the checker regenerates them again.
(a) Every set of 7 distinct positive reals contains a dissociated 4-subset. (b) The 6-element sets {1,2,3,4,5,6}, {1,2,3,5,7,8}, {1,2,3,4,6,7}, {2,3,5,10,12,15}, and the one-parameter families through them, contain none. (c) Every 4 distinct positive reals contain a dissociated triple, and {1,2,3} shows that three do not. Hence m3 = 4 and m4 = 7.
Part (c) has a two-line proof: if no triple of a1<a2<a3<a4 is dissociated then a3 = a1+a2 and a4 = a1+a2, contradicting a3 < a4. Part (a) is an exhaustive exact case analysis, and it is the reason this result is labelled certified rather than proved: there is no written argument, only a machine case tree and a program that checks it.
A sorted point a ∈ ℝ7 with no dissociated 4-subset must satisfy, for each of the 35 four-subsets, one of the six relations above. The search keeps a rational linear subspace S spanned by the relations chosen so far, calls a 4-subset blocked if one of its relations vanishes identically on S, and while some 4-subset is unblocked branches on its six relations, each child being S ∩ r⊥, one dimension smaller. A child on which some ai = 0 or ai = aj is forced is discarded. A child whose subspace misses the open cone {0 < a1 < … < a7} is discarded with an explicit Gordan certificate (λ ≥ 0, λ ≠ 0, Σ λici in the span of the relations, for the cone rows ci), obtained by Fourier-Motzkin elimination or from a floating-point linear program whose dual is rationalised and verified exactly. A feasible leaf is a counterexample family and yields an explicit rational witness. Soundness is the observation that every valid point on S lies on one of the six relations of the branching subset, hence in one of its children.
| Engine | Organisation | Nodes | Certificate |
|---|---|---|---|
| A | fail-first branching, Fourier-Motzkin leaves | 290 | certs/A_k4_m7.json, checked |
| B | row-echelon state, prefix-first branching, exact LP certificates at every node | 1099 | no certificate emitted |
| C | fail-first, certified LP pruning, subspace memoisation | 111 | certs/C_k4_m7.json, checked |
| D | dissociation case split (section 5) | 62 | certs/D_k4_m7.json, checked |
The checker (code/checker.py, exact rational arithmetic, no code shared with
the engines) re-derives the six relation patterns from scratch, verifies that every
branching is exhaustive, that every forced-equality pruning is a true linear consequence,
that every infeasible leaf or pruned child carries a valid Gordan certificate (recomputing
one when the file supplies none), and that every witness is a sorted positive point of its
subspace whose largest dissociated subset really is smaller than 4. Re-running it today on
the three shipped trees reproduces the node counts above and the verdict
g(7) ≥ 4 from each one independently, and the four 6-element witness sets of part
(b) were re-verified here by brute force over all their subsets: each has
d = 3.
Lemma 1.1 turns Theorem 3.1 into exact values. Since g(m) = 3 for 4 ≤ m ≤ 6 and g(m) = 4 for 7 ≤ m ≤ 13 (the upper bounds from {1, …, 12} and from BAKKAOUI's 13-element set {1, …, 10, 12, 13, 15}, both re-verified here), f(n) = g(⌈(n−1)/2⌉) is determined up to n = 27.
Two consequences worth stating separately. The problem page's entry for this function recorded f(13) ≤ 4; the reduction gives f(13) = 3. And the strictness at n = 14, 15 is the first place where Erdős's guessed bound is not tight, which is evidence in favour of the inequality rather than against it.
By Lemma 2.2 and BAKKAOUI's 13-element set, m5 ≥ 14; by Lemma 2.1, m5 ≤ 41. Erdős's question at n = 32, 33 is whether m5 ≤ 16. This session did not answer it, and the reason is worth recording, because it is a statement about cost rather than about mathematics.
Engines C and D find explicit sets with no dissociated 5-subset for every size m ≤ 13 in seconds to minutes, for example {1,2,3,5,6,7,8,9,10,12,13,15} at m = 12, all re-verified by brute force; the m = 8 case ships a checked certificate. Engine E works directly inside the four-parameter family of Lemma 2.3. Engine F adds a normalisation that puts the dissociated 4-set inside the seven smallest elements, leaving only 21 five-subsets to block. Engine G replaces every linear program in F by exact extreme-ray arithmetic: the feasible region is a pointed polyhedral cone kept as its primitive integer rays and updated by one double-description step per constraint. G reproduces F's k = 4 enumeration node for node (159 nodes) and agrees with the LP tests on 3968 random region decisions, and it is about twenty times faster, but its k = 5 enumeration has 1,103,785 phase-one configurations, which is roughly thirty hours of Python per candidate order. Four two-hour runs reached 5.3 % and 6.8 % of phase one in the forward and reversed orders and two shuffled orders got no further; all four ended with a best set of size 12. A completeness control, feeding BAKKAOUI's 13-set's sign vectors first, reaches it after 5 nodes, so the enumeration does find 13-element sets when they are early in its order.
So m5 ∈ [14, 41] is the state of knowledge, f(28) through f(31) are known only to be at least 4, and Erdős's inequality at n = 32 is undecided. What is certified at k = 5 is the list of witnesses for every m ≤ 13 and the m = 8 certificate. A C port of engine G, whose arithmetic is all small integers, should bring the full enumeration under an hour, and m5 = 14 would give f(n) = 5 for 28 ≤ n ≤ 47 and Erdős's inequality for all n ≤ 63.
A24 = {1, 2, …, 21, 24, 25, 27} has d(A24) = 5: the subset {1, 2, 4, 8, 16} is dissociated and none of the 134,596 six-element subsets is. Hence g(24) ≤ 5 and m6 ≥ 25, one more than the interval bound m6 ≥ F(6) = 24.
Found by simulated annealing over 24-element subsets of {1, …, 40} (seed 1, 8 seconds) and verified by two independent exact programs, one a depth-first search over dissociated subsets and one an enumeration of all six-element subsets. Re-verified here: zero of the 134,596 six-subsets is dissociated, and {1,2,4,8,16} is. The same annealing campaign found no 25-element set with d ≤ 5 (its best kept 4 dissociated 6-subsets) and no 14-element set with d ≤ 4 (its best kept 7), which is heuristic evidence only and is labelled numerical: a failure to find is not a proof of absence.