Kombinatorikus számelmélet

1.) Konstruáljunk (a mohó algoritmus segítségével) olyan Sidon halmazt, (azaz a természetes számoknak olyan A részhalmazát, melyre az x+y = u+v egyenletnek, ahol u, v, x, y ∈ A különböző számok, nincs megoldása) melynek metszete az {1, …, n} halmazzal legalább const.n^{1/3} számot tartalmaz.

A következő feladatokban fontos szerepet játszik a következő

Szemerédi tétel: Tetszóleges k > 0 pozitív egész és ε > 0 valós számra létezik olyan N_{0} = N_{0}(ε, k) küszöbindex, melyre igaz, hogy minden olyan A ⊂ {1, …, N} halmaz, N ≥ N_{0}, melyre |A| ≥ Nε tartalmaz k hosszúságú számtani sorozatot.

2.) Legyen A egész számokból álló mátrix, b egész elemekből álló vektor, melyekre az xA = b egyenletnek van olyan x = (x_{1}, …, x_{k}) megoldása, melynek minden x_{j} koordinátája különböző. a.) Bizonyítsuk be a Szemerédi tétel segítségével azt, hogy ha A a természetes

számok pozitív sűrűségű részhalmaza, a fenti egyenletben b = 0 és 1A = 0, 1 = (1, …, 1), akkor létezik (végtelen sok) olyan {m_{1}, …, m_{k}} ⊂ A, részhalmaz, melyre m = (m_{1}, …, m_{k}) teljesíti az mA = 0 egyenletet.

b.) Ha a b ≠ 0 vagy 1A ≠ 0 feltétel teljesül, akkor létezik a természetes számoknak olyan pozitív sűrűségű A részhalmaza, melyből nem választható ki az mA = b, m = (m_{1}, …, m_{k}), {m_{1}, …, m_{k}} ⊂ A egyenletet kielégítő k elemű számhalmaz.

A következő feladatban viszonylag sűrű három elemű számtani sorozatot nem tartalmazó halmazt konstruálunk. (Behrend konstrukciója.)

3.) Rögzítsünk egy d és s egész számot. Definiáljuk a

B(s, d) = {l: l = ∑_{j=0}^{s} a_{j}(2d + 1)^{j}, 0 ≤ a_{j} ≤ d, 0 ≤ j ≤ k}

halmazt, és vezessük be rajta az ∥l∥ = ( ∑_{j=0}^{s} a_{j}^{2})^{1/2} normát. Lássuk be, hogy

tetszőleges n számra az A_{n} = {l: l ∈ B(s, d), ∥l∥ = n} halmaz nem tartalmaz három elemű számtani sorozatot. a.) Az s, d és n számok alkalmas megválasztásával meg lehet adni az {1, …, N}

halmaz olyan három elemű számtani sorozatot nem tartalmazó (A_{n} tipusú) részhalmazát, melynek számossága nagyobb mint Ne^{−const. \sqrt{log N}}. (Érdemes

s = const. \sqrt{log N}, log(2d + 1) = \frac{1}{s} log N választást tenni. Miért?)

Be kívánjuk látni a Szemerédi tétel ekvivalenciáját egy Fürstenberg által megfogalmazott és közvetlenül (a Szemerédi tétel felhasználása nélkül) bebizonyított ergod elméleti tétellel.

Fürstenberg tétel: Legyen (X, B, μ) valószínűségi mező, T invertálható mértéktartó leképezés ezen a téren. Ekkor tetszőleges pozitív mértékű, μ(A) > 0, A ∈ B halmazra, és k egész számra létezik olyan n egész szám, melyre

μ ( ⋂_{j=0}^{k} T^{−jn}A) > 0  (∗)

4.) Lássuk be, hogy a Szemerédi tétel ekvivalens a következő állítással: Ha A a termé-

szetes számok pozitív felső sűrűségű halmaza, azaz lim sup_{n→∞} \frac{1}{n}|A ∩ \{1, …, n\}| > 0,

k > 1 tetszőleges természetes szám, akkor A tartalmaz k hosszúságú számtani sorozatot.

5.) Legyen B_{j}, j = 1, 2, …, olyan halmazok egy (X, B, μ) téren, melyekre μ(B_{j}) > ε minden j = 1, 2, … -ra valamilyen rögzített ε > 0-ra. Lássuk be a Szemerédi tétel segítségével, hogy ha N > N_{0} valamilyen N_{0} = N_{0}(ε, k) küszöbindex-szel, akkor létezik olyan a és b pozitív egész szám, melyre

μ(\{x: x ∈ B_{a+bj} ha j = 1, 2, …, k\}) > \frac{ε}{2N^{2}}

E tény segítségével mutassuk meg, hogy a Szemerédi tételből következik a Fürstenberg tétel. Segítség: x ∈ X pontok viszonylag nagy mérerű halmazára igaz, hogy az x ∈ B_{j} esemény sok j-re teljesül. Az ilyen x-ekre a Λ(x) = {j: x ∈ B_{j}} halmaz tartalmaz k hosszúságú számtani sorozatot a Szemerédi tétel szerint.

Legyen X = ∏_{n=−∞}^{∞} Z_{n}, Z_{n} = {0, 1}, azaz X a két irányban végtelen 0, 1 sorozatok

halmaza, B (a {0, 1} halmazon értelmezett diszkrét topológia által generált) szorzat σalgebra az X téren. Definiáljuk a T shift operátort X-en, azaz x = (…, ε_{j}, ε_{j+1}, …)-ra legyen Tx = (…, ε_{j+1}, ε_{j+2}, …), (ε_{j} = 0 vagy ε_{j} = 1, j = 0, ±1, ±2, …). Ahhoz, hogy a Fürstenberg tételből levezessük a Szemerédi tételt (annak a 4. feladatban megfogalmazott változatát) szükségünk van az (X, B) téren olyan T invariáns μ valószínűségi mértékre, mely lényegében egy előre megadott pozitív felső sűrűségű halmaz eltoltjaira van koncentrálva. (E konstrukcióban jól használható egy standard eredmény az analízisból (valószínűségszámításból), mely szerint kompakt téren definiált valószínűségi mértékeknek van gyengén konvergens részsorozata. A következő feladat célja ennek az állításnak a bizonyítása a 7. feladatban szükséges speciális esetben.

6.) Legyen μ_{n}, n = 1, 2, … valószínűségi mértékek egy sorozata a fent definiált (X, B)

téren. (X = ∏_{n=−∞}^{∞} Z_{n}, Z_{n} = {0, 1}). A μ_{n} sorozatnak létezik olyan μ_{n_{k}} rész-

sorozata, és olyan μ^{∗} valószínűségi mérték, melyre igaz, hogy tetszőleges A ⊂ X hengerhalmazra, lim_{k→∞} μ_{n_{k}}(A) = μ^{∗}(A). (Az A ⊂ X halmaz hengerhalmaz, ha létezik olyan m csak az A halmaztól függő szám, melyre ha x ∈ X és y ∈ X olyan sorozatok, melyeknek az m-nél nagyobb abszolut értékű koordinátái megegyeznek, akkor x és y egyszerre van vagy nincs benne az A halmazban.) Megjegyzés: Az átlós eljárás segítségével találhatunk olyan μ^{∗} additiv halmazfüggvényt, melyre lim_{k→∞} μ_{n_{k}}(A) = μ^{∗}(A). De a feladat állításának bizonyításához be kell látni azt is, hogy μ^{∗} σ-additiv. Ehhez kompaktsági meggondolások kellenek.

7.) Legyen x = (x_{n}, n = 0, ±1, ±2, …) egész számoknak pozitív felső sűrűségű sorozata, ω̄ ∈ X az x sorozat indikátorfüggvénye, azaz legyen ω̄ = (…, ε_{j}, ε_{j+1}, …), ε_{j} = 1, ha j ∈ x, és ε_{j} = 0, ha j ∉ x. Legyen a_{n}, b_{n} egész számok olyan sorozata,

melyre b_{n} −a_{n} → ∞, és lim_{k→∞} \frac{#\{j: a_{n} < j ≤ b_{n}, j ∈ x\}}{b_{n} − a_{n}} > 0 ha n → ∞. Definiáljuk

a μ_{n} = \frac{1}{b_{n} − a_{n}} ∑_{j=a_{n}+1}^{b_{n}} δ_{T^{−j} ω̄} mértékeket, ahol T a shift operátor, és δ_{u}, u ∈ X

az u pontba koncentrált mérték. Legyen μ^{∗} a μ_{n} sorozat egy μ_{n_{k}} részsorozatának a limesze az 6.) feladatban definiált értelemben. Lássuk be, hogy μ^{∗} mérték T invariáns, és a μ^{∗} mérték szerint a 0-ik koordináta pozitív valószínűséggel 1, azaz μ^{∗}(A) > 0 az A = {ω ∈ X: ω = (…, ε_{−1}, ε_{0}, ε_{1} …), ε_{0} = 1} halmazra. Lássuk be e tények segítségével, hogy a Fürstenberg tételből következik a Szemerédi tétel.

A Fürstenberg tételben a (∗) reláció helyett a következő élesebb állítást bizonyítják:

lim inf_{N→∞} \frac{1}{N} ∑_{n=1}^{N} μ ( ⋂_{j=0}^{k} T^{−jn}A) > 0 .  (∗∗)

Továbbá elég feltenni azt, hogy T mértéktartó transzformáció, de nem kell feltétlenül invertálhatónak lenni. Nem ismeretes, hogy (∗∗) relációban a lim inf helyettesíthető-e lim-mel. A bizonyítás transzfinit indukcióval történik egyre bonyolultabb szerkezetű rendszerekre.