Kezdőlap


Cím:	Körök és multiplikatív Sidon-sorozatok
Szerző(k):	Pach Péter Pál
Füzet:	2014/december, 514 - 519. oldal	PDF \| MathML

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

Ebben a cikkben egy számelméleti kérdést, az ún. multiplikatív Sidon-sorozatok maximális elemszámát fogjuk vizsgálni. A matematikában sokszor előfordul, hogy valamely terület eredményeit egy attól látszólag távol álló területen is felhasználják. A multiplikatív Sidon-sorozatokkal kapcsolatos problémák is ilyenek, ugyanis ezek vizsgálatában bizonyos gráfelméleti eredmények is jelentős szerepet kapnak.
Egy pozitív egész számokból álló $A$ halmazt akkor hívunk multiplikatív Sidon-sorozatnak (továbbiakban röviden: Sidon-sorozatnak), ha az

\begin{matrix} a b = c d \end{matrix}

(1)

egyenletnek csak triviális megoldása van

A

-ban, vagyis

a, b, c, d \in A

esetén csak akkor teljesülhet az (1) egyenlet, ha

{a, b} = {c, d}

. Azt szeretnénk meghatározni, hogy az első

n

pozitív egész szám közül legfeljebb hányat lehet úgy kiválasztani, hogy azok Sidon-sorozatot alkossanak. Ezt a maximális elemszámot jelölje

F (n)

. Könnyű észrevenni, hogy a prímek Sidon-sorozatot alkotnak, ugyanis, ha

a

b

c

d

(pozitív) prímszámok, és

a b = c d

, akkor a számelmélet alaptétele miatt valóban

{a, b} = {c, d}

. A prímek számát

n

-ig

π (n)

-nel jelöljük, és a prímszámtétel szerint

π (n) \sim \frac{n}{ln n}

¹. Tehát

F (n) \geq π (n)

minden

n

-re teljesül. A kérdés az, hogy lehet-e ennél több számot is kiválasztani, és ha igen, akkor mennyivel.
A következő ötlet segítségével adhatunk felső becslést a Sidon-sorozatok elemszámára: az

A = {a_{1}, a_{2}, ..., a_{k}} \subseteq {1,2, ..., n}

halmaz minden

a_{i}

elemét írjuk fel ,,ügyesen'' két pozitív egész szám szorzataként:

a_{i} = u_{i} v_{i}

. Ezután tekintsük azt a

G

gráfot, amelynek csúcsai

1,2, ..., n

, és minden

1 \leq i \leq k

-ra kössük össze az

u_{i}

és

v_{i}

csúcsokat; ily módon egy

k

élű gráfot kapunk. Megmutatjuk, hogy ha

A

Sidon-sorozat, akkor

G

-ben nem lehet 4 hosszúságú kör. Ha ugyanis

x_{1} x_{2} x_{3} x_{4}

egy 4 hosszú kör lenne

G

-ben, akkor mivel

(x_{1}, x_{2})

(x_{2}, x_{3})

(x_{3}, x_{4})

(x_{4}, x_{1})

élek

G

-ben, ezért az

x_{1} x_{2}

x_{2} x_{3}

x_{3} x_{4}

x_{4} x_{1}

szorzatok különböző elemei lennének

A

-nak. (Azért különbözők, mert minden

A

-beli számhoz csak egyetlen

G

-beli élet húztunk be.) Ekkor azonban

a = x_{1} x_{2}

b = x_{3} x_{4}

c = x_{2} x_{3}

d = x_{4} x_{1}

nemtriviális megoldása lenne az (1) egyenletnek. Vagyis a kapott

G

gráfra mindenképpen teljesül, hogy nem tartalmaz

4

hosszúságú kört. Persze

G

-nek ettől még lehet sok éle, például, ha minden

a_{i}

számot

a_{i} = 1 \cdot a_{i}

alakban írunk fel, azaz például

u_{i} = 1

v_{i} = a_{i}

(minden

1 \leq i \leq k

esetén), akkor egy csillagot kapunk: minden csúcs az 1-gyel van összekötve (

1 \in A

esetén van egy hurokél is), ami nem tartalmaz 4 hosszú kört, viszont egy ilyen csillagnak

n

éle is lehet (az 1-hez tartozó hurokéllel együtt), és így csak a magától értetődő

F (n) \leq n

becslést kapnánk. A cél tehát az, hogy a számokat oly módon írjuk fel szorzat alakban, hogy annak segítségével jó becslést kapjunk. Az ehhez szükséges ötlet Erdőstől származik, és a következő állításra épül:

1. állítás. Minden

a \leq n

pozitív egész szám felírható

u v

alakban, ahol

v \leq u \leq n^{2 / 3}

, vagy

u > n^{2 / 3}

prímszám.

Ez az állítás könnyen igazolható, a logaritmusokra áttérve levezethető a KöMaL 2012. májusi számában kitűzött B. 4455. számú feladatának állításából, ami a következő volt: Véges sok pozitív szám közül egyik sem nagyobb a többi összegénél. Igazoljuk, hogy két részre oszthatjuk őket úgy, hogy bármelyik részben a számok összege legfeljebb kétszer akkora, mint a másikban. Az állításból az derül ki, hogy minden számot fel tudunk írni két ,,nem túl nagy'' ‐ precízebben

n^{2 / 3}

-nál nem nagyobb ‐ szám szorzataként, kivéve, ha van egy ,,túl nagy'' ‐ precízebben:

n^{2 / 3}

-nál nagyobb ‐ prímosztója, amikor is ez nyilvánvalóan nem lehetséges, hiszen a szorzat két tényezője közül az egyiknek tartalmaznia kell ezt a már önmagában is

n^{2 / 3}

-nál nagyobb prímtényezőt.
Az ,,ügyes'' szorzattá alakítás mellett szükségünk lesz 4 hosszú kört nem tartalmazó gráfok élszámára vonatkozó becslésekre, most az előkészületeket folytatva ilyen típusú állításokat fogunk kimondani és bizonyítani.

2. állítás. Ha a

G

egyszerű gráfnak

n

csúcsa van és nem tartalmaz

4

hosszú kört, akkor az éleinek száma legfeljebb

\frac{n}{4} (1 + \sqrt[]{4 n - 3})

Bizonyítás. Számoljuk meg, hogy a gráfban hány ,,cseresznye'' van, vagyis hány olyan részgráfot tartalmaz, amelynek csúcsai

a

b

c

és

a

össze van kötve

b

-vel és

c

-vel is. (A háromszögeket mindhárom csúcsuknál számolni fogjuk cseresznyeként.) Egyrészt, ha

b

-t és

c

-t már kiválasztottuk, akkor

a

csak a két csúcs egy közös szomszédja lehet. Ilyenből legfeljebb egy lehet, hiszen ha

a_{1}

és

a_{2}

is közös szomszéd lenne, akkor

b a_{1} c a_{2}

egy 4 hosszú kört alkotna. Vagyis minden pontpárhoz legfeljebb egy cseresznye tartozhat, és így a cseresznyék száma legfeljebb

(\binom{n}{2})

. Másrészt, a csúcsok fokszámát

d_{1}, d_{2}, ..., d_{n}

-nel jelölve a cseresznyék száma pontosan

(\binom{d_{1}}{2}) + ... + (\binom{d_{n}}{2})

, hiszen ha először a cseresznye középső csúcsát választjuk ki, akkor ezután a szomszédjai közül kell még két különbözőt választanunk. A gráf élszámát

k

-val jelölve és a számtani és négyzetes közepek közötti összefüggést felhasználva:

\begin{matrix} (\binom{n}{2}) & \geq (\binom{d_{1}}{2}) + ... + (\binom{d_{n}}{2}) = \frac{1}{2} (d_{1}^{2} + ... + d_{n}^{2}) - \frac{1}{2} (d_{1} + ... + d_{n}) \geq \\ \geq \frac{1}{2} \frac{{(d_{1} + ... + d_{n})}^{2}}{n} - \frac{1}{2} (d_{1} + ... + d_{n}) = \frac{2 k^{2}}{n} - k . \end{matrix}

Tehát

\frac{2 k^{2}}{n} - k \leq (\binom{n}{2})

, amiből már következik az állítás, hiszen a

\frac{2 k^{2}}{n} - k - (\binom{n}{2})

(

k

-ban) másodfokú polinom nagyobbik gyöke éppen

\frac{n}{4} (1 + \sqrt[]{4 n - 3})

□

Olyan becslésekre is szükségünk lesz, amikor a 4 hosszú kört nem tartalmazó gráfról tudjuk, hogy páros, és ismerjük a két független csúcsosztályának elemszámát:

3. állítás. Ha a

G

páros egyszerű gráf két független csúcsosztályának mérete

s

, illetve

t

, és

G

nem tartalmaz

4

hosszú kört, akkor éleinek száma legfeljebb

\begin{matrix} \frac{t + \sqrt[]{t^{2} + 4 t (s^{2} - s)}}{2} . \end{matrix}

Bizonyítás. Számoljuk meg, hogy hány olyan cseresznye van a gráfban, amelynek ,,középső'' csúcsa a

t

csúcsot tartalmazó csúcsosztályba esik. A

t

csúcsot tartalmazó csúcsosztályban a fokszámok legyenek rendre

d_{1}, d_{2}, ..., d_{t}

, ekkor a kérdéses cseresznyék száma

(\binom{d_{1}}{2}) + ... + (\binom{d_{t}}{2})

. Ugyanakkor ez legfeljebb

(\binom{s}{2})

lehet, hiszen a másik csúcsosztály bármely két csúcsát kiválasztva azoknak legfeljebb egy közös szomszédja lehet, hiszen a gráf nem tartalmaz 4 hosszú kört. Az előző állítás bizonyításához hasonlóan a számtani és négyzetes közepek közötti összefüggésből (az élek számát most is

k

-val jelölve) a következő becslés adódik:

\begin{matrix} (\binom{s}{2}) \geq (\binom{d_{1}}{2}) + ... + (\binom{d_{t}}{2}) \geq \frac{k^{2}}{2 t} - \frac{k}{2}, \end{matrix}

és így

\begin{matrix} \frac{k^{2}}{2 t} - \frac{k}{2} \leq (\binom{s}{2}), \end{matrix}

amiből már következik az állítás.

□

A könnyebb felhasználás érdekében ennek a becslésnek megfogalmazzuk két következményét:

4. következmény. Ha a

G

páros egyszerű gráf két független csúcsosztályának mérete

s

, illetve

t

, melyekre

s \leq t

és

G

nem tartalmaz

4

hosszú kört, akkor éleinek száma legfeljebb

i)

t + s^{2}

i i)

2 \sqrt[]{t} s

, ha

t \leq s^{2}

Mindkét állítás egyszerűen levezethető az előző becslésből. Amikor

t

,,lényegesen nagyobb'', mint

s^{2}

, akkor

i)

ad erősebb becslést, amikor pedig

t

,,lényegesen kisebb'', mint

s^{2}

, akkor

i i)

.
Most már készen állunk a következő tétel bizonyítására Sidon-sorozatok elemszámáról:

5. tétel. Ha

A \subseteq {1,2, ..., n}

multiplikatív Sidon-sorozat, akkor

| A | \leq π (n) + 11 n^{3 / 4}

Bizonyítás. Tegyük fel, hogy az

A = {a_{1}, a_{2}, ..., a_{k}} \subseteq {1,2, ..., n}

halmazon belül az

a b = c d

egyenletnek nincsen páronként különböző számokból álló megoldása. Minden

a_{i}

számot írjunk fel

a_{i} = u_{i} v_{i}

alakban az 1. állításnak megfelelően, azaz úgy, hogy

u_{i}

-re és

v_{i}

-re minden

1 \leq i \leq k

esetén a következő két lehetőség valamelyike teljesüljön:

i)

v_{i} \leq u_{i} \leq n^{2 / 3}

i i)

n^{2 / 3} < u_{i}

prímszám.
Tekintsük azt a

G

gráfot, mely csúcshalmaza

{1,2, ..., n}

és élei

(u_{i}, v_{i})

(ahol

1 \leq i \leq k

A

-ban legfeljebb

\sqrt[]{n}

darab négyzetszám lehet, így a gráfban legfeljebb

\sqrt[]{n}

hurokél keletkezhet. Mivel

\sqrt[]{n}

a becslés

n^{2 / 3}

-os ,,hibatagjához'' képest elhanyagolható, ezért feltehetjük, hogy

G

-ben nincs hurokél. A

G

gráf éleit osszuk

K + 2

csoportba (

K

értékét később választjuk meg): először is,

G_{0}

legyen az a részgráf, amelyet a

\sqrt[]{n}

-nél nem nagyobb csúcsok feszítenek, vagyis a

G_{0}

-ban szereplő

(u_{i}, v_{i})

élek mindkét végpontja legfeljebb

\sqrt[]{n}

. Ezután, ha

1 \leq h \leq K

, akkor

G_{h}

legyen az a gráf, amelyben szereplő élek egyik végpontja az

(n^{\frac{1}{2} + \frac{h - 1}{6 K}}, n^{\frac{1}{2} + \frac{h}{6 K}}]

intervallumba esik. (Azokat a csúcsokat, amelyekből

G_{h}

-ban nem indul él, elhagyjuk a

G_{h}

gráfból.) Mivel

G

-ben csak olyan élek szerepelhetnek, ahol a két végpont szorzata legfeljebb

n

, ezért ekkor a másik végpont biztosan az

[1, n^{\frac{1}{2} - \frac{h - 1}{6 K}})

intervallumba esik. Ez azt is jelenti, hogy

G_{h}

egy olyan páros gráf, amelynek két független csúcsosztályának elemszáma felülről becsülhető

n^{\frac{1}{2} + \frac{h}{6 K}}

-val, illetve

n^{\frac{1}{2} - \frac{h - 1}{6 K}}

-val. Végül, a

G

gráfból törölve a

G_{0}, G_{1}, ..., G_{K}

gráfok éleit (és azokat a csúcsokat, melyekből így már nem indul él) csak olyan élek maradnak, amelyek egyik végpontja nagyobb, mint

n^{2 / 3}

. Ez csak úgy lehetséges, ha a

i i)

-es feltétel teljesül rájuk, vagyis az

n^{2 / 3}

-nál nagyobb végpont prímszám. A másik végpont pedig kisebb, mint

n^{1 / 3}

, hiszen a két végpont szorzata legfeljebb

n

lehet. Vagyis a megmaradó élek egy olyan

G_{K + 1}

páros gráfot alkotnak, amelynek két független csúcshalmaza az

(n^{2 / 3}, n]

-be eső prímszámok, illetve az

n^{1 / 3}

-nál nem nagyobb pozitív egészek halmaza.
Jelölje

0 \leq h \leq K + 1

esetén

G_{h}

éleinek számát

k_{h}

, most felső becslést adunk a

k_{h}

értékekre.
Ha

A

multiplikatív Sidon-sorozat, akkor

G

nem tartalmazhat 4 hosszúságú kört, így a

G_{h}

gráfok sem. A

G_{0}

gráf élszámát a 2. állítás segítségével a következő módon becsüljük:

\begin{matrix} k_{0} \leq \frac{\sqrt[]{n}}{4} (1 + \sqrt[]{4 \sqrt[]{n} - 3}) \leq n^{3 / 4} . \end{matrix}

1 \leq h \leq K

, akkor a

G_{h}

páros gráf élszámának becsléséhez a 4. következmény

i i)

-es becslését használjuk:

\begin{matrix} k_{h} \leq 2 n^{\frac{1}{4} + \frac{h}{12 K}} n^{\frac{1}{2} - \frac{h - 1}{6 K}} = 2 n^{3 / 4} n^{\frac{2 - h}{12 K}} . \end{matrix}

Akkor fogjuk ezekből az egyenlőtlenségekből a legjobb becslést kapni, ha

K

-t

K = ⌊ \frac{1}{12} ln n ⌋

-nek választjuk. Most az egyszerűség kedvéért számoljunk úgy, mintha

K = \frac{1}{12} ln n

teljesülne, nem nehéz meggondolni, hogy az ebből adódó hiba elhanyagolható. Mivel

n^{\frac{1}{12 K}} = n^{\frac{1}{ln n}} = e

, ezért

k_{h} \leq 2 n^{3 / 4} n^{\frac{2 - h}{12 K}} = 2 n^{3 / 4} \cdot e^{2 - h}

, és így

\begin{matrix} k_{1} + k_{2} + ... + k_{K} \leq 2 e n^{3 / 4} (1 + \frac{1}{e} + \frac{1}{e^{2}} + ...) = \frac{2 e^{2}}{e - 1} n^{3 / 4} \leq 9 n^{3 / 4}, \end{matrix}

hiszen az

1, \frac{1}{e}, \frac{1}{e^{2}}, ...

mértani sorozat első

K

tagjának összegét az összes tag összegével felülről becsültük.
Végül, a

G_{K + 1}

páros gráf élszámának becsléséhez a 4. következmény

i)

-es becslését használjuk, hiszen most az egyik független csúcsosztály ,,sokkal nagyobb'', mint a másik. A nagyobb független csúcsosztályt az

(n^{2 / 3}, n]

-be eső prímszámok alkotják, a számuk

π (n) - π (n^{2 / 3})

, a kisebbiknek pedig csak

n^{1 / 3}

eleme van, így:

\begin{matrix} k_{K + 1} \leq π (n) - π (n^{2 / 3}) + n^{2 / 3} . \end{matrix}

A kapott becsléseket összeadva

G

élszámára éppen a bizonyítandó felső becslést kapjuk:

\begin{matrix} k_{0} + ... + k_{K + 1} \leq n^{3 / 4} + 9 n^{3 / 4} + π (n) - π (n^{2 / 3}) + n^{2 / 3} \leq π (n) + 11 n^{3 / 4} . \end{matrix}

□

A prímszámok kiválasztásával az eddig kapott legjobb alsó becslésünk

π (n) \leq F (n)

, azonban ezen szintén gráfelméleti eszközöket felhasználva még lehet javítani. Mutatunk egy konstrukciót olyan Sidon-sorozatra, amelynek elemszáma

π (n) + \frac{n^{3 / 4}}{{(ln n)}^{3 / 2}}

. Tegyük fel, hogy

H

egy olyan egyszerű gráf a

\sqrt[]{n}

-nél nem nagyobb prímszámokból álló csúcshalmazon, amely nem tartalmaz 4 hosszúságú kört. Az

A

halmaz elemei legyenek azok az

u v

szorzatok, amelyekre

(u, v)

éle

H

-nak, továbbá a

\sqrt[]{n}

-nél nagyobb prímszámok. Most tegyük fel, hogy

a b = c d

teljesül valamely

a, b, c, d \in A

elemekre. Ekkor

a

b

c

d

mindegyike vagy

\sqrt[]{n}

-nél nagyobb prímszám, vagy két

\sqrt[]{n}

-nél nem nagyobb prímszám szorzata. Ha például

a

prím, akkor

a ∣ c d

miatt

a = c

vagy

a = d

és így

{a, b} = {c, d}

teljesül, vagyis az egyenlet egy

A

-beli nemtriviális megoldásában nem szerepelhet prímszám. Ha

a

kanonikus alakja

a = p q

, akkor feltehető, hogy

p ∣ c

, mondjuk

c = p r

. Ha

r = q

, akkor

a = c

és ismét triviális megoldást kapunk. Ha

r \neq q

, akkor

r ∤ a

, és így

r ∣ b

, mondjuk

b = r s

, és így

d = q s

. Ekkor viszont

p q s r

egy 4 hosszú kör lenne

H

-ban, ami ellentmondás. Tehát a megadott

A

halmaz valóban Sidon-sorozat, a mérete pedig

π (n) - π (\sqrt[]{n}) + k (H)

, ahol

k (H)

H

gráf éleinek számát jelöli. Másrészt, meg lehet mutatni, hogy a 2. állításban szereplő felső becslés konstans szorzótól eltekintve pontos, például igaz az, hogy minden elég nagy

n

-re konstruálható 4 hosszú kört nem tartalmazó

n

csúcsú

\frac{2}{5} n^{3 / 2}

élű gráf. Mivel

\begin{matrix} π (\sqrt[]{n}) \sim \frac{\sqrt[]{n}}{\frac{1}{2} ln n}, \end{matrix}

ezért a

H

gráf élszáma

\begin{matrix} k (H) \sim \frac{2}{5} {(\frac{\sqrt[]{n}}{\frac{1}{2} ln n})}^{3 / 2} \geq \frac{n^{3 / 4}}{{(ln n)}^{3 / 2}} . \end{matrix}

Ebből következik, hogy létezik

π (n) + \frac{n^{3 / 4}}{{(ln n)}^{3 / 2}}

méretű multiplikatív Sidon-sorozat, hiszen

π (\sqrt[]{n})

a ,,hibataghoz'' képest is elhanyagolható. Ezzel igazoltuk a következő tételt:

6. tétel. Léteznek olyan

c_{1}

c_{2}

pozitív konstansok, hogy minden elegendően nagy

n

-re

\begin{matrix} π (n) + c_{1} \frac{n^{3 / 4}}{{(ln n)}^{3 / 2}} \leq F (n) \leq π (n) + c_{2} n^{3 / 4} . \end{matrix}

(

Például

c_{1} = 1

c_{2} = 11

megfelelő konstansok.

)

Ezt a tételt Erdős 1938-ban bizonyította. Az alsó és a felső becslésben nem csak a fő tag egyezik, hanem a ,,hibatagok'' is csak ln-hatvány szorzóban térnek el, azaz a becslés nagyon pontos. Érdekesség, hogy Erdős 31 évvel később a felső becslést

π (n) + c_{2} \frac{n^{3 / 4}}{{(ln n)}^{3 / 2}}

-re javította, így a hibatagok már csak konstans szorzóban térnek el.

Köszönetnyilvánítás. A kutatás a TÁMOP 4.2.4.A/1-11-1-2012-0001 Nemzeti Kiválóság Program című kiemelt projekt keretében zajlott. A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával valósul meg.

¹Ez azt jelenti, hogy

\frac{π (n)}{\frac{n}{ln n}}

tart az 1-hez, ha

n

tart a végtelenhez. A prímszámtétel első bizonyítását Hadamard és de la Vallée Poussin adta 1896-ban.