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 (A000058 sorozat az OEIS-ben).
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 ((wd), (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:
Az üres szorzat értéke megegyezés szerint 1, ezért s0 = 2 a sorozat kezdőértéke.
egy E számra, ami körülbelül 1,264084735305302.[1] Ez azt jelenti, hogy s0 az E2-hez legközelebb álló egész szám, s1 az E4-hez legközelebb álló egész szám, s2 az E8-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 sn-re, vedd E2-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 sn 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 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:
Egyiptomi törtekkel való kapcsolatai
A Sylvester-sorozat reciprokai által kapott egységtörtek végtelen sora a következő:
A sor részösszegeinek egyszerű alakja:
ami igazolható indukcióval, vagy akár közvetlen módon – belátva, hogy a rekurzióból következik az
összefüggés, amivel teleszkopikus összegzést végezve:
Mivel a részösszegek ezen sorozata 1-hez konvergál, ezért a teljes sor az 1-nek végtelen egyiptomitört-reprezentációját adja:
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:
Ez általánosan így néz ki egy tetszőleges k index esetén: .
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.[2] 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(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.[3]
Ha egy sorozat elég gyorsan nő ahhoz, hogy
és a sorozat egy A racionális számhoz konvergál, akkor egy bizonyos küszöbindextől kezdődően minden n indexre az sorozatot ugyanazon
rekurrencia-szabály kell meghatározza, mint a Sylvester-sorozatot (Badea 1993).
(Erdős & Graham 1980) 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:
(Badea 1995) vizsgálta a sejtés megoldásának előrehaladását; lásd még (Brown 1979).
Oszthatóság és prímfelbontások
Ha i < j, a definícióból következik, hogy . 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.[4]
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 (Vardi 1991) í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:[5] valóban, az x-nél kisebb ilyen prímek száma .[6]
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).[7] Konvenció szerint Pn és Cn bizonyos n számjegyű prímszámokat, illetve összetett számokat jelölnek.
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.[9]
D. R. Curtiss (1922) 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; (Miller 1919) ugyanezt a tulajdonságot használja bizonyos csoportok méretére vonatkozó alsó korlát meghatározására.
↑Munkájukban Seiden és Woeginger végig „Salzer sorozata”-ként hivatkoznak a Sylvester-sorozatra, (Salzer 1947) legjobb approximációra vonatkozó munkája nyomán.
Brown, D. J. (1979). „A lower bound for on-line one-dimensional bin packing algorithms”, Kiadó: Coordinated Science Lab., Univ. of Illinois, Urbana-Champaign.