Dirichletov aproksimacijski teorem

Dirichletov aproksimacijski teorem jedan je od najvažnijih rezultata u teoriji brojeva, a izniče u njenoj disciplini pod nazivom diofantske aproksimacije, nazvane po starogrčkom matematičaru Diofantu.

Iskaz teorema glasi ovako.

Ako su $\alpha ,Q$ realni brojevi i $Q>1$, tada postoje cijeli brojevi $p,q$ takvi da vrijedi $1\leq q<Q$ te $||q\alpha ||=|q\alpha -p|\leq {\frac {1}{Q}}$.

Oznaka $||q\alpha ||$ predstavlja udaljenost od $q\alpha$ do njemu najbližeg cijelog broja. Dakle, općenito vrijedi $||\alpha ||={\text{min}}(\{{\alpha }\},1-\{{\alpha }\})$ gdje je $\{{\alpha }\}=\alpha -\left\lfloor \alpha \right\rfloor$ razlomljeni dio od $\alpha$.

Ovaj je teorem prvi dokazao njemački matematičar Dirichlet još 1842. godine.

Motivacija

Jedno od glavnih pitanja diofantskih aproksimacija je naći racionalan broj ${\frac {p}{q}}$ koji dobro aproksimira zadani iracionalni broj $\alpha$.

Osnovni postupak koji bismo mogli učiniti je da lociramo između koja dva prirodna broja se nalazi iracionalan broj $\alpha$. Jasno je da su ta dva tražena prirodna broja $\left\lfloor \alpha \right\rfloor ,\left\lfloor \alpha +1\right\rfloor$ pa se $\alpha$ očito nalazi u segmentu $I=[\left\lfloor \alpha \right\rfloor ,\left\lfloor \alpha +1\right\rfloor ]$.

No, ovo je prilično gruba aproksimacija. Za bolju, dijelit ćemo segment $I$ na sve više dijelova, tj. podintervala. Recimo da smo $I$ podijelili na točno $q\in \mathbb {N}$ jednakih dijelova.

Pitamo se koji je od racionalnih brojeva $\left\lfloor \alpha \right\rfloor +{\frac {1}{q}},\left\lfloor \alpha \right\rfloor +{\frac {2}{q}},...,\left\lfloor \alpha \right\rfloor +{\frac {q}{q}}=\left\lfloor \alpha \right\rfloor +1$ najbliži broju $\alpha$. Neka je to $\left\lfloor \alpha \right\rfloor +{\frac {k}{q}}={\frac {p}{q}}$.

Očigledno je onda $|\alpha -{\frac {p}{q}}|<{\frac {1}{2}}\cdot {\frac {1}{q}}$ jer je svaki podsegment duljine ${\frac {1}{q}}$ pa $\alpha$ mora biti udaljen od rubne točke podsegmenta u kojem pripada za manje od polovice njegove duljine. Valja uočiti da treba biti stroga nejednakost jer $\alpha$ ne može biti udaljen od ${\frac {p}{q}}$ za točno pola duljine posegmenta, odnosno ${\frac {1}{2q}}$, jer je $\alpha$ iracionalan.

Vidimo da ovime birajući broj $q$ generiramo točno jedan $p$ tako da je $d(\alpha ,{\frac {p}{q}})<{\frac {1}{2q}}$.

No, ovo nije naročito dobra aproksimacija. Na primjer, ako želimo da bude $d<{\frac {1}{10000}}$ trebamo za nazivnik uzeti čak $q=5000$ da bi ova aproksimacija uspjela.

Dirichletov će nam teorem dati puno bolje aproksimacije, $|\alpha -{\frac {p}{q}}|<{\frac {1}{q^{2}}}$, ali za manje parova $(p,q)$. Naime, želimo li da bude $d(\alpha ,{\frac {p}{q}})<{\frac {1}{10000}}$, Dirchletov teorem kaže da će postojati barem jedan broj $p$ za koji će ta aproksimacija uspjeti i to za nazivnike $q$ manje ili jednake $100.$

Dokazat ćemo Dirichletov teorem u ekvivalentnom (skaliranom) obliku, dakle $|q\alpha -p|<{\frac {1}{q}}.$

Pomoćna lema

Neka imamo dva realna broja $x<y.$ Tada je s brojevnog pravca očito da vrijedi $|x-y|=|\left\lfloor x\right\rfloor -\left\lfloor y\right\rfloor |\pm |\{x\}-\{y\}|.$

Dakle, vidimo da na udaljenosti $|\{x\}-\{y\}|$ od $|x-y|$ postoji prirodni broj, i to s obje strane broja $|x-y|.$

Primjer i dokaz

Uzmimo $\alpha ={\sqrt {2}},Q=100$.

Dakle, želimo dokazati da među brojevima u skupu $S=\{0,{\sqrt {2}},2{\sqrt {2}},3{\sqrt {2}},...,100{\sqrt {2}}\}$ postoji barem jedan koji je udaljen od nekog cijelog broja za manje od ${\frac {1}{Q}}={\frac {1}{100}}$.

Jasno je da je dovoljno promatrati razlomljene (decimalne) dijelove brojeva u skupu $S.$

U tu svrhu, promotrimo skup $S'=\{0,\{{\sqrt {2}}\},\{2{\sqrt {2}}\},...,\{100{\sqrt {2}}\}\}.$

Kako su svi članovi skupa $S'$ u segmentu $[0,1)$, podijelimo taj segment na 100 podintervala. Dobivamo $[0,{\frac {1}{100}}),[{\frac {1}{100}},{\frac {2}{100}}),...,[{\frac {99}{100}},1).$

Prema Dirichletovom principu je očito da barem dva broja (ili više) $\{x{\sqrt {2}}\},\{y{\sqrt {2}}\}$ iz $S$ pripadaju istom podintervalu.

Prema tome, postoje barem dva $x,y\in \{0,1,2,...,100\},x\neq y$ takvi da je $0\leq |\{x{\sqrt {2}}\}-\{y{\sqrt {2}}\}|<{\frac {1}{100}}$.

Prema pomoćnoj lemi slijedi da na udaljenosti $|\{x{\sqrt {2}}\}-\{y{\sqrt {2}}\}|$ od broja $x{\sqrt {2}}-y{\sqrt {2}}={\sqrt {2}}(x-y)$ postoji $p\in \mathbb {Z}$.

Kako je $1\leq |x-y|\leq Q=100$ stavimo $q=|x-y|$. (Postojanje brojeva $x,y$ očito dokazuje postojanje broja $q.$)

Ovime smo dokazali da postoje $p,q\in \mathbb {Z} ,1\leq q\leq 100$ takvi da je $|q{\sqrt {2}}-p|<{\frac {1}{Q}}={\frac {1}{100}}.$

Zbog toga što je $1\leq q\leq Q=100$ slijedi ${\frac {1}{Q}}={\frac {1}{100}}\leq {\frac {1}{q}}$. Zato vrijedi $|q{\sqrt {2}}-p|\leq {\frac {1}{100}}<{\frac {1}{q}}.$

Evidentno je da, uz to, mora biti $||q\alpha ||=|q{\sqrt {2}}-p|\leq {\frac {1}{100}}.$

Slično, ako je pak $1<Q<Q'<Q+1$ očito je ${\frac {1}{Q'}}<{\frac {1}{Q}}$ pa teorem vrijedi i u tom slučaju.

Jasno je da je nejednakost $|q{\sqrt {2}}-p|\leq {\frac {1}{100}}<{\frac {1}{q}},$ ekvivalentna s $|{\sqrt {2}}-{\frac {p}{q}}|\leq {\frac {1}{100q}}<{\frac {1}{q^{2}}},$ čime smo pokazali Dirichletov teorem u aproksimacijskom obliku sličnom uvodnom primjeru.

Analogno se pokazuje za bilo koji $\alpha \geq 0,Q>1,$ a onda očito i za $\alpha <0$.

Zanimljivosti

Dirichlet je u svome dokazu ovog teorema, po prvi puta koristio elementarnu i jednu od najvažnijih metoda u kombinatorici, poznatu pod nazivom Dirichletov princip (u nas još poznatu kao princip kutija ili pak u stranoj literaturi kao “princip pretinaca” i “princip golubinjaka”), koja upravo zato nosi njegovo ime.