Dirichletov teorem

Dirichletov teorem je jedan 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, Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |\alpha -{\frac {p}{q}}|<{\frac {1}{q^{2}}}} , ali za manje parova Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (p,q)} . Naime, želimo li da bude Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 100.}

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

Pomoćna lema

Neka imamo dva realna broja Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x<y.} Tada je s brojevnog pravca očito da vrijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |x-y|=|\left\lfloor x\right\rfloor -\left\lfloor y\right\rfloor |\pm |\{x\}-\{y\}|.}

Dakle, vidimo da na udaljenosti Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |\{x\}-\{y\}|} od Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |x-y|} postoji prirodni broj, i to s obje strane broja $|x-y|.$

Primjer i dokaz

Uzmimo Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \alpha ={\sqrt {2}},Q=100} .

Dakle, želimo dokazati da među brojevima u skupu Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\frac {1}{Q}}={\frac {1}{100}}} .

Jasno je da je dovoljno promatrati razlomljene (decimalne) dijelove brojeva u skupu Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle S.}

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

Kako su svi članovi skupa $S'$ u segmentu Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle [0,1)} , podijelimo taj segment na 100 podintervala. Dobivamo Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle [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) Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \{x{\sqrt {2}}\},\{y{\sqrt {2}}\}} iz $S$ pripadaju istom podintervalu.

Prema tome, postoje barem dva Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |\{x{\sqrt {2}}\}-\{y{\sqrt {2}}\}|} od broja Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x{\sqrt {2}}-y{\sqrt {2}}={\sqrt {2}}(x-y)} postoji Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p\in \mathbb {Z} } .

Kako je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 1\leq |x-y|\leq Q=100} stavimo Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q=|x-y|} . (Postojanje brojeva $x,y$ očito dokazuje postojanje broja $q.$)

Ovime smo dokazali da postoje Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p,q\in \mathbb {Z} ,1\leq q\leq 100} takvi da je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |q{\sqrt {2}}-p|<{\frac {1}{Q}}={\frac {1}{100}}.}

Zbog toga što je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 1\leq q\leq Q=100} slijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle ||q\alpha ||=|q{\sqrt {2}}-p|\leq {\frac {1}{100}}.}

Slično, ako je pak Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 1<Q<Q'<Q+1} očito je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\frac {1}{Q'}}<{\frac {1}{Q}}} pa teorem vrijedi i u tom slučaju.

Jasno je da je nejednakost Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \alpha \geq 0,Q>1,} a onda očito i za Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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.