3
$\begingroup$

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

$\endgroup$
1
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Steven Stadnicki Dec 12 '14 at 16:18
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I dont think you can assume what you say in your first sentence. $\endgroup$ – ILoveMath Dec 1 '14 at 22:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Simon S Dec 1 '14 at 22:55
  • 1
    $\begingroup$ @FromCuba If I say assume then I do assume :) $\endgroup$ – Hagen von Eitzen Dec 1 '14 at 22:59
  • $\begingroup$ 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. :) $\endgroup$ – John Hughes Dec 10 '14 at 13:17
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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