BİR YAPAY ZEKÂ BİR BOYAMA BULMACASINI ÇÖZÜYOR

Çizgilerle birbirine bağlanmış noktalardan oluşan bir ağ düşünün — matematikçilerin çizge (graph) dediği şey. Şimdi noktaları, bir çizgiyle bağlı iki nokta asla aynı renge sahip olmayacak şekilde boyayın. İşe yarayan en küçük renk sayısı, çizgenin kromatik sayısıdır. Ünlü bir özel durum, 1977’de ispatlanan ve başlığı her şeyi anlatan dört renk teoremidir: “Every planar map is four colorable” (Her düzlemsel harita dört renkle boyanabilir).

Hadwiger’in 1943 iddiası

1943’te Hadwiger, tüm çizgeler için kapsamlı bir kural önerdi. Bir çizgeyi, noktalar ya da çizgiler silerek ve bağlı iki noktayı tek bir noktada birleştirerek küçültün. Sonuca minör denir. Hadwiger bu yolla elde edilebilecek en büyük tam çizgeye — her noktanın diğer her noktaya bağlı olduğu bir kümeye — baktı ve gereken renk sayısının asla bu kümenin boyutunu aşmadığını öne sürdü.

Makale bunu “çizge kuramının en eski ve en temel problemlerinden biri” olarak niteliyor. Yalnızca küçük durumlar için ispatlanmış durumda: beşli kümelere kadar; burada dört renk teoremine denk olduğu ya da ona indirgenebildiği ortaya çıkıyor. Altıdan itibaren açık.

Her seferinde bir logaritma, yaklaşmak

Tam ifade direndiği için araştırmacılar renk sayısını, küme boyutunun mümkün olduğunca yavaş büyüyen bir fonksiyonuyla sınırlamaya çalıştı. Makale ilerlemeyi anlatıyor. On yıllar boyunca en iyi sınır, orantılıdan biraz daha hızlı büyüyordu — bir logaritmanın karekökünü içeren bir çarpanla. Birkaç yıl önce Norin, Postle ve Song bu engeli aştı. Ardından Delcourt ve Postle bunu daha da iyileştirdi ve en önemlisi, oldukça küçük çizgelerle uğraşmanın yeterli olduğunu gösterdi. Liu ve Luo ek çarpanı üçlü logaritmaya kadar indirdi.

Doğal varış noktası doğrusal Hadwiger sanısı: küme boyutunun sabit bir katı her zaman yeterlidir. Montreal’deki McGill Üniversitesi’nden Sergey Norin ve ETH Zürih’ten Raphael Steiner’in şimdi ispatladıklarını öne sürdükleri şey bu.

Makinenin oynadığı rol

Yazarlar açık konuşuyor: ispatı, onların yönlendirmelerini izleyen bir OpenAI modeli olan GPT-6 Astra buldu. Önce ondan, eksik parça olduğuna inandıkları çok yoğun çizgeler durumunu ispatlamasını istediler. Yazdıklarına göre model “yalnızca birkaç saat ve biraz cesaretlendirmenin ardından” başardı. Bir bağımlılığı açık hâle getirmesi istendiğinde, belli bir boyuta kadar olan çizgeleri kapsadı — ama gereken aralığı tam olarak değil. Ardından ondan boşluğu kapatacak özgün bir fikir istediler; bu da nihai ispatın “bootstrap” adımını ortaya çıkardı. Yazarlara göre, büzmelerle (contraction) ilgili tek bir öneri dışında, kendi özgün ispat fikirlerinin neredeyse hiçbiri ayakta kalmadı.

Metni insanlar yazdı. Başka bir OpenAI modeli düzeltme okumasına ve kaynakçaya yardım etti. Yazarlar, OpenAI’nin Codex’inin tüm ispatın Lean ispat asistanında biçimsel, makinece denetlenebilir bir sürümünü ürettiğini ve bunun yapay zekâ tarafından yazılmış erken bir taslakla birlikte çevrimiçi yayımlandığını bildiriyor. Matematiğin tüm sorumluluğunu üstleniyorlar.

İspatın içi

Argümanın iki yarısı var:

Küçük çizgeler, az renk. Küme sınırından çok da büyük olmayan çizgeler için yazarlar, küme boyutunun yaklaşık dört katının yettiğini gösteriyor. Başlangıç noktası Reed ve Seymour’un 1998 tarihli bir sonucu: boyamanın gevşetilmiş, “kesirli” bir biçimi, doğrusal kurala iki çarpanıyla zaten uyuyor. Yeni çalışma, çizgeye birkaç ek çizgi ekleyerek ve yardımcı bir yapıda devasa eşleşmeler bularak kesirli boyamaları gerçek boyamalara dönüştürüyor.
Bir bootstrap. İkinci bir argüman, kapsanan çizge boyutları aralığını her adımda üste dört bölü üç (4/3) çarpanıyla genişletiyor; bedeli daha büyük bir sabit. On adım, aralığı üçte birden yaklaşık 5,92’ye taşıyor; bu, Delcourt-Postle indirgemesinin gerektirdiği 5 eşiğinin ötesinde. Bu yarı, Gyárfás’a ait eski bir hileyi kullanıyor; yazarlara göre bu hile bu probleme daha önce hiç uygulanmamıştı.

Yazarlar ispatı bilinen araçlardan inşa edilmiş olarak tanımlıyor — “mevcut sonuçların dışbükey zarfı (convex hull) içinde yer alan,” ama onun bariz bir kenarında olmayan bir şey.

Açık kalanlar

Sabit muazzam: kaba bir tahmin yaklaşık 10¹⁰⁰ veriyor. Yazarlar onu 10¹⁰’un altına indirmek için yer görüyor, ama örneğin 100’e ulaşmanın yeni fikirler gerektireceğini düşünüyor. Hadwiger’in tam sanısına dokunulmadı: “Kararsızız,” diye yazıyorlar. Makale bir ön baskı; 41 sayfalık yeni matematik şimdi başka uzmanların incelemesiyle yüzleşecek.