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.

This is a question from Complex analysis by Stein.

The question is

Prove that it is not possible to partition $\mathbb N$ into finitely many infinite AP's with distinct common differences.(other than the trivial $a=d=1$)

Infinite AP:=$\{a,a+d,a+2d,......\}$.I have no idea as to how to approach it. Any hints are welcome. Thanks.

share|improve this question

marked as duplicate by Grigory M, Daniel Rust, Goos, M Turgeon, Eric Stucky May 11 at 2:25

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
Are you sure you've written the question correctly? –  Hurkyl May 9 at 9:06
1  
What is wrong with $\{1, 3, 5, 7, \ldots\}$ and $\{2, 4, 6, 8, \ldots\}$? –  Benjamin Dickman May 9 at 9:06
    
@Hurkyl sorry forgot to add that common difference has to be different for all the infinite AP's which make up the partition. Thanks for pointing it out –  happymath May 9 at 9:13
    
@BenjaminDickman I think the problem with your solution is that the common difference is 2 in both cases. Is that correct @happymath? –  gebruiker May 9 at 9:34
    
@Aal Right; the OP edited in the "distinct common differences" after my comment. –  Benjamin Dickman May 9 at 9:36

2 Answers 2

up vote 5 down vote accepted

There are a couple of proofs of this, but the complex-analysis tag points to D J Newman's proof. Corresponding to each arithmetic progression $a,a+d,a+2d,\dots$ is a generating function, $$x^a+x^{a+d}+x^{a+2d}+\cdots={x^a\over1-x^d}$$ To say the arithmetic progressions partition the natural numbers is to say the generating functions add up to $1/(1-x)$. This has a pole at $x=1$, and nowhere else. Now, consider the arithmetic progression with the greatest common difference --- call that common difference, $m$. Then the generating function for that AP will have a pole at $e^{2\pi i/m}$, which can't be cancelled by any of the other generating functions. So, we have a contradiction.

share|improve this answer
    
can you please share the other proofs as well –  happymath May 9 at 10:15
    
what is the proof that we cannot cancel out a pole because if the subsets are infinite then i think it is possible –  happymath May 9 at 10:17
    
Don't know them by heart, and they're a bit much to write out. –  Gerry Myerson May 9 at 10:17
1  
Exactly one of the generating functions has a pole at $e^{2\pi i/m$. Nothing else has a pole to cancel that pole. –  Gerry Myerson May 9 at 10:24
2  
For more work on this kind of problem, and references to other proofs, see matwbn.icm.edu.pl/ksiazki/aa/aa50/aa5011.pdf –  Gerry Myerson May 9 at 13:16

This is an old chestnut solvable by generating functions. For any infinite AP $\{a,a+d,a+2d, \dots\}$ consider the power series (generating function) $z^a + z^{a+d} + z^{a+2d} + \cdots$, which can be written as a rational function by summing the geometric series. The generating function for a disjoint union is the sum of the generating functions. So your hypothesized partition of $\Bbb N$ into infinite APs will give an expression for $x+x^2+x^3+\cdots = z/(1-z)$ (the generating function for $\Bbb N$) as a sum of these other rational functions. From there you should be able to derive a contradiction (which definitely requires something like the common differences are distinct...).

share|improve this answer

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