Computational research note · Additive combinatorics
Take a handful of different whole numbers, say ten of them. Now list every possible way of adding some of them together, including adding none of them (a total of zero) and adding all ten, and everything in between: that is 210 = 1,024 different totals. A set of numbers has distinct subset sums if none of those 1,024 totals ever comes out the same twice.
The property gets harder to keep as the set grows, and there is a natural question hiding underneath it: how small can you be forced to make the largest number in such a set? Erdős asked exactly this in 1931, for sets of any size n — he later called it perhaps his first serious problem, and put $500 on a full answer. For up to nine numbers, the smallest possible largest element, written f(n), has been known exactly since the 1980s: 1, 2, 4, 7, 13, 24, 44, 84, 161. For ten numbers, f(10), nobody has known the exact value — not for lack of trying, the space of candidate sets is simply too large to search by brute force on ordinary hardware.
Before this session the public record was thin: a working 10-element set with largest element 309 (found by Conway and Guy in 1967, and believed but not proved to be the best possible), and a lower bound of only 220 that any working set had to clear. Anywhere in that 89-number gap was still possible.
Nobody has decided f(10) exactly. This session narrows where it can be.
Everything below is the technical version. Section 4 has the certified floor and what it cost; section 5 has the ruled-out neighborhood; section 6 has the classical bound.
Let f(n) be the least possible largest element of a set of n positive integers all of whose 2n subset sums are distinct (OEIS A276661 (secondary)). Exact values were previously known for n ≤ 9 (secondary); for n = 10 the Conway–Guy construction gives f(10) ≤ 309, conjectured sharp, and the literature recorded f(10) > 220 (secondary). This note (i) re-derives f(1..9) = 1, 2, 4, 7, 13, 24, 44, 84, 161 from scratch with three mutually node-count-verifying implementations plus an independent Python reference, enumerating all optimal sets at every level; (ii) pushes the certified frontier to f(10) > 262 — 102 exhausted maxima m = 161..262, 166,893,497,453 search-tree nodes in 2.87 hours of 4-thread wall time — by exhaustive branch-and-bound over every possible maximum m; (iii) rules out every witness below 309 whose deficiency profile lies within L1-distance 8 of the Conway–Guy profile (19,125,539 candidate sets, checked exactly); (iv) proves, by a classical second-moment argument, f(10) ≥ 192 and f(11) ≥ 362; and (v) records the empirical growth law of the search tree (×1.20 per unit of m in the probed range, easing to ×1.14 near the certified frontier), which prices the full a(10) decision at CPU-months on commodity hardware and motivates a sketched multi-m engine as the natural next step.
Let S = {a1 < … < an} be a set of positive integers.
S has distinct subset sums (DSS) if the map A ↦ Σi∈A ai is injective on the 2n subsets of S. Write f(n) for the least possible value of max S over all n-element DSS sets.
Erdős asked (1931; problem #1 of the Erdős problems database, $500 (secondary)) whether max S ≥ c·2n for an absolute constant c > 0. The powers of two {1,2,4,…,2n−1} give f(n) ≤ 2n−1 trivially; Conway and Guy (1967) constructed sets with a smaller maximum, and Bohman (1996) proved every set in their recursive sequence is DSS, with the best known asymptotic upper bound f(n) ≤ 0.22002·2n. In the other direction, the second-moment method of Erdős and Moser gives f(n) ≥ c′·2n/√n, with the record constant √(2/π) due to Elkies and Gleason (unpublished; re-proved by Dubroff–Fox–Xu 2021 and Steinerberger 2023). All statements in this paragraph are (secondary): the research sandbox that produced this note had no access to any primary source (arXiv, OEIS, erdosproblems.com and MathOverflow were all unreachable), so every literature claim here rests on search-engine snippets retrieved 2026-08-13, not on a read primary page.
The known exact values, OEIS A276661 (secondary): f(1..9) = 1, 2, 4, 7, 13, 24, 44, 84, 161, due to Lunnon (1988, exhaustive for n ≤ 8) and J. P. Grossman (n = 9; his optimal set coincides with the 9-element Conway–Guy set) (secondary). Nothing below depends on any of these secondary facts except where explicitly noted: every certified result in this note is re-derived independently, and the published values enter only as targets to be matched, never as inputs to a proof.
Fix n and a candidate maximum m. Sweeping m upward from f(n−1) and testing each value exhaustively, the first m admitting a DSS set is f(n) by definition. Running this sweep for n = 2..9, independently of any published value:
For n = 2..9, exhaustive search over every possible maximum m proves f(n) = 2, 4, 7, 13, 24, 44, 84, 161 respectively, and the complete list of optimal sets (those attaining max S = f(n)) is exactly as recorded in data/optimal_sets.txt. This re-derives the known ladder without assuming it: OEIS values enter only as assertions to be matched, and, for pruning, as floors on earlier, already-decided levels (§3).
| n | f(n) | optimal sets | note |
|---|---|---|---|
| 2 | 2 | 1 | |
| 3 | 4 | 2 | |
| 4 | 7 | 1 | |
| 5 | 13 | 2 | |
| 6 | 24 | 1 | |
| 7 | 44 | 1 | |
| 8 | 84 | 3 | two of the three are not of Conway–Guy shape |
| 9 | 161 | 1 | unique optimum, equals Grossman's / the 9-element Conway–Guy set |
Whether these multiplicities were previously published is unknown to this session (Lunnon's paper was unreachable); they are possibly known for n ≤ 8. The n = 9 uniqueness may be new — Grossman's value is an OEIS credit line, not a paper.
The engine builds candidate sets in strictly decreasing order an = m > an−1 > … > a1 ≥ 1, maintaining for the chosen suffix T either the bitset of its achievable subset sums (engine v2) or, equivalently, the set D(T) of pairwise differences of achievable sums (engine v3). A run at (n, m) reports FOUND with every solution, or NONE with exact per-depth node counts.
Adding a new smallest element a to suffix T preserves DSS iff no achievable sum of T plus a equals another achievable sum of T, i.e. iff sums(T) ∩ (sums(T) + a) = ∅, i.e. iff a ∉ D(T). Any collision in a completed set is therefore detected at the moment its largest-index differing element is added, so a leaf is reported iff the full set is DSS. (Induction on the suffix; both engine representations implement the identical test.)
Three exact, integer-only prunes cut the tree without ever excluding a completable branch, because each is a necessary condition on any completion: P1 (position floor) — the bottom r elements of a DSS set form an r-element DSS set, so the next element chosen must be ≥ f(r), consulting only already-decided, smaller levels; P2 (sum) — the 2n distinct subset sums live in [0, Σai], forcing Σai ≥ 2n − 1; P3 (second moment) — Lemma 4 below, applied to the achievable remainder at each node. A NONE run traverses the entire pruned tree, so its node counts are deterministic and comparable across implementations and thread schedules; FOUND runs are re-run in full-traversal mode before being compared, for the same reason.
Four implementations of the identical search tree: v2 (dss_search.c), its pre-optimization snapshot (dss_search_basic.c), v3 (dss_search3.c, a 4.1× faster difference-set representation, same tree in default mode), and an independent Python reference (dss_reference.py) — plus a zero-cleverness brute validator (validate_set.py) with positive controls (every known optimal set n = 4..9, the Conway–Guy 10-set, the Conway–Guy recurrence itself) and negative controls. All equality checks passed: v2 ≡ basic on 42 full-traversal cases; v2 ≡ v3-default on the same 42 cases plus n = 9 at m ∈ {150, 155} (429,697,049 and 769,328,147 nodes, identical per-depth profiles); v2 ≡ the Python reference, exhaustively for n ≤ 7 and on enumeration runs; every reported solution independently re-validated by brute enumeration; every f(n) checked against A276661. No floating point exists in any engine's search-critical path; all arithmetic is 64-bit integer with magnitudes bounded by 3·(nm)² < 263.
No 10-element DSS set has largest element ≤ 262. Hence f(10) > 262. Combined with the validated Conway–Guy witness (Theorem 3(i)), 262 < f(10) ≤ 309. Every row of data/n10_sweep.csv with status NONE is an independent statement of this form for its own m; the theorem is the union of the contiguous cleared prefix m = 161..262.
Hardware and cost: 4 shared cloud cores, 15 GB RAM, gcc 13.3 (-O3 -march=native -fopenmp). The certified sweep above is 102 independently-timed rows; summed wall time is 2.87 hours. The full ladder of section 2, including every enumeration re-run and the Python cross-checks, took an additional 2,991 seconds.
(i) The Conway–Guy 10-set {148, 225, 265, 285, 296, 302, 305, 307, 308, 309} is DSS, verified by brute enumeration of all 1,024 sums; hence f(10) ≤ 309.
(ii) Writing a 10-set with maximum m as {m−d9, …, m−d1, m} with deficiencies 0 < d1 < … < d9 < m, there is no DSS set with m ≤ 308 whose deficiency vector d satisfies Σi|di − ui| ≤ 8, where u = (1, 2, 4, 7, 13, 24, 44, 84, 161) is the Conway–Guy deficiency profile — which is, not coincidentally, exactly the ladder of section 2. 19,125,539 candidate sets were checked exactly.
Every n-element DSS set satisfies Σai2 ≥ (4n − 1)/3. Consequently f(10) ≥ 192 and f(11) ≥ 362.
Proof. For ε ∈ {−1,+1}n uniform, let X = Σεiai. The map A ↦ ε(A) (sign +1 exactly on A) is a bijection from subsets to sign vectors, and X(A) = 2·SA − Σai, so the DSS property forces the 2n values of X to be pairwise distinct. They are also all congruent to Σai (mod 2), and the value multiset is symmetric under negation, so E[X] = 0 and, by independence of the εi, E[X2] = Σai2. Writing each value as 2y + c with c the common parity bit, the y-values are N = 2n distinct integers and E[X2] = Var(X) = 4·Var(y). Among N distinct integers the variance is minimized by N consecutive integers — an exchange argument: if the sorted values contain a gap > 1, shrinking it moves the two blocks it separates closer to the common mean and strictly decreases the sum of squared deviations — and Var({0,…,N−1}) = (N2−1)/12. Hence Σai2 ≥ 4(N2−1)/12 = (4n−1)/3.
For n = 10: the ten elements are distinct and at most m, so Σai2 ≤ Σj=09(m−j)2 = 10m2 − 90m + 285, and 10m2 − 90m + 285 ≥ 349,525 forces m ≥ 192 (root ≈ 191.44). For n = 11: 11m2 − 110m + 385 ≥ (411−1)/3 = 1,398,101 forces m ≥ 362 (root ≈ 361.5). ∎
The bound f(10) ≥ 192 is strictly weaker than Theorem 2 (262 > 192) and is stated for two reasons: the search engine itself uses it as an exact prune (P3, section 3), and its n = 11 instance is the current analytic floor for the next open value once f(10) closes — Conway–Guy gives f(11) ≤ 594, so f(11) ∈ [362, 594] today.
Tree growth (NUMERICAL, a fit, not a theorem). Between m = 230 and m = 250 the tight-mode tree grows ×40.4 over 20 steps of m, i.e. ×1.203 per unit, fitted on that range only. Over the later certified stretch m = 250..262 the measured rate eased to ×1.138 per unit (21.2 billion nodes at m = 262 alone). Even at the gentler rate, the remaining range to 308 costs on the order of 102.6 ≈ 400× the m = 262 instance — CPU-months on this hardware. This is what prices the full a(10) decision and motivates the multi-m engine sketched in section 8.
A documented negative result. Simulated annealing over 10-sets (uniform and local ±δ moves, exact collision-count energy) stalls at energy 3–5 across dozens of restarts and cannot rediscover any DSS set, even with the cap fixed at 309, where the Conway–Guy witness is known to exist — the annealer fails its own positive control. Near-optimal DSS sets appear to be isolated points of the move graph: changing one element at a time almost always breaks more collision-freedom constraints than it fixes. No heuristic evidence about whether f(10) < 309 can be extracted this way, and none is claimed; this is why section 5 replaces a heuristic witness search with an exhaustive one over a bounded neighborhood instead.