Açık Problemler · 1937'den Bugüne
Bir sayı çiftse ikiye bölün. Tekse, 3 ile çarpıp 1 ekleyin. Tekrar edin. Her zaman 1'e ulaşır mısınız? Bu soru, ilkokul seviyesinde anlaşılır, ama 1937'den beri kimse kanıtlayamadı. Paul Erdős'ün dediği gibi, "matematik henüz bu tür sorular için hazır değil." Aşağıdaki araçla kendi sayınızı deneyin, "dolu tanesi" gibi inip çıkan bir yörünge izleyeceksiniz.
Önce Temel Kavramlar
Pozitif bir tam sayı \(n\) için Collatz fonksiyonu:
Bu işlemi tekrar tekrar uygularsanız, ortaya çıkan dizi "dolu tanesi dizisi" (hailstone sequence) olarak anılır, çünkü değerler bir bulutun içindeki dolu tanesi gibi defalarca yükselip düşer, ve sonunda (konjektüre göre) "yere düşer", yani 1'e ulaşır.
1'e ulaştığınızda: \(f(1)=3\times1+1=4\), \(f(4)=2\), \(f(2)=1\), ve tekrar 1'e dönersiniz. Bu \(\{1,4,2\}\) döngüsüne "bayağı (trivial) çevrim" denir. Konjektür şunu söyler: hangi pozitif tam sayıdan başlarsanız başlayın, er ya da geç bu çevrime girersiniz. Negatif sayılara genişletilirse, 3 farklı bayağı olmayan çevrim de biliniyor, ama bu sayfa sadece pozitif tam sayılarla ilgileniyor.
Durma zamanı \(\sigma(n)\): dizinin ilk kez \(n\)'den küçük bir değere düştüğü adım sayısı. Toplam durma zamanı \(\sigma_\infty(n)\): dizinin 1'e ulaştığı toplam adım sayısı.
Örnek, \(n=3\): \(3\to10\to5\to16\to8\to4\to2\to1\), toplam 7 adım, yani \(\sigma_\infty(3)=7\). Dizi, 3'ün altına ancak 6. adımda iner (\(4\to2\), ve \(2<3\)), yani \(\sigma(3)=6\). Bu örnek, \(\sigma\) ile \(\sigma_\infty\)'un her zaman birbirine yakın olmadığını da gösteriyor, dizi önce 3'ün üzerinde uzun süre kalabilir.
27 ile başlayın. Önce artıyor: 27→82→41→124→...→9232 (zirve!), sonra 111 adım sonra 1'e iniyor. 1 ile 27 arasındaki bir sayı için, zirvenin 9232 gibi büyük olması, ilk bakışta "asla 1'e dönmeyecek" hissi veriyor, ama döner. Bu, konjektürün neden "sezgiye aykırı" hissettirdiğinin küçük bir örneği.
\(n\) tekse, \(3n+1\) her zaman çifttir (tek×3=tek, +1=çift). Yani tek bir adımdan sonra zaten bölme adımı garantidir. Bazı araştırmacılar bu yüzden "sıkıştırılmış" formu kullanır: \(n\) tekse direkt \((3n+1)/2\)'ye geçilir. Bu, dizinin temel davranışını değiştirmez, sadece adım sayılarını yarıya yakın kısaltır. Bu sayfadaki "uzun form" (önce \(3n+1\), sonra ayrı bir adımda \(/2\)) görsel olarak daha "dolu tanesi" hissi verdiği için tercih edildi.
90 Yıllık Bir Bilmece
Bu konjektür kısa ömrüne karşın, isim karmaşası, kanıtlanmamış ama "neredeyse" ispatlar, ve son yıllarda büyük bir adımla zengin bir tarihe sahip.
1935'te Alfred Klose danışmanlığında doktorasını tamamlayan Collatz, iki yıl sonra, fonksiyonların grafiksel iterasyonu üzerine çalışırken bu problemi formüle etti. Kökeni biraz "bulanık": İngiliz matematikçi Bryan Thwaites de bağımsız keşif iddiasında bulundu, ve problem yıllarca gayriresmi olarak matematik camiasında dolaştı.
1950'lerde, Cambridge, Massachusetts'teki Uluslararası Matematikçiler Kongresi'nde Collatz bu problemi Shizuo Kakutani, Stanisław Ulam (evet, Asal Sayı Avı'ndaki aynı Ulam) ve H.S.M. Coxeter ile paylaştı. Sonuç: "Collatz Konjektürü", "Ulam Konjektürü", "Kakutani Problemi", "Thwaites Konjektürü", "Hasse Algoritması" ve "Syracuse Problemi" gibi en az altı farklı adla anılan bir problem.
Conway, Collatz'ın kuralına benzeyen ama her artık sınıfı (mod k) için farklı doğrusal kurallar kullanan genelleştirilmiş fonksiyonların, genel olarak algoritmik olarak karar verilemez olduğunu kanıtladı: "bu fonksiyon her zaman 1'e ulaşır mı?" sorusuna, genel bir algoritmayla cevap verilemez. Bu, Collatz'ın özel durumu için bir şey kanıtlamaz, ama neden bu kadar dirençli olabileceği konusunda ürkütücü bir ipucu verir.
Terras ve Everett, birbirinden bağımsız olarak, "neredeyse her" pozitif tam sayının (doğal yoğunluk anlamında %100'ü), dizisinde kendisinden küçük bir değere ulaştığını kanıtladı. Bu, "her sayı 1'e ulaşır" iddiasından çok daha zayıf (1'e ulaşmadan "küçülmek" yeterli değil), ama 40 yıllık sessizlikten sonra ilk somut ilerlemeydi.
Bir "çevrim" (cycle), dizinin tekrar başlangıç değerine döndüğü bir döngüdür. Steiner, tek bir yerel minimumu olan (yani sadece bir kez "dibe vuran") herhangi bir çevrimin, zorunlu olarak \(\{1,4,2\}\) bayağı çevrimi olduğunu kanıtladı. Daha karmaşık çevrimler (birden fazla "dip" noktası olan) için soru açık kaldı, ama bu, "başka çevrim yok" yönündeki kanıtların ilk adımıydı.
Lagarias, American Mathematical Monthly'de yayımladığı bu makaleyle problemi geniş bir matematik kitlesine tanıttı ve o zamandan beri bir "kapsamlı kaynakça" (annotated bibliography) tutmaya başladı, bugün hâlâ güncelleniyor. Aynı dönemde, Bryan Thwaites problemi çözene £1000 ödül teklif etti, bu yüzden bazı kaynaklarda "Thwaites Konjektürü" adı geçer.
Eliahou, bayağı olmayan herhangi bir çevrimin en az 17.087.915 elemanlı olması gerektiğini, ve çevrim uzunluğunun belirli bir formülle (\(2\)'nin kuvvetlerinin \(3\)'e oranının sürekli kesir açılımıyla ilişkili) sınırlı olduğunu gösterdi. Pratik anlamı: eğer bir karşı-örnek çevrim varsa, o kadar büyük olmalı ki bilgisayarla "kazara" bulunmuş olamaz.
1976'daki "neredeyse her sayı" sonucunu nicel hale getirdiler: \(x\)'in altındaki sayıların en az \(x^{0{,}84}\) kadarı, dizilerinde 1'e ulaşır (yörüngesinde 1 içerir). Bu oran 1'e (yani "%100"e) yaklaşsa da, tam %100'ü kapsamıyor, ve konjektürün tamamını kanıtlamıyor.
Steiner'in 1977'deki "tek dip noktalı çevrim yok" sonucunu genişlettiler: en fazla 68 yerel minimumu olan hiçbir bayağı olmayan çevrim yoktur. Eliahou'nun "en az 17 milyon eleman" sınırıyla birleştiğinde, olası bir karşı-örnek çevrimin hem çok uzun hem çok "karmaşık" (çok dip noktalı) olması gerekiyor, iki bağımsız kısıtlama aynı anda.
Tao, 1976'daki Terras/Everett sonucunu çok daha güçlü bir biçimde genelleştirdi: logaritmik yoğunluk anlamında, neredeyse her başlangıç değeri, sonunda istediğiniz kadar küçük bir değere iner (sadece "kendisinden küçük" değil, "neredeyse herhangi bir hedefin altına"). Bu, 1985'ten beri yapılan en büyük ilerleme olarak kabul edildi, ama Tao'nun kendisi de bunun konjektürü kanıtlamadığını, "tam %100" ile "neredeyse %100" arasındaki farkın hâlâ aşılmaz olduğunu vurguladı.
2020'de Bařina, konjektürü \(2^{68}\)'e (\(\approx2{,}95\times10^{20}\)) kadar tüm sayılar için doğruladı; takip eden çalışmalarla bu sınır \(2^{71}\)'e kadar genişletildi. Bu, "şimdiye kadar hiçbir karşı-örnek yok" demek, ama matematiksel bir kanıt değil, bir sonraki sayı her zaman teorik olarak farklı davranabilir.
Araştırmacının Pusulası
Aşağıdaki sekiz başlık, konjektürün "neden muhtemelen doğru ama kanıtı neden bu kadar zor" sorusuna farklı açılardan yaklaşıyor. Her başlıkta bir durum etiketi var (kanıtlanmış / konjektür-açık / araç-veri).
Bir sayı tekse, \(3n+1\) yapılır (çarpı ~3), sonra kesinlikle çift olduğu için bölünür (bölü 2): net etki çarpı ~1,5. Sayı çiftse, bölünür: çarpı 0,5. "Ortalama" bir sayı, yaklaşık yarı yarıya tek/çift olacağından, geometrik ortalama:
1'den küçük! Yani "ortalama olarak" her adımda sayı biraz küçülmeli, bu da neden hemen hemen her sayının sonunda 1'e düştüğünü hissettiren bir argüman. Ama "ortalama davranış", her sayı için garanti değildir, tek bir "şanssız" sayı sonsuza kadar büyüyebilir (teorik olarak), bu yüzden bu argüman bir kanıt değil.
2002'de Kontorovich ve Sinai, Collatz yörüngelerinin istatistiksel olarak bir Brownian hareket (rastgele yürüyüş) gibi davrandığını gösterdi. Yukarıdaki \(\sqrt3/2\) sezgisi, bu modelin "sürüklenme" (drift) teriminin negatif olduğunu söylüyor, yani rastgele yürüyüş "ortalamada" sıfıra (1'e) doğru kayıyor. Ama rastgele yürüyüşlerde bile, sonsuza kadar uzaklaşan tek bir yörünge olasılık 0 olsa da imkânsız değildir, olasılık 0 olması matematiksel kanıt anlamına gelmez.
Terras ve Everett'in kanıtladığı şey hassas bir şekilde şu: doğal yoğunluk anlamında, \(\{n : \exists k, f^{(k)}(n) < n\}\) kümesinin yoğunluğu 1'dir. Yani "rastgele" bir sayı seçerseniz, o sayının yörüngesinde, kendisinden küçük bir değere düşme olasılığı %100'e yaklaşır.
Bu teorem, bir sayının yörüngesinin en az bir kez kendisinin altına düştüğünü garanti eder. Ama o "küçük değer" hâlâ çok büyük olabilir, ve o değerin de 1'e ulaşıp ulaşmayacağını bilmiyoruz! Yani bu teorem, sonsuz bir "küçülme zinciri" kurmaz, sadece ilk halkasını garanti eder. Konjektürün tamamı için, bu argümanın sonsuz kez, her sayı için işlemesi gerekir, tam da Tao'nun 2022'deki ilerlemesinin (madde 3) odaklandığı nokta.
Tao'nun kanıtladığı şey kabaca şu: herhangi bir \(f(N)\to\infty\) fonksiyonu seçin (ne kadar yavaş büyüse de). O zaman, \(\{1,\ldots,N\}\) içindeki sayıların logaritmik yoğunluk anlamında %100'ü, yörüngelerinde \(f(N)\)'in altına inen bir değere ulaşır.
Önemli, çünkü "küçük bir değere düşme" garantisini keyfi derecede küçük hedeflere genişletiyor, 1976'daki "sadece kendinden küçük" sonucundan çok daha güçlü. Tao bunu, Collatz haritasının ergodik teori ve olasılık teorisindeki araçlarla incelenebilecek bir "rastgele dinamik sistem" gibi davrandığını göstererek yaptı. Ama "logaritmik yoğunluk %100" ile "her sayı için doğru" arasında matematiksel bir uçurum var: yoğunluğu sıfır olan bir istisna kümesi hâlâ var olabilir (sonsuz olsa bile). Tao, blog yazısında bunu açıkça "konjektürün kendisine yaklaşmıyoruz, ona paralel bir sonuç" diye tanımladı.
Konjektürün başarısız olmasının iki yolu var: (a) bir sayının yörüngesi sonsuza kadar büyür, ya da (b) bayağı \(\{1,4,2\}\) dışında bir çevrime girer. (b) yönünde üç sonuç birleşiyor:
Olası bir karşı-örnek çevrim, aynı anda çok uzun (Eliahou) ve çok karmaşık (Simons & de Weger, 68'den fazla dip noktası) olmak zorunda. Bu, "böyle bir çevrim var olamaz" demek değil, ama olası "arama uzayını" inanılmaz küçültüyor. Bu üç sonuç, birbirinden bağımsız tekniklerle (transandantal sayı teorisi, sürekli kesirler, bilgisayarlı diophantine yaklaşım) elde edildi, bu da onları birleştirildiğinde daha güvenilir kılıyor.
"\(qx+1\)" ailesini düşünün: \(n\) çiftse \(n/2\), tekse \(qn+1\) (\(q\) tek sayı, \(q\geq3\)). \(q=3\) bizim problemimiz. Diğer \(q\) değerleri için durum çok farklı:
\(\sqrt{q/2}<1\) koşulu, \(q<2\) gerektirir, yani \(q=1\) hariç tüm tek \(q\geq3\) için "ortalama çarpan" 1'den büyük! Bu, \(q=3\)'ün bile, sezgisel olarak "büyümesi gerektiği" bir aralıkta olduğunu gösteriyor, ki bu da konjektürün neden "yalan olması beklenir gibi göründüğü ama doğru olduğu düşünülen" bir sınır vakası olduğunu açıklıyor. \(q=3\)'ün "şanslı" olmasının derin bir nedeni var mı, yoksa sadece küçük sayıların istatistiksel bir tesadüfü mü, bu hâlâ açık bir soru.
Kuralı tersine çevirin: bir sayı \(m\)'ye hangi sayılar ulaşabilir? Her zaman \(2m\) (çünkü \(2m/2=m\)). Eğer \(m\equiv1\pmod3\) ve \((m-1)/3\) tek bir sayıysa, \((m-1)/3\) de bir "ata"dır (çünkü \(3\times\frac{m-1}{3}+1=m\)).
1'den başlayıp bu tersine kuralı tekrar tekrar uygularsanız, bir ağaç büyür. Konjektür, bu ağacın tüm pozitif tam sayıları içerdiğini söyler, yani ağaç "budaksız" tek bir bütün.
Bu Sayfada
Kollatz Konjektürü, "Özel Sayılar" ve "Asal Sayı Avı" sayfalarındaki birçok temayla kesişiyor: Ulam'ın adı burada da geçiyor (sarmal ve "şanslı sayılar"ın yanına bir üçüncü buluş daha), olasılıksal sezgiler asal yoğunluğu tartışmalarındaki Bateman-Horn mantığıyla aynı ruhta, ve "basit ifade, kanıtlanamayan sonuç" teması π'nin normalliği veya Goldbach konjektürü gibi diğer açık sorularla aynı ailede.
"Neredeyse her" sayı küçülür (Terras/Everett 1976), logaritmik yoğunlukta "neredeyse sınırlı" (Tao 2022), bayağı olmayan bir çevrim varsa ≥17 milyon elemanlı ve ≥69 dip noktalı olmalı (Eliahou 1993, Simons & de Weger 2005).
"Her" pozitif tam sayı için 1'e ulaşma garantisi. \(2^{71}\)'e kadar doğrulandı (Bařina), ama bu bir kanıt değil. 3, neden bu eşikte bir "sınır durum" gibi davranıyor (madde 5), tam olarak anlaşılmadı.
Kaynakça
Çekirgeler Eğitim