2

From Stein and Shakarchi's Complex Analysis book, Chapter 1 Exercise 22 asks the following:

Let $\Bbb N=\{1,2,\ldots\}$ denote the set of positive integers. A subset $S\subseteq \Bbb N$ is said to be in arithmetic progression if $$S=\{a,a+d,a+2d,\ldots\}$$ where $a,d\in\Bbb N$. Here $d$ is called the step of $S$. We are asked to show that $\Bbb N$ cannot be partitioned into a finite number of subsets that are in arithmetic progression with distinct steps (except for the case $a=d=1$).

He gives a hint to write $$\sum_{n\in\Bbb N}z^n$$ as a sum of terms of the type $$\frac{z^a}{1-z^d}.$$ How do I apply the hint? I know that $$\sum_{n\in\Bbb N}z^n=\frac{z}{1-z}$$ but that doesn't have anything to do with the $a$ or $d$. Thanks for any help!

leonbloy
  • 63,430
anon271828
  • 932

1 Answers1

2

Suppose $\mathbf{N}=S_1\cup\cdots S_k$ is a partition of $\bf N$ and $S_r=\{a_r+d_rm:m\ge0\}$. Then

$$\begin{array}{cl}\frac{z}{1-z} & =\sum_{n\in\bf N}z^n \\ & =\sum_{r=1}^k\left(\sum_{n\in S_r}z^n\right) \\ & = \sum_{r=1}^k\left(\sum_{m\ge0}z^{a_r+d_rm}\right) \\ & = \sum_{r=1}^k\frac{z^{a_r}}{1-z^{d_r}}.\end{array}\tag{$\circ$}$$

Suppose each $d_r$ is distinct. Do both sides of $(\circ)$ have the same poles in the complex plane?

anon
  • 151,657
  • This sounds convincing, but as of Chapter 1, the book hasn't discussed poles; is there another reason? – anon271828 Jan 13 '13 at 21:10
  • @anon271828 You don't really need to think in terms of poles - it would be more simplistic to ask where the functions on either side of $(\circ)$ are defined in the first place. Surely the concept of where a rational function is defined and where it isn't is something you can take for granted in Chapter 1, I would think... – anon Jan 13 '13 at 21:14
  • I'm still a little bit confused. It would seem the right-hand side is defined for all $z$ that isn't some kind of $d_r$ root of unity while the right-hand side is defined for $z\neq1$... – anon271828 Jan 16 '13 at 16:37
  • @anon271828 Correct. So if you were to take the limit at a $d_r$th root of unity for example, the RHS would blow up and the LHS wouldn't. So these can't be the same function, contrary to hypothesis. In which case there is no partition of the naturals into arithmetic progressions of distinct stepsizes. – anon Jan 16 '13 at 16:41
  • AH, I see now. Thanks! – anon271828 Jan 16 '13 at 16:44
  • 1
    @anon271828 One has to be slightly careful here. Note that the question specifies that the ${d_r}$ are distinct, which is an important assumption. Just because individual terms of the RHS blow up doesn't mean that the entire RHS blows up, because cancellation could occur. But if you look at a primitive $d_r$th root where, say $d_r$ is the largest, then it can't be cancelled by any other term. – Erick Wong Jan 17 '13 at 07:07