Kezdőlap


Cím:	Rácspontok a körben
Szerző(k):	Ruzsa Z. Imre
Füzet:	1999/január, 1 - 8. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A számsíkon az egész koordinátájú pontokat rácspontoknak nevezzük. Megpróbáljuk megmondani, hány rácspont van az origú középpontú, $r$ sugarú körben. Ezt a számot a továbbiakban $N (r)$ fogja jelölni.
Mivel általában egységnyi területre esik egy rácspont, azt várjuk, hogy $N (r)$ körülbelül akkora lesz, mint a kör területe, vagyis $π r^{2}$ . Ez a gondolat az alábbi módon önthető egzakt formába. Minden egyes rácspont köré írjunk a tengelyekkel párhuzamos oldalú egységnégyzetet. Ezek hézagtalanul lefedik a síkot. Ha közülük csak azokat tekintjük, amelyek középpontja az $r$ sugarú körbe esik, ezek összterülete éppen $N (r)$ . Mivel egy ilyen négyzet pontjainak legnagyobb távolsága a négyzet középpontjától $\frac{\sqrt[]{2}}{2}$ , a fenti alakzat benne lesz az origó körüli $r + \frac{\sqrt[]{2}}{2}$ sugarú körben. Hasonlóan, mivel a körön kívüli középpontú négyzetek csak $\frac{\sqrt[]{2}}{2}$ mélységig tudnak a körbe benyúlni, alakzatunk tartalmazza az $r - \frac{\sqrt[]{2}}{2}$ sugarú kört. Így

\begin{matrix} π {(r - \frac{\sqrt[]{2}}{2})}^{2} \leq N (r) \leq π {(r + \frac{\sqrt[]{2}}{2})}^{2}, \end{matrix}

vagyis a

Δ (r) = N (r) - π r^{2}

jelöléssel

\begin{matrix} | Δ (r) | \leq \sqrt[]{2} π r + \frac{1}{2} < 5 r . \end{matrix}

(1.1)

Ez az érvelés alig használt valamit a kör tulajdonságaiból, és csipetnyi változtatással szinte minden alakzatra elmondható. Vessük össze pl. a kört a köré írt,

2 r

oldalú négyzettel. Ennek területe

4 r^{2}

, és azon rácspontok vannak benne, amelyek koordinátái 0,

\pm 1

\pm 2

...

\pm [r]

, számuk

{(2 [r] + 1)}^{2}

. A terület és a rácspontok száma különbsége ekkor

\begin{matrix} Δ^{*} (r) = {(2 [r] + 1)}^{2} - 4 r^{2} = 4 r (1 - 2 {r}) + {(1 - 2 {r})}^{2} . \end{matrix}

Mivel

r

0 és 1 között változik,

(1 - 2 {r})

bármi lehet

- 1

és 1 között,

Δ^{*} (r)

pedig

- (4 r - 1)

és

4 r + 1

között van, a felső határt néha (

r

egész értékeinél) felvéve, az alsót csak megközelítve. Ilyen általános gondolatmenettől tehát lényegesen jobb eredményt nem várhatunk.
Annak okát, hogy a négyzetnél ekkora eltérés lehet a terület és a rácspontok száma között, abban vélhetjük fellelni, hogy amikor

r

áthalad egy egész számon, a rácspontok száma egyszerre

8 r

-et ugrik. Szemléletünk azt sugallja, hogy a kör ilyen disznóságot nem csinál. A körvonalra eső rácspontok száma, vagyis azon

(x, y)

egész számpárok száma, amelyekre

\begin{matrix} x^{2} + y^{2} = r^{2} \end{matrix}

(1.2)

felírható képlettel, mégpedig az alábbi módon. Ilyen pont persze csak akkor van, ha

r^{2} = n

is egész szám. Bontsuk fel

n

-et prímtényezőkre, különválasztva a 2-t, a

4 k + 1

és

4 k - 1

alakú prímeket:

\begin{matrix} n = 2^{a} p_{1}^{b_{1}} ... p_{k}^{b_{k}} q_{1}^{c_{1}} ... q_{l}^{c_{l}}, p_{i} \equiv 1 (mod 4), q_{j} \equiv 3 (mod 4) . \end{matrix}

E jelölésekkel az (1.2) egyenlet megoldásainak száma,

ϱ (n) = 0

, ha a

c_{j}

számok között van páratlan, és

\begin{matrix} ϱ (n) = 4 (b_{1} + 1) ... (b_{k} + 1), \end{matrix}

(1.3)

ha az összes

c_{j}

páros. Erről a

ϱ (n)

mennyiségről belátható, hogy nemcsak

r = \sqrt[]{n}

-nél lesz kisebb, de

n

akármilyen kicsi pozitív kitevőjű hatványánál is, ha

n

elég nagy. Ha tehát csak ezen múlna,

Δ (r)

lehetne kisebb, mint

r^{ε}

akármilyen kicsi pozitív

ε

-nal.
A valóság kevésbé idilli; be lehet látni, hogy

\begin{matrix} {lim sup}_{}^{} \frac{| Δ (r) |}{\sqrt[]{r}} = \infty . \end{matrix}

(1.4)

A továbbiakban megmutatjuk, hogyan lehet elemi geometriai eszközökkel (kihasználva, hogy a kör nem szögletes) túllépni (1.1)-en, és belátni, hogy

\begin{matrix} | Δ (r) | < C r^{2 / 3} \end{matrix}

(1.5)

alkalmas

C

konstanssal.

2. Bizonyítás

A továbbiakhoz bevezetjük az alábbi konvenciót:

c

, indexszel vagy anélkül, pozitív konstanst jelöl (amelyet kiszámolhatnánk, de nem tesszük); a ,,van olyan pozitív

c

, hogy" szavakat tehát elblicceljük.
A rácspontok alábbi tulajdonságai, amelyeket használni fogunk, fellelhetők az Erdős‐Surányi könyv 4. fejezetében. ^{$^{*}$}Erdős Pál, Surányi János: Válogatott fejezetek a számelméletből, Polygon könyvtár, Szeged, 1996.
Ha egy egyenesen legalább két rácspont van, akkor már végtelen sok van, és ezek egyenlő távolságban követik egymást (az ilyen egyenes neve rácsegyenes). Ha ez a távolság

v

, akkor az egyenessel párhuzamos rácsegyenesek egymást

\frac{1}{v}

távolságban követik.
Rácssokszögek azon egyszerű sokszögek, amelyeknek minden csúcsa rácspont. Ezek területe és a bennük lévő rácspontok száma között az alábbi kapcsolat van:

\begin{matrix} T = B + \frac{H}{2} - 1, \end{matrix}

(2.1)

ahol

T

a terület,

B

a sokszög belsejében,

H

pedig a határán lévő rácspontok száma.
A (2.1) képletet írjuk fel a körben lévő legnagyobb rácssokszögre, vagyis a körben lévő rácspontok konvex burkára. Tegyük még hozzá, hogy a keresett szám

\begin{matrix} N (r) = B + H, \end{matrix}

és a kör területe

\begin{matrix} π r^{2} = T + T', \end{matrix}

ahol

T'

a sokszög és a körvonal közti sáv területe. A fentiekből

\begin{matrix} Δ (r) = \frac{H}{2} + 1 - T'; \end{matrix}

(1.5) bizonyításához tehát elég belátni, hogy

\begin{matrix} \begin{matrix} H & < c_{1} r^{2 / 3} & (2.2) \\ és \\ T' & < c_{2} r^{2 / 3} . & (2.3) \end{matrix} \end{matrix}

A továbbiakban bebizonyítjuk (2.2)-t, és vázoljuk (2.3) bizonyítását. Legyen

k

a sokszög oldalainak száma. Egy oldalt a rajta levő rácspontok egyenlő szakaszokra osztanak; legyen

n_{i}

i

-edik oldalon levő szakaszok száma (tehát

n_{i} - 1

belső pont van az oldalon; ha csak a két csúcspont van, akkor

n_{i} = 1

). A két szomszédos osztópontot összekötő vektor legyen

{\vec{v}}_{i}

, ennek hossza

v_{i}

; az oldal hossza tehát

n_{i} v_{i}

, (1. ábra) a sokszög kerülete pedig

\begin{matrix} \sum_{}^{} n_{i} v_{i} \leq 2 π r \end{matrix}

(2.4)

(miért is?).

Az oldalegyenes által meghatározott húr hossza legyen

l_{i}

, a (kisebbik, a sokszögön kívül eső) körszelet magassága pedig

h_{i}

. Az

l_{i}

hosszú húrt a rácspontok

n_{i} + 2

részre osztják, amelyek közül a középső

n_{i}

hossza

v_{i}

, a két szélsőé kisebb, így

\begin{matrix} n_{i} v_{i} \leq l_{i} < (n_{i} + 2) v_{i} \leq 3 n_{i} v_{i} . \end{matrix}

(2.5)

A továbbiakban az

i

indexeket általában elhagyjuk.
Eddig nem használtuk ki, hogy nem akármilyen rácssokszög van a körben, hanem a lehető legnagyobb. Ezt pedig így tehetjük meg. Húzzuk meg az oldallal párhuzamos szomszédos rácsegyenest, mégpedig a kör középpontjától távolabbit (2. ábra). Ennek távolsága az oldalegyenestől

\frac{1}{v}

. Ha

h > \frac{1}{v}

, akkor ez metszi a kört, és egy olyan körszeletet vág le, amelynek magassága

\begin{matrix} h' = h - \frac{1}{v} . \end{matrix}

A húr hossza Püthagorasz tételéből számolható:

\begin{matrix} r^{2} = {(\frac{l}{2})}^{2} + {(r - h)}^{2} = {(\frac{l'}{2})}^{2} + {(r - h')}^{2}, \end{matrix}

(2.6)

tehát

\begin{matrix} \frac{l^{2} - l^{' 2}}{4} = {(r - h')}^{2} - {(r - h)}^{2} = (h - h') (2 r - h - h') = \frac{1}{v} (2 r - h - h') < \frac{2 r}{v} . \end{matrix}

Számolás nélkül is észrevehetjük viszont, hogy

l' < v

, hiszen a rácspontok egymást

v

távolságban követik, és erre a húrra nem jut rácspont. Emiatt

\begin{matrix} l^{2} < l^{' 2} + \frac{8 r}{v} < v^{2} + \frac{8 r}{v} . \end{matrix}

(2.7)

h \leq \frac{1}{v}

, akkor ez az egyenes a kört nem metszi. (2.7) ekkor is igaz, mert

\begin{matrix} l^{2} = 4 (r^{2} - {(r - h)}^{2}) = 4 h (2 r - h) < 8 r h \leq \frac{8 r}{v} . \end{matrix}

Mivel

l \geq n v

, ezért (2.7) azt adja, hogy

\begin{matrix} (n^{2} - 1) v^{2} \leq \frac{8 r}{v} . \end{matrix}

(2.8)

Innen

\begin{matrix} n^{2} \leq \frac{8 r}{v^{3}} + 1. \end{matrix}

(2.9)

Foglalkozzunk először azokkal az oldalakkal, ahol

v < 2 r^{1 / 3}

. Itt (2.9)-ben az első tag a nagyobb, és így

n^{2} \leq \frac{16 r}{v^{3}}

n \leq \frac{4 r^{1 / 2}}{v^{3 / 2}}

.

Legyen

\begin{matrix} H_{1} = \sum_{v_{i} < 2 r^{1 / 3}}^{} n_{i}; \end{matrix}

ekkor tehát

\begin{matrix} H_{1} < 4 \sqrt[]{r} \sum_{v_{i} < 2 r^{1 / 3}}^{} v_{i}^{- 3 / 2} \leq 4 \sqrt[]{r} \sum_{v < 2 r^{1 / 3}}^{} v^{- 3 / 2}, \end{matrix}

(2.10)

ahol a második összegzés az összes legfeljebb

2 r^{1 / 3}

hosszú vektorra kiterjed, nemcsak azokra, amelyek valamelyik oldal irányába mutatnak.
Egy ilyesféle összeget így lehet becsülni. Legyen az összegzés határa

a

(most tehát

a = 2 r^{1 / 3}

). Nézzük először azokat a vektorokat, amelyek hossza

\frac{a}{2} \leq v < a

. Ezek száma legfeljebb annyi, mint az origótól különböző rácspontok száma az origó körüli

a

sugarú körben, tehát kisebb, mint

c_{3} a^{2}

(most a legdurvább becslés is elég nekünk), egy összeadandó pedig kisebb, mint

{(\frac{a}{2})}^{- 3 / 2}

, ez a részösszeg tehát kisebb, mint

c_{4} \sqrt[]{a}

. Ezt a becslést

a

helyett elvégezzük az

\frac{a}{2}

\frac{a}{4}

...

\frac{a}{2^{j}}

számokra, amíg csak

\frac{a}{2^{j}} < 1

nem lesz, és az eredményt összeadjuk:

\begin{matrix} \sum_{}^{} v^{- 3 / 2} < c_{4} \sum_{i = 1}^{\infty} \sqrt[]{\frac{a}{2^{i}}} = c_{5} \sqrt[]{a} . \end{matrix}

Ezt (2.10)-be helyettesítve

\begin{matrix} H_{1} < c_{6} \sqrt[]{r} \sqrt[]{r^{1 / 3}} = c_{6} r^{2 / 3} . \end{matrix}

v \geq 2 r^{1 / 3}

esethez tartozó

H_{2}

összeget pedig (2.4)-ből becsülhetjük azonnal:

\begin{matrix} H_{2} = \sum_{v_{i} \geq 2 r^{1 / 3}}^{} n_{i} \leq \frac{1}{2} r^{- 1 / 3} \sum_{}^{} n_{i} v_{i} \leq π r^{2 / 3} . \end{matrix}

H_{1}

és

H_{2}

becslését összeadva (2.2)-t beláttuk.
Foglalkozzunk most

T'

becslésével. Egy körszelet területe

\begin{matrix} t_{i} < l_{i} h_{i}; \end{matrix}

a körszeletek lefedik (átfedéssel) a sokszög és a körvonal közti sávot, tehát

\begin{matrix} T' < \sum_{}^{} t_{i} < \sum_{}^{} l_{i} h_{i} . \end{matrix}

h

és

l

között kapcsolat van: Püthagorasz (2.6) alatt felírt tételéből

\begin{matrix} h = \frac{l^{2}}{4 (2 r - h)} < \frac{l^{2}}{4 r} . \end{matrix}

Tehát

t < h l < \frac{r^{3}}{r}

, és (2.5) miatt

1 < 3 n v

, ezért végül

\begin{matrix} t < c_{7} \frac{n^{3} v^{3}}{r} . \end{matrix}

(2.11)

v \leq 2 n^{1 / 3}

, akkor az

n \leq 4 r^{1 / 2} v^{3 / 2}

egyenlőtlenség miatt

t < c_{9} n

, úgyhogy az ehhez az esethez tartozó területek összege

< c_{9} B < c_{10} r^{2 / 3}

.
A hátralevő eset ‐ azon szeletek területét becsülni ‐ ahol

v

nagy, komplikáltabb az eddigieknél. Mindenesetre (2.9)-ből látszik, hogy

n = 1

, de

t

nem lesz általában korlátos. Ha pl.

r

alig nagyobb egy

n

egész számnál,

n^{2} < r^{2} < n^{2} + 1

, akkor az

(n, 0)

pontot az

(n - 1, [\sqrt[]{2 n - 1}])

ponttal egy kb.

\sqrt[]{2 n}

hosszú oldal köti össze, amely egy

\sqrt[]{n}

nagyságrendű szeletet jelent. Ez az oldal ,,közel függőleges"; be lehet bizonyítani, hogy általában azok a hosszú oldalak, amelyeken csak a két csúcspont van, közel párhuzamosak egy kicsi vektorral. Ezt csak felszínesen vázoljuk, a számítások elvégzése nélkül.
Mivel

v

nagy (

> 2 r^{1 / 3}

l \geq v

is nagy és

h \approx l^{2} / r

nagy

\frac{1}{v}

-hez képest. Ekkor a szomszédos rácsegyeneshez tartozó

l'

húr alig rövidebb

l

-nél. Mivel pedig rajta a rácspontok

v \leq l

távolságra vannak, a húr két oldalán levő rácspontok a körvonaltól legfeljebb

l - l'

távolságra vannak (3. ábra). Erről kiszámolható (újra Püthagorasz tételével), hogy kisebb, mint

c \frac{r}{v^{2}}

. A két csúcspontból ehhez a két rácsponthoz vezető

\vec{w}

vektornak

\vec{v}

irányú komponense tehát legfeljebb ekkora, a rá merőleges komponens pedig pontosan

\frac{1}{v}

, jóval kisebb. Ez a ,,közel párhuzamos" kicsi vektor (az ábra erősen torzít).

Mivel

v < c \sqrt[]{\frac{r}{w}}

és

t < c \frac{v^{3}}{r}

, ezért

t < c \frac{\sqrt[]{r}}{w^{3 / 2}}

. Ez ugyanarra az összegre vezet, amit már egyszer kiszámítottunk; a baj csak az, hogy egy

\vec{w}

vektor többször is előfordulhat. Némi fejtöréssel bizonyítható, hogy nemcsak egy körszelet területe becsülhető

\frac{\sqrt[]{r}}{w^{3 / 2}}

-nel, hanem az adott

\vec{w}

-hez tartozó összes körszeletek területeinek összege is.

3. Megjegyzések

1. Az (1.3) képlet bizonyítása megtalálható pl. a Turán‐Gyarmati jegyzetben^{$^{*}$}Gyarmati Edit: Számelmélet, Nemzeti Tankönyvkiadó (ELTE-jegyzet). Ez a képlet mutatja, hogy

ϱ (n) \leq 4 τ (n)

, ahol

τ

az osztók száma.

τ (n) < n^{ε}

nagy

n

-re.^{$^{*}$}l. Erdős Pál‐Surányi János: Válogatott fejezetek a számelméletből, Polygon, Szeged, 1996. 8. fejezet X. tétel.
2. (1.4)-nél több is igaz, éspedig

\begin{matrix} \begin{matrix} {lim sup}_{}^{} \frac{Δ (r)}{\sqrt[]{r}} = \infty, {lim inf}_{}^{} \frac{Δ (r)}{\sqrt[]{r}} = - \infty . \end{matrix} \end{matrix}

Az első eredmény G. H. Hardytól származik 1915-ből, a második A. E. Inghamtől 1940-ből. Azóta mindkét tételt némileg erősítették, mégpedig a nevezőbe betettek egy-egy végtelenhez tartó függvényt (

log r

hatványát).
3. A kiinduló

r

-es becslés Gausstól származik; az

r^{2 / 3}

-os javítás Sierpińskitől 1906-ból. W. Sierpiński bizonyítása hosszú; többen készítettek egyszerű bizonyítást, rendszerint többé-kevésbé analitikus módon.
Az

r^{2 / 3}

-os becslés javításával sokan küszködtek, egy-egy hajszálnyit csökkentve a kitevőn. A rekord

\frac{46}{73} \approx 0,630137

. Általában azt sejtik, hogy az igazság

\frac{1}{2}

, vagyis

\frac{| Δ (r) |}{r^{t}}

bármely

t > \frac{1}{2}

kitevőre korlátos. Ez irányban ismert, hogy

Δ (r)

,,rendszerint" nem nagyobb, mint

\sqrt[]{r}

abban az értelemben, hogy

\begin{matrix} \int_{0}^{R} Δ {(r)}^{2} < c R^{2} \end{matrix}

Ez az eredmény E. G. H. Landautól származik.
Az itt leírt bizonyításnak

r^{2 / 3}

a természetes határa.

\frac{Δ (r)}{r^{2 / 3}} \to 0

bizonyítása elképzelhető volna úgy, hogy belátjuk, hogy

\frac{H}{r^{2 / 3}} \to 0

és

\frac{T'}{r^{2 / 3}} \to 0

; ezek viszont nem igazak, sőt az sem, hogy

\begin{matrix} \frac{H}{r^{2 / 3}} \to a, \frac{T'}{r^{2 / 3}} \to \frac{a}{2} \end{matrix}

valamely

a

konstanssal.

H

és

T'

között tehát nemtriviális kapcsolat van, amelynek jellegéről nem tudunk semmit.
4. Lehetséges, hogy

Q

nagy pozitív és negatív kilengései máshogy viselkednek. Mindenesetre a pozitív és negatív becslések bizonyítása gyakran másmilyen és nem is ugyanolyan erősek. A mi bizonyításunkban is, amikor beláttuk (2.2)-t, ezzel már megkaptuk, hogy

Δ (r) < c r^{2 / 3}

, míg az alsó becslés további kínlódással jár.

Ruzsa Z. Imre

^{$^{*}$}*

^{$^{*}$}**

^{$^{*}$}***