Diszkrepanciák számtani sorozatokban

Diplomamunka

Valkó Benedek

Témavezető: Sárközy András

Eötvös Loránd Tudományegyetem Természettudományi Kar

Tartalomjegyzék

Bevezetés 2

1 Az alapprobléma 6 1.1. Roth tétele és következményei . . . . . . . . . . . . . . . . . . . . . . 6 1.2. A diszkrepancia felső becslése . . . . . . . . . . . . . . . . . . . . . . 10

2 d-dimenziós számtani sorozatok diszkrepanciája 24 2.1. A diszkrepancia alsó becslése . . . . . . . . . . . . . . . . . . . . . . . 25 2.2. A diszkrepancia felső becslése . . . . . . . . . . . . . . . . . . . . . . 30

3 Kéttagú összegek eloszlásának irregularitása 35 3.1. Alsó becslés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2. Felső becslés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.3. Moduláris változat . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

Nyitott kérdések 55

Irodalomjegyzék 56

Bevezetés

Az angol discrepancy szó (egyik) magyar jelentése: egyenetlenség, eltérés. A matematikában a diszkrepancia általában egy adott eloszlás távolságának mértéke az ”ideális” (általában egyenletes) eloszlástól. Klasszikus példa a következő: legyen P = {p_{1}, p_{2}, …, p_{n}} véges ponthalmaz [0, 1)-ben. Ha P eloszlása egyenletes lenne, akkor egy (x, y) ⊆ [0, 1) intervallumba nagyjából n (y − x) pont kellene, hogy essen. Így nem meglepő, hogy a pontsorozat diszkrepanciáját a következőképpen definiáljuk:

D (P) = sup_{0≤x<y<1} | ∑_{x<p_{i}<y} 1 − n · (x − y)| .

\underline{Bevezetés}

Látható, hogy fix n mellett létezik ”nagyon egyenletes” eloszlású ponthalmaz, hiszen P = \{0, \frac{1}{n}, …, \frac{n−1}{n}\} esetén D (P) = 2, azaz n-től független korlát alatt marad, és az is könnyen meggondolható, hogy a kapott eredmény éles. Lényegesen bonyolultabb a helyzet d-dimenzióban (itt a [0, 1)^{d}-beli tengelypárhuzamos téglákon vett eltérések szuprémumaként definiáljuk a diszkrepanciát). 1954-ben Roth bebizonyította, hogy d ≥ 2 esetén tetszőleges n-elemű P ⊂ [0, 1)^{d} ponthalmazra D (P) ≥ c_{d} (log n)^{\frac{d−1}{2}} . Másrészt Halton konstruált tetszőleges d-re és n-re olyan n-elemű P ⊂ [0, 1)^{d} ponthalmazt, amelyre D (P) ≤ cd^{′} (log n)^{d−1}. Schmidtnek sikerült bebizonyítania, hogy d = 2-re ez éles, de a többi esetben az alsó és felső becslést nem sikerült sokkal közelebb hozni. Szintén érdekes, az eredeti problémával szoros kapcsolatban álló kérdés, hogy mit mondhatunk egy végtelen P ⊂ [0, 1)^{d} pontsorozat kezdőszeleteinek diszkrepanciájáról. Itt az első eredmény van Aardenne-Ehrenfest nevéhez fűződik, aki belátta, hogy a kezdőszeletek diszkrepanciái még egy dimenzióban sem lehetnek korlátosak.

Egy pontsorozat eloszlásának egyenletességét ill. irregularitását a tengelypárhuzamos téglatesteken kívül többféle geometriai objektumra nézve is vizsgálták. A terület eredményeinek egy összefoglalása megtalálható például [6]-ban, amelynek irodalomjegyzékében az előbb felsorolt eredményekhez tartozó cikkek is fellelhetőek.

Az eddigi példák alapján a következő (általunk is használt) diszkrepancia definícióhoz jutunk: legyen adott egy X mérhető tér, azon egy μ mérték és mérhető halmazoknak egy H rendszere. Akkor egy P = {p_{1}, p_{2}, …, p_{n}} ⊂ X véges ponthalmaz diszkrepanciáját így definiáljuk:

D (P) = sup_{H∈H} | ∑_{p_{i}∈H} 1 − n · μ (H)| .

Esetünkben X mindig diszkrét lesz, valamely M-re az M-nél nem nagyobb pozitív egészek vagy valamely q-ra a mod q maradékosztályok.

Ezen dolgozat kiindulási problémájával az 1. részben ismerkedhetünk meg. 1964ben megjelent cikkében ([9]) Roth vizsgálta, hogy az [1, N] = {1, 2, …, N} halmaz egy η · N elemszámú A részhalmaza mennyire egyenletesen oszolhat el a számtani sorozatokban. Ha az n, n + q, …, n + (k − 1) q számtani sorozatnak t eleme esik [1, N]-be, akkor egy ”egyenletes” eloszlású A halmaznak nagyjából η · t eleme kellene, hogy essen ebbe a számtani sorozatba. Roth bebizonyította, hogy a nem triviális eseteken kívül (amikor η = 1 vagy 0) nem létezhet ”nagyon egyenletes” A részhalmaz, van olyan c > 0, hogy mindig létezik olyan számtani sorozat, amelyben az eltérés legalább c\sqrt{η (1 − η)}N^{\frac{1}{4}} . (A \sqrt{η (1 − η)} faktor 0-vá válik a két triviális esetben.) Tehát ha egy A halmaz D (A) diszkrepanciáját a számtani sorozatokbeli megfelelő eltérések maximumaként definiáljuk, akkor Roth tétele szerint D (A) ≥ c\sqrt{η (1 − η)}N^{\frac{1}{4}} egy fix pozitív c konstanssal. (Roth célja az akkor még Erdős-Turán sejtésként ismert Szemerédi-tétel bizonyítása volt, és egy 5 cikkből álló sorozatot szentelt a témának. Mint később kiderült ez az út nem volt járható a bizonyításhoz, de így is több, magában is érdekes eredmény adódott a cikkekből.) A másik irányú állításhoz egy rokon problémát vizsgáltak: ha kiszínezzük az [1, N] halmazt két színnel, és tekintjük azt a számtani sorozatot, amelyben a legnagyobb a két szín előfordulása számának különbsége, akkor mennyire kicsivé tehető ez a maximális különbség. (A két probléma közti kapcsolatot az 1.2. részben részletesen tisztázzuk.) Roth cikkéből adódik, hogy ez az eltérés legalább O (N^{\frac{1}{4}} ). Furcsa módon Roth nem gondolta, hogy az eredménye éles, ő azt sejtette, hogy az igazság N^{\frac{1}{2} −o(1)}. Ezt látszott alátámasztani az, hogy viszonylag egyszerű valószínűségi eszközökkel bizonyítható, hogy létezik olyan színezés, ahol a legnagyobb eltérés O (\sqrt{N log N}). Ezt az eredményt lényegesen megjavította Sárközy ([3]), aki belátta, hogy létezik olyan színezés is, ahol a maximális eltérés legfeljebb N^{\frac{1}{3} +o(1)} (ezzel egyúttal Roth sejtését is megdöntötte). A nagy áttörést Beck 1981-es eredménye hozta ([1]), ő belátta, hogy Roth eredeti eredménye lényegében éles, van olyan színezés, amelyben a legnagyobb eltérés O (N^{\frac{1}{4}} log^{\frac{5}{2}} N). Végül 1996-ban megjelent cikkükben Spencer és Matoušek ([11]) végleg lezárták a kérdést, Beck módszerét továbbfejlesztve belátták, hogy Roth eredménye konstans szorzótól eltekintve éles. (Fontos megjegyeznünk, hogy míg a két színnel színezés esetén a maximális abszolútértékű eltérés nagyságrendje ismert, addig a természetesen felmerülő maximális pozitív eltérés kérdése közel sem tisztázott. A problémával kapcsolatos eredmények megtalálhatók például [12], [13], [14], [15]- ben, illetve ezek irodalomjegyzékeiben.)

A dolgozat 2. és 3. fejezetében az előbb ismertetett probléma különböző általánosításai, rokon problémái szerepelnek. A 2. fejezetben a d-dimenziós megfelelőt tárgyaljuk: egy A ⊆ [1, N]^{d} halmaz diszkrepanciáját vizsgáljuk a d-dimenziós számtani sorozatokra vonatkozóan. Bebizonyítjuk Roth tételének megfelelőjét, és azt is belátjuk, hogy a kapott eredmény lényegében éles. A kapott eredményt alkalmazzuk egy Knieper által felvetett problémára ([5]). A 3. fejezetben kéttagú összegek eloszlásának irregularitásait vizsgáljuk. Ehhez persze meg kell mondanunk, hogy milyen eloszlástól való eltérést tekintünk, azaz mit tekintünk ”ideálisnak”. Legyen megint A ⊆ [1, N] egy η · N elemszámú halmaz, és tekintsük az a_{1} + a_{2} alakú összegeket, ahol a_{1}, a_{2} ∈ A. Legyen f (n) = ∑_{\begin{matrix}a_{1}+a_{2}=n \\ a_{1},a_{2}∈A \end{matrix}} 1 és g (n) = ∑_{1≤k,n−k≤N} 1 (ezek adják meg, hogy n hányféleképpen áll elő A-beli ill. [1, N]-beli kéttagú összegként). Ha véletlenszerűen konstruálnánk A-t, hogy minden n ∈ [1, N] számot egymástól függetlenül η valószínűséggel választanánk be A-ba, akkor f (n) várható értéke körülbelül η^{2}g (n) lenne (pontosabban a várható érték η^{2}g (n) − (η^{2} − η) ha n páros, egyébként η^{2}g (n)). Így az n, n + q, …, n + (k − 1) q számtani sorozatban ”ideális” esetben nagyjából ∑_{i=0}^{k−1} η^{2}g(n + iq) darab a_{1} + a_{2} alakú összeg kellene, hogy legyen, és ezért érthető, hogy itt a diszkrepanciát a |∑_{i=0}^{k−1} (f(n + iq) − η^{2}g(n + iq))| eltérések maximumaként definiáljuk. Erre a diszkrepanciára bizonyítunk majd alsó becslést, és felső becslést is adunk. Megvizsgáljuk a probléma moduláris változatát is, szintén alsó és felső becsléseket adva a megfelelő diszkrepanciára. A dolgozat utolsó, 4. részében a nyitott kérdéseket összegezzük.

Köszönettel tartozom Sárközy András tanár úrnak a diplomamunka megírásához nyújtott segítségéért, és az évek során kapott rengeteg törődésért, tanításért, továbbá Károlyi Gyulának értékes megjegyzéseiért.

1. Fejezet

Az alapprobléma

Legyen A ⊆ [1, N] és \frac{|A|}{N} = η. Tetszőleges n, k > 0, q > 0 egészekre legyen

V (n, q, k) = | ∑_{\begin{matrix}0≤i<k \\ n+iq∈A \end{matrix}} 1 − η ∑_{\begin{matrix}0≤i<k \\ 1≤n+iq≤N \end{matrix}} 1| ,

ami (mint a bevezetésben láttuk) azt ”méri”, hogy az n, n + q, …, n + (k − 1) q számtani sorozatban mennyire ”egyenletes” az A eloszlása. Mi azt vizsgáljuk, hogy mennyire lehet kicsi max_{n,q,k} V (n, q, k).

1.1. Roth tétele és következményei

Roth-tól származik a következő tétel ([9]): 1.1.1. Tétel (Roth). Tetszőleges A ⊆ [1, N] halmazhoz léteznek n, 1 ≤ q ≤ ⌊\sqrt{N}⌋ egészek, hogy

V (n, q, k) ≥ c\sqrt{η (1 − η)}N^{\frac{1}{4}}

(ahol c egy N-től független konstans).

1. Az alapprobléma

A tétel szerint ha A nem az üres vagy az egész [1, N] halmaz, akkor nem lehet ”nagyon” egyenletes az eloszlása a számtani sorozatok között illetve azokon belül. (Ha az előbbi esetek valamelyike áll fenn, akkor η (1 − η) = 0, ami egybevág V (n, q, k) ≡ 0val.) A tétel bizonyításának alapja a következő állítás, amelyet később mi is többször használni fogunk.

1.1.2. Tétel. Legyen M pozitív egész, R ≥ 2 egész, R_{1} = ⌊\frac{R}{2}⌋. Legyenek s_{1}, s_{2}, …, s_{M} komplex számok, és definiáljuk s_{j}-t 0-nak, ha j ≤ 0 vagy j > M. Jelöljük a ∑_{i=0}^{k−1} s_{n+iq} összeget D(n, q, k)-val. Ekkor

∑_{q=1}^{R} ∑_{n=1−(R_{1}−1)q}^{M} |D(n, q, R_{1})|^{2} ≥ (\frac{2}{π} R_{1})^{2} ∑_{m=1}^{M} |s_{m}|^{2} .

Bizonyítás. A bizonyítás exponenciális összegek segítségével történik. Jelölje a továbbiakban e^{2πiα}-t e (α). Legyen S (α) = ∑_{n=1}^{M} s_{n}e (nα) (az s_{n} sorozat generátorfüggvénye), és H_{k} (α) = ∑_{n=0}^{k−1} e (nα). A kívánt egyenlőtlenséget a

J = ∫_{0}^{1} |S (α)|^{2} ∑_{q=1}^{R} |H_{R_{1}} (qα)|^{2} dα

kifejezés becslésével nyerjük. |H_{R_{1}} (α)| = |\begin{matrix}sin & (πR_{1}α) \\ sin & (πα) \end{matrix} |, és mivel \frac{2}{π} |x| ≤ |sin x| ≤ |x|, ha |x| ≤ \frac{π}{2}, ezért könnyen ellenőrizhető, hogy |H_{R_{1}} (α)| ≥ \frac{2}{π}R_{1}, ha |α| ≤ \frac{1}{2R_{1}} . Ismert, hogy tetszőleges α-ra léteznek olyan p, q relatív prím R-nél nem nagyobb pozitív egészek, hogy |α − \frac{q}{p} | ≤ \frac{1}{qR}. Akkor |qα − p| ≤ \frac{1}{R} ≤ \frac{1}{2R_{1}} , és így

|H_{R_{1}} (qα)|^{2} = |H_{R_{1}} (p − qα)|^{2} ≥ (\frac{2}{π} R_{1})^{2} .

Ebből következik, hogy tetszőleges α -ra

∑_{q=1}^{R} |H_{R_{1}} (qα)|^{2} ≥ (\frac{2}{π} R_{1})^{2} .

Ezzel máris egy alsó becslést kaptunk J-re:

J ≥ min_{α} ∑_{q=1}^{R} |H_{R_{1}} (qα)|^{2} ∫_{0}^{1} |S (α)|^{2} dα ≥ (\frac{2}{π} R_{1})^{2} ∑_{m=1}^{M} |s_{m}|^{2} ,

ahol az utolsó egyenlőtlenségnél a Parseval-formulát is alkalmaztuk. Másrészt J definíciójából:

J = ∫_{0}^{1} ∑_{q=1}^{R} |S (α) H_{R_{1}} (qα)|^{2} dα = ∑_{q=1}^{R} ∫_{0}^{1} |∑_{m=1}^{M} s_{m}e (mα) ∑_{j=0}^{R_{1}−1} e (jqα)|^{2} dα
= ∑_{q=1}^{R} ∫_{0}^{1} | ∑_{\begin{matrix}1≤m≤M \\ 0≤j≤R_{1}−1 \end{matrix}} s_{n}e ((m + jq) α)|^{2} dα = ∑_{q=1}^{R} ∫_{0}^{1} | ∑_{t=1}^{M+(R_{1}−1)q} ∑_{j=0}^{R_{1}−1} s_{t−jq}e (tα)|^{2} dα
= ∑_{q=1}^{R} ∫_{0}^{1} | ∑_{t=1}^{M+(R_{1}−1)q} D (t − (R_{1} − 1) q, q, R_{1}) e (tα)|^{2} dα
= ∑_{q=1}^{R} ∑_{t=1}^{M+(R_{1}−1)q} |D (t − (R_{1} − 1) q, q, R_{1})|^{2} = ∑_{q=1}^{R} ∑_{n=1−(R_{1}−1)q}^{M} |D (n, q, R_{1})|^{2} .

(Az átalakítások során változótranszformációt, a Parseval-formulát, illetve a megfelelő definíciókat használtuk.) A nyert eredményt összevetve a J-re kapott alsó becsléssel következik a tétel állítása.

1.1.3. Következmény. Létezik n, 1 ≤ q ≤ R, hogy

|D (n, q, R_{1})| ≥ \frac{2}{π} R_{1}\sqrt{∑_{m=1}^{M} |s_{m}|^{2}} (M + \frac{R^{2}}{4} )^{− \frac{1}{2}} R^{− \frac{1}{2}} .

Bizonyítás. Legyen T = max_{n,1≤q≤R} |D (n, q, R_{1})|. Akkor az előző tétel állításából adódik, hogy

∑_{q=1}^{R} ∑_{n=1−(R_{1}−1)q}^{M} T^{2} ≥ (\frac{2}{π} R_{1})^{2} ∑_{m=1}^{M} |s_{m}|^{2} .

Egyszerűsítve a bal oldalt:

∑_{q=1}^{R} ∑_{n=1−(R_{1}−1)q}^{M} T^{2} = T^{2} ∑_{q=1}^{R} (M + (R_{1} − 1) q) = T^{2} (MR + (R_{1} − 1) \frac{R (R + 1)}{2})
≤ T^{2} (M + \frac{R^{2}}{4} ) R.

Innen átrendezéssel következik a bizonyítandó állítás.

Az alábbi (számunkra igen fontos) következmény egyszerű behelyettesítéssel adódik. 1.1.4. Következmény. Létezik n, 1 ≤ q ≤ ⌊\sqrt{M}⌋, hogy

|D (n, q, ⌊\frac{1}{2} ⌊\sqrt{M}⌋⌋)| ≥ c\sqrt{\frac{∑_{m=1}^{M} |s_{m}|^{2}}{M}} M^{\frac{1}{4}} .

(Itt c fix konstans, M ≥ M_{ε} esetén választható (\frac{2}{π\sqrt{5}} − ε)-nak.) Most már készen állunk az 1.1.1. tétel bizonyítására.

Az 1.1.1. tétel bizonyítása. Használjuk a Q = ⌊\sqrt{N}⌋ és Q_{1} = ⌊\frac{1}{2}Q⌋ jelöléseket. Definiáljuk az s_{n} számokat a következőképpen: s_{n} = η ha n ∉ A és 1 ≤ n ≤ N, s_{n} = η − 1 ha n ∈ A és s_{n} = 0 egyébként. Az 1.1.4. következmény szerint létezik n, 1 ≤ q ≤ Q, hogy

| ∑_{i=0}^{Q_{1}−1} s_{n+iq}| ≥ c\sqrt{\frac{∑_{m=1}^{N} |s_{n}|^{2}}{N}} N^{\frac{1}{4}} = c\sqrt{\frac{η^{2} (1 − η) N + (1 − η)^{2} ηN}{N}} N^{\frac{1}{4}}
= c\sqrt{η (1 − η)}N^{\frac{1}{4}} .

Másrészt vegyük észre, hogy tetszőleges n, k > 0, q > 0 egészekre

|∑_{i=0}^{k−1} s_{n+iq}| = | ∑_{\begin{matrix}0≤i<k \\ n+iq∈A \end{matrix}} (η − 1) + ∑_{\begin{matrix}0≤i<k \\ n+iq∉A \\ 1≤n+iq≤N \end{matrix}} η| = |η ∑_{\begin{matrix}0≤i<k \\ 1≤n+iq≤N \end{matrix}} 1 − ∑_{\begin{matrix}0≤i<k \\ n+iq∈A \end{matrix}} 1| = V (n, q, k) ,

amiből következik a tétel állítása.

Érdemes megjegyeznünk, hogy Roth bizonyítása nem csak azt mutatja, hogy létezik olyan számtani sorozat, amelyben ”nagy” az egyenletes eloszlástól való eltérés, hanem azt is, hogy ezek az eltérések négyzetes középben nagyok. Tekintsünk még egy számunkra lényeges alkalmazást.

1.1.5. Állítás. Bárhogyan színezzük két színnel az 1, 2, …, N számokat, létezik olyan számtani sorozat, amelyben legalább c\sqrt[4]{N}-nel több van az egyik színből, mint a másikból (c fix konstans).

Bizonyítás. Jelöljük a két színt +1-gyel és −1-gyel, és definiáljuk az s_{n} számokat a színezésnek megfelelően (s_{n} = 0 ha n ≤ 0 vagy n > N). Az 1.1.4. következményből azonnal adódik a bizonyítandó állítás.

1.2. A diszkrepancia felső becslése

Roth tétele alsó becslést ad a legnagyobb eltérésre. Ha felső becslést szeretnénk, akkor olyan (nem triviális) A ⊆ [1, N] halmazt kell keresnünk, ami minden számtani sorozatban egyenletesen oszlik el (a lehetőségekhez mérten), azaz minden számtani sorozatban az eltérés O (\sqrt[4]{N}). Mint a bevezetőben is említettük, a felső becsléshez nem konkrétan ezt a problémát vizsgálták, hanem az 1.1.5. állítás megfelelőjét, azaz, hogy ki lehet-e színezni két színnel [1, N]-et úgy, hogy mindegyik számtani sorozatban a két szín előfordulásának eltérése O (\sqrt[4]{N}). A következő állítás a két probléma közötti szoros kapcsolatra világít rá. (A továbbiakban egy H halmaz két színnel színezése alatt mindig egy f : H → {−1, 1} függvényt értünk. Ekkor egy adott H_{1} részhalmazban a két szín előfordulásának eltérése | ∑_{h∈H_{1}} f (h)|.)

1.2.1. Állítás. Tegyük fel, hogy f az [1, N] egy olyan két színnel színezése, amelyre minden számtani sorozatban a két szín előfordulásának eltérése legfeljebb C. Ekkor létezik olyan A ⊆ [1, N], hogy |A| = ⌊\frac{N}{2} ⌋, és tetszőleges n, k > 0, q > 0 egészekre V (n, q, k) ≤ C + \frac{1}{2}. Bizonyítás. Mivel az 1, 2, …, N sorozat is számtani sorozat, így |∑_{n=1}^{N} f (n)| ≤ C. Akkor legfeljebb \frac{C}{2} helyen az ellentettjére változtatva f-et elérhető, hogy a +1-ekből vagy a −1-ekből éppen ⌊\frac{N}{2} ⌋ darab legyen. Nyilván feltehetjük, hogy a +1-ekből van ennyi. Így most minden számtani sorozatban a két szín előfordulásának eltérése legfeljebb C + 2\frac{C}{2} = 2C. Legyen A = \{n |f (n) = 1\} ⊆ [1, N], belátjuk, hogy ez teljesíti az állítás feltételeit. Ehhez azt kell belátnunk, hogy tetszőleges k elemű H ⊆ [1, N] számtani sorozatra

| ∑_{n∈H∩A} 1 − ηk| ≤ C + \frac{1}{2}.

Mivel |η − \frac{1}{2} | ≤ \frac{1}{2N}, és k ≤ N, ezért elég igazolni, hogy

| ∑_{n∈H∩A} 1 − \frac{1}{2}k| ≤ C.

Ehhez vegyük észre, hogy

∑_{n∈H∩A} 1 − \frac{1}{2}k = \frac{1}{2} ∑_{n∈H} f (n) ,

és így az előzőek miatt következik a bizonyítandó állítás.

A bevezetőben leírtuk, hogy meglehetősen hosszú ideig tartott, amíg bebizonyították, hogy az 1.1.5. állítás éles. Viszont az, hogy a bizonyítás nem javítható, már lényegesebben korábban ismert volt (lásd pl. [13]). Mint már korábban is megjegyeztük, a bizonyításból nem csak az jön ki, hogy van olyan H számtani sorozat, amire

|∑_{n∈H} f (n)| ≥ c\sqrt[4]{N},

hanem hogy ez négyzetes középben is teljesül, pontosabban, hogy

∑_{q=1}^{Q} ∑_{n=1−(Q_{1}−1)q}^{N} |D(n, q, Q_{1})|^{2} ≥ (\frac{2}{π} Q_{1})^{2} ∑_{m=1}^{N} |s_{m}|^{2} ≥ c′N^{2}.

(Itt az előző részben megismert jelöléseket használjuk, Q = ⌊\sqrt{N}⌋, Q_{1} = ⌊\frac{1}{2}Q⌋, s_{n} = f (n), ha 1 ≤ n ≤ N, és 0 egyébként, és D(n, q, Q_{1}) = ∑_{i=0}^{Q_{1}−1} s_{n+iq}.) Célunk először az, hogy megmutassuk, hogy ez éles, azaz minden N-re létezik olyan színezés, hogy

∑_{q=1}^{Q} ∑_{n=1−(Q_{1}−1)q}^{N} |D(n, q, Q_{1})|^{2} ≤ cN^{2}

teljesül alkalmas fix c-vel. 1.2.2. Állítás. Ha S (α) = ∑_{n=1}^{N} f (n) e (nα)-ra teljesül, hogy |S (α)| ≤ c_{1}\sqrt{N} minden α-ra, akkor

∑_{q=1}^{Q} ∑_{n=1−(Q_{1}−1)q}^{N} |D(n, q, Q_{1})|^{2} ≤ cN^{2}

valamely c_{1}-től függő c-vel. Bizonyítás. Tudjuk, hogy

∑_{q=1}^{Q} ∑_{n=1−(Q_{1}−1)q}^{N} |D(n, q, Q_{1})|^{2} = ∫_{0}^{1} |S (α)|^{2} ∑_{q=1}^{Q} |H_{Q_{1}} (qα)|^{2} dα.

A jobb oldalt triviálisan becsülve:

∫_{0}^{1} |S (α)|^{2} ∑_{q=1}^{Q} |H_{Q_{1}} (qα)|^{2} dα ≤ c_{1}^{2}N ∫_{0}^{1} ∑_{q=1}^{Q} |H_{Q_{1}} (qα)|^{2} dα.

Mivel a definíció szerint H_{k} (α) = ∑_{n=0}^{k−1} e (nα), ezért a Parseval-formula szerint

c_{1}^{2}N ∫_{0}^{1} ∑_{q=1}^{Q} |H_{Q_{1}} (qα)|^{2} dα = c_{1}^{2}NQQ_{1}.

Innen pedig Q és Q_{1} definíciója miatt következik az állítás.

Így most már elég találnunk N-hez N-edfokú polinomot, amelynek konstans tagja 0, többi együtthatója ±1, és egyenletesen kis abszolútértékű az egységkörön. Ehhez az ismert Rudin-Shapiro konstrukciót használjuk (pl. [10]). Legyen P_{0} (z) = Q_{0} (z) = 1, és n ≥ 1-re legyen

P_{n} (z) = P_{n−1} (z) + z^{2^{n−1}}Q_{n−1} (z) , és Q_{n} (z) = P_{n−1} (z) − z^{2^{n−1}}Q_{n−1} (z) .

Teljes indukcióval könnyen bizonyítható, hogy |z| = 1 esetén

|P_{n} (z)|^{2} + |Q_{n} (z)|^{2} = 2^{n+1},

amiből következik, hogy |P_{n} (z)| legfeljebb \sqrt{2}\sqrt{2^{n}} az egységkörön. Így tetszőleges n-re zP_{n} (z) olyan 2^{n} fokszámú polinom, amely eleget tesz a kívánt feltételeknek, és ezek segítségével tetszőleges N-hez tudunk konstruálni megfelelő polinomot. A konstrukcióból látszik, hogy létezik olyan ε_{1}, ε_{2}, … ±1-ekből álló végtelen sorozat, hogy zP_{n} (z) = ∑_{i=1}^{2^{n}} ε_{i}z^{i}, legyen N ≥ 1-re S_{N} (α) = ∑_{j=1}^{N} ε_{i}e (jα). Egyszerűen igazolható, hogy |S_{N} (α)| ≤ 5\sqrt{N} tetszőleges α-ra, azaz S_{N} (α) kielégíti az 1.2.2. állításhoz szükséges feltételeket. Ezzel beláttuk, hogy valóban éles a négyzetes középre vonatkozó alsó becslés. Most a maximumra vonatkozó felső becslés tárgyalására térünk rá. A nagy áttörést Beck 1981-es tétele hozta ([1]).

1.2.3. Tétel (Beck). Minden N-re létezik olyan f : [1, N] → {−1, 1} színezés, hogy tetszőleges {n, n + q, …, n + (k − 1) q} ⊆ [1, N] számtani sorozatra

|∑_{i=0}^{k−1} f (n + iq)| ≤ c\sqrt[4]{N} (log N)^{\frac{5}{2}} .

Az állítás egy sokkal általánosabb, hipergráfok diszkrepanciájára vonatkozó tételből következik. Ahhoz, hogy ezt kimondhassuk, először be kell vezetnünk néhány jelölést.

Hipergráf alatt itt véges halmazok egy véges rendszerét értjük. Egy adott H hipergráf esetén legyen

S (H) = ⋃_{A∈H} A  (a csúcsok halmaza),
deg (H, x) = |{A ∈ H : x ∈ A}| (x foka H-ban),
deg (H) = max_{x} deg (H, x)  (H foka).

Legyen továbbá

disc (H) = min_{g:S(H)→{−1,1}} max_{A∈H} |∑_{x∈A} g (x)| .

(Ez mutatja meg, hogy mennyire egyenletesen lehet kiszínezni két színnel a hipergráfunkat.)

1.2.4. Tétel (Beck). Legyen H hipergráf, és tegyük fel, hogy létezik olyan t valós szám, hogy

deg ({A ∈ H : |A| ≥ t}) ≤ t.

Akkor

disc (H) ≤ c_{0}\sqrt{t}\sqrt{(log |H|)} log |S (H)| ,

ahol c_{0} fix konstans.

Először megmutatjuk, hogy hogyan következik az 1.2.3. tétel a 1.2.4. tételből.

Az 1.2.3. tétel bizonyítása. A továbbiakban i ≤ j esetén jelöljük AP(a, d, i, j)-vel azt a d-differenciájú számtani sorozatot, amelynek első eleme a + id, utolsó eleme pedig a + jd. A következő nagyon fontos fogalmat Beck vezette be. Egy számtani sorozatot eleminek nevezünk, ha a hossza 2-hatvány (pl. 2^{s}, s ≥ 0), a differenciája d ≥ 1, és az első eleme b + (i2^{s}) d, ahol 1 ≤ b ≤ d, i ≥ 0. Azaz formálisan, ha AP(b, d, i2^{s}, (i + 1) 2^{s} − 1) alakú, ahol 1 ≤ b ≤ d, d ≥ 1, i ≥ 0 és s ≥ 0. Jelöljük H_{N}-nel az [1, N]-be eső elemi számtani sorozatok családját. A definícióból adódóan

deg ({A ∈ H_{N} : |A| ≥ k}) = max_{m} |{m ∈ AP (b, d, i2^{s}, (i + 1) 2^{s} − 1) ⊆ [1, N] : 2^{s} ≥ k}|
= max_{m} ∑_{1≤d≤ \frac{N}{k}} ∑_{\begin{matrix}1≤b≤d \\ b≡mmodd \end{matrix}} ∑_{\begin{matrix}2^{s}≥k \\ b+(2^{s}−1)d≤N \end{matrix}} 1.

(A rövidség kedvéért nem írtuk bele a második tagba az összes szükséges feltételt.) Könnyen látható, hogy

∑_{\begin{matrix}2^{s}≥k \\ b+(2^{s}−1)d≤N \end{matrix}} 1 ≤ log_{2} (\frac{N}{dk} ) ,

így

deg (\{A ∈ H_{N} : |A| ≥ k\}) ≤ max_{m} ∑_{1≤d≤ \frac{N}{k}} ∑_{\begin{matrix}1≤b≤d \\ b≡m mod d \end{matrix}} log_{2} (\frac{N}{dk} ) = ∑_{1≤d≤ \frac{N}{k}} log_{2} (\frac{N}{dk} ) ≤ c_{1} \frac{N}{k}

egy megfelelő c_{1} konstanssal (az utolsó lépés következik például a Stirling formulából). Ezért t = \sqrt{c_{1}N} választással alkalmazható az 1.2.4. tétel:

disc (H_{N}) ≤ c_{0}\sqrt{t}\sqrt{(log |H_{N}|)} log |S (H_{N})| .

Egyszerű leszámlálással adódik, hogy |H_{N}| ≤ 2N^{2}, és mert S (H_{N}) = [1, N], ezért

disc (H_{N}) ≤ c_{2}\sqrt[4]{N} (log N)^{\frac{3}{4}} .

Ez azt jelenti, hogy létezik olyan f : [1, N] → {−1, 1} színezés, hogy tetszőleges A ⊆ [1, N] elemi számtani sorozatra

|∑_{n∈A} f (n)| ≤ c_{2}\sqrt[4]{N} (log N)^{\frac{3}{4}} .

Belátjuk, hogy ez a színezés eleget tesz a tételünk feltételeinek. Először is vegyük észre, hogy tetszőleges H = {a, a + d, …, a + md} ⊆ [1, N] számtani sorozat előáll

AP (b, d, 0, p_{1}) \ AP (b, d, 0, p_{2})

alakban, ahol a = b + p_{2}d, 1 ≤ b ≤ d, és p_{1} = m + p_{2}. i = 1, 2-re legyen p_{i} + 1 kettes számrendszerbeli felírása

p_{i} + 1 = ∑_{j=1}^{l_{i}} 2^{s(i,j)}, s (i, 1) > s (i, 2) > … > s (i, l_{i}) .

Akkor

AP (b, d, 0, p_{i}) = ⋃_{r=1}^{l_{i}} AP (b, d, ∑_{j=1}^{r−1} 2^{s(i,j)}, ∑_{j=1}^{r} 2^{s(i,j)} − 1) ,

ahol láthatóan diszjunkt unió szerepel. Azaz AP(b, d, 0, p_{i}) felbontható l_{i} ≤ log_{2} N diszjunkt elemi számtani sorozat uniójára. Ez viszont az elemi számtani sorozatok diszkrepanciájáról kapott becsléssel együtt azt adja, hogy

|∑_{n∈H} f (n)| ≤ (2 log_{2} N) c_{2}\sqrt[4]{N} (log N)^{\frac{3}{4}} = c\sqrt[4]{N} (log N)^{\frac{5}{4}} ,

és éppen ezt kellett belátnunk.

Az 1.2.4. tétel bizonyításának alapja a következő lemma: 1.2.5. Lemma. Az 1.2.4. tétel feltételei mellett létezik olyan f : S (H) → {0, −1, +1} függvény, hogy

|\{x ∈ S (H) : f (x) = 0\}| ≤ \frac{9}{10} |S (H)| ,  (1)

és

|∑_{x∈A} f (x)| ≤ c_{2}\sqrt{t}\sqrt{log |H|} minden A ∈ H halmazra,  (2)

ahol c_{2} fix konstans.

A lemma szerint a hipergráfunknak létezik olyan részleges egyenletes színezése, hogy az elemek legalább \frac{1}{10}-ed része ki van színezve. A nekünk szükséges teljes egyenletes színezést a lemma sorozatos egymás utáni alkalmazásával kapjuk majd.

Bizonyítás. A bizonyítás tulajdonképpen leszámlálással történik, de a háttérben valószínűségszámítási megfontolások vannak. Legyen H^{∗} = {A ∈ H : |A| ≥ t}, |S (H)| = N, és |H^{∗}| = K. Jelöljük G-vel a g : S (H) → {−1, +1} függvények halmazát. Tetszőleges A ∈ H halmazra

\{g ∈ G : |∑_{x∈A} g (x)| ≥ μ\sqrt{|A|}\} = 2^{N−|A|} ∑_{|i−|A|/2|≥ \frac{1}{2} μ\sqrt{|A|}} \binom{|A|}{i} ≤ 2^{N−|A|}2^{|A|} (2e^{−2μ^{2}}) ,

ahol az utolsó egyenlőtlenség az ismert Chernoff-egyenlőtlenségből következik ([2]). Ebből adódik, hogy egy megfelelően nagy c_{3} konstanssal a

G_{1} = \{g ∈ G : |∑_{x∈A} g (x)| ≥ c_{3}\sqrt{|A| log |H|} minden A ∈ H-ra\}

halmaz számossága legalább 2^{N−1} (az előző egyenlőtlenség segítségével meg tudjuk becsülni a ”rossz” függvények számát). Legyen H^{∗} = {A_{1}, A_{2}, …, A_{K}}, és minden 1 ≤ i ≤ K egészre osszuk fel az

I_{i} = [−c_{3}\sqrt{|A_{i}| log |H|}, c_{3}\sqrt{|A_{i}| log |H|}]

intervallumot r_{i} = ⌊\sqrt{\frac{|A_{i}|}{t}}⌋ darab egyenlő részre:

I_{i} = ⋃_{j=1}^{r_{i}} I_{i,j}.

Egy tetszőleges g ∈ G_{1} függvényhez rendeljünk hozzá egy K-dimenziós \underline{v} (g) vektort a következő módon:

\underline{v} (g) = (j_{1}, j_{2}, …, j_{K}) ,

ahol minden 1 ≤ i ≤ K egészre

∑_{x∈A_{i}} g (x) ∈ I_{i,j_{i}}.

Belátjuk, hogy legfeljebb 2^{\frac{3N}{10}} darab ilyen vektor képződött. A definíció szerint

|\{\underline{v} (g) : g ∈ G_{1}\}| ≤ ∏_{i=1}^{K} r_{i} ≤ ∏_{i=1}^{K} \sqrt{\frac{|A_{i}|}{t}} ≤ exp (\frac{∑_{i=1}^{K} |A_{i}|}{2et}) ≤ exp (\frac{∑_{i=1}^{K} |A_{i}|}{5t}) .

Közben felhasználtuk a következő ismert egyenlőtlenséget: tetszőleges b_{1}, b_{2}, …, b_{K} valós számokra

∏_{i=1}^{K} b_{i} ≤ exp (\frac{∑_{i=1}^{K} b_{i}}{e} ) .

A lemma feltételei szerint deg(H^{∗}) ≤ t, emiatt

∑_{i=1}^{K} |A_{i}| = ∑_{x∈S(H)} deg (H^{∗}, x) ≤ |S (H)| deg (H^{∗}) ≤ |S (H)| t = Nt,

és így valóban

|\{\underline{v} (g) : g ∈ G_{1}\}| ≤ e^{\frac{N}{5}} ≤ 2^{\frac{3N}{10}} .

Akkor a skatulya-elv miatt létezik G_{1}-nek olyan G_{2} részhalmaza, amire

|G_{2}| ≥ |G_{1}| 2^{− \frac{3N}{10}} ≥ 2^{− \frac{7N}{10} −1},

és \underline{v} (g_{1}) = \underline{v} (g_{2}) minden g_{1}, g_{2} ∈ G_{2} függvényre. Válasszunk egy tetszőleges g_{0} ∈ G_{2} függvényt, és legyen

F_{2} = \{\frac{g_{0} − g_{1}}{2} : g ∈ G_{2}\} .

Vizsgáljuk meg, milyen függvények lesznek F_{2}-ben. Látható, hogy a halmazban olyan f : S (H) → {0, −1, +1} függvények vannak, amelyekre

|∑_{x∈A} f (x)| ≤ 2 max_{g∈G_{2}} |∑_{x∈A} g (x)| ≤ 2c_{3}\sqrt{|A| log |H|} ≤ 2c_{3}\sqrt{t log |H|}

minden A ∈ H \ H^{∗} = {A ∈ H : |A| < t} halmazra, és ha A ∈ H^{∗}, akkor

|∑_{x∈A} f (x)| ≤ max_{i,j} |I_{i,j}| ≤ max_{i} 2c_{3}\sqrt{|A_{i}| log |H|}/ ⌊\sqrt{\frac{|A_{i}|}{t}}⌋ ≤ c_{4}\sqrt{t log |H|}

egy megfelelő c_{4} konstanssal. Összegezve eredményeinket azt kapjuk, hogy F_{2} minden eleme teljesíti a (2) feltételt, és így elég találnunk egyetlen olyan F_{2}-beli elemet, amely teljesíti (1)-et. Legyen F^{∗} azon f : S (H) → {0, −1, +1} függvények halmaza, amelyekre

|\{x ∈ S (H) : f (x) = 0\}| ≥ \frac{9}{10} |S (H)| = \frac{9}{10}N.

Látható, hogy

|F^{∗}| = ∑_{i=0}^{⌊N/10⌋} \binom{N}{i}2^{i} ≤ 2\binom{N}{⌊N/10⌋}2^{\frac{N}{10}} < 2^{− \frac{7N}{10} −1} ≤ |F_{2}| ,

ezért az F_{2} \ F^{∗} halmaz nem üres, és ebből már következik a lemma állítása.

Az 1.2.4. tétel bizonyítása. Az 1.2.5. lemma szerint létezik olyan f_{1} : S (H) → {0, −1, +1} függvény, amire teljesül (1) és (2). Jelölje H_{1} a H megszorítását arra a halmazra, ahol f_{1} eltűnik, azaz legyen

H_{1} = {A ∩ f_{1}^{−1} ({0}) : A ∈ H} .

Nyilván

deg ({B ∈ H_{1} : |B| ≥ t}) ≤ deg ({A ∈ H : |A| ≥ t}) ≤ t,

azaz H_{1}-re is alkalmazható a 1.2.5. lemma, létezik olyan f_{2} : S (H_{1}) → {0, −1, +1} függvény, amire teljesül (1) és (2). Folytatva ezt az eljárást, az i-dik lépésben egy olyan f_{i} : S (H_{i−1}) → {0, −1, +1} függvényt kapunk, amire

|\{x ∈ S (H_{i−1}) : f_{i} (x) = 0\}| ≤ \frac{9}{10} |S (H_{i−1})| ,

és

|∑_{x∈B} f_{i} (x)| ≤ c_{2}\sqrt{t}\sqrt{log |H_{i−1}|} minden B ∈ H_{i−1} halmazra.

Az eljárás megáll, ha olyan függvényt kapunk, amely csak +1-et és −1-et vesz fel. Mivel a lemma állításából adódóan

|S (H_{i})| ≤ \frac{9}{10} |S (H_{i−1})| ≤ (\frac{9}{10})^{i} |S (H)| ,

ezért ez be is következik legfeljebb ⌊log |S (H)| / log (\frac{10}{9})⌋ + 1 lépésen belül. Legyen g = ∑_{i≥1} f_{i}. Látható, hogy így egy S (H) → {−1, +1} függvényt kaptunk. Adott A ∈ H esetén i ≥ 1-re jelölje A_{i} az A ∩ S (H_{i}) halmazt, és A_{0} = A. Az eljárás szabályából következik, hogy

|∑_{x∈A} g (x)| = |∑_{i≥1} ∑_{x∈A_{i−1}} f_{i} (x)| ≤ ∑_{i≥1} | ∑_{x∈A_{i−1}} f_{i} (x)|
≤ ∑_{i≥1} c_{2}\sqrt{t}\sqrt{log |H_{i−1}|} ≤ c_{2}\sqrt{t}\sqrt{log |H|} (⌊log |S (H)| / log (\frac{10}{9})⌋ + 1)
≤ c_{0}\sqrt{t}\sqrt{log |H|} log |S (H)|

egy megfelelő fix c_{0} konstanssal. Ezzel pedig beláttuk a tétel állítását.

A következőkben az lesz a célunk, hogy teljes általánosságban belássuk, hogy az 1.1.1. tétel lényegében éles.

1.2.6. Tétel. Legyenek N és K adott pozitív egészek, és 0 < η = \frac{K}{N} < 1. Akkor létezik olyan A ⊆ [1, N], hogy |A| = K = ηN, és tetszőleges n, k > 0, q > 0 egészekre

V (n, q, k) ≤ c\sqrt[4]{N} (log N)^{\frac{5}{2}} .

1. Az alapprobléma

A bizonyításhoz az 1.2.4. tétel egy általánosabb alakja szükséges. A továbbiakban tegyük fel, hogy H hipergráf, melyre S (H) = [1, N]. A definíció szerint

disc (H) = min_{g:[1,N]→{−1,1}} max_{A∈H} |∑_{i∈A} g (i)| .

Ezt kicsit más alakban felírva:

disc (H) = 2 min_{g:[1,N]→\{0,1\}} max_{A∈H} |∑_{i∈A} (g (i) − \frac{1}{2})| .

Így már könnyen összehasonlítható a diszkrepancia az alább definiált lineáris diszkrepanciával:

lindisc (H) = max_{α_{1},... ,α_{N} ∈[0,1]} min_{g:[1,N]→{0,1}} max_{A∈H} |∑_{i∈A} (g (i) − α_{i})| ,

világos, hogy

2lindisc (H) ≥ disc (H) .

Másrészt az alábbi tétel szerint a lineáris diszkrepancia felülről becsülhető az ún. öröklött diszkrepanciával, amelynek definíciója:

herdisc (H) = max_{X⊆[1,N]} disc ({A ∩ X : A ∈ H}) ,

(azaz H megszorításainak diszkrepanciái közül a legnagyobb). 1.2.7. Tétel (Lovász-Spencer-Vesztergombi [7]).

lindisc (H) ≤ herdisc (H) .

Vegyük észre, hogy az 1.2.4. tétel feltétele öröklődik a megszorításra, azaz ha deg ({A ∈ H : |A| ≥ t}) ≤ t, akkor H_{1} = {A ∩ X : A ∈ H}-re teljesül

deg ({A ∈ H_{1} : |A| ≥ t}) ≤ t.

Így az 1.2.4. tétel felső becslést szolgáltat herdisc(H)-ra, és az 1.2.7. tétel segítségével lindisc(H)-ra is. Tehát igaz a következő állítás: 1.2.8. Állítás. Az 1.2.4. tétel feltételei mellett

lindisc (H) ≤ c_{0}\sqrt{t}\sqrt{(log |H|)} log |S (H)| .

Ha a lineáris diszkrepancia definíciójában az {α_{1}, …, α_{N} ∈ [0, 1]} halmaz helyett a kisebb {α_{1} = … = α_{N} = η ∈ [0, 1]} halmazon vesszük a maximumot, akkor nyilván nem nő a maximum értéke. Így kapjuk az alábbi következményt: 1.2.9. Következmény. Az 1.2.4. tétel feltételei mellett tetszőleges 0 ≤ η ≤ 1 esetén létezik olyan f : [1, N] → {1 − η, −η} függvény, hogy tetszőleges A ∈ H esetén

|∑_{i∈A} f (i)| ≤ c_{0}\sqrt{t}\sqrt{(log |H|)} log |S (H)| .

Most már nincs nehéz dolgunk az 1.2.6. tétel bizonyításával.

Az 1.2.6. tétel bizonyítása. Az 1.2.9. következményből az 1.2.3. bizonyításával analóg módon belátható, hogy létezik olyan f : [1, N] → {1 − η, −η} függvény, hogy tetszőleges {n, n + q, …, n + (k − 1) q} ⊆ [1, N] számtani sorozatra

|∑_{i=0}^{k−1} f (n + iq)| ≤ c_{0}\sqrt[4]{N} (log N)^{\frac{5}{2}} .

Lényegében elismételve az 1.2.1. állítás bizonyítását könnyen igazolható, hogy van olyan f : [1, N] → {1 − η, −η} függvény, hogy ∑_{n=1}^{N} f (n) = 0, és tetszőleges [1, N]-beli {n, n + q, …, n + (k − 1) q} számtani sorozatra

|∑_{i=0}^{k−1} f (n + iq)| ≤ c\sqrt[4]{N} (log N)^{\frac{5}{2}}

egy alkalmas c konstanssal. Az A = {n : f (n) = 1 − η} definícióval így éppen egy K = ηN elemű halmazt definiáltunk, és egyszerűen ellenőrizhető, hogy erre teljesülnek a 1.2.6. tétel feltételei.

d-dimenziós számtani sorozatok

diszkrepanciája

Az évek során Roth eredményét többen általánosították különböző irányokban. Knieper a következő problémát vizsgálta ([5]): legyen d ≥ 1, és jelöljük S-sel [1, N]^{d} azon részhalmazainak halmazát, amelyek előállnak d darab [1, N]-beli számtani sorozat direkt szorzata; mekkora lesz S diszkrepanciája. (Látható, hogy a d = 1 eset visszaadja az eredeti problémát.) Belátta, hogy disc(S) ≥ cN^{\frac{d}{4}} , és hogy ez a becslés log-hatványtól eltekintve éles. Mi most egy másik természetesen felmerülő általánosítást vizsgálunk. Legyen H az [1, N]^{d}-be eső számtani sorozatok halmaza, azaz

H = \{\{\underline{a} + k · \underline{b} : 0 ≤ k ≤ r\} ⊂ [1, N]^{d}\} ,

(ez szintén visszadja az eredeti problémát d = 1-re). Megmutatjuk, hogy

disc (H) ≥ cN^{\frac{d}{2d+2}} ,

2. d-dimenziós számtani sorozatok diszkrepanciája

és ez a becslés log-hatványtól eltekintve éles, továbbá a kapott eredményt akalmazzuk egy Knieper által felvetett problémára. A továbbiakban az aláhúzott változók d-dimenziós vektorokat jelölnek (ℝ^{d} vagy ℤ^{d}- belieket), ⟨., .⟩ a megfelelő skaláris szorzat.

2.1. A diszkrepancia alsó becslése

A bizonyításhoz az 1.1.2. tételt és következményeit igazoljuk általánosabb formában.

2.1.1. Tétel. Legyen \{c\underline{a}, \underline{a} ∈ [1, N]^{d}\} komplex számok egy rögzített halmaza, és legyen c\underline{a} = 0 ha \underline{a} ∉ [1, N]^{d}. Legyenek továbbá Q, Q_{1} pozitív egészek, amelyekre teljesül Q^{d} ≥ 2Q_{1}, N ≥ Q. Tetszőleges \underline{a}, \underline{b} ∈ ℤ^{d} esetén legyen D (\underline{a}, \underline{b}) = ∑_{k=0}^{Q_{1}−1} c_{\underline{a}+k\underline{·b}}, és vezessük be az

A = \{\underline{b} : \underline{b} = (b_{1}, b_{2}, …, b_{d}) ≠ \underline{0}, |b_{i}| ≤ Q minden 1 ≤ i ≤ d-re\}

és

B (\underline{b}) = ⋃_{k=0}^{Q_{1}−1} ([1, N]^{d} − k · \underline{b})

jelöléseket. Akkor

∑_{\underline{b}∈A} ∑_{\underline{a}∈B(\underline{b})} |D (\underline{a}, \underline{b})|^{2} ≥ (\frac{2}{π} Q_{1})^{2} ∑_{\underline{a}∈[1,N]^{d}} |c\underline{a}|^{2} .

Bizonyítás. A bizonyítás az 1.1.2. tétel bizonyításával analóg módon történik. \underline{α} ∈ [0, 1]^{d}-

re legyen S (\underline{α}) = ∑_{\underline{a}∈[1,N]^{d}} c\underline{a} · e (⟨\underline{a}, \underline{α}⟩) és x ∈ [0, 1]-re H (x) = ∑_{k=0}^{Q_{1}−1} e (k · x). Az alábbi

integrált fogjuk vizsgálni:

J = ∫_{[0,1]^{d}} |S (\underline{α})|^{2} ∑_{\underline{b}∈A} |H (⟨\underline{b}, \underline{α}⟩)|^{2} d\underline{α}.

2. d-dimenziós számtani sorozatok diszkrepanciája

Legyen \underline{b} ∈ A tetszőleges fix vektor, és tekintsük ∫_{[0,1]^{d}} |S (\underline{α})|^{2} |H (⟨\underline{b}, \underline{α}⟩)|^{2} d\underline{α}-t:

∫_{[0,1]^{d}} |S (\underline{α})|^{2} |H (⟨\underline{b}, \underline{α}⟩)|^{2} d\underline{α} = ∫_{[0,1]^{d}} |( ∑_{\underline{a}∈[1,N]^{d}} c\underline{a} · e (⟨\underline{a}, \underline{α}⟩)) ( ∑_{k=0}^{Q_{1}−1} e (k · ⟨\underline{b}, \underline{α}⟩))|^{2} d\underline{α}
= ∫_{[0,1]^{d}} | ∑_{\underline{a}∈[1,N]^{d}} c\underline{a} · ∑_{k=0}^{Q_{1}−1} e (⟨\underline{a} + k · \underline{b}, \underline{α}⟩)|^{2} d\underline{α}.

B (\underline{b}) definíciójából könnyen belátható, hogy

∑_{\underline{a}∈[1,N]^{d}} c\underline{a} · ∑_{k=0}^{Q_{1}−1} e (⟨\underline{a} + k · \underline{b}, \underline{α}⟩) = ∑_{\underline{a}∈B(\underline{b})} e (⟨\underline{a}, \underline{α}⟩) ( ∑_{k=0}^{Q_{1}−1} c_{\underline{a}+k·\underline{b}}) .

A Parseval formula d-dimenziós változata szerint, ha G (\underline{α}) = ∑_{\underline{a}∈ℤ^{d}} h\underline{a} · e (⟨\underline{a}, \underline{α}⟩) (ahol az összeg konvergens), akkor ∫_{[0,1]^{d}} |G (\underline{α})|^{2} d\underline{α} = ∑_{\underline{a}∈ℤ^{d}} |h\underline{a}|^{2}. Ezt felhasználva

∫_{[0,1]^{d}} | ∑_{\underline{a}∈[1,N]^{d}} c\underline{a} · ∑_{k=0}^{Q_{1}−1} e (⟨\underline{a} + k · \underline{b}, \underline{α}⟩)|^{2} d\underline{α} = ∫_{[0,1]^{d}} | ∑_{\underline{a}∈B(\underline{b})} e (⟨\underline{a}, \underline{α}⟩) ( ∑_{k=0}^{Q_{1}−1} c_{\underline{a}+k·\underline{b}})|^{2} d\underline{α}
= ∑_{\underline{a}∈B(\underline{b})} | ∑_{k=0}^{Q_{1}−1} c_{\underline{a}+k·\underline{b}}|^{2} = ∑_{\underline{a}∈B(\underline{b})} |D (\underline{a}, \underline{b})|^{2} ,

és így

J = ∑_{\underline{b}∈A} ∑_{\underline{a}∈B(\underline{b})} |D (\underline{a}, \underline{b})|^{2} .

Tehát a tétel bizonyításához J-re kell alsó becslést adnunk. A 2.1.2. lemmában majd belátjuk, hogy tetszőleges \underline{α} ∈ [0, 1]^{d}-re

∑_{\underline{b}∈A} |H (⟨\underline{b}, \underline{α}⟩)|^{2} ≥ (\frac{2}{π} Q_{1})^{2} .

Ebből pedig már következik a bizonyítandó állítás, hiszen

J ≥ min_{\underline{α}∈[0,1]^{d}} ∑_{\underline{b}∈A} |H (⟨\underline{b}, \underline{α}⟩)|^{2} ∫_{[0,1]^{d}} |S (\underline{α})|^{2} d\underline{α}
= min_{\underline{α}∈[0,1]^{d}} ∑_{\underline{b}∈A} |H (⟨\underline{b}, \underline{α}⟩)|^{2} ∑_{\underline{a}∈[1,N]^{d}} |c\underline{a}|^{2} ≥ (\frac{2}{π} Q_{1})^{2} ∑_{\underline{a}∈[1,N]^{d}} |c\underline{a}|^{2} .

2.1.2. Lemma.

∑_{\underline{b}∈A} |H (⟨\underline{b}, \underline{α}⟩)|^{2} ≥ (\frac{2}{π} Q_{1})^{2}

Bizonyítás. Korábban már láttuk, hogy |H (x)|^{2} = \begin{matrix}sin & ^{2} & (πQ_{1}x) \\ sin & ^{2} & (πx) \end{matrix}, és ha ∥x∥ ≤ \frac{1}{2Q_{1}} , akkor |H (x)|^{2} ≥ (\frac{2}{π}Q_{1})^{2} ( ∥x∥ az x távolságát jelöli a legközelebbi egésztől). A Dirichletféle szimultán approximáció tétel szerint tetszőleges \underline{α} = (α_{1}, α_{2}, …, α_{d}) ∈ [0, 1]^{d} vektorhoz létezik olyan \underline{b}^{∗} ∈ A, hogy ∥⟨\underline{b}^{∗}, \underline{α}⟩∥ ≤ \frac{1}{Q^{d}} ≤ \frac{1}{2Q_{1}} teljesül. Innen már következik a lemma:

∑_{\underline{b}∈A} |F (⟨\underline{b}, \underline{α}⟩)|^{2} ≥ |F (⟨\underline{b}^{∗}, \underline{α}⟩)|^{2} ≥ (\frac{2}{π} Q_{1})^{2} .

2.1.3. Tétel. Q = ⌊2N^{\frac{1}{d+1}} ⌋, Q_{1} = ⌊\frac{Q^{d}}{2} ⌋ választással létezik olyan \underline{a}, \underline{b} ∈ ℤ^{d}, hogy

|D (\underline{a}, \underline{b})| ≥ c · N^{\frac{d}{2d+2}} \sqrt{\frac{∑_{\underline{a}∈[1,N]^{d}} |c\underline{a}|^{2}}{N^{d}}} ,

ahol c d-től függő konstans. Bizonyítás. Alkalmazzuk a 2.1.1. tételt (a feltételek teljesülnek), és az egyszerűség kedvéért a továbbiakban legyen S = ∑_{\underline{a}∈[1,N]^{d}} |c\underline{a}|^{2}. A tétel szerint

∑_{\underline{b}∈A} ∑_{\underline{a}∈B(\underline{b})} |D (\underline{a}, \underline{b})|^{2} ≥ (\frac{2}{π} Q_{1})^{2} S.

2. d-dimenziós számtani sorozatok diszkrepanciája

Jelöljük max_{\underline{b}∈A,\underline{a}∈B(\underline{b})} |D (\underline{a}, \underline{b})|-et M-mel. Az előző egyenlőtlenségből:

M^{2} ∑_{\underline{b}∈A} |B (\underline{b})| ≥ (\frac{2}{π} Q_{1})^{2} S.  (1)

Legyen \underline{b} = (b_{1}, b_{2}, …, b_{d}) ∈ A rögzített vektor. Akkor

B (\underline{b}) = ⋃_{k=0}^{Q_{1}−1} ([1, N]^{d} − k · \underline{b})
= ( ⋃_{k=0}^{Q_{1}−2} ([1, N]^{d} − k · \underline{b}) \ ([1, N]^{d} − (k + 1) · \underline{b})) ⋃ ([1, N]^{d} − (Q_{1} − 1) · \underline{b}) ,

és egyszerűen ellenőrizhető, hogy a jobb oldalon álló Q_{1} darab halmaz diszjunkt. Látható, hogy

|([1, N]^{d} − k · \underline{b}) \ ([1, N]^{d} − (k + 1) · \underline{b})| = |([1, N]^{d}) \ ([1, N]^{d} − \underline{b})|
= N^{d} − ∏_{i=1}^{d} (N − |b_{i}|) ,

(felhasználva, hogy |b_{i}| ≤ Q ≤ N minden 1 ≤ i ≤ d-re), és ezért

|B (\underline{b})| = (Q_{1} − 1) (N^{d} − ∏_{i=1}^{d} (N − |b_{i}|)) + N^{d} = Q_{1}N^{d} − (Q_{1} − 1) ∏_{i=1}^{d} (N − |b_{i}|) .

Így

∑_{\underline{b}∈A} |B (\underline{b})| = ( ∑_{−Q≤b_{1}≤Q} ∑_{−Q≤b_{2}≤Q} … ∑_{−Q≤b_{d}≤Q} |B (\underline{b})|) − |B (\underline{0})|
= ( ∑_{−Q≤b_{1}≤Q} ∑_{−Q≤b_{2}≤Q} … ∑_{−Q≤b_{d}≤Q} (Q_{1}N^{d} − (Q_{1} − 1) ∏_{i=1}^{d} (N − |b_{i}|))) − N^{d}
= ((2Q + 1)^{d} Q_{1} − 1) N^{d} − (Q_{1} − 1) ∏_{i=1}^{d} ∑_{−Q≤b_{i}≤Q} (N − |b_{i}|)
= ((2Q + 1)^{d} Q_{1} − 1) N^{d} − (Q_{1} − 1) ((2Q + 1) N − Q (Q + 1))^{d} .

Ha x ≥ y ≥ 0, akkor

dx^{d−1}y ≥ y ∑_{j=0}^{d−1} x^{d−1−j} (x − y)^{j} = x^{d} − (x − y)^{d} ,

ezért

(x − y)^{d} ≥ x^{d} − dx^{d−1}y.

Alkalmazva ezt x = (2Q + 1) N és y = Q (Q + 1) választással:

∑_{\underline{b}∈A} |B (\underline{b})| ≤ ((2Q + 1)^{d} Q_{1} − 1) N^{d} −
− (Q_{1} − 1) ((2Q + 1)^{d} N^{d} − dQ (Q + 1) (2Q + 1)^{d−1} N^{d−1})
= ((2Q + 1)^{d} − 1) N^{d} + d (Q_{1} − 1) Q (Q + 1) (2Q + 1)^{d−1} N^{d−1}
≤ 3^{d}Q^{d}N^{d} + d 3^{d}Q_{1}Q^{d+1}N^{d−1} ≤ c_{1} (d) Q_{1}N^{d−1} (N + QQ_{1}) .

Összevetve ezt a korábban nyert (1) egyenlőtlenséggel:

M ≥ \sqrt{c_{2} (d) \frac{Q_{1}^{2}S}{Q_{1}N^{d−1} (N + QQ_{1})}} ≥ c (d) N^{\frac{d}{2d+2}} \sqrt{\frac{S}{N^{d}}} ,

és éppen ezt kellett belátnunk. 2.1.4. Következmény.

disc (H) ≥ cN^{\frac{d}{2d+2}} ,

ahol a c konstans csak d-től függ. Bizonyítás. Azt kell belátnunk, hogy tetszőleges f : [1, N]^{d} → {−1, 1} függvényhez létezik olyan \underline{a}, \underline{a} + \underline{b}, …, \underline{a} + r · \underline{b} számtani sorozat [1, N]^{d}-ben, amelyre

|∑_{k=0}^{r} f (\underline{a} + k · \underline{b})| ≥ cN^{\frac{d}{2d+2}} .

Alkalmazva a 2.1.3. tételt a c\underline{a} = f (\underline{a}) (\underline{a} ∈ [1, N]^{d}) számokra éppen a bizonyítandó állítást kapjuk.

Könnyen bizonyítható az alábbi, 1.1.1. tétellel analóg állítás is:

2.1.5. Következmény. Tetszőleges A ⊆ [1, N]^{d} halmazhoz létezik olyan [1, N]^{d}-beli \{\underline{a} + i · \underline{b} : 0 ≤ i < k\} számtani sorozat, amelyre

| ∑_{\begin{matrix}0≤i<k \\ \underline{a}+i·\underline{b}∈A \end{matrix}} 1 − ηk| ≥ c\sqrt{η (1 − η)}N^{\frac{d}{2d+2}} ,

ahol η = \frac{|A|}{N^{d}}, és c d-től függő konstans.

2.2. A diszkrepancia felső becslése

Először megmutatjuk, hogy az előbb belátott 2.1.4. és 2.1.5. állítások élesek. Ehhez az 1.2.6. tétel bizonyítását fogjuk adaptálni.

2.2.1. Tétel. Minden N-re létezik olyan f : [1, N]^{d} → {−1, 1} színezés, hogy tetszőleges \{\underline{a}, \underline{a} + \underline{b}, …, \underline{a} + (k − 1) \underline{b}\} ⊆ [1, N]^{d} számtani sorozatra

|∑_{i=0}^{k−1} f (n + iq)| ≤ cN^{\frac{d}{2d+2}} (log N)^{\frac{5}{2}} .

Bizonyítás. Jelöljük i ≤ j esetén AP(\underline{a}, \underline{b}, i, j)-vel azt a \underline{b}-differenciájú számtani sorozatot, amelynek első eleme \underline{a} + i\underline{b}, utolsó eleme pedig \underline{a} + j\underline{b}. Szükségünk lesz a d-dimenziós elemi számtani sorozatokra. Egy számtani sorozatot eleminek nevezünk, ha a hossza 2-hatvány (pl. 2^{s}, s ≥ 0), a differenciája \underline{b} ≠ \underline{0}, és az első eleme \underline{a} + (i2^{s}) \underline{b}, ahol i ≥ 0 és \underline{a} ∈ [1, N]^{d} \ ([1, N]^{d} − \underline{b}). Azaz formálisan, ha AP(\underline{a}, \underline{b}, i2^{s}, (i + 1) 2^{s} − 1) alakú, ahol i, s, \underline{a}, \underline{b} teljesíti az előbb felsorolt feltételeket (d = 1-re ez lényegében visszadja az eredeti definíciót). Jelöljük H_{N}-nel az [1, N]^{d}- be eső elemi számtani sorozatok családját. Próbájuk meg megbecsülni egy fix k-ra a deg({A ∈ H_{N} : |A| ≥ k + 1}) értékét. A definícióból adódóan

deg ({A ∈ H_{N} : |A| ≥ k + 1}) =

= max_{\underline{m}} |\{\underline{m} ∈ AP (\underline{a}, \underline{b}, i2^{s}, (i + 1) 2^{s} − 1) ⊆ [1, N]^{d} : 2^{s} ≥ k + 1\}|

(ahol persze a második tagban AP(\underline{a}, \underline{b}, i2^{s}, (i + 1) 2^{s} − 1) elemi számtani sorozat). Ahhoz, hogy létezzen \underline{b} differenciájú legalább k + 1 hosszú számtani sorozat [1, N]^{d}- ben, minden 1 ≤ j ≤ d-re teljesülnie kell az alábbi egyenlőtlenségnek:

−\frac{N}{k} ≤ b_{j} ≤ \frac{N}{k} ,

(ahol \underline{b} = (b_{1}, …, b_{d})). Fix \underline{b}, \underline{m} ∈ [1, N]^{d}-re pontosan egy olyan [1, N]^{d} \ ([1, N]^{d} − \underline{b})- beli \underline{a} vektor van, amelyből \underline{b} differenciájú számtani sorozattal el tudunk jutni \underline{m}-be (vegyük a legnagyobb olyan l ≥ 0-t, amelyre még teljesül \underline{m} − l · \underline{b} ∈ [1, N]^{d}, akkor csak a kapott \underline{m} − l · \underline{b} lehet megfelelő \underline{a}-ra). Ha \underline{a}, \underline{b} ∈ [1, N]^{d} és s ≥ 0 rögzített, akkor ahhoz, hogy létezzen AP(\underline{a}, \underline{b}, i2^{s}, (i + 1) 2^{s} − 1) ⊆ [1, N]^{d} elemi számtani sorozat, \underline{a} + (2^{s} − 1) \underline{b} ∈ [1, N]^{d}-nek kell teljesülnie. (Világos, hogy ha ez teljesül, akkor legfeljebb egy olyan i ≥ 0 van, amire \underline{m} ∈AP(\underline{a}, \underline{b}, i2^{s}, (i + 1) 2^{s} − 1).) Látható, hogy ha \underline{a}, \underline{b} ∈ [1, N]^{d} rögzített, akkor s legfeljebb log_{2} (_{\frac{N}{k max_{1≤j≤d}|b_{j}|}}) olyan különböző értéket vehet fel, amire 2^{s} ≥ k + 1, és \underline{a} + (2^{s} − 1) \underline{b} ∈ [1, N]^{d}. Bevezetve a ∥b∥_{d} = max_{1≤j≤d} |b_{j}| jelölést, eddigi eredményeink így összegezhetők:

deg (\{A ∈ H_{N} : |A| ≥ k + 1\}) ≤ ∑_{∥b∥_{d}≤ \frac{N}{k}} log_{2} (\frac{N}{k ∥b∥_{d}} ) .

Rögzített z ≥ 1 egész esetén |\{∥\underline{m}∥_{d} = z : \underline{m} ∈ ℤ^{d}\}| = |[−z, z]^{d} \ [− (z − 1) , z − 1]^{d}| = (2z + 1)^{d} − (2z − 1)^{d} , ahol [−z, z] = {−z ≤ n ≤ z : n ∈ ℤ}. Emiatt

∑_{∥b∥_{d}≤ \frac{N}{k}} log_{2} (\frac{N}{k ∥b∥_{d}} ) = ∑_{1≤z≤ \frac{N}{k}} ((2z + 1)^{d} − (2z − 1)^{d}) log_{2} (\frac{N}{kz} ) .

Az f (z) = (2z − 1)^{d} jelölést bevezetve:

∑_{1≤z≤ \frac{N}{k}} ((2z + 1)^{d} − (2z − 1)^{d}) log_{2} (\frac{N}{kz} ) = ∫_{1}^{⌊\frac{N}{k} ⌋+1}log_{2} (\frac{N}{k ⌊z⌋}) df (z)

= (3^{d} − 1) log_{2} (\frac{N}{k} ) + ∫_{2}^{⌊\frac{N}{k} ⌋+1}log_{2} (\frac{N}{k ⌊z⌋}) df (z) .

Az f (z) függvény monoton nő, log_{2} (\frac{N}{k⌊z⌋}) ≤ log_{2} (\frac{N}{k(z−1)}), ha z > 1, ezért

(3^{d} − 1) log_{2} (\frac{N}{k} ) + ∫_{2}^{⌊\frac{N}{k} ⌋+1}log_{2} (\frac{N}{k ⌊z⌋}) df (z) ≤

≤ (3^{d} − 1) log_{2} (\frac{N}{k} ) + \begin{matrix}⌊ & \frac{N}{k} & ⌋ \\ ∫ \\ 1 \end{matrix}log_{2} (\frac{N}{kz} ) df (z) .

Mivel

∫ log_{2} (\frac{u}{z}) df (z) = ∫ d log_{2} (\frac{u}{z}) z^{d−1}dz = z^{d} (log_{2} (\frac{u}{z}) + \frac{1}{d log 2}) ,

ezért

\begin{matrix}⌊ & \frac{N}{k} & ⌋ \\ ∫ \\ 1 \end{matrix}log_{2} (\frac{N}{kz} ) df (z) = ⌊\frac{N}{k} ⌋^{d} (log_{2} (\frac{N}{k ⌊\frac{N}{k} ⌋}) + \frac{1}{d log 2}) − (log_{2} (\frac{N}{k} ) + \frac{1}{d log 2}) .

Ezek után már könnyen ellenőrizhető, hogy létezik olyan csak d-től függő c_{1} konstans, amellyel

deg (\{A ∈ H_{N} : |A| ≥ k + 1\}) ≤ ∑_{1≤z≤ \frac{N}{k}} ((2z + 1)^{d} − (2z − 1)^{d}) log_{2} (\frac{N}{kz} ) ≤ c_{1} (\frac{N}{k + 1})^{d} .

Így t = (c_{1}N)^{\frac{d}{d+1}} választással H_{N}-re teljesül az 1.2.4. tétel feltétele, és a tétel állítása szerint ezért

disc (H_{N}) ≤ c_{0}\sqrt{t}\sqrt{(log |H_{N}|)} log |S (H_{N})| .

Ha AP(\underline{a}, \underline{b}, i2^{s}, (i + 1) 2^{s} − 1) ⊆ [1, N]^{d} elemi, akkor 1 ≤ j ≤ d-re b_{j} = 0 vagy AP(a_{j}, b_{j}, i2^{s}, (i + 1) 2^{s} − 1) ⊆ [1, N] elemi számtani sorozat egydimenzióban. Egyszerű leszámlálás mutatja, hogy egydimenziós elemi számtani sorozatból legfeljebb 2N^{2} darab van, ezért

|H_{N}| ≤ c_{2}N^{2d}

valamely c_{2} konstanssal. Mivel |S (H_{N})| = N^{d}, ezért az előző egyenlőtlenségekből

disc (H_{N}) ≤ cN^{\frac{d}{2d+2}} (log N)^{\frac{3}{2}}

adódik, ahol a konstans csak d-től függ. Innen a már látott úton fejezhető be a bizonyítás. Tetszőleges [1, N]^{d}-be eső számtani sorozat felírható

AP (\underline{a}, \underline{b}, 0, p_{1}) \AP (\underline{a}, \underline{b}, 0, p_{2})

alakban, ahol \underline{a} ∈ [1, N]^{d} \ ([1, N]^{d} − \underline{b}), és mindkét számtani sorozat [1, N]^{d}-be esik. AP(\underline{a}, \underline{b}, 0, p_{i}) viszont i = 1, 2-re felírható legfeljebb log_{2} N elemi számtani sorozat diszjunkt uniójaként, ebből pedig következik a tétel állítása.

Knieper azt is vizsgálta, hogy mi mondható az [1, N]^{2} négyzetrács szakaszainak diszkrepanciájáról ([5]). Tehát most a hipergráfunk

H_{L} = \{AP (\underline{a}, \underline{b}, 0, k) ⊆ [1, N]^{2} : \underline{b} = (b_{1}, b_{2}) ≠ \underline{0} és b_{1}, b_{2} relatív prímek\} ,

és disc(H_{L}) becslése a feladat. Knieper valószínűségszámítási módszerekkel bizonyítja, hogy

disc (H_{L}) ≤ c\sqrt{N log N},

és részletes bizonyítás nélkül közli a

disc (H_{L}) ≥ c_{1}\sqrt[4]{N}

eredményt. Vegyük észre, hogy az általunk bizonyított 2.2.1. tételből lényegesen erősebb felső becslés jön ki disc(H_{L})-re. Mivel H_{L} elemei 2-dimenziós [1, N]^{2}-beli számtani sorozatok, ezért nyilván

disc (H_{L}) ≤ disc (H) ,

ahol H az összes 2-dimenziós [1, N]^{2}-beli számtani sorozat halmaza. A 2.2.1. tétel d = 2-re a

disc (H) ≤ c\sqrt[3]{N} (log N)^{\frac{5}{2}}

felső becslést adja, és ez így felső becslés disc(H_{L})-ra is. Valószínűleg az igazság \sqrt[3]{N} ”körül” van, de ezt nem sikerült bebizonyítani.

Kéttagú összegek eloszlásának

irregularitása

Ebben a részben Roth tételének egy másik lehetséges általánosítását tárgyaljuk. Legyen ismét A ⊆ [1, N], és η = \frac{|A|}{N}. A eloszlása helyett most vizsgáljuk az Aból elkészíthető kéttagú összegek eloszlását (multiplicitással). Az, hogy a kéttagú összegek eloszlásában fellelhetők irregularitások, nem meglepő, ha figyelembe vesszük Erdős, Sárközy és T. Sós egy tételét ([4]). Ez ”lényegében” azt mondja ki, hogy ha egy végtelen, egészekből álló halmaz komplementerére teljesülnek bizonyos gyenge feltételek, akkor a belőle készített kéttagú összegek között ”több” a páros, mint a páratlan. Mi kvantitatív jellegű állításokat fogunk bizonyítani az irregularitásokról. Legyen

f (n) = ∑_{\begin{matrix}a_{1}+a_{2}=n \\ a_{1},a_{2}∈A \end{matrix}} 1,

3. Kéttagú összegek eloszlásának irregularitása

f (n) azt mutatja meg, hogy n hányféleképpen áll elő kéttagú összegként A-beli tagokkal. Azt vizsgáljuk, hogy mennyire lehet ez a függvény közel az ”ideálishoz” a számtani sorozatokban. Persze ehhez meg kell mondanunk, hogy mi az az ideális függvény, amihez viszonyítunk. Jelöljük g (n)-nel azt, hogy n hányféleképpen áll elő kéttagú összegként [1, N]-beli tagokkal, azaz

g (n) = ∑_{\begin{matrix}1≤k≤N \\ 1≤n−k≤N \end{matrix}} 1.

Ha véletlenszerűen konstruálnánk A-t, hogy minden n ∈ [1, N] számot egymástól függetlenül η valószínűséggel választanánk be A-ba, akkor f (n) várható értéke körülbelül η^{2}g (n) lenne (pontosabban a várható érték η^{2}g (n) − (η^{2} − η) ha n páros, egyébként η^{2}g (n)). Így ésszerű, hogy az f (n) függvényt az η^{2}g (n)-hez viszonyítjuk, ez utóbbit tekintjük ”ideális”-nak. (Egy másik lehetséges magyarázat: az eredeti problémában A eloszlását egy η sűrűségű [1, N]-en egyenletes eloszláshoz viszonyítottuk. Az f (n) függvényt megkaphatjuk az A generátorfüggvénye négyzetének megfelelő együtthatóiból, és ha ugyanezt elvégezzük az előbbi egyenletes eloszlásra, akkor az együtthatók éppen rendre η^{2}g (n)-et adnak.) Vegyük észre, hogy a két szélsőséges esetben, amikor η = 0 vagy 1, akkor f (n) = η^{2}g (n) minden n-re, azaz csakúgy, mint az eredeti problémánál ezekben az esetekben az eloszlás megegyezik az ideális eloszlással. Egy adott n, n + q, …, n + (k − 1) q számtani sorozatban az ideálistól való eltérést méri az alábbi függvény:

A(n, q, k) = |∑_{i=0}^{k−1} (f(n + iq) − η^{2}g(n + iq))| ,

mi azt fogjuk vizsgálni, hogy mennyire lehet kicsi ezen eltérések maximuma. Az 1.1.1. tétellel analóg módon alsó becslést adunk az eltérések maximumára, azaz belátjuk, hogy a kéttagú összegek eloszlása nem lehet túl közel az ideálishoz a számtani sorozatokban (kivéve a két triviális esetet). A felső becsléshez olyan nem triviális A-t konstruálunk, amire a számtani sorozatok egy nagy részén alacsony a fenti eltérés. Végül megvizsgáljuk a probléma moduláris változatát is.

3.1. Alsó becslés

3.1.1. Tétel. Legyen ε > 0 és N > N_{ε}, akkor tetszőleges A ⊆ [1, N]-re léteznek olyan n és q egészek, hogy 1 ≤ q ≤ ⌊\sqrt{N}⌋, és

A(n, q, ⌊\frac{⌊\sqrt{N}⌋}{2}⌋) ≥ (\frac{1}{6\sqrt{3}π} − ε) η(1 − η)N^{\frac{3}{4}} .

A korábban bevezetett jelöléseket fogjuk használni, legyen Q = ⌊\sqrt{N}⌋ és Q_{1} = ⌊^{\frac{⌊\sqrt{N}⌋}{2}}⌋. A bizonyítás alapja az 1.1.2. tétel lesz, de először szükségünk lesz az alábbi lemmára.

3.1.2. Lemma. Ha N ≥ 8, akkor

∑_{i=1}^{2N} (f(i) − η^{2}g(i))^{2} ≥ \frac{1}{48} (η (1 − η) N)^{2} .

Bizonyítás. Ha η = 0 vagy 1 (azaz η (1 − η) = 0), akkor ∑_{i=1}^{2N} (f(i) − η^{2}g(i))^{2} = 0. Ha |A| = 1 (azaz η = \frac{1}{N}), és A = \{a\}, akkor

∑_{i=1}^{2N} (f(i) − η^{2}g(i))^{2} ≥ (f(2a) − η^{2}g(2a))^{2} ≥ (1 − \frac{1}{N^{2}} N)^{2} = (η (1 − η) N)^{2} .

Ha |A| = N − 1 (η = 1 − \frac{1}{N}), és A = [1, N] \ \{a\}, akkor

f(a) = g(a) = a − 1,

és

f(N + a + 1) = g(N + a + 1) = max (N − a − 1, 0) .

3. Kéttagú összegek eloszlásának irregularitása

Könnyen látható, hogy max (g(a), g(N + a + 1)) ≥ \frac{N}{3} , így ebben az esetben

∑_{i=1}^{2N} (f(i) − η^{2}g(i))^{2} ≥ (\frac{N}{3} − η^{2} \frac{N}{3} )^{2} = \frac{1}{9} ((1 − η^{2}) N)^{2} ≥ \frac{1}{9} (η (1 − η) N)^{2} .

Tehát a továbbiakban feltehetjük, hogy 2 ≤ |A| ≤ N − 2. Legyen F (α) = ∑_{i=1}^{2N} f(i)e(iα), és G(α) = ∑_{i=1}^{2N} η^{2}g(i)e(iα). A definíciókból látszik, hogy

F (α) = (∑_{a∈A} e(aα))^{2} ,

és

G(α) = η^{2} (∑_{i=1}^{N} e(iα))^{2} = η^{2} (\frac{e((N + 1)α) − e(α)}{e(α) − 1})^{2} .

A Parseval formulából következik, hogy

∑_{i=1}^{2N} (f(i) − η^{2}g(i))^{2} = ∫_{0}^{1} |F (α) − G(α)|^{2} dα.  (1)

A Cauchy-Schwarz egyenlőtlenségből:

\sqrt{∫_{0}^{1} |F (α) − G(α)|^{2} dα} ≥ ∫_{0}^{1} |F (α) − G(α)| dα.  (2)

Mivel 2 ≥ |e(⌊\frac{N}{2} ⌋ α) − 1|, ezért

4 ∫_{0}^{1} |F (α) − G(α)| dα ≥ ∫_{0}^{1} |F (α) − G(α)| |e(⌊\frac{N}{2} ⌋ α) − 1|^{2} dα.  (3)

Triviálisan becsülve a jobb oldalon integrált függvényt:

|F (α) − G(α)| |e(⌊\frac{N}{2} ⌋ α) − 1|^{2} ≥ |F (α)(e(⌊\frac{N}{2} ⌋ α) − 1)^{2}| − |G(α)(e(⌊\frac{N}{2} ⌋ α) − 1)^{2}| .

3. Kéttagú összegek eloszlásának irregularitása

Egyszerű átalakításokkal, és a Parseval formula felhasználásával:

∫_{0}^{1} |G(α)(e(⌊\frac{N}{2} ⌋ α) − 1)^{2}| dα = ∫_{0}^{1} η^{2} |(\frac{e((N + 1)α) − e(α)}{e(α) − 1})^{2} (e(⌊\frac{N}{2} ⌋ α) − 1)^{2}| dα
= η^{2} ∫_{0}^{1} |\frac{e(⌊\frac{N}{2} ⌋ α) − 1}{e(α) − 1} (e((N + 1)α) − e(α))|^{2} dα
= η^{2} ∫_{0}^{1} | ∑_{i=0}^{⌊\frac{N}{2} ⌋−1} e(iα)|^{2} |e((N + 1)α) − e(α)|^{2} dα
= η^{2} ∫_{0}^{1} |− \begin{matrix}⌊ & \frac{N}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix} e(iα) + ∑_{i=N+1}^{N+⌊\frac{N}{2} ⌋} e(iα)|^{2} dα
= 2η^{2} ⌊\frac{N}{2} ⌋ ≤ η^{2}N.

Ezért

∫_{0}^{1} |F (α) − G(α)| |e(⌊\frac{N}{2} ⌋ α) − 1|^{2} dα ≥ ∫_{0}^{1} |F (α) (e(⌊\frac{N}{2} ⌋ α) − 1)^{2}| dα − η^{2}N.

Másrészt,

F (α) (e(⌊\frac{N}{2} ⌋ α) − 1)^{2} = ((∑_{a∈A} e(aα)) (e(⌊\frac{N}{2} ⌋ α) − 1))^{2} = ( ∑_{i=1}^{i=N+⌊\frac{N}{2} ⌋} a_{i}e(iα))^{2} ,

ahol

a_{i} = \{ \begin{matrix}−1 & ha & i ∈ A és i − ⌊\frac{N}{2} ⌋ ∉ A, \\ 1 & ha & i ∉ A és i − ⌊\frac{N}{2} ⌋ ∈ A, \\ 0 & & egyébként. \end{matrix}

Mivel

∫_{0}^{1} |F (α) (e(⌊\frac{N}{2} ⌋ α) − 1)^{2}| dα = ∑_{i=1}^{N+⌊\frac{N}{2} ⌋} |a_{i}|^{2} = ∑_{i=1}^{N+⌊\frac{N}{2} ⌋} |a_{i}| ,

ezért az integrál értéke megegyezik azon i egészek számával, amelyekre a_{i} ≠ 0. Ha 1 ≤ i ≤ ⌊\frac{N}{2} ⌋, és i ∈ A, akkor a_{i} = −1, mert i − ⌊\frac{N}{2} ⌋ ≤ 0, és így i − ⌊\frac{N}{2} ⌋ ∉ A. Hasonlóan, ha N − ⌊\frac{N}{2} ⌋ < i ≤ N, és i ∈ A, akkor a_{i+⌊\frac{N}{2} ⌋} = 1. Ha i ∈ A ,akkor 1 ≤ i ≤ ⌊\frac{N}{2} ⌋ vagy N−⌊\frac{N}{2} ⌋ < i ≤ N, és ha N páratlan, akkor i = ⌊\frac{N}{2} ⌋+1 is lehetséges. Az előzőekből következik, hogy az integrál értéke legalább |A| − 1 = ηN − 1, és ezért

∫_{0}^{1} |F (α) − G(α)| |e(⌊\frac{N}{2} ⌋ α) − 1|^{2} dα ≥ ηN − η^{2}N − 1 = η (1 − η) N − 1.

2 ≤ |A| ≤ N − 2, és N ≥ 8, ezért

η (1 − η) N ≥ \frac{2 (N − 2)}{N} ≥ \frac{3}{2},

és

η (1 − η) N − 1 ≥ \frac{1}{3}η (1 − η) N.

Akkor pedig az (1), (2) és (3) felhasználásával következik a lemma állítása.

A 3.1.1. tétel bizonyítása. Az 1.1.3. következményt fogjuk használjuk az M = 2N, s_{j} = f(j) − η^{2}g(j), ha 1 ≤ j ≤ M, és R = Q = ⌊\sqrt{N}⌋ értékekkel. A következmény szerint létezik n, 1 ≤ q ≤ Q, hogy

|A(n, q, Q_{1})| ≥ \frac{2}{π} Q_{1}\sqrt{∑_{m=1}^{2N} |s_{m}|^{2}} (2N + \frac{Q^{2}}{4} )^{− \frac{1}{2}} Q^{− \frac{1}{2}} .

A 3.1.2. lemmából

\sqrt{∑_{m=1}^{2N} |s_{m}|^{2}} ≥ \frac{1}{4\sqrt{3}}η (1 − η) N, ha N ≥ 8.

Ezért ha N elég nagy (N > N_{ε}), akkor

\frac{2}{π} Q_{1}\sqrt{∑_{m=1}^{2N} |s_{m}|^{2}} (2N + \frac{Q^{2}}{4} )^{− \frac{1}{2}} Q^{− \frac{1}{2}} ≥ (\frac{1}{6\sqrt{3}π} − ε) η(1 − η)N^{\frac{3}{4}} ,

és ebből már következik a bizonyítandó állítás. (A bizonyításból az is látszik, hogy az alsó becslés nem csak a maximumra, hanem az eltérések egy jelentős részének négyzetes középére is teljesül.)

3.2. Felső becslés

A 3.1.1. tétel alsó becslést adott a max_{n,1≤q≤Q} A(n, q, Q_{1}) kifejezésre, most megpróbálunk olyan A-t konstruálni, amire ez a maximum minél kisebb. A 3.2.1. tételben minden elég nagy N-re mutatunk olyan A ⊆ [1, N] halmazt (amire η ≈ \frac{1}{2}), hogy A(n, q, Q_{1}) ≤ cN minden n, 1 ≤ q ≤ Q egészre, és a ”legtöbb” ilyen n és q párra A(n, q, Q_{1}) ≤ c_{1}N^{\frac{5}{6}} log N (a konstansok mindenhol rögzítettek). A bizonyításban Sárközy azon módszerét adaptáljuk, amellyel felső becslést adott az eredeti Roth problémára ([3]).

3.2.1. Tétel. Legyen N pozitív egész, p prímszám, melyre N^{\frac{2}{3}} < p ≤ 2N^{\frac{2}{3}} . Legyen A az [1, N]-beli mod p kvadratikus maradékok halmaza, azaz

A = \{a : (\frac{a}{p}) = 1, 1 ≤ a ≤ N\} .

(Ahol (\frac{y}{p}) az ismert Legendre-szimbólum, (\frac{y}{p}) = 0 ha y ≡ 0 mod p.) Erre a halmazra

|η − \frac{1}{2}| ≤ c_{1}N^{− \frac{2}{3}} log N,

és

A(n, q, Q_{1}) ≤ c_{2}N

minden n, 1 ≤ q ≤ Q egészre. Továbbá ha N > N_{ε}, és tekintjük azon (n, q) párokat, amelyekre 1 ≤ q ≤ Q, és 1 − (Q − 1) q ≤ n ≤ N, akkor a párok legalább (1 − ε)- részére teljesül, hogy

A(n, q, Q_{1}) ≤ c_{3}N^{\frac{5}{6}} log N.

(A konstansok mind rögzítettek.)

Mauduit és Sárközy következő tételét ([8]) gyakran fogjuk használni. (Ez A. Weil híres tételének egy következménye ([17]).)

3.2.2. Tétel (Mauduit-Sárközy). Ha p prím, h(x) ∈ F_{p} [x] egy legfeljebb k-adfokú polinom, amely nem írható fel b (h_{1}(x))^{2} alakban (ahol b ∈ F_{p}, és h_{1}(x) ∈ F_{p} [x]), továbbá X, Y egészek, melyekre 0 < Y ≤ p, akkor

| ∑_{X<n≤X+Y} (\frac{h(n)}{p})| < 9k\sqrt{p} log p.

A 3.2.1. tétel bizonyítása előtt szükségünk lesz néhány lemmára.

3.2.3. Lemma. A 3.2.1. tételben definiált A ⊆ [1, N] halmazra:

|η − \frac{1}{2}| ≤ c_{1}N^{− \frac{2}{3}} log N.

Bizonyítás. A Csebisev tétel biztosítja, hogy létezik megfelelő p prím a konstrukcióhoz. Tekintsük a következő halmazokat j = −1, 0, 1-re:

B_{j} = \{i |(\frac{i}{p}) = j, 1 ≤ i ≤ N\} .

Látszik, hogy |B_{0}| = ⌊\frac{N}{p} ⌋, B_{1} = A és

∑_{i=1}^{N} (\frac{i}{p}) = |B_{1}| − |B_{−1}| = 2ηN − N + ⌊\frac{N}{p} ⌋ .

Tetszőleges a egészre ∑_{i=a}^{a+p−1} (\frac{i}{p}) = 0, és felhasználva a 3.2.2. tételt h(x) = x választással (vagy az ismert Pólya-Vinogradov egyenlőtlenséget):

|∑_{i=1}^{N} (\frac{i}{p})| = | ∑_{i=⌊\frac{N}{p} ⌋p}^{N} (\frac{i}{p})| ≤ 9\sqrt{p} log p.

Tehát |2ηN − N| ≤ 9\sqrt{p} log p + ⌊\frac{N}{p} ⌋, és ezért

|η − \frac{1}{2}| ≤ \frac{1}{2N} (9\sqrt{p} log p + ⌊\frac{N}{p} ⌋) .

Mivel N^{\frac{2}{3}} < p ≤ 2N^{\frac{2}{3}} , ezért ebből már következik a lemma állítása.

3.2.4. Lemma. Ha 2 ≤ n ≤ 2N, akkor

|f(n) − ∑_{k=x_{0}}^{x_{1}} (\frac{(\frac{k}{p}) + 1}{2}) (\frac{(\frac{n−k}{p}) + 1}{2})| ≤ cN^{\frac{1}{3}} ,

ahol x_{0} = 1, és x_{1} = n − 1, ha 2 ≤ n ≤ N, illetve x_{0} = n − N, és x_{1} = N, ha N + 1 ≤ n ≤ 2N.

Bizonyítás. Legyen először n rögzített egész, melyre 2 ≤ n ≤ N. Akkor

f(n) = ∑_{\begin{matrix}a_{1}+a_{2}=n \\ a_{1},a_{2}∈A \end{matrix}} 1 = ∑_{k=1}^{n−1} α_{k},

ahol α_{k} = 1 ha k, n − k ∈ A, és α_{k} = 0 egyébként. Legyen

C_{1} = {k |k or n − k ≡ 0 mod p, 1 ≤ k ≤ n − 1} ,

és

C = {1, 2, …, n − 1} \ C_{1}.

Akkor f(n) = ∑_{k∈C} α_{k} + ∑_{k∈C_{1}} α_{k}. Ha k ∈ C, akkor (\frac{k}{p}) = ±1, és α_{k} = 1 pontosan akkor, ha (\frac{k}{p}) = (\frac{n−k}{p}) = 1. Ennek segítségével ellenőrizhető, hogy k ∈ C esetén

α_{k} = (\frac{(\frac{k}{p}) + 1}{2}) (\frac{(\frac{n−k}{p}) + 1}{2}) .

Ha k ∈ C_{1}, azaz k vagy n − k többszöröse p-nek, akkor α_{k} = 0, és látszik, hogy

(\frac{(\frac{k}{p}) + 1}{2}) (\frac{(\frac{n−k}{p}) + 1}{2}) = \frac{(\frac{n}{p}) + 1}{4}.

Ezért

|f(n) − ∑_{k=1}^{n−1} (\frac{(\frac{k}{p}) + 1}{2}) (\frac{(\frac{n−k}{p}) + 1}{2})| = | ∑_{k∈C_{1}} (α_{k} − (\frac{(\frac{k}{p}) + 1}{2}) (\frac{(\frac{n−k}{p}) + 1}{2}))|
= |C_{1}| |\frac{(\frac{n}{p}) + 1}{4}| ≤ 2 ⌊\frac{n − 1}{p}⌋ |\frac{(\frac{n}{p}) + 1}{4}| .

Emiatt

|f(n) − ∑_{k=1}^{n−1} (\frac{(\frac{k}{p}) + 1}{2}) (\frac{(\frac{n−k}{p}) + 1}{2})| ≤ ⌊\frac{n − 1}{p}⌋ ≤ \frac{N}{p} ,

és mert N^{\frac{2}{3}} < p ≤ 2N^{\frac{2}{3}} , ezért következik a bizonyítandó állítás. Ha N + 1 ≤ n ≤ 2N, akkor

f(n) = ∑_{\begin{matrix}a_{1}+a_{2}=n \\ a_{1},a_{2}∈A \end{matrix}} 1 = ∑_{k=N−n}^{N} α_{k},

ahol α_{k} = 1, ha k, n − k ∈ A, és α_{k} = 0 egyébként. A bizonyítás az előző esethez hasonlóan befejezhető.

3.2.5. Lemma. Ha 2 ≤ n ≤ 2N, és p ∤ n, akkor

|\frac{1}{4}g(n) − ∑_{k=x_{0}}^{x_{1}} (\frac{(\frac{k}{p}) + 1}{2}) (\frac{(\frac{n−k}{p}) + 1}{2})| ≤ cN^{\frac{1}{3}} log N,

ahol x_{0} = 1, és x_{1} = n − 1, ha 2 ≤ n ≤ N, illetve x_{0} = n − N, és x_{1} = N, ha N + 1 ≤ n ≤ 2N. (A konstans rögzített.) Ha p | n, akkor

|\frac{1}{4}g(n) − ∑_{k=x_{0}}^{x_{1}} (\frac{(\frac{k}{p}) + 1}{2}) (\frac{(\frac{n−k}{p}) + 1}{2})| ≤ N.

Bizonyítás. Legyen először n rögzített egész, melyre 2 ≤ n ≤ N, és p ∤ n. Akkor

g(n) = ∑_{\begin{matrix}1≤k≤N \\ 1≤n−k≤N \end{matrix}} 1 = n − 1,

és

\frac{1}{4}g(n) − ∑_{k=x_{0}}^{x_{1}} (\frac{(\frac{k}{p}) + 1}{2}) (\frac{(\frac{n−k}{p}) + 1}{2}) = \frac{1}{4} (n − 1) − \frac{1}{4} ∑_{k=1}^{n−1} (\frac{k (n − k)}{p}) −

− \frac{1}{2} ∑_{k=1}^{n−1} (\frac{k}{p}) − \frac{1}{4} (n − 1) = −\frac{1}{4} ∑_{k=1}^{n−1} (\frac{k (n − k)}{p}) − \frac{1}{2} ∑_{k=1}^{n−1} (\frac{k}{p}).

Ismert, hogy ha (a, p) = 1, akkor∑_{k=1}^{p} (\frac{k(a−k)}{p}) = −(\frac{−1}{p}) (pl. [16, 5. fejezet]). Továbbá ha p ∤ n, akkor x(n − x) nem írható fel b (h_{1}(x))^{2} alakban F_{p} [x], és így alkalmazható a 3.2.2. tétel. Ezekből:

|∑_{k=1}^{n−1} (\frac{k (n − k)}{p})| ≤ ⌊\frac{n − 1}{p}⌋ + 18\sqrt{p} log p ≤ \frac{N}{p} + 18\sqrt{p} log p.

A 3.2.2. tételből, és ∑_{k=a}^{a+p−1} (\frac{k}{p}) = 0-ból, a már látott módon

|∑_{k=1}^{n−1} (\frac{k}{p})| ≤ 9\sqrt{p} log p.

A kapott egyenlőtlenségekből (figyelembe véve az N^{\frac{2}{3}} < p ≤ 2N^{\frac{2}{3}} egyenlőtlenséget) esetünkben következik a bizonyítandó állítás . Ha n egész, melyre N + 1 ≤ n ≤ 2N, és p ∤ n, akkor

g(n) = ∑_{\begin{matrix}1≤k≤N \\ 1≤n−k≤N \end{matrix}} 1 = 2N − n + 1.

A bizonyítás az előző esetben látott módon befejezhető. Ha 1 ≤ n ≤ 2N, és p | n, akkor

∑_{k=1}^{n−1} (\frac{k (n − k)}{p}) = ∑_{k=1}^{n−1} (\frac{−k^{2}}{p}) = (n − 1) (\frac{−1}{p}),

így az előbbi bizonyítás nem vihető véghez. De mert

0 ≤ ∑_{k=x_{0}}^{x_{1}} (\frac{(\frac{k}{p}) + 1}{2}) (\frac{(\frac{n−k}{p}) + 1}{2}) ≤ N

(ahol x_{0} és x_{1} a korábban látott módon definiáltak), és g(n) ≤ N, ezért

|\frac{1}{4}g(n) − ∑_{k=x_{0}}^{x_{1}} (\frac{(\frac{k}{p}) + 1}{2}) (\frac{(\frac{n−k}{p}) + 1}{2})| ≤ N,

és ez kellett a 3.2.5. lemma bizonyításnak befejezéséhez.

A 3.2.1. tétel bizonyítása. Felhasználva a 3.2.3. lemmát, és g(n) ≤ N-et:

|\frac{1}{4}g(n) − η^{2}g(n)| = g(n) |\frac{1}{2} + η| |\frac{1}{2} − η| ≤ N \frac{3}{2}c_{1}N^{− \frac{2}{3}} log N ≤ c′_{1}N^{\frac{1}{3}} log N.

A 3.2.4. és 3.2.5. lemmákból következik, hogy ha 2 ≤ n ≤ 2N, és p ∤ n, akkor

|f(n) − η^{2}g(n)| ≤ cN^{\frac{1}{3}} log N

(a konstans rögzített), és ha p | n, akkor

|f(n) − η^{2}g(n)| ≤ N.

Világos, hogy ha n < 2 vagy 2N < n, akkor f(n) = g(n) = 0. Legyen most n és 1 ≤ q ≤ Q rögzített. Mivel Q_{1} ≤ \frac{\sqrt{N}}{2} , és N^{\frac{2}{3}} < p prím, ezért az n, n + q, …, n + (Q_{1} − 1)q egészek közül legfeljebb egy osztható p-vel. Ezért

A(n, q, Q_{1}) = | ∑_{k=0}^{Q_{1}−1} (f(n + kq) − η^{2}g(n + kq))| ≤ cN^{\frac{1}{3}} Q log N + N ≤ cN^{\frac{5}{6}} log N + N.

Ez mutatja, hogy

A(n, q, Q_{1}) ≤ c_{2}N

egy fix c_{2} konstanssal. De az is következik, hogy ha az n, n + q, …, n + (Q_{1} − 1)q egészek egyike sem osztható p-vel, akkor

A(n, q, Q_{1}) ≤ cN^{\frac{5}{6}} log N.

Ha tekintjük az összes olyan n, n + q, …, n + (Q_{1} − 1)q számtani sorozatot, amely belemetsz [1, N]-be, és 1 ≤ q ≤ Q (ezek pontosan azok, amelyekre teljesül az 1 − (Q − 1) q ≤ n ≤ N egyenlőtlenség), akkor könnyen meggondolható, hogy legalább az (1 − \frac{2Q}{p})-részük nem tartalmaz p-vel osztható elemet. Mivel \frac{2Q}{p} ≤ 4N^{− \frac{1}{3}} ≤ ε , ha N ≥ N_{ε}, ezért ebből következik a 3.1.1. tétel utolsó állítása is.

Korábban megjegyeztük, hogy a 3.1.1. tétel bizonyításából kijön, hogy a maximális eltérésre bizonyított alsó becslés igaz lesz az eltérések egy bizonyos részének négyzetes közepére is. (Éppen az előbbi bizonyítás végén tekintett számtani sorozatokban vett eltérések négyzetes közepéről van szó.) Az előbbi bizonyítás eredményeit felhasználva könnyen igazolható, hogy a definiált A halmaz esetén a megfelelő négyzetes közép felülről becsülhető cN^{\frac{5}{6}} log N-nel. Látható, hogy itt nem sikerült belátni, hogy a 3.1.1. tétel éles (vagy legalább loghatványtól eltekintve éles). A sejtés az, hogy ez igaz, de a bizonyítása valószínűleg nehéz (figyelembe véve, hogy az eredeti problémánál is csak nehézségek árán lehetett ezt igazolni).

3.3. Moduláris változat

Legyen A ⊆ \{0, 1, …, q − 1\}, és η = \frac{|A|}{q}. Legyen

h(i) = ∑_{\begin{matrix}a_{1}+a_{2}≡i mod q \\ a_{1},a_{2}∈A \end{matrix}} 1.

Látható, hogy h (i) azt mutatja, hogy az i mod q maradékosztály hányféleképpen áll elő kéttagú összegként A-beli tagokkal. Mivel

\frac{1}{q} ∑_{i=0}^{q−1} h(i) = \frac{1}{q} |A|^{2} = η^{2}q,

ezért az A-ból készített kéttagú összegek eloszlása akkor lesz ”egyenletes” modq, ha max_{0≤i≤q−1} |h(i) − η^{2}q| ”kicsi”. A következő tétel és következménye alsó becslést ad az előbbi maximumra. 3.3.1. Tétel. Tetszőleges A ⊆ {0, 1, …, q − 1} esetén (ha q ≥ 2):

∑_{i=0}^{q−1} (h(i) − η^{2}q)^{2} ≥ \frac{q^{3}}{q − 1}η^{2} (1 − η)^{2} .

3.3.2. Következmény. Tetszőleges A ⊆ {0, 1, …, q − 1} halmazra, ahol q ≥ 2, létezik olyan 0 ≤ i ≤ q − 1 egész, hogy

|h(i) − η^{2}q| ≥ \sqrt{q}η (1 − η) .

A 3.3.1. tétel bizonyítása. Legyen S(α) = ∑_{a∈A} e(aα). Látható, hogy ha k egész, akkor

(S(\frac{k}{q}))^{2} = ∑_{i=0}^{q−1} h (i) e(i\frac{k}{q}).

Ismert (diszkrét Parseval formula), hogy ha B (α) = ∑_{j=0}^{q−1} b_{i}e (jα), akkor

\frac{1}{q} ∑_{k=0}^{q−1} |B (\frac{k}{q} )|^{2} = ∑_{j=0}^{q−1} |b_{j}|^{2} .

3. Kéttagú összegek eloszlásának irregularitása

Legyen b_{j} = h (j) − η^{2}q (0 ≤ j ≤ q − 1), akkor

∑_{i=0}^{q−1} (h(i) − η^{2}q)^{2} = \frac{1}{q} ∑_{k=0}^{q−1} |B (\frac{k}{q} )|^{2} .

B (0) = ∑_{i=0}^{q−1} h(i) − η^{2}q^{2} = 0, és ha 1 ≤ k ≤ q − 1, akkor

B (\frac{k}{q} ) = ∑_{j=0}^{q−1} (h (j) − η^{2}q) e (j \frac{k}{q} ) = ∑_{j=0}^{q−1} h (j) e (j \frac{k}{q} ) − η^{2}q ∑_{j=0}^{q−1} e (j \frac{k}{q} )
= ∑_{j=0}^{q−1} h (j) e (j \frac{k}{q} ) = (S(\frac{k}{q}))^{2} .

Ezért

∑_{i=0}^{q−1} (h(i) − η^{2}q)^{2} = \frac{1}{q} ∑_{k=1}^{q−1} |S (\frac{k}{q} )|^{4} .

S (0) = |A| = ηq, ezért

\frac{1}{q} ∑_{k=1}^{q−1} |S (\frac{k}{q} )|^{2} = \frac{1}{q} ∑_{k=0}^{q−1} |S (\frac{k}{q} )|^{2} − \frac{1}{q}η^{2}q^{2} = ηq − η^{2}q = qη (1 − η) .

A Cauchy-Schwarz egyenlőtlenséget használva:

∑_{i=0}^{q−1} (h(i) − η^{2}q)^{2} = \frac{1}{q} ∑_{k=1}^{q−1} |S (\frac{k}{q} )|^{4} ≥ \frac{1}{q (q − 1)} (∑_{k=1}^{q−1} |S (\frac{k}{q} )|^{2})^{2} =
= \frac{1}{q (q − 1)}q^{4}η^{2} (1 − η)^{2} = \frac{q^{3}}{q − 1}η^{2} (1 − η)^{2} .

Ezzel beláttuk a bizonyítandó állítást. A 3.3.1. tétel általánosításaként vizsgálhatjuk a ∑_{i=1}^{k} a_{i} alakú összegek eloszlását mod q, ahol a_{1}, a_{2}, …, a_{k} ∈ A, és k ≥ 2 rögzített egész. Legyen

h_{k}(n) = ∑_{\begin{matrix}a_{1}+a_{2}+...+a_{k}≡n mod q \\ a_{1},a_{2},... ,a_{k}∈A \end{matrix}} 1.

Világos, hogy \frac{1}{q} ∑_{i=0}^{q−1} h_{k}(i) = η^{k}q^{k−1}, és a 3.3.1. tétel bizonyításához hasonló módon belátható, hogy

∑_{i=0}^{q−1} (h_{k}(i) − η^{k}q^{k−1})^{2} ≥ \frac{q^{2k−1}}{(q − 1)^{k−1}} η^{k} (1 − η)^{k} .

A következő tételek azt mutatják, hogy mennyire éles a 3.3.1. tétel és a következménye. A 3.3.3. tétel azt mutatja, hogy a 3.3.1. tétel végtelen sok egészre lényegében éles, és a következő tétel szerint a 3.3.2. következmény log-hatványtól eltekintve mindig véges. (Ebből az is következik, hogy a 3.3.1. tétel is log-hatványtól eltekintve mindig véges.)

3.3.3. Tétel. Legyen p > 2 prímszám, és A = \{a : (\frac{a}{p}) = 1, 0 ≤ a ≤ p − 1\}. Erre a részhalmazra

∑_{i=0}^{p−1} (h(i) − η^{2}p)^{2} ≤ \frac{p^{3}}{p − 1}η^{2} (1 − η)^{2} + p.

Bizonyítás. |A| = \frac{p−1}{2}, η = \frac{1}{2} − \frac{1}{2p}, és

η^{2}p = \frac{(p − 1)^{2}}{4p} = \frac{p − 2}{4} + \frac{1}{4p}.

Mivel (\frac{a}{p}) = (\frac{−1}{p})(\frac{p−a}{p}), ezért h(0) = 0, ha (\frac{−1}{p}) = −1, és h(0) = \frac{p−1}{2}, ha (\frac{−1}{p}) = 1. Emiatt

(h(0) − η^{2}p)^{2} ≤ (\frac{p − 1}{2} − \frac{(p − 1)^{2}}{4p} )^{2} = \frac{p^{2}}{16} − \frac{1}{8} + \frac{1}{16p^{2}} .

Legyen most 1 ≤ a ≤ p − 1. Belátjuk, hogy

h(a) = ∑_{i=0}^{p−1} \frac{((\frac{i}{p}) + 1) ((\frac{a−i}{p}) + 1)}{4} − \frac{(\frac{a}{p}) + 1}{2} = ∑_{\begin{matrix}0≤i≤p−1 \\ i≠0,a \end{matrix}} \frac{((\frac{i}{p}) + 1) ((\frac{a−i}{p}) + 1)}{4}.

3. Kéttagú összegek eloszlásának irregularitása

Legyen f (n) = ∑_{\begin{matrix}a_{1}+a_{2}=n \\ a_{1},a_{2}∈A \end{matrix}} 1, akkor h(a) = f(a) + f(a + p). i és a − i pontosan akkor lesznek egyszerre A elemei, ha

\frac{((\frac{i}{p}) + 1) ((\frac{a−i}{p}) + 1)}{4} = 1,

egyébként

\frac{((\frac{i}{p}) + 1) ((\frac{a−i}{p}) + 1)}{4} = 0,

ha i ≠ 0, a. Hasonlóan i és a + p − i pontosan akkor lesznek egyszerre A-ban, ha

\frac{((\frac{i}{p}) + 1) ((\frac{a−i}{p}) + 1)}{4} = 1,

és egyébként

\frac{((\frac{i}{p}) + 1) ((\frac{a−i}{p}) + 1)}{4} = 0,

ha i ≠ 0, a. Ebből következik, hogy

∑_{\begin{matrix}0≤i≤p−1 \\ i≠0,a \end{matrix}} \frac{((\frac{i}{p}) + 1) ((\frac{a−i}{p}) + 1)}{4} = f(a) + f(a + p) = h(a).

Ezért

h (a) = ∑_{i=0}^{p−1} \frac{((\frac{i}{p}) + 1) ((\frac{a−i}{p}) + 1)}{4} − \frac{(\frac{a}{p}) + 1}{2}
= \frac{1}{4} ∑_{i=0}^{p−1} (\frac{i(a − i)}{p}) + \frac{1}{2} ∑_{i=0}^{p−1} (\frac{i}{p}) + \frac{p − 2}{4} − \frac{1}{2}(\frac{a}{p}).

Mivel ∑_{i=0}^{p−1} (\frac{i}{p}) = 0, és ∑_{i=0}^{p−1} (\frac{i(a−i)}{p}) = −(\frac{−1}{p}), így

h(a) = \frac{p − 2}{4} − \frac{1}{4}(\frac{−1}{p}) − \frac{1}{2}(\frac{a}{p}),

ha 1 ≤ a ≤ p − 1. Akkor

(h(a) − η^{2}p)^{2} = (\frac{p − 2}{4} − \frac{1}{4}(\frac{−1}{p}) − \frac{1}{2}(\frac{a}{p}) − \frac{p − 2}{4} − \frac{1}{4p})^{2} ≤ 1.

Összegezve eredményeinket:

∑_{i=0}^{p−1} (h(i) − η^{2}p)^{2} ≤ \frac{p^{2}}{16} − \frac{1}{8} + \frac{1}{16p^{2}} + p − 1,

és mert

\frac{p^{3}}{p − 1}η^{2} (1 − η)^{2} + p = \frac{1}{16}p^{2} + \frac{17}{16}p − \frac{1}{16} − \frac{1}{16p},

ezért a bizonyítandó állítás következik.

3.3.4. Tétel. Legyen q > 1 egész, és p prím, melyre 2q < p ≤ 4q. Tekintsük a következő A ⊆ {0, 1, 2, …, q − 1} halmazt:

A = \{a : (\frac{a}{p}) = 1, 1 ≤ a ≤ q\} .

(q nem oszthatja p-t, így ez valóban a mod q maradékosztályok egy részhalmaza lesz.) Erre a részhalmazra

|η − \frac{1}{2}| ≤ 9\frac{log(4q)}{\sqrt{q}},

és

|h(i) − η^{2}q| ≤ 50\sqrt{q} log(4q)

minden 0 ≤ i ≤ q − 1-re.

Bizonyítás. A Csebisev-tétel miatt létezik olyan p prím, melyre 2q < p ≤ 4q. A halmaz definíciójából következik, hogy

∑_{i=1}^{q} (\frac{i}{p}) = qη − q(1 − η) = q(2η − 1),

és a 3.2.2. tételből (vagy a Pólya-Vinogradov egyenlőtlenségből) így

q |2η − 1| = |∑_{i=1}^{q} (\frac{i}{p})| ≤ 9\sqrt{p} log p ≤ 18\sqrt{q} log(4q).

Emiatt pedig

|η − \frac{1}{2}| ≤ 9\frac{log(4q)}{\sqrt{q}}.

Legyen a egész, melyre 1 ≤ a ≤ q. A már látott technikával bizonyítható, hogy

f(a) = ∑_{i=1}^{a−1} \frac{((\frac{i}{p}) + 1) ((\frac{a−i}{p}) + 1)}{4} = \frac{1}{4} ∑_{i=1}^{a−1} (\frac{i(a − i)}{p}) + \frac{1}{2} ∑_{i=1}^{a−1} (\frac{i}{p}) + \frac{a − 1}{4}.

1 ≤ a < p, ezért x(a − x) nem írható fel b (h_{1}(x))^{2} alakban F_{p} [x]-ben, ezért használhatjuk a 3.2.2. tételt az első tagra, és nyílván a másodikra is:

|\frac{1}{4} ∑_{i=1}^{a−1} (\frac{i(a − i)}{p}) + \frac{1}{2} ∑_{i=1}^{a−1} (\frac{i}{p})| ≤ (\frac{18}{4} + \frac{9}{2}) \sqrt{p} log p ≤ 18\sqrt{q} log(4q).

Tehát

|f(a) − \frac{a − 1}{2}| ≤ 18\sqrt{q} log(4q).

Hasonlóan

f(a + q) = ∑_{i=a}^{q} \frac{((\frac{i}{p}) + 1) ((\frac{q+a−i}{p}) + 1)}{4}
= \frac{1}{4} ∑_{i=a}^{q} (\frac{i(q + a − i)}{p}) + \frac{1}{2} ∑_{i=a}^{q} (\frac{i}{p}) + \frac{q − a + 1}{4}.

1 ≤ a + q < p, ezért az előzőekhez hasonló módon belátható, hogy

|f(a + q) − \frac{q − a + 1}{4}| ≤ 18\sqrt{q} log(4q).

Ha 1 ≤ i ≤ q, akkor h(i) = f(i) + f(q + i) (és h(q) = h(0)), ezért a most belátott egyenlőtlenségek miatt

|h(i) − \frac{q}{4}| ≤ 36\sqrt{q} log(4q)

3. Kéttagú összegek eloszlásának irregularitása

minden 1 ≤ i ≤ q-re. Látszik, hogy

|\frac{q}{4} − η^{2}q| = \frac{q}{4} |2η − 1| |2η + 1| ≤ \frac{3}{4}q |2η − 1| ≤ \frac{27}{2}\sqrt{q} log(4q).

Ezért

|h(i) − η^{2}q| ≤ |h(i) − \frac{q}{4}| + |\frac{q}{4} − η^{2}q| ≤ \frac{99}{2}\sqrt{q} log(4q)

minden 0 ≤ i ≤ q − 1 egészre, és ezzel beláttuk a bizonyítandó állítást.

Nyitott kérdések

Ebben a részben a dolgozat során felmerült nyitott problémákat összegezzük. Mint láttuk, Roth eredeti, számtani sorozatok színezésére vonatkozó problémája teljesen megoldott, az ismert alsó és felső becslés csak konstans szorzóban tér el egymástól. A d-dimenziós általánosítások esetében már nem ez a helyzet, mind az általunk, mind a Knieper által vizsgált problémánál ([5]) a felső becslés egy loghatvány szorzóval rosszabb az alsó becslésnél. Mindkét esetben a bizonyítás Beck módszerét alkalmazza, esetleg Matoušek és Spencer bizonyítását adaptálva kihozható lenne a pontos felső becslés. (Knieper az általa vizsgált esetben sikertelenül próbálkozott ezzel.) Megoldatlan az N × N-es rácson tekintett szakaszok diszkrepanciájának meghatározása. A 2.2. részben bizonyítottunk egy felső becslést, a sejtés az, hogy ez log-hatvány szorzó erejéig éles, eddig azonban alsó becslést nem sikerült bizonyítani. A kéttagú összegek eloszlásának irregularitásairól szóló tételeknél is van hézag az ismert alsó és felső becslés között. Itt nem világos, hogy az alsó becslés vajon éles-e, bár az tűnik valószínűnek. A moduláris verzióban az alsó és felső becslés között a különbség csak egy log-hatvány szorzó, de esetleg ez is csökkenthető.

Irodalomjegyzék

[1] J. Beck. Roth’s estimate of the discrepancy of integer sequences is nearly sharp. Combinatorica, 1:319–325, 1981.

[2] H. Chernoff. A measure of asymptotic tests of a hypothesis based on the sum of observations. Ann. Math. Stat., 23:493–509, 1952.

[3] P. Erdős and A. Sárközy. Some solved and unsolved problems in combinatorial number theory. Math. Slovaca, 28:407–421, 1978.

[4] P. Erdős, A. Sárközy, and V. T. Sós. Problems and results on additive properties of general sequences, V. Monatshafte Math., 102:183–197, 1986.

[5] P. Knieper. Discrepancy of Arithmetic Progressions. PhD thesis, Institute für Informatic, Humboldt-Universität zu Berlin, 1997.

[6] Gy. Károlyi. Geometric discrepancy theorems in higher dimensions. Studia Sci. Math. Hung., 30:59–94, 1995.

[7] L. Lovász, J. H. Spencer, and K. Vesztergombi. Discrepancy of set-systems and matrices. European J. Combin., 7:151–160, 1986.

[8] C. Maudit and A. Sárközy. On finite binary sequences I: Measure of pseudorandomness, the Legendre symbol. Acta Arith., 82:365–377, 1997.

[9] K. F. Roth. Remark concerning integer sequences. Acta Arithmetica, IX:257– 260, 1964.

[10] W. Rudin. Some theorems on Fourier coefficients. Proc. Amer. Math. Soc., 10:855–859, 1959.

[11] J. Matoušek and J. Spencer. Discrepancy in arithmetic progressions. J. Amer. Math. Soc., 9:195–204, 1996.

[12] A. Sárközy. Some remarks concerning irregulaties of distribution of sequences of integers in arithmetic progressions, I. Coll. Math. Soc. J. Bolyai, 13:287–303, 1974.

[13] A. Sárközy. Some remarks concerning irregulaties of distribution of sequences of integers in arithmetic progressions, II. Studia Sci. Math. Hung., 11:79–104, 1976.

[14] A. Sárközy. Some remarks concerning irregulaties of distribution of sequences of integers in arithmetic progressions, III. Periodica Math. Hungar., 9:127–144, 1978.

[15] A. Sárközy. Some remarks concerning irregulaties of distribution of sequences of integers in arithmetic progressions, IV. Acta Math. Acad. Sci. Hung., 30:155– 162, 1977.

[16] I. M. Vinogradov. Elements of Number Theory. Dover, 1954.

[17] A. Weil. Sur les courbes algébriques et les variétés qui en déduisent. Actualités Sci. et Ind., 1041, 1948.