Gyarmati Katalin

Hatvány-, hatványteli és hatványmentes számok összegsorozatokban és multiplikatív

struktúrákban. Témavezető: Dr. Sárközy András Tartalomjegyzék

1. Bevezetés 2 2. Előzmények 3 3. Diofantosz problémájának kiterjesztése 15 4. ab+1 alakú számoknak egy oszthatósági tulajdonsága 32 5. Hatvány, hatványteli számok összegsorozatokban 40 6. Hatványszámok multiplikatív struktúrákban 54 Hivatkozások 57

1. Bevezetés

Gyakran felmerülő kérdés a számelméletben természetes számokból álló sorozatok, halmazok sűrűségének becslése. A klasszikus számelmélet a speciális sorozatok (prímszámok, négyzetszámok stb) tulajdonságait vizsgálta, míg a XX. században megkezdődött az általános sorozatok, vagyis a sűrűségi feltételekkel karakterizált sorozatok vizsgálata. Hibrid problémán olyan problémát értünk, melyben mind speciális, mind általános sorozat szerepel.

Definiáljuk az A, B ⊆ ℕ halmazok összegét az A+B = {a+b : a ∈ A, b ∈ B} halmazzal, és legyen A × B + 1 = {ab + 1 : a ∈ A, b ∈ B}, A · A + 1 = {aa′ + 1 : a, a′ ∈ A, a ≠ a′}. Ekkor A × A + 1 ≠ A · A + 1, mivel az egyik esetben az összes a, a′ ∈ A-ra, a másik esetben csak a különböző a, a′ ∈ A (a ≠ a′) esetén képeztük az aa′ + 1 számokat ahhoz, hogy a halmaz elemeit megkapjuk. Dolgozatomban azokat a speciális eseteket tekintem át, amikor A + B, A × B + 1, A · A + 1 halmazok valamelyike része egy előre megadott P halmaznak. Ekkor P-től függően különböző becslések adódnak az A és a B halmaz méretére. Az egyik, első ilyen jellegű megállapítás Diofantosztól származik, aki megadott egy olyan 4 elemű A halmazt, amelyre A · A + 1 minden eleme egy racionális szám négyzete.

A következő jelöléseket fogjuk használni: Legyen a p elemű test F_{p}. Tetszőleges n természetes szám pozitív osztóinak számát d(n)-nel, különböző prímosztóinak számát ω(n)-nel, a Mangoldt szimbólumot Λ(n)-nel jelöljük. π(x) az x-et meg nem haladó prímszámok száma, míg P (x) az x legnagyobb prímosztója. Multiplikatív illetve additív karakterek esetén mindig χ_{0} a főkarakter. Definició szerint e(x) =^{def} e^{2πix}. Tetszőleges G egyszerű gráf szögpontjainak halmazát V (G), éleinek halmazát E(G) jelölje. Legyen végül K_{r,r} az a teljes páros gráf, melyben a két osztály elemszáma r.

2. Előzmények

Ebben a fejezetben egy rövid áttekintést, vagy inkább szemléltetést szeretnék adni a témakörben eddig elért eredményekről, tételekről.

A III. században Diofantosz talált egy racionális számokból álló 4 elemű halmazt: \{\frac{1}{16}, \frac{33}{16}, \frac{17}{4}, \frac{105}{4}\}, mely azzal a tulajdonsággal rendelkezik, hogy bármely két különböző elem szorzatához 1-et adva egy racionális szám négyzetét kapjuk. Később Fermat az egész számok körében vizsgálta a problémát, és az {1, 3, 8, 120} halmazt adta meg az előbb említett tulajdonsággal. (Könnyen látjuk, hogy ha a halmaz elemei egész számok, akkor bármely két különböző elem szorzatához 1-et adva, nemcsak egy racionális szám négyzetét, hanem mindíg négyzetszámot is kell kapnunk.) Felmerül a kérdés létezik-e ennél több elemű A halmaz, melyre A · A + 1 minden eleme egy racionális szám négyzete. Az egész számok körében még nem találtak ilyen, 5 elemű A halmazt. Viszont a racionális számok körében már három 5 elemű halmaz is van, sőt nemrég Phil Gibbs [13] egy 6 elemű halmazt adott meg: \{\frac{11}{192}, \frac{35}{192}, \frac{155}{27}, \frac{512}{27}, \frac{1235}{36}, \frac{180873}{16}\}. A továbbiakban csak egész számokból álló halmazokat tekintünk.

Euler bebizonyította, hogy minden két elemű A halmaz, a fenti tulajdonsággal, 4 tagúvá bővíthető lásd [5]. Arkin, Hoggatt, Straus [1] pedig azt, hogy ez minden 3 elemű halmazra is igaz.

Felső becslést Dujella [4] adott: Ha A ⊆ ℕ, és A · A + 1 minden eleme négyzetszám, akkor |A| ≤ 9. Később általánosította eredményét az A · A + n esetre, ekkor A elemszámát n függvényében becsülte [6].

Erdős [7] és Moser [32] kérdezték a probléma additív analogonját: Mit mondhatunk akkor, ha az A halmaz bármely két különböző elemének az összege négyzetszám? J. Lagrange [23] és Nicolas [25] talált egy ilyen 6 elemű A halmazt. A. Sárközy, J. Rivat, C. L. Stewart [26] igazolta azt, hogy ha A ⊆ {1, 2, …, N} és rendelkezik az előbb említett tulajdonsággal, akkor |A| ≪ log N.

A hibrid problémák témakörében, az összegsorozatokra vonatkozó eredmények közül az egyik első, nagyon szép és elemien is igazolható Erdős Pál és Turán Pál [12] tétele.

2.1. Tétel. Létezik c pozitív állandó, hogy ha A ⊆ ℕ véges sorozat, akkor

ω ( ∏_{a,a′∈A}(a + a′)) > c log |A| .

A most következő bizonyítás Erdős Pál és Surányi János [11]: Válogatott fejezetek a számelméletből című könyvében található.

Az alábbi kissé erősebb állítást fogjuk igazolni: Ha A minden eleme pozitív egész, és |A| = 2^{k} + 1, akkor

ω ( ∏_{a,a′∈A}(a + a′)) ≥ k + 1.

Abban, hogy a kéttagú összegek prímosztói közt sok különbözőt találjunk, az egyik fő akadály az, hogy egy összeg egy prímszám magas hatványával lehet osztható akkor is, ha az egyes összeadandókra ez nem áll. Ezért úgy próbálunk egy-egy p prímszámhoz minél több számot kiválasztani, hogy közülük kettőnek az összege p-nek ne legyen magasabb hatványával osztható, mint az összeadandók. Így várható, hogy a kettős összegeknek sok más prímosztója is lesz. Ennek a célkitűzésnek a megvalósítására egy lemmát látunk be.

Legyen adva páratlan számú különböző pozitív egész szám:

n_{1}, n_{2}, …, n_{2ℓ+1}

és egy p páratlan prímszám. Írjuk a számokat

n_{i} = p^{α_{i}}q_{i} (i = 1, 2, …, 2ℓ + 1)

alakban, ahol q_{i} már nem osztható p-vel. Ekkor kettőnek, mondjuk n_{i}-nek és n_{j}-nek az összege, ha α_{i} ≤ α_{j},

n_{i} + n_{j} = p^{α_{i}}(q_{i} + p^{α_{j}−α_{i}}q_{j}).

Ha α_{i} ≠ α_{j}, akkor a zárójelben levő összeg nem lehet p-vel osztható, ha azonban α_{i} = α_{j}, akkor gondoskodnunk kell arról, hogy q_{i} + q_{j} ne legyen p-vel osztható. Ez biztosan bekövetkezik, ha vagy mindkét összeadandó p/2nél kisebb maradékot ad p-vel osztva, vagy mindkettő p/2-nél nagyobbat. Ilyen választással a maradékok összege 0 és p közé, illetőleg p és 2p közé esik, a határokat már nem engedve meg, s így az összeg nem lehet p-vel osztható. A

q_{1}, q_{2}, …, q_{2ℓ+1}

számok maradékai közt azonban, ha p-vel osztunk (legkisebb nemnegatív maradékot véve) vagy p/2 alá, vagy p/2 fölé legalább ℓ + 1 esik. Ezzel a következőt láttuk be:

2.2. Lemma. Ha p páratlan prímszám, akkor 2ℓ+1 különböző pozitív egész szám közül kiválasztható ℓ + 1 úgy, hogy kettőnek az összege ne legyen p-nek magasabb hatványával osztható, mint bármelyik összeadandó.

Ez a lemma a kulcsa a tétel bizonyításának. Legyen adva 2^{k}+1 különböző pozitív egész szám (ahol k legalább 1). Az ezekből képezett kéttagú összegek prímszám osztói közt szerepel a 2, mivel legalább három számunk van. Az összegek páratlan prímosztói legyenek p_{1}, p_{2}, …, p_{i}. Megmutatjuk indirekt okoskodással, hogy i ≥ k.

Tegyük fel, hogy i < k volna. Alkalmazzuk ismételten a segédtételt. Eszerint a 2^{k} + 1 szám közül kiválasztható 2^{k−1} + 1 úgy, hogy ha valamelyik kettőnek az összege osztható p_{1}^{α_{1}}-nal, akkor mindegyik összeadandó is osztható vele. Ezek közül kiválasztható 2^{k−2} + 1 szám úgy, hogy ezen kivül teljesüljön az is, hogy ha valamelyik kettőnek az összege osztható p_{2}^{β}-nal, akkor az összeadandók külön-külön is oszthatók vele.

Az eljárást ismételgetve, végül kapunk 2^{k−i} + 1, tehát az indirekt feltevés szerint legalább három számot, amelyekre már p_{1}, p_{2}, …, p_{i} mindegyikét illetően teljesül a p_{1}-re és p_{2}-re kimondott tulajdonság. Legyen a megmaradt számok közül három a_{1}, a_{2}, a_{3}. Mivel feltettük, hogy a kéttagú összegek összes páratlan prímszám osztóit felsoroltuk, így a kettős összegek ilyen alakúak:

a_{1} + a_{2} = 2^{u_{0}}p_{1}^{u_{1}}p_{2}^{u_{2}} … p_{i}^{u_{i}}, a_{1} + a_{3} = 2^{v_{0}}p_{1}^{v_{1}}p_{2}^{v_{2}} … p_{i}^{v_{i}},

a_{2} + a_{3} = 2^{w_{0}}p_{1}^{w_{1}}p_{2}^{w_{2}} … p_{i}^{w_{i}}.

Itt a_{1} és a_{2} is osztható kell, hogy legyen p_{1}^{u_{1}}p_{2}^{u_{2}} … p_{i}^{u_{i}}-nel, tehát egyik sem lehet még 2^{u_{0}}-nal is osztható. Az összegük azonban csak úgy lehet 2-nek magasabb hatványával osztható, mint az összeadandók, ha a 2 mindkét szám kanonikus felbontásában ugyanazon a kitevőn szerepel. Ugyanez igaz a_{1}-re és a_{3}-ra is, tehát a három szám ilyen alakú:

a_{i} = 2^{t}b_{i}, i = 1, 2, 3,

ahol b_{1}, b_{2} és b_{3} páratlan, továbbá kettőnek az összege

b_{1} + b_{2} = 2^{r_{1}}p_{1}^{u_{1}}p_{2}^{u_{2}} … p_{i}^{u_{i}}, b_{1} + b_{3} = 2^{r_{2}}p_{1}^{v_{1}}p_{2}^{v_{2}} … p_{i}^{v_{i}},
b_{2} + b_{3} = 2^{r_{3}}p_{1}^{w_{1}}p_{2}^{w_{2}} … p_{i}^{w_{i}}.

alakú (r_{1} = u_{0} − t, r_{2} = v_{0} − t, r_{3} = w_{0} − t). A b-kre fennáll ezenkivül, hogy pl. b_{1} és b_{2} osztható p_{1}^{u_{1}}p_{2}^{u_{2}} … p_{i}^{u_{i}}-nel, tehát ennél egyik sem kisebb, sőt legalább az egyik ennél nagyobb, mert a számok különbözőek.

Eszerint kell, hogy r_{1} legalább 2 legyen. Ugyanígy r_{2}, r_{3} is lagalább 2. Ennélfogva

b_{1} + b_{2} = 4x, b_{1} + b_{3} = 4y, b_{2} + b_{3} = 4z,

valamilyen x, y, z egész számokkal. Ezeket összeadva és 2-vel osztva

b_{1} + b_{2} + b_{3} = 2x + 2y + 2z.

Ez azonban nem lehetséges, mert a baloldalon három páratlan szám összege áll, míg a jobboldal páros. Nem lehet tehát i < k. Ezzel a 2.1. tételt bebizonyítottuk.

Sokáig sejtés volt, hogy a tétel általánosítható két különböző sorozat esetére is. Győry, Stewart és Tijdeman [20] 1986-ban igazolta ezt a sejtést. A következőt látták be:

2.3. Tétel. Ha |A| ≥ |B| ≥ 2, akkor

ω (∏_{a∈A} ∏_{b∈B}(a + b)) > c log |A| .

A tétel multiplikatív analogonját Győry, Sárközy, Stewart [19] bizonyította tíz évvel később.

2.4. Tétel. Ha |A| ≥ |B| ≥ 2, akkor

ω (∏_{a∈A} ∏_{b∈B}(ab + 1)) > c log |A| .

Ezután a 2.3 tétel bizonyítását vázoljuk, a főlemma bizonyítása nélkül, mivel az, Evertsenek egy S-egység egyenletek megoldásszámára vonatkozó mély eredményre épül. (Megjegyzem, hogy e tételre máig nem ismeretes elemi bizonyítás.)

2.5. Lemma. Legyen λ, μ és ν pozitív egész számok, p_{1}, p_{2}, …, p_{w} különböző prímszámok. Ekkor a

λx + μy = νz

egyenletnek legfeljebb 3 × 7^{2w+3} olyan megoldása van x, y, z-ben, ahol x, y, z páronként relatív prímek, és mindegyik prímtényezős felbontásában csak a p_{1}, p_{2}, …, p_{w} számok közül szerepelnek a prímszámok.

Legyen b_{1}, b_{2} ∈ B. Jelölje p_{1}, p_{2}, …, p_{w} azokat a prímeket, melyek osztják a

∏_{a∈A} ∏_{b∈B}(a + b)

számot. Az

x − y = (b_{1} − b_{2})z

egyenletnek x = a+b_{1}, y = a+b_{2}, z = 1 megoldása minden a ∈ A-ra. Mivel a + b_{1} és a + b_{2} minden prímosztója p_{1}, p_{2}, …, p_{w} prímszámok között van, ezért a 2.5. lemma szerint az ilyen megoldások száma legfeljebb 3 × 7^{2w+3}. Tehát

|A| ≤ 3 × 7^{2w+3}.

Ebből w ≫ log |A|, és ez igazolja a 2.3. tételt.

Erdős, Stewart, Tijdeman [10]-ben foglalkozott a problémával, hogy mennyire pontos ez az eredmény.

2.6. Tétel. Legyen 0 < ε < 1 valós szám, f : ℝ_{>1} → ℝ függvény, melyre f(x) → ∞ ha x → ∞. Legyen továbbá k és 2 ≤ ℓ ≤ \frac{log k}{f(k)} pozitív egészek, ahol még k > c(ε, f) is teljesül (c(ε, f) csak ε-tól, f-től függő konstans). Ekkor léteznek a_{1}, a_{2}, …, a_{k} különböző pozitív egészek és b_{1}, b_{2}, …, b_{l} különböző természetes számok, hogy

P (∏_{i=1}^{k} ∏_{j=1}^{l}(a_{i} + b_{j})) < ((1 + ε)\frac{log k}{ℓ} log (\frac{log k}{ℓ} ))^{ℓ} .

Itt ennél a tételnél egy kicsit kevesebbet igazolunk annyiban, hogy egy konkrét f függvényre mondjuk ki azt, de a bizonyítás alapötlete és menete megegyezik Erdős, Stewart, Tijdeman eredeti bizonyításával.

2.7. Tétel. Létezik c > 0 konstans, hogy minden k ≥ ℓ pozitív egészekre létezik A, B ⊆ ℕ, melyre |A| ≥ k, |B| = ℓ és

P (∏_{a∈A} ∏_{b∈B}(a + b)) ≤ (c log |A| log log |A|)^{ℓ}

A tételből azonnal következik, hogy a fenti A és B halmazokra

ω (∏_{a∈A} ∏_{b∈B}(a + b)) ≤ (c^{∗} log |A|)^{ℓ} (log log |A|)^{ℓ−1}

is fenn áll valamilyen c^{∗} > 0 konstansra. A 2.7. tétel a 2.10. lemmából következik, amit a 2.8. és 2.9. lemmából vezetünk le.

2.8. Lemma. Legyen N pozitív egész, W ⊆ {1, 2, … N} nem üres halmaz, ℓ egész szám, 1 ≤ ℓ ≤ |W|. Ekkor létezik A, B halmazpár, hogy 0 ∈ B, |B| = ℓ, és

A + B ⊆ W, |A| ≥ \begin{matrix}( & {|W| \atop ℓ} & ) \\ ( & {N−1 \atop ℓ−1} & ) \end{matrix}

W-nek minden ℓ elemű részhalmaza felírható {w_{1}, w_{2}, …, w_{ℓ}} alakban, ahol w_{1} < w_{2} < ⋯ < w_{ℓ}. Ekkor minden ilyen {w_{1}, w_{2}, …, w_{ℓ}} halmazhoz rendeljük hozzá a {w_{2}−w_{1}, …, w_{ℓ}−w_{1}} ⊆ {1, 2, …, N}, ℓ−1 elemű halmazt. A skatulyaelv szerint létezik az {1, 2, …, N} halmaznak olyan ℓ − 1 elemű {b_{1}, …, b_{ℓ−1}} részhalmaza, melyet W-nek k darab ℓ elemű részhalmazához rendeltük hozzá, ahol

k ≥ \begin{matrix}( & {|W| \atop ℓ} & ) \\ ( & {N−1 \atop ℓ−1} & ) \end{matrix}.

Jelölje a_{1}, a_{2}, …, a_{k} e k darab részhalmaz legkisebb elemeit. Könnyen ellenőrizhető, hogy A = {a_{1}, …, a_{k}}, B = {0, b_{1}, …, b_{ℓ−1}} eleget tesz a lemma feltételeinek.

Jelölje ψ(x, y) azon pozitív egészek számát, amelyek x-et nem haladják meg, és nincsen y-nál nagyobb prímosztójuk. Canfield, Erdős, Pomarence, [2, 3.1.tétel] igazolta a következő lemmát.

2.9. Lemma. Létezik c konstans, hogy ha x pozitív egész, u ≥ 3 valós szám, akkor

ψ(x, x^{1/u}) ≥ x exp (−u (log u + log log u − 1 + c (\frac{log log u}{log u}))) .

Ez utóbbi két lemma segítségével igazoljuk az alábbit.

2.10. Lemma. Legyen ℓ, N pozitív egész, és

m = ⌈exp (\frac{log N}{2 log log N} )⌉ ,
t = [(log N)^{ℓ}] .

Ekkor van olyan c(ℓ), csak ℓ-től függő konstans, hogy ha N > c(ℓ) teljesül, akkor létezik A, B ⊆ ℕ halmazpár, melyre |A| = m, |B| = ℓ valamint

P (∏_{a∈A} ∏_{b∈B}(a + b)) ≤ t.

Legyen W = {n ≤ N : P (n) ≤ t}. Ekkor |W| = ψ(N, t). Ha N elég nagy

ψ(N, t) ≥ t ≥ ℓ^{3} ≥ ℓ.

Tehát alkalmazhatjuk a 2.8. lemmát. Eszerint létezik A, B halmazpár, melyre 0 ∈ B, |B| = ℓ, és P (a + b) ≤ t minden a ∈ A, b ∈ B esetén. Így a lemma igazságához elegendő belátni, hogy |A| ≥ m. A 2.8. lemma szerint még

|A| ≥ \begin{matrix}( & {ψ(N,t) \atop ℓ} & ) \\ ( & {N−1 \atop ℓ−1} & ) \end{matrix} ≥ \frac{(ψ(N, t) − ℓ)^{ℓ}}{ℓN^{ℓ−1}} ≥ (1 + o(1)) \frac{(ψ(N, t))^{ℓ}}{ℓN^{ℓ−1}}  (2.1)

is teljesül az A halmazra. Ezután ψ(N, t)-re adunk alsó becslést. Ehhez Legyen u = \frac{log N}{log t} = \frac{log N}{ℓ log log N+o(1)}, így u definiciója miatt t = N^{1/u}. A 2.9. lemma alapján:

ψ(N, t) = ψ(N, N^{1/u}) ≥ N exp (−u (log u + log log u − 1 + o(1))) .

Mivel

log u = log log N − log ℓ − log log log N + o(1),
log log u = log log log N + o(1),
log u + log log u − 1 ≤ log log N − 1 + o(1),

ezért

ψ(N, t) ≥ N exp (−\frac{log N}{ℓ log log N + o(1)} (log log N − 1 + o(1)))
= N exp (−\frac{log N}{ℓ} + (1 + o(1))\frac{ℓ log N}{log log N} ) .

Ezt (2.1)-be írva kapjuk:

|A| ≥ \frac{(1 + o(1))}{ℓ} exp ((1 + o(1))\frac{log N}{log log N} ) ≥ exp (\frac{log N}{2 log log N} ) ,

ha N elég nagy. Ezzel a lemmát igazoltuk.

A 2.10. lemmából már könnyen bizonyítható a 2.7. tétel. Legyen N = [exp (4 log k log log k)]. Ha k, ℓ függvényében, elég nagy, akkor alkalmazható a 2.10. lemma. A lemmabeli t-re teljesül, hogy

t = [(log N)^{ℓ}] ≤ (4 log k log log k)^{ℓ} .

Tehát már csak azt kell belátnunk, hogy

k ≤ m = ⌈exp (\frac{log N}{2 log log N} )⌉ .

Valóban

log N = 4 log k log log k + o(1),
log log N = (1 + o(1)) log log k,
⌈exp (\frac{log N}{2 log log N} )⌉ > k.

A multiplikatív esetben Győry, Sárközy, Stewart [20] a következőt igazolta:

2.11. Tétel. Minden ε > 0 valós számra, k ≥ ℓ pozitív egészekre létezik A, B ⊆ ℕ, melyre |A| ≥ k, |B| = ℓ és

P (∏_{a∈A} ∏_{b∈B}(ab + 1)) ≤ (log |A|)^{ℓ+1+ε} .

Érdemes még megemlíteni a következő, karakterekre vonatkozó tételt, annál is inkább, mivel a dolgozatban később felhasználjuk. A tétel és bizonyítása Erdőstől és Shapirotól [9] származik.

2.12. Tétel. Legyen A, B ⊆ {1, 2, …, p} és χ ≠ χ_{0} multiplikatív karakter mod p. Ekkor:

|∑_{a∈A} ∑_{b∈B} χ(a + b)| ≤ \sqrt{p |A| |B|}.

A 2.12. tétel bizonyításának céljából Gauss-összegeket használunk:

τ (χ) =^{def} ∑_{i=1}^{n} χ(m)e (\frac{m}{q}) ,

ahol χ primitív karakter mod p. Ekkor |τ(χ)| = \sqrt{p} (lásd például [3, 66.o.]). A Gauss-összegekre vonatkozik a következő két lemma.

2.13. Lemma. Ha χ primitív karakter mod p, akkor minden n-re:

χ(n) = \frac{1}{τ (\overline{χ})} ∑_{h=1}^{p} \overline{χ}(h)e (\frac{hn}{p}) .

A bizonyítás megtalálható [3, 68.o.]-ban. Egyszerű és jól ismert az alábbi Parseval típusú azomosság.

2.14. Lemma. T (α) = ∑_{n=1}^{p} c_{n}e(nα) esetén

∑_{h=1}^{p} |T (\frac{h}{p})|^{2} = p ∑_{n=1}^{p} |c_{n}|^{2} .

A bizonyítást az olvasóra hagyjuk.

A 2.13. lemma, a háromszögegyenlőtlenség és |τ(\overline{χ})| = \sqrt{p} miatt:

S =^{def} |∑_{a∈A} ∑_{b∈B} χ(a + b)| = |\frac{1}{τ (\overline{χ})} ∑_{a∈A} ∑_{b∈B} ∑_{h=1}^{p} \overline{χ}(h)e (\frac{(a + b)h}{p})|

≤ \frac{1}{\sqrt{p}} ∑_{h=1}^{p} |∑_{a∈A} e (\frac{ah}{p})| |∑_{b∈B} e (\frac{bh}{p})| .

A Cauchy-Schwarz egyenlőtlenség szerint:

S ≤ \frac{1}{\sqrt{p}}\sqrt{∑_{h=1}^{p} |∑_{a∈A} e (\frac{ah}{p})|^{2} ∑_{h=1}^{p} |∑_{b∈B} e (\frac{bh}{p})|^{2}}.  (2.2)

Alkalmazzuk a 2.14 lemmát a következő helyetesítéssel:

c_{n} = \{ \begin{matrix}0 & ha n ∉ A, \\ 1 & ha n ∈ A. \end{matrix}

Ebből azt kapjuk, hogy:

∑_{h=1}^{p} |∑_{a∈A} e (\frac{ah}{p})|^{2} = p |A| .

Hasonlóan

∑_{h=1}^{p} |∑_{a∈A} e (\frac{bh}{p})|^{2} = p |B| .

Az utóbbi két egyenletet (2.2)-be írva azonnal adódik a tétel állítása.

Ezeken kívül számos más tulajdonságát is vizsgálták hibrid sorozatoknak. Erdős Pál és Sárközy András [8] adott becslést az A halmaz méretére, ha A + A minden eleme négyzetmentes szám. A problémát Sárközy Gábor [29] terjesztette ki két különböző halmaz és k-adik hatványok esetére. Bebizonyította, hogy ha k, N > N_{0}(k) pozitív egészek, A, B ⊆ {1, 2, …, N}, és |A| |B| > c(k)N^{2−1/k}, akkor létezik p prím, a ∈ A, b ∈ B, hogy p^{k}|a + b. Alsó becslésként pedig megadott egy olyan A, B ⊆ {1, 2, …, N} halmazpárt, melyre nem létezik p prím, hogy p^{k}|a + b teljesül valamilyen a ∈ A, b ∈ B-re, és

|A| |B| > \frac{(k − 1)N(log N)^{k−1}}{65e^{4}(3k)^{k−1}} .

Dolgozatom további részeiben saját, illetve társszerzőkkel közösen írt cikkeink tartalmát ismertetem a [15], [16], [17] és [18] alapján, azonban az ottani bizonyításokat kissé átdolgozva, helyenként egyszerűsítve.

3. Diofantosz problémájának kiterjesztése

Ebben a fejezetben Diofantosz problémájának két különböző sorozatra való általánosítását vizsgáljuk. A most következő tétel érdekessége, hogy k ≥ 3 esetén sokkal jobb becslést ad k-adik hatványokra mint négyzetszámokra.

3.1. Tétel. Ha A, B ⊆ {1, 2, 3, …, N} és A × B + 1 minden eleme k-adik hatvány, akkor: a)

min (|A| , |B|) ≤ \frac{1}{log 2} log N ha k = 2,

b)

min (|A| , |B|) ≤ \frac{1}{log(k − 1)} log log N + 1 ha k ≥ 3.

Legyen A és B a tételnek megfelelő halmazok. A bizonyítás a következő lemmán alapul:

3.2. Lemma. Legyen k ≥ 2 és x < y, c < d pozitív egész számok. Ha xc + 1, xd + 1, yc + 1, yd + 1 számok mindegyike k-adik hatvány, akkor

yd > k^{k}(xc)^{k−1}.

Valóban, ha x < y és c < d, akkor

(y − x)(d − c) > 0.

Ez utóbbi ekvivalens az

(xc + 1)(yd + 1) > (xd + 1)(yc + 1)

egyenlőtlenséggel. Mivel (xc+1)(yd+1) k-adik hatvány és \sqrt[k]{(xd + 1)(yc + 1)} egész szám, ezért:

xycd + xc + yd + 1 ≥ (\sqrt[k]{(xd + 1)(yc + 1)} + 1)^{k} .

A binomiális tétel szerint becsülve a jobboldalt, kapjuk:

xycd + xc + yd + 1 ≥ xycd + xd + yc + 1 + k(xycd)^{\frac{k−1}{k}} .

Rendezve:

yd ≥ xd + yc − xc + k(xycd)^{\frac{k−1}{k}} .

d > c miatt xd + yc − xc > 0, tehát

yd > k^{k}(xc)^{k−1}.

Ezzel a 3.2. lemmát igazoltuk. Most már rátérhetünk a 3.1. tétel bizonyítására.

Legyen A = {a_{1}, a_{2}, …, a_{m}}, B = {b_{1}, b_{2}, …, b_{n}} ahol a_{1} < a_{2} < ⋯ < a_{m} és b_{1} < b_{2} < ⋯ < b_{n}. Az általánosság megsértése nélkül feltehetjük, hogy m ≤ n.

k = 2 esetén a_{1}b_{1} ≥ 4 vagy a_{2}b_{2} ≥ 16, mivel a_{i}b_{j} + 1 négyzetszám minden 1 ≤ i ≤ j ≤ 2 esetén. Így a 2.1. tétel alapján kapjuk:

N^{2} ≥ a_{m}b_{m} > 4a_{m−1}b_{m−1} > ⋯ > 4^{m}.

Tehát: m ≤ \frac{1}{log 2} log N.

Hasonló állítások állnak fenn k > 2 esetén is. Ekkor: a_{t+1}b_{t+1} > (a_{t}b_{t})^{k−1}, ha 1 ≤ t ≤ m. Mivel most a_{1}b_{1} > 2^{k−1}, ezért:

N^{2} ≥ a_{m}b_{m} > k^{k−1}(a_{m−1}b_{m−1})^{k−1} > ⋯ > k^{(k−1)^{m−1}}2^{(k−1)^{m}} = (2 \sqrt[k−1]{k})^{(k−1)^{m}}.

Tehát:

m ≤ \frac{1}{log(k − 1)} log log N + 1.

Ezzel a bizonyítást befejeztük.

Az előző tétel a két halmaz közül csak a kisebbik méretére adott felső becslést. Valószínűleg k = 2 esetén bármelyik halmaz elemszáma kisebb mint log N-nek egy konstansszorosa, ezt azonban csak egy további feltétel mellett tudtam igazolni.

3.3. Tétel. Legyen A, B ⊆ {1, 2, 3, …, N}, és A × B + 1 minden eleme négyzetszám. Tegyük fel, hogy létezik a_{1}, a_{2} ∈ A, amelyre a_{1} ≤ a_{2} ≤ 2a_{1}. Ekkor:

|B| ≤ \frac{1}{log 2} log N.

Legyen B = {b_{1}, b_{2}, …, b_{n}} továbbra is. A 2.2. lemma szerint a_{2}b_{t+1} > 4a_{1}b_{t} ha 1 ≤ t ≤ n − 1. A 2a_{1} > a_{2} feltétel miatt ebből azt kapjuk, hogy b_{t+1} > 2b_{t}. Innen már azonnal adódik az állítás.

Pell-egyenletek segítségével könnyen látható, hogy a 3.3. tételben a B halmaz méretére adott felső becslés konstans szorzótól eltekintve éles:

3.4. Tétel. Az A = {1, 2} halmazhoz létezik B ⊆ {1, 2, 3, …, N}, melyre

|B| ≥ [\frac{1}{log 36} log N]

és A × B + 1 minden eleme négyzetszám.

Defináljuk az {x_{n}} sorozatot a következőképpen: x_{0} = 1, x_{1} = 5 és n ≥ 2 esetén x_{n} = 6x_{n−1} − x_{n−2}. Ekkor x_{n} ≤ 6x_{n−1}. Ezt többszörösen alkalmazva adódik, hogy x_{n} < 6^{n}. Legyen B = \{x_{i}^{2} − 1 : x_{i} < \sqrt{N}, i ≥ 1\}. Ezek után már csak két dolgot kell igazolnunk. Egyrészt, hogy |B| ≥ [\frac{1}{log 36} log N], másrészt a ∈ A, b ∈ B esetén ab + 1 négyzetszám.

Ha 6^{i} ≤ \sqrt{N} és i ≥ 1, akkor x_{i}^{2} −1 ∈ B tehát |B| ≥ [\frac{1}{log 36} log N]. Legyen

y_{n} = \frac{1}{2}x_{n+1} − \frac{3}{2}x_{n}.

minden n-re. Ebből x_{n+1} = 2y_{n} + 3x_{n}, valamint:

y_{n+1} = \frac{1}{2} (6x_{n+1} − x_{n}) − \frac{3}{2}x_{n+1} = 4x_{n} + 3 (\frac{1}{2}x_{n+1} − \frac{3}{2}x_{n}) = 4x_{n} + 3y_{n}.

Összefoglalva:

y_{n+1} = 3y_{n} + 4x_{n},
x_{n+1} = 2y_{n} + 3x_{n}.

Mivel a 3, 2 számpár az y^{2} − 2x^{2} = 1 Pell-egyenlet legkisebb megoldása, és x_{0} = y_{0} = 1 esetén y_{0}^{2} − 2x_{0}^{2} = −1, ezért az y_{n}, x_{n} számpár az y^{2} − 2x^{2} = −1 Pell-egyenlet megoldása. Vagyis 2 (x_{i}^{2} − 1) + 1 = y_{i}^{2}. Azaz minden a ∈ A, b ∈ B esetén ab + 1 teljes négyzet. Ezzel a tételt igazoltuk.

Érdemes megvizsgálni a probléma moduláris változatát, mivel itt Diofantosz problémájával ellentétben, akármilyen nagy halmaz megadható a megfelelő tulajdonsággal.

3.5. Tétel. Létezik olyan p_{0} konstans, hogy ha p 4k + 1 alakú prím, és p > p_{0}, akkor létezik A ⊆ ℤ_{p} halmaz, amelyre

|A| ≥ \frac{1}{6 log 3} log p,

valamint A · A + 1 minden eleme kvadratikus maradék vagy 0 mod p.

A bizonyítás érdekessége, hogy gráfelméleten alapul. Nevezetesen, ismeretes a Ramsey tételnek a következő általánosítása:

3.6. Lemma. Minden s_{1}, s_{2}, s_{3} nem negatív számokra létezik egy r egész szám az alábbi tuljdonsággal:

Ha G olyan teljes gráf, amelyre V (G) ≥ r, és C tetszőleges három színezése G gráfnak a c_{1}, c_{2}, c_{3} színekkel, akkor létezik 1 ≤ i ≤ 3, hogy G-nek van egyszínű G′ részgráfja, ahol |V (G′)| ≥ s_{i}. Jelöljük az ilyen r számok közül a legkisebbet R(a, b, c)-vel. Ekkor:

R (s_{1}, s_{2}, s_{3}) ≤ \frac{(s_{1} + s_{2} + s_{3})!}{s_{1}!s_{2}!s_{3}!}.

Ha az s_{1}, s_{2}, s_{3} számok valamelyike 0, akkor az állítás triviális, mert R (s_{1}, s_{2}, s_{3}) = 0. s_{1}, s_{2}, s_{3} > 0 esetén igaz és jól ismert az alábbi egyenlőtlenség (lásd [14]):

R (s_{1}, s_{2}, s_{3}) ≤ R (s_{1} − 1, s_{2}, s_{3}) + R (s_{1}, s_{2} − 1, s_{3}) + R (s_{1}, s_{2}, s_{3} − 1)

Ebből s_{1}+s_{2}+s_{3}-ra vonatkozó indukcióval kapjuk: R (s_{1}, s_{2}, s_{3}) ≤ \frac{(s_{1}+s_{2}+s_{3})!}{s_{1}!s_{2}!s_{3}!}.

Nézzük most azt a gráfot, amelynek pontjai a mod p maradékosztályok. Mivel p 4k + 1 alakú prím, ezért létezik i maradékosztály, hogy i^{2} ≡ −1 mod p. Az élek színét a Legendre szimbólum segítségével határozzuk meg (\frac{0}{p}) értékét vegyük 0-nak.

Az a és b maradékosztályokat összekötő élt színezzük c_{1} színnel, ha (\frac{ab+1}{p}) = 1 vagy 0, c_{2} színnel, ha (\frac{−ab+1}{p}) = 1 vagy 0, és (\frac{ab+1}{p}) = −1. c_{3} színnel, ha (\frac{−a^{2}b^{2}+1}{p}) = 1 vagy 0, és (\frac{ab+1}{p}) = (\frac{−ab+1}{p}) = −1. Ekkor minden élt megszíneztünk, ellenkező esetben ugyanis:

(\frac{ab + 1}{p}) = (\frac{−ab + 1}{p}) = (\frac{−a^{2}b^{2} + 1}{p}) = −1.

Tehát:

−1 = (\frac{(ab + 1) (−ab + 1) (−a^{2}b^{2} + 1)}{p}) = (\frac{(a^{2}b^{2} − 1)^{2}}{p} ) .

De ez ellentmond a nyilvánvaló ténynek, hogy (^{\frac{(a^{2}b^{2}−1)^{2}}{p}} ) = 1 vagy 0. Legyen c = [\frac{1}{3 log 3} log p] + 1. A 3.6. lemma szerint:

R(c, c, c) ≤ \frac{(3c)!}{c!c!c!}.

Az egyenlőtlenség jobboldalát Stirling formulával becsüljük. Elég nagy c esetén:

\frac{(3c)!}{c!c!c!} ≤ (1 + o(1)) \begin{matrix}(\frac{3c}{e}) & 3c & \sqrt{2π3c} \\ ((\frac{c}{e})^{c}\sqrt{2πc}) & 3 \end{matrix} ≤ 3^{3c−3} ≤ p.

Azaz, ha p elég nagy, akkor R(c, c, c) ≤ p. Tehát van a gráfban egy c darab szögpontból álló egyszínű G′ részgráf.

Legyen

A = \{ \begin{matrix}V (G′) & ha a G′ éleit c_{1} színnel színeztük, \\ \{ig : g ∈ V (G′)\} & ha a G′ éleit c_{2} színnel színeztük, \\ \{ig^{2} : g ∈ V (G′)\} & ha a G′ éleit c_{3} színnel színeztük. \end{matrix}

Ekkor |A| ≥ \frac{1}{2} |V (G′)|. A színezés definiciója miatt A halmaz bármely két elemének szorzatához 1-et adva mindig kvadratikus maradékot vagy 0-t kapunk mod p.

Hasonló konstrukciót adott Erdős és Sárközy [28] a probléma additív analogonja esetén. Ahhoz, hogy felső becslést tudjunk adni a moduláris esetben, szükségünk van Vinogradov [34] következő tételére.

3.7. Tétel. Legyen A, B ⊆ ℤ_{p} és S = ∑_{a∈A} ∑_{b∈B} (\frac{ab+1}{p}), akkor |S| ≤

\sqrt{2p |A| |B|}.

Ebből már könnyen levezethető az alábbi tétel.

3.8. Tétel. Legyen p prím, A, B ⊆ {1, 2, …, p − 1}, és A × B + 1 minden eleme kvadratikus maradék vagy 0 mod p. Ekkor |A| |B| ≤ (\sqrt{2p} + 1)^{2}.

A bizonyítás során feltehetjük, hogy |A| ≤ |B|. A tétel feltétele szerint minden a ∈ A, b ∈ B esetén (\frac{ab+1}{p}) = 1 vagy 0. A 3.7. tételből következik, hogy

|A| |B| − \sqrt{|A| |B|} ≤ |A| (|B| − 1) ≤ ∑_{a∈A} ∑_{b∈B} (\frac{ab + 1}{p}) ≤ \sqrt{2p |A| |B|}.

De ez ekvivalens az állítással.

Ahhoz, hogy Diofantosz problémáját, illetve annak, additív változatát a moduláris esetben 2-nél magasabb hatványokra is vizsgálni tudjuk, multiplikatív karakterekre van szükségünk. A következő tétel a) része Vinogradov eredményét általánosítja, míg b) részét Erdős és Shapiro [9] bizonyította, és a 2. fejezetben tárgyaltuk.

3.9. Tétel. Legyen A, B ⊆ {1, 2, …, p} és χ ≠ χ_{0} multiplikatív karakter mod p. Ekkor: a)

|∑_{a∈A} ∑_{b∈B} χ(ab + 1)| ≤ \sqrt{p |A| |B|},

b)

|∑_{a∈A} ∑_{b∈B} χ(a + b)| ≤ \sqrt{p |A| |B|}.

A 3.9.a tétel bizonyításában Gauss-összegeket használunk:

τ (χ) =^{def} ∑_{i=1}^{n} χ(m)e (\frac{m}{q}) ,

ahol χ primitív karakter mod p. Ekkor |τ(χ)| = \sqrt{p} (lásd például [3, 66.o.]). A 2.13. lemma szerint:

S =^{def} |∑_{a∈A} ∑_{b∈B} χ(ab + 1)| = |\frac{1}{τ (\overline{χ})} ∑_{a∈A} ∑_{b∈B} ∑_{h=1}^{p} \overline{χ}(h)e (\frac{(ab + 1)h}{p})| .

h = ℓb^{−1} helyettesítve, és |τ(\overline{χ})| = \sqrt{p}-t használva kapjuk:

S = \frac{1}{\sqrt{p}} |∑_{a∈A} ∑_{b∈B} ∑_{ℓ=1}^{p} \overline{χ}(ℓb^{−1})e (\frac{(aℓ + ℓb^{−1)}}{p} )| .

Legyen B′ = {b^{−1} : b ∈ B}. Nyilván |B′| = |B|. Továbbá:

S = \frac{1}{\sqrt{p}} |∑_{ℓ=1}^{p} \overline{χ}(ℓ) ∑_{a∈A} e (\frac{aℓ}{p}) ∑_{b∈B′} \overline{χ}(b)e (\frac{bℓ}{p})| ≤

≤ \frac{1}{\sqrt{p}} ∑_{ℓ=1}^{p} |∑_{a∈A} e (\frac{aℓ}{p})| |∑_{b∈B′} \overline{χ}(b)e (\frac{bℓ}{p})| .

A Cauchy-Schwarz egyenlőtlenség szerint:

S ≤ \frac{1}{\sqrt{p}}\sqrt{∑_{ℓ=1}^{p} |∑_{a∈A} e (\frac{aℓ}{p})|^{2} ∑_{ℓ=1}^{p} |∑_{b∈B′} \overline{χ}(b)e (\frac{bℓ}{p})|^{2}}.  (3.1)

A 2. fejezetben már beláttuk, hogy

∑_{ℓ=1}^{p} |∑_{a∈A} e (\frac{aℓ}{p})|^{2} = p |A| .  (3.2)

Alkalmazzuk a 2.13 lemmát a következő helyetesítéssel:

c_{n} = \{ \begin{matrix}0 & ha n ∉ B, \\ \overline{χ}(n) & ha n ∈ B. \end{matrix}

Ebből azt kapjuk, hogy:

∑_{ℓ=1}^{p} |∑_{b∈B′} \overline{χ}(b)e (\frac{bℓ}{p})|^{2} = p |B| .  (3.3)

(3.2)-t és (3.3)-t beírva a (3.1) egyenlőtlenségbe, kapjuk:

S ≤ \sqrt{p}\sqrt{|A| |B|}.

Ezzel a 3.9. tételt igazoltuk.

A fenti, karakterekre vonatkozó tétel lehetővé teszi, hogy a moduláris esetben a triviálisnál jobb felső becslést adjunk a halmazok méretére.

3.10. Tétel. Legyen k pozitív egész. Ha p prímszám, (p − 1, k) ≠ 1, A, B ⊆{1, 2, …, p − 1} és

a) minden a ∈ A, b ∈ B estén létezik egy x egész, hogy ab + 1 ≡ x^{k} (mod p), vagy

b) minden a ∈ A, b ∈ B esetén létezik egy x egész, hogy a + b ≡ x^{k} (mod p), akkor |A| |B| ≤ (\sqrt{p} + 2)^{2}.

A (p − 1, k) ≠ 1 feltétel mindenképpen szükséges a tételben, mivel (p − 1, k) = 1 esetén az x^{k} ≡ a (mod p) egyenletnek rögzített a-ra pontosan 1 megoldása van x-ben. Így ekkor tetszőleges A, B ⊆ {1, 2, …, p − 1} halmazpár eleget tenne a tétel feltételeinek.

Legyen f(a, b) ab + 1 az a) esetben és a + b a b) esetben. Elegendő azt belátni, hogy a tétel igaz akkor, ha k prím. Megadható ugyanis k helyett egy olyan k_{0}, ami már prím és eleget tesz a tétel feltételeinek. Valóban, az általános esetben, ha (k, p − 1) ≠ 1, akkor k-nak létezik egy olyan k_{0} prímosztója, amelyre k_{0}|p − 1. Ekkor minden a ∈ A, b ∈ B-re, f(a, b) nemcsak k-adik, hanem k_{0}-adik hatvány is mod p, és (k_{0}, p − 1) ≠ 1.

Tehát az általánosság megsértése nélkül feltehetjük, hogy k prím, és szimmetrikus okokból azt is, hogy |A| ≤ |B|. Ekkor k|p−1. Ismeretes a következő egyszerű állítás: Ha (x, p) = 1, úgy:

∑_{χ:χ^{k}=χ_{0}} χ(x) = \{ \begin{matrix}k & ha x k-adik hatvány mod p és x ≢ 0 mod p, \\ 0 & ha x nem k-adik hatvány mod p vagy x ≡ 0 mod p. \end{matrix}

Ezt, a 3.9. tételt, és |A| ≤ |B| használva kapjuk:

k (|A| |B| − \sqrt{|A| |B|}) ≤ k |A| (|B| − 1) ≤ ∑_{a∈A} ∑_{f(a,b)≠0^{b∈B}} ∑_{χ:χ^{k}=χ_{0}} χ (f(a, b)) ≤
≤ |A| |B| + ∑_{χ≠χ_{0}^{χ:χ^{k}=χ_{0}}} ∑_{a∈A} ∑_{b∈B} χ (f(a, b)) ≤
≤ |A| |B| + (k − 1)\sqrt{p}\sqrt{|A| |B|}.

Ebből:

|A| |B| ≤ (\sqrt{p} + \frac{k}{k − 1})^{2} .

Ezután már bebizonyíthajuk a következő összegsorozatokra vonatkozó tételt, a 3.1. tétel additív megfelelőjét.

3.11. Tétel. Minden k > 1 egész esetén létezik N_{0}, hogy ha N ≥ N_{0}, A, B ⊆ {1, 2, …, N} és A + B minden eleme k-adik hatvány, akkor

min (|A| , |B|) ≤ 4k log N.

A bizonyítás Gallagher nagyobb szitáján alapul.

3.12. Lemma. (Gallagher) Legyen X ⊆ {M + 1, M + 2, …, M + N} egész számokból álló halmaz. Minden p prímre jelölje ν_{X}(p) azon mod p maradék osztályok számát, amelyek tartalmaznak X-ből elemet. Ha P prímszámok egy véges halmaza, akkor

|X| ≤ \frac{∑_{p∈P} log p − log N}{∑_{p∈P} \frac{log p}{ν_{X}(p)} − log N}

feltéve, hogy a nevező pozitív.

A lemma bizonyítása megtalálható például [26]-ben

Legyen p prím és p ≡ 1 mod k. Ezután hagyjuk el egy pillanatra az A és a B halmazokból a p-vel osztható elemeket. A 3.12. tétel szerint az alábbi egyenlőtlenséget kapjuk:

(ν_{A} (p) − 1) (ν_{B} (p) − 1) ≤ (\sqrt{p} + 2) .

Ebből:

min\{ν_{A} (p) , ν_{B} (p)\} ≤ \sqrt{p} + 3.

Legyen P = {p : p prím, p ≡ 1 mod k, p ≤ 4 (ϕ(k) log N)^{2})}. Osszuk a P halmazt két diszjunkt részre:

P_{A} = {p ∈ P : min{ν_{A} (p) , ν_{B} (p)} = ν_{A} (p)},
P_{B} = {p ∈ P : min{ν_{A} (p) , ν_{B} (p)} ≠ ν_{A} (p)}.

3.14. lemma szerint az alábbi egyenlőtlenségek közül az áll fenn, amelyikre teljesül, hogy a jobboldalon álló tört nevezője pozitív.

|A| ≤ \frac{∑_{p∈P_{A}} log p − log N}{∑_{p∈P_{A}} \frac{log p}{ν_{A}(p)} − log N} ,

|B| ≤ \frac{∑_{p∈P_{B}} log p − log N}{∑_{p∈P_{B}} \frac{log p}{ν_{B}(p)} − log N} .

Szimmetrikus okokból feltehetjük, hogy

∑_{p∈P_{A}} \frac{log p}{ν_{A} (p)} − log N ≥ ∑_{p∈P_{B}} \frac{log p}{ν_{B} (p)} − log N.

A Mertens tétel és a kis modulusú számtani sorozatokra vonatkozó prímszámtétel szerint:

2 ( ∑_{p∈P_{A}} \frac{log p}{ν_{A} (p)} − log N) ≥ ∑_{p∈P_{A}} \frac{log p}{ν_{A} (p)} − log N + ∑_{p∈P_{B}} \frac{log p}{ν_{B} (p)} − log N =

∑_{p∈P} \frac{log p}{min (ν_{A} (p) , ν_{B} (p))} − 2 log N ≥ ∑_{p∈P} \frac{log p}{\sqrt{p} + 3} − 2 log N = (2 + o(1)) log N

Ahonnan:

|A| ≤ \frac{∑_{p∈P} log p − log N}{(1 + o(1)) log N} ≤ 4k log N.

Tehát igaz a 3.13. tétel állítása.

Végül általánosítjuk a 3.12. tétel eredményét x^{k} helyébe más h(x) polinomt írva.

3.13. Tétel. Legyen p prím és h(x) ∈ F_{p}[x] n-edfokú polinom, ahol 2 ≤ n < p. Legyen A, B ⊆ \{1, 2, …, p − 1\} és |A| |B| ≥ p (\frac{p−1}{p−n})^{2} (n − 1)^{2}, ekkor:

a) Ha p − 1-nek nincs olyan d > 1 osztója, amelyre h(x) egy polinom d-edik hatványának a konstansszorosa, akkor létezik a ∈ A, b ∈ B, melyre ab ≡ h(x) (mod p) kongurencia megoldható. Sőt, e kongruencia megoldásszámát (a, b, x)-ben N-nel jelölve,

|N − |A| |B|| < \frac{n}{p − 1} |A| |B| + (n − 1)\sqrt{p |A| |B|}

is fenn áll.

b) Létezik a ∈ A, b ∈ B, hogy az a + b ≡ h(x) mod p kongruencia megoldható, továbbá a kongruencia megoldásszámát (a, b, x)-ben M-mel jelölve, kapjuk:

|M − |A| |B|| < (n − 1)\sqrt{p |A| |B|}.

A tétel a) részében a h(x)-re vonatkozó feltétel szükséges, hiszen ha d|p−1 és h(x) = c (h′[x])^{d}, úgy létezik m ∈ F_{p}, amely nem d-edik hatvány a p elemű testben. Legyen A = {x^{d} : x ∈ F_{p}, x ≠ 0}, B = {cmx^{d} : x ∈ F_{p}, x ≠ 0}. Ekkor az ab ≡ h(x) ≡ c (h′(x))^{d} mod p kongurenciának nincs megoldása a ∈ A, b ∈ B-ben, mert A és B halmaz definiciója miatt, ekkor ab = cmy^{d} teljesül valamiyen y ∈ F_{p}-re, ami ellentmond m választásának. Viszont |A| |B| = (\frac{p−1}{d})^{2}.

Először a tétel a) részét bizonyítjuk. Könnyen igazolható és jól ismert az alábbi lemma.

3.14. Lemma.

∑_{χ} |∑_{n=1}^{p−1} c_{n}χ(n)|^{2} = (p − 1) ∑_{n=1}^{p−1} c_{n}^{2}.

A következő lemma A. Weiltől származik. A bizonyítás megtalálható [31, 43.o]-ban.

3.15. Lemma. Legyen χ mod p multiplikatív karakter rendeje d > 1. Tegyük fel, hogy f(x) ∈ F_{p}[x] polinomnak m különböző gyöke van F_{p} algebrai lezártja felett, és nincs olyan polinom, amely d-edik hatványának konstansszorosa f(x). Ekkor:

|∑_{x∈F_{p}} χ (f(x))| ≤ (m − 1)\sqrt{p}.

Tetszőleges karakterre igaz az alábbi összefüggés:

∑_{χ} χ (a^{−1}b^{−1}h(x)) = \{ \begin{matrix}p − 1 & ha ab ≡ h(x) mod p, \\ 0 & különben. \end{matrix}

Ez alapján az ab ≡ h(x) mod p kongruencia akkor és csak akkor oldható meg a ∈ A, b ∈ B, x ∈ F_{p}-ben, ha

0 < (p − 1)N = ∑_{a∈A} ∑_{b∈B} ∑_{x=0}^{p−1} ∑_{χ} χ (a^{−1}b^{−1}h(x)) .

Jelölje H a h(x) polimom különböző gyökeinek számát. Így:

|(p − H) |A| |B| − (p − 1)N| = |∑_{a∈A} ∑_{b∈B} ∑_{x=0}^{p−1} ∑_{χ≠χ_{0}} χ (a^{−1}b^{−1}h(x))| .

A Cauchy-Schwarz egyenlőtlenséget, a 3.14. és 3.15. lemmát használva kapjuk:

|∑_{a∈A} ∑_{b∈B} ∑_{x=0}^{p−1} ∑_{χ≠χ_{0}} χ (a^{−1}b^{−1}h(x))| ≤

≤ ∑_{χ≠χ_{0}} |∑_{a∈A} χ(a^{−1}) ∑_{b∈B} χ(b^{−1})| |∑_{x=0}^{p−1} χ (h(x))| ≤

≤ \sqrt{∑_{χ≠χ_{0}} |∑_{a∈A} χ(a^{−1})|^{2}}\sqrt{∑_{χ≠χ_{0}} |∑_{b∈B} χ(b^{−1})|^{2}}(H − 1)\sqrt{p} ≤

≤ (H − 1)(p − 1)\sqrt{p |A| |B|}.

Tehát ha |A| |B| ≥ p (\frac{p−1}{p−n})^{2} (n−1)^{2}, akkor ∑_{a∈A} ∑_{b∈B} ∑_{x=0}^{p−1} ∑_{χ} χ (a^{−1}b^{−1}h(x)) > 0.

Továbbá:

(H − 1)\sqrt{p |A| |B|} > |N − \frac{p − H}{p − 1} |A| |B|| ≥ |N − |A| |B|| − \frac{H}{p − 1} |A| |B| .

Ezzel a tétel a) részét igazoltuk.

A b) rész igazolásához Weil tételének egy másik alakját használjuk.

3.16. Lemma. Legyen p prím és g(x) = a_{n}x^{n} + ⋯ + a_{0} olyan egész együtthatós polynom, ahol 0 < n < p és p |̸a_{n}. Ekkor:

|∑_{x=0}^{p−1} e (\frac{g(x)}{p})| ≤ (n − 1)\sqrt{p}.

A bizonyítás megtalálható [31, 45.o.]-ben. Tekintsük a következő egyszerű összefüggést:

∑_{k=0}^{p−1} e (\frac{k (h(x) − a − b)}{p}) = \{ \begin{matrix}p & ha a + b ≡ h(x) mod p, \\ 0 & különben. \end{matrix}

Ez alapján az a + b ≡ h(x) mod p kongruencia akkor és csak akkor oldható meg a ∈ A, b ∈ B, x ∈ F_{p}-ben, ha

0 < pN = ∑_{a∈A} ∑_{b∈B} ∑_{x=0}^{p−1} ∑_{k=0}^{p−1} e (\frac{k (h(x) − a − b)}{p}) .

Ebből:

|p |A| |B| − pN| = |∑_{a∈A} ∑_{b∈B} ∑_{x=0}^{p−1} ∑_{k=1}^{p−1} e (\frac{k (h(x) − a − b)}{p})| .

A Cauchy-Schwarz egyenlőtlenséget, a 2.14. és 3.16. lemmát használva kapjuk:

|∑_{a∈A} ∑_{b∈B} ∑_{x=0}^{p−1} ∑_{k=1}^{p−1} e (\frac{k (h(x) − a − b)}{p})| =

= ∑_{k=1}^{p−1} |∑_{a∈A} e (−\frac{ka}{p}) ∑_{b∈B} e (−\frac{kb}{p})| |∑_{x=0}^{p−1} e (\frac{kh(x)}{p})| ≤

≤ \sqrt{∑_{k=1}^{p−1} |∑_{a∈A} e (−\frac{ka}{p})|^{2}}\sqrt{∑_{k=1}^{p−1} |∑_{b∈B} e (−\frac{kb}{p})|^{2}}(n − 1)\sqrt{p} ≤

≤ (n − 1)p\sqrt{p |A| |B|}.

Tehát ha |A| |B| > p(n − 1)^{2}, akkor ∑_{a∈A} ∑_{b∈B} ∑_{x=0}^{p−1} ∑_{k=1}^{p−1} e (\frac{k(h(x)−a−b)}{p}) > 0. Ezzel

a 3.13. tételt bizonyítását befejeztük.

A 3.13. tételnek egyszerű következménye az általánosított Fermat kongruencia megoldhatóságára vonatkozó állítás.

3.17. Következmény. Legyen f(x), g(x), h(x) ∈ F_{p}[x] polinomok fokszáma közül a legnagyobb n, p prím és p > n^{4}.

a) Tegyük fel, hogy az f(x), g(x), h(x) polinomok között van egy, amely p−1nek semelyik d > 1 osztójára nem áll elő c (q(x))^{d} alakban, ahol c ∈ F_{p} és q(x) ∈ F_{p}[x]. Ekkor az f(x)g(y) ≡ h(z) mod p kongruencia megoldható.

b) Az f(x) + g(y) ≡ h(z) mod p kongruencia megoldható.

Ez az állítás nem új (lásd [21, 97-98.o.]); csak a nézőpont, amellyel megközelítettük a problémát, hiszen ezt az eredményt speciális eseteként kaptuk meg egy hibrid sorozatokra vonatkozó általános tételnek.

A tétel a) részének igazolásakor csak azt az esetet nézzük, amikor d|p−1, d > 1 esetén h(x) nem egy polinom d-edik hatványánk konstansszorosa. A többi eset ugyanúgy bizonyítható mint ez. Legyen A = {f(x) : x ∈ F_{p}}, B = \{g(y) : y ∈ F_{p}\}. Ekkor |A| , |B| ≥ \frac{p−1}{n} mivel az f(x) ≡ a mod p, g(y) ≡ a mod p kongurenciák bármelyikének legfeljebb n megoldása van. Így |A| |B| > p (\frac{p−1}{p−n})^{2} (n − 1)^{2}. Ezután a 3.13. tételt alkalmazva a 3.18. következmény állítását kapjuk.

4. ab+1 alakú számoknak egy oszthatósági tu-

lajdonsága

Diofantosz problémájának egy lehetséges megfordítása az, ha olyan A, B halmazok méretét becsüljük, ahol A × B + 1 minden eleme négyzetmentes szám. Először felső becslést adunk.

4.1. Tétel. Ha A, B ⊆ {1, 2, …, N} és A × B + 1 minden eleme négyzetmentes szám, akkor

|A| |B| ≪ N^{\frac{3}{2}} (log N)^{2}.

A bizonyításhoz a következő jelöléseket használjuk: Minden m-re, legyen f(m) azon mod m maradékosztályok száma, amelyek metszik A-t. Hasonlóan g(m) azon mod m maradékosztályok száma, amelyek metszik B-t. Legyen végül ρ(m) azon mod m maradékosztályok száma, amelyek diszjunktak A-tól. A következő lemma a kínai maradéktételre épül.

4.2. Lemma. Legfeljebb egy p prím létezik, hogy \sqrt[4]{\frac{N}{2}} ≤ p ≤ \sqrt[4]{N} és ρ(p^{2}) < p^{c}, ahol c = 2\frac{log|A|−log 2}{log N}.

Tegyük fel ugyanis, hogy két különböző prím is eleget tesz a lemma feltételeinek: p_{1} és p_{2}. A kínai maradéktétel szerint legfeljebb ρ(p_{1}^{2})ρ(p_{2}^{2}) darab olyan mod p_{1}^{2}p_{2}^{2} maradékosztály van, amely metszi A-t. Felhasználva ezt, és azt, hogy \sqrt[4]{\frac{N}{2}} ≤ p_{1}, p_{2} ≤ \sqrt[4]{N}, kapjuk:

|A| ≤ ρ(p_{1}^{2})ρ(p_{2}^{2}) ⌈\frac{N}{p_{1}^{2}p_{2}^{2}} ⌉ ≤ 2ρ(p_{1}^{2})ρ(p_{2}^{2}) < 2(p_{1}p_{2})^{c} ≤ 2N^{\frac{c}{2}} = |A| .

Ezzel ellentmondásra jutottunk.

A 4.1. tétel bizonyítása során feltehetjük, hogy |A| ≥ 2\sqrt{N}(log N)^{2} és |B| ≥ 2\sqrt{N}(log N)^{2}, különben a tétel triviális. Ha N ≥ e^{4} és \sqrt[4]{\frac{N}{2}} ≤ p ≤ \sqrt[4]{N}, úgy

2\frac{log |A| − log 2}{log N} ≥ 2\frac{log (\sqrt{N}(log N)^{2})}{log N} = 1 + \frac{4 log log N}{log N} ≥
≥ 1 + \frac{8 log 2}{log N} ≥ 1 + \frac{log 2}{log \sqrt[4]{\frac{N}{2}}} ≥ \frac{log(2p)}{log p}.

Ez alapján, a 4.2. lemmát alkalmazva kapjuk, hogy legfeljebb egy olyan p_{A} prím létezik, melyre \sqrt[4]{\frac{N}{2}} ≤ p_{A} ≤ \sqrt[4]{N} és ρ(p_{A}^{2}) < 2p_{A}. Ezért, ha \sqrt[4]{\frac{N}{2}} ≤ p ≤ \sqrt[4]{N} prím és p ≠ p_{A}, akkor f(p^{2}) ≤ p^{2} − 2p. Hasonlóan bizonyíthatjuk, hogy legfeljebb egy p_{B} prím kivételével, minden \sqrt[4]{\frac{N}{2}} ≤ p ≤ \sqrt[4]{N} prímre teljesül az, hogy g(p^{2}) ≤ p^{2} − 2p.

Legyen x egy tetszőleges mod p^{2} maradékosztály, amely metszi A-t és (x, p^{2}) = 1. Ekkor egyértelműen létezik egy x^{∗} maradékosztály, melyre

xx^{∗} ≡ −1 mod p^{2}.

Nyilvánvaló, hogy ez az x^{∗} maradékosztály diszjunkt B-től. Ezért ρ(p^{2})−p ≤ g(p^{2}), és így p^{2} − f(p^{2}) − p ≤ g(p^{2}). Tehát:

f(p^{2}) + g(p^{2}) ≥ p^{2} − p.

A nagy szita következő alakját Sárközy Gábor [29, 274.o.] bizonyította: Ha A, B ⊆ \{1, 2, …, N\}, M ⊆ \{1, 2, …, [\sqrt{N}]\}, és M elemei páronként relatív prímek, akkor

|A| ≤ \frac{2N}{∑_{m∈M} \frac{f(m)}{m−f(m)}} , |B| ≤ \frac{2N}{∑_{m∈M} \frac{g(m)}{m−g(m)}} .

Összeszorozva e két egyenlőtlenséget:

|A| |B| ≤ \frac{4N^{2}}{∑_{m∈M} \frac{f(m)}{m−f(m)} ∑_{m∈M} \frac{g(m)}{m−g(m)}} .  (4.1)

Legyen M = \{p^{2} : \sqrt[4]{\frac{N}{2}} ≤ p ≤ \sqrt[4]{N}, p prím, p ≠ p_{A} és p ≠ p_{B}\}. A (4.1) jobboldalán álló tört nevezőjét alulról becsüljük a Cauchy-Schwarz egyenlőtlenség segítségével.

∑_{p^{2}∈M} \frac{f(p^{2})}{p^{2} − f(p^{2})} ∑_{p^{2}∈M} \frac{g(p^{2})}{p^{2} − g(p^{2})} ≥

≥ ( \sqrt[∑_{p^{2}∈M}]{\frac{f(p^{2})g(p^{2})}{p^{4} − (f(p^{2}) + g(p^{2}))p^{2} + f(p^{2})g(p^{2})}})^{2} .

Mivel f(p^{2})+g(p^{2}) ≥ p^{2} −p és f(p^{2}), g(p^{2}) ≤ p^{2} −2p, ha p^{2} ∈ M, ezért ekkor

f(p^{2})g(p^{2}) ≥ (p^{2} − 2p)(f(p^{2}) + g(p^{2}) − (p^{2} − 2p)) ≥ (p^{2} − 2p)p ≥ \frac{p^{3}}{3} .

Így:

( \sqrt[∑_{p^{2}∈M}]{\frac{f(p^{2})g(p^{2})}{p^{4} − (f(p^{2}) + g(p^{2}))p^{2} + f(p^{2})g(p^{2})}})^{2} ≥

≥ (  \sqrt[∑_{p^{2}∈M}]{\frac{f(p^{2})g(p^{2})}{p^{3} + f(p^{2})g(p^{2})}})^{2} = (  \sqrt[∑_{p^{2}∈M}]{1 − \frac{p^{3}}{p^{3} + f(p^{2})g(p^{2})}})^{2} ≥

≥ ( \sqrt[∑_{p^{2}∈M}]{1 − \frac{p^{3}}{p^{3} + p^{3}/3}})^{2} = ( ∑_{p^{2}∈M} \frac{1}{2})^{2} ≫ \begin{matrix}√ & \overline{N} \\ (log N) & 2 \end{matrix} .

Ezt a (4.1) egyenlőtlenségbe írva, kapjuk:

|A| |B| ≪ N^{\frac{3}{2}} (log N)^{2}.

Ezzel a 4.1. tételt igazoltuk.

Ezután egy alsó becslést adunk |A| = |B| esetén.

4.3. Tétel. a) Léteznek A, B ⊆ {1, 2, …, N} halmazok, melyekre

|A| = |B| ≫ (log N)^{2},

és A + B minden eleme négyzetmentes szám.

b) Léteznek A, B ⊆ {1, 2, …, N} halmazok, melyekre |A| = |B| ≫ (log N)^{2}

és A × B + 1 minden eleme négyzetmentes szám.

Az alsó és a felső becslés elég messze van egymástól. Valószínűnek tartom, hogy a két becslés közül, az alsó van közelebb az igazsághoz. A fenti tétel gráfelméleten alapul.

Jelölje p_{i} az i-edik prímszámot, és legyen N elég nagy pozitív egész szám. Definiáljuk K-t a következő módon:

∏_{i=1}^{K−1} p_{i} < N^{\frac{1}{6}} ≤ ∏_{i=1}^{K} p_{i}.  (4.2)

Legyen P =^{def} ∏_{i=1}^{K} p_{i}. Ekkor, a prímszám tétel szerint

log P = ∑_{i=1}^{K} log p_{i} ∼ ∑_{n≤p_{K}} Λ(n) ∼ p_{K}.  (4.3)

Így nagy N-ekre:

N^{\frac{1}{6}} ≤ P < N^{\frac{1}{5}} .  (4.4)

Tekintsük a következő gráfelméleti lemmát.

4.4. Lemma. Tegyük fel, hogy a G egyszerű gráfnak n szögpontja és m éle van. Ha G nem tartalmaz K_{r,r}-t, akkor

2m < \sqrt[r]{r − 1} · n^{2− \frac{1}{r}} + (r − 1)n.

A bizonyítás megtalálható [24]-ben. Ebből a lemmából vezetjük le a következőt.

4.5. Lemma. Létezik n_{0} pozitív szám, hogy ha n ≥ n_{0}, és G egyszerű gráfnak n szögpontja, m éle van, továbbá

r ≤ min \{\frac{2m}{n}, \frac{\binom{n}{2} − m}{n}, \frac{n^{2} log n}{7 (\binom{n}{2} − m)} − \frac{3 log n}{7}\} ,

akkor G tartalmaz K_{r,r}-t.

Tegyük fel, hogy a lemma állítás nem igaz. Ekkor a 4.4. lemma szerint:

2m < \sqrt[r]{r − 1} · n^{2− \frac{1}{r}} + (r − 1)n.

r ≤ \frac{2m}{n}, tehát:

(2m − (r − 1)n)^{r} < (r − 1)n^{2r−1}.

Ebből, és az r − 1 ≤ \sqrt{\frac{\binom{n}{2}−m}{n} \frac{n^{2} log n}{7(\binom{n}{2}−m)}} ≤ n^{\frac{4}{7}} , rn ≤ \binom{n}{2} − m, 1 + x < e^{x} egyenlőtlenségekből kapjuk:

n^{\frac{3}{7}} ≤ \frac{n}{r − 1} < (\frac{n^{2}}{2m − (r − 1)n})^{r} = (1 + \frac{2 (\binom{n}{2} − m) + rn}{n^{2} − 2 (\binom{n}{2} − m) − rn})^{r} <

< (1 + \frac{3 (\binom{n}{2} − m)}{n^{2} − 3 (\binom{n}{2} − m)})^{r} < e^{r \frac{3(\binom{n}{2}−m)}{n^{2}−3(\binom{n}{2}−m)}} .

Ezt r-re rendezve:

\frac{n^{2} log n}{7 (\binom{n}{2} − m)} − \frac{3 log n}{7} < r,

ami ellentmondás.

Legyen f(a, b) értéke a + b az a) esetben és ab + 1 a b) esetben. A 4.3. tétel bizonyítása céljából nézzük azt a gráfot, amelynek szögpontjai 1, 2P + 1, 4P + 1, …, [\frac{N−1}{2P}] 2P + 1. Az x, y szögpontokat pontosan akkor köti össze él G-ben, ha f(x, y) négyzetmentes szám. Ha x, y ∈ {1, 2P + 1, 4P + 1, …, [\frac{N−1}{2P}] 2P + 1\}, akkor (x, y) pár értéke legyen f(x, y).

P definiciója miatt nincs olyan (x, y) pár, amelynek értéke osztható egy olyan q^{2}-tel, ahol q ≤ p_{K} és q prím. Azon pároknak a száma, melyeknek értéke osztható egy olyan q^{2}-tel, ahol q ≥ p_{K} és q prím:

\begin{aligned}[ & \frac{N−1}{2P} & ] \\ & ∑ \\ & k=0 \end{aligned} [\frac{N−1}{2P}] ; ∑ ; q^{2}|f(2P k+1,2P ℓ+1)^{ℓ=0} 1 ≤ \begin{aligned}[ & \frac{N−1}{2P} & ] \\ & ∑ \\ & k=0 \end{aligned} (\frac{[\frac{N−1}{2P}]}{q^{2}} + 1) =
= \frac{[\frac{N−1}{2P}]^{2} + [\frac{N−1}{2P}]}{q^{2}} + [\frac{N − 1}{2P}] + 1.  (4.5)

Mivel x + y ≤ 2N így az a) esetben nincs olyan (x, y) pár, amelynek az értéke osztható egy \frac{N^{2}}{P^{2}} -nél nagyobb számmal.

A b) esetben pedig legfeljebb (π(N) − π (\frac{N}{P} )) P^{2} < P^{2}N olyan xy + 1 szám van, melynek létezik egy q^{2} alakú osztója, ahol q^{2} > \frac{N^{2}}{P^{2}} , és q prím. Wigert’s tétele [35] szerint, ha N elég nagy, és xy + 1 értéke adott, úgy x legfeljebb d(xy) ≤ max_{m≤N^{2}} d(m) ≤ N^{\frac{2}{log log N}} értéket vehet fel. Összefoglalva, a b) esetben legfeljebb P^{2}N^{1+ \frac{2}{log log N}} olyan (x, y) pár van, amelynek értéke osztható egy olyan q^{2} számmal, ahol q^{2} > \frac{N^{2}}{P^{2}} és q prím. (4.4) alapján P^{2}N^{1+ \frac{2}{log log N}} < \frac{N^{2}}{P^{2} log N}.

(4.3), (4.4) és (4.5) szerint, azoknak az (x, y) pároknak a száma, amelyeknek az értéke nem négyzetmentes, kevesebb mint

\frac{N^{2}}{P^{2} log N} + ∑_{q prime^{p_{K+1}≤q≤ \frac{N}{P}}} (\frac{[\frac{N−1}{2P}]2}{q^{2}} + 3 [\frac{N − 1}{2P}]) ≤ \frac{N^{2}}{P^{2} log N} + ∑_{p_{K+1}≤q} \frac{[\frac{N−1}{2P}]2}{q(q − 1)}

+3 [\frac{N − 1}{2P}] π (\frac{N}{P} ) ≪ \frac{N^{2}}{P^{2} log N} + \frac{[\frac{N−1}{2P}]2}{p_{K+1} − 1} ≪ log [\frac{N−1}{2P}]^{[\frac{N−1}{2P}]2}.

Kiszámoltuk tehát, hogy a G gráfnak n = [\frac{N−1}{2P}] + 1 szögpontja és m > \binom{n}{2} − c\frac{n^{2}}{log n} éle van, ahol c konstans. Hagyjunk el G-ből éleket addíg, amig a G-nek pontosan [\binom{n}{2} − c\frac{n^{2}}{log n}] + 1 darab éle nem lesz. A 4.5. lemmát alkalmazva, azonnal adódik, hogy G tartalmaz K_{r,r}-t, ahol r = [\frac{(log n)^{2}}{8c} ]. Könnyen látszik, hogy ha A és B halmazoknak K_{r,r} két osztályát választjuk, úgy azok eleget tesznek a 4.3. tétel feltételeinek.

Felmerül a kérdés, hogy egy halmaz esetén, hogyan módosul ez az alsó becslés.

4.6. Tétel. a) Létezik A ⊆ {1, 2, …, N} halmaz, melyre |A| ≫ log N és A + A minden eleme négyzetmentes szám.

b) Létezik A ⊆ {1, 2, …, N} halmaz, melyre |A| ≫ log N és A × A + 1 minden eleme négyzetmentes szám.

A tétel a) része Erdős Páltól és Sárközy Andrástól [8] származik. Most egy új bizonyítást adunk erre a tényre, együtt kezelve az additív és a multiplikatív esetet.

Legyen f(a, b) értéke továbbra is a+b az a) esetben és ab+1 a b) esetben. Kicsit módosítjuk az előző bizonyításban szereplő G gráf definicióját.

V (G) =^{def} \{2ℓP + 1 : f(2ℓP + 1, 2ℓP + 1) négyzetmentes, 1 ≤ ℓ ≤ [\frac{N−1}{2P}]\} .

Erre azért van szükség, mert különben előfordulhatna, hogy a ∈ A esetén a+a (illetve a b) esetben aa + 1) nem négyzetmetes szám. Az éleket ugyanúgy definiáljuk, ahogy a 4.3. tétel bizonyításában.

Érdemes G gráfban minél nagyobb teljes gráfot keresni, és annak csúcsait választani az A halmaznak. Ehhez először G gráf n szögpontszámát és m élszámát becsüljük.

Az a) esetben triviális, hogy n ≫ [\frac{N−1}{2P}]. Belátjuk, hogy ugyanez fennáll a b) esetben is. Ehhez azon ℓ-ek számát kell becsülni, ahol (2ℓP + 1)^{2} + 1 nem négyzetmentes szám. Két esetet különböztetünk meg aszerint, hogy (2ℓP + 1)^{2} + 1-nek létezik-e olyan q^{2} osztója, ahol q > (\frac{N}{12P} ) és q prím.

Legyen q prím. Ha q < p_{K} úgy q^{2} ∤ (2ℓP + 1)^{2} + 1. Ha p_{K} < q akkor legfeljebb \frac{N−1}{p^{2}P} +2 olyan 1 ≤ ℓ ≤ [\frac{N−1}{2P}] szám van, amelyre q^{2} | (2ℓP +1)^{2} +1. Tehát legfeljebb

\frac{N}{6P} + \frac{N − 1}{p_{K}^{2}P} + \frac{N − 1}{p_{K+1}^{2}P} + \frac{N − 1}{p_{K+2}^{2}P} ⋯ < \frac{N}{6P} + \frac{2N}{P log P} < \frac{N}{5P}

olyan 1 ≤ ℓ ≤ [\frac{N−1}{2P}] szám van, amelyre (2ℓP +1)^{2}+1-nek van egy q^{2} osztója, ahol q ≤ \frac{N}{12P} és q prím. A másik esetben, mikor (2ℓP + 1)^{2} + 1-nek olyan q^{2} osztója van, ahol q > \frac{N}{12P} és q prím, felírhatjuk a következő Pell-egyenletet:

(2ℓP + 1)^{2} + 1 = q^{2}D.

Ekkor D ≤ \frac{(2ℓP +1)^{2}+1}{(\frac{N}{12P})^{2}} ≤ \frac{N^{2}+1}{(\frac{N}{12P})^{2}} < 150P^{2}. Fix D-re az a^{2} − p^{2}D = −1 Pell-

egyenlet megoldásszáma a ∈ \{1, 2, …, N\}, q ∈ ℕ-re nem haladja meg \frac{log N}{log 2} -t.

Ezért a

(2ℓP + 1)^{2} − p^{2}D = −1

egyenlet megoldásszáma 2ℓP + 1 ∈ {1, …, N}, q ∈ ℕ, D ∈ {1, … 150P^{2}}-re kevesebb mint 150P^{2} \frac{log N}{log 2} < 500P^{2} log N. Összesen, tehát legfeljebb

\frac{N}{5P} + 500P^{2} log N < \frac{1}{2} [\frac{N − 1}{2P}]

olyan 1 ≤ ℓ ≤ [\frac{N−1}{2P}] szám van, amelyre (2ℓP + 1)^{2} + 1 nem négyzetmentes szám. Ezzel a b) esetben is beláttuk, hogy V (G) = n ≫ [\frac{N−1}{2P}].

A 4.3. tétel bizonyítása szerint E(G) = m > \binom{n}{2}−c′ \frac{n^{2}}{log n}, ahol c′ konstans. A Turán tételt [33] alkalmazva adódik a 4.6. tétel állítása.

5. Hatvány, hatványteli számok összegsoroza-

tokban

A. Sárközy, J. Rivat, C.L.Stewart [26] foglalkozott azzal a problémával, amikor a, a′ ∈ A, a ≠ a′ esetén a+a′ négyzetszám. Ennek egy további lehetséges általánosítása az, ha a, a′ ∈ A, a ≠ a′ esetén a+a′ mindig hatványszám. Később ennek az eredménynek egy részhalmaz összegekre vonatkozó analogonját vizsgáljuk.

Legyen V a hatványszámok halmaza:

V = {x^{k} : x ∈ ℕ, k ∈ ℕ, k ≥ 2} ,

és minden K egész számra

V_{K} = {x^{k} : x ∈ ℕ, k ∈ ℕ, 2 ≤ k ≤ K} .

Egy n számot pontosan akkor nevezünk hatványtelinek, ha p | n, p prím esetén p^{2} | n is teljesül. A hatványteli számok halmaza legyen W:

W = {n : n ∈ ℕ, p | n p prím esetén p^{2} | n} .

Végül az A halmaz minden véges részhalmazára vegyük a benne lévő elemek összegét:

P(A) = {∑_{a∈A} ε_{a}a : a ∈ A ε_{a} = 0 vagy 1, 0 < ∑_{a∈A} ε_{a} < ∞} .

5.1. Tétel. Létezik c_{1} > 0 konstans, hogy ha N, K > 1 egész számok, A ⊆ {1, 2, …, N} és a, a′ ∈ A, a ≠ a′ esetén a + a′ ∈ V_{K}, akkor

|A| < c_{1}e^{46K} log N.

Az 5.1. tétel bizonyításhoz szükségünk van néhany lemmára. Az 5.2. lemmában és bizonyításában q, q_{1}, q_{2}, … prímeket jelöl.

5.2. Lemma. Legyen K ≥ 2 egész szám és Q_{K} = ∏_{q≤K} q. Tegyük fel, hogy p prímre

p ≡ 1 (mod Q_{K}).  (5.1)

Legyen B ⊆ ℤ_{p} halmaz, melyre b, b′ ∈ B b ≠ b′ esetén létezik egy k és x egész, hogy 2 ≤ k ≤ K, továbbá

b + b′ ≡ x^{k} mod p.  (5.2)

Ekkor létezik egy abszolút c_{2} > 0 konstans, melyre

|B| < c_{2}(log K)2^{π(K)}p^{\frac{1}{2}} .  (5.3)

Ha rögzített b, b′ és k esetén megoldható a (5.2) kongruencia, úgy nyilvánvaló, hogy

b + b′ ≡ y^{q} (mod p)

kongruencia is megoldható, ha q prím és q | k. Minden q prímre és n egészre f_{q}(n)-t a következőképpen definiáljuk:

f_{q}(n) = \{ \begin{matrix}1 & ha n ≡ y^{q} (mod p) kongruencia megoldható, \\ 0 & különben. \end{matrix}

Az előző megjegyzésből következik, hogy az F_{K}(n) =^{def} 1 − ∏_{2≤q≤K}(1 − f_{q}(n)) függvényre teljesül az alábbi:

F_{K}(n) = \begin{cases}1 & ha n ≡ y^{k} (mod p) kongruencia megoldható \\ & valamilyen 2 ≤ k ≤ K egész számra, \\ 0 & különben. \end{cases}

A lemma B-re vonatkozó feltétele miatt:

∑_{b∈B} ∑_{b′∈B} F_{K}(b + b′) ≥ ∑_{\begin{matrix}b,b′∈B \\ b≠b′ \end{matrix}} 1 = |B|^{2} − |B|.

Legyen g primitív gyök modulo p. Ha q ≤ K prím, akkor jelölje χ_{q} azt az egyértelműen meghatározott modulo p karaktert, amelyre

χ_{q}(g) = e (\frac{1}{q});

megjegyezzük, hogy q ≤ K és (5.1) miatt p | q − 1, tehát valóban létezik ilyen karakter. Mivel ez a karakter q-ad rendű:

f_{q}(n) = \frac{1}{q} ∑_{j=0}^{q−1} χ_{q}^{j}(n) ha (n, p) = 1.  (5.4)

F_{K}(n) definiciójából és (5.4)-ből következik, hogy ha (n, p) = 1, akkor:

\begin{aligned}F_{K}(n) & = ∑_{ℓ=1}^{π(K)}(−1)^{ℓ+1} ∑_{q_{1}<···<q_{ℓ}≤K} ∏_{i=1}^{ℓ} f_{q_{i}}(n) \\ & = ∑_{ℓ=1}^{π(K)}(−1)^{ℓ+1} ∑_{q_{1}<···<q_{ℓ}≤K} \frac{1}{q_{1} ⋯ q_{ℓ}} ∑_{j_{1}=0}^{q_{1}−1} ⋯ ∑_{j_{ℓ}=0}^{q_{ℓ}−1} χ_{q_{1}}^{j_{1}} ⋯ χ_{q_{ℓ}}^{j_{ℓ}}(n). \end{aligned} (5.5)

Érdemes külön vizsgálni azt a két esetet, amikor χ_{q_{1}}^{j_{1}} … χ_{q_{ℓ}}^{j_{ℓ}} főkarakter illetve azt, amikor nem az. χ_{q_{1}}^{j_{1}} … χ_{q_{ℓ}}^{j_{ℓ}} pontosan akkor főkarakter, ha (χ_{q_{1}}(g))^{j_{1}} … (χ_{q_{ℓ}}(g))^{j_{ℓ}} = e (\frac{j_{1}}{q_{1}} + ⋯ + \frac{j_{ℓ}}{q_{ℓ}} ) = 1, azaz \frac{j_{1}}{q_{1}} + ⋯ + \frac{j_{ℓ}}{q_{ℓ}} egész, ami 0 ≤ j_{1} < q_{1}, …, 0 ≤ j_{ℓ} < q_{ℓ} esetén ekvivalens azzal, hogy j_{1} = ⋯ = j_{ℓ} = 0. Így (5.5) alapján:

∑_{\begin{matrix}b,b′∈B \\ (b+b′,p)=1 \end{matrix}} F_{K}(b + b′) = ∑_{ℓ=1}^{π(K)}(−1)^{ℓ+1} ∑_{q_{1}<···<q_{ℓ}≤K} \frac{1}{q_{1} ⋯ q_{ℓ}} ∑_{\begin{matrix}b,b′∈B \\ (b+b′,p)=1 \end{matrix}} 1

+ ∑_{ℓ=1}^{π(K)}(−1)^{ℓ+1} ∑_{q_{1}<···<q_{ℓ}≤K} \frac{1}{q_{1} ⋯ q_{ℓ}} ∑_{\begin{matrix}0≤j_{1}<q_{1},...,0≤j_{ℓ}<q_{ℓ} \\ (j_{1},...,j_{ℓ})≠(0,...,0) \end{matrix}}

∑_{\begin{matrix}b,b′∈B \\ (b+b′,p)=1 \end{matrix}} χ_{q_{1}}^{j_{1}} ⋯ χ_{q_{ℓ}}^{j_{ℓ}}(b + b′) = ∑_{1} + ∑_{2} .

Ezután ∑_{1}, ∑_{2} értékét becsüljük. ∑_{1} szorzattá alkítható, majd a Mertens Tétel alapján felülről becsülhető:

\begin{aligned}|_{∑1}| & = (1 − ∏_{q≤K} (1 − \frac{1}{q})) ∑_{\begin{matrix}b,b′∈B \\ (b+b′,p)=1 \end{matrix}} 1 ≤ (1 − ∏_{q≤K} (1 − \frac{1}{q})) |B|^{2} < \\ & < |B|^{2} − \frac{2 |B|^{2}}{c_{2} log K} . \end{aligned}

Mivel ∑_{2}-ben a χ_{q_{1}}^{j_{1}} … χ_{q_{ℓ}}^{j_{ℓ}} karakter nem főkarater, ezért a 2.12. tételt használva a következőt kapjuk:

|∑_{2}| ≤ ∑_{ℓ=1}^{π(K)} ∑_{q_{1}<···<q_{ℓ}≤K} \frac{1}{q_{1} ⋯ q_{ℓ}} ∑_{\begin{matrix}0≤j_{1}<q_{1},...,0≤j_{ℓ}<q_{ℓ} \\ (j_{1},...,j_{ℓ})≠(0,...,0) \end{matrix}} | ∑_{\begin{matrix}b,b′∈B \\ (b+b′,p)=1 \end{matrix}} χ_{q_{1}}^{j_{1}} ⋯ χ_{q_{ℓ}}^{j_{ℓ}}(b + b′)|

≤ ∑_{ℓ=1}^{π(K)} ∑_{q_{1}<···<q_{ℓ}≤K} \frac{1}{q_{1} ⋯ q_{ℓ}} ∑_{\begin{matrix}0≤j_{1}<q_{1},...,0≤j_{ℓ}<q_{ℓ} \\ (j_{1},...,j_{ℓ})≠(0,...,0) \end{matrix}} p^{\frac{1}{2}} |B|

≤ p^{\frac{1}{2}} |B| ∑_{ℓ=1}^{π(K)} ∑_{q_{1}<···<q_{ℓ}≤K} 1 < p^{\frac{1}{2}} |B|2^{π(K)}.

Összefoglalva:

\begin{aligned}|B|^{2} − |B| & ≤ ∑_{b∈B} ∑_{b′∈B} F_{K}(b + b′) ≤ ∑_{\begin{matrix}b,b′∈B \\ (b+b′,p)=1 \end{matrix}} F_{K}(b + b′) + |B| = ∑_{1} + ∑_{2} + \\ & + |B| < |B|^{2} − \frac{2 |B|^{2}}{c_{2} log K} + p^{1/2}|B|2^{π(K)} + |B|. \end{aligned}

Ebből pedig már a lemma állítása már triviálisan következik.

A Linnik konstans segítségével igazolható az alábbi lemma.

5.3. Lemma. Léteznek q_{0}, c_{3} konstansok, hogy ha q ≥ q_{0}, a ∈ ℤ, (a, q) = 1 és

x ≥ q^{80},  (5.6)

akkor

∑_{\begin{matrix}\frac{x}{q^{8}} <p<x \\ p≡a (mod q) \end{matrix}} \frac{log p}{p} > c_{3} \frac{log q}{φ(q)}.  (5.7)

Mivel a bizonyítás kissé hosszadalmas, ezért elhagyjuk.

Most már rátérhetünk az 5.1. tétel bizonyítására. Tegyük fel, hogy A és K eleget tesz a tétel feltételeinek. Legyen Q_{K} = ∏_{\begin{matrix}q≤K, \\ q prím \end{matrix}} q, és p ≡ 1 mod Q_{K}. B_{p} definiciója az alábbi:

B_{p} = {b : b ∈ {0, 1, …, p − 1}, ∃ a ∈ A melyre a ≡ b (mod p)} .

Mivel B_{p} halmaz teljesíti az 5.1. lemma feltételeit, ezért

|B_{p}| < c_{2} log K2^{π(K)}p^{1/2}.

A 3.12. lemma jelöléseit használva, ebből

ν_{A}(p) < c_{2} log K2^{π(K)}p^{1/2}.

Legyen P = {p : p prím, p ≤ CQ_{K}^{80} (log N)^{2} p ≡ 1 mod Q_{K}}, ahol C konstans elegendően nagy. A 3.12. és az 5.3. lemmát valamint a Brun-Titchmarsh egyenlőtlenséget alkalmazva, kapjuk:

|A| ≤ c_{1}e^{46} log N.

Ezzel az 5.1. tételt igazoltuk.

Az 5.1. tételben V_{K}-t V -vel helyettesítve lényegesen gyengébb felső becslést tudunk adni.

5.4. Tétel. Létezik N_{0} konstans, hogy ha N > N_{0} positív egész, és A ⊆ {1, 2, …, N} halmazra teljesül, hogy a, a′ ∈ A, a ≠ a′ esetén a + a′ ∈ V, akkor

|A| < exp (22(log N)^{1/2}) .

A tételt indirekten bizonyítjuk. Tegyük fel, hogy

|A| ≥ exp (22(log N)^{1/2}) .

Legyen K = \frac{1}{5} (log N)^{1/2}, és a ∈ A-ra jelölje S(a) a következő halmazt:

S(a) = {a′ : a + a′ = x^{k}, ahol x ∈ ℕ, k ∈ ℕ, k > K}.

Mivel a + a′ ≤ 2N minden a, a′ ∈ A-ra, ezért

|S(a)| ≤ |{x^{k} : x ∈ ℕ, k ∈ ℕ, k > K, x^{k} ≤ 2N}|
≤ ∑_{K<k≤ \frac{log 2N}{log 2}} (2N)^{\frac{1}{K}} < exp (11(log N)^{\frac{1}{2}} )

(5.8)

minden a ∈ A esetén. Legyen L = exp (11(log N)^{\frac{1}{2}} ) és r = [\frac{|A|}{2L}]. A_{0}, A_{1}, …, A_{r} halmazokat és b_{1}, b_{2}, …, b_{r} egész számokat a következő módon definiáljuk: A_{0} = A, és ha 1 ≤ i ≤ r, akkor legyen b_{i} ∈ A_{i−1}, b_{i} ∉ {b_{1}, …, b_{i−1}} tetszőleges egész, és A_{i} = A_{i−1}\S(b_{i}). (5.8)-ből következik, hogy |A_{i}| > |A_{i−1}| − L, így |A_{i}| > |A| − iL. Tehát

|A_{r}| ≥ |A| − rL = |A| − [\frac{|A|}{2L}] L ≥ \frac{|A|}{2},

ezért az előző rekurzív definició valóban működik.

Legyen B = {b_{1}, b_{2}, …, b_{r}}. Ekkor

|B| = r = [\frac{|A|}{2L}] > exp (10(log N)^{\frac{1}{2}} ) .

Másrészt b_{1}, …, b_{r} számok és A_{0}, A_{1}, …, A_{r} halmazok definiciója miatt b_{i} + b_{j} ∈ V_{K}, 1 ≤ i < j ≤ r esetén. Az 5.1.tétel szerint:

|B| < c_{1}e^{46K} log N < exp (10(log N)^{\frac{1}{2}} ) ,

ha N elég nagy. Ez azonban ellentmond B méretére vonatkozó előző eredményünknek.

A következő tétel végtelen sok elemből álló A halmazok sűrűségét vizsgálja. Ehhez legyen A(x) = |{a : a ∈ A, a ≤ x}|.

5.5. Tétel. Ha A ⊆ ℕ halmazra teljesül, hogy a, a′ ∈ A, a ≠ a′ esetén a + a′ ∈ V, akkor

lim inf_{x→+∞} \frac{A(x)}{log x} ≤ 4.

Megint indirekten bizonyítunk. Tegyük fel, hogy

lim inf_{x→+∞} \frac{A(x)}{log x} > 4.  (5.9)

Ekkor A végtelen sok elemből áll. Tehát létezik tetszőlegesen nagy x, amelyre A ∩ (x/2, x] ≠ ∅. Vagyis van egy \overline{a} ∈ A, amelyre \frac{x}{2} < \overline{a} ≤ x. Ha x elég nagy, akkor (5.9) szerint

A(x^{1/2}) > 4 log x^{1/2} = 2 log x.

Minden a ∈ A esetén létezik y ∈ ℕ, ℓ = ℓ(a) ∈ ℕ, ℓ ≥ 2 melyre a + \overline{a} = y^{ℓ}. Ekkor:

2^{ℓ} ≤ y^{ℓ} = a + \overline{a} ≤ 2x

ahonnan, nagy x-re:

ℓ ≤ \frac{log x}{log 2} + 1 < 2 log x.

A skatulya elv szerint létezik a_{1}, a_{2} ∈ A, a_{1} < a_{2} ≤ x^{1/2}, melyre ℓ(a_{1}) = ℓ(a_{2}) = ℓ. Vagyis létezik u és v egész, hogy

a_{1} + \overline{a} = u^{ℓ},
a_{2} + \overline{a} = v^{ℓ}.

Ekkor

v^{ℓ} − u^{ℓ} = a_{2} − a_{1} < a_{2} ≤ x^{1/2}.  (5.10)

Másrészt

v^{ℓ} − u^{ℓ} ≥ (u + 1)^{ℓ} − u^{ℓ} ≥ ℓu^{ℓ−1} ≥ ℓ(u^{ℓ})^{1/2} > ℓ\overline{a}^{1/2} > ℓ (\frac{x}{2})^{1/2} > x^{1/2}.

Ez ellentmond (5.10)-nek. Tehát a tétel állítás igaz. Alsó becslésként a következőt igazoljuk:

5.6. Tétel. N ≥ 3 esetén létezik olyan A ⊆ {1, 2, …, N} halmaz, melyre A + A ⊆ V és

|A| ≥ [\frac{log log N}{12 log log log N} ] .

Legyen A = \{x, 2x, 3x, …, nx\}, ahol n = [\frac{log log N}{12 log log log N} ]. x értékét később adjuk meg. Ekkor A + A = {2x, 3x, …, 2nx}. Jelölje az i-edik prímszámot p_{i}, és legyen ℓ az a lehető legnagyobb egész szám, amelyre

p_{ℓ} ≤ 2n.

1 ≤ t ≤ 2n − 1 esetén t + 1 prímtényezős felbontása legyen a következő:

t + 1 = p_{1}^{β_{1,t}}p_{2}^{β_{2,t}} … p_{ℓ}^{β_{ℓ,t}}.

A továbbiakban x értékét is p_{1}^{α_{1}}p_{2}^{α_{2}} … p_{ℓ}^{α_{ℓ}} alakban keressük. Ekkor (t + 1)x akkor és csak akkor p_{t}-edik hatvány minden 1 ≤ t ≤ 2n − 1-re, ha

α_{i} + β_{i,t} ≡ 0 mod p_{t} 1 ≤ i ≤ ℓ, 1 ≤ t ≤ 2n − 1 esetén.  (5.11)

A kínai maradéktétel szerint (5.11)-nek létezik megoldása (α_{1}, α_{2}, …, α_{ℓ})- ben, sőt ez a megoldás egyértelmű modulo p_{1}p_{2} … p_{2n−1}. Ezért feltehetjük α_{1}, α_{2}, …, α_{ℓ} eleget tesz (5.11)-nek, és

0 ≤ α_{i} ≤ p_{1}p_{2} … p_{2n−1} ha 1 ≤ i ≤ ℓ.

Vagyis ekkor A + A minden eleme hatványszám. Továbbá:

0 ≤ α_{i} ≤ p_{1}p_{2} … p_{2n−1} ≤ 4^{p_{2n−1}} < e^{11n log n},
nx = np_{1}^{α_{1}}p_{2}^{α_{2}} … p_{ℓ}^{α_{ℓ}} < n(p_{1}p_{2} … p_{ℓ})^{e^{11n log n}} <
< n4^{p_{ℓ}e^{11n log n}} < n4^{2ne^{11n log n}} < e^{e^{12n log n}} < N.

Így A = {x, 2x, …, nx} ⊆ {1, 2, …, N} is teljesül, ezzel a tétel állítását beláttuk.

Ezután rátérünk a hatványteli számok esetére. Ekkor is megadható akármilyen nagy halmaz a kivánt tulajdonsággal.

5.7. Tétel. Létezik N_{1} konstans, hogy N > N_{1} esetén van olyan A ⊆ {1, 2, …, N} halmaz, melyre A + A ⊆ W és

|A| > \frac{1}{5} log N.

Legyen P_{x} = ∏_{\begin{matrix}p≤x \\ p prím \end{matrix}} p. Jelölje x azt a legnagyobb pozitív egészet, amelyre

\frac{1}{2}xP_{x}^{2} ≤ N. Könnyen ellenőrizhető, hogy az

A = \{iP_{x}^{2} : 1 ≤ i ≤ \frac{x}{2}, i ∈ ℕ\}

halmaz eleget tesz a tétel feltételeinek.

A + A ⊆ W esetén csak triviális felső becsléseket tudunk adni az A halmaz méretére. Ezért inkább a kérdés részhalmaz összegekre vonatkozó analogonját vizsgáljuk. Jelölje F (N) az olyan A halmazok elemszámának maximumát, amelyre A ⊆ {1, 2, …, N}, P (A) ⊆ W.

5.8. Tétel. Létezik c_{4}, c_{5} > 0 konstansok, hogy ha N ≥ 4 egész, akkor

c_{4}(log N)^{1/2} < F (N) < c_{5}(log N)^{3}(log log N)^{−1/2}.

Az alsó becslés bizonyítása hasonló mint az előző tételé. P_{x}-t ugyanúgy definiáljuk, ahogyan ott. Jelölje ezúttal azonban x azt a legnagyobb egészet, amelyre x^{1/2}P_{x}^{2} ≤ N. Ekkor az A = {iP_{x}^{2} : 1 ≤ i ≤ x^{1/2}, i ∈ ℕ} halmaz elemszáma nagyobb mint c_{4} (log N)^{1/2}, és P(A) ⊆ W.

A következő lemmát Sárközy András bizonyította [30]-ben. (Megjegyzem, hogy [30]-ben c_{6}, c_{7}, c_{8}, c_{9} konstansok értéke számszerűen volt megadva, nekünk azonban a pontos értékekre nincs szükségünk.)

5.9. Lemma. Ha N pozitív egész, A ⊂ {1, 2, …, N} és

|A| > c_{6}(N log N)^{1/2},  (5.12)

akkor léteznek d, y, z pozitív egészek, melyekre

d < c_{7}N|A|^{−1}, z > c_{8}|A|^{2}, y < c_{9}Nz|A|^{−2},

továbbá

{yd, (y + 1)d, …, zd} ⊂ P(A).

Az 5.9. lemmából levezetjük a következőt:

5.10. Lemma. Létezik c_{10} > 0 konstans, hogy ha p elegendően nagy prím, B ⊂ \{1, …, p^{2} − 1\}, |B| > c_{10}p(log p)^{\frac{1}{2}} , akkor van egy s = ∑_{b∈B} ε_{b}b ∈ P(B), melyre p | s, p^{2} ∤ s.

Ha c_{10} konstans elég nagy, akkor N = p^{2}, A = B helyettesítéssel alkalmazható az 5.9. lemma. Eszerint létezik d, z, y, melyre

d < c_{7}p^{2}|B|^{−1} < c_{11}p(log p)^{− \frac{1}{2}} ,
z > c_{8}|B|^{2} > c_{12}p^{2} log p,  (5.13)
y < c_{9}p^{2}z|B|^{−2} < c_{13}z(log p)^{−1},

és

{yd, (y + 1)d …, zd} ⊂ P(B).  (5.14)

Ha p prím nagy, akkor (5.13) miatt (d, p) = 1. Tekintsük az yd, (y+1)d, (y+ 2)d, … számtani sorozatban az első két p-vel osztható elemet. (d, p) = 1, tehát ezek közül valamelyikre, mondjuk ud-re teljesül

p | ud, p^{2} ∤ ud.

Nyilvánvaló, hogy y ≤ u ≤ u + 2p. (5.13)-ből következik:

z − y > z − c_{13}z(log p)^{−1} > \frac{z}{2} > c_{14}p^{2} log p.

Összefoglalva

y ≤ u ≤ y + 2p < y + c_{14}p^{2} log p < z.

Így ud ∈ P(A), és ezzel a lemmát beláttuk.

Az 5.10. lemma segítségével befejezhetjük az 5.8. tétel bizonyítását. Tegyük fel, hogy A ⊆ {1, 2, …, N} és P(A) minden eleme hatványteli szám. P_{x} = ∏_{p≤x, p prím} p továbbra is, de most x azt a legkisebb pozitív egészet jelöli, amelyre P_{x}^{2} > N. A prímszámtétel miatt

x = (\frac{1}{2} + o(1)) log N.  (5.15)

Minden p ≤ x prímre, legyen

A_{p} = {a : a ∈ A, p^{2} ∤ a}.  (5.16)

A = ⋃_{p≤x, p prím} A_{p}, hiszen az ellenkező esetben, létezik a ∈ A, hogy a ∉ A_{p} minden p ≤ x prímre. Ekkor A_{p} definiciója miatt p^{2} | a is teljesül minden p ≤ x prímre. Tehát P_{x}^{2} | a, ahonnan N < P_{x}^{2} ≤ a, ami ellentmond a ∈ A ⊆ {1, 2, …, N}-nek.

Ezután A_{p} méretét becsüljük. Fix p ≤ x prímre, r(n) jelölje n-nek a legkisebb nem negatív maradékát modulo p^{2}.

r(n) ≡ n mod p^{2}, 0 ≤ r(n) < p^{2}.

Legyen

B = {b : ∃ a ∈ A_{p}, melyre r(a) = b}.

(5.10) miatt 0 ∉ B.

Tegyük fel, hogy van egy s = b_{1} + ⋯ + b_{t} ∈ P(B) ( ahol b_{1}, …, b_{t} ∈ B, b_{1} < b_{2} < ⋯ < b_{t}), amelyre p | s, p^{2} ∤ s. B deiniciója miatt létezik a_{1}, …, a_{t} ∈ A, ahol

r(a_{1}) = b_{1}, …, r(a_{t}) = b_{t}.

Innen a_{1} + ⋯ + a_{t} ≡ b_{1} + ⋯ + b_{t} ≡ s mod p^{2}, és ezért

p | a_{1} + ⋯ + a_{t}, p^{2} ∤ a_{1} + ⋯ + a_{t}.

Tehát a_{1} + ⋯ + a_{t} nem lehet hatványteli szám. Ezzel ellentmondásra jutottunk, vagyis s ∈ P(B) esetén, ha p prím és p | s, akkor p^{2} | s.

Az 5.10. lemma miatt

|B| ≤ c_{10}p(log p)^{1/2}.  (5.17)

Másrészt bebizonyítjuk, hogy minden b ∈ B esetén

|{a : a ∈ A_{p}, a ≡ b (mod p^{2})}| < p.  (5.18)

Valóban, az ellenkező esetben létezik:

a_{1} ≡ ⋯ ≡ a_{p} ≡ b mod p^{2},

ahol a_{1}, …, a_{p} ∈ A, a_{1} < ⋯ < a_{p}. Ekkor a_{1} + ⋯ + a_{p} ≡ pb mod p^{2}. Így:

p | a_{1} + ⋯ + a_{p} de p^{2} ∤ a_{1} + ⋯ + a_{p}.

Tehát a_{1} + ⋯ + a_{p} nem hatványteli szám, ami ellenmond P(A) ⊆ W -nek. (5.17) és (5.18) szerint:

\begin{aligned}|A_{p}| & = ∑_{b∈B} |\{a : a ∈ A_{p}, a ≡ b (mod p^{2})\}| \\ & < ∑_{b∈B} p = |B|p ≤ c_{10}p^{2}(log p)^{1/2}. \end{aligned}

Mivel, A = ⋃_{p≤x, p prím} A_{p}, ezért (5.15) alapján:

|A| ≤ ∑_{p≤x} |A_{p}| ≤ c_{10} ∑_{p≤x} p^{2}(log p)^{1/2}
< c_{11}(log N)^{3}(log log N)^{−1/2}.

Ezzel beláttuk az 5.8. tételt.

6. Hatványszámok multiplikatív struktúrák-

ban

Az előző fejezetben, akkor becsültük az A halmaz méretét, ha a, a′ ∈ A, a ≠ a′ esetén a + a′ hatványszám. Most ennek a multiplikatív analogonját vizsgáljuk, azt az esetet, amikor A·A+1 halmaz minden eleme hatványszám. Ehhez V_{K} és V halmazokat ugyanúgy definiáljuk, ahogyan az 5. fejezetben.

6.1. Tétel. Létezik N_{0} konstans, hogy ha N > N_{0}, K ≥ 2 egész, A ⊆ {1, …, N} és A · A + 1 ⊆ V_{K}, akkor

|A| < 160\frac{K^{2}}{(log K)^{2}} log log N.

A tétel bizonyítása két gráfelméleti lemmán alapul. A Turán tétel [33] egyszerű következménye az alábbi.

6.2. Lemma. Tegyük fel, hogy r ≥ 2 egész, és G egyszerű gráfnak n szögpontja és m éle van. Ha

m > \frac{r − 2}{2(r − 1)}n^{2},

akkor G tartalmaz r szögpontú teljes gráfot.

P. Kővári, V. Sós, P. Turán [22]-tól származik az következő lemma.

6.3. Lemma. Tegyük fel, hogy a G egyszerű gráfnak n szögpontja és m éle van. Ha

m > \frac{1}{2} (n^{\frac{3}{2}} + n − n^{\frac{1}{2}} ) ,

akkor G tartalmaz K_{r,r}-t.

A tétel bizonyításához, az állítással ellentétben, tegyük fel, hogy

|A| ≥ 160\frac{K^{2}}{(log K)^{2}} log log N.

Mivel M = 1+ \frac{1}{log 2} log (log N/ log 2) esetén N < 2^{2^{M+1}}, ezért ha N elég nagy, létezik 1 ≤ m ≤ 1 + \frac{1}{log 2} log (log N/ log 2) = M egész, amelyre

|A ∩ \{2^{2^{m}}, 2^{2^{m}} + 1, …, 2^{2^{m+1}} − 1\}| > 110\frac{K^{2}}{(log K)^{2}} .

Legyen a fenti A ∩ {2^{2^{m}}, 2^{2^{m}} + 1, …, 2^{2^{m+1}} − 1} halmaz A_{m}, és G teljes gráfnak a szögpontjai A_{m} elemei. Ekkor n = V (G) > 110\frac{K^{2}}{(log K)^{2}} . Ezután G gráf minden élét megszínezzük a c_{2}, c_{3}, …, c_{K} színek valamelyikével a következő módon: az a, a′ ∈ V (G) között futó él színe c_{ℓ}, ahol ℓ az a legkisebb pozitív egész, amelyre aa′ + 1 ℓ-edik hatvány. Ekkor persze ℓ prím. Jelölje 2 ≤ i ≤ K esetén b_{i} a c_{i} színű élek számát G-ben.

Ha b_{2} > \frac{7}{16}n^{2}, akkor a 6.2. lemma szerint G gráfban van 9 szögpont, hogy közöttük minden él színe c_{2}, azaz létezik 9 szám, hogy bármely kettő szorzatához 1-et adva mindig négyzetszámot kapunk. Dujella [4]-ben bebizonyította, hogy nem létezik 9 szám a fenti tulajdonsággal. Tehát b_{2} ≤ \frac{7}{16}n^{2}. Ebből

b_{3} + ⋯ + b_{K} ≥ \binom{n}{2} − \frac{7}{16}n^{2} = \frac{n^{2}}{16} − \frac{n}{2}.

Rosser és Schoenfeld [27] bebizonyította, hogy π(K) ≤ \frac{5K}{4 log K}. Vagyis a skatulya elv miatt van 3 ≤ p ≤ K prím, hogy

b_{p} ≥ \frac{4 log k}{5k} (\frac{n^{2}}{16} − \frac{n}{2}) .

Legyen G_{p} szögpontjai G-nek szögpontjai, és G_{p} élei G-nek c_{p} színű élei. Mivel n > 110\frac{K^{2}}{(log K)^{2}} , ezért

\frac{4 log K}{5k} (\frac{n^{2}}{16} − \frac{n}{2}) = n^{\frac{3}{2}} \frac{log K}{K} \frac{n^{\frac{1}{2}}}{20} (1 − \frac{8}{n}) >

> n^{\frac{3}{2}} \frac{\sqrt{110}}{20} (1 − \frac{8}{110} (\frac{log 3}{3})^{2}) > 0.519n^{\frac{3}{2}} .

Viszont

\frac{1}{2} (n^{\frac{3}{2}} + n − n^{\frac{1}{2}} ) < \frac{1}{2}n^{\frac{3}{2}} (1 + \frac{1}{\sqrt{n}}) < \frac{1}{2}n^{\frac{3}{2}} (1 + \frac{1}{\sqrt{110}} \frac{log 3}{3}) < 0.518n^{\frac{3}{2}} .

Tehát:

b_{p} > \frac{4 log K}{5K} (\frac{n^{2}}{16} − \frac{n}{2}) .

Vagyis 6.3. lemma szerint G_{p}-ben van K_{2,2}. Azaz létezik x < y, c < d, melyre x, y, c, d ∈ V (G_{p}), és xc + 1, xd + 1, yc + 1, yd + 1 számok mindegyike p-edik hatvány. Az 1.2. lemma szerint

yd > (xc)^{p−1} ≥ (xc)^{2} .

De x, y, c, d ∈ {2^{2^{m}}, 2^{2^{m}} + 1, …, 2^{2^{m+1}} − 1}, ahonnan

yd < (2^{2^{m+1}} − 1)^{2} < 2^{2^{m+2}} ≤ (xc)^{2}.

Ezzel ellentmondásra juttotunk. Tehát a tétel állítása igaz.

V_{K} helyett V -t írva a 6.1. tételben, a következőt tudjuk igazolni.

6.4. Tétel. Létezik N_{0} konstans, hogy ha N > N_{0}, pozitív egész, A ⊆ {1, …, N} és A · A + 1 ⊆ V_{K}, akkor

|A| < 1340\frac{(log N)^{2}}{log log N} .

Valóban, legyen K_{0} a lehető legkisebb pozitív egész, amelyre N^{2}+1 ≤ 2^{K_{0}}. Ekkor 2^{K_{0}−1} < N^{2} + 1, tehát K_{0} < 1 + \frac{1}{log 2} log(N^{2} + 1). Mivel a, a′ ∈ A, a ≠ a′ esetén aa′ + 1 ≤ N^{2} + 1, ezért aa′ + 1 legfeljebb K_{0}-adik hatvány. A 6.1. tételt alkalmazva megkapjuk a tétel állítását.

Szeretném megköszönni Sárközy András Tanár Úrnak a szép témát és a dolgozat megírásához nyújtott segítségét.

Hivatkozások

[1] J. Arkin, V. E. Hogatt, E. G. Straus,On Euler’s solution of a problem of Diophantus, Fibonacci Quart 17 (1979), 333-339.

[2] E. R. Canfield, P. Erdős, C. Pomarence, On a problem of Oppenheim concerning "Factorisatio Numerorum", J. Number Theory 17 (1983), 1-28.

[3] H. Davenport, Multiplicative Number Theory, Markham Publishing Co., Chicago, first ed., 1967.

[4] A. Dujella, An absolute bound for the size of Diophantine m-tuples, J. Number Theory, publikálás alatt.

[5] A. Dujella, On Diophantine quintuples, Acta Arithmetica 81 (1997), 69-79.

[6] A. Dujella, On the size of Diophantine m-tuples, Math. Proc. Cambridge Philos. Soc., publikálás alatt.

[7] P. Erdős, Quelques problems de la theorie des nombres, Monographie de l’enseignement mathematique, Geneve, (1963), 81-135.

[8] P. Erdős, A. Sárközy, On divisibility properties of integers of the form a+a’, Acta Math. Hung. 50 (1987), 117-122

[9] P. Erdős, N. H. Shapiro, On the least primitive root of a prime, Pacific J. Math. 7 (1957), 861-865.

[10] P. Erdős, C. L. Stewart, R. Tijdeman, Some diophantine equations with many solutions, Composito Mathematica 66 (1988), 37-48.

[11] P. Erdős, J. Surányi, Válogatott fejezetek a számelméletből, Polygon, Szeged, 1996, 215-217.

[12] P. Erdős, P. Turán, On a problem in the elementary theory of numbers, Amer. Math. Monthly 41 (1934), 608-611.

[13] P. Gibbs, Some rational Diophantine sixtuples, publikálás alatt.

[14] R.L. Graham, B.L. Rothschild, J.H. Spencer, Ramsey Theory, Wiley 1980, 75.

[15] K. Gyarmati, On a problem of Diophantus, Acta Arithmetica 97 (2001), 53-65.

[16] K. Gyarmati, On divisibility properties of integers of the form ab+1, Period. Math. Hungar. 43 (2001), 71-79.

[17] K. Gyarmati, A. Sárközy, C. L. Stewart, On sums which are powers, Acta Math. Hungar., publikálás alatt [18] K. Gyarmati, A. Sárközy, C. L. Stewart, On shifted products which are

powers, Mathematika, publikálás alatt.

[19] K. Győry, C. L. Stewart, R. Tijdeman, On prime factors of sums of integers, I., Composito Math. 59 (1986), 81-88.

[20] K. Győry, A. Sárközy, C. L. Stewart, On the number of prime factors of integers of form ab+1, Acta Arithmetica 74 (1996), 365-385.

[21] K. Ireland, M. Rosen A Classical Introduction to Modern Number Theory, Springer-Verlag, 1980.

[22] P. Kővári, V. Sós and P. Turán, On a problem of K. Zarankiewicz, Colloq.Math. 3 (1954), 50-57.

[23] J. Lagrange, Six entiers dont les sommes deux à deux sont des carrés, Acta Arithmetica 40 (1981), 91-96.

[24] L. Lovász Combinatorical Problems and Exercises, Akadémiai Kiadó Budapest, 1979, 10. fejezet, 37. feladat.

[25] J.-L. Nicolas, Six nombres dont les sommes deux à deux sont des carrés, Calculeteur en Math (1975), Limoges, Bull. Soc. Math. France 49-50 (1977), 141-143.

[26] J. Rivat, A. Sárközy, C.L.Stewart, Two problems on sum sets, Illinois J. Math., publikálás alatt.

[27] J. B. Rosser, L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. (1962), 64-94.

[28] A. Sárközy, On difference sets of sequences of integers II., Annales Univ. Budapest Eötvös 21 (1978), 41-53.

[29] G. N. Sárközy, On a problem of Erdős, Acta Math. Hung. 60 (1992), 271-282.

[30] A. Sárközy, Finite addition theorems, II., J. Number Theory 48 (1994), 197-218.

[31] W.M. Schmidt, Equations over Finite Fields an Elementary Approach, Lecture Notes in Mathematics, Vol. 536., Sringer-Verlag, 1976.

[32] W. Sierpienski, A Solution of Problems in the Theory of Numbers, Pergamon Press. Warszawa, first ed., 1964.

[33] P. Turán, On the theory of graphs, Coll. Math. 3 (1953) 19-30.

[34] I.M. Vinogradov, A számelmélet alapjai, Tankönyvkiadó, Budapest, 1952, 5. fejezet, 8. feladat.

[35] S. Wigert, Sur l’ordre de grandeur du nombre de diviseurs d’un entier, Arkiv für Mathematik 3 (1906/1907), 1-9.