Finitely many arithmetic progressions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T01:32:21Z http://mathoverflow.net/feeds/question/25313 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/25313/finitely-many-arithmetic-progressions Finitely many arithmetic progressions Andres Caicedo 2010-05-20T02:46:27Z 2010-09-13T16:06:15Z <p>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. </p> <p>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.</p> <p>Assume the natural numbers are partitioned into finitely many arithmetic progressions. Then two of these progressions must have the same common difference. </p> http://mathoverflow.net/questions/25313/finitely-many-arithmetic-progressions/25315#25315 Answer by Gerry Myerson for Finitely many arithmetic progressions Gerry Myerson 2010-05-20T02:52:17Z 2010-05-20T02:52:17Z <p>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. </p> <p>I suppose that when you state the problem you must require finitely many but <em>at least two</em> arithmetic progressions. </p> http://mathoverflow.net/questions/25313/finitely-many-arithmetic-progressions/25317#25317 Answer by Andres Caicedo for Finitely many arithmetic progressions Andres Caicedo 2010-05-20T02:54:27Z 2010-05-20T02:54:27Z <p>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|&lt;1$.</p> <p>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.</p> <p>This shows that the <em>largest</em> of the common differences must appear at least twice. </p> http://mathoverflow.net/questions/25313/finitely-many-arithmetic-progressions/25322#25322 Answer by Hugh Thomas for Finitely many arithmetic progressions Hugh Thomas 2010-05-20T04:13:41Z 2010-05-20T04:13:41Z <p>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. </p> http://mathoverflow.net/questions/25313/finitely-many-arithmetic-progressions/25340#25340 Answer by Tamas Hausel for Finitely many arithmetic progressions Tamas Hausel 2010-05-20T10:21:47Z 2010-05-20T10:21:47Z <p>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. </p> http://mathoverflow.net/questions/25313/finitely-many-arithmetic-progressions/25347#25347 Answer by jvp for Finitely many arithmetic progressions jvp 2010-05-20T11:44:46Z 2010-05-20T11:44:46Z <p>Chapter one of the <a href="http://books.google.com.br/books?id=Vn3GLf-4YkEC&amp;printsec=frontcover&amp;dq=the+mathematical+coloring+book&amp;source=bl&amp;ots=mUwuVkZiyW&amp;sig=u0bqVVQEtAEz5V8b4fAUpuK57_k&amp;hl=pt-BR&amp;ei=bx71S8rhH86HuAf7vsy_CA&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=4&amp;ved=0CDIQ6AEwAw#v=onepage&amp;q&amp;f=false" rel="nofollow">Mathematical Coloring Book</a> 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. </p>