Tervetuloa!



Hakemisto (Aiempien kirjoitusten pikahaku)


Viikkojuttu (Viikon pääpauhanta)


sunnuntai 13. toukokuuta 2012

Helppoa, vaan kun ei ratkea

Matematiikka on täynnä väittämiä, joita ei ole vielä onnistuttu todistamaan sen paremmin oikeiksi kuin vääriksikään. Tunnetuin matemaatikkoja piinannut väittämä oli Fermat'n suuri teoreema, joka esitettiin 1637 ja todistettiin oikeaksi vasta 1995. Teoreeman kiehtovuus oli siinä, että siinä esitetty ongelma oli niin yksinkertainen, että sen pystyi ymmärtämään kuka tahansa peruskoulumatematiikan edes seiskalla suorittanut.

Merkittävimpien todistamattomien väittämien todistamisesta tai kumoamisesta on perinteisesti luvattu palkintoja. Tunnetuimmat ovat vuosituhannen vaihteessa julkistetut millennium-palkinnot, jotka koskevat seitsemää todistamatonta väitettä. Jokaisen todistamisesta tai kumoamisesta on luvattu miljoonan dollarin palkinto. Itse asiassa yksi väittämistä on jo todistettu, mutta keksijä kieltäytyi rahasäkistä ideologisista syistä. Hatunnoston paikka lujasta luonteesta.

Kuudesta jäljellä olevasta ongelmasta tärkein on Riemannin hypoteesi, jota on yritetty turhaan todistaa satojen huippumatemaatikoiden voimin. Sivutuotteena on syntynyt merkittäviä uusia matemaattisia tuloksia. Väitetään erään matemaatikon myyneen sielunsa pirulle sillä ehdolla, että piru toimittaisi hänelle todistuksen. Parin viikon kuluttua piru palasi ja totesi: en onnistunut, mutta löysin seuraavan mielenkiintoisen lemman...

Esimerkkinä miljoonan taalan ongelmista Hodgen otaksuma: Olkoon X projektiivinen kompleksinen monisto. Tällöin jokainen Hodgen luokka X:ssä on rationaalinen lineaarikombinaatio X:n kompleksisten alivaristojen kohomologialuokista. Jaa ette ymmärtäneet mitään? No en minäkään.

Heprealta vaikuttavien teoreemojen vastapainoksi matematiikassa on lukuisia sellaisia yhä selvittämättömiä ongelmia, jotka kykenee täysin maallikkokin ymmärtämään. Yrittäkää vaikka itse, huolella lukien onnistuu. Tässä helpolta vaikuttavien, mutta yhä ratkaisemattomien ongelmien top 10. Muuten puolueettomasti valitussa järjestyksessä, mutta listaykkönen on kyllä täysin subjektiivisesti omiin mieltymyksiin pohjautuva päätös.

10. Lychrelin luku
Palindromiksi kutsutaan sellaista sanaa tai lukua, joka on sama, luettiin se sitten oikealta vasemmalle tai vasemmalta oikealle. Esimerkiksi 7337 on palindromiluku. Lychrelin luku on sellainen luku, joka ei muutu palindromiluvuksi, vaikka seuraavaa proseduuria toistettaisiin loputtomiin: lisätään lukuun se itse, mutta oikealta vasemmalle luettuna. Esimerkiksi luku 59 (ja samalla tietysti myös 95) vaatii kolme iteraatiota muuttuakseen palindromiluvuksi: 59 + 95 = 154, 154 + 451 = 605, 605 + 506 = 1111, joka on palindromiluku. Ei tiedetä, onko Lychrelin lukuja olemassa, vai muuttuvatko kaikki luvut palindromeiksi riittävän monella iteraatiolla. Ongelmasta tekee kiehtovan se, että pienin ehdokas Lychrelin luvuksi on niinkin vaatimaton kuin 196 ja on olemassa toistakymmentä muutakin kolminumeroista ehdokasta. Lukua 196 on iteroitu 300 miljoonaa numeroa käsittäväksi löytämättä palindromia. Sen vastapainoksi ne luvut, joiden tiedetään muuttuvan palindromeiksi, muuttuvat sellaisiksi varsin pian. Kymmentätuhatta pienemmistä luvuista pisimpään vie luvulta 89, vain 24 iteraatiota ja lopputuloksena ainoastaan 13-numeroinen luku. Varsin vaatimatonta verrattuna 300 miljoonaa numeroa käsittävään luvun 196 iteraatioon, joka ei vieläkään väänny palindromiksi.

9. Gilbreathin konjektuuri
Alkuluvut ovat lukuja, jotka ovat jaollisia vain itsellään ja ykkösellä. Ensimmäiset alkuluvut ovat 2, 3, 5, 7, 11, 13, 17, 21, 23, 29, ... . Jos näistä luvuista lasketaan kahden peräkkäisen erotuksen itseisarvo, saadaan uusi lukujono 1, 2, 2, 4, 2, 4, 2, 4, 6, ... (eli |3-2|, |5-3|, |7-5|, |11-7| jne). Seuraava askel tehdään tällä uudella lukujonolla: 1, 0, 2, 2, 2, 2, 2, 2, 4, ... (eli |2-1|, |2-2|, |4-2|, |2-4| jne). Kuudes lukujono, josta on laskettu edellisen lukujonon peräkkäisten termien erotuksen itseisarvo, alkaa 1, 2, 0, 0, 2, ... . Väittämän mukaan jokaisen jonon ensimmäinen luku on yksi, jonka automaattinen seuraus on se, että toinen luku on aina 0 tai 2. Sen tiedetään pitävän paikkansa muutamalle sadalle miljardille ensimmäiselle alkuluvulle, mutta oikeaksi sitä ei ole todistettu.

8.Keplerin konjektuuri
Kun palloja pakataan mahdollisimman tiiviisti kolmiulotteisesti, väliin jää silti tyhjää tilaa niiden kaarevuuden takia. Keplerin konjektuurin mukaan pallot kykenevät parhaallakin pakkauksella täyttämään tilavuudesta korkeintaan hieman yli 74 prosenttia. Tarkka arvo on pii jaettuna neliöjuuri 18:lla. Hauskaksi asian tekee se, että väittämä on luultavasti jo todistettu vuonna 1998. Valitettavasti todistus on tehty väsytystekniikalla, mikä tarkoittaa ongelman pilkkomista lukuisiin pienempiin palasiin, jotka todistetaan yksi kerrallaan. Keplerin konjektuurin tapauksessa tämä tarkoittaa noin sataatuhatta palasta, jotka on todistettu tietokoneohjelmalla. Kukaan ei ole vielä käynyt todistusta käsipelissä läpi, se kun käsittää 250 sivua huomautuksia ja kolme gigabittiä tietokonekoodia tuloksineen.

7. Täydelliset luvut
Täydelliseksi luvuksi kutsutaan lukua, joka on yhtä suuri kuin sen itseään pienempien tekijöiden summa. Esimerkiksi luku 28 on täydellinen luku, koska sen itseään pienemmät tekijät ovat 1, 2, 4, 7 ja 14. 1 + 2 + 4 + 7 + 14 = 28. Sen sijaan esimerkiksi 24 ei ole täydellinen luku, koska sen itseään pienemmistä tekijöistä tulee 1 + 2 + 3 + 4 + 6 + 8 + 12 = 36. Tällaista lukua kutsutaan runsaaksi luvuksi, koska kyseinen summa on lukua itseään suurempi. Vastaavasti luku 26 ei myöskään ole täydellinen luku, koska 1 + 2 + 13 = 16. Tällaista lukua kutsutaan vajaaksi luvuksi, koska summa on lukua itseään pienempi. Neljä ensimmäistä täydellistä lukua tunnettiin jo antiikin aikana. Ne ovat 6, 28, 496 ja 8128, kaikki parillisia. Nyttemmin täydellisiä lukuja on löydetty paljon lisää, mutta ratkaisematta on yhä, onko olemassa suurinta täydellistä lukua vai onko niitä äärettömästi, samoin kuin mm. se, onko olemassa parittomia täydellisiä lukuja.

6. Parittomat oudot luvut
Edellisessä kohdassa mainittiin runsaat luvut, jotka ovat siis lukuja joiden tekijöiden summa on lukua itseään suurempi. Useimpien runsaiden lukujen tekijöistä saadaan kuitenkin laskettua luku itse, mikäli tekijöistä jätetään pois sopivat. Esimerkiksi runsas luku 24 = 4 + 8 + 12, jolloin sen tekijöistä on jätetty pois 1, 2, 3 ja 6. Mikäli temppu ei jollain luvulla onnistu, kyseistä lukua kutsutaan oudoksi luvuksi. Pienimmät oudot luvut ovat 70, 836, 4030, 5830, ... . Ei tiedetä, onko olemassa parittomia outoja lukuja.

5. Erdösin-Szekeresin konjektuuri
Ongelma sai alkunsa väittämästä, jonka mukaan mikä tahansa tasossa oleva viiden pisteen joukko, jossa ei ole yhtään kolmen pisteen samalla suoralla olevaa joukkoa, sisältää neljän pisteen joukon, joka muodostaa nelikulmion, jossa ei ole yhtään yli 180 asteen kulmaa. (Kannattaa hahmottaa piirtämällä.) Väittämän yleistyksen mukaan mille tahansa luvulle N on olemassa tietty määrä pisteitä käsittävä tason pistejoukko (ei kolmea samalla suoralla olevaa pistettä), josta sopivasti valitsemalla saadaan N-kulmainen monikulmio ilman yli 180 asteen kulmia. Mikäli N = 3, riittää kolme pistettä. Mikäli N = 4, vaaditaan enintään viisi pistettä (kuten alkuperäinen väittämä totesi). N = 5, enintään 9 pistettä, N = 6, enintään 17 pistettä. Konjektuurin mukaan mille tahansa arvolle N riittää maksimissaan 1 + 2N-2 pistettä. Vuonna 1935 esitetty väittämä on yhä todistamatta.

4. Collatzin konjektuuri
Konjektuurin esitti ensimmäisenä saksalainen matemaatikko Lothar Collatz vuonna 1937. Historianharrastajat kiinnittänevät huomiota kansallisuuden ja vuosiluvun yhdistelmään – eivät Natsi-Saksasta kaikki tiedemiehet paenneet. Konjektuuri voidaan ilmaista sanallisesti seuraavasti: Otetaan mikä tahansa positiivinen kokonaisluku. Mikäli luku on parillinen, se jaetaan kahdella ja saadaan uusi kokonaisluku. Mikäli luku taas on pariton, se kerrotaan kolmella ja lisätään saatuun tuloon yksi. Näin on saatu uusi luku, jolle tehdään sen parillisuudesta riippuen jompikumpi edellä mainituista toimenpiteistä. Lähtöarvosta riippumatta päädytään jossakin vaiheessa ikuiseen silmukkaan 4, 2, 1, 4, 2, 1, 4, 2, 1, … .
Esimerkkinä luku 37 lähtöarvona: 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, … .
Unkarilaisen matemaatikko Paul Erdösin kuultua konjektuurista hänen kerrotaan kalvenneen ja mutisseen jotakin siihen suuntaan, että matematiikka ei yksinkertaisesti ole vielä valmis käsittelemään noin vaikeita ongelmia. Collatzin (k. 1990) oppilas Gerhard Opfer julkaisi konjektuurille todistuksen 2011, mutta tapahtui odotetusti. Tarkistusluennassa löydettiin ”hupsis” ja toisin kuin Wilesillä Fermat’n teoreeman kanssa, kyseinen porsaanreikä osoittautui ainakin toistaiseksi mahdottomaksi paikata. Sarjakuva xkcd tosin muotoili konjektuurin hieman toisin...

3. Suurimmat alkulukukaksoset
Alkulukukaksosiksi nimitetään sellaisia alkulukuja, joiden erotus on kaksi. Esimerkiksi 11 ja 13 ovat alkulukukaksoset. Eukleides todisti jo yli 2000 vuotta sitten, että suurinta alkulukua ei ole olemassa, vaan ne jatkuvat loputtomiin. Sen sijaan ei vielä tiedetä, onko alkulukukaksosia loputtomasti. On siis mahdollista, että jossain kaukaisuudessa ovat olemassa suurin mahdollinen alkulukukaksospari. Pienimmät alkulukukaksoset ovat 3 ja 5, seuraavat 5 ja 7. Viisi onkin ainoa luku, joka voi esiintyä kahdessa alkulukukaksosparissa. Lukijan tehtäväksi jätetään todistaa, miksi. Ei ole vaikeaa.

2. Goldbachin konjektuuri
Konjektuuri on saanut nimensä preussilaisen matemaatikon Christian Goldbachin vuonna 1742 suurelle Leonard Eulerille lähettämässä kirjeessä muotoilemasta ongelmasta. Goldbachin muotoilu tosin oli hieman erilainen kuin nykyinen, joka kuuluu: Jokainen kahta suurempi parillinen luku on kahden alkuluvun summa.
Esimerkiksi 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5 ja 48 = 11 + 37. Joillekin löytyy useita vaihtoehtoja, kuten 48 = 7 + 41 = 5 + 43 = 17 + 31 = 19 + 29.
Kirjan Petros-setä ja Goldbachin konjektuuri kustantaja tarjosi miljoonan dollarin palkinnon sille, joka julkaisee todistuksen kahden vuoden kuluessa kirjan julkaisemisesta. Lunastamatta jäi.

1. Yksinäisen juoksijan konjektuuri
Yksinäisen juoksijan konjektuuri kuuluu seuraavasti: Olkoon meillä rata, jonka pituus on a. Rataa kiertää k + 1 (huom. k toimisi periaatteessa, mutta aiheuttaisi teknisen ongelman) juoksijaa. Hetkellä t = 0 kaikki lähtevät samasta pisteestä kiertämään rataa vakionopeudella siten, että jokaisella juoksijalla on eri nopeus. Kutsutaan juoksijaa yksinäiseksi hetkellä t, mikäli hänen etäisyytensä (rataa pitkin mitaten) lähimpään toiseen juoksijaan on vähintään a/(k + 1). Väitteen mukaan jokainen juoksija on jossakin vaiheessa yksinäinen.
Esimerkki kahdella juoksijalla normaalilla 400 metrin pituisella radalla: juoksija on yksinäinen silloin, kun etäisyys toiseen juoksijaan on vähintään 400/2 = 200 metriä. Mikäli juoksijat etenevät eri nopeudella, tämä tapahtuu silloin – ja vain silloin – kun he ovat täsmälleen radan vastakkaisilla puolilla. On varsin ilmeistä, että näin tapahtuu ajan myötä. Mikäli juoksijoita on esimerkiksi neljä, juoksija on yksinäinen silloin kun etäisyys toiseen juoksijaan on vähintään 400/4 = 100 metriä. Sivumennen sanoen on periaatteessa mahdollista (ja myös suhteellisen helppoa, vähän jaollisuuden alkeita) löytää sellaiset esimerkkinopeudet, että yksi juoksijoista on jossain vaiheessa jopa 200 metrin päässä lähimmästä juoksijasta eli kolme muuta juoksijaa ovat samassa nipussa neljännen ollessa täsmälleen vastakkaisella puolella rataa. Mutta minimivaatimus on siis tuo 100 metriä tässä tapauksessa ja jossakin vaiheessa jokainen neljästä juoksijasta todella on yksinäinen.
Konjektuuri on osoittautunut todella piinaavaksi. Tähän mennessä se on onnistuttu todistamaan päteväksi vasta seitsemän tai harvemman juoksijan tapauksessa. Joskus pitäisi piruuttaan testata Huitsinnevadan urheilukentällä vapaaehtoisilla koekaniineilla...

11 kommenttia:

Tomi kirjoitti...

Kiitos taas mukavasta listauksesta.
Tosin kaikki olivat minulle ennestään tuttuja.

Yrjöperskeles kirjoitti...

Ja minulle eivät olleet tuttuja mitkään. Mutta joskus on kiva lukea sujuvasti sellaista, mistä itse on ihan pihalla.

Anonyymi kirjoitti...

Jee, taas listauksia pienen tauon jälkeen. Lisää näitä!

Tomi kirjoitti...

Goldbachin konjektuuria on käytetty skeprtisessä kirjallisuudessa UFO-kontaktihenkilöitä vastaan.

Jos kerran tänne pystyy teknisesti edistynyt laji matkudstamaan, toki he ratkaisevat myös Goldbachin konjektuurin. Goldbachin konjektuuri on tässä hyvä, koska kuka tahansa pulliainen pystyy sen selittämään.

Jaska Brown kirjoitti...

Yrjö: Ihan mielenkiinnon vuoksi kerron, että satun tietämään joitakin tällaisia ongelmia käytetyn syrjäytymässä olleiden, mutta muuten fiksunoloisten nuorten herättelijöinä. Kuulemma turhautuneet mutta älykkäät saattavat innostua, kun heille selittää esim listakakkosen (Goldbach) ja nelosen (Collatz) ja kertoo, että noita ei muuten kukaan ole ratkaissut.

Tomi: Vaan entäpä jos Goldbach totetuttaakin Gödelin teoreeman? Eli se olisi siis väittämä, jonka totuusarvoa ei voida selvittää. Turingin todistuksen mukaanhan todistettavuutta ei voi päätellä a priori, joten... Toki jos pienet vihreät miehet todistuksen esittävät, niin asiahan on pihvi.

Tomi kirjoitti...

Jaska Goldbachin konjektuuri ei ole luultavastikkaan Gödelin teoreeman mukainen väittämä.
Heikko Goldbachin konjektuuri (alkuperäinen Goldbachin konjektuuri) on todeistettu pitävän paikkansa suurilla luivuilla (jostain luvusta N lähtien) joten testaamalla kaikki lukua N pienemmät luvut voidaan todeta väitteen paikkansa pitävyys tai löytää vasta esimerkki.

Kaiken kaikkiaan Goldbachin konjektuurissa väitteen paikkansa pitämättömyys merkitsisi vastaesimerkin olemassa oloa, joten se ei voi olla Gödelin lauseen mukainen väittämä.

Jaska Brown kirjoitti...

No onhan se tietysti "ilmeistä", että Goldbach on tosi, perusteluita löytyy paljonkin. Vaan ei vielä todistusta.
Heikko konjektuuri on osoitettu todeksi suurilla luvuilla, mutta välimaasto on vielä sen verran laaja, että sitä ei millään tietokoneajoilla pysty tutkimaan järjestelmällisesti. Ja vaikka pystyisikin, ei se sanoisi mitään vahvan konjektuurin totuusarvosta - sen sijaan vahvan konjektuurin oikeaksi todistamisesta seuraisi korollaarina heikon oikeassa oleminen (eli lisätään parilliseen lukuun kolme ja se on siinä).
Jos vahva konjektuuri on epätosi, niin sitten esimerkki on löydettävissä - mutta se voidaan löytää myös alueelta, jossa heikko on todistettu todeksi. Mikäli onnistutaan heikon konjektuurin osalta todistamaan, että lisättävä luku voi aina olla kolme, on vahva konjektuuri tosi aina silloin kun heikkokin, mutta tätäpä ei ole tehty mistään rajasta alkaen.
JOS vahva konjektuuri on tosi MUTTA Gödelin teoreeman toteuttava, niin sitä ei sen paremmin voi todistaa kuin löytää vastaesimerkkiäkään (koska tällä oletuksella vastaesimerkkiä ei tietenkään ole).
Eli Goldbachin vahva konjektuuri voi olla Gödelin epätäydellisyyslauseen kummitus, mutta heikko konjektuuri ei mainitsemastasi syystä voi sellainen olla.

Tomi kirjoitti...

Jaska, Goldbachin konjektuuri ei missaan nimessa ole Godelin teoreeman mukainen vaite. Luonollinen luku voidaan esittaa alkulukujen summana tai sitten ei. Emme voi luoda jarjestelmaa luonnollisista luvuista joissa Goldbachin konjektuurin totuusarvo jaa kyseen alaiseksi.


Jos otetaan mika tahansa luonnollinen luku n, niin on periaatteessa mahdollista tarkistaa toteuttaako se Goldbachin konjektuurin vai ei (vaihtoehtoja on aarellinen maara).

Siis Goldbachin konjektuuri on totta tai ei, eika mitaan silta valilta.

Tomi kirjoitti...

Jaska:"JOS vahva konjektuuri on tosi MUTTA Gödelin teoreeman toteuttava, niin sitä ei sen paremmin voi todistaa kuin löytää vastaesimerkkiäkään (koska tällä oletuksella vastaesimerkkiä ei tietenkään ole)."

Talloin Goldbachin konjektuuri on totta.

Godelin lause sanoo, etta aksioomajarjestelmat eivat ole taydellisia, vaan kukin riittavan rikas aksioomajarjestelma sisaltaa tosivaittamia joita ei voi aksioomista lahtien todistaa. Kontinuumihypoteesi on ainut tunnettu Godelin lauseen mukainen tosivaittama. Jarjestelmat joissa kontinuumihypoteesi ei ole tosi eivat tuota mitaan hedelmallista.

Luonnolliset luvut eivat ole tallainen jarjestelma.

Jaska Brown kirjoitti...

Jos otetaan mika tahansa luonnollinen luku n, niin on periaatteessa mahdollista tarkistaa toteuttaako se Goldbachin konjektuurin vai ei (vaihtoehtoja on aarellinen maara).
Niin on, mutta luonnollisia lukuja on äärettömästi.
Huumoria: Miten fyysikko todistaa, että kaikki ykköstä suuremmat parittomat luvut ovat alkulukuja? No, helppoa. 3 on alkuluku, 5 on alkuluku, 7 on alkuluku, 9 on kokeessa tapahtunut virhemittaus, 11 on alkuluku, 13 on alkuluku... no eiköhän tämä ollut tässä, koetulokset ovat kiistattomat.

Tässä Institute of Advanced Study:n lisätietoa asiasta, enemmän kaunokirjalliselta puolelta suosittelen muuten luettavaksi kirjaa Petros-setä ja Goldbachin hypoteesi, jonka kirjoittaja on kreikkalainen huippumatemaatikko.

Muuta kantaa en nyt halua Goldbach-Gödel -syndroomaan ottaa.

Tomi kirjoitti...

Vielä Goldbachin konjektuurista ja Gödelin teoreemasta.

Jos Goldbachin konjektuuri olisi Gödelin teoreeman mukainen väittämä, niin tällöin olisi mahdollista luoda kaksi eri luonnollisten lukujen järjestelmää. Toinen, jossa Goldbahin konjektuuri on voimassa ja toinen, jossa se ei ole.
Eli jälkimmäisessä järjestelmässä olisi luonnollinen luku n jota ei voitaisi esittää kahden alkuluvun summana. Tämä on ristiriidassa luonnollisten lukujen yksikäsitteisyyden kanssa.