UZAYI BOYAMAK İÇİN KAÇ RENK GEREKİR? TİPİK BİR CETVEL İÇİN 2d'DEN FAZLASI DEĞİL

Düz bir düzlemin her noktasını alın ve her birine bir renk verin. Tek bir kural var: tam olarak bir birim uzaklıktaki iki nokta asla aynı renge sahip olmamalı. İşe yarayan en küçük renk sayısı nedir?

Bu, 1950’ye uzanan Hadwiger–Nelson problemidir ve yazarların deyişiyle ayrık geometrinin en ünlü açık problemlerinden biridir. Uzun süre yanıtın 4 ile 7 arasında olduğu biliniyordu. Yakın zamanda gelen bir atılım alt sınırı 5’e çıkardı. Kesin yanıt hâlâ bilinmiyor.

Cetveli değiştirmek

Mesafenin sıradan bir cetvelle ölçülmesi gerekmez. Matematikçiler pek çok başka norm — uzunluk ölçme yolu — tanımlar; her biri kendi “birim yuvarı” ile, yani merkeze uzaklığı en fazla 1 olan noktalar kümesiyle betimlenir. Alışılmış mesafe için bu yuvarlak bir küredir; başka normlar için merkezine göre simetrik herhangi bir dışbükey şekil olabilir.

Düzlem üzerindeki her norm için boyama bulmacasının yanıtı 4 ile 7 arasındadır. d boyutta ise herhangi bir norm için en fazla d’nin üstel bir fonksiyonudur ve pek çok doğal norm için — olağan Öklid normu dahil — en az üsteldir de: boyut büyüdükçe renk sayısı patlar.

Bu patlama kural mı? Noga Alon (Princeton Üniversitesi ve Tel Aviv Üniversitesi), Matija Bucić (Viyana Üniversitesi) ve James Davies (Leipzig Üniversitesi) tipik bir norma baktı. Bir normu “rastgele” seçmenin doğal bir yolu yoktur; bu yüzden topolojik bir kavram kullanıyorlar: istisnalar ihmal edilebilir (“cılız”, meagre) bir küme oluşturuyorsa, bir özellik tipik bir norm için geçerlidir. Alon, Bucić ve Lisa Sauermann’ın daha önceki çalışması, tipik bir normun en fazla 2ᵈ renk gerektirdiğini göstermiş ve bunun gerçeğe ne kadar yakın olduğunu sormuştu.

Üstel değil, doğrusal

Yanıt: hiç yakın değil. Yeni makale şunları kanıtlıyor:

• d boyutlu uzaydaki tipik bir norm için 2d renk her zaman yeterlidir;
• bu en iyi sonuçtur: açık bir norm kümesi en az 2d renk gerektirir. Dolayısıyla bazı normlar tam olarak 2d renk ister.

On boyutta tipik bir norm en fazla yirmi renk gerektirirken, olağan mesafe üstel olarak büyüyen bir sayı gerektirir. Yazarlara göre bu, herhangi bir d boyutunda “kesin dışbükey” bir norm için boyama sayısının ilk kez tam olarak belirlenmesi.

Alt sınır zarif bir tuzak kullanıyor. Birbirlerinden tam bir birim uzaklıkta olan 2d nokta bulun; yalnızca ikisi, a ve b, yarım birim uzaklıkta olsun. Tüm yapılandırmanın a’ya göre ayna görüntüsünü ekleyin. 2d’den az renkle hem b hem de onun ayna görüntüsü a’nın rengini almak zorunda kalır — oysa ikisi tam bir birim uzaklıktadır. Çelişki. Bir kararlılık lemması, bu yapılandırmanın normdaki her küçük değişikliğe dayandığını gösteriyor.

Yüksek boyutlarda yalnız bir koşucu

Üst sınır, her noktayı iyi seçilmiş bir izdüşümünün 1/(2d) genişliğindeki dilimlerden hangisine düştüğüne göre boyuyor. Bunun çalışması için, yazarların ünlü yalnız koşucu sanısının (lonely runner conjecture) yüksek boyutlu, matris versiyonu olarak tanımladığı temel bir bileşen gerekiyor:

sup over x of minᵢ ‖aᵢ · x − bᵢ‖ ≥ k / (2n)

Burada ‖t‖, t’nin en yakın tam sayıya uzaklığıdır; k boyuttaki herhangi n vektör aᵢ için geçerlidir, öyle ki bunların herhangi k tanesi bağımsızdır. Bu ifade aynı zamanda I. J. Schoenberg’in “görüş engellemesi” (view obstruction) üzerine 1978 tarihli bir sanısını çözüyor — sonsuza uzanan her görüşü kapatmak için periyodik dilimlerin ne kadar kalın olması gerektiğine dair bir soru; yazarlar bunu alanın en klasik açık problemlerinden biri olarak niteliyor — ve Henze ile Malikiosis’in ilgili bir sanısını da.

Teşekkür bölümündeki makine

Yazarlar açık konuşuyor: “ChatGPT 6 Pro, uzun bir tartışmanın ardından, Teorem 1’in kanıtında ihtiyaç duyduğumuz son bileşenin, yani Lemma 7’nin kanıtını bize sağladı”; bu tartışmada kendi gözlemlerini — tümevarım fikri ve genel strateji dahil — paylaşmışlardı. “Alt sınır argümanı da ChatGPT 6 Pro’nun yardımıyla bulundu.”

Sorular sürüyor. 2d kesin değeri tipik normların tümü için değil, açık bir norm kümesi üzerinde kanıtlandı. Sıradan Öklid mesafesi içinse yazarlar, her boyutta kesinlikle 2d’den fazla renk gerektiğini bekliyor — bu, 2, 4, 7, 8 ve 9 ile üstü boyutlarda zaten biliniyor, ama 3, 5 ve 6 boyutlarında hâlâ açık.