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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

marked as duplicate by Grigory M, Dan Rust, 6005, M Turgeon, Eric Stucky May 11 '14 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 '14 at 9:06
What is wrong with $\{1, 3, 5, 7, \ldots\}$ and $\{2, 4, 6, 8, \ldots\}$? – Benjamin Dickman May 9 '14 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 '14 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 '14 at 9:34
@Aal Right; the OP edited in the "distinct common differences" after my comment. – Benjamin Dickman May 9 '14 at 9:36
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|cite|improve this answer
can you please share the other proofs as well – happymath May 9 '14 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 '14 at 10:17
Don't know them by heart, and they're a bit much to write out. – Gerry Myerson May 9 '14 at 10:17
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 '14 at 10:24
For more work on this kind of problem, and references to other proofs, see – Gerry Myerson May 9 '14 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|cite|improve this answer

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