More Sums Than Differences

Take a finite set of integers $A$. Form every sum $a + b$ with $a$ and $b$ drawn from $A$, and every difference $a - b$. Throw away repeats and you have two new sets, $A+A$ and $A-A$.

Addition commutes and subtraction does not. $3+5$ and $5+3$ are one sum, while $5-3$ and $3-5$ are two different differences. A set with $k$ elements can produce at most $k(k+1)/2$ distinct sums but up to $k(k-1)+1$ distinct differences, close to twice as many. The safe bet is that $A-A$ is always at least as large as $A+A$.

The bet loses. The set $\{0, 2, 3, 4, 7, 11, 12, 14\}$ has 26 distinct sums and 25 distinct differences.

Sets like that are called MSTD sets, for more sums than differences. In 2006 Melvyn Nathanson wrote that they “should be rare”. Within months Greg Martin and Kevin O’Bryant proved that they are not: a fixed positive fraction of all subsets of $\{0, 1, \dots, n-1\}$ are MSTD, however large $n$ gets. The fraction is small, roughly one set in 2,200. It never goes to zero.

I wanted to see how that fraction behaves on its way to its limit, so I wrote a simulator and put about 55 billion random sets through it, on top of an exhaustive count of every subset up to $n = 36$. The published plots show a steady climb toward the limit. Followed further, the climb overshoots: the fraction crosses its limit near $n = 35$, peaks around $n = 45$, and comes back down from above. I have not found this reported in the literature on these sets, and the mechanism behind it involves Fibonacci numbers.

Conway’s set

Figure 1. Of the 29 values a sum could take, 0 to 28, three are missing. Of the 29 values a difference could take, −14 to 14, four are missing. 26 beats 25.

The example is usually credited to John Conway, though nobody seems sure when. Peter Hegarty describes the question as “of murky origins, but dating back to the 1960s”. The first MSTD sets in print are a nine-element example in a 1969 note by John Marica, titled “On a conjecture of Conway”, and a seventeen-element one by Freiman and Pigarev in 1973. Hegarty proved in 2007 that eight elements is the minimum, and that Conway’s set is the only eight-element MSTD set up to shifting, scaling and reflecting. His proof leaned on a computer search. A computer-free proof for seven elements appeared this September.

Look at where the missing values sit. The missing sums are 1, 20 and 27: one step in from the bottom of the range, and one and eight steps in from the top. The missing differences are ±13 and ±6, one and eight steps in from either end. Nothing near the middle is missing.

Where the counting goes wrong

The $k(k+1)/2$ against $k(k-1)+1$ count is about how many values could appear. Now take a random subset of $\{0, \dots, n-1\}$ instead, flipping a fair coin for each number. It has about $n/2$ elements and about $n^2/8$ pairs, but its sums can only land on the $2n-1$ values from $0$ to $2n-2$. A sum near the middle of that range can be formed in about $n/8$ ways on average. For a set drawn from $\{0, \dots, 999\}$ that is more than a hundred ways, so the middle of $A+A$ is essentially always full. The same holds for differences near zero.

So $A+A$ and $A-A$ each have exactly $2n-1$ possible values, and each comes close to filling them. The contest is decided by which one has fewer gaps, and the gaps live near the edges.

Two strings of coin flips

That observation becomes an exact model. Read the bottom of the set as a string of bits, $X_i = 1$ when $i \in A$. Read the top downwards, $Y_i = 1$ when $n-1-i \in A$. Then:

• A sum $j$ near the bottom can only use elements up to $j$, so it is missing exactly when position $j$ is missing from $X+X$.
• A sum near the top is missing exactly when the matching position is missing from $Y+Y$.
• A difference near the maximum, $n-1-j$, needs an element $i$ near the bottom and an element $n-1-(j-i)$ near the top. It is missing exactly when position $j$ is missing from $X+Y$, and its negative goes missing with it.

As $n$ grows, $X$ and $Y$ behave like two independent strings of fair coin flips, and the middle stops mattering. Writing $m(\cdot)$ for the number of positions a sumset misses,

A question about a random set with a million elements has become a question about two short random bit strings. In practice 128 bits per end is plenty, because a sum that far from the edge goes missing with probability around $10^{-8}$. Conway’s set fits the pattern: its bottom string misses one sum, its top string misses two, and the two together miss two cross sums, which cost the set four differences. Three against four.

The model also gives the averages. A sum at distance $j$ from the edge can be built from about $j/2$ unordered pairs $\{i, j-i\}$, each present with probability $1/4$, plus the pair $j/2 + j/2$ when $j$ is even, present with probability $1/2$. A difference at the same distance from its edge can be built from $j+1$ ordered pairs, each present with probability $1/4$. Adding up the chances of being missing, for sums

and for differences

Figure 2. The chance that a value at a given distance from the edge of a long random set is missing. Differences are more fragile right at the edge, but sums have the longer tail. Summed over every distance, about 5 sums and 3 differences go missing per edge.

Two edges, so on average a large random set misses 10 sums and 6 differences. Martin and O’Bryant proved these limits, and Lazarev, Miller and O’Bryant later showed the expected size of $A+A$ is $2n - 11 + O\big((3/4)^{n/2}\big)$. The commutativity intuition does survive, at the edges: near an edge a sum has about half as many ways to be made as a difference, because $\{i, j-i\}$ and $\{j-i, i\}$ are the same pair. It buys differences an average lead of four values, not a factor of two.

A lead of four is small next to the spread. The number of missing sums has a variance of about 36, a standard deviation of six. What keeps MSTD sets rare is that missing sums and missing differences come from the same two strings and rise and fall together. In $10^{10}$ samples of the model the two counts have a correlation of 0.88, so the gap between them has a standard deviation of only 2.9, against the 7.7 it would have if they were independent. The sets that do win mostly win narrowly: 84% of MSTD sets have exactly one more sum than difference, as Conway’s set does, and fewer than one in 500 wins by three or more. On average they miss 5.6 sums instead of 10, and 6.7 differences instead of 6. To win, a set needs ends that are dense exactly where sums need them and gappy exactly where differences need them, and few coin-flip strings manage that.

How many there are

Martin and O’Bryant proved the MSTD fraction stays above $2 \times 10^{-7}$ for every $n \ge 15$. Yufei Zhao proved in 2011 that it converges to a limit $\rho$ and that $\rho > 4.28 \times 10^{-4}$, from a computation that took about a week. His upper bound, which he called “rather disappointing”, is 0.43. Monte Carlo estimates have put $\rho$ near $4.5 \times 10^{-4}$. Exact counts exist up to $n = 45$ (OEIS A222807): 16,326,307,392 of the $2^{45}$ subsets of $\{0, \dots, 44\}$ are MSTD, a fraction of $4.640 \times 10^{-4}$.

The published picture of how the fraction gets to its limit is a steady climb. Martin and O’Bryant plotted it up to $n = 27$ and noted that “each graph is monotonic in n”. A 2015 paper on higher-dimensional versions asks whether these proportions grow monotonically “as computations suggest” for the one-dimensional case. Zhao listed the question as open: how fast does the fraction converge, and does it approach its limit from above or from below?

What I ran

The core operation is cheap with bitsets. Store the set as a bitmask. Then $A+A$ is the union of the shifted copies $A+i$ over the elements $i$, and the non-negative half of $A-A$ is the union of $A-i$.

// sumsAndDiffs returns |A+A| and |A-A| for a nonempty set A of
// integers in [0, 64), stored as a bitmask (bit i set means i is in A).
func sumsAndDiffs(a uint64) (sums, diffs int) {
	var lo, hi, pos uint64 // A+A as a 128-bit mask, and the non-negative half of A-A
	for w := a; w != 0; w &= w - 1 {
		i := bits.TrailingZeros64(w) // i is an element of A
		lo |= a << i                 // add the translate A+i
		if i > 0 {
			hi |= a >> (64 - i)
		}
		pos |= a >> i // differences b-i with b >= i
	}
	sums = bits.OnesCount64(lo) + bits.OnesCount64(hi)
	diffs = 2*bits.OnesCount64(pos) - 1 // A-A is symmetric and contains 0
	return
}

The real code uses multi-word masks, but the idea is the same. On top of it I built three experiments, all in Go across 16 threads.

The first is exhaustive. It classifies every subset of $\{0, \dots, n-1\}$ for each $n$ up to 36. A set and its shifts behave identically, so it is enough to enumerate sets that contain both endpoints and weight each by the number of positions it fits in. The counts of sum-dominant, balanced and difference-dominant sets match OEIS A222807, A118544 and A222808 term for term. The only eight-element MSTD sets that fit are Conway’s set, its mirror image and their two doubled copies, as Hegarty’s theorem requires.

The second samples the two-string model $10^{10}$ times, which estimates the limit $\rho$ directly.

The third is a coupled comparison. To see how the finite fraction $\rho_n$ differs from $\rho$, the obvious move is to estimate both and subtract, but the noise in each swamps a difference of a few millionths. Instead, each sample draws two 128-bit end strings, classifies them with the limit model, then builds an actual random set of size $n$ from the first $n/2$ bits of each string and classifies that too. Both are correctly distributed, and at $n = 45$ they disagree on only about one sample in 7,800, so the difference between them is pinned down far more tightly than either fraction alone. I ran $10^9$ coupled samples at each of 27 values of $n$ between 30 and 80, and $3 \times 10^8$ at four more, up to 128.

Then the checks. Wherever exact counts exist, the simulated fractions match them within ordinary statistical scatter. A direct run of $10^9$ sets at $n = 45$, using a second random number generator (ChaCha8 instead of PCG), gives $4.6401 \times 10^{-4}$ against the exact $4.6402 \times 10^{-4}$. The largest deviation anywhere was 2.2 standard errors, at $n = 30$, and it fell to 1.5 when I ran six times as many samples there. The model reproduces the averages of 10 and 6, and its variance of missing sums, 35.9657, matches the 35.9658 that Lazarev, Miller and O’Bryant computed from their exact formula. Its distribution of missing sums also shows the oddity they proved, a dip at exactly seven: 7.15% of sets miss seven sums, against 7.19% for six and 7.26% for eight.

The fraction overshoots

The first result needs no simulation. The exact counts already break monotonicity. Each subset of $\{0, \dots, 42\}$ extends to exactly two subsets of $\{0, \dots, 43\}$, so if the fraction held steady from $n = 43$ to $n = 44$, the count would double from 4,080,654,360 to 8,161,308,720. It is 8,159,557,326, short by 1,751,394. The fraction dips, from $4.63917 \times 10^{-4}$ to $4.63817 \times 10^{-4}$, then recovers at $n = 45$.

The second result is the overshoot. Sampling the two-string model $10^{10}$ times gives

one standard error, or about one set in 2,195. The exact fraction at $n = 45$ is $4.6402 \times 10^{-4}$, 1.8% higher. The coupled runs measure that gap directly, $(8.64 \pm 0.36) \times 10^{-6}$ at $n = 45$, and trace the rest of the curve. The gap is $-17.0$ millionths at $n = 30$, indistinguishable from zero at $n = 35$, peaks near $+9$ millionths at $n = 45$, and shrinks from there: $+6.9$ at $n = 50$, $+3.6$ at $n = 60$, $+0.53$ at $n = 80$.

Figure 3. Top: the fraction of subsets of $\{0, \dots, n-1\}$ that are MSTD. Dark points are exact counts; green points are the limit plus the coupled estimate of $\rho_n - \rho$. Bottom: the same data as the distance from the limit, in millionths, with two-standard-error bars on the simulated points. Where the two overlap, between $n = 30$ and $45$, they agree. The fraction crosses its limit near $n = 35$, overshoots by up to 1.9%, and comes back from above.

Why it overshoots

The two-string model treats a set as two infinitely long, independent ends. A real set of size $n$ differs from that in three ways, and each one moves the fraction.

First, a real set has a middle. The model has no middle, so it never misses a sum there. A real set occasionally does, and an extra missing sum works against sum-dominance.

Second, a short set cannot miss far differences. The model lets the cross sums $X+Y$ go missing arbitrarily far from the edge. A real set has no differences beyond $\pm(n-1)$, so it loses that tail of possible gaps, and fewer missing differences also works against sum-dominance. This one fades fast, like $(3/4)^n$.

Third, and most important, differences chain. A difference $d$ is missing when no two elements of $A$ are exactly $d$ apart. In the model, the pairs that could produce it are independent. In a real set they are not, once $d < n/2$: the pairs $(a, a+d)$ and $(a+d, a+2d)$ share an element, so the candidate pairs link into chains $a, a+d, a+2d, \dots$. Missing $d$ means never picking two neighbours in any chain, and the number of ways to do that along a chain of length $L$ is the Fibonacci number $F_{L+2}$. So

which is larger than it would be if the pairs were independent. A chain of three avoids both of its pairs with probability $5/8$, where two independent pairs would manage $9/16$. Lazarev, Miller and O’Bryant met the same Fibonacci counting in their variance formula. Sums never chain. For a given sum $s$, each element has exactly one possible partner, $s - i$, so the candidate pairs are disjoint. For a given difference, each element has two, one on each side. Averaged over all subsets of $\{0, \dots, 44\}$, the formula gives 6.016 missing differences instead of 6, and essentially all of the excess comes from $d < n/2$. Chaining favours sums, and it fades slowly, like $(3/4)^{n/2}$.

To check that these are the effects that matter, I took the coupled samples where the real set and the limit model disagree about sum-dominance, and sorted them by what changed. For each kind of change, the table gives the number of sets pushed into sum-dominance for every set pushed out of it:

From $2 \times 10^8$ coupled samples at $n = 25$ and $30$ and $6 \times 10^8$ at $45$ and $60$, which produced between 22,000 and 103,000 disagreements each.

Changes in sums always cost sum-dominance, by a shrinking margin. Changes in differences cost it at $n = 25$, while the lost tail still outweighs the chains, and help it more and more from there on. Every one of the extra missing differences behind those gains sat below $n/2$, as chaining predicts, and between 79% ($n = 25$) and 95% ($n = 60$) of them sat between $0.3n$ and $0.5n$, where most chains have two or three links.

So the shape of the curve is a handful of effects with different lifetimes. Below $n = 35$, the missing middle and the lost tail of differences hold the fraction under its limit. The tail fades first, chaining takes over, and the fraction crosses the limit near $n = 35$ and overshoots, peaking near $n = 45$. Then chaining fades too. Every difference below $n/2$ has more than $n/2$ candidate pairs, and avoiding all of them becomes vanishingly unlikely however they chain, so the fraction settles back onto its limit from above.

What this does and does not show

The dip at $n = 44$ is exact arithmetic on published counts. The overshoot is a statistical result, with a wide margin. At $n = 45$ the exact fraction sits 39 standard errors above the direct estimate of the limit, and the coupled estimate of the gap is 24 standard errors from zero. Three routes to $\rho$ agree. Direct sampling with PCG gives $(4.5564 \pm 0.0021) \times 10^{-4}$, direct sampling with ChaCha8 gives $(4.5510 \pm 0.0048) \times 10^{-4}$, and the exact counts at $n = 30$ to $45$ minus the coupled gaps give $(4.5552 \pm 0.0016) \times 10^{-4}$. A direct ChaCha8 run at $n = 60$, which does not use the coupling at all, puts the fraction $(3.2 \pm 0.7) \times 10^{-6}$ above the limit, against the coupled $(3.6 \pm 0.2) \times 10^{-6}$.

It is not a proof. Proving that $\rho_n$ overshoots needs a rigorous upper bound on $\rho$ below $4.640 \times 10^{-4}$, and the best one known is 0.43. Zhao’s algorithm can in principle squeeze $\rho$ as tightly as you like, but its error terms shrink slowly, and I have not found a better upper bound published since.

Some questions stay open. Nobody knows a closed form for $\rho$. Rigorously, all that is known is that it lies between $4.28 \times 10^{-4}$ and $0.43$. The rate is only half explained: by $n = 80$ the overshoot shrinks by about 12% per step, close to the 13.4% at which the average corrections vanish, but between $n = 50$ and $70$ it fades more slowly than the averages alone would predict, and I do not have a clean account of why. And I would not bet on the fraction being monotone after its peak. From $n = 33$ on, the exact counts grow more at each odd step than at the even step after it, and the dip at $n = 44$ is an even step that went below zero. Past the peak, my coupled estimates at odd and even $n$ fall on one smooth curve within error bars of about $\pm 0.3$ millionths, which is too coarse to tell whether every single step goes down.

Nathanson’s sentence had two halves: such sets should be rare, and “with the right way of counting” the vast majority of sets should have more differences than sums. The second half holds. About 93% of large random sets have more differences, and most of the rest are balanced. The first half fails by a fixed margin, one set in 2,200, because the count that decides the contest runs over gaps at the edges, not over pairs. Near an edge, a sum really does have half as many ways to happen as a difference, which is the commutativity argument working as intended. Away from the edges every value is hit many times over, by sums and differences alike. The overshoot is the one place the middle still shows up: in sets of a few dozen numbers, chained differences through the middle go missing often enough to tip about one set in 120,000.