Kolacova pretpostavka

Matematika nije spremna za ovakve probleme – Pol Erdoš

Odužilo mi se čekanje proleća ovih dana, a neplanirano sam dobio par slobodnih popodneva od drugih obaveza, pa sam pomislio da bi bilo dobro  da doprinesem nešto  vremenu sporta i razonode ovde kod nas. Nemam vremena da se duže posvetim problemu koji dugujem onima koji prate milenijumske probleme Clayton Instituta  - videti Millennium_Prize_Problems – u pitanju je nedavno obećana Birch&Swinnerton-Dyer hipoteza (BSD), i najzad sam se opredelio za problem koji je, veruje se, mnogo teži od BSD, ali neuporedivo lakši da se opiše.

Nadam se da će čitaoci namernici uvideti da se ovaj problem može opisati deci u nižim razredima osnovne škole (Taso, obrati pažnju!).  Ilustracija Kolacove pretpostavke je ona slika na početku, i o tome je ovaj post. Iz nekih razloga Clayton Institut ovu pretpostavku nije uvrstio u spisak milenijumskih problema, a ja mislim da je to zbog onoga što je rekao Pol Erdoš, jedan od značajnijih matematičara XX veka, a što je citirano na početku – matematika nije spremna za ovakve probleme. Ima i drugih razloga, ali o tome ćemo malo kasnije.

Najpre da pretpostavku iskažemo. Nju je formulisao poznati nemački matematičar  Lothar Collatz godine 1937., i u prvi mah je izgledalo da je ona lako rešiva, ali se rešenje nije našlo.  Collatz je umro od srčanog udara 1990. godine na jednoj konferenciji u Varni, i nije doživeo da se njegova pretpostavka dokaže.  Evo, već oko 30 godina od njegove smrti je prošlo, i oko 80 godina od postavljanja pretpostavke, ali dokaz još nije pronađen.

Kolacova pretpostavka, dakle.

Zamislimo sledeću proceduru.

Pođimo od nekog pozitivnog celog broja , zovimo ga n.

1. Ako je n paran broj, podelimo ga sa 2 (dva) – setimo se da su svi celi pozitivni parni brojevi deljivi sa dva i kao rezultat deljenja daju ceo pozitivan broj.

2. Ako je n neparan broj, pomnožimo ga sa 3 i dodajmo tom rezultatu jedinicu. Drugim rečima, napravimo operaciju nad našim brojem 3n+1.

I to je sve. Ako ovu transformaciju nastavimo dovoljan broj puta, zanimljiv rezultat se dobija. Na primer, pođimo od broja n=6.

Pošto je broj 6 paran, prva transformacija (deljenje sa dva) daje 6/2=3, aha!, neparan, druga transformacija daje 3*3+1=10, paran, 10/2=5, neparan, 3*5+1=16, paran, 16/2=8, paran, 8/2=4, paran, 4/2=2, paran, 2/2=1.  Ukratko, sekvenca koja sadrži šesticu se ovako piše  6--3--10--5--16--8--4--2--1.

I ovde dolazimo do zatvorene petlje. Kada za rezultat dobijemo 1, neparan broj, onda 3*1+1=4, paran, 4/2=2, paran, 2/2=1, tj. vratili smo se tamo odakle smo počeli, do jedinice.  Zatvorena petlja 4--2--1--4 je konačni rezultat ovih operacija.

Kolacova pretpostavka kaže: bez obzira od kog pozitivnog celog broja počeli, uvek ćemo doći do petlje   4--2--1--4. Uvek.

Ili, još kraće: Od ma kog pozitivnog broja počeli, primenjujući opisanu proceduru završićemo sa brojem 1.

Probajmo sa još nekim primerom. Neka je naš početni broj n=7. Sada imamo sledeću sekvencu 7--22--11--34--17--52--26--13--40--20--10… hej, 10 smo već imali gore! 10--5--16--8--4--2--1.

Uzmimo neki drugi broj n.  Koji broj izabrati? Jasno je da ako izaberemo bilo koji broj koji se pojavljuje negde u gornjim sekvencama, završićemo sa jedinicom. Takođe je odmah jasno da početni brojevi 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, itd., najbrže vode (deljenjem sa 2) do jedinice.  Na primer broj 512 je, zapravo, 512= 2^9, pa će posle devet deljenja rezultat biti 1. Ovo se obično ilustruje pomoću Kolacovog “drveta” i  često korišćena ilustracija je ova dole

Na dnu ovog drveta je označena terminalna petlja 4--2--1--4.  Ako idemo “uzbrdo” levom stranom drveta, dobijamo gore pomenute brojeve 2,4,8,16,32,64,128,256…stepene broja 2. Postoje različite grafičke reprezentacije ovog drveta, i jedna od njih je prikazana na početku ovog posta, i o tome ćemo u sledećem paragrafu.  Ovde je prikazano samo 37 brojeva (u najvišem redu 8, u sledeća dva po 6,  u naredna dva po 4, u naredna dva po 2,  i najzad pet redova sa po jednim brojem, što se sve sabira do 37) koji se dobijaju procedurom opisanom ranije.

Jasno je da je ovo samo deo Kolacovog drveta i da se ono sve više i više grana kako uzimamo dalje brojeve.

Da bi ilustrovali pravu strukturu ovog drveta mnogi matematičari kreću od “korena” drveta (broja 1) i idući uzbrdo dopisuju brojeve koji bi mogli tzv. 3x+1   procedurom, ili deljem brojem 2, da se dobiju.  Da odmah objasnim.

Posmatrajmo, na primer, broj 10 na drvetu. Do tog broja je moguće doći ili deljenjem broja 20 sa 2, ili množenjem broj 3 trojkom i dodavanjem jedinice (3*3+1=10) , kao što se vidi na drvetu: od broja 20 i broja 3 upravljene su strelice ka broju 10. Radi dramatičnosti, svaki put kad je neki broj na drvetu dobijen deljenjem dvostruko većeg broja dvojkom, onda se strelica crta s malim nagibom na levo,  a ako je dobijen iz 3x+1   transformacije onda je nagib strelice malo na desno. Kada se tako predstavi, uzimajući mnogo brojeva, dobije se slika kao na početku ovog posta koja predstavlja Kolacovo drvo sa 10.000 brojeva.

Različite putanje do nekog broja su obojene drugačijim nijansama. Ovako predstavljeno, Kolacovo drvo je inspiracija naučnicima da govore kako ono ima “organsku” prirodu jer liči na sliku morske trave, na primer.

Zanimljivo je posmatrati dužine različitih “vlati” ove trave.  Na primer, dužina sekvence (ili broj trasformacija koje je potrebno primeniti da se od broja n stigne do jedinice)  za broj 6 je, vidi se gore, je 8, tj. potrebno je 8 koraka da se od broja 6 dođe do jedinice. Polazeći od broja 7, videli smo, potrebno je 16 koraka da se stigne do jedinice.  Taj broj koraka da se od nekog broja n stigne do jedinice (koristeći, naravno, pomenute transformacije) se zove total stopping time (TST), ili ukupno vreme zaustavljanja.  Za neke brojeve  TST ima malu vrednost – videli smo primere malo gore kad je TST(6)=8, i TST(7)=16  - ali ako bi počeli od broja 27 potrebno je 111 koraka da se dođe do jedinice, tj. TST(27)=111.

Čini se da nema neke očevidne zakonitosti po kojoj se TST različitih brojeva menja. Recimo, TST(19)=21, ali TST(2097152) je takođe 21. Iako je drugi broj oko sto hiljada puta veći od prvog, broj koraka da se od jednog, ili drugog, broja dođe do jedinice je isti i iznosi 21. Na slici dole je prikazana vrednost TST za brojeve od 1 do 10.000.

Vidi se da je broj koraka do jedinice (TST), u ovom rasponu brojeva (1-10.000), u najvećem broju slučajeva manji od oko 200.

Za veće brojeve (u rasponu 1- 10 miliona), grafik je kvalitativno sličan

 U ovom slučaju, kada je raspon posmatranih brojeva hiljadu puta veći nego na gornjem grafiku, TST uzima vrednosti ispod 550, otprilike.

Nije precizno poznato kako se TST(n) menja sa promenom broja n, tj., ne zna se tačno kako ta funkcija izgleda. U najprostijem slučaju, za brojeve oblika 2^N, TST(2^N)=N, tj. jasno je da se TST povećava, barem za ovakve brojeve, ali konačni oblik te funkcije se ne zna.

Da bi stekli malo širi uvid u ponašanje ove “3x+1” transformacije, kako se ona često zove među matematičarima, moguće je isprobati sličnu transformaciju i videti čemu nas ona vodi. Isprobajmo, na primer, šta se dešava, ako uradimo ovako: ako je dati broj paran podelimo ga sa 2, kao i ranije, ali ako je neparan pomnožimo ga sa 3 i oduzmemo jedinicu, tj. za neparno n konstruišemo broj 3*n-1. Pođimo opet od broja 7. Sledeći pravila ove nove transformacije dobijamo sekvencu 7--20--10--5--14--7. Ups! Vratili smo se na početni broj  7 i zatvorili ciklus, ali nismo došli do jedinice. Polazeći od nekih drugih brojeva možemo doći do jedinice, ali ovo nije garantovano. Nije poznato ni koliko ovih "ne-jediničnih" petlji ima.

Izgleda da je transformacija 3*n+1 po nečemu posebna. Nije poznato u čemu je ta posebnost. Poznato je, međutim da generalizovana transformacija a*n+b , gde su a i b celi pozitivni brojevi, vodi do problema koji matematički ne može da se odluči – tehnički izraz je undecidable.

Malo drugačiji pogled na Kolacovu hipotezu može da se dobije ako posmatramo ne samo cele brojeve, n, nego dozvolimo da n može da bude i kompleksan broj.

Lako je se uveriti da Kolacova transformacija može da se zapiše kao

Ova formula deluje zastrašujuće, ali malo srednjoškolske algebra će vas uveriti da je veoma prosta. Uzmimo da je z neki paran pozitivan ceo broj: u tom slučaju argument sinusa je celobrojni umnožak broja pi, tako da je drugi član u jednačini 0, dok član sa kosinusom postaje jedinica i transformacija je, prosto z/2, kao što treba. Ako je z neparan pozitivan ceo broj, prvi član u gornjoj jednačini je nula, a drugi član daje 3*z+1 , kao što nalaže originalna Kolacova transformacija. Međutim, ako pored ovih vrednosti za broj z dopustimo i kompleksne brojeve, onda su rezultati zanimljivi i neočekivani.

Setimo se da je u gornjim primerima, svaki broj posle dovoljnog broj transformacija davao kao rezultat jedinicu. Ako z može da bude i kompleksan broj, onda Kolacova transformacija može da iteriše do beskonačnosti, po apsolutnoj vrednosti, i da se nikad ne vrati u blizinu početnog broja.  Ako nacrtamo regione (skup tačaka) u kompleksnoj ravni koji iterišu do konačnog broja, onda dobijamo Kolacov fractal, sliku koja će obradovati sve fractal aficionados.  Dakle, nešto ovako:

Na horizontalnoj (realnoj) osi se nalaze tačke koje smo ranije posmatrali (pozitivni celi brojevi) i mnoge druge, na vertikalnoj osi je imaginarna komponenta. Tamna ostrva su skupovi tačaka koji ostaju konačni prilikom iteracija.

Kao i svaki fraktal, i Kolacov fraktal pokazuje samo-sličnost prilikom uvećanja/smanjenja I generalno ima bogatiju strukturu od, recimo, poznatog Mandelbrotovog (Julia) skupa.

Ako bi umesto gornje kompleksne transformacije uveli neku sličnu (matematičari su pokušavali sa nekoliko različitih) dobije se takođe fraktalni skup, nešto drugačijeg oblika. Na primer

Detaljno ponašanje ovih fraktala nije poznato jer, kako kaže P. Erdos – Matematika nije spremna za ovakve probleme.

Jedan od razloga što Kolacova pretpostavka nije suviše privukla pažnju matematičara je i taj što ona postoji sama za sebe, bez ozbiljnijeg kontakta sa drugim oblastima matematike. Takođe, ne vidi se šta bi novo u matematici donelo rešenje/dokaz Klacove pretpostavke. Ja mislim da je iz tog razloga ova pretpostavka, koja stoji nerešena već 80 godine, izostavljena iz spiska Milenijumskih problema. A ipak stoji i posmatra nas upornošću nerazrešene misterije.