Syrakusan arvelu

On matematiikka , kutsumme Syracuse sekvenssin sekvenssi on luonnollinen kokonaislukuja määritellään seuraavasti: aloitamme tiukasti positiivinen kokonaisluku; jos se on parillinen, jaamme sen 2: lla; jos se on pariton, kerrotaan se 3: lla ja lisätään 1. Toistamalla operaatio saadaan sarja tiukasti positiivisia kokonaislukuja, joista kukin riippuu vain sen edeltäjästä.

Esimerkiksi 14: stä rakennetaan numerosarja: 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4 , 2 ... Tätä kutsutaan luvun 14 Syracuse-sekvenssiksi.

Kun numero 1 on saavutettu, arvosarja (1,4,2,1,4,2…) toistetaan loputtomasti syklissä, jonka pituus on 3, jota kutsutaan triviaaliseksi sykliksi.

Jos olisimme aloittaneet toisesta kokonaisluvusta, soveltamalla siihen samoja sääntöjä, olisimme saaneet erilaisen numerosarjan. A priori olisi mahdollista, että tiettyjen lähtöarvojen Syracuse-sekvenssi ei koskaan saavuta arvoa 1, joko päättyy muuhun kuin triviaaliseen sykliin tai että se eroaa kohti ääretöntä. Emme kuitenkaan ole koskaan löytäneet esimerkkiä annettujen sääntöjen mukaisesti saadusta sekvenssistä, joka ei johda arvoon 1, sitten triviaalissa jaksossa.

Collatz arveluihin , joka tunnetaan myös nimellä arveluihin Collatz , konjektuurin Ulam , Tsekin olettamuksiin tai ongelma 3 x + 1 , on matemaattinen oletus, että sen jälkeen, kun Syracuse mikä tahansa positiivinen kokonaisluku saavuttaa 1.

Lausunnon yksinkertaisuudesta huolimatta tämä arvelu on uhannut matemaatikkoja monien vuosien ajan. Paul Erdős sanoi Syrakusan arveluista: "matematiikka ei ole vielä valmis tällaisiin ongelmiin" .

Alkuperä

Jo vuonna 1928 Lothar Collatz oli kiinnostunut kokonaislukuisista iteraatioista, joita hän edusti graafien ja hypergraafien avulla . Sitten hän keksi 3x + 1 -ongelman ja esitteli sen usein seminaareissaan. Vuonna 1952 vierailunsa aikana Hampurissa Collatz selitti ongelmansa Helmut Hasselle . Viimeksi mainittu lähetti sen Amerikassa Syracusen yliopistossa : Collatz-sarja otti sitten nimen "Suite of Syracuse". Sillä välin puolalainen matemaatikko Stanislas Ulam levittää sitä Los Alamosin kansallisessa laboratoriossa . 1960-luvulla ongelman otti vastaan matemaatikko Shizuo Kakutani, joka jakoi sen Yalen ja Chicagon yliopistoille .

Tämä arvelu mobilisoi matemaatikot niin 1960-luvulla, kylmän sodan keskellä , että vitsi, että ongelma oli osa Neuvostoliiton juonia hidastaa amerikkalaista tutkimusta.

Ensimmäinen lähestymistapa oletukseen

Syracuse-sviitti

Syracuse sekvenssi kokonaisluku $N > 0$ on määritelty induktio , seuraavasti:

u_0 = N

ja minkä tahansa luonnollisen luvun

n suhteen

u _ {{n + 1}} = {\ aloita {tapaukset} {\ dfrac {u_ {n}} {2}} ja {\ mbox {si}} u_ {n} {\ mbox {on tasainen,}} \ \ 3u_ {n} +1 ja {\ mbox {si}} u_ {n} {\ mbox {on pariton.}} \ Lopeta {tapaukset}}

Lausunto olettamuksesta

Arveluihin todetaan, että mikä tahansa kokonaisluku $N > 0$ , on olemassa indeksin $n$ siten, että $u n = 1$ .

Syracuse-sviitti N = 15

$u 0$	$u 1$	$u 2$	$u 3$	$u 4$	$u 5$	$u 6$	$u 7$	$u 8$	$u 9$	$u 10$	$u 11$	$u 12$	$u 13$	$u 14$	$u 15$	$u 16$	$u 17$	$u 18$	$u 19$	$u 20$
15	46	23	70	35	106	53	160	80	40	20	10	5	16	8	4	2	1	4	2	1	...

Sanasto

$N = 15: n$ ja $N = 27:$ n sekvenssin graafinen havainnointi osoittaa, että sekvenssi voi nousta melko korkealle ennen putoamista uudelleen. Grafiikka muistuttaa raekuuron kaoottista kaatumista tai tuulen puhaltaman lehden polkua. Tästä havainnosta syntyi koko värikäs sanasto: puhumme jatkeen varkaudesta .

Määritämme sitten:

lentoaika : se on pienin indeksi $n$ sellainen, että $u n = 1$ .Se on 17 Syracuse 15: n jatkoa varten ja 46 on Syracuse 127: n jatkoa varten;
korkeuden lentoaika : se on pienin indeksi $n$ sellainen, että $u n +1 < u 0$ .Se on kymmenen Syracuse 15: n jatkoa varten ja 23 on Syracuse 127: n jatkoa varten;
suurin korkeus : tämä on sekvenssin suurin arvo.Syracuse 15: n jatkoa on 160 ja Syracuse 127: n jatkoa 4372.

Muita arvailuja

Voimme antaa monia Syracuse-ongelmaa vastaavia formulaatioita. Syrakusan oletus vastaa seuraavia ehdotuksia:

minkä tahansa lennon kesto on ohi;
minkä tahansa lennon kesto korkeudessa on ohi;
jokaisella lennolla on rajallinen määrä parillisia vaiheita;
jokaisella lennolla on rajallinen määrä parittomia vaiheita;
jokaisella lennolla on rajallinen määrä tasaisia vaiheita korkeudessa;
jokaisella lennolla on rajallinen määrä parittomia portaita korkeudessa.

Oletusten lähestymistavat ja tulokset

Pakattu sviitti

Huomaa, että jos $u n$ on pariton yllä olevassa kaavassa, $u n +1$ on välttämättä tasainen ja siksi sekvenssin seuraavan vaiheen on oltava jako kahdella; voimme määritellä uuden pakatun version Syracuse-paketista yhdistämällä nämä kaksi vaihetta seuraavasti:

v_ {n + 1} = \ aloita {tapaukset} \ frac {v_n} {2} & \ mbox {si} v_n \ mbox {on jopa} \\ \ frac {3v_n \, + \, 1} {2} & \ mbox {si} v_n \ mbox {on pariton.} \ end {cases}

Uusi sekvenssi on sekvenssi, joka on erotettu perusversiosta, ja arveluiden mukaan tämä sekvenssi päättyy aina jaksoon (1,2,1…).

Syrakusan sekvenssi pakattu arvolle N = 15

$v 0$	$v 1$	$v 2$	$v 3$	$v 4$	$v 5$	$v 6$	$v 7$	$v 8$	$v 9$	$v 10$	$v 11$	$v 12$	$v 13$	$v 14$
15	23	35	53	80	40	20	10	5	8	4	2	1	2	1	...

Käänteinen lähestymistapa

Voimme myös aloittaa käänteisalgoritmista :

R (n) = \ alkaa {tapaukset} \ {2n \} & \ mbox {si} n \ ekvivalentti 0,1,2,3 \ mbox {tai} 5 \\ \ {2n, (n-1) / 3 \} & \ mbox {si} n \ equiv 4 \ end {cases} \ pmod {6}.

Sen sijaan, että osoittaisimme, että suora sekvenssi, joka alkaa mistä tahansa nollasta poikkeavasta luonnollisesta kokonaisluvusta, johtaa aina arvoon 1, yritämme osoittaa, että käänteinen algoritmi, joka alkaa 1: stä, pystyy tuottamaan kaikki nollasta poikkeavat luonnolliset luvut.

On myös pakattu versio käänteisalgoritmista:

R (n) = \ aloita {tapaukset} \ {2n \} & \ text {si} n \ equiv 0 \ mbox {tai} 1 \\ \ {2n, (2n-1) / 3 \} ja \ text { if} n \ equiv 2 \ end {cases} \ pmod {3}.

Nämä käänteiset algoritmit voidaan esittää puilla , joiden juuri on 1. Jos oletus on totta, nämä puut kattavat kaikki nollasta poikkeavat luonnolliset kokonaisluvut.

Binaarinen lähestymistapa

Syracuse-toiminnon toistuvat sovellukset voidaan esittää abstraktina koneena, joka käsittelee binääriprosessia . Kone suorittaa seuraavat kolme vaihetta parittomalle numerolle, kunnes jäljellä on vain yksi "1":

Siirrä binaarinen numero yksi lovi vasemmalle ja lisää "1" oikeaan päähän (jolloin 2 n + 1);
Lisää alkuperäinen numero n (jolloin 2 n + 1 + n = 3 n + 1);
Poista kaikki "0" oikealta (eli jaa kahdella, kunnes tulos on pariton).

Esimerkki

Valittu aloitusnumero on 7. Sen kirjoitus binäärisenä on 111 (koska 7 = 2 2 + 2 1 + 2 0 ) Tuloksena oleva sekvenssi on seuraava:

111 1111 10110 10111 100010 100011 110100 11011 101000 1011 10000 11 100

Todennäköisyys

On heuristisia ja tilastollisia argumentteja, jotka kykenevät motivoimaan oletuksia. Tarkastellaan esimerkiksi Syracuse-sekvenssin iteraatiota, joka on pakattu luvulle v satunnaisesti riittävän suurena aikavälinä. Jos v on parillinen, se kerrotaan (1/2), kun taas pariton luku kerrotaan arvolla (3/2). Molemmissa tapauksissa tarkistamme, että tuloksen pariteetti on riippumaton arvosta v . Heuristinen päättely koostuu siitä, että oletetaan, että tämä todennäköisyysperuste on pätevä minkä tahansa pakatun sekvenssin termin suhteen. Vaikka se ei ole tiukka (sekvenssin ehdot eivät ole satunnaisia), tietyt kokeelliset havainnot pyrkivät vahvistamaan sen. Näin ollen tätä olettamusta käyttämällä saatu malli ennustaa oikein lentoajan sviitin korkeudessa. Tämän heuristisen arvion avulla voimme sanoa, että tilastollisesti kahden peräkkäisen operaation vaikutus peräkkäin tarkoittaa alkuluvun kertomista (3/4) tai että Syracuse-operaatio supistuu keskimäärin suhteessa, joka on suunnilleen sama kuin neliöjuuri (3/4) = 0,866 ...

Tämä huomattavasti pienempi kuin yhtenäisyyden suhde viittaa vahvasti siihen, että Syracuse-sarjan peräkkäiset elementit eivät voi kasvaa loputtomiin. Tästä väitteestä ei ole tarkkaa näyttöä (ja vaikka onnistutaankin tekemään tämä todennäköisyysperuste tiukaksi, se ei vielä salli johtopäätöstä, koska äärettömän pienen todennäköisyyden tapahtuma ei sen vuoksi ole mahdotonta). Myöskään tässä esitetty argumentti ei millään tavalla sulje pois ei-triviaalien jaksojen olemassaoloa.

Syrakusa-hypoteesin tyydyttävien lukujen jakautumisesta voidaan kehittyneillä lineaarisen ohjelmoinnin menetelmillä osoittaa, että $x: n ollessa$ riittävän suuri, alle $x: n$ kokonaislukujen määrä, joka tyydyttää Syracuse-hypoteesin, on vähintään $x, on$ tietty vakio $a <1$ . Vuonna 2002, I. Krasikov ja J. Lagarias saatu $= 0,84$ .

Terence Tao ilmoitti vuonna 2019 osoittaneensa todennäköisyysperusteella, että melkein kaikkia Collatzin kiertoratoja rajoittaa mikä tahansa toiminto, joka eroaa äärettömyyteen. Raportoidessaan tästä artikkelista Quanta Magazine uskoo, että "Tao saavutti yhden merkittävimmistä tuloksista Collatz-olettamuksissa vuosikymmenien ajan".

Laskennallinen lähestymistapa

Mielenkiintoinen etsintätapa on järjestelmällinen tutkimus Syracuse-paketin käyttäytymisestä tietokoneiden avulla yhä suuremmille lähtömäärille. Olemme täten vahvistaneet kaikkien N <1,25 × 2 62 arviot . Tämän määrän suuruus, noin kuusi miljardia miljardia, vahvistaa todennäköisesti uskoamme Syrakusan arveluiden oikeellisuuteen. On kuitenkin ymmärrettävä, että niin kauan kuin jatkamme laskutoimitusta, se ei voi suoraan todistaa tätä oletusta; laskelma voisi päinvastoin kohdata vasta-esimerkin, joka osoittaisi oletuksen virheellisyyden. Tämän lähestymistavan etuna on myös se, että se tarjoaa numeerisia tuloksia, joita teoreetikot voivat käyttää todisteidensa täydentämiseen. Esimerkiksi käyttämällä yllä olevaa sidottua N: tä Syracuse-sekvenssin syklien pituuden lauseella voidaan päätellä, että triviaalisen jakson (1,4,2,1…) lisäksi ei ole sykliä alle 17 miljardia pituudessa.

Numeeristen tulosten avulla voidaan etsiä korrelaatioita lähtöjen $N määrän$ ja lennon keston tai korkeustietueen välillä. Täten havaittiin, että jos korkeustietueet voisivat olla erittäin korkeita, lennon kesto oli verrattain vaatimaton. Havaittu jo tutkittu lukumäärä näyttää osoittavan, että maksimikorkeutta kasvatetaan $φ ( N ) \times N 2$ , missä $φ ( N )$ voi olla joko vakio tai hitaasti kasvava funktio. Lentoaika on epätasaisempi, mutta näyttää siltä, että se kasvaa log $N$ : n kerrannaisella . Numeeriset kokeet ehdottavat siis uusia oletuksia, joihin teoreetikot voivat puuttua.

Toisaalta vain teoreettinen tutkimus kykenee valaisemaan ääretön liikeradan olemassaoloa: on osoitettu, että tällaiseen polkuun kuuluvalla numerosarjalla olisi nolla asymptoottista tiheyttä; voidakseen pysyä lennon kuvassa, voisi sanoa, että raekuuron on päästävä korkealle "vapautumisnopeudelle", jotta se ei putoa maahan. Jos arvelu on totta, niin ääretön lento on mahdotonta.

Päättämätön lausunto?

Saatujen tulosten suhteellinen heikkous huolimatta voimakkaiden matemaattisten menetelmien hellittämättömästä soveltamisesta on saanut jotkut tutkijat kyseenalaistamaan, onko Syracuse- spekulaatio ratkaisematon ongelma . Vuonna 1972 John Conway loi algoritmisen päättämättömyyden ongelmaryhmälle, joka luonnollisesti yleistää 3 x +1 -ongelman (katso artikkeli eksoottisesta ohjelmointikielestä FRACTRAN ). Tämä tulos viittaa siihen, että tarkastellussa perheessä on yksittäisiä ongelmia, joita ei voida ratkaista (tosiasiassa on jopa mahdollista, teoriassa ellei käytännössä, tehdä siitä selvä), mutta se ei ratkaise Syracuse-ongelman ratkaisemiskykyä erityisesti.

Laajennus todellisiin ja monimutkaisiin numeroihin

Syracuse-ongelma voidaan nähdä rajoitukseksi luonnollisille kokonaislukuille sekvenssissä, jossa on hyvin valittu todellinen tai monimutkainen toiminto, esimerkiksi seuraava toiminto: ${\ displaystyle z_ {n + 1} = f (z_ {n})}$ $f (z)$ ${\ displaystyle f (z) = {\ frac {1} {2}} z \ cos ^ {2} \ vasen ({\ frac {\ pi} {2}} z \ oikea) + (3z + 1) \ sin ^ {2} \ vasen ({\ frac {\ pi} {2}} z \ oikea).}$

Tai pakatussa versiossa, joka on korvattu seuraavalla : ${\ displaystyle 3z + 1}$ ${\ displaystyle {\ frac {(3z + 1)} {2}}}$

{\ displaystyle f (z) = {\ frac {1} {2}} z \ cos ^ {2} \ vasen ({\ frac {\ pi} {2}} z \ oikea) + {\ frac {(3z +1)} {2}} \ sin ^ {2} \ vasen ({\ frac {\ pi} {2}} z \ oikea).}

Reaalilukujen joukossa tätä toimintoa tutki Marc Chamberland. Se osoittaa, että oletus ei pidä paikkaansa tässä funktiossa todellisille numeroille, koska kiinteitä pisteitä on ääretön. Hän osoitti myös, että on olemassa ainakin yksi muu sykli: 1.1925 - 2.1386 ja että on olemassa loputtomia erilaisia reaalisekvenssejä.

Letherman, Schleicher ja Wood ovat tutkineet tätä toimintoa monimutkaisessa tasossa. Monet pisteet eroavat toisistaan loputtomasti, mikä näkyy vastakkaisessa kuvassa keltaisella tai sinisellä. Raja, joka erottaa nämä toisistaan poikkeavat ja ei-eroavat alueet, tässä mustana, muodostaa fraktaalikäyrän. Löydämme Mandelbrot-sarjalle tyypillisiä elementtejä (tämä viimeinen tulos ei ole kovin yllättävä, koska tämä sarja on universaali ).

Huomautuksia ja viitteitä

(in) Jeffrey C. Lagarias , " $3$ $x$ $+ 1$ ongelma ja sen Yleistyksiä " , Amer. Matematiikka. Kuukausi. , voi. 92, n o 1,Tammikuu 1985, s. 3-23 ( JSTOR 10.2307 / 2322189 , lue verkossa ).
Tätä tietä tutkivat Terras, Everett ja Crandall (1978-1977), Lagarias (1985) ja E. Barone (1999) [1]
Jean-Paul Delahaye , Matemaattiset ja matemaattiset pelipelit , Pariisi, Belin - Pour la Science ,Joulukuu 1999, 143 Sivumäärä ( ISBN 2-84245-010-8 ) , luku . 18 ("Syrakusan arvelu"), s. 124-125
Terence Tao , ” Lähes Collatz kiertoradat saavuttavat lähes joka rajoittuu arvoihin ”, toimitettu ,2019( arXiv 1909.03562 ).
Terence Tao , " Lähes kaikki Collatzin kiertoradat saavuttavat melkein rajatut arvot " , artikkelissa Mitä uutta ,10. syyskuuta 2019
(in) Kevin Hartnett " Matemaatikko Proves Valtava tulos on 'vaarallinen' Problem " , Quanta Magazine ,26. joulukuuta 2019
T. Oliveira e Silva, 3x + 1-oletuksen laskennallinen todentaminen .
T. Oliveira e Silva, 3x + 1: n ja siihen liittyvien oletusten empiirinen todentaminen , The Ultimate Challenge: the 3x + 1 problem, American Mathematical Society, Providence, (2010) s.189-207
(en) Shalom Eliyahu, Ongelma 3x + 1: uudet alarajat ovat ei-triviaaliset jaksojen pituudet , Diskreetti matematiikka 118 (1993) s. 45-56
Shalom Eliahou, 3n + 1-ongelma: onko olemassa muita kuin triviaalia jaksoa? , Matematiikan kuvat (2011) [2]
John H.Conway, käsittelemättömistä aritmeettisista ongelmista , Amer. Math Kuukausittain, 120 , n o 3 (maaliskuu 2013), 192-198.
Voimme lisätä f: ään minkä tahansa funktion, joka peruu kaikki kokonaisluvut, esimerkiksi muodon g (z) * sin (pi * z)
Marc Chamberland, " 3 x + 1-ongelman jatkuva jatkuminen todelliseen viivaan ", Dynam. Jatka. Discrete Impuls Systems , voi. 2, n o 4, 1996, s. 495–509
Simon Letherman, Schleicher ja Wood, " The (3 n + 1) -ongelma ja holomorfinen dynamiikka ", kokeellinen matematiikka , voi. 8, n o 3, 1999, s. 241–252 ( DOI 10.1080 / 10586458.1999.10504402 )

Katso myös