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\le q<Q$ te $||q\alpha ||=|q\alpha -p|\le \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 -\lfloor \alpha \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 $\lfloor \alpha \rfloor ,\lfloor \alpha +1\rfloor$ pa se $\alpha$ očito nalazi u segmentu $I=[\lfloor \alpha \rfloor ,\lfloor \alpha +1\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 $\lfloor \alpha \rfloor +\frac{1}{q},\lfloor \alpha \rfloor +\frac{2}{q},...,\lfloor \alpha \rfloor +\frac{q}{q}=\lfloor \alpha \rfloor +1$ najbliži broju $\alpha$. Neka je to $\lfloor \alpha \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|=|\lfloor x\rfloor -\lfloor y\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^{\prime }=\{0,\{\sqrt{2}\},\{2\sqrt{2}\},...,\{100\sqrt{2}\}\}.$

Kako su svi članovi skupa $S^{\prime }$ 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\ne y$ takvi da je $0\le |\{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\le |x-y|\le 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\le q\le 100$ takvi da je $|q\sqrt{2}-p|<\frac{1}{Q}=\frac{1}{100}.$

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

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

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

Jasno je da je nejednakost $|q\sqrt{2}-p|\le \frac{1}{100}<\frac{1}{q},$ ekvivalentna s $|\sqrt{2}-\frac{p}{q}|\le \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 \ge 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.