maanantai 8. toukokuuta 2017

Melkein kaikki olennainen alkuluvuista

Alkuluvut ovat lukujen teorian olennaisin rakennuspalikka, joihin viittaan itsekin tämän tästä. Kuitenkaan niiden ominaisuudet eivät ole itsestäänselviä, joten tässä on kevyt referenssi/pikakertaus siihen, miksi alkuluvut ovat Iso Juttu. Joukossa pitäisi olla uusia tiedonmurusia lukion lukuteorian käyneillekin. Ota hyvä asento, niin aloitetaan!

Mistä "luku" tulee?

Lukuteoriasta puhuessa tehdään yleensä hiljainen taustaoletus: luku tarkoittaa luonnollista lukua. Luonnolliset luvut ovat äärettömän iso kourallinen "luonnolliselta" tuntuvia lukuja, ja pitkän matikan lukijat tunnistavat sen myös symbolista $\mathbb{N}$. Kaikki ovat sitä mieltä, että $1, 2, 3$ ja niin edelleen ovat luonnollisia lukuja. Siitä ei olla yhtä mieltä, onko $0$ luonnollinen luku — tässä tekstissä jätän nollan pois, koska se mutkistaisi asioita turhaan.

Siitä ollaan yksimielisiä, että yksikään näistä ei ole luonnollinen luku: $0.3$, $-1$, $\dfrac 3 2$, kökköfantti ja $\sqrt{-1}$.

Mistä "alku" tulee?

Jokainen luku voidaan esittää kertomalla alkulukuja yhteen. Esimerkiksi $60$ on sama kuin $2 \cdot 2 \cdot 3 \cdot 5$. Mikä tärkeintä, jokaista lukua vastaa tasan yksi alkulukujen tulo. Tämä on niin tärkeä juttu, että se on nimetty aritmetiikan peruslauseeksi. Luvun jakamista sen muodostaviin alkulukuihin kutsutaan alkutekijöihin jakamiseksi tai alkutekijähajotelmaksi.

Mitkä sitten ovat alkulukuja?

Alkuluvut ovat niitä lukuja, jotka eivät ole jaollisia millään muulla luvulla. Niiden alkutekijähajotelma koostuu vain luvusta itsestään: esimerkiksi $7 = 1 \cdot 7$.

Alkulukujen löytämiseen on yksinkertainen menetelmä, harvinaisen vaikeanimisen antiikin kreikkalaisen mukaan nimetty Eratostheneen seula. Se toimii näin: Listataan lukuja kakkosesta eteenpäin. Ympyröidään kakkonen ja vedetään yli kaikki kakkosen monikerrat. Sitten ympyröidään kolmonen ja vedetään yli kolmosen monikerrat. Jatketaan ensimmäisen jäjellä olevan luvun ympyröimistä ja muiden ylivetämistä, kunnes kaikki luvut on käyty läpi. Ympyröidyt luvut ovat alkulukuja, koska ne eivät ole jaollisia millään niitä pienemmällä luvulla.

Animaatio Eratostheneen seulasta.

(Itse asiassa kaikkia lukuja ei tarvitse käydä läpi. Kuinka monen luvun ylivetämisen jälkeen kaikki jäljellä olevat luvut ovat alkulukuja? Miksi?)

Hetkinen, onko ykkönen alkuluku?

Ei.

Osa matematiikasta toimisi, vaikka ykkönen olisikin alkuluku, mutta aritmetiikan peruslauseella olisi vaikeampaa: koska ykkösellä kertominen ei muuta lukua, jokaiselle luvulle voisi kirjoittaa äärettömän monta alkutekijähajotelmaa, jotka eroavat toisistaan vain ykkösten määrässä. Myös Eratostheneen seula hajoaisi, koska ykkösen ympyröinnin jälkeen yliviivattaisiin... niin, ihan kaikki.

Siksi on sovittu, ettei ykkönen ole alkuluku. Se on aivan omaa luokkaansa ja omaa koko joukon jänniä erikoisominaisuuksia. Se ei muuta toista lukua kertolaskussa ja sitä yhteenlaskemalla saadaan kaikki luonnolliset luvut. Tietyllä tavalla se on kaikkien lukujen alku.

Onko alkulukuja äärettömästi?

On, ja se tarina on puhkikaluttu matematiikan tunneilla. Vaka vanha Eukleides esitti sen näin:

Oletetaan, että alkulukuja on rajallinen määrä. Kerrotaan ne kaikki keskenään ja plussataan siihen ykkönen. Luku olisi muuten jaollinen kahdella, mutta lisätty ykkönen estää sen. Samoin käy kolmoselle, vitoselle ja niin edelleen aina viimeiseen alkulukuun asti. Koska keksimämme luku ei siis ole jaollinen millään niistä, se on alkuluku, mutta samalla suurempi kuin oletettu viimeinen alkuluku. Tämä on ristiriita, joten alkulukuja ei voi olla rajallisesti — niitä on pakko olla äärettömän monta.

Ne kuitenkin harvenevat suurempiin lukuihin mennessä?

Kyllä. Tuhatta pienempiä alkulukuja on 168 kappaletta. Seuraavassa tuhannessa niitä on 135 ja sitä seuraavassa 127. Harveneminen on kuitenkin kohtalaisen hidasta. Niissä suuruusluokissa, joissa tietokoneet tuntevat olonsa vielä mukavaksi, noin yksi tuhannesta luvusta on alkuluku.

Lukua $x$ pienempien alkulukujen määrää merkitään yleensä $\pi(x)$, jossa pii on pee niin kuin prime. Alkulukujen laskemisen lisäksi sen arviointiin on joukko kaavoja. Yksi arvio on hyvin yksinkertainen, vaikkakin vähän epätarkka:

\[ \frac{x}{\ln x} < \pi(x) < \frac{1.26x}{\ln x}. \]

Eli alkulukujen välillä on paljon tylsiä lukuja?

Ei läheskään aina. Alkulukupareja, joiden välissä on vain yksi luku, on paljon alkaen $(3,5)$-parista. Sataa pienemmissä luvuissa on kahdeksan paria, ja viime syksynä löydettiin lähes 400 000 numeroa pitkä pari. Vielä ei kuitenkaan tiedetä, onko kaksikoita äärettömän monta.

Kaksikoiden lisäksi on olemassa kolmikoita kuten $(37, 41, 43)$, nelikoita, viisikoita ja suurempia ryhmiä. Jaollisuussääntöjen vuoksi ne eivät tosin voi koostua peräkkäisistä tai edes kahden välein olevista luvuista.

Onko alkulukujen tekemiseen jotain kaavaa?

Mitään sellaista ei tunneta. Jotkin lausekkeet kuitenkin tuottavat yllättävän alkulukuisia tuloksia. Esimerkiksi $n^2 + n + 41$ tuottaa pelkkiä alkulukuja ännän arvoilla nollasta kolmeenkymmeneenyhdeksään.

Eikö yhtään mitään?

60-luvulla matemaatikko Stanislaw Ulam teki kuten jokainen meistä kuolettavan tylsää esitelmää kuunnellessaan ja piirusteli spiraaleja. Hän asetti luvut spiraalille...

Spiraali!

...ja väritti alkuluvut:

Jotakuinkin melkein kuvioita sisältävä spiraali!

Erilaiset alkulukuja tiheästi tuottavat kaavat näkyvät spiraalilla jonkunasteisina kuvioina. Kuitenkaan niitä ei yhdistä mikään tietty sääntö.

Tämä on siis olennainen asia, josta matemaatikot eivät tajua kaikkea edes yli kahden vuosituhannen jälkeen?

Näin juuri. Alkulukuihin liittyy vielä paljon avoimia kysymyksiä. Esimerkiksi Riemannin hypoteesi, joka liittyy alkulukujen määrään, on odottanut todistusta puolitoista vuosisataa. Perustavanlaatuisimmat asiat ovatkin osoittautuneet syviksi ja vaikeiksi.

Onko tällä mitään käytännön merkitystä?

Ensinnäkin: erittäin paheksuva tuhahdus, senkin hyötyajattelija. Toisekseen: Kyllä, paljonkin. Käytännössä kaikki lukuteoria rakentuu alkulukujen pohjalle. Esimerkiksi nykyaikainen salakirjoitus perustuu suurelti siihen, että suuria lukuja on vaikea purkaa alkutekijöikseen. (Ks. Julkisia salaisuuksia)

16 kommenttia:

  1. "Matemaatikot ihmeissään: Alkuluvuista paljastui uusi ominaisuus"

    https://www.tekniikkatalous.fi/tiede/matemaatikot-ihmeissaan-alkuluvuista-paljastui-uusi-ominaisuus-6534210

    "Jos alkuluku esimerkiksi loppuu numeroon 9, on 65 prosenttia todennäköisempää, että sitä seuraava alkuluku loppuu numeroon 1 kuin numeroon 9."

    Laskeskelin ja taulukoin noita alkuluvun viimeisen numeron ja sitä seuraavan alkuluvun viimeisen numeron määriä ja sain seuraavanlaisen taulukon:

    http://petke.info/lukuparit.jpg

    Laskin nuo luvut kaikista 10 miljoonaa pienemmistä alkuluvuista.

    VastaaPoista
    Vastaukset
    1. Erittäin kiinnostava lisäys! Tutkimusartikkeli (vapaasti luettavissa) sisältää samannäköisen taulukon $10^8$ ensimmäiselle alkuluvulle — ja runsaasti hyvin tiukkaa matematiikkaa!

      Poista
    2. Sinänsähän tuo on melko yksinkertainen ominaisuus, mikä ollaan nyt vasta löydetty - mutta auta armias, kun se täytyy matemaattisesti todistaa olemassaolevaksi, niin yli mun hilseen menee! Innostuin etsimään muita melko yksinkertaisia ominaisuuksia alle 10 miljoonan alkuluvuista, mutta se ei tietenkään riitä, että niitä algoritmeillä löytäisikin, kun ne pitäisi TODISTAA! Kerron täällä jos sellaisia löydän...

      Poista
  2. Laskin kuinka monta kolme peräkkäistä alkulukua on, joiden vikat numerot ovat {1,1,1}, {1,1,3}, {1,1,7}...,{9,9,9} (4 * 4 * 4 = 64 kpl) ja sain seuraavanlaisen taulukon. En sitten tiedä, mitä siitä voisi päätellä? - Ainakin sen, että harvinaisin kolmen viimeisimmän luvun järjestys peräkkäisistä alle 10 miljoonan alkuluvuista on {7,7,7}, joita on 3080 kpl ja yleisin {9,1,7}, joita on 14922 kpl. Onhan siinä melkoinen ero.

    Koko taulukko html muodossa:

    http://petke.info/kombinaatiot.html

    Jos jotakuta kiinnostaa REBOL-koodi, jolla taulukon tein niin se näkyy tuolla:

    http://petke.info/koodi2.jpg

    VastaaPoista
    Vastaukset
    1. Vastaan itselleni kysymykseen "Mitä siitä voidaan päätellä" - Ei ehkä mitään, mutta alkuluvuilla on kiva leikkiä.

      Poista
  3. Anteeksi. Yleisin on: {3,9,1} 15094 kpl

    VastaaPoista
  4. Tein tuollaisen Ulamin spiraalin (artikkeli Wikipediassa) miljoonasta ensimmäisestä alkuluvusta eli taulukon koko 1000*1000:

    Ulamin spiraali miljoonalle alkuluvulle

    Siinäkin on mielestäni selvästi nähtävissä tiettyä "säännöllisyyttä" - siinä näkyy vinottaisia viivoja.

    VastaaPoista
    Vastaukset
    1. Hiomakuviolta näyttää, vaikkei liityy juuri asiaan. Materiaalina vaikka kiiltävä pelti tai höylätty puu jota hiottu ensin pysty ja vaaka suuntaan, sitten ristikkäin jossa edellinen kuvio melkein katoaa, jossain kohti vähän enempi painettu. Kokeile. Myös auton peltien hiomisessa ohje jotenkin tuolleen ennen maalausta. Jotku vanhat ikilevy pöydän pinnat vähän tuommoissella kuviolla.

      Poista
  5. Koko Tekniikka&Talous lehden artikkeli haukuttiin lyttyyn Suomi24:n keskustelupalstalla:
    Keeskusteluaa Suomi24:ssa
    "Tekniikka ja Talous -lehden uutistoimittajat ovat täysin ammattitaidotomia ja englantia osaamattomia. Suurin osa ainakin verkkolehden "ihmeuutisista" on suureksi osaksi puppua. Satoja erilaisia "keksintöjä" (akuista, metalleista, jne.), joista ei kirjoiteta missään muualla. Perustuvat ymmärtämättömyyteen asioiden tarkoitushakuiseen vääristelyyn. Tekstejä on lyhennetty ja hävitetty faktat."

    Aloin ohjelmoimaan Pythonilla. Sen ohjelmakirjastolla gmpy2 on tehokkaat funktiot gmpy2.is_prime(luku) ja gmpy2.next_prime(luku). Koitan tutkia noiden eri peräkkäisten viimeisten lukujen pareja väliltä (100 miljardia)...(100 miljardia + 10 miljoonaa). Mielenkiinnolla odotan minkälaisen tilastollisen jakauman saan.

    VastaaPoista
    Vastaukset
    1. Harvemmin toimittajilla on asiantuntemusta analysoida matemaattisia löytöjä muuten kuin pintapuolisesti, siinä ei ole mitään yllättävää. Tämä artikkeli vaikuttaa kuitenkin aika järkevältä. Tosiaan kyseessä on lähinnä havainto ja sitä tukeva konjektuuri eli valistunut arvaus, ei mikään kiveen hakattu fakta. Kuten tässä tekstissä (josta kommenttiketju alkaa hieman etääntyä) mainitsin, alkulukuihin liittyy vielä valtavasti tuntematonta.

      Kokeellinen tutkimus on aina hauskaa ja usein valaisevaa, mutta lukuteoriassa sillä on hankala todistaa mitään. Myöskään tilastollinen päättely ei ole täysin triviaalia (näin veikkaan tilaston perusopintoja suorittavana).

      Poista
    2. Tässä nyt olisi vielä viimeinen kommenttini tähän asiaan:
      Perättäisten alkulukujen viimeisten numeroiden tilasto väliltä kvadriljoona (10 potetenssiin 24) ja (kvadriljoona + miljardi).
      (7, 3) : 1166576
      (9, 3) : 1144502
      (1, 3) : 1220574
      (3, 7) : 1188492
      (9, 1) : 1259451
      (7, 1) : 1141032
      (3, 1) : 1129175
      (7, 7) : 991558
      (9, 9) : 995211
      (3, 9) : 1213985
      (1, 9) : 1096316
      (1, 7) : 1212767
      (3, 3) : 990388
      (9, 7) : 1130502
      (1, 1) : 995038
      (7, 9) : 1224154
      Todennäköisyys että 9:n seuraisi 1 useammin kuin 9 on pienentynyt oleellisesti. Tässä enää 27% suurempi on tn. sille että seuraa 9 (mikäli osasin ja tajusin prosenttilaskun oikein). Mun konjektuuri on, että eri peräkkäisten lukuparien määrät lähestyvät toisiaan kun alkulukujen määrä lähestyy ääretöntä ;) .

      Poista
    3. Tässä vain vastaan tulee laskennallisten menetelmien perusongelma: onko tulos todellinen vaiko sattumaa? Lukua $10^{24}$ pienempiä alkulukuja on noin $10^{22}$ kappaletta, joten tilaisuuksia sattumille kyllä on — mutta kuinka satunnaisia alkuluvut ovat? Laskennallisesti ilmiselviä juttuja on murrettu isommillakin luvuilla. Omalla lukuteorian tasollani en osaa sanoa muuta kuin että jännää on!

      Poista
    4. No, kun sinäkin vielä jatkoit keskustelua, niin:
      Kaikissa ajoissani muistaakseni {7,7} on ollut harvinaisin. Ehkä matemaatikoiden kannattaisi tarttua siihen ensin ja yrittää todistaa se jotenkin kunnolla, eikä vain konjektuurin tasolla?

      Poista
    5. Olisipa se niin helppoa! (Samalla fyysikot voisivat viimein rakentaa fuusiovoimaloita, jne.) Arvelisin tämän ominaisuuden olevan lukuteoreetikkojen piirissä aika matalalla prioriteetilla: ilmiö on helppo kuvailla, mutta veikkaisin (en ole vielä ammattilainen) sen olevan teoreettisesti aika tylsä verrattuna moneen muuhun pulmaan. Voi myös olla, ettei sopivia työkaluja vielä löydy. Fermat'n konjektuuri (yhtälöllä $a^n+b^n=c^n$ ei ole kokonaislukuratkaisuja, kun $n \geq 3$) kesti aikaa melkein 400 vuotta ja ratkesi matematiikalla, jonka esivanhemmistakaan ei osattu haaveilla kysymyksen esittämisen aikaan! Jos uusia apukeinoja tarvitaan, ne taas luultavasti löytyvät joltain ihan muulta suunnalta.

      Poista
  6. Tuo Eratostheneen seulasi vähän vuotaa, koska väittää että luku 33 olisi alkuluku.

    VastaaPoista
    Vastaukset
    1. Kiitos huomautuksesta, korjattu! Hieman ironista blogata samaan aikaan päässälaskusta ja väittää moista... (Jonkin copy-paste-erheen takia animaatio myös esitti, että 35 olisi jaollinen kolmella.)

      Poista

Kommentit ovat moderoituja — yritän hyväksyä kommenttisi mahdollisimman pian. Voit kirjoittaa kommenttiin LaTeX-koodia tai yksinkertaista HTML-merkintää: lue lisää Kommentointi-sivulta.