More on sums and differences

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

This entry was posted in mathematics, problems and puzzles.

Comments are closed.