MY AMERICAN SCIENTIST
SEARCH

HOME > PAST ISSUE > Article Detail

COMPUTING SCIENCE

# Calculemus!

Celebrating 25 years of celebrating computation

# Sums and Differences

Take a set of integers, say {0, 2, 3, 4}, and calculate the sums of all possible pairs of numbers drawn from the set. A set of four numbers yields 16 pairs, but not all the sums are necessarily distinct. In this case there are just eight different sums: {0, 2, 3, 4, 5, 6, 7, 8}. Now build the analogous set of pairwise differences; it turns out there are nine of them: {–4, –3, –2, –1, 0, 1, 2, 3, 4}.

If you try the same experiment with a few more small sets of numbers, you may be ready to guess that the sums never outnumber the differences. And there's a plausible rationale to back up this conjecture: Addition is commutative but subtraction isn't. The sums 5+8 and 8+5 both yield 13, whereas 5–8 and 8–5 produce two distinct differences, –3 and +3. Nevertheless, the conjecture is false. A counterexample is the eight-member set {0, 2, 3, 4, 7, 11, 12, 14}, which has 26 distinct pairwise sums but only 25 differences. It is called an MSTD set (for "more sums than differences").

I first learned about MSTD sets in publications by Melvyn B. Nathanson of Lehman College in the Bronx, Kevin O'Bryant of the College of Staten Island and Imre J. Ruzsa of the Mathematical Institute of the Hungarian Academy of Sciences. (I have written about their work earlier here .)

A program to search for MSTD sets can take a direct approach to the problem. For each set of numbers, the program forms all pairwise sums and then eliminates duplicates; it does the same for the differences, and then compares. The trickiest part of the program turns out to be the routine for generating the sets of integers to be tested. The sets are characterized by two parameters: the number of elements n and the size of the largest element m (which cannot be less than n –1). For any given values of n and m, the sets can be ordered from smallest to largest and enumerated in a way that's something like ordinary counting, but you have to be careful that a set never has duplicate elements.

This process of enumerating sets and checking all sums and differences sounds arduous, but it goes faster than you might expect. For example, in less than a second of running time you can establish that the example mentioned above, {0, 2, 3, 4, 7, 11, 12, 14}, is the smallest MSTD set with eight elements. (Peter V. Hegarty of Chalmers University of Technology has since shown that there are no MSTD sets with fewer than eight elements, so this is the smallest example overall.) Checking all sets with n =11 and m ≤20 takes less than a minute; there are 184,756 of these sets, and 160 of them are MSTDs, including a dozen where the sums exceed the differences by 2.

The search for MSTD sets is a peculiar kind of quest that seems to be possible only in mathematics. The sets are very rare, and yet there are infinitely many of them.