AYÇİÇEĞİ SANISI ÇÖZÜLDÜ
1’den n’ye kadar olan sayıları alın ve bunlardan bazılarını seçmenin tüm yollarına bakın: bu türden 2ⁿ alt küme vardır. Şimdi tam olarak aynı ortak parçayı paylaşan, başka hiçbir şeyi paylaşmayan birkaç alt küme seçin. Matematikçiler buna ayçiçeği der: ortak parça çekirdektir, her kümeden geriye kalan da başka hiçbir yaprağa değmeyen bir yapraktır.
Ayçiçekleri kombinatoriğin temel araçlarından biridir. Makale, bazı mantık devrelerinin sınırlarıyla, “cap set” problemiyle, hızlı matris çarpımıyla ve bilgi kuramıyla bağlantılarını sıralıyor.
1970’ten kalma bir soru
Yazarlara göre bunlarla ilgili en doğal soru, Paul Erdős’ün 1970 tarihli bir makalesine dayanıyor. {1, …, n} kümesinin alt kümelerinden oluşan bir koleksiyon, hiçbir k kümesi bir ayçiçeği oluşturmuyorsa en fazla ne kadar büyük olabilir?
1970’lerde Erdős ve Endre Szemerédi, böyle bir koleksiyonun 2ⁿ olası alt kümeden üstel olarak daha küçük olması gerektiğini öne sürdü: 2’den kesinlikle küçük bir c sayısı için en fazla cⁿ.
Onlarca yıl boyunca en iyi sınırlar yalnızca küçük bir kazanç sağladı, tabanı 2’nin altına indirmeye hiçbir zaman yetmedi. Yalnızca üç yapraklı durum (k = 3), 2016’da cap set problemindeki atılım ve Alon, Shpilka ve Umans’a ait bir indirgeme sayesinde çözüldü.
Sınır
Matija Bucić ve Fankang He (Viyana Üniversitesi) ile Hyunwoo Lee (KAIST ve Güney Kore Temel Bilimler Enstitüsü) sanıyı her k ≥ 3 için kanıtlıyor. Ana teoremleri: k yapraklı ayçiçeği içermeyen bir koleksiyonun en fazla
3 · (2 − 1/(16k³))ⁿ
elemanı vardır. Taban 2’nin hemen altında duruyor, ama 2’nin altında sabit bir sayı ve Erdős ile Szemerédi’nin istediği tam olarak buydu. 1997’den kalma bir yapı, büyük k için gerçek değerin bundan çok daha düşük olamayacağını gösteriyor.
Kümelerden vektörlere
Kanıt, problemin vektörlerle ifade edilen bir versiyonundan geçiyor. Sayıları D elemanlı n bloğa bölün ve her bloktan bir eleman seçin: her seçim bir vektördür. Birkaç vektör, her konumda girdileri ya hepsi eşit ya da hepsi farklı olduğunda bir ayçiçeği oluşturur.
Yazarlar ardından bir “ayçiçeği test edicisi” kuruyor: ayçiçeği içermeyen bir koleksiyon üzerinde, yalnızca tüm girdileri aynı vektör olduğunda sıfırdan farklı olan bir fonksiyon. Yeni bileşen, bu fonksiyonu adım adım düşük dereceli interpolasyon polinomlarıyla yazmak. Bu polinomları saymak koleksiyonun boyutunu sınırlıyor (Teorem 2). Olasılıksal bir argüman, yani tüm küme boyutları üzerinden ortalaması alınan rastgele bloklar, sınırı sıradan kümelere geri taşıyor.
Bir makine buldu, bir başkası doğruladı
Makalenin yapay zekâ konusundaki açıklaması alışılmadık derecede doğrudan. Teorem 2’nin kanıtını ChatGPT 6 Astra Pro buldu; bu, bilinen üç yapraklı argümanı genelleştirmesini isteyerek başlayan kısa bir tartışmanın ardından oldu. Yazarların bu adıma başka bir amaç için ihtiyacı vardı: Szemerédi’nin ortaya attığı bir graf probleminin indüklenmiş bir versiyonu; bunu sonraki bir notta duyuracaklarını belirtiyorlar.
Model kanıtını “slice rank” (dilim rankı) dilinde yazdı. Yazarlar onu, okuyucular için daha kolay buldukları polinom yönteminin diliyle yeniden yazdı. Her sonucu doğruladıklarını ve tüm sorumluluğu üstlendiklerini, ayrıca kanıtın bir kanıt denetleme yazılımı olan Lean 4.35’te doğrulandığını ve doğrulamanın Palomar deposunda yayımlanacağını belirtiyorlar.
Neyi çözmüyor
Yazarlar tabanı optimize etmeye çalışmadı. Üç yaprak için, Naslund ve Sawin’in yaklaşık 1,89 olan 2017 sınırını geçmiyor. Daha güçlü kardeş problem olan Erdős–Rado ayçiçeği sanısı ise hâlâ açık: sınırları hâlâ büyük ölçüde blok boyutu D’ye bağlı ve o problemin yasakladığı da tam olarak bu.