Collatz-sejtés

A Wikipédiából, a szabad enciklopédiából

A Collatz-sejtés egy máig megoldatlan probléma a matematikában. Több más néven is ismert, például Ulam-sejtés vagy 3n+1 probléma. A sejtés a nevét Lothar Collatzról kapta, aki 1937-ben fogalmazta meg azt.

Lényegében arról van szó, hogy egy kiválasztott számból egy egyszerű szabály ismételt alkalmazásával milyen sorozatot kapunk. A sejtés szerint bárhonnan indulva a sorozatok ugyanabba a ciklusba futnak bele.[1]

A sejtés megfogalmazása[szerkesztés]

Legyen egy tetszőleges egész szám. A sorozat szabálya a következő:

A sejtés szerint a sorozat egy -tól függő értéktől kezdve ugyanazt a ciklust fogja ismételni minden kiindulási érték esetén: . Azt a legkisebb számot, amitől kezdve ismétlődik a sorozat, megállási időnek nevezzük. Így a sejtés átfogalmazható: A fenti rekurziós képlet esetén minden -ra van megállási idő.

Ha a sejtés hamis, akkor két lehetőségünk van:

  1. a sorozat olyan ciklusba fut bele, ami nem tartalmazza az 1-et;
  2. a sorozat minden határon túl növekszik.

Példák[szerkesztés]

esetén a sorozat:

esetén a sorozat kissé hosszabb: , és, mint látható, egészen 160-ig növekszik.

Ha az indulási szám 2-hatvány, a sorozat megállási ideje kicsi lesz, egészen pontosan , mivel csak a felezési iteráció történik meg. Ellenben Mersenne-prímek esetén először alkalommal növekedni fog a sorozat -ről indulva, mielőtt csökkenne.

Ciklusok[szerkesztés]

A ciklusok olyan szám-n-esek, amelyek periodikusan ismétlődnek. A ciklus triviális, a sejtés szerint minden sorozat tartalmazza.

A pontos definíció szerint -ból kiindulva az n-ciklus azt jelenti, hogy . Ha van ilyen ciklus, akkor a sejtés hamis.

A "rövidített" definíciója a ciklusoknak a következő:

Páratlan szám után ugyanis mindig páros következik. Így a ciklusokat a következőképpen jelölhetjük: , mivel .

Ebben az esetben növekedés után ugyanennyi csökkenés következik be, ezt k-ciklusnak nevezzük. A triviális ciklus az , ezt 1-ciklusnak nevezzük. Ez az egyetlen ismert ciklus, így a sejtés másik formája. 1977-ben Steiner igazolta, hogy kizárólag ez az 1-ciklus létezik. A bizonyítást felhasználva Simons igazolta 2000-ben, hogy nincs 2-ciklus. 2003-ban Simons és de Weger igazolta, hogy nincsen k-ciklus, ha .

Vizsgálatok[szerkesztés]

A legtöbb matematikus szerint a sejtés igaz, erre utalnak a kísérleti vizsgálatok.

Kísérleti tapasztalatok[szerkesztés]

Számítógépes módszerekkel a sejtést igazolták minden egészre. Ez magában nem jelenti a sejtés valószínűségének növekedését, mivel csak véges sok esetet lehet megvizsgálni a végtelen sokból. Előfordulhat ugyanis, hogy extrém nagy számok esetén találnak ellenpéldát, mint az történt például a Pólya-sejtés esetén. Éppen ezért a kérdést a kísérleti tapasztalatok nem támasztják alá megnyugtató módon.

Valószínűségi heurisztika[szerkesztés]

Ha valaki csak a páratlan számokat veszi figyelembe valamely sorozatban, akkor azt fogja találni, hogy az egymást követő páratlan számok hányadosa körülbelül 3/4. Ez arra utal. hogy a sorozat egy idő után csökkenni kezd. Természetesen mindez csak a divergenciát cáfolja, a sejtést nem igazolja. Ez alapján annyit lehet mondani, hogy a sejtés igazolódásának valószínűsége 1 bármely számra, ami nem jelenti azt, hogy minden számra igaz. (Ez egyszerűen a valószínűség tulajdonságaiból fakad.)

Szigorú határok[szerkesztés]

Bár szigorúan nem sikerült még belátni minden számra, hogy igaz rá a sejtés, igen sokra teljesül. Krasikov és Lagarias igazolta, hogy az intervallumban az ilyen számok mennyisége arányos -nal.[2]

Érdekességek[szerkesztés]

Collatz maga nagyon nehéznek ítélte a problémát, azért sokáig nem is publikálta, csak az ismerőseinek beszélt róla. Már 1929-ben részt vett Göttingenben többek között gráfokat is említő előadásokon, és a 30-as években megfogalmazott kérdéseket, de csak az ötvenes évekből említik, hogy a konkrét sejtést szóban emlegette más matematikusoknak, és az első publikációk csak az 1970-es évek elején születtek meg.[2]

Erdős Pál "teljesen reménytelen" problémának vélte. Ez nem akadályozta meg abban, hogy 500 dolláros díjat írjon ki a bizonyításáért.

B. Thwaites 1000 dollárt ajánlott fel a probléma megoldásáért.[3]

John Horton Conway bebizonyította, hogy a sejtés általánosítása algoritmikusan eldönthetetlen probléma.[4]

Shizuo Kakutani megemlékezik egy viccről, ami szerint a Collatz-sejtést azért találták ki, hogy lelassítsák az amerikai matematikai haladást. Erre példának hozta fel, hogy egyszer egy teljes hónapig a Yale egyetem minden matematikusa a sejtést próbálta bizonyítani.

Források[szerkesztés]

  1. Eric W. Weisstein írása a MathWorld oldalon
  2. ^ a b "Jeffrey C. Lagarias". „"The 3x+1 Problem: An Overview"”.  
  3. Thwaites, B. "Two Conjectures, or How to Win £1100." Math. Gaz. 80, 35-36, 1996.
  4. Conway, J. H. "Unpredictable Iterations." Proc. 1972 Number Th. Conf., University of Colorado, Boulder, Colorado, pp. 49-52, 1972.