Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

A few years ago, somebody told me a lovely problem. I suspect there may be more to it (which I would be interested in learning), and would very much like to find a reference, it makes me uncomfortable to use it in class without being able to point to its source.

The problem is as follows. I'll post the solution I know, which is the reason I like it, as an answer, to give a bit of a chance to people who read it and want to think about it without being spoiled.

Assume the natural numbers are partitioned into finitely many arithmetic progressions. Then two of these progressions must have the same common difference.

share|improve this question
3  
I find the generating function proof quite illuminating. It can be summarized as follows: arithmetic progressions have Fourier coefficients, and the nonzero Fourier coefficients of the natural numbers are all zero. But arithmetic progressions with pairwise distinct common differences have Fourier coefficients which are too different to sum to zero. –  Qiaochu Yuan May 20 '10 at 4:07
1  
What I wonder is if you can prove the same for any partition of a finite (not necessarily abelian) group into left cosets of some subgroups (the partition of $\mathbb Z$ is actually a partition of $\mathbb Z_N$ where $N$ is any common multiple of all differences). Here the generating function approach will meet some troubles. –  fedja May 20 '10 at 5:18
1  
@fedja, no. You can partition $S_3$ into cosets of the 2-element subgroups. That is, if $A$, $B$, and $C$ are the 2-element subgroups, then there are group elements $g$, $h$, and $k$ such that $S_3$ is the disjoint union of $gA$, $hB$, and $kC$. Also, if $G$ is any finitely generated abelian group of rank at least 3, finite or infinite, then you can partition $G$ into cosets of distinct subgroups. So far as I know, the question is wide open for abelian groups of rank 2. @Michael, yes, there is another proof, but I don't have access to my references. I'll try to look it up soon. –  Gerry Myerson May 20 '10 at 11:59
2  
@Michael, Zeilberger wrote up a history of the two proofs of the result. It's at emis.de/journals/EJC/Volume_8/PDF/v8i2a1.pdf –  Gerry Myerson May 20 '10 at 12:29
2  
There are a couple of papers by David Feldman, Jim Propp, and Sinai Robins (arXiv:0905.0441 (one page long) and arXiv:1006.0472) which treat a generalization to $\mathbb Z^d$. In the first paper, they give an example showing that the most obvious generalization to sublattices fails for dimension greater than or equal to three, and they prove a generalization where there is an additional assumption that the lattices are "straight", i.e. there is some basis with respect to which each of the lattices is generated by integer multiples of that same basis. –  Hugh Thomas Jun 3 '10 at 12:42
show 4 more comments

5 Answers

up vote 10 down vote accepted

You're probably thinking of the proof, via generating functions, due to D J Newman. I don't have a reference to the first appearance in print, but it's in his book, A Problem Seminar, problem 90, on page 18, with solution on page 100.

I suppose that when you state the problem you must require finitely many but at least two arithmetic progressions.

share|improve this answer
    
Hi Gerry. Oh, that was fast! Thanks! I guess I can at least start to track the problem down with your reference. –  Andres Caicedo May 20 '10 at 2:56
add comment

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

Now, since the $A_i$ partition ${\mathbb N}$, we have $\sum_{i=1}^n f_i(x)=1/(1-x)$. 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.

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

share|improve this answer
add comment

This is "the same" as the generating function proof, but it doesn't use generating functions explicitly. Take the largest common difference in any of the sequences, say n, and pick $\zeta$ a primitive n-th root of unity. To each positive integer $m$, associate the complex number $\zeta^m$. Note that in any arithmetic sequence with common difference less than n, the sum over its entries of $\zeta^m$ stays bounded, while for an arithmetic sequence of common difference n, it grows unboundedly. Since the sum over all integers stays bounded, there has to be a second sequence of common difference n to balance out the first one.

share|improve this answer
add comment

This was one of my favourite problems in high school. My proof went like this: if you look at the problem modulo n where n is the least common multiple of the differences of the arithmetic progressions then you can rephrase the problem as follows: if the vertices of a regular n-gon are partitioned into regular k-gons centered at the origin then two of them will have the same size. To prove this arrange the regular n-gon to have vertices at the nth roots of unity in the complex plane and assign the monic polynomial to every individual k-gon whose roots are exactly the vertices of the polygon. This way you will get the expression $x^n-1=(x^{k_1}-\zeta_1)(x^{k_2}-\zeta_2)\cdots$. Multiplying out the RHS we see that if $k_1$ is the least of the $k_i$'s then the only way to cancel the term of $x^{k_1}$ from the RHS is to have another $k_i=k_1$ proving the claim.

share|improve this answer
add comment

Chapter one of the Mathematical Coloring Book discuss this problem. There you will found some of its history. Apparently it was conjecture by Erdös in 1950 and proved (but not published) a few months later by Donald Newman and Leon Misrky.

share|improve this answer
    
Thanks! This book looks interesting, I'll have to take a careful look at it. –  Andres Caicedo May 20 '10 at 14:47
    
I've been reading the library copy of this book since you mentioned it. It is fascinating how unorthodox it is, I'll have to get one for myself. The remarks in the book surrounding the problem are also very interesting: The result was rediscovered in a completely different way, as a problem about coloring the vertices of a regular polygon, by N. B. Vasiliev, who suggested it as a problem in the IV Soviet Union National Olympiad, 1970. His solution had a mistake, and the judges spent the day prior to the competition trying to find a correct proof! Finally, A. Livshits found an argument. –  Andres Caicedo May 29 '10 at 5:56
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.