Numbers whose subset sums all differ

A set of weights is to be used on a balance with only one pan, and every subset of the weights must give a different total, so that the total on the pan identifies which weights are there. The powers of two do it perfectly: weights of 1, 2, 4, 8, 16, 32 and 64 grams give every total from 0 to 127 exactly once, because the totals are the numbers written in binary. Seven weights, largest 64.

Can the largest weight be smaller? It can. The seven weights 20, 31, 37, 40, 42, 43 and 44 also give 128 different totals, now spread between 0 and 257 with gaps between them, and their largest member is only 44. Paul Erdős asked in the 1930s how small the largest member of $n$ numbers with distinct subset sums can be, and he believed that the answer is never much smaller than for the powers of two — that it is always at least some fixed fraction of $2^n$. He offered five hundred dollars for a proof or a disproof, and the question is still open.

The question is a natural test of the pigeonhole principle, because the first lower bound is a pigeonhole and the whole difficulty of the problem is in how much more than a pigeonhole is needed. This essay follows the bounds upward, from counting boxes to counting where the sums crowd, and the constructions downward, from the powers of two to a recipe of John Conway and Richard Guy, and finds the true answer for small sets by exhaustive search.

The pigeonhole bound #

Let the numbers be $a_1 < a_2 < \cdots < a_n$, all positive whole numbers, with largest member $M = a_n$. There are $2^n$ subsets, counting the empty one, and every subset sum is a whole number between 0 and the total, which is at most $nM$. If all the sums are different, $2^n$ different whole numbers lie in an interval containing $nM + 1$ of them, so

$$nM + 1 \ge 2^n, \qquad M \ge \frac{2^n - 1}{n}.$$

That is the pigeonhole: the subsets are the pigeons, the possible sums the boxes. For seven numbers it gives $M \ge 18.1$, so $M \ge 19$, against the true value of 44. For a hundred numbers it says $M$ is at least about $1.27 \times 10^{28}$, while the powers of two use $2^{99} \approx 6.3 \times 10^{29}$. The bound captures the exponential growth, which is the main fact, and loses a factor of $n$, which is the whole question.

Read the other way, the same count is a theorem about every set of numbers. Any ten whole numbers from 1 to 100 add to at most 955, so their 1,024 subsets have at most 956 possible totals, and two subsets must share a total. If the two share some members, remove those from both; the totals stay equal, and what is left is two disjoint groups with the same sum. The figure does this for ten numbers drawn at random. Their total is 654, so there are at most 655 possible sums for 1,024 subsets. The first coinciding pair found, with the common members removed, is 11 + 12 + 54 on one side and 77 on the other.

The argument proves that such groups exist and gives no way of finding them except by looking. That is typical of the pigeonhole principle, and it is the same weakness that limited it in the lonely runner problem: it uses only the total size of the boxes and nothing about how the pigeons are distributed among them. Here the sums are not distributed evenly at all, and that is the first thing a better bound can use.

Subset sums of a small set of numbers turn up in places that have nothing to do with weighing. In a weighted vote, a member’s power depends on which coalitions its votes can turn from losing into winning, and that is a question about which subset sums of the other members’ weights fall just below the quota — the reason Luxembourg’s vote was worth nothing for fifteen years. Numbers whose subset sums cover a whole range, rather than avoid each other, are the subject of divisors that make every amount. The distinct-sums condition is the opposite extreme: not every total reachable, but no total reachable twice, so that the sum remembers which numbers made it.

That memory is what costs room. The powers of two pay for it in the most wasteful way possible, leaving no gaps at all but spending a factor of two at every step; the question is how much of that waste is necessary. The pigeonhole says the saving over the powers of two can never be more than a factor of about $n/2$; Erdős’s question is whether it can be more than a constant factor at all.

Where the sums crowd #

Choose a subset at random, each number included independently with probability one half. Its sum is a random variable whose average is half the total, and whose variance is

$$\sigma^2 = \sum_{i=1}^n \frac{a_i^2}{4} \le \frac{n M^2}{4},$$

since each number contributes either 0 or $a_i$ with equal chances, a variance of $a_i^2/4$, and independent variances add. So the standard deviation is at most $\tfrac12\sqrt n\, M$. That is much less than the full range $nM$: the sums are concentrated in the middle, as sums of many independent pieces always are.

Chebyshev’s inequality says that at least three quarters of the probability lies within two standard deviations of the mean, whatever the distribution. Each subset has probability $2^{-n}$, so at least $\tfrac34 \cdot 2^n$ of the subset sums lie in an interval of width $4\sigma \le 2\sqrt n\, M$. Now apply the pigeonhole to that interval alone: it contains at most $2\sqrt n\, M + 1$ whole numbers, and if the sums are distinct it must contain at least $\tfrac34 \cdot 2^n$ of them. So

$$M \ge \frac{3 \cdot 2^n - 4}{8 \sqrt n},$$

and the loss has shrunk from a factor of $n$ to a factor of $\sqrt n$. Erdős and Leo Moser found this argument in the 1950s, and the figure shows it at work on a set of twelve numbers with distinct sums: of its 4,096 sums, 3,918 lie in the shaded band, far more than the three quarters Chebyshev guarantees, because the sums of a set like this are close to the bell curve that the central limit theorem predicts.

The improvement is real and it is also the end of what concentration alone can do. A tighter estimate of how much probability lies near the mean improves the constant in front, and a long line of work — by Noam Elkies, by Aliev, and by others — did exactly that. But the factor $\sqrt n$ is the width of the bell, and nothing about the bell can remove it.

The widest layer #

The best lower bound known, proved by Quentin Dubroff, Jacob Fox and Max Wenqiang Xu in 2021, is strikingly clean:

$$M \ge \binom{n}{\lfloor n/2 \rfloor}.$$

The middle binomial coefficient is the widest layer of subsets, the number of subsets of exactly half the size, and it is about $2^n \sqrt{2/(\pi n)}$, the same order as the variance bound with a better constant. The proof uses a theorem of Lawrence Harper about the vertices of a cube: among all ways of choosing a fixed number of corners of an $n$-dimensional cube, the choice with the fewest neighbours outside it is a ball around one corner. Translated into sums, it shows that the subset sums cannot all be squeezed into a short interval without many of them colliding, and the count of how many must collide is a binomial coefficient.

The figure puts all the bounds on one scale by dividing by $2^n$. On that scale a bound that grows like a constant times $2^n$ is a level line, and Erdős’s conjecture says that the true values form a line that stays above some positive level for ever. The pigeonhole bound falls like $1/n$. The variance bound and the binomial bound both fall like $1/\sqrt n$, the binomial one higher. Every lower bound anybody has proved falls to nought on this scale. The constructions, at the top, fall much more slowly — and whether they eventually level off or keep falling is exactly what nobody knows.

The truth for small sets #

For a handful of numbers the least possible largest member can be found exactly, by searching. Choose the numbers from the largest down. Keep, as a list of bits, every sum the chosen numbers already make; a new number $a$ is allowed only if shifting that list by $a$ creates no overlap, since an overlap is two subsets with the same sum. Two observations prune the search hard. The numbers still to be chosen are smaller than the last one, and they must have distinct subset sums among themselves; so $r$ of them must add to at least $2^r - 1$, by the pigeonhole bound applied to them alone, and if the largest $r$ numbers still available cannot reach that total, the branch is abandoned.

Run with the cap one below the answer, the search finds nothing; run at the answer, it lists every set there is. The least largest members for three to seven numbers are 4, 7, 13, 24 and 44. For four, six and seven numbers the optimal set is unique — $\{3, 5, 6, 7\}$, $\{11, 17, 20, 22, 23, 24\}$ and $\{20, 31, 37, 40, 42, 43, 44\}$ — and for three and for five there are two each, $\{1, 2, 4\}$ and $\{2, 3, 4\}$, and $\{3, 6, 11, 12, 13\}$ and $\{6, 9, 11, 12, 13\}$. Proving that 43 does not suffice for seven numbers takes about half a million partial sets.

The search grows explosively, by roughly a factor of fifty with each extra number at this size, and for eight and nine numbers the least values, 84 and 161, were established by searches of the same kind, starting with Fred Lunnon’s in 1988. Beyond nine the exact values are not known.

What the optimal sets look like is the useful information. They are nothing like the powers of two. Their members bunch together near the top: the seven-number optimum has four members within four of 44, and its smallest member, 20, is almost half the largest. The sums still manage to differ because the members differ from each other in a carefully arranged way, and the arrangement has a pattern.

A recipe from differences #

The pattern was found by John Conway and Richard Guy in 1968. Define a sequence by $u_0 = 0$, $u_1 = 1$ and

$$u_{n+1} = 2u_n - u_{n-r}, \qquad r = \operatorname{round}\big(\sqrt{2n}\big),$$

so that each term is twice the last minus a term a few places back, the distance back growing slowly. The sequence runs 0, 1, 2, 4, 7, 13, 24, 44, 84, 161. Then take the $n$-th term and subtract each earlier one: the $n$ numbers $u_n - u_0, u_n - u_1, \ldots, u_n - u_{n-1}$ are the Conway–Guy set of size $n$.

For seven numbers the recipe gives $44 - \{0, 1, 2, 4, 7, 13, 24\}$, which is exactly the optimal set $\{20, 31, 37, 40, 42, 43, 44\}$, and for every size where the least value is known, it is attained by the Conway–Guy set. The figure checks distinct sums for every size up to 18 by building each set’s sums one member at a time and confirming that no sum is ever reached twice; at 18 numbers the largest member is 68,008, which is $0.259 \times 2^{18}$, against $\tfrac12 \times 2^{18}$ for the powers of two.

Two things about the recipe are open. Nobody has proved that the Conway–Guy sets have distinct sums for every $n$; it has been checked by computer much further than here, and it is the construction that every table quotes, but a proof is missing. And the ratio to $2^n$, still falling at 18, is believed to level off near 0.22, which would make the best known upper constant about 0.22. Tom Bohman found a modification in 1998 that does slightly better, and nobody has found sets that do essentially better than a constant times $2^n$ — which is consistent with Erdős’s conjecture and is not evidence for it of any strength.

Why a pigeonhole cannot finish the job #

The surprising connection here is with the problem of weighing coins. A collection of $n$ coins, some of them counterfeit and one gram light, is to be sorted by weighing chosen subsets of coins together on a scale that reports the total; how few weighings identify every counterfeit? Each weighing gives a whole number from 0 to $n$, so $m$ weighings give at most $(n + 1)^m$ outcomes, and there are $2^n$ possible sets of counterfeits. The pigeonhole says $m \ge n/\log_2(n + 1)$. The true answer, found by Alfréd Rényi and Erdős and matched by constructions of Bernt Lindström and of David Cantor and W. H. Mills in the 1960s, is about $2n/\log_2 n$ — twice the pigeonhole count, and the factor of two comes from exactly the argument above: the total weight of a random subset concentrates within $\sqrt n$ of its middle, so each weighing has effectively only about $\sqrt n$ likely outcomes rather than $n$.

In the coin problem, that concentration argument is the end of the story; the constructions meet it. In the distinct-sums problem it is not, and the difference is instructive. Weighing coins asks for many weighings each with few outcomes; distinct sums asks for one weighing with enormously many outcomes, and the question is how tightly those outcomes can be packed.

That is why the pigeonhole cannot finish it. Every proof so far bounds $M$ by counting how many sums can be packed near the middle of their range, and every one loses at least the width of the bell curve, $\sqrt n$, because the sums of a random subset genuinely do spread over a width of $\sqrt n\, M$ and not $M$. Proving Erdős’s conjecture would mean showing that distinct sums cannot be packed even into a bell-shaped region of that width without the largest member being of order $2^n$ — an argument about the arithmetic of the numbers, not about how many sums there are. The same thing happened in the sum that forbids half the pairings, where a parity count rules out half the cases and is silent about the rest, and in two numbers approximated at once, where a pigeonhole gives the right exponent and leaves the constant for harder work.

One weakening of the condition changes nothing, which is worth knowing. If the requirement is only that no two disjoint subsets have equal sums, the problem is the same, because two subsets with equal sums can always have their common members removed, as the figure of random numbers showed. The difficulty is in the exponential count of subsets itself, and in the arithmetic needed to keep that many sums apart in a space only a constant factor larger than strictly necessary.

Eighteen numbers say nothing about infinity #

The figures cover at most 18 numbers. The bounds and constructions are drawn up to there, the exact values only up to seven, and the open question is entirely about what happens as $n$ grows without bound. A curve that is still falling at $n = 18$ might level off, or it might keep falling like $1/\log n$ or like $n^{-0.01}$, and no finite picture can tell those apart. The belief that the Conway–Guy ratio levels off near 0.22 comes from analysing the recipe, not from the figure.

The random example shows one set of ten numbers; that every set of ten numbers up to 100 has two equal-sum groups is the pigeonhole theorem, not the picture. And the histogram of sums shows a set that happens to have distinct sums; it illustrates where the variance argument gets its leverage, not that the sums of every such set are bell-shaped.

Searched to seven, quoted beyond #

Computed here: the 128 sums of the optimal seven-number set; the random ten-number set and its first coinciding pair; the 4,096 sums of the twelve-number Conway–Guy set and the 3,918 of them within two standard deviations; the exhaustive search for three to seven numbers, including the proof that nothing smaller works and the complete list of optimal sets; the Conway–Guy sets up to 18 numbers, each checked to have distinct sums; and the curves of the three lower bounds.

Quoted: Erdős’s question and prize; the Erdős–Moser variance argument, re-derived here in its simplest form; the theorem of Dubroff, Fox and Xu and its use of Harper’s inequality; the improvements of the constant by Elkies, Aliev and others; Lunnon’s computation of the values for eight numbers and the later confirmation of 161 for nine; the Conway–Guy recipe; and Bohman’s modification.

Still open: a constant times two to the n #

Is there a constant $c > 0$ such that $n$ positive whole numbers with distinct subset sums always have a largest member of at least $c \cdot 2^n$? Every lower bound proved so far is of order $2^n/\sqrt n$, and the best constructions are of order $0.22 \times 2^n$. Closing that gap in either direction would be news: a lower bound of $2^n/n^{0.49}$ would need a genuinely new idea, and a construction of order $2^n/\log n$ would refute the conjecture outright.

Two smaller questions are open beside it. Do the Conway–Guy sets have distinct subset sums for every size? They do for every size anyone has checked. And what is the least largest member for ten numbers? The Conway–Guy value is 309, and it is not known whether something smaller exists; the search that settled nine numbers grows too fast to be pushed much further without a better way of pruning it.

A factor of root n #

A pigeonhole on the sums shows that $n$ numbers with distinct subset sums need a largest member of at least $(2^n - 1)/n$; counting where the sums crowd improves that to about $2^n/\sqrt n$; and the best sets known, found by a recipe of Conway and Guy, need about $0.22 \times 2^n$. For seven or fewer numbers an exhaustive search finds the true least values, 4, 7, 13, 24 and 44 for three to seven, and the recipe attains every one.

The gap that remains is a factor of $\sqrt n$, and it is not an accident of technique. It is the width of the bell curve that the subset sums of any set form, and every argument that counts sums in an interval pays it. The pigeonhole principle gives the exponential growth at once, which is most of the truth; the rest is a question about arithmetic that counting does not see.