Partitions of Natural Numbers

1.5k Views Asked by At

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.

2

There are 2 best solutions below

10
On BEST ANSWER

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.

0
On

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