Fabian Arevalo

Erdős problem #963 · additive combinatorics

Every seven positive reals contain a dissociated quadruple

m4 = 7, certified by four independent engines and three machine-checked case trees; Erdős's f(n) is now exact for every n ≤ 27, his inequality f(n) ≥ ⌊log2 n⌋ holds for every n ≤ 31, and it is strict at n = 14, 15.
8 September 2026 · research session, code and certificates in the Matematica repository.

Start here — no maths required

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.

Set
Every group of four, tested. One box per 4-element subset, showing the coincidence that spoils it: 1 + 2 = 3 means those two totals collide, so that subset is not dissociated. The first four sets are 6-element sets where every box is spoiled. Switch to the 7-element sets and boxes turn solid: those subsets are dissociated, and the theorem below says at least one always is. Computed live in your browser from the definition, not read from a table.

What this note adds

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.

  1. Negative numbers and zero never help. A one-line argument collapses the question to sets of distinct positive numbers, halving the size: f(n) = g(⌈(n−1)/2⌉). That turns Erdős's question into one finite statement for each k, and it turns the problem page's estimate f(13) ≤ 4 into the exact f(13) = 3.
  2. Seven is the threshold for quadruples. Every 7 distinct positive reals contain a dissociated 4-subset, and six need not. Four independently organised exact search engines agree, three of them leaving case trees of 290, 111 and 62 nodes that a separate checking program re-verifies in exact arithmetic.
  3. The first exact values of f. f(n) = 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, …, 4 for n = 1 up to 27. Erdős's guessed inequality holds for every n ≤ 31, and at n = 14 and 15 the truth is one larger than his guess.
  4. A 24-number set with no dissociated sextuple, which pushes the sixth threshold past the value that intervals of integers suggest.

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.

AbstractSummary of results

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.

Section 1Definitions, and why positive numbers are enough

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

Lemma 1.1 · proved

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. ∎

Corollary 1.2 · proved

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.

Section 2Elementary bounds, and the signed-sum structure

Lemma 2.1 · greedy · proved

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.

Lemma 2.2 · intervals · proved

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.

Lemma 2.3 · signed sums · proved

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.

Section 3The first open instance: m4 = 7

Theorem 3.1 · certified

(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.

Engines at k = 4, m = 7. Node counts re-derived by the checker on 20 September 2026 from the committed certificates.
EngineOrganisationNodesCertificate
Afail-first branching, Fourier-Motzkin leaves290certs/A_k4_m7.json, checked
Brow-echelon state, prefix-first branching, exact LP certificates at every node1099no certificate emitted
Cfail-first, certified LP pruning, subspace memoisation111certs/C_k4_m7.json, checked
Ddissociation case split (section 5)62certs/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.

Section 4What follows: f(n) exactly, for n ≤ 27

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.

proved, given Theorem 3.1
f(n) = 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, …, 4   for n = 1, …, 27
and f(n) ≥ ⌊log2 n⌋ for every n ≤ 31, with equality except at n = 14 and 15, where f(n) = 4 > 3
Show
Erdős's guess against the truth. The solid staircase is f(n), evaluated live from f(n) = g(⌈(n−1)/2⌉) with the g values this note establishes; the dashed staircase is ⌊log2 n⌋. They agree everywhere the solid line is drawn except at n = 14 and 15, where f is one larger. Beyond n = 27 the solid line stops and only a lower bound is known: the shaded region is what an exhaustive k = 5 search would settle, and section 5 explains why that search is not finished. Switching to n ≤ 63 shows how much would follow from a single further value, m5.

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.

Section 5The k = 5 threshold, which is not decided here

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.

Curves
How far the thresholds are from the question. Vertical bars are what is known about mk, the least number of positive reals that forces a dissociated k-subset: exact points at k ≤ 4, intervals at k = 5 and 6. F(k) is the Conway-Guy threshold for integer sets with distinct subset sums, a lower bound for mk; the greedy bound (3k−1+1)/2 is the upper bound of Lemma 2.1. Erdős's question asks whether the bars stay below 2k−1. All four are computed from their definitions, with F(7..9) taken from OEIS A276661. The bars are measurements; the two smooth curves are formulas.

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.

Section 6A 24-element set with no dissociated 6-subset

Proposition 6.1 · certified

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.

Section 7Open questions

  1. Is m5 = 14? A completed exhaustive run of engine G, ported to C, decides it. The consequence would be f(n) = 5 for 28 ≤ n ≤ 47 and Erdős's inequality for all n ≤ 63.
  2. Is mk ≤ 2k−1 for all k? This is Erdős's question in the form of Corollary 1.2. The data mk = 1, 2, 4, 7 and 14 ≤ m5 ≤ 41, 25 ≤ m6 ≤ 122 track the Conway-Guy thresholds F(k) = 1, 2, 4, 7, 13, 24 closely, and mk ≥ F(k) always. If mk − F(k) stayed bounded the inequality would hold with room to spare, since F(k)/2k−1 tends to about 0.44. That is an observation about six data points, not a conjecture this note can support.
  3. A human-readable proof of Theorem 3.1(a). Engine D's 62-node tree is the skeleton: split on {a1,a2,a3,a4}; in the dissociated branch every other element is a signed sum of it and the remaining checks are short; in the six relation branches recurse on {a1,a2,a3,a5} or {a2,a3,a5,a6}.
  4. Sharper general bounds. Applying Lemma 2.3 to every dissociated (k−1)-subset of P at once, rather than to one of them, should improve mk ≤ (3k−1+1)/2. We did not find the argument.