Erdős–Straus-sejtés

A matematika megoldatlan problémája: Rendelkezik-e 4/n = 1/x + 1/y + 1/z pozitív egész megoldással minden n ≥ 2 egészre? (A matematika további megoldatlan problémái)

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. 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

${\frac {4}{n}}={\frac {1}{x}}+{\frac {1}{y}}+{\frac {1}{z}}.$

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:

${\frac {4}{5}}={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{20}}={\frac {1}{2}}+{\frac {1}{5}}+{\frac {1}{10}}.$

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. Számítógépes kereséssel a sejtést n ≤ 10¹⁴-ig igazolták, de tetszőleges n értékre továbbra is eldöntetlen.

Háttér

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 pontosan akkor í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.

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

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). 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:

${\frac {4}{n}}={\frac {1}{n}}+{\frac {1}{(n-2)/3+1}}+{\frac {1}{n((n-2)/3+1)}}.$

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.

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 é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 n ≡ p (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

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 ≤ 10⁷-re Yamamoto igazolta. Hasonló kereséssel Allan Swett igazolta, hogy a sejtés igaz minden n ≤ 10¹⁴ esetre.

A megoldások száma

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. 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

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:

${\frac {4}{4k+1}}={\frac {1}{k}}-{\frac {1}{k(4k+1)}}$

vagy

${\frac {4}{4k-1}}={\frac {1}{k}}+{\frac {1}{k(4k-1)}}.$

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

${\frac {4}{n}}={\frac {1}{(n-1)/2}}+{\frac {1}{(n+1)/2}}-{\frac {1}{n(n-1)(n+1)/4}}.$

Általánosítások

A sejtés egy általánosítása kimondja, hogy minden pozitív k-hoz létezik egy olyan N szám, hogy minden n ≥ N-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.

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. Í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ő. 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.

További információk

• Weisstein, Eric W.: Erdos-Straus Conjecture (angol nyelven). Wolfram MathWorld
• Counting the number of solutions to the Erdös-Straus equation on unit fractions, Terence Tao, July 31, 2011.

Jegyzetek

• Ahmadi, M. H. & Bleicher, M. N. (1998), "On the conjectures of Erdős and Straus, and Sierpiński on Egyptian fractions", International Journal of Mathematical and Statistical Sciences 7 (2): 169–185.
• Bernstein, Leon (1962), "Zur Lösung der diophantischen Gleichung m/n = 1/x + 1/y + 1/z, insbesondere im Fall m = 4", Journal für die Reine und Angewandte Mathematik 211: 1–10.
• Elsholtz, Christian (2001), "Sums of k unit fractions", Transactions of the American Mathematical Society 353 (8): 3209–3227, DOI 10.1090/S0002-9947-01-02782-9.
• Elsholtz, Christian & Tao, Terence (2011), Counting the number of solutions to the Erdős–Straus equation on unit fractions, <http://terrytao.files.wordpress.com/2011/07/egyptian-count13.pdf>.
• Eppstein, David (1995), Small numerators, "Ten algorithms for Egyptian fractions", Mathematica in Education and Research 4 (2): 5–15, <http://www.ics.uci.edu/~eppstein/numth/egypt/smallnum.html>
• Erdős, Paul (1950), "Az 1/x₁ + 1/x₂ + ... + 1/x_n = a/b egyenlet egész számú megoldásairól (On a Diophantine Equation)", Mat. Lapok. 1: 192–210, <http://www.renyi.hu/~p_erdos/1950-02.pdf>.
• Guy, Richard K. (2004), Unsolved Problems in Number Theory (3rd ed.), Springer Verlag, pp. D11, ISBN 0-387-20860-7.
• Hagedorn, Thomas R. (2000), "A proof of a conjecture on Egyptian fractions", American Mathematical Monthly (Mathematical Association of America) 107 (1): 62–63, DOI 10.2307/2589381.
• Hofmeister, Gerd & Stoll, Peter (1985), "Note on Egyptian fractions", Journal für die Reine und Angewandte Mathematik 362: 141–145.
• Jaroma, John H. (2004), "On expanding 4/n into three Egyptian fractions", Crux Mathematicorum 30 (1): 36–37, <http://cms.math.ca/crux/v30/n1/page36-37.pdf> Archiválva 2011. július 16-i dátummal a Wayback Machine-ben.
• Jollensten, Ralph W. (1976), "A note on the Egyptian problem", Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), vol. XVII, Congressus Numerantium, Winnipeg, Man.: Utilitas Math., pp. 351–364.
• Kiss, Ernest (1959), "Quelques remarques sur une équation diophantienne", Acad. R. P. Romîne Fil. Cluj Stud. Cerc. Mat. 10: 59–62.
• Kotsireas, Ilias (1999), "The Erdős-Straus conjecture on Egyptian fractions", Paul Erdős and his mathematics (Budapest, 1999), Budapest: János Bolyai Math. Soc., pp. 140–144.
• Li, De Lang (1981), "Equation 4/n = 1/x + 1/y + 1/z", Journal of Number Theory 13 (4): 485–494, DOI 10.1016/0022-314X(81)90039-1.
• Mordell, Louis J. (1967), Diophantine Equations, Academic Press, pp. 287–290.
• Obláth, Richard (1950), "Sur l'équation diophantienne 4/n = 1/x₁ + 1/x₂ + 1/x₃", Mathesis 59: 308–316.
• Rosati, Luigi Antonio (1954), "Sull'equazione diofantea 4/n = 1/x₁ + 1/x₂ + 1/x₃", Boll. Un. Mat. Ital. (3) 9: 59–63.
• Sander, J. W. (1994), "On 4/n = 1/x + 1/y + 1/z and Iwaniec' half-dimensional sieve", Journal of Number Theory 46 (2): 123–136, DOI 10.1006/jnth.1994.1008.
• Schinzel, André (1956), "Sur quelques propriétés des nombres 3/n et 4/n, où n est un nombre impair", Mathesis 65: 219–222.
• Sierpiński, Wacław (1956), "Sur les décompositions de nombres rationnels en fractions primaires", Mathesis 65: 16–32.
• Suryanarayana, D. & Rao, N. Venkateswara (1965), "On a paper of André Schinzel", J. Indian Math. Soc. (N.S.) 29: 165–167.
• Terzi, D. G. (1971), "On a conjecture by Erdős-Straus", Nordisk Tidskr. Informationsbehandling (BIT) 11 (2): 212–216, DOI 10.1007/BF01934370.
• Vaughan, R. C. (1970), "On a problem of Erdős, Straus and Schinzel", Mathematika 17 (02): 193–198, DOI 10.1112/S0025579300002886
• Webb, William A. (1970), "On 4/n = 1/x + 1/y + 1/z", Proceedings of the American Mathematical Society (American Mathematical Society) 25 (3): 578–584, DOI 10.2307/2036647.
• Yamamoto, Koichi (1965), "On the Diophantine equation 4/n = 1/x + 1/y + 1/z", Memoirs of the Faculty of Science. Kyushu University. Series A. Mathematics 19: 37–47, DOI 10.2206/kyushumfs.19.37.
• Yang, Xun Qian (1982), "A note on 4/n = 1/x + 1/y + 1/z", Proceedings of the American Mathematical Society 85 (4): 496–498, DOI 10.2307/2044050.