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