Sylvester-sorozat

Az 1/2 + 1/3 + 1/7 + 1/43 + ... összeg 1-hez való konvergenciájának ábrázolása. Minden sorban k db négyzet van, 1/k oldalhosszúsággal, melyek területösszege 1/k, az összes négyzet pedig pontosan lefed egy nagyobb, 1 területű négyzetet. Az 1/1807 vagy kisebb oldalhosszúságú négyzetek nem szerepelnek az ábrán

A számelmélet területén a Sylvester-sorozat (vagy Sylvester-féle sorozat) olyan egész számokat tartalmazó sorozat, melynek első tagja a 2, és minden további tag az előző tagok szorzatánál 1-gyel nagyobb szám. Így az első néhány tagja:

2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 Sablon:OEIS.

A Sylvester-sorozatot James Joseph Sylvester brit matematikusról nevezték el, aki 1880-ban elsőként tanulmányozta azt. A sorozat tagjai dupla exponenciális sebességgel nőnek, a reciprokok sorösszege pedig gyorsabban tart 1-hez, mint bármely más egységtört-sorozat. A rekurzív definíció lehetővé teszi a sorozat tagjainak gyorsabb prímtényezőkre bontását a velük azonos nagyságrendű egész számokhoz képest, de a sorozat rendkívül gyors növekedése miatt így is csak az első néhány tagnak ismert a pontos felbontása. A sorozat felhasználható az 1 véges egyiptomitört-felbontásaihoz, a Szaszaki–Einstein-sokaságok (Sablon:Wd, Sablon:Wd) konstruálásához és egyes bonyolultabb online algoritmusokban (olyan algoritmusok, amelyek a bemenetet nem egyszerre kapják meg, hanem több részben, a feldolgozási folyamat közben).

Formális definíciók

A Sylvester-sorozat formális meghatározása:

$s_n=1+\prod _{i=0}^{n-1}{s}_i.$

Az üres szorzat értéke megegyezés szerint 1, ezért s₀ = 2 a sorozat kezdőértéke.

Egy másik rekurzív definíció:

$s_0=2$ és $s_{n+1}=s_n(s_n-1)+1$ (minden $n\ge 0$-ra)

Könnyen megmutatható a két definíció egyenértékűsége (teljes indukcióval).

Zárt alak, aszimptotikus viselkedés

A Sylvester-számok n függvényében dupla exponenciálisan nőnek. Megmutatható, hogy

$s_n=\lfloor E^{2^{n+1}}+\frac{1}{2}\rfloor ,$

egy E számra, ami körülbelül 1,264084735305302. Ez azt jelenti, hogy s₀ az E²-hez legközelebb álló egész szám, s₁ az E⁴-hez legközelebb álló egész szám, s₂ az E⁸-hoz legközelebb álló egész szám stb.

Az előbbi képlet hatásában a következő algoritmussal egyezik meg: bármely s_n-re, vedd E²-et, emeld négyzetre n-szer, majd vedd a hozzá legközelebbi egész számot. Ez viszont csak akkor lehetne praktikus algoritmus, ha az s_n kiszámolásán, majd egymás utáni négyzetgyökvonásokon kívül lenne más módja is E meghatározásának.

A Sylvester-sorozat dupla exponenciális növekedése nem meglepő, ha összehasonlítjuk az $F_n=2^{2^n}+1$ Fermat-számok sorozatával, hiszen a Fermat-számok az előbbi megszokott képlet mellett a Sylvester-sorozathoz hasonló módon is megadhatóak:

$F_n=2+\prod _{i=0}^{n-1}{F}_i.$

Egyiptomi törtekkel való kapcsolatai

A Sylvester-sorozat reciprokai által kapott egységtörtek végtelen sora a következő:

$\sum _{i=0}^{\mathrm{\infty }}\frac{1}{s_i}=\frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{43}+\frac{1}{1807}+\cdots .$

A sor részösszegeinek egyszerű alakja:

$\sum _{i=0}^{j-1}\frac{1}{s_i}=1-\frac{1}{s_j-1}=\frac{s_j-2}{s_j-1},$

ami igazolható indukcióval, vagy akár közvetlen módon – belátva, hogy a rekurzióból következik az

$\frac{1}{s_i-1}-\frac{1}{s_{i+1}-1}=\frac{1}{s_i}$

összefüggés, amivel teleszkopikus összegzést végezve:

$\sum _{i=0}^{j-1}\frac{1}{s_i}=\sum _{i=0}^{j-1}(\frac{1}{s_i-1}-\frac{1}{s_{i+1}-1})=\frac{1}{s_0-1}-\frac{1}{s_j-1}=1-\frac{1}{s_j-1}.$

Mivel a részösszegek ezen $\frac{s_j-2}{s_j-1}$ sorozata 1-hez konvergál, ezért a teljes sor az 1-nek végtelen egyiptomitört-reprezentációját adja:

$1=\frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{43}+\frac{1}{1807}+\cdots .$

Az 1 bármilyen hosszú egyiptomitört-megfeleltetése megkapható a sorozat „levágásával”, majd az utolsó tört nevezőjéből 1 levonásával, például:

$1=\frac{1}{2}+\frac{1}{3}+\frac{1}{6},1=\frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{42},1=\frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{43}+\frac{1}{1806}\text{stb.}$

Ez általánosan így néz ki egy tetszőleges k index esetén: $1=\sum _{i=0}^{k-1}\frac{1}{s_i}+\frac{1}{s_k-1}$.

A végtelen sorozat első k tagjának összege adja a legközelebbi lehetséges alsó becslését 1-nek az összes k-tagú egyiptomi törtes sorozat között. Például az első négy tag összege 1805/1806, ezért bármely (1805/1806, 1) intervallumban lévő egyiptomitört-megfeleltetés legalább 5 elemet igényel.

A Sylvester-sorozat úgy is felfogható, mint egy egyiptomi törteket előállító mohó algoritmus Sablon:Wd, ami minden lépésben kiválasztja a lehető legkisebb nevezőt, amitől a sor részösszege még 1 alatt marad. Más megközelítésben a sorozat első tagjától tekinthető az ½ páratlan mohó felbontásának.

Egyediség és racionális összegű gyorsan növő sorok

Amint azt Sylvester maga is megjegyezte, a Sylvester-sorozat egyedinek tűnik abban a tekintetben, hogy ilyen gyorsan növekvő értékek mellett a reciprokok összege racionális számhoz konvergál. A Sylvester-sorozat példát nyújt arra, hogy önmagában a dupla exponenciális növekedés nem elégséges feltétele a sorozat irracionális voltának.

Ha egy $a_n$ sorozat elég gyorsan nő ahhoz, hogy

$a_n\ge a_{n-1}^2-a_{n-1}+1,$

és a $\sum \frac{1}{a_i}$ sorozat egy A racionális számhoz konvergál, akkor egy bizonyos küszöbindextől kezdődően minden n indexre az $a_n$ sorozatot ugyanazon

$a_n=a_{n-1}^2-a_{n-1}+1$

rekurrencia-szabály kell meghatározza, mint a Sylvester-sorozatot Sablon:Harvtxt.

Sablon:Harvtxt sejtése szerint az ilyen típusú eredményekben a sorozat növekedését korlátozó egyenlőtlenség lecserélhető a következő gyengébb feltételre:

$\underset{n\to \mathrm{\infty }}{\lim }\frac{a_n}{a_{n-1}^2}=1.$

Sablon:Harvtxt vizsgálta a sejtés megoldásának előrehaladását; lásd még Sablon:Harvtxt.

Oszthatóság és prímfelbontások

Ha i < j, a definícióból következik, hogy $s_j\equiv 1(\mathrm{mod}{s}_i)$. Ezért a Sylvester-sorozat bármely két tagja relatív prím. Továbbá a sorozat tagjainak egyetlen prímtényezője sem lehet kongruens 5-tel modulo 6. A sorozat segítségével bebizonyítható, hogy végtelen sok prímszám létezik (hiszen bármely prímszám a sorozat legfeljebb egy tagjának lehet osztója), sőt, sorozat segítségével az is bebizonyítható, hogy végtelen sok olyan prím létezik, ami kongruens 7-tel modulo 12.

A Sylvester-számok faktorizációjával kapcsolatban számos kérdés áll még nyitva. Nem ismert például, hogy minden tag négyzetmentes-e.

Ahogy Sablon:Harvtxt írja, könnyen meghatározható, hogy adott p melyik Sylvester-számnak osztója (ha osztója bármelyiknek): egyszerűen modulo p kell számítani a Sylvester-sorozat rekurrenciáját, amíg olyan számhoz nem érünk, ami kongruens 0-vel (mod p), vagy ismétlődő modulushoz. Ezzel a technikával az első 3 millió prímszám közül 1166 vagy 1167 prímosztóját találta meg a Sylvester-számoknak, melyek közül egyiknek a négyzete sem volt osztója Sylvester-számnak. A Sylvester-számokat osztó prímszámok sűrűsége nulla az összes prímszám között: valóban, az x-nél kisebb ilyen prímek száma $O(\pi (x)/\log \log \log x)$.

A következő táblázat a Sylvester-számok prímtényezős felbontását mutatja be (kivétel az első 4 tag, amik prímek). Konvenció szerint Pn és Cn bizonyos n számjegyű prímszámokat, illetve összetett számokat jelölnek.

n	sn prímtényezői
4	13 × 139
5	3263443, ami prím
6	547 × 607 × 1033 × 31051
7	29881 × 67003 × 9119521 × 6212157481
8	5295435634831 × 31401519357481261 × 77366930214021991992277
9	181 × 1987 × 112374829138729 × 114152531605972711 × 35874380272246624152764569191134894955972560447869169859142453622851
10	2287 × 2271427 × 21430986826194127130578627950810640891005487 × P156
11	73 × C416
12	2589377038614498251653 × 2872413602289671035947763837 × C785
13	52387 × 5020387 × 5783021473 × 401472621488821859737 × 287001545675964617409598279 × C1600
14	13999 × 74203 × 9638659 × 57218683 × 10861631274478494529 × C3293
15	17881 × 97822786011310111 × 54062008753544850522999875710411 × C6618
16	128551 × C13335
17	635263 × 1286773 × 21269959 × C26661
18	50201023123 × 139263586549 × 60466397701555612333765567 × C53313
19	775608719589345260583891023073879169 × C106685
20	352867 × 6210298470888313 × C213419
21	387347773 × 1620516511 × C426863
22	91798039513 × C853750

Alkalmazásai

Sablon:Harvtxt a Sylvester-sorozat tulajdonságait használják fel arra, hogy nagy számú olyan Szaszaki-féle Einstein-sokaságot definiáljanak, melyek differenciális topológiája megegyezik a páratlan dimenziójú gömbökével vagy egzotikus gömbökével. Megmutatják, hogy a 2n − 1 dimenziós topologikus gömb különböző Szaszaki-féle Einstein-metrikája legalább arányos az s_n-nel, így n-re nézve dupla exponenciálisan nő.

Ahogy Sablon:Harvtxt is lejegyezte, Sablon:Harvtxt és Sablon:Harvtxt a Sylvester-sorozatból vett értékekkel konstruált alsó korlátos példákat az online ládapakolási algoritmusokhoz. Sablon:Harvtxt hasonlóan használta fel a sorozatot egy kétdimenziós szabási feladat-algoritmus teljesítményének alsó korlátjának beállítására.

A Znám-probléma olyan számhalmazokkal foglalkozik, melyek közül bármelyik szám osztója az összes többi szám szorzata plusz 1-nek, de egyik szám sem azonos vele (tehát valódi osztója). Az utóbbi követelmény hiányában a Sylvester-sorozat értékei megoldásait adnák a problémának; a követelménnyel együtt más megoldásai vannak, melyek a Sylvester-sorozatéhoz hasonló rekurziókból származnak. A Znám-probléma megoldásainak a felületi szingularitások osztályozásában (Brenton and Hill 1988) és a nemdeterminisztikus véges állapotú automaták elméletében vannak alkalmazásai.

Sablon:Harvs leírja a k taggal való, egyhez legközelebbi közelítések egy alkalmazását a tökéletes számok osztószámának alsó korlátjának meghatározásában; Sablon:Harvtxt ugyanezt a tulajdonságot használja bizonyos csoportok méretére vonatkozó alsó korlát meghatározására.

Kapcsolódó szócikkek

• Cahen-állandó
• Elsődleges áltökéletes számok
• Eukleidész–Mullin-sorozat

Irodalom

• Sablon:Cite journal
• Sablon:Cite web
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite book
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite book
• Sablon:Cite book
• Sablon:Cite journal
• Jones, Rafe (2006). "The density of prime divisors in the arithmetic dynamics of quadratic polynomials" arXiv:math.NT/0612415
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite journal
• Sablon:Cite book

További információk

• Irrationality of Quadratic Sums, from K. S. Brown's MathPages.
• Sablon:Mathworld