Erdős-Strausova domneva

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Erdős-Strausova domneva je v matematiki domneva, ki za vsako celo število n > 1 predvideva, da lahko racionalno število 4/n izrazimo 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:

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

Brez poseganja v splošnost lahko domnevamo, da velja x \leq y \leq z \!\, , oziroma še ostreje x < y < z \!\, . Zato ti enotski ulomki načeloma predstavljajo egipčanski ulomek za število 4/n, saj drugače lahko vedno preprosto rečemo, da trivialno velja:

 \frac{4}{n} = \frac{1}{n/2} + \frac{1}{n} + \frac{1}{n} \!\, .

Za n = 2 je takšna trivialna rešitev tudi edina:

 \frac{4}{2} = \frac{1}{1} + \frac{1}{2} + \frac{1}{2} \!\, .

Za n = 3 in 4 na primer obstaja ena netrivialna rešitev:

 \frac{4}{3} = \frac{1}{1} + \frac{1}{4} + \frac{1}{12}, \qquad \frac{4}{4}=\frac{1}{2}+\frac{1}{3}+\frac{1}{6} \!\, ,

za n = 5 dve rešitvi:

 \frac{4}{5} = \frac{1}{2} + \frac{1}{4} + \frac{1}{20} = \frac{1}{2} + \frac{1}{5} + \frac{1}{10} \!\, ,

za n = 6 pa pet rešitev:

 \frac{4}{6} = \frac{1}{2} + \frac{1}{7} + \frac{1}{42} = \frac{1}{2} + \frac{1}{8} + \frac{1}{24} =
\frac{1}{2} + \frac{1}{9} + \frac{1}{18} = \frac{1}{2} + \frac{1}{10} + \frac{1}{15} =
\frac{1}{3} + \frac{1}{4} + \frac{1}{12} \!\, ,

ki sicer niso najmanjše rešitve, saj je še edina dvočlena rešitev:

 \frac{4}{6} = \frac{1}{2} + \frac{1}{6} \!\, ,

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 veljavnost 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 naslabš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 enačbo 4/n = 1/x + 1/y + 1/z z obeh strani pomnožimo z nxyz, dobimo enakovredno obliko enačbe za problem:

 4xyz = n(xy+xz+yz) \!\, . [6]

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 jih dobimo s kongruenco po modulo za vsako možno praštevilo. Očitno ima to načelo za Erdős-Strausovo domnevo malo smisla, saj lahko enačbo 4xyz = n(xy + xz + yz) preprosto rešimo s kongruenco po modulu poljubnega praštevila. navkljub temu so se modularne enakosti pokazala za zelo pomembno orodje pri raziskovanju domneve.

Za vrednosti n, za katere veljajo določene kongruenčne zveze, lahko najdemo razvoj za 4/n takoj kot primer polinomske enakosti. Če je na primer n ≡ 2 (mod 3), je razvoj 4/n enak:

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

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 dasta razvoja v treh ali manj členih, tiste, ki so kongruentne 1 (mod 24).

Enačba:[4]

 \frac{4}{3k+2} = \frac{1}{3k+2} + \frac{1}{k+1} + \frac{1}{(k+1)(3k+2)} \!\,

da posebej na primer veljavnost domneve za n = 3k + 2 = 2, 5, 8, 11, 14, 17, ... (za vrednosti k = 0, 1, 2, 3, 4, 5, ...), (OEIS A016789). Domneva velja 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, niso v nasprotju z Mordellovim rezultatom, vendar je 1 kvadratni ostanek po modulu 3, in rezultat dokazuje, da lahko obstaja podobna enakost za vrednoti 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 np (mod q) - če bi bilo to mogoče, nobeno praštevilo p ne bi moglo biti protiprimer za domnevo in domneva bi bila resnična.

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 resničnost 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 postavimo a = b = 1, dobimo 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:

 \frac{4}{4k+1} = \frac{1}{2k} + \frac{1}{2k} - \frac{1}{k(4k+1)} = \frac{1}{k} - \frac{1}{k(4k+1)} \!\,

in:

 \frac{4}{4k-1} = \ldots = \frac{1}{k} + \frac{1}{k(4k-1)} \!\, .

Za lihi n je možna tričlena rešitev z enim negativnim členom:[3]

 \frac{4}{n}=\frac{1}{(n-1)/2}+\frac{1}{(n+1)/2}-\frac{1}{n(n-1)(n+1)/4} \!\, .
Zgleda
1.  n = 97 \, :
 \frac{4}{97} = \frac{1}{(97-1)/2}+\frac{1}{(97+1)/2}-\frac{1}{97(97-1)(97+1)/4} 
                      = \frac{1}{48}+\frac{1}{49}-\frac{1}{228144} \!\, .
2.  n = 99 = 3^{2} \cdot  11 \, :
 \frac{4}{99} = \frac{1}{3^{2}} \cdot \frac{4}{11} = \frac{1}{3^{2}} \left[ \frac{1}{(11-1)/2}+\frac{1}{(11+1)/2}-\frac{1}{11(11-1)(11+1)/4} \right]
                      = \frac{1}{45}+\frac{1}{54}-\frac{1}{2970} \!\, .

Posplošitve[uredi | uredi kodo]

Posplošena različica domneve pravi, da za poljubni pozitivni k obstaja takšno število N, da za vse nN obstaja rešitev diofanstke enačbev v pozitivnih celih številih:

 \frac{k}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z} \!\, .

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, lahko po analogiji za problem lihega požrešnega razvoja za egipčanske ulomke vprašamo 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:

 \frac{3}{n} = \frac{1}{x} + \frac{1}{y} \!\,

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}, ...:
 \frac{3}{25} = \frac{1}{10} + \frac{1}{50} \!\,
 \frac{3}{55} = \frac{1}{20} + \frac{1}{220} = \frac{1}{22} + \frac{1}{110} \!\,
 \frac{3}{85} = \frac{1}{30} + \frac{1}{510} = \frac{1}{34} + \frac{1}{170} \!\,
 \frac{3}{115} = \frac{1}{40} + \frac{1}{920} = \frac{1}{46} + \frac{1}{230} \!\,
 \frac{3}{121} = \frac{1}{44} + \frac{1}{484} \!\,
 \frac{3}{145} = \frac{1}{50} + \frac{1}{1450} = \frac{1}{58} + \frac{1}{290} \!\,
 \frac{3}{175} = \frac{1}{60} + \frac{1}{2100} = \frac{1}{70} + \frac{1}{350} = \frac{1}{100} + \frac{1}{140} \!\,
 \frac{3}{187} = \frac{1}{66} + \frac{1}{1122} =  \frac{1}{68} + \frac{1}{748} \!\, \cdots

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, ...
 \frac{3}{2} = \frac{1}{1} + \frac{1}{2} \!\,
 \frac{3}{5} = \frac{1}{2} + \frac{1}{10} \!\,
 \frac{3}{11} = \frac{1}{4} + \frac{1}{44} \!\,
 \frac{3}{17} = \frac{1}{6} + \frac{1}{102} \!\, \cdots

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:

 \frac{3}{4} = \frac{1}{2} + \frac{1}{4} \!\,
 \frac{3}{15} = \frac{1}{6} + \frac{1}{30} \!\,
 \frac{3}{33} = \frac{1}{12} + \frac{1}{132} \!\,
 \frac{3}{51} = \frac{1}{18} + \frac{1}{306} \!\,
 \frac{3}{77} = \frac{1}{26} + \frac{1}{2002} = \frac{1}{28} + \frac{1}{308} = \frac{1}{42} + \frac{1}{66} \!\, \cdots

Sklici[uredi | uredi kodo]

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]