Take the 2-minute tour ×
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.

An arithmetic sequence of step $d$ is a set of the form: {$a, a+d, a+2d, a+3d, ...$} where $a, d$ are positive integers.

Show that the positive integers cannot be partitioned into a finite number of arithmetic sequences s.t. each sequence has a distinct step $d$. (Except the trivial sequence $a=1, d=1$.)

Now the book gives me a hint:
Write $\sum_{n\in\mathbb{N}}z^n$ as a sum of terms of the type $\frac{z^a}{1-z^d}$.

But it isn't clear that the power series can even be put such a form, and even if it can, why does that help me?

share|improve this question
2  
Can you think of any way at all to relate integers to that power series? Or that power series to that rational function? –  Hurkyl May 24 '12 at 1:18
    
I can take the derivative of the power series, maybe? And then the coefficients of the series would be the positive integers. –  Mark May 24 '12 at 1:21
add comment

3 Answers 3

up vote 3 down vote accepted

This is a pretty problem. I asked a question about it in MathOverflow a while back. Here is the solution using complex analysis, copying from the link above, and adding some details: (I've added the details in between square brackets. Ignore those paragraphs if you want to work out the details on your own.)

Assign to each progression $A_i=(a_i+kb_i\mid k\in{\mathbb N})$, $1\le i\le n$, its generating series, $f_i(x)=\sum_{k=0}^\infty x^{a_i+kb_i}$. Then $f_i(x)=x^{a_i}/(1-x^{b_i})$. Note the series converges for $|x|<1$.

[ To see this: $\sum_{k=0}^\infty x^{a_i+kb_i}=x^{a_i}\sum_{k=0}^\infty (x^{b_i})^k$, and use that if $|t|<1$, the geometric series $\sum_{k=0}^\infty t^k$ equals $1/(1-t)$. ]

Now, since the $A_i$ partition ${\mathbb N}$, we have $\sum_{i=1}^n f_i(x)=\sum_{m=1}^\infty x^m=x/(1-x)$.

[ For this, observe that if $m\in A_i$, then $x^m$ is one of the terms being added in $f_i(x)$, and $x^m$ is not a term in any of the other series $f_j$ for $j\ne i$. ]

If all the $b_i$ are different, let $b$ be the largest, and fix a primitive $b$-th root of unity $\zeta$. Now let $x\to\zeta$ to reach a contradiction.

[ In detail, $\zeta=e^{2\pi i/b}$ is a primitive $b$-th root of unity ($i$ the square root of $-1$). This means that $\zeta^b=1$, if $k$ is an integer, then $\zeta^k=1$ iff $k$ is a multiple of $b$, and if $z^b=1$, then $z=\zeta^n$ for some integer $n$. You then have that $$\frac{x^{a_1}}{1-x^{b_1}}+\dots+\frac{x^{a_n}}{1-x^{b_n}}=f_1(x)+f_2(x)+\dots f_n(x)=\sum x^m=\frac x{1-x}. $$ Call $(*)$ this equation. When $x\to\zeta$, we obtain on the right hand side of $(*)$ the fraction $\displaystyle \frac{\zeta}{1-\zeta}$. Note here that $\zeta\ne 1$ because we are assuming we have at least two arithmetic progressions, so $b>1$. On the other hand, if $b_j\ne b$, then $$ \frac{x^{a_j}}{1-x^{b_j}}\to\frac{\zeta^{a_j}}{1-\zeta^{b_j}} $$ and $\zeta^{b_j}\ne 1$ because $b>b_j$. But if $b_j=b$, then $\displaystyle \frac{x^{a_j}}{1-x^{b_j}}\to\infty$ because $\zeta^{b_j}=\zeta^b=1$. The contradiction is that the left hand side of $(*)$ converges to $\infty$, while the right hand side does not. ]

This shows that the largest of the common differences must appear at least twice.

As Gerry Myerson pointed out in MO, this argument is due to D J Newman. It appears in his book A Problem Seminar, problem 90, on page 18, with solution on page 100.

share|improve this answer
    
I also pointed it out here, just a few minutes before you did. –  Gerry Myerson May 24 '12 at 2:33
    
Here you are using the facts: In an absolutely convergent series, any permutation of the terms will lead to the same sum. Functions which are equal on an open set must have the same limits on their limit points, if such limits exist. But can you please expand on the fact that, just because one of the terms of the LHS of (*) approaches $\infty$ then the whole LSH of (*) does not converge? Specifically, I am not sure under which conditions a pole might "cancel out." –  Mark May 24 '12 at 4:28
1  
@Mark You are adding finitely many terms ($n$ of them), and all but one have a finite limit. The limit of the remaining term is infinite, and the limit of the right hand side is finite. Now, this remaining term can be written as the right hand expression minus the other $n-1$ terms on the left. The limit of this expression is the sum (well, difference) of their individual (finite) limits, so it is finite. But we argued that it is actually infinite. You are right that if we were "adding several infinities" it could be that they cancel out. That's why we chose $b$ to be largest, to avoid this. –  Andres Caicedo May 24 '12 at 5:17
    
Of course! Thanks! –  Mark May 24 '12 at 13:52
add comment

Suppose you could partion the positive integers into disjoint arithmetic progressions $$a_1, a_1 + d_1, a_1 + 2d_1,\ldots$$ $$a_2, a_2 + d_2, a_2 + 2d_2,\ldots$$ $$\ldots$$ $$a_n, a_n + d_n, a_n + 2d_n,\ldots$$

Then the power series $\sum z^n$ can be rewritten as $$ \frac{z}{1-z} = \sum_{k=1}^\infty z^k = \sum_{j=1}^n\sum_{k=0}^\infty z^{a_j+kd_j} = \sum_{j=1}^n z^{a_j}\frac{1}{1-z^{d_j}},$$ which is the form you want it in. These series all converge absolutely and locally uniformly in the unit disk. Thus you can conclude that $$\frac{z}{1-z} = \sum_{j=1}^n\frac{z^{a_j}}{1 - z^{d_j}}.$$ The only pole of the left hand side is $z = 1$. If $J$ is the unique index such that $d_J$ is maximal, then the $j = J$ term on the right hand side has poles at the $d_J$th roots of unity, and no other term contributes poles at the primitive $d_J$th roots of unity. This is a contradiction if $d_J\neq 1$, that is, if you haven't partitioned the positive integers with the trivial partition.

share|improve this answer
    
You've supplied the flesh to the bones of my answer, but you haven't left much for Mark to do. –  Gerry Myerson May 24 '12 at 1:29
    
Why is it important that $d_J$ is the unique maximum step? What goes wrong with the proof otherwise? –  Mark May 24 '12 at 2:48
1  
(Antonio's comment has since been deleted, but it pertained to the fact that maybe there are other terms with poles at the $d_j^{th}$ roots of unity.) Antonio, maybe since $d_j$ is maximum, we know for sure that there is a pole $e^{\frac{2\pi i}{d_j}}$ such that it is not a pole for any other term, because you need to raise this number to the $d_j^{th}$ power to get 1. And we only need one such pole to reach the contradiction. I guess uniqueness is being used so that this pole doesn't get cancelled. –  Mark May 24 '12 at 4:22
1  
See what goes wrong if you try to use this argument to prove you can't partition the positive integers into 0 mod 2, 1 mod 4, and 3 mod 4. –  Gerry Myerson May 24 '12 at 4:33
1  
Trying an example with 1 mod 2 and 2 mod 2, I see that the terms together will cancel out the pole at -1. Andres has also mentioned that it is not possible for poles to cancel out like this when all the other terms have finite limits and one term has an infinite limit. I think I understand now. –  Mark May 24 '12 at 13:53
add comment

Given an arithmetic progression $a,a+d,a+2d,\dots$, you write down its generating function, $z^a+z^{a+d}+z^{a+2d}+\dots$ which you recognize as a geometric series, so you sum the geometric series and get a function with certain poles.

The generating function for the full set of positive integers is $z+z^2+z^3+\dots$, which you recognnize as a geometric series, etc., etc.

Partitioning the positive integers into arithmetic progressions is writing the generating function for the positive integers as the sum of generating functions for the arithmetic progressions. The desired conclusion comes from thinking about the poles on each side of the equation.

This proof is due to D J Newman.

share|improve this answer
    
It seems that even with the more detailed answers, I'm still having trouble with the proof. –  Mark May 24 '12 at 3:12
2  
Work at it - it builds character. –  Gerry Myerson May 24 '12 at 4:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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