Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
For $n$ even it is easy to get a contradiction by summing up, but for $n$ odd? –  darij grinberg Aug 3 '10 at 22:24
1  
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! –  Fedor Petrov Aug 4 '10 at 6:39
1  
@Fedor, I don't follow your proof. –  Gerry Myerson Aug 4 '10 at 7:09
1  
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 n*n*(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 n*n*(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. –  Aaron Meyerowitz Aug 4 '10 at 7:40
1  
$n^2(n-1)/2$ is not always $0$ modulo $n^2$, but it always differs from $n^2(n-1)/2+n$ –  Fedor Petrov Aug 4 '10 at 9:12
show 3 more comments

2 Answers 2

up vote 2 down vote accepted

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$)

share|improve this answer
    
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... –  Gjergji Zaimi Aug 4 '10 at 7:03
    
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. –  Fedor Petrov Aug 4 '10 at 7:20
    
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. –  Aaron Meyerowitz Aug 4 '10 at 7:25
add comment

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.

share|improve this answer
    
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. –  Aaron Meyerowitz Aug 4 '10 at 4:25
2  
@Aaron, Fedor calls it an "easy lemma" so I infer he already has a proof and just wants a citation. –  Gerry Myerson Aug 4 '10 at 5:50
    
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. –  Aaron Meyerowitz Aug 4 '10 at 6:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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