|
Jeg har skrevet en kort opgave om det åbne matematiske problem "Collatz-formodningen"/"3n+1-problemet". Og da jeg er en stor og mægtig flod der gavmildt strømmer rundt i landet og øser af sit krystalklare, nærende vand til folk og fæ, har jeg valgt at dele den med jer.
For at forstå problemet og og formodningen kræves kun folkeskole-matematik.
For at forstå de tekniske symboler og udtryk i opgaven kræves kun gymnasie-matematik.
Det er et matematisk emne som der forskes i, og som kræver meget avanceret matematisk værktøj.
Men opgaven er skrevet som en slags "videnskabs-journalistik", hvor der ikke dykkes for dybt ned i de tekniske detaljer, men fokuseres på de overordnede problem-stillinger.
God fornøjelse:
3n+1
Nogle af de mest interessante matematiske problemer er dem som er lette at formulere og forstå, men som er utroligt svære at bevise og trænge dybere ned i. ”Collatz-formodningen” eller ”3n+1-problemet” er præcis sådan et problem.
Betragt funktionen f fra de naturlige tal ind i de naturlige tal. Lad f være givet ved:
hvor vi definerer f(2)(n):=f(f(n)), f(3)(n):=f(f(f(n))) og f(k)(n) som den k’ende iteration af n.
Hvis vi vælger n=3 får vi følgen: 3,10,5,16,8,4,2,1,4,2,1…, dvs. f(7)(3)=1
Hvis vi vælger n=7 får vi følgen: 7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1… , dvs.f(16)(7)=1
Hvis vi vælger n=27 får vi følgen: 27,82,41,124,62,31,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1,4,2,1… dvs. f(111)(27)=1.
Hvis en iteration ender i 1 er det tydeligt at næste iteration vil være 4, så 2, så 1 og dernæst 4 igen. Der opstår altså en cykel af tallene 1, 4 og 2.
Et naturligt spørgsmål er nu, om alle naturlige tal n efter et endeligt antal anvendelser af funktionen f vil ende i cyklen (421).
Collatz-formodningen er, at for ethvert naturligt tal n findes der et naturligt tal k således at f(k)(n)=1 – altså at alle tal ender altså i cyklen (142) efter et endeligt antal iterationer.
Selvom det kun kræver simpel folkeskole-matematik at formulere og teste formodningen, har den ikke desto mindre vist sig utroligt svær at vise, og den er stadig (oktober 2008) et åbent problem.
Historie
Formodningen er opkaldt efter Lothar Collatz, som i 1930erne undersøgte tal-teoretiske funktioner. Nogle kilder angiver at han stillede problemet i 1937 , men han publicerede dog intet om emnet. Han diskuterede imidlertid emnet med sine kolleger og uddelte papirer om lignende tal-teoretiske funktioner til en matematik-kongres i Cambridge 1950 . 3n+1-problemet var med sikkerhed kendt i det matematiske fællesskab i 1950erne og Twaites hævder at have opdaget problemet i 1952 . Den første vigtige forsknings-artikel dedikeret til problemet blev udgivet i 1976 og i løbet af 1970erne dukkede problemet op fra den matematiske undergrund og flere og flere begyndte at arbejde med det. Det har medført en lind strøm af bevis-forsøg (specielt af ”hobby-matematikere”), dog alle uden held. Der er dog opnået flere vigtige resultater.
Resultater
Man har vha. computere testet utroligt mange tal, og indtil videre har alle vist sig at bekræfte Collatz-formodningen – dvs. alle tal er efter et vist antal iterationer endt i 1. Pr. 4. september 2008 har man testet alle naturlige tal op til 19·258 = 5.476.377.146.882.523.136 > 5.476·1018 vha. et ”distributed computer project” , dvs. et program der kører på en masse ”normale” computere og benytter sig af deres regnekraft til at teste tal. Dette resultat kunne tyde på, at formodningen holder, men det er selvfølgelig ikke et bevis og det udelukker ikke muligheden for at der gemmer sig et modeksempel et sted.
I det følgende vil vi undersøge funktionen T i stedet for f; T er en funktion fra de naturlige tal ind i de naturlige tal defineret ved:
Funktionen T er en ”optimeret” version af f hvor vi har skåret nogle af iterationerne væk ved at kombinere operationerne 3n+1 og n/2 når n er ulige (hvis n er ulige er 3n+1 altid lige).
Der er 3 muligheder for en bane (n, T(n), T2(n), … ):
1) Banen er konvergent, dvs. der findes et k så Tk(n) = 1
2) Der findes en ikke-triviel cyklisk bane, dvs. at følgen Tk(n) bliver periodisk, men der ikke findes et k, således at Tk(n) = 1
3) Der findes en divergent bane, dvs. limk->∞Tk(n) = ∞
Det er oplagt sandt, at for n>1 kan vi kun have T(k)(n) = 1 hvis der findes et x, således at T(x)(n)<n.
Def (stoppetid): Vi definerer nu det mindste positive x, således at T(x)(n)<n som stoppetiden s(n) for n, og lader s(n)= ∞ hvis der ikke findes noget x således at T(x)(n)<n. For eksempel: s(17)=2, da banen for 17 starter: (17 26 13 …) – det tager altså 2 iterationer for T at ”komme under” 17. Tilsvarende: s(15)=7, da banen for 15 starter (15 23 35 53 80 40 20 10 …).
Vi kan reformulere Collatz-formodningen som: ”Hvert naturligt tal n>1 har endelig stoppe-tid”. Hvis det gælder for alle tal større end 1 at de vil blive itereret ”ned under sig selv”, vil det betyde, at alle tal ”ryger ned” på 1 (hvis en iteration af 4 er under 4 og en iteration af 3 er under 3 og en iteration af 2 er under 2, så følger det oplagt at en iteration af 4 er 1).
Betragt mængden Sk af tal med stoppetid svagt mindre end k: Sk:={n: s(n) k}.
Terras viste, at denne mængde har begrænset asymptotisk tæthed F(k), dvs. at
Teorem (Terras) grænseværdien F(k) = limx->∞ #{n: n x og s(n) k}eksisterer. Desuden har vi, at
Teorem (Terras) F(k)à1 som kà∞, så næsten alle tal har endelig stoppetid.
Derefter har Lagarias vist, at
Teorem (Lagarias) 1–F(k) = limx->∞ #{n: n x og s(n)> k} 2-hk hvor h=0,05004…
Da 2-hkà0 for kà∞ betyder dette ca. ”næsten ingen tal har uendelig stoppetid”.
Def (samlet stoppetid): Hvis vi definerer det mindste positive x, således at Tx(n)=1 som den samlede stoppetid s∞(n) for n, kan vi definere størrelsen ptotal(x):
Def (ptotal): ptotal(x):=|{n: n x og s∞(n) ∞}| - ptotal(x) er altså antallet af tal lavere end eller lig med x som af T-funktionen bliver sendt ned i 1. Hvis ptotal(x)=x for alle x er Collatz-formodningen altså sand.
Crandall viste i 1978 Følgende teorem:
Teorem (Crandall) Der findes en positiv konstant c, således at ptotal(x)>xc for alle tilstrækkeligt store x’er.
I de følgende år udregnede J.W. Sander vha. en ”tree search method” denne konstant til c=0,057 og i 1990 til c=1/4. D.Applegate og J.C.Lagarias forbedrede metoden og beregnede vha. et computer-assisteret bevis konstanten til c=0,654 i 1995 . Det bedste resultat til dato er følgende opnået ved hjælp af ”Krasikow-uligheder”:
Teorem (Lagarias & Krasikow) : ptotal(x)>x0,84
Bevisforsøg
Der er dukket en del ”beviser” op for Collatz-formodningen, men indtil videre er ingen anerkendt af det matematiske fællesskab eller et seriøst tidsskrift med peer-review.
Under min informations-søgning/læsning på nettet om 3n+1 er jeg stødt på bevisforsøg af
Kawasaki Hiroyuki
Peter Schorer
Craig Alan Feinstein
Paul S. Bruckman
Ben Cawailing
Charles Cadogan
Kenneth Conrow
Et sjovt fællestræk for nogle af ”beviserne” for Collatz-formodningen er, at deres forfattere også har ”løst” andre store matematiske problemer/formodninger, som f.eks. P=NP (hævdet løst af Feinstein) eller Goldbachs formodning (hævdet løst af Paul S. Bruckman).
En af eksperterne i 3n+1 er Jeffrey C. Lagarias, der har specialiseret sig indenfor computervidenskab og analytisk algebraisk talteori og har udgivet en del artikler om 3n+1. Han har personligt kritiseret beviserne af Bruckman og Cadogan, hvilket er rimelig plausibel indikation på at de ikke holder.
Desuden har en vis Paul Stadfeld også skabt en hobby ud af at finde fejl i beviserne for Collatz-formodningen, og han har påpeget fejl hos de fleste af de nævnte forfattere.
Det er en rimelig sikker antagelse at et godkendt og solidt bevis vil skabe så meget opmærksomhed, at man ikke kan undgå at høre om det (i matematiske kredse). Det har ikke været tilfældet for nogen af de påståede beviser.
Fremtiden – afvisning af formodningen?
Paul Stadfeld har skrevet en artikel kaldet ”Blueprint for Failure – How to Construct a Counterexample to the Collatz Conjecture” hvor han prøver at beskrive hvordan et muligt modeksempel til Collatz-formodningen skulle se ud, og hvordan man leder efter dem.
Den kendte engelske matematiker John Horton Conway beviste i 1972 at en variation af 3n+1-problemet var algoritmisk uafgørligt, dvs. at en Turing-maskine ikke ville kunne afgøre problemet indenfor et endeligt antal skridt. Selvom han ikke beviser uafgørligheden af selve 3n+1-problemet men en generalisering af det, kunne det alligevel være en indikation på at 3n+1 er uafgørligt – Lagarias kalder f.eks. Conways bevis for et ”remarkable result” .
Konklusion
3n+1-problemet/Collatz-formodningen er et utroligt svært matematisk problem. Selvom problemet kan formuleres og forstås af en folkeskole-elev har matematiske forskere indenfor computer-videnskab, graf-teori, algebraisk talteori og mange andre grene af matematikken ikke kunnet nå frem til et endeligt resultat. Den kendte ungarnske matematiker Paul Erdõs sagde om problemet ”Mathematics is not yet ready for such problems.” . Lagarias skriver, at sværheden af 3n+1-problemet skyldes, at det er ”en deterministisk proces der simulerer tilfældig opførsel” . Hvis emnet rummer struktur kan det analyseres, men så forhindrer strukturen én i at vise, at systemet opfører sig tilfældigt. Og omvendt; hvis emnet er fuldstændig strukturløst og tilfældigt er der intet at analysere, og man kan ikke føre rigide matematiske beviser om det.
Man har testet utroligt mange tal vha. computere og kan teste lige så mange man vil. Sålænge alle tal bekræfter formodningen får man dog intet andet ud af disse tal-tjek end en slags sandsynliggørelse af formodningen og en retfærdiggørelse af at blive ved med at beskæftige sig med den.
Der er bevist nogle sætninger omkring bl.a. stoppetiden for tal, men disse resultater siger alle noget i stil med ”næsten alle tal har endelig stopptid” eller ”næsten ingen tal har uendelig stoppetid”. De fungerer altså også kun som en slags sandsynliggørelse af formodningen og en retfærdiggørelse af at blive ved med at bruge tid på at forsøge at bevise den.
Lagarias skriver, at de eksisterende metoder og teknikker i talteori og de andre grene af matematikken man har forsøgt at anvende på problemet ikke ser ud til at være stærke nok til at løse problemet. Desuden ser bekræftende beviser for formodningen (med de eksisterende teknikker) umulige ud – der vil formodentlig være større chance for at bevise negationerne.
Senest rettet af Zarathustra 30 okt 2008 19:13, rettet i alt 1 gang.
|
Log ind
Tilmeld
OSS
Søg
