# Set of the form $m + n \alpha$ is bounded by $0$?

Let $\alpha >0$ be an irrational number and consider

$$A = \{ m + n \alpha : m + \alpha n > 0 , \; \; \; m,n \in \mathbb{Z} \}$$

Obviously, $A$ is bounded below by $0$. But, how can I show that actually $\inf A = 0$ ?

This is just an amalgam of the other answers, with a little bit more explanation. You are basically showing the numbers $n\alpha$ are equidistributed modulo $1$.

Theorem (Dirichlet): For any real number $\alpha \in \mathbb{R}$ there exist integers $p,q \in \mathbb{Z}$ with $1 \leq q \leq N$ such that $|q\alpha - p| \leq \frac{1}{N+1}$

Historically, this is one of the original use of Pigeonhole principle.

Proof Among the $N+2$ numbers $\color{red}{\mathbf{0}}, \{ \alpha\}, \{ 2\alpha\}, \dots, \{ n\alpha\},\color{blue}{\mathbf{1}}$ two of them lie in the same interval of length $\frac{1}{N+1}$.

Don't forget 0 and 1 (like I do) or else you don't get enough room!

According to this MathOverflow post (Avoiding Minkowski's theorem in algebraic number theory) one can prove the Dirichlet Unit Theorem using just pigeonhole, in a style similar to your question.

Dirichlet did not have Minkowski’s theorem available; he proved the unit theorem in 1846, while Minkowski developed the geometry of numbers only near the end of the 19th century. His substitute for the convex-body theorem was the pigeonhole principle.

• Strictly speaking, this is a much weaker result than equidistribution - that states that the density is uniform over the unit interval, whereas this result just says that it's supported everywhere on the interval. – Steven Stadnicki Dec 12 '14 at 16:18

Assume there is an irrational $\beta\in A$ with $\beta<1$. Then we have $\beta':=1-\lfloor\frac1\beta\rfloor \beta\in A$ and $\beta''=\lceil\frac1\beta\rceil \beta-1\in A$ and both $\beta'$ and $\beta''$ are irrational. As $\beta'+\beta''=\beta$, one of them is $\le \frac12\beta$.

From $\lceil\alpha\rceil-\alpha\in A$ we conclude that indeed some irrational $<1$ is in $A$. By repeatedly doing the construction as in the first paragraph, starting with $\beta_0=\lceil\alpha\rceil-\alpha$ and recursively letting $\beta_{n+1}$ be the smaller of the numbers $\beta',\beta''$ constructed from $\beta=\beta_n$, we obtain a sequence with $\beta_n\le 2^{-n}\beta_0$. We conclude $\inf A\le \inf_n \beta_n\le 0$.

• I dont think you can assume what you say in your first sentence. – ILoveMath Dec 1 '14 at 22:52
• That's why later @Hagen later chooses $\beta_0 = \lceil \alpha \rceil - \alpha$; that is such an irrational number from which to start the procedure. – Simon S Dec 1 '14 at 22:55
• @FromCuba If I say assume then I do assume :) – Hagen von Eitzen Dec 1 '14 at 22:59
• This is a really sweet and direct argument. I guess that with @Marvin, I might have started with (1) $\lceil \alpha \rceil - \alpha \in A$ and is irrational, (2) for ANY irrational $\beta \in A$, one of $\beta', \beta''$ is irrational and less than $\beta/2$, and then have drawn the conclusion, so that the reader would know the discussion of $\beta$ was not vacuous, but that's a matter of taste, and Hagen's ideas are nice enough that I'm happy to let him exposit them in any order he likes. :) – John Hughes Dec 10 '14 at 13:17

It's a "well known fact" that the set $\{n\alpha \mod 1\ |\ n \in \mathbb N \}$ is dense in $[0,1].$ See, for example, here
So, given $\epsilon > 0,$ we can pick an $n \in \mathbb N$ such that $0 < n\alpha \mod 1 < \epsilon.$ Then put $m = -[n\alpha],$ i.e. the negative integer part of $n\alpha.$ Then we have $m \in \mathbb Z,$ and $m+n\alpha = (n\alpha \mod 1),$ and thus $0 < m+n\alpha < \epsilon,$ and of course $m+n\alpha \in A.$ As $\epsilon > 0$ is arbitrary, this shows $\inf A =0,$ as desired.

This question has already been well-answered (in particular let me include a link to this answer to a related question), but I have my favorite way of doing it, so here we go.

It is enough to show that the set $B = \{ m + n \alpha : m,n \in \mathbb{Z} \} = \Bbb Z+\alpha\Bbb Z$ is dense in the real line $\Bbb R$.
(The set $B$ is defined like $A$ but without the restriction that $m + \alpha n > 0$.)
Notice that $B=D$ where $D=\{a-b: a,b\in\Bbb Z+\alpha\Bbb Z\}=\{a-b: a,b\in B\}=B-B$.
Also $\Bbb Z\subset B$ and $\alpha\in B$, hence $\varepsilon\in B$ where $\varepsilon$ is the distance from $\alpha$ to the nearest integer, and
hence $0<\varepsilon<1$.

Now let $r=\inf A$. Assume (for a contradiction) that $r>0$.

Case 1. $r\not\in A$. Then, by definition of $\inf$, there are (distinct) elements of $A$ (and hence of $B$) that are arbitrarily close to $r$, and hence arbitrarily close to each other. Since the differences between such elements are in $D=B$, it follows that $B$ contains arbitrarily small positive elements, and hence $B$ is dense in $\Bbb R$, using also that $B=\Bbb Z B =\{j b: j\in\Bbb Z, \ b\in B\}$.

Case 2. $r\in A$. Then $0<r\le\varepsilon<1$, hence $r=m+n\alpha$ with $n\not=0$ and $r$ is irrational. There is $k\in\Bbb Z$ with $k\ge 1$ and $k r<1<(k+1)r$. But then $1-kr\in D=B$ and $0<1-kr<(k+1)r-k r = r$, so $1-kr\in A$, contradicting the minimality of $r$ in $A$.

My favorite proof is by the pigeonhole principle, and moreover it's effective, in that it tells you you can get within $1/N$ of zero with $|n| \leq N$.

For every $n$, there's a unique $m$ such that $0< m+n\alpha < 1$. This is $\{n\alpha\}$, the fractional part of $n\alpha$.

Split $[0,1]$ into $N$ bins of length $1/N$.

By the pigeonhole principle, at least two $\{n\alpha\}$'s are in the same bin with $1\leq n \leq N+1$.

Then their positive difference is less than $1/N$, and is of the form $m+n\alpha$ with $|n| \leq N$.

Edit: In fact, including 0 and 1 as in another answer, we see we can get within $1/N$ with $|n| \leq N-1$. Also, with nonnegative $0 \leq n \leq N-1$ we can get $|\{n\alpha\}| \leq 1/N$, but this is slightly different than what was asked.