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 [math]\displaystyle{ \alpha, Q }[/math] realni brojevi i [math]\displaystyle{ Q \gt 1 }[/math], tada postoje cijeli brojevi [math]\displaystyle{ p, q }[/math] takvi da vrijedi [math]\displaystyle{ 1 \leq q \lt Q }[/math] te [math]\displaystyle{ ||q\alpha|| = |q\alpha - p| \leq \frac{1}{Q} }[/math].

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

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 [math]\displaystyle{ \frac{p}{q} }[/math] koji dobro aproksimira zadani iracionalni broj [math]\displaystyle{ \alpha }[/math].

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

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

Pitamo se koji je od racionalnih brojeva [math]\displaystyle{ \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 }[/math] najbliži broju [math]\displaystyle{ \alpha }[/math]. Neka je to [math]\displaystyle{ \left\lfloor\alpha\right\rfloor + \frac{k}{q} = \frac{p}{q} }[/math].

Očigledno je onda [math]\displaystyle{ |\alpha - \frac{p}{q}| \lt \frac{1}{2} \cdot \frac{1}{q} }[/math] jer je svaki podsegment duljine [math]\displaystyle{ \frac{1}{q} }[/math] pa [math]\displaystyle{ \alpha }[/math] 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 [math]\displaystyle{ \alpha }[/math] ne može biti udaljen od [math]\displaystyle{ \frac{p}{q} }[/math] za točno pola duljine posegmenta, odnosno [math]\displaystyle{ \frac{1}{2q} }[/math], jer je [math]\displaystyle{ \alpha }[/math] iracionalan.

Vidimo da ovime birajući broj [math]\displaystyle{ q }[/math] generiramo točno jedan [math]\displaystyle{ p }[/math] tako da je [math]\displaystyle{ d(\alpha, \frac{p}{q}) \lt \frac{1}{2q} }[/math].

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

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

Dokazat ćemo Dirichletov teorem u ekvivalentnom (skaliranom) obliku, dakle [math]\displaystyle{ |q\alpha - p| \lt \frac{1}{q}. }[/math]

Pomoćna lema

Neka imamo dva realna broja [math]\displaystyle{ x \lt y. }[/math] Tada je s brojevnog pravca očito da vrijedi [math]\displaystyle{ |x - y| = |\left\lfloor x \right\rfloor - \left\lfloor y \right\rfloor| \pm |\{x\} - \{y\}|. }[/math]

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

Primjer i dokaz

Uzmimo [math]\displaystyle{ \alpha = \sqrt{2}, Q = 100 }[/math].

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

Jasno je da je dovoljno promatrati razlomljene (decimalne) dijelove brojeva u skupu [math]\displaystyle{ S. }[/math]

U tu svrhu, promotrimo skup [math]\displaystyle{ S' = \{0, \{\sqrt{2}\}, \{2\sqrt{2}\}, ..., \{100\sqrt{2}\}\}. }[/math]

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

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

Prema tome, postoje barem dva [math]\displaystyle{ x, y \in \{0, 1, 2, ..., 100\}, x \neq y }[/math] takvi da je [math]\displaystyle{ 0 \leq |\{x\sqrt{2}\} - \{y\sqrt{2}\}| \lt \frac{1}{100} }[/math].

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

Kako je [math]\displaystyle{ 1 \leq |x - y| \leq Q = 100 }[/math] stavimo [math]\displaystyle{ q = |x - y| }[/math]. (Postojanje brojeva [math]\displaystyle{ x, y }[/math] očito dokazuje postojanje broja [math]\displaystyle{ q. }[/math])

Ovime smo dokazali da postoje [math]\displaystyle{ p, q \in \mathbb{Z}, 1 \leq q \leq 100 }[/math] takvi da je [math]\displaystyle{ |q\sqrt{2} - p| \lt \frac{1}{Q} = \frac{1}{100}. }[/math]

Zbog toga što je [math]\displaystyle{ 1 \leq q \leq Q = 100 }[/math] slijedi [math]\displaystyle{ \frac{1}{Q} = \frac{1}{100} \leq \frac{1}{q} }[/math]. Zato vrijedi [math]\displaystyle{ |q\sqrt{2} - p| \leq \frac{1}{100} \lt \frac{1}{q}. }[/math]

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

Slično, ako je pak [math]\displaystyle{ 1 \lt Q \lt Q' \lt Q + 1 }[/math] očito je [math]\displaystyle{ \frac{1}{Q'} \lt \frac{1}{Q} }[/math] pa teorem vrijedi i u tom slučaju.

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

Analogno se pokazuje za bilo koji [math]\displaystyle{ \alpha \geq 0, Q \gt 1, }[/math] a onda očito i za [math]\displaystyle{ \alpha \lt 0 }[/math].

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.