4
$\begingroup$

I would be glad to see a reference to the following easy lemma in additive combinatorics: if $A_1$ and $A_2$ are two sets of remainders modulo $n^2$, each has cardinality $n > 1$ and all elements of $A_i$ are different modulo $n$ (for $i=1,2$), then $A_1+A_2$ is not equal to the set of all remainders modulo $n^2$.

Maybe, it is a partial case of more general and deep:) result.

$\endgroup$
8
  • $\begingroup$ For $n$ even it is easy to get a contradiction by summing up, but for $n$ odd? $\endgroup$ Aug 3, 2010 at 22:24
  • 1
    $\begingroup$ Well, the easy proof is as follows: assuming contrary, consider all $n$ remainders with remainder $r$ modulo $n$, sum up. We get that sum of all elements of $A_1$ and $A_2$ equals $r+(r+n)+\dots+r+(n^2-n)$. But this does depend on $r$. Contradiction! $\endgroup$ Aug 4, 2010 at 6:39
  • 1
    $\begingroup$ @Fedor, I don't follow your proof. $\endgroup$ Aug 4, 2010 at 7:09
  • 1
    $\begingroup$ It is cute! Line up the elements of A_1 by increasing residue mod n. underneath them put the elements of A_2 in decreasing order (mod n). The sums (reduced mod n^2) are 0, n,2n,...,(n-1)*n in some order for a grand total of nn*(n-1)/2 which is 0 mod n^2. Now cyclically shift the second row. The n sums (reduced mod n^2) would be 1 n+1, ...,(n-1)n+1 for a grand total of nn*(n-1)/2+n*1 which is n mod n^2. But the grand total should remain unchanged since it is the sum sum of 2n integers. $\endgroup$ Aug 4, 2010 at 7:40
  • 1
    $\begingroup$ $n^2(n-1)/2$ is not always $0$ modulo $n^2$, but it always differs from $n^2(n-1)/2+n$ $\endgroup$ Aug 4, 2010 at 9:12

2 Answers 2

2
$\begingroup$

There must be an easier proof but here is a nice approach which can indeed lead to deeper results (feel free to edit for math display, I tried): Techniques with characteristic polynomials and roots of unity can be very powerful. I like the way that the appropriate lemmas are explained in my paper with Ethan Coven "Tiling the Integers with Translates of One Finite Set" http://arxiv.org/abs/math/9802122 or Journal of Algebra v 212 (1988) p 161-174. One does not need their full generality for this problem but perhaps for deeper results.

I'll sketch this result which implies what was asked for: Suppose that A and B are sets of size #A and #B so that A+B is a complete set of residues mod N=#A#B. Let p be a prime dividing N. Then exactly one of the sets has its members equally distributed mod p.

digression: Lemma 3.2 from the paper above (not needed here) shows that at least one of the following is true:

1) No member of A-A is relatively prime to #B

2) No member of B-B is relatively prime to #A end of digression

Consider the corresponding polynomials $A(x)=\sum_{a \in A}x^a$ and $B(x)=\sum_{b \in B}x^b$. Then

i) A(1)=#A and B(1)=#B

ii) A(x)B(x) is a sum of N distinct powers of x, one from each residue class.

iii) $A(x)B(x)=(x^N-1)Q(x)+\frac{x^N-1}{x-1}$ for some polynomial Q(x).

iv) Every irreducible polynomial dividing $\frac{x^N-1}{x-1}$ divides at least one of $A(x)$ and $B(x)$

As an example consider A={0,9,13,16,29,32} B={0,10,12,22,24,34} with A+B a complete set of residues mod N=36.

$$\frac{x^{36}-1}{x-1}=(x+1)(x^2+x+1)(x^2+1)(x^2-x+1)(x^4+x^2+1)(x^4-x^2+1)(x^{18}-x^9+1)$$

evaluated at $x=1$ this becomes 36=2 * 3 * 2 * 1 * 3 * 1

In general the irreducible polynomial divisors of $\frac{x^N-1}{x-1}$ are the cyclotomic polynomials corresponding to the divisors of N. Evaluated at x=1 each is either 1 (composite divisor) or a prime p (prime power divisor) and the primes have product N. Since A(1)B(1)=N and A(x)B(x) is divisible by all the prime power cyclotomic divisors of $\frac{x^N-1}{x-1}$ and these evaluated at 1 also have product N, each divides just one of A(x) or B(x) and all other polynomial divisors evaluate to 1 at 1. In particular: for each prime divisor of N, only one of A(X), B(x) divides by $\frac{x^p-1}{x-1}$ and only that one has corresponding set equidistributed mod p.

In our example A is a complete set of residues mod 6 so A(x) divides by (1+x) and by (1+x+x^2). Since A(1)=6 , A(x) can't have either of (1+x^2) and (1+x^2+x^4) as factors. But they do divide A(x)B(x) and hence they divide B(x). This means that neither (1+x) nor (1+x+x^2) can divide B(x), again since B(1)=6. Hence, B is not equidistributed mod 2 (or mod 3) and certainly not mod 6.

By the way, $B(x)=(x^{10}+1)(x^{24}+x^{12}+1)$ and $A(x)=(x^{13}+1)(x^{32}+x^{16}+1)$ (mod $x^{36}-1$)

$\endgroup$
3
  • $\begingroup$ I don't see how any of the facts you wrote help with this problem. Here we need to show that $x^{n^2}-1$ does not divide $A(x)B(x)$ in your notation... $\endgroup$ Aug 4, 2010 at 7:03
  • $\begingroup$ Oh, Aaaron, thanks! That's what I actually needed. Gjergji, I think Aaaron is correct: we assume that $A+B$ is full set of residues modulo $N$ ($N=n^2$ in my case), then we have such equality and that's it. $\endgroup$ Aug 4, 2010 at 7:20
  • $\begingroup$ I show that if $x^{n^2}-1$ does divide A(x)B(x) and A(x) is equally distributed mod n then B(x) is not equally distributed mod n. $\endgroup$ Aug 4, 2010 at 7:25
-1
$\begingroup$

Replace each set by a sum of powers of x. Let p be a prime like 5 dividing n. Under your condition 1+ x + x^2 + x^3 + x^4 would divide both polynomials. Show it only divides the product once. I'd be less coy but I am typing this on a phone in a power outage! I've used those ideas to great effect. If n is prime then one set not only is not distinct mod n but actually has all elements equal mod n.

$\endgroup$
3
  • $\begingroup$ Ok, this is messed up. {0,1,4,5,8,9}+{0,2,12,14,24,26} is a counter-example. But note that mod 6 the second set is {0,2,0,2,0,2}. I'll post a clearer answer and take this one down. $\endgroup$ Aug 4, 2010 at 4:25
  • 2
    $\begingroup$ @Aaron, Fedor calls it an "easy lemma" so I infer he already has a proof and just wants a citation. $\endgroup$ Aug 4, 2010 at 5:50
  • $\begingroup$ I suppose you are right. The approach I give shows (inter alia) that if A+B is a complete set of residues mod N=#A#B and both A and B contain 0 (no loss of generality in assuming that) then at least one of the two contains no elements relatively prime to N. $\endgroup$ Aug 4, 2010 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.