Helpoin ratkai­sematon pulma

Antti Hämäläinen HS, teksti

Sillä on monia toinen toistaan mystisempiä nimiä: 3x+1-ongelma, Collatzin konjektuuri, Kakutanin probleema, Hassen algoritmi, Syracusa-ongelma.

Mutta ei huolta, uhkaavista nimistä huolimatta sinun tarvitsee osata vain jakaa kahdella ja kertoa kolmella. Ei kuulosta kovin vaikealta.

Tämä matemaatikoita turhauttava, "vaarallinen" ongelma rakentuu seuraavan yksinkertaisen leikin ympärille:

Keksi päästäsi mikä tahansa positiivinen kokonaisluku.

• Jos se on parillinen, jaa se kahdella.

• Jos se on pariton, kerro se kolmella ja lisää yksi.

Tällä tavalla saat uuden luvun. Toista edellinen vaihe tälle uudelle luvulle. Jatka tätä niin kauan kunnes päädyt lukuun 1.

Menikö yli hilseen? Kokeillaan käytännössä.

Voit edelleen jatkaa samoilla säännöillä soveltaen sitä lukuun 1. Se on pariton, joten saat luvun 4. Päädyt ikuiseen silmukkaan.

Saatiin siis jono numeroita 10, 5, 16, 8, 4, 2, 1. Tätä kutsutaan Collatzin lukujonoksi.

Jos otat mielivaltaisen luvun voi lukujonon pituus kasvaa karmivan suureksi ennenkuin kuin se päättyy. Esimerkiksi jos aloitat luvusta 27, joudut laskemaan uuden luvun 112 kertaa ennen lukujonon päättymistä. Kokeile itse valitsemalla mikä tahansa luku:

Vaikuttaa yksinkertaiselta ja suoraviivaiselta. Missä piilee siis se ongelma?

Ongelma on lukujonon viimeinen luku 1. Voitko olla varma siitä että mikä tahansa ensimmäisenä valitsemasi luku päätyy yllä kuvatun prosessin tuloksena lopulta lukuun 1? Tämä yksinkertainen kysymys ajaa matemaatikot järjiltään, kuin seireenin laulu. Arkijärki kun voisi sanoa että lopputulos riippuu siitä, mistä luvusta aloittaa.

Kyseessä on matemaatikoiden kielellä konjektuuri, eli väite jonka arvellaan pitävän paikkansa, mutta jota kukaan ei ole vielä todistanut aukottomasti.

Ongelman ratkaisuun on historian saatossa valjastettu ihmisaivojen lisäksi myös tehokkaita tietokoneita. Konjektuuria on testattu käsittämättömän suurilla luvuilla tarkoituksena etsiä vastaesimerkki.

Vuoteen 2017 mennessä konjektuuria on testattu jokaisella luvulla joka on pienempi kuin 87×2⁶⁰, eli 100 304 170 900 795 686 912.

Yhtäkään vastaesimerkkiä ei ole löydetty.

Tietokoneen tuottama valtava todistusaineisto ei kuitenkaan riitä, ja tässä juuri piilee matemaattisen tarkkuuden armottomuus. Ns. näppituntuma ei riitä, vaikka sitä olisi kottikärryittäin.

Entäs jos otat vielä hieman suuremman luvun? Tai vielä yhden suuremman? Voitko olla varma että päädyt lukuun 1?

Todistuksen täytyy olla sellainen että yksinkertaisesti mitään ei jää epäilyksen varaan.

Mutta toisaalta yksikin vastaesimerkki voi osoittaa väitteen epätodeksi.

Lukuteoria on todellakin osoittanut että joskus ongelma voi olla luonteeltaan sellainen että vasta tarpeeksi suurilla luvuilla väite osoittautuu epätodeksi.

Visainen pähkinä kulkee monilla nimillä, mutta alkuperäisen idean kerrotaan saaneen vuonna 1937 saksalainen arvostettu matemaatikko Lothar Collatz (1910–1990). Monet tutkijat ja harrastelijat ovat sittemmin yrittäneet ratkaista houkuttelevan yksinkertaiselta vaikuttavaa ongelmaa, kenenkään siinä onnistumatta.

Sen sanotaan olevan vaarallinen, sillä tuotteliaskin matemaatikko voi siihen uppouduttuaan heittää hukkaan viikkokausia aikaa jonka voisi käyttää johonkin hyödyllisempään.

Muun muassa tutkija Paul Erdős (1913–1996) uhrasi ajatuksia ongelmalle.

Erdős on yksi maailmanhistorian tuotteliaimmista matemaatikoista joka julkaisi eläessään noin 1 500 artikkelia jopa 500 muun matemaatikon kanssa. Hän matkusti jatkuvasti, kertoman mukaan usein ilmaantuen yllättäen kollegoidensa ovelle ilmoittaen mielensä olevan avoin uusille haasteille.

Collatzin konjektuurista hänen kerrotaan sanoneen, ettei matematiikka ole valmis tämän kaltaisiin ongelmiin. Hän tarjosi 500 dollaria ratkaisun esittäjälle.

Viimeisimmän merkittävän panostuksen ongelmaan on antanut "matematiikan Nobel-voittaja", Fieldsin mitalisti Terence Tao vuonna 2019.

Kuten suurin osa matemaatikoista, hänkin keskittyy yleensä yleisluonteeltaan hedelmällisempään ja tuottavampaan perustutkimukseen.

Tao tarttui kuitenkin ongelmaan ja pystyi osoittamaan että lähes kaikki lähtöarvot päätyvät lopulta arvoon joka on lähellä lukua 1. Blogissaan julkaisemassaan esitelmässä hän kertoo tuloksensa olevan niin lähellä ongelman kokonaista ratkaisua kuin vain voi.

Mutta sekään ei riitä.

Kuinka sitten voidaan osoittaa että väite pätee lähes kaikille luvuille, mutta ei kaikille? Tälle on olemassa tarkka ja tekninen matemaattinen määritelmä, mutta esitetään asia yksinkertaistetulla esimerkillä:

Ennen presidentinvaaleja tehdyn mielipidemittauksen mukaan voidaan vetää johtopäätöksiä mahdollisesta vaalien lopputuloksesta, jos kyselyyn valitaan mukaan mahdollisimman hyvin väestöä kuvaava otos. Ei riitä siis että haastatellaan pelkästään Keskustan kannattajia. Mukaan tarvitaan kaikkien eri puolueiden kannattajia ja kaikkien sukupuolten edustajia vieläpä mahdollisimman laajasta ikähaarukasta.

Samalla tavoin luvuilla on omia "demografisia" erityispiirteitään: on parillisia, parittomia, kolmella jaollisia, jne. Jos valitaan tilanteeseen mahdollisimman sopiva lähtöjoukko lukuja, voidaan teoria todistaa päteväksi lähes kaikilla luvuilla.

Tieteen tekemiselle tyypillinen tapa ratkaista mahdottomalta tuntuvia ongelmia on tyytyä aluksi vähän vähempään, osittaiseen ratkaisuun.

Tämä voi tuoda sen verran lisävaloa aiheeseen, että täydellinen ratkaisu voidaan myöhemmin rakentaa edellisten yritysten päälle, niistä saadun uuden intuition perusteella.

Kuinka tämän kaltaista ongelmaa sitten ryhdytään ratkaisemaan? Tähän oikea henkilö vastaamaan on Turun yliopiston akatemiatutkija Kaisa Matomäki.

Matomäki on analyyttisen lukuteorian saralla ansioitunut arvostettu tutkija. Vuonna 2016 Matomäki ja hänen pitkäaikainen yhteistyökumppaninsa Maksym Radzwill palkittiin nuorille tutkijoille suunnatulla SASTRA Ramanujan palkinnolla heidän merkittävästä panoksestaan alkulukujen tutkimuksessa.

Saman palkinnon sai kymmenen vuotta aikaisemmin myös Terence Tao, ja Matomäki onkin julkaissut useita analyyttiseen lukuteoriaan syventyviä tieteellisiä julkaisuja yhteistyössä Taon kanssa.

Matomäki kertoo tuntevansa Collatzin konjektuurin, mutta ei ole käyttänyt merkittävästi aikaa siihen syventymiseen tai ratkaisuyritysten etsimiseen.

Hän kertoo kyllä vilkuilleensa läpi Taon viimevuotisen osittaisen todistuksen.

Tällaisten ongelmien ratkaisua voi lähteä hakemaan tarkastelemalla ongelman dynamiikkaa ja etsimällä mitä tahansa esiin nousevia säännönmukaisuuksia, Matomäki sanoo. Näihin säännönmukaisuuksiin tarttumalla voi ongelmaa yrittää lähteä purkamaan systemaattisesti.

Aikooko Matomäki seurata Taon jalanjälkiä ja lähteä yrittämään Collatzin konjektuurin ratkaisua?

"Tuskin", hän naurahtaa.

Mitä merkitystä ongelman ratkaisulla sitten olisi? Matomäki myöntää, että suoria sovelluksia ei mahdollisella ratkaisulla näytä tällä hetkellä olevan. Yksinään sitä voidaankin pitää lähinnä puhtaana älyllisenä haasteena, tavoiteltavana merkkipaaluna lukuteorian ymmärryksessä.

Sen ratkaisu voisi antaa suuntaa uusille matemaattisille löydöksille ja tuoda valoa muihin ongelmiin.

Tähän astiset ratkaisuyritykset ovatkin paljastaneet yhteyksiä muihin matematiikan osa-alueisiin.

Siinä on huomattu samankaltaisuuksia hyvin laajalti matemaattisissa tieteissä esiintyviin otuksiin, differentiaaliyhtälöihin. Näiden yhtälöiden avulla kuvataan dynaamisia, eli muuttuvia, ja jopa kaoottisia järjestelmiä.

Differentiaaliyhtälöihin törmää esimerkiksi lähes kaikkialla modernissa fysiikassa lähtien nesteen virtauksesta aina kvanttimekaniikkaan ja gravitaatioon asti. Niiden sovellukset ovat rajattomat, ja ne ovatkin aktiivisen tukimuksen kohteena.

"Niitä voidaan käyttää esimerkiksi sääennustemallien rakentamiseen tai viime aikoina ajankohtaisten epidemiamallien tutkimukseen", Kaisa Matomäki sanoo.

Niiden tarkoitus on yksinkertaisesti kuvata tilanteen muutosta ja mahdollisia loppuskenaarioita.

Esimerkiksi Collatzin konjektuurin tapauksessa lähtötilanne on jokin satunnaisesti valittu luku. Tämä luku muuttuu toisiksi kun sovellamme siihen pariton/parillinen -laskusääntöä.

Luku kasvaa ja pienenee ja saatujen uusien lukujen jono pitenee. Se vaikuttaa lähes kaoottiselta.

Lopputulos näyttäisi kuitenkin aina olevan luku 1, mutta silti prosessin toimintamekanismi on yksinkertaisesti vain niin kummallinen, että tästä ei voida olla sataprosenttisen varmoja.

Collatzin konjektuuri toimiikin esimerkkinä tilanteesta, missä viattoman yksinkertainen lähtöasetelma johtaa käsittämättömän monimutkaiseen dynamiikkaan.

Antti Hämäläinen HS, teksti, kuvitus, koodi

Juho Salminen HS, tuottaminen

JULKAISTU 20.6.2020 © Helsingin Sanomat