# Proving a set of numbers has arithmetic progressions of arbitrary length, but none infinite

For each real number $x$, let $[x]$ be the largest integer less than or equal to $x$. For example, $$[5] = 5$$

$$[7.9] = 7,$$ and $$[−2.4] = −3.$$

An arithmetic progression of length $k$ is a sequence $a_1, a_2, \dots, a_k$ with the property that there exists a real number $b$ such that $a_{i+1} − a_i = b$ for each $1 \leq i \leq k − 1.$

Let $\alpha > 2$ be a given irrational number. Let $S = \{[n · α] : n ∈ Z\}$, the set of all integers that are equal to $[n \alpha]$ for some integer $n$.

(a) Prove that for any integer $m \geq 3$, there exist m distinct numbers contained in $S$ which form an arithmetic progression of length $m$.

(b) Prove that there exist no infinite arithmetic progressions contained in $S$.

I'm thinking that for (a), some application pigeonhole principle can be considered... but otherwise, I don't really know how to prove this.

Some suggestions on a strategy would be awesome. Thanks.

• How familiar are you with the proof that the set of fractional parts $\{\{n\alpha\}\}_{n \in \mathbb N}$ is dense in the unit interval? – Erick Wong Aug 18 '14 at 3:15
• Not very familiar at all... – user164403 Aug 18 '14 at 14:14
• By the way, how does this relate to Number Theory? I know only very elementary Number Theory, so just wondering if there are some good books that cover these types of Number Theory questions. – user164403 Aug 18 '14 at 15:50

Outline: We want to construct an arithmetic sequence of length $n$ that is a subsequence of the sequence $(\lfloor i\alpha\rfloor)$.

For $i=1,2,3, \dots, 10n+1$, let $b_i$ be the fractional part of $i\alpha$, that is, $i\alpha-\lfloor i\alpha\rfloor$. These fractional parts are all distinct, since $\alpha$ is irrational. By the Pigeonhole Principle, there exist $i$ and $j$ with $i\lt j$ such that $|b_j-b_i|\lt \frac{1}{10n}$. Let $k=j-i$. Then either (i) $b_k\gt 1-\frac{1}{10n}$ or (i) $b_k\lt \frac{1}{10n}$.

We look first at case (i). Consider the numbers $k\alpha$, $2k\alpha$, $3k\alpha$ and so on up to $nk\alpha$. The fractional parts of these are slowly decreasing. Thus the numbers $\lfloor k\alpha\rfloor$, $\lfloor 2k\alpha\rfloor$, $\lfloor 3k\alpha\rfloor$, and so on up to $\lfloor nk\alpha\rfloor$ form an arithmetic progression of length $n$. There is a lot of slack, we can continue well beyond $\lfloor nk\alpha\rfloor$.

Case (ii) is essentially the same, except that the fractional parts of the $ik\alpha$ slowly increase instead of decreasing.

The argument that our sequence has no infinite arithmetic progression uses similar ideas.

• Would it be essential to apply the Pigeonhole Principle? I'm not used to using it, so I'm just wondering if there are other ways. Also, when do you know that a problem uses the Pigeonhole Principle? Is there anything that 'ticks', and you know that you have to use the Pigeonhole Principle? Are there any clues that show this in the question when not explicitly stated? – user164403 Sep 6 '14 at 4:19
• Well, I guess we do not have to mention the Pigeonhole Principle explicitly. But we will have to use it implicitly, since the $\alpha$ is general. It comes up whenever we are interested in the distribution of fractional parts. Here it was integer parts, but the technique was worth trying, and works. An indication that Pigeonhole might be useful is if the problem says that a set has more than $k$ elements, then a certain nice thing happens. The problem above, however, does not really have that shape. – André Nicolas Sep 6 '14 at 5:20
• What type of math is this? I'm very interested in it and would like to learn more by checking out resources pertaining to that aspect of math. – user164403 Sep 30 '14 at 3:42
• It belongs, more or less, to Diophantine Approximation. – André Nicolas Sep 30 '14 at 3:45
• Are there any good books on those kinds of questions? This question was from a Math Challenge, and this challenge stated that to prepare, one should go over such topics as sequences and series, which I thought was to be in real analysis. – user164403 Sep 30 '14 at 16:40