Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The statement is:

Let $A=\{(a_s(n_s)\}^k_{s=1}$ be an exact cover of $\mathbb{Z}$ with $1<n_1\leq\ldots\leq n_{k-1}\leq n_k$. Then we must have $n_{k-1}=n_k$.

The only proof I could find was here. But I have some difficulties understanding it. It is very short and it goes like this:

Without loss of generality we assume that $0\leq a_s<n_s$ for all $s\in[1,k]$. For $|z|<1$ we have $$\sum_{s=1}^k\frac{z^{a_s}}{1-z^{n_s}}=\sum_{s=1}^k\sum_{q=0}^\infty z^{a_s+qn_s}=\sum_{n=0}^\infty z^n=\frac{1}{1-z}.$$ If $n_{k-1}<n_k$ then $$\infty=\lim_{\substack{z\to e^{2\pi i/n_k}\\ |z|<1}}\frac{z^{a_k}}{1-z^{n_k}}=\lim_{\substack{z\to e^{2\pi i/n_k}\\ |z|<1}}\left(\frac{1}{1-z}-\sum_{s=1}^{k-1}\frac{z^{a_s}}{1-z^{n_s}}\right)<\infty,$$ a contradiction!

What I don't get is the following: $$\sum_{s=1}^k\sum_{q=0}^\infty z^{a_s+qn_s}=\sum_{n=0}^\infty z^n.$$ It just doesn't make sense to me. So what am I misunderstanding?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

That equation states that $A$ is an exact cover. On the left, you have all the terms $z^m$ where $m$ satisfies $m\equiv a_s\pmod{n_s}$, with coefficient the number of such congruences $m$ satisfies. On the right, you have $z^n$ for every $n$, with coefficient $1$. So, the equality is saying that every non-negative integer satisfies exactly one congruence.

share|improve this answer
    
Oh... I think I get it now. While we're at it, can you please explain the last equation/inequality as well? I don't understand why we take the limit $z\to e^{2\pi i/n_k}$. –  Carolus Nov 15 '12 at 12:55
    
The point of the proof is that exactly one of the terms $z^{a_s}/(1-z^{n_s})$ has a pole at $z=e^{2\pi i/n_k}$, so the sum on $s$ must have a pole there --- but the sum on $s$ equals $1/(1-z)$, which manifestly has no pole there. –  Gerry Myerson Nov 15 '12 at 22:23
    
I see now, thank you very much. –  Carolus Nov 16 '12 at 7:33

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.