Can $\mathbb{N}$, the set of natural numbers, be partitioned into a finite number of subsets that are in arithmetic progression with distinct steps ?
Partitioning $\mathbb{N}$ into distinct AP’s
2 Answers
-
3Alternatively: "Suppose it could, then all that thread in MathOverflow is bunk; since the users on MathOverflow are mathematicians it is not bunk. Therefore $\mathbb N$ cannot be partitioned into finitely many AP's $\square$". – 2012-08-21
-
3That is the worst best comment I've seen in recent memory.... – 2012-08-21
-
0@Asaf, I don't understand you. The occupation of the users on MO does not enter into it. On that page you find complete proofs and references to complete proofs, and anyone, mathematician or not, can check those proofs. – 2012-08-21
-
0@Gerry: I didn't check the page myself, actually. So I just relied on the fact that MO users are research mathematicians (as it was clearly asserted in a recent meta discussion, non-researchers are shot on sight, and all their posts are immediately downvoted; closed; and deleted.) – 2012-08-21
-
1@Cameron: It's based on an old SMBC based proof of infinitude of prime numbers, to be fair... :-) – 2012-08-21
The answer is no. Here is a proof:
Proof by Contradiction:
Suppose that $\mathbb{N}$ can be partitioned into a finite number of subsets say: $$$$ $$ \{a_1, a_1 + d_1, a_1 + 2d_1,...\}, \{a_2, a_2 + d_2,...\},...\{a_m, a_m + d_m, ...\} $$
$$$$ Then for |z| < 1, $\sum_{n=0}^\infty z^n = \sum_{k=0}^\infty z^{a_1 + kd_1} + ... + \sum_{k=0}^\infty z^{a_m + kd_m}$
By convergence of geometric series, the above simplifies to:
$$ \frac{1}{1-z} = \frac{z^{a_1}}{1-z^{d_1}} + ... + \frac{z^{a_m}}{1-z^{d_m}} $$ Note that the left hand side has a simple pole only at z = 1. However, the right hand side can be written as
$$ \frac{z^{a_1}(1-z^{d_2})***(1-z^{d_m}) + ... + z^{a_m}(1-z^{d_1})***(1-z^{d_m-1})}{(1-z^{d_1})(1-z^{d_2})***(1-z^{d_m})} $$
Since the step sizes, the d's, are all distinct, the above expression has poles on the unit circle, $\{z: |z|=1\}$, at points not equal to 1. This means that this expression in neighborhoods of those poles get arbitrarily large. Since those neighborhoods intersect the unit disk, $\{z: |z|<1\}$, we have that $\frac{1}{1-z}$ is also arbitrarily large in those neighborhoods. This however, contradicts that $\frac{1}{1-z}$ has exactly one pole at z=1.