More on sums and differences

by Brian Hayes

Published 20 August 2006

Kevin O’Bryant, whose work on sets that have more sums than differences was mentioned in this recent post, writes as follows:

Here’s a related problem that Mel Nathanson and myself (with Ruzsa and a few students) have also been thinking about. For a finite set A of integers, let \(S = {a + b : a,b \in A}\) be the sumset, and let \(T = \{2a + b : a,b \in A\}\). Can it happen that S is larger than T? The answer is yes (we have a proof) but we don’t have a single example. Our proof gives a set that would have at least \(e^{2000}\) elements, so although our proof is “constructive”, it really isn’t in any practical sense. My professors thought “constructive” referred to a proof that didn’t use the axiom of choice, my generation thinks of it as an algorithm that runs in polynomial time, my students will have to worry about which polynomial. :)

Note that this problem, like the original MSTD problem, has the pleasant property of affine invariance: You can scale or translate the elements of the set by any constant, and the size of the S and T sets remains unchanged. In the case of an arithmetic progression, such as the n-element set {0, 1, 2,…, n–1}, the sumset S has 2n–1 elements, whereas the set T has 3n–2 elements. Thus |T| is greater than |S| by about n. For a random sampling of sets other than arithmetic progressions, it appears that |T| usually exceeds |S| by an even larger margin. I have no idea where to look for that elusive example with |T| < |S|.

Tags for this article: mathematics, problems and puzzles.

Publication history

First publication: 20 August 2006

Converted to Eleventy framework: 22 April 2025

Added links to related stories: 14 May 2025