Erdős–Straus-sejtés

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

Az Erdős–Straus-sejtés a számelmélet területének egy sejtése, mely kimondja, hogy minden n ≥ 2 egész szám esetén a 4/n racionális szám kifejezhető három egységtört összegeként (ismert tény, hogy minden racionális szám felírható véges számú egységtört összegeként). A sejtést 1948-ban fogalmazta meg Erdős Pál és Ernst G. Straus.[1] Egyike az Erdős által megfogalmazott számos sejtésnek.

Formálisabban megfogalmazva, a sejtés kimondja, hogy minden n ≥ 2 egész számhoz létezik x, y és z pozitív egész, ahol

Ezek az egységtörtek megadják a 4/n egyiptomi törtekkel való felírásának módját. Például az n = 5 esetben két megoldás is létezik:

A probléma nehézségéhez nagyban hozzájárul a kikötés, hogy x, y és z is pozitív legyen. Ha megengedjük a negatív értékeket, a probléma triviálisan megoldható lenne. Továbbá, ha n összetett szám, azaz n = pq, akkor a 4/n felbontása azonnal megoldható a 4/p vagy a 4/q segítségével. Tehát, ha létezik ellenpélda az Erdős–Straus-sejtésre, akkor a legkisebb n ellenpéldának prímszámnak kellene lennie, továbbá mindössze 6, 840-nel való osztáskor kapott maradékosztályba tartozhat.[2] Számítógépes kereséssel a sejtést n ≤ 1014-ig igazolták[3], de tetszőleges n értékre továbbra is eldöntetlen.

Háttér[szerkesztés]

A racionális számok egységtörtek összegeként való felírásával már az ókori Egyiptom matematikusai is foglalkoztak, akik a tört számok leírására ezt az egyiptomi tört alakot használták. Az egyiptomiak által készített táblázatok, amilyen a Rhind-papirusz, tartalmazták a 2/n alakú törtek egységtört-felírását, amihez a legtöbb esetben mindössze két vagy három tagra volt szükségük.

Az egyiptomi törteket előállító mohó algoritmus először Fibonacci 1202-ben kiadott könyvében, a Liber Abaciben szerepelt. Az algoritmus olyan felbontást keres, ahol a soron következő egységtört a legnagyobb, amely nem nagyobb a maradék kifejezni kívánt számnál. 2/n vagy 3/n alakú törteket a mohó algoritmus legfeljebb két vagy három tag segítségével előállítja. Általánosabban, megmutatható, hogy a 3/n alakú törtek csakkor írhatók fel két taggal, ha n-nek van olyan osztója, ami 3-mal osztva 2 maradékot ad (azaz ≡ 2 mod 3), egyébként három taggal írhatók csak fel.[4]

Tehát a 2 vagy 3 számlálójú törteknél teljes mértékben tisztázott a kérdés, hogy hány egységtört-taggal írhatók fel, a 4/n alakú törtek az első eset, ahol nem ismert, hogy a legrosszabb esetben hány tagra van szükség. A mohó algoritmus kettő, három vagy négy tagból álló felbontást ad, az n modulo 4 értékétől függően; ha n ≡ 1 (mod 4), a mohó algoritmus négytagú felbontást produkál. Tehát a 4/n egyiptomi törtekkel való felírásának legrosszabb esete három vagy négy. Az Erdős–Straus-sejtés azt mondja ki, hogy ebben az esetben is, ugyanúgy, mint amikor a számlálóban 3 állt, a felírás elvégezhető három taggal.

Moduláris aritmetikai azonosságok[szerkesztés]

Ha a 4/n = 1/x + 1/y + 1/z egyenlet mindkét oldalát megszorozzuk nxyz-zel, a következő, az eredetivel ekvivalens alakhoz jutunk: 4xyz = n(xy + xz + yz).[5] Egész változós polinom egyenletként ez a diofantoszi egyenletek közé tartozik. A Hasse-elv kimondja, hogy a diofantoszi egyenletek egész megoldásai megkaphatók a minden lehetséges prímszám szerinti maradékosztály szerint vett megoldások kombinálásával. Ránézésre a Hasse-elvnek nem sok értelme van az Erdős–Straus-sejtés esetében, hiszen a 4xyz = n(xy + xz + yz) egyenlet könnyen megoldható bármilyen prímszám szerinti maradékosztályok szerint. Mégis, a moduláris azonosságok nagyon hasznos eszközt nyújtanak a sejtés tanulmányozásához.

Bizonyos kongruenciarelációkat kielégítő n-ek esetében a 4/n automatikusan, polinomiális azonosságként felírható. Például minden esetben, amikor n ≡ 2 (mod 3), a 4/n felírása automatikusan következik:

Itt mindhárom nevező, az n, az (n − 2)/3 + 1 és az n((n − 2)/3 + 1) is n-nek a polinomja, továbbá mindhárom egész értéket vesz fel, ha n ≡ 2 (mod 3). A már említett mohó algoritmus azokra az esetekre talál három vagy kevesebb tagból álló megoldást, amikor n nem ≡ 1 vagy 17 (mod 24), az n ≡ 17 (mod 24) esetet viszont lefedi a 2 (mod 3) reláció, tehát az egyetlen fennmaradó eset, amire a két módszer nem talál három vagy kevesebb tagból álló megoldást, az az n ≡ 1 (mod 24).

Ha lehetséges lenne elég sok, a fentiekhez hasonló megoldást találni különböző modulusokra oly módon, hogy azok a kongruenciák teljes lefedőrendszerét alkossák, a probléma meg is lenne oldva. Azonban, ahogy azt (Mordell 1967) megmutatta, a polinomazonosság, ami megoldást nyújt az n értékekre ≡ r (mod p) csak akkor létezhet, amikor az r nem kvadratikus maradék modulo p. Például a 2 nem kvadratikus maradék modulo 3, így az azonosság létezése az n ≡ 2 (modulo 3) értékekre nem mond ellent Mordell eredményének, ellenben 1 kvadratikus maradék modulo 3, tehát Mordell eredménye bizonyítja, hogy nem létezhet hasonló azonosság az n ≡ 1 (modulo 3) értékekre.

Mordell polinomazonosságokról készített listájában szerepelnek 4/n-t három tagból előállító azonosságok, azokra az esetekre, ha n ≡ 2 mod 3 (mint fent), n ≡ 3 (mod 4), n ≡ 5 (mod 8), n ≡ 2 vagy 3 (mod 5), illetve n ≡ 3, 5 vagy 6 (mod 7). Ezek az azonosságok lefedik az összes számot, amik kvadratikus nem-maradékok ezekre a modulusokra nézve. Nagyobb modulusoknál azonban nem sikerült az összes nem-maradékot lefedni hasonló relációkkal. Mordell azonosságaiból következik, hogy létezik megoldás az összes n-re, kivéve talán azokat, ahol n ≡ 1, 121, 169, 289, 361 vagy 529 (mod 840). 1009 a legkisebb prímszám, ami nincs lefedve ezzel a kongruenciarendszerrel. Még több moduláris azonosságot kombinálva Webb és mások megmutatták, hogy a lehetséges ellenpéldák száma az n nevezőjű törtnél az [1,N] intervallumban nullához tart, ha N tart a végtelenhez.[6]

Mordell a kongruenciaazonosságok formáját korlátozó eredményének dacára van még némi remény, hogy lehetséges moduláris azonosságokkal bizonyítani az Erdős–Straus-sejtést. Egyetlen prímszám sem lehet teljes négyzet, ezért a Hasse–Minkowski-tétel[7] értelmében minden p prímszámhoz található egy nála nagyobb q prímszám, ahol p nem kvadratikus maradék modulo q. A sejtés bizonyításának egy lehetséges megközelítése az lenne, hogy minden p prímhez találni kellene egy nála nagyobb q prímszámot, és egy kongruenciát, ami megoldja a 4/n problémát np (mod q)-ra; ha ez lehetséges, akkor egyetlen p prím sem lehetne a sejtés ellenpéldája, így a sejtés igazolt lenne.

Részeredmények számítógépes ellenőrzéssel[szerkesztés]

Különböző szerzők értek el eredményeket ellenpéldák brute-force keresésével; ezek a keresések nagyban felgyorsíthatók, ha csak az ismert kongruenciarelációk által le nem fedett prímszámok között végzik a keresést. A sejtést az n ≤ 5000 esetre maga Straus, n ≤ 8000-re Bernstein, n ≤ 20 000-re Shapiro, n ≤ 106 128-ra Obláth, n ≤ 107-re Yamamoto igazolta.[8] Hasonló kereséssel Allan Swett igazolta, hogy a sejtés igaz minden n ≤ 1014 esetre.[3]

A megoldások száma[szerkesztés]

A 4/n probléma különböző megoldásainak számát, n függvényében, számítógépes segítséggel szintén meghatározták kis n értékekre, és úgy tűnik, n-nel együtt kissé szabálytalanul növekszik. Kezdve n = 3-mal, a különböző nevezők különböző megoldásainak száma:

1, 1, 2, 5, 5, 6, 4, 9, 7, 15, 4, 14, 33, 22, 4, 21, 9, ... (A073101 sorozat az OEIS-ben).

Még nagyobb n-ekre is előfordulhat, hogy viszonylag kevés eltérő megoldás létezik; például az n = 73 esetre mindössze hét.

(Elsholtz & Tao 2011) megmutatta, hogy a 4/n probléma lehetséges megoldásainak számának átlagára (ha az n-ig vett prímszámokra átlagolunk) létezik n polilogaritmikus függvénye szerinti felső korlát. Más diofantoszi problémáknál előfordul olyan bizonyítás, ahol a megoldás létezését a megoldások számára adott aszimptotikus alsó korlát létezésének bizonyításával igazolják, de az ilyen típusú bizonyítások főként az olyan problémáknál működnek, ahol a megoldások száma polinomiálisan növekszik, így Elsholtz és Tao eredménye ezt a fajta megoldást valószínűtlenné teszi.[9] Elsholtz és Tao a megoldások számával kapcsolatos bizonyításukban felhasználják a Bombieri–Vinogradov-tételt, a Brun–Titchmarsh-féle egyenlőtlenséget, valamint moduláris azonosságok egy rendszerét, melyek akkor érvényesülnek, ha n ≡ −c vagy −1/c (modulo 4ab), ahol a és b tetszőleges relatív prímek, c pedig az a + b bármelyik páratlan osztója. Például az a = b = 1 az egyik Mordell-azonosságot adja, ami akkor érvényes, ha n ≡ 3 (mod 4).

Negatív számos megoldások[szerkesztés]

A megszorítás, hogy x, y és z is pozitív legyen, megalapozza a probléma nehézségi fokát; ha ugyanis negatív értékeket is megengednék, a probléma triviálisan megoldható volna a következő két azonosság bármelyikének segítségével:

vagy

Páratlan n-ekre ráadásul három tagból álló, egy negatív tagot tartalmazó megoldás mindig lehetséges:[10]

Általánosítások[szerkesztés]

A sejtés egy általánosítása kimondja, hogy minden pozitív k-hoz létezik egy olyan N szám, hogy minden nN-re van a pozitív egész számok körében megoldása a k/n = 1/x + 1/y + 1/z egyenletnek. A sejtés ilyen jellegű változatát k = 5 esetre Wacław Sierpiński mondta ki, a teljes általánosított változat Andrzej Schinzel eredménye.[11]

Még ha az általánosított Erdős–Straus-sejtés nem is bizonyul igaznak bármely fix k értékre, akkor is kimondható, hogy az olyan, három taggal ki nem fejezhető k/n törtek száma, ahol az n értéke 1 és N közé esik, N függvényében a lineárisnál gyengébben nőhet csak.[12] Így tehát ha az eredeti Erdős–Straus-sejtés maga (tehát a k = 4 eset) tévesnek bizonyul, akkor az ellenpéldák száma csak a lineárisnál gyengébben nőhet. Még erősebb állítás, hogy bármely fix k értékre csak szublineáris számú olyan n létezik, ami kettőnél több egyiptomi tört tag összegeként állna elő.[13] A sejtés általánosított változata ekvivalens azzal állítással, hogy a fel nem bontható törtek száma nem csak szublineáris, de korlátos.

Ha n páratlan szám, a „páratlan mohó felbontás algoritmusa” szerint kereshetjük a k/n = 1/x + 1/y + 1/z egyenlet olyan megoldásait, ahol x, y és z különböző, pozitív páratlan számok. Tudjuk, hogy az egyenletnek mindig létezik ilyen megoldása a k = 3 esetben.[14]

További információk[szerkesztés]

Jegyzetek[szerkesztés]

  1. Lásd pl. (Elsholtz 2001). A legkorábbi ismert publikációja azonban valószínűleg (Erdős 1950).
  2. (Mordell 1967).
  3. ^ a b Swett, Allan, The Erdos-Straus Conjecture, <http://math.uindy.edu/swett/esc.htm>. Hozzáférés ideje: 2006-09-09.
  4. (Eppstein 1995).
  5. Lásd pl. (Sander 1994)-nél egy egyszerűbb diofantoszi felírást, ahol specifikusan feltételezi, hogy x, y, és z közül melyik osztható n-nel.
  6. (Webb 1970)
  7. A Hasse–Minkowski-tétel (BSc szakdolgozat)
  8. (Obláth 1950); (Rosati 1954); (Kiss 1959); (Bernstein 1962); (Yamamoto 1965); (Terzi 1971); (Jollensten 1976); (Kotsireas 1999).
  9. On the number of solutions to 4/p = 1/n_1 + 1/n_2 + 1/n_3, Terence Tao, "What's new", July 7, 2011.
  10. (Jaroma 2004).
  11. (Sierpiński 1956); (Vaughan 1970).
  12. (Webb 1970); (Vaughan 1970); (Li 1981); (Yang 1982); (Ahmadi & Bleicher 1998); (Elsholtz 2001).
  13. (Hofmeister & Stoll 1985).
  14. (Schinzel 1956); (Suryanarayana & Rao 1965); (Hagedorn 2000).