# How many pairs (M, N) of sets of size n have M + N = {0, 1, …, n^2-1}?

How many pairs (M, N) of sets of size n have M + N = {0, 1, ..., n^2-1}?

Manfred Schroeder, in Number Theory in Science and Communication, 4th edition, asks (p. 27): find all pairs of sets $(M,N)$, each of size 10, such that $$M + N = \{ m + n : m \in M, n \in N \}$$ is the set $\{ 0, \ldots, 99 \}$. One example is, of course, the pair $M = \{ 0, 1, \ldots 9 \}$ and $N = \{ 0, 10, \ldots, 90 \}$. Of course there's nothing special about 10 here, and one can instead look for pairs $(M,N)$ such that $|M| = |N| = n$ and $M + N = \{0, 1, \ldots, n^2-1\}$.

This reminded me of the following problem: are there two six-sided dice, other than the standard ones, such that the probabilities of obtaining $2, 3, \ldots, 12$ are the same as on the standard dice? The solution I know is as follows: this is equivalent to finding polynomials $f(z), g(z)$ with positive coefficients, with $f(1) = g(1) = 6$, such that $$f(z) g(z) = z^2 + 2z^3 + 3z^4 + 4z^5 + 5z^6 + 6z^7 + 5z^8 + 4z^9 + 3z^{10} + 2z^{11} + z^{12}$$ Then $f$ and $g$ are the generating functions (polynomials) of the two dice, and $f \cdot g$ the generating function of the possible sums, counted with multiplicity.

Now, this polynomial of degree $12$ factors as $$z^2 (z+1)^2 (z^2+z+1)^2 (z^2-z+1)^2$$ and the only way we can group these factors together to get $f(z)$ and $g(z)$ as desired is to take $$f(z) = z(z+1)(z^2+z+1) = 1+2z^2+2z^3+z^4, g(z) = z(z+1)(z^2+z+1)(z^2-z+1)^2 = z+z^3+z^4+z^5+z^6+z^8$$ That is, two dice labelled $(1,2,2,3,3,4)$ and $(1,3,4,5,6,8)$ have the same probabilities of each outcome as the standard dice. (See Sicherman dice in Wikipedia.)

So I tried to do something analogous for Schroeder's problem: factor $1+z+z^2+\cdots+z^{99} = (z^{100}-1)/(z-1)$ into two factors $f(z), g(z)$ with $f(1) = g(1) = 10$ and all coefficients positive. (Factoring $z^{100}-1$ isn't too hard, with the help of the theory of cyclotomic polynomials.) But this method of solution doesn't seem to work. How do we put the factors back together? For example we can take $$f(z) = 1 + z + z^2 + z^3 + z^4 + z^{50} + z^{51} + z^{52} + z^{53} + z^{54}, g(z) = 1 + z^5 + z^{10} + z^{15} + z^{20} + z^{25} + z^{30} + z^{35} + z^{40} + z^{45}$$ which I found by experiment. But I can't see how to find all the good'' factorizations, since a lot of the irreducible factors of $1+z+z^2 + \cdots + z^{99}$ have negative signs. Presumably someone a bit more comfortable with cyclotomic polynomials can answer Schroeder's question, or the (probably not much simpler) question of finding the number of pairs of sets $(M,N)$ having this splitting property.

-
Do you want to restrict M,N to have only nonnegative elements? Otherwise you get infinitely any such pairs by translations. :) – Gjergji Zaimi Apr 8 '10 at 4:37
Yes. As a combinatorialist, infinite sets offend me. – Michael Lugo Apr 8 '10 at 14:21

Let $a$, $b$ be divisors of $n$. Convince yourself that the sets

$M = \{0,1,\ldots,a-1\} + ab \cdot \{0,1,\ldots,n/a-1\}$

$N = \{0,a,\ldots,(b-1)a\} + bn \cdot \{0,1,\ldots,n/b-1\}$

have the desired property. These pairs $(M,N)$ are all distinct as $a$, $b$ vary over divisors other than $1$, $n$. On the other hand the pairs coming from choosing $a=n$ or $b=1$ or $(a,b)=(1,n)$ all coincide with the obvious ("base $n$") pair, while the pair coming from $(a,n)$ coincides with the pair coming from $(1,a)$. So if $\sigma$ is the number of divisors of $n$, this gives you at least $\sigma^2 - 3 \sigma + 3$ such pairs. For $n=10$ you can check (e.g. using the generating function method that you described) that this gives all the possibilities.

In general there will be more, because you can iterate the construction: you have pairs of the form

$M = \{0,1,\ldots,d_1-1\} + d_1 d_2 \{0,1,\ldots,d_3-1\} + d_1 d_2 d_3 d_4 \{0,1,\ldots,d_5-1\} + \cdots$

$N = d_1 \{ 0,1,\ldots,d_2-1\} + d_1 d_2 d_3 \{0,1,\ldots,d_4-1\} + \cdots$

for divisors $d_1,d_2,\ldots$ of $n$ with $d_2 d_4 \cdots d_{2k} = n$ and similarly for the product of the odd-indexed $d$'s. Now collisions between the various pairs should happen precisely whenever any of the $d_i$'s happens to be $1$, and so distinct pairs should come from distinct sequences $d_1,\ldots,d_{\ell}$ of divisors of $n$ other than $1$ such that the odd terms multiply to $n$ and the even terms also multiply to $n$. For instance we find that we've correctly re-counted the $\sigma^2-3\sigma +3$ possibilities that we found and counted before: the sequences of $d$'s of length at most $4$ are

$n,n$

$a,n,n/a$

$a,b,n/a,n/b$

as $a,b$ range over nontrivial divisors of $n$. But of course if $n$ has more than two prime factors, you get longer sequences as well. I'll leave it to someone else to do the enumeration of the sequences.

I think I've convinced myself that this construction gives you everything, but it might be a pain to write down. (Suppose $M$ is the set containing $1$. Take $d_1$ to be the smallest nonzero integer contained in $N$. Then the smallest integers in $N$ have to consist of multiples of $d_1$ up to some $d_1(d_2-1)$, and the next integer contained in $M$ is $d_1 d_2$. But then $d_1 d_2 + 1,\ldots,d_1 d_2 + (d_1-1)$ each have to be in one or the other of the sets, and in fact they have to be in $M$ or else you could form the sum $d_1 (d_2+1)$ in two ways. And so forth.)

-
Here's a sketch of a cleaner way to prove that your construction gives everything: Notation: let f and g be the generating functions for the sets M, N, as in Michael's post, and let $d_1$ be as above. Then one can verify the following Lemma: $f(z) = (1 + z + ... + z^{d_1 - 1}) \cdot f_1(z^{d_1})$ and $g = g_1(z^{d_1})$, where $f_1$ and $g_1$ have all coefficients $0$ or $1$. Given the lemma, we can factoring out the $1 + z + ... + z^{d_1 - 1}$ term and change variables to $z_1 = z^{d_1}$, to get $f(z_1) g(z_1) = 1 + z_1 + ... + z_1^{n/d}$. Now induct. – Alison Miller Apr 8 '10 at 5:27