Explanation for Concrete Mathematics 3.38's solution

Question

I'm working on the exercises in Concrete Mathematics recently. In Exercise 3.38, one of the key points is to prove that:

For any real numbers $x,\ y \in (0,\ 1)$，$\exists n \in \mathbf{N}^+$ such that $\{nx\} + \{ny\} \geqslant 1$, where $\{x\}$ represents the fractional part of $x$ i.e. $\{x\} = x - \lfloor x \rfloor$.

Actually, I have known the method to prove it, but I just can't understand what the answer said:

I wonder why Dirichlet's box principle works and how $\vert P_k - P_j\vert < \epsilon$ is related to $P_{k - j - 1} \in B$.

I would appreciate it if someone could offer a clearer explanation.

Answer 1

Hint.

Consider the numbers represented in base $2$

$$ n = \sum_{k=0}^m a_k 2^k \\ x = \sum_{k=1}^p b_k 2^{-k}\\ y = \sum_{k=1}^q c_k 2^{-k}\\ $$

with $a_k,b_k,c_k \in\{0,1\}$ and then compare

$$ \{nx\} + \{ny\} =\frac{a_0 b_1}{2}+\frac{a_0c_1}{2}+\frac{a_1b_2}{2}+\frac{a_1 c_2}{2}+\frac{a_2 b_3}{2}+\frac{a_2c_3}{2}+\frac{a_3 b_4}{2}+\frac{a_3 c_4}{2}+\frac{a_0 b_2}{4}+\frac{a_0 c_2}{4}+\frac{a_1 b_3}{4}+\frac{a_1c_3}{4}+\frac{a_2 b_4}{4}+\frac{a_2 c_4}{4}+\frac{a_0 b_3}{8}+\frac{a_0 c_3}{8}+\frac{a_1 b_4}{8}+\frac{a_1 c_4}{8}+\frac{a_0b_4}{16}+\frac{a_0 c_4}{16}+\cdots + $$

with $ 1$

Here $a_0,a_1,a_2,\cdots, a_k ,\cdots, $ are for our choice (decision variables)

NOTE

Suffices that three of the products divided by $2$ are non null which is ever possible choosing conveniently the $a_k$'s

Answer 2

If we keep finding points $P_i$ and drawing disk $D$ of radius $\epsilon$ centered at $P_i$, then either there will be two points $P_k$ and $P_j$ within a distance $\epsilon$ of each other so that $|P_k-P_j|<\epsilon$ OR eventually the disks will cover the whole region with the distance between any two $P_i$'s exceeding $\epsilon$. But then the next point $P$ must lie on one of the disks and so we would then have found $P_k$ and $P_j$ such that $|P_k-P_j|<\epsilon$.

Answer 3

The important step that this book has skipped this time is the following fact: $$\{P_m + P_n\}$$ $$= (\{\{mx\} + \{nx\}\}, \{\{my\} + \{ny\}\})$$ $$= (\{(m+n)x\}, \{(m+n)y\})$$ $$= P_{m+n}$$ where $\{P_m\}$ represents the point with the fractional part applied to each coordinate.

Note that $P_{-1} = (1,1) - P_1$. But this is not the point we are looking for because the subscript must be positive. $P_{-1 + k - j}$ is actually the point we need, and we can prove that its distance to $P_{-1}$ is less than $\epsilon$.

$$ |P_{-1 + k - j} - P_{-1}| $$ $$ = |\{ P_{-1} + P_k - P_j\} - P_{-1}|$$ $$ = |P_{-1} + P_k - P_j - P_{-1}|$$ $$ = |P_k - P_j| < \epsilon$$

In the second step, the fractional part can be eliminated because we know that $P_k - P_j$ has at most magnitude $\epsilon$. By construction, the disk $D$ centered at $P_1$ with radius $\epsilon$ is completely contained in $A$. Finally, $P_{-1}$ is symmetric to $P_1$, so the disk centered at $P_{-1}$ is completely contained in $B$. This means that $P_{-1} + P_k - P_j$ is still contained in the square from $0$ to $1$ and therefore the fractional part has no effect.