Fabian Arevalo

Computational research note · Additive combinatorics

A new certified floor for Erdős's distinct subset sums problem

Four cross-verified search engines push the tenth value of Erdős's distinct-subset-sums function past the recorded floor of 220 to a certified 262, narrowing f(10) to the window (262, 309]; the known ladder f(1)…f(9) is re-derived from scratch with every optimal set enumerated, and 19.1 million candidates near the best known construction are ruled out as a smaller witness.
August 13, 2026 · produced in a Claude Code research session, merged and published the same day.
Code, data & certificates in the companion repository.

Start here: no maths required

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.

Hover or tap a point.
Every exact value up to n = 9, and where n = 10 now stands. The dots are certified exact values, re-derived from scratch in this session. At n = 10 the black bar is the window this session narrows the truth to: more than 262 (proved here), at most 309 (Conway–Guy's construction). The faded dot marks the previous public floor of 220 — superseded, not wrong.

What this note adds

Nobody has decided f(10) exactly. This session narrows where it can be.

  1. A new certified floor: f(10) > 262. An exhaustive, four-times-cross-checked search proves no 10-element set with all subset sums distinct has largest element 262 or smaller. That shrinks the 89-number gap between the old floor (220) and Conway–Guy's construction (309) down to 47.
  2. The whole known ladder, rebuilt from nothing. f(1) through f(9) were re-derived assuming none of the published values, and for the first time (as far as this session could check) every equally-good solution at each size was counted, not just one example: most sizes have exactly one best set, but size 8 has three and size 5 has two.
  3. 19.1 million near-best candidates, all ruled out. Every 10-element set close in shape to Conway and Guy's, up to their same maximum of 309, was checked exactly. None works. If a better set exists, it is not a small tweak of the known one.
  4. A classical lower bound, written out in full. A short counting argument — not new, but not previously stated for this exact problem here — proves by pure algebra, no search required, that f(10) cannot be below 192, and the next open value, f(11), cannot be below 362.
  5. A documented dead end. A standard optimization shortcut (simulated annealing) was tried as a fast route to a smaller 10-element set, and it completely failed to find one, even when told where a valid example was known to sit. Recorded so the next attempt does not repeat it.

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.

AbstractSummary of results

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.

Section 1The problem, and what was known

Let S = {a1 < … < an} be a set of positive integers.

Definition · distinct subset sums

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.

Section 2The ladder, re-derived from scratch

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:

Theorem 1 · the ladder (CERTIFIED)

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

nf(n)optimal setsnote
221
342
471
5132
6241
7441
8843two of the three are not of Conway–Guy shape
91611unique 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.

Section 3The search engine, and why it is exhaustive

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.

Completeness of the collision test

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.

Verification architecture

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.

Section 4The a(10) frontier: f(10) > 262

Theorem 2 · the frontier (CERTIFIED)

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.

Hover or tap the curve.
What each +1 on the maximum costs. The solid line is measured: exact node counts from every one of the 102 exhausted values of m. The dashed line is a model, not data: the growth rate fitted only over m ∈ [230, 250] (×1.203 per unit), extrapolated forward. By m = 262 the flat extrapolation over-predicts by about 1.9× (41 billion projected vs. 21 billion measured) — growth measurably eased to ×1.138 per unit over the certified stretch itself. Even at the gentler rate, the remaining climb to 308 is priced at roughly 400× the m = 262 instance: CPU-months on this hardware, the reason §6 of the companion note sketches a different engine rather than just running longer.

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.

Section 5The witness side: how far a smaller set could hide

Theorem 3 · the witness side (CERTIFIED)

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

Where a smaller 10-element set cannot be hiding. Horizontal axis: the candidate maximum m, 161 to 309. Vertical axis: how far a set's deficiency profile sits from Conway–Guy's, by the L1 distance of Theorem 3(ii) (schematic, not to scale above 8). The solid block is section 4's exhaustive result: every shape is excluded up to m = 262. The hatched band is this section's result: every m up to 308 is excluded within distance 8 of Conway–Guy's own profile, independent of the exhaustive sweep. Only the small region at top right — larger m, and a shape unlike Conway–Guy's — is still open. If a better-than-Conway–Guy set exists, it is neither small nor a tweak of Conway–Guy.

Section 6A classical floor, by counting alone

Lemma 4 · second-moment floor (PROVED, classical method)

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.

Section 7What is not yet certified

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.

Section 8Open threads

  1. Finish a(10). The sweep is resume-safe: every completed m is a permanent certified row, and future sessions can continue directly from m = 263. Projected completion at the current rate needs roughly 103 core-hours, or the engine below.
  2. A multi-m deficiency engine (sketch, unimplemented). Parametrize sets by deficiency vector d = (m−ai) instead of by absolute value. Collisions between subsets of equal cardinality impose conditions on d alone, independent of m; a collision between subsets whose cardinalities differ by k ≥ 1 excludes exactly one value of m for that deficiency difference. One tree over d, with a per-node interval of still-alive m values (clipped by the monotone P2/P3 inequalities) and finite exclusion lists, would replace roughly 150 separate per-m trees with one. Projected 5–10× over the current approach.
  3. f(11) once f(10) closes. The same machinery applies with f(10) as the new position-floor prune; the analytic window is already [362, 594] (section 6, Conway–Guy).
  4. The multiplicity question. The optimal set is unique at n = 4, 6, 7, 9 but not at n = 3, 5, 8 (counts 2, 2, 3). Is there structure predicting which n admit non-Conway–Guy optima? What is the multiplicity at n = 10, once it is decided?