Erdős-Strausova domneva
Erdős-Strausova domneva je v matematiki domneva, ki za vsako celo število n > 1 predvideva, da se lahko racionalno število 4/n izrazi kot vsoto treh enotskih ulomkov. Domnevo sta formulirala leta 1948 Paul Erdős in Ernst Gabor Straus.[1]
Bolj formalno domneva trdi, da za vsako celo število n > 1 obstajajo takšna pozitivna cela števila x, y in z, ki rešijo linearno diofantsko enačbo:
Brez poseganja v splošnost se lahko domneva, da velja , oziroma še ostreje . Zato ti enotski ulomki načeloma predstavljajo egipčanski ulomek za število 4/n, saj se drugače lahko vedno preprosto reče, da trivialno velja:
Za n = 2 je takšna trivialna rešitev tudi edina:
Za n = 3 in 4 na primer obstaja ena netrivialna rešitev:
za n = 5 dve rešitvi:
za n = 6 pa pet rešitev:
ki sicer niso najmanjše rešitve, saj je še edina dvočlena rešitev:
in te rešitve ne vplivajo na domnevo.
Omejitev, da so x, y in z pozitivni, je za težavnost problema bistvena, saj, če bi bile dovoljene tudi negativne vrednosti, bi bil problem spet rešljiv trivialno. Če je n sestavljeno število oblike n = pq, izhaja razvoj za 4/n takoj iz razvoja za 4/p ali 4/q. Zato, če za Erdős-Strausovo domnevo obstaja protiprimer, mora v njem biti najmanjši n praštevilo, in lahko je še naprej omejen na šest aritmetičnih zaporedij po modulu 840: n ≡ 1, 121, 169, 289, 361, 529 (mod 840).[2][3] Računalniška iskanja so potrdila pravilnost domneve do n ≤ 1014,[4] dokaz za vse n pa ostaja odprti problem.
Ozadje
[uredi | uredi kodo]Iskanje razvojev racionalnih števil v vsote enotskih ulomkov sega do egipčanske matematike. Tedaj so za zapis ulomljenih količin rabili razvoje v egipčanske ulomke. Egipčani so izdelali razpredelnice, kot je npr. razpredelnica 2/n v Rhindovem papirusu o razvoju ulomkov oblike 2/n, od katerih ima večina dva ali tri člene.
Požrešni algoritem, ki ga je leta 1202 prvi opisal Fibonacci v svoji knjigi Knjiga o abaku (Liber Abaci), išče razvoj v katerem je vsak zaporedni člen največji enotski ulomek, ki ni večji od preostalega prikazanega števila. Za ulomke oblike 2/n ali 3/n požrešni algoritem rabi največ dva ali tri člene. V splošnem se lahko pokaže, da ima oblika 3/n v razvoju dva člena, če in samo če ima n faktor, ki je kongruenten 2 mod 3, drugače pa v kateremkoli razvoju zahteva 3 člene.[5]
Tako je vprašanje koliko členov je v egipčanskem ulomku potrebnih za števca 2 in 3 popolnoma rešeno. Ulomki oblike 4/n so prvi primer v katerem število členov za razvoj v naslabšem primeru ostaja neznano. Požrešni algoritem daje razvoje z dvema, tremi ali štirimi členi, kar je odvisno od vrednosti n mod 4; ko je n kongruenten 1 mod 4, daje požrešni algoritem razvoje s štirimi členi. Zato mora biti število členov v razvoju egipčanskega ulomka oblike 4/n v najslabšem primeru tri ali štiri. Erdős-Straussova domneva pravi, da je v tem primeru, kot tudi v primeru za števec 3, največje število členov v razvoju enako 3.
Modularne enakosti
[uredi | uredi kodo]Če se enačbo 4/n = 1/x + 1/y + 1/z z obeh strani pomnoži z nxyz, se dobi enakovredno obliko enačbe za problem:
Kot polinomska enačba s celoštevilskimi vrednostmi je to zgled diofantske enačbe. Hassejevo načelo za diofantske enačbe zahteva, da je treba celoštevilsko rešitev diofantske enačbe tvoriti s kombinacijo rešitev, ki se jih dobi s kongruenco po modulo za vsako možno praštevilo. Očitno ima to načelo za Erdős-Strausovo domnevo malo smisla, saj se lahko enačbo 4xyz = n(xy + xz + yz) preprosto reši s kongruenco po modulu poljubnega praštevila. Navkljub temu so se modularne enakosti pokazale za zelo pomembno orodje pri raziskovanju domneve.
Za vrednosti n, za katere veljajo določene kongruenčne zveze, se lahko najde razvoj za 4/n takoj kot primer polinomske enakosti. Če je na primer n ≡ 2 (mod 3), je razvoj 4/n enak:
Tukaj je vsak od treh imenovalcev n, (n − 2) / 3 + 1 in n((n − 2) / 3 + 1) polinom n, in vsak je celo število, če je n kongruentno 2 (mod 3). Požrešni algoritem da za rešitev tri ali manj členov, kadar n ni 1 ali 17 (mod 24), primer za n ≡ 17 (mod 24) pa pokriva zveza za 2 (mod 3), tako da so edine vrednosti n, za katere ti dve metodi ne data razvoja v treh ali manj členih, tiste, ki so kongruentne 1 (mod 24).
Enačba:[4]
da posebej na primer pravilnost domneve za n = 3k + 2 = 2, 5, 8, 11, 14, 17, ... (za vrednosti k = 0, 1, 2, 3, 4, 5, ...), (OEIS A016789). Domneva jepravilna za vsa pozitivna cela števila n, ki so kongruentna 2 mod 3. Dve števili sta kongruentni mod n, če in samo če n deli njuno razliko. V tem primeru je 3k + 2 ≡ 2 (mod 3).
Če bi bilo mogoče najti rešitve kot so zgornje za dovolj različne module, bi bil s tvorjenjem polnega pokrivnega sistema kongruenc problem rešen. Vendar, kot je pokazal Mordell,[2] lahko polinomska enakost, ki zagotavlja rešitev za vrednosti n kongruentne r mod p, obstaja le, če r ni kvadratni ostanek po modulu p. 2 na primer ni kvadratni ostanek po modulu 3, tako da enakost za vrednosti n, ki so kongruentne 2 po modulu 3, ni v nasprotju z Mordellovim rezultatom, vendar je 1 kvadratni ostanek po modulu 3, in rezultat dokazuje, da lahko obstaja podobna enakost za vrednosti n, ki so kongruentne 1 po modulu 3.
Mordell navaja polinomske enakosti, ki dajo tričlene egipčanske ulomke za 4/n, ko je n ≡ 2 (mod 3) (zgoraj), 3 (mod 4), 5 (mod 8), 2 ali 3 (mod 5) in 3, 5 ali 6 (mod 7). Te enakosti pokrivajo vsa števila, ki niso kvadratni ostanki za te baze. Vendar za večje baze niso znana vsa števila, ki niso ostanki, in bi jih pokrivale enakosti takšne vrste. Iz Mordellovih enakosti se lahko zaključi, da obstaja rešitev za vse n, razen za tiste, ki so 1, 121, 169, 289, 361 ali 529 (mod 840). 1009 je najmanjše praštevilo, ki ga ta sistem kongruenc ne pokriva. S kombiniranjem večjih razredov modularnih enakosti so Webb in drugi pokazali, da delež števil n v intervalu [1,N], ki bi bili protiprimer za domnevo, teži k 0 v limiti, ko gre N k neskončnosti.[7]
Navkljub Mordellovemu rezultatu, ki omejuje obliko teh kongruenčnih enakosti, je še vedno nekaj upanja za rabo modularnih enakosti pri dokazovanju Erdős-Strausove domneve. Nobeno praštevilo ne more biti kvadrat, tako da po izreku Hasseja in Minkowskega velja, kadar je p praštevilo, obstaja takšno veliko praštevilo q, da p ni kvadratni ostanek po modulu q. Eden od možnih pristopov dokazovanja domneve bi bilo iskanje večjega praštevila q za vsako praštevilo p in kongruence, ki bi rešila problem 4/n za n ≡ p (mod q) - če bi bilo to mogoče, nobeno praštevilo p ne bi moglo biti protiprimer za domnevo in domneva bi bila pravilna.
Računsko preverjanje
[uredi | uredi kodo]Več avtorjev je izvedlo iskanja z grobo silo za protiprimere domneve. Ta iskanja se lahko precej pospešijo z upoštevajem le praštevil, ki jih ne pokrivajo znane kongruenčne enačbe.[8] Takšno preverjanje Allana Swetta je potrdilo pravilnost domneve za vsa števila n ≤ 1014.[4]
Število rešitev
[uredi | uredi kodo]Tudi število različnih rešitev za problem 4/n kot funkcije n so za majhne n našli z računalniškim iskanjem. Z naraščajočim n število rešitev raste nekoliko nepravilno. Število prvih n rešitev za n > 0 podaja naslednja razpredelnica:
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | … | OEIS |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 3 | 12 | 16 | 12 | 45 | 36 | 58 | 36 | 75 | 48 | 136 | 24 | 105 | 240 | 190 | 24 | 159 | 66 | 250 | 186 | 153 | 132 | 364 | 78 | 129 | 180 | 292 | 42 | 531 | 114 | … | A192786 | |
0 | 1 | 3 | 3 | 2 | 8 | 7 | 10 | 6 | 12 | 9 | 21 | 4 | 17 | 39 | 28 | 4 | 26 | 11 | 36 | 29 | 25 | 21 | 57 | 10 | 20 | 29 | 42 | 7 | 81 | 19 | … | A192787 | |
0 | 0 | 1 | 1 | 2 | 5 | 5 | 6 | 4 | 9 | 7 | 15 | 4 | 14 | 33 | 22 | 4 | 21 | 9 | 30 | 25 | 22 | 19 | 45 | 10 | 17 | 25 | 36 | 7 | 72 | 17 | … | A073101 |
Najprej je število vseh možnih rešitev z možnimi enakimi imenovalci s ponavljanjem, nato število različnih rešitev z možnimi enakimi imenovalci (brez ponavljanja) in nazadnje število različnih rešitev z različnimi imenovalci samo z egipčanskimi ulomki. Tudi za velike n je lahko relativno malo rešitev; za n = 73 je na primer le sedem različnih rešitev.
Elsholtz in Tao[9] sta pokazala, da je povprečno število rešitev za problem 4/n (povprečje čez praštevila do n) navzgor omejeno polilogaritemsko v n. Za nekatere druge diofantske probleme se lahko dokaže, da rešitev zmeraj obstaja z dokazovanjem asimptotičnih spodnjih mej števila rešitev, vendar takšne vrste dokazov obstajajo prvenstveno za probleme pri katerih število rešitev raste polinomsko, tako da je Elsholtzev in Taojev rezultat za to rešitev malo verjeten.[10] Dokaz Elsholtzeve in Taojeve meje števila rešitev vsebuje izrek Bombierija in Vinogradova, Brun-Titchmarshev izrek in sistem modularnih enakosti, ki veljajo kadar je n kongruenten −c ali −1/c po modulu 4ab, kjer sta a in b dve tuji pozitivni celi števili, c pa je lihi faktor od a + b. Če se postavi a = b = 1, se dobi na primer eno od Mordellovih enakosti, ki velja, kadar je n ≡ 3 (mod 4).
Rešitve v negativnih številih
[uredi | uredi kodo]Omejitev, da so x, y in z pozitivni, je za težavnost problema bistvena. Če bi bile dovoljene negativne vrednosti, bi bil problem spet rešljiv trivialno prek ene od enakosti:
in:
Za lihi n je možna tričlena rešitev z enim negativnim členom:[3]
- Zgleda
- 1. :
- 2. :
Posplošitve
[uredi | uredi kodo]Posplošena različica domneve pravi, da za poljubni pozitivni k obstaja takšno število N, da za vse n ≥ N obstaja rešitev diofanstke enačbe v pozitivnih celih številih:
Različica za k = 5 je Sierpiński-Erdőseva domneva iz leta 1956, za vse k pa je domnevo postavil Andrzej Schinzel istega leta.[11]
Četudi je posplošena domneva za poljubno določen k napačna, mora število ulomkov k/n z n od 1 do N, ki nimajo tričlenega razvoja, naraščati le podlinearno kot funkcija N.[7] Če je posebej Erdős-Strausova domneva sama (primer k = 4) napačna, potem število protiprimerov narašča le podlinearno. Velja še močnejši privzetek, da za določen k le podlinearno število vrednosti n za razvoj v egipčanske ulomke potrebuje več kot dva člena.[12] Posplošena različica domneve je enakovredna izjavi, da število ulomkov, ki se jih ne da razviti, ni le podlinearno, ampak omejeno.
Kadar je n liho število, se lahko po analogiji za problem lihega požrešnega razvoja za egipčanske ulomke vpraša po rešitvah za zgornjo diofantsko enačbo, kjer so x, y in z različna pozitivna liha števila. Rešitve za ta primer vedno obstajajo, če je k = 3.[13]
Posebni primeri
[uredi | uredi kodo]Mini Erdős-Strausova domneva
[uredi | uredi kodo]Ena različica te domneve za k = 3 je mini Erdős-Strausova domneva, ki pravi, da je diofantska enačba:
rešljiva za vsa cela števila n > 1 v pozitivnih celih številih x in y.
Ta trditev je napačna, saj enačba ni rešljiva za n = 3, ter natanko tedaj, ko imajo vsi prafaktorji števila n obliko 6k + 1 za k > 0, torej za števila (OEIS A004611):
- 7, 13, 19, 31, 37, 43, 49, 61, 67, 73, 79, 91, 97, 103, 109, 127, 133, 139, ...
Sem spadajo tudi sama praštevila oblike 6k + 1. Na primer 3/37, kjer ni rešitev z dvema členoma, je pa 15 rešitev s tremi. Rešljiva ni tudi s kvadrati takšnih prafaktorjev, kot npr.: 3/49 ali 3/91, kjer ni rešitev z dvema členoma, je pa 38 in 117 različnih rešitev s tremi.
Rešljiva pa je enačba, ko je npr. n sestavljeno število oblike 6k + 1 z vsemi prafaktorji oblike 6m - 1 za m > 0, npr. za vrednosti k (OEIS A070799) in n (OEIS A176275):
- {k,n} = {4, 25}, {9, 55}, {14, 85}, {19, 115}, {20, 121}, {24, 145}, {29, 175}, {31, 187}, {34, 205}, {39, 235}, {42, 253}, ...:
Rešljiva je tudi za praštevila oblike 3k - 1 za k > 0; za števila (OEIS A003627):
- 2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, 107, ...
Rešljiva je tudi za sestavljena števila (OEIS A175526):
- 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 96, 98, 99, 100, ...
razen za polpraštevila (sestavljena števila z dvema prafaktorjema) oblike 6k + 1: (OEIS A108164):
- 49, 91, 133, (169), 217, (247), 259, 301, (361), 403, 427, 469, 481, (511), 553, ...:
Na primer:
Sklici
[uredi | uredi kodo]- ↑ Glej npr. Elsholtz (2001). Najzgodnejši objavljen vir je sicer Erdős (1950).
- ↑ 2,0 2,1 Mordell (1967).
- ↑ 3,0 3,1 Jaroma (2004).
- ↑ 4,0 4,1 4,2 Swett, Allan. »The Erdos-Straus Conjecture« (v angleščini). Pridobljeno 9. septembra 2006.
- ↑ Eppstein (1995).
- ↑ Glej npr. Sander (1994) za preprostejšo diofantsko formulacijo z bolj specifičnimi privzetki kateri x, y in z so deljivi z n.
- ↑ 7,0 7,1 Webb (1970), Vaughan (1970), Li (1981), Yang (1982), Ahmadi; Bleicher (1998), Elsholtz (2001).
- ↑ Obláth (1950), Rosati (1954), Kiss (1959), Bernstein (1962), Yamamoto (1965), Terzi (1971), Jollensten (1976), Kotsireas (1999).
- ↑ Elsholtz; Tao (2011).
- ↑ Tao (2011).
- ↑ Sierpiński (1956), Vaughan (1970).
- ↑ Hofmeister; Stoll (1985).
- ↑ Schinzel (1956), Suryanarayana; Rao (1965), Hagedorn (2000).
Viri
[uredi | uredi kodo]- 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, MR 1666363
- 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 (v nemščini), 211: 1–10, MR 0142508
- 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, MR 1828604
- Elsholtz, Christian; Tao, Terence (2011), Counting the number of solutions to the Erdős–Straus equation on unit fractions (PDF), arXiv:1107.1010
- Eppstein, David (1995), »Ten algorithms for Egyptian fractions«, Mathematica in Education and Research, 4 (2): 5–15
{{citation}}
: Prezrt|contribution=
(pomoč) - Erdős, Paul (1950), »Az 1/x1 + 1/x2 + ... + 1/xn = a/b egyenlet egész számú megoldásairól (O diofantski enačbi)« (PDF), Mat. Lapok. (v madžarščini), 1: 192–210, MR 0043117
- Guy, Richard Kenneth (2004), Unsolved Problems in Number Theory (3. izd.), Springer Verlag, str. 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, JSTOR 2589381, MR 1745572
- Hofmeister, Gerd; Stoll, Peter (1985), »Note on Egyptian fractions«, Journal für die Reine und Angewandte Mathematik, 362: 141–145, MR 0809971
- Ionascu, Eugen J.; Wilson, Andrew (2010), On the Erdös-Straus conjecture, arXiv:1001.1100
- Jaroma, John H. (2004), »On expanding 4/n into three Egyptian fractions« (PDF), Crux Mathematicorum, 30 (1): 36–37, arhivirano iz prvotnega spletišča (PDF) dne 16. julija 2011, pridobljeno 21. aprila 2013
- 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), Congressus Numerantium, zv. XVII, Winnipeg, Man.: Utilitas Math., str. 351–364, MR 0429735
- Kiss, Ernest (1959), »Quelques remarques sur une équation diophantienne«, Acad. R. P. Romîne Fil. Cluj Stud. Cerc. Mat. (v romunščini), 10: 59–62, MR 0125069
- Kotsireas, Ilias (1999), »The Erdős-Straus conjecture on Egyptian fractions«, Paul Erdős and his mathematics (Budimpešta 1999), Budimpešta: János Bolyai Math. Soc., str. 140–144, MR 1901903
- 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, MR 0642923
- Mizony, Michel; Gardes, Marie-Line (Junij 2012), Un point sur la conjecture d'Erdös et Straus (PDF) (v francoščini), pridobljeno 5. maja 2013
- Monks, Maria; Velingker, Ameya A., »On the Erdös-Straus Conjecture: Properties of Solutions to its Underlying Diophantine Equation« (PDF), School of Computer Science, Univerza Carnegie Mellon (v angleščini), pridobljeno 5. maja 2013
- Mordell, Louis Joel (1967), Diophantine Equations, Academic Press, str. 287–290
- Obláth, Richard (1950), »Sur l'équation diophantienne 4/n = 1/x1 + 1/x2 + 1/x3«, Mathesis (v francoščini), 59: 308–316, MR 0038999
- Rosati, Luigi Antonio (1954), »Sull'equazione diofantea 4/n = 1/x1 + 1/x2 + 1/x3«, Boll. Un. Mat. Ital. (3) (v italijanščini), 9: 59–63, MR 0060526
- 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, MR 1269248
- Schinzel, André (1956), »Sur quelques propriétés des nombres 3/n et 4/n, où n est un nombre impair«, Mathesis (v francoščini), 65: 219–222, MR 0080683
- Sierpiński, Wacław Franciszek (1956), »Sur les décompositions de nombres rationnels en fractions primaires«, Mathesis (v francoščini), 65: 16–32, MR 0078385
- Suryanarayana, D.; Rao, N. Venkateswara (1965), »On a paper of André Schinzel«, J. Indian Math. Soc. (N.S.), 29: 165–167, MR 0202659
- Tao, Terence (7. julij 2011), »On the number of solutions to 4/p = 1/n_1 + 1/n_2 + 1/n_3]«, What's new (v angleščini)
- Terzi, D. G. (1971), »On a conjecture by Erdős-Straus«, Nordisk Tidskr. Informationsbehandling (BIT), 11 (2): 212–216, doi:10.1007/BF01934370, MR 0297703
- Vaughan, R. C. (1970), »On a problem of Erdős, Straus and Schinzel«, Mathematika, 17 (02): 193–198, doi:10.1112/S0025579300002886, MR 0289409
- Webb, William A. (1970), »On 4/n = 1/x + 1/y + 1/z«, Proceedings of the American Mathematical Society, Ameriško matematično društvo, 25 (3): 578–584, doi:10.2307/2036647, JSTOR 2036647, MR 0256984
- 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, MR 0177945
- 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, JSTOR 2044050, MR 0660589
Zunanje povezave
[uredi | uredi kodo]- Knot, Ron, Egyptian fractions (angleško)
- Tao, Terence, Counting the number of solutions to the Erdös-Straus equation on unit fractions, pridobljeno dne 2011-07-31. (angleško)
- Weisstein, Eric Wolfgang. »Erdős-Straus Conjecture«. MathWorld.
- Erdős-Strausova domneva na PlanetMath (angleško)