Sum of sets modulo a square

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-
For $n$ even it is easy to get a contradiction by summing up, but for $n$ odd? – darij grinberg Aug 3 2010 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 2010 at 6:39

1
@Fedor, I don't follow your proof. – Gerry Myerson Aug 4 2010 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 2010 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 2010 at 9:12
show 3 more comments

2 Answers

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

-

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 2010 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 2010 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 2010 at 7:25

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-
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 2010 at 4:25

1
@Aaron, Fedor calls it an "easy lemma" so I infer he already has a proof and just wants a citation. – Gerry Myerson Aug 4 2010 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 2010 at 6:48
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 40, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9246813654899597, "perplexity_flag": "middle"}