Please take a look at my proof on Dirichlet's theorem

152 Views Asked by At

General/simultaneous Dirichlet's theorem : If $α_1,\dots,α_m\in \mathbb R$ and $n\ge 1$ is an integer, then there are integers $p_1,\dots,p_m$ and there exists an integer $q$ with $1\le q\le N^m$ such that $\left|x_j-\frac {p_j}q\right|<\frac 1{qN}$.

I have not found a good proof of it online so here is my own proof using pigeonhole principle please correct me if i have any mistakes:

To show that for any real α,β and any positive integer n, there are integers p and p′, and an integer q satisfying 1 ≤ q ≤ $n^2$, we can prove it by proving a stronger result that if $α_1,\dots,α_m\in \mathbb R$ and $n\ge 1$ is an integer, then there are integers $p_1,\dots,p_m$ and there exists an integer $q$ with $1\le q\le n^m$ such that $\left|x_j-\frac {p_j}q\right|<\frac 1{qn}$.

Using the notation $$x=(x_1,\dots,x_m)$$ and $$\{k\cdot x\}=(\{kx_1\},\dots,\{kx_m\})$$. We can consider $n^m+1$ vectors $(\{kx_1\},\dots,\{kx_m\})$, $k=0,\dots, n^m$ in the unit cube $[0,1)^m$ divided into $n^m$ equal subcubes.

Consider the fractional parts $\{0\cdot x\},\{1\cdot x\}, \{2\cdot x\},\dots, \{n^m\cdot x\}$. They all belong to the the unit cube $[0,1)^m$.

We can split the cube by splitting each edge into $n$ subintervals and form a grid:

$$[0,1)^m=\bigcup_{(j_1,\dots,j_m)\in\{1,\dots,n\}^m } [\frac{j_1-1}{n},\frac{j_1}{n})\times\dots\times [\frac{j_m-1}{n},\frac{j_m}{n})$$

Each small cube is an $m$-dimensional cube whose sides are open intervals of size $1/n$.

Since we have $n^m+1$ pigeons/vectors and only $n^m$ holes (as we have $m$-dimensional cube whose sides are open intervals of size $1/n$, so n subintervals in total), the pigeonhole principle implies that there are distinct k, l, with $0\le k<\ell\le n^m$ such that $$\{k\cdot x\}=(\{kx_1\},\dots,\{kx_m\}),$$ $$\{l\cdot x\}=(\{lx_1\},\dots,\{lx_m\})$$are in the same small cube.

This implies in particular that $|\{kx_i\}-\{lx_i\}|<1/n$, so there is some integer $p_i$ such that $|(k-l)x_i-p_i|<1/n$. So, making $q=|k-l|$, we get $|x_i-p_i/q|<1/nq$. (*)

Thus if $α_1,\dots,α_m\in \mathbb R$ and $n\ge 1$ is an integer, then there are integers $p_1,\dots,p_m$ and there exists an integer $q$ with $1\le q\le n^m$ such that $\left|x_j-\frac {p_j}q\right|<\frac 1{qn}$ when we list out (*), i.e. all $|\{kx_i\}-\{lx_i\}|<1/n$ for i between 1 and m (including 1 and m).

This directly proves our problem when we make m=2.

1

There are 1 best solutions below

11
On BEST ANSWER

The idea is in the right direction, but there are a lot of mistakes in terms of notation which makes feel that the logic doesn't make sense at some moment. I'll point out the mistakes here and you can correct them. You are using $N$ unnecessarily. Your $n$ is the same as your $N$ (I'll use $n$) The same with $\alpha_i$, this is the same as $x_i$(I'll use $x_i$)

First, I think you are using the notation $$x=(x_1,\dots,x_m)$$ and $$\{k\cdot x\}=(\{kx_1\},\dots,\{kx_m\})$$

Second, the way you split your big cube is not correct (it doesn't make sense). The way you have to split your cube is by splitting each edge into $n$ subintervals and form a grid. So, the correct way to split it is $$[0,1)^m=\bigcup_{(j_1,\dots,j_m)\in\{1,\dots,n\}^m } [\frac{j_1-1}{n},\frac{j_1}{n})\times\dots\times [\frac{j_m-1}{n},\frac{j_m}{n})$$ Each small cube is an $m$-dimensional cube whose sides are open intervals of size $1/n$.

Now as you said, by Pigeon hole principle there are distinct $k,l$ such that $$\{k\cdot x\}=(\{kx_1\},\dots,\{kx_m\}),$$ $$\{l\cdot x\}=(\{lx_1\},\dots,\{lx_m\})$$are in the same small cube. This implies in particular that $|\{kx_i\}-\{lx_i\}|<1/n$, so there is some integer $p_i$ such that $|(k-l)x_i-p_i|<1/n$. So, making $q=|k-l|$, you get $|x_i-p_i/q|<1/nq$.