ÖDEYEMEYECEĞİNİZ EN BÜYÜK TUTARA ARTIK SIKI BİR SINIR VAR

Yalnızca birkaç tür madeni parayı, sınırsız miktarda kabul eden ve asla para üstü vermeyen bir kasa düşünün. Bazı tutarlar tam olarak ödenebilir; bazıları ise asla. Matematikçiler para değerlerine üreteçler (generators) der ve aldatıcı derecede basit bir soru sorar: ödenemeyen en büyük tutar nedir?

Asla ödenemeyen tutarlar

Hepsinin paylaştığı bir çarpan bulunmayan a₁ < a₂ < … < aₙ tam sayılarını alın. Bu sayıların her birini istediğiniz kadar kez toplayarak elde edilen bir toplam “temsil edilebilir”dir. Temsil edilemeyen tam sayılar yalnızca sonlu sayıdadır; bunların en büyüğü Frobenius sayısı F’dir. (Değerlerden biri 1 ise her şey ödenebilir ve F, −1 olarak tanımlanır.)

Küçük bir örnek: 3, 4 ve 6’lık paralarla 3, 4, 6, 7, 8’i ve bundan sonraki her tutarı ödeyebilirsiniz, ama asla 1, 2 ya da 5’i ödeyemezsiniz. Dolayısıyla F = 5. 3 ile 6’nın ortak bir çarpanı olduğuna dikkat edin; önemli olan, üçünün birden ortak bir çarpanı olmaması.

İki para için kesin bir yanıt var, Sylvester formülü: F(a₁, a₂) = a₁a₂ − a₁ − a₂. Üç ya da daha fazlası için iş, F’yi sınırlamaktan ibaret: paralardan hesaplanan belirli bir değeri aşamayacağını kanıtlamak.

İnatçı bir 2 çarpanı

Paul Erdős ve Ronald Graham, üç ya da daha fazla üreteç için şunu kanıtladı:

F ≤ 2aₙ₋₁⌊aₙ/n⌋ − aₙ

Burada aₙ en büyük değer, aₙ₋₁ ikinci en büyük değer, n değerlerin sayısı; ⌊ ⌋ ise aşağı yuvarlama anlamına geliyor. Sylvester formülü gibi bu da en büyük iki parayı içeriyor.

İkili ayrıca en kötü durumu, yani n değerin hepsi en fazla t olduğunda mümkün olan en büyük F’yi de tahmin etti. Tahminleri arasındaki kabaca 2 katlık fark, Erdős Problemi #433 olarak kayda geçen bir sanıya yol açtı. Jacques Dixmier bu sanıyı çözdü ve ayrıca her küme için geçerli daha basit bir sınır kanıtladı: F ≤ aₙ²/(n − 1). 2 çarpanı gitti, ama ikinci en büyük para da gitti.

En büyük iki parayı birden korumak

Zhejiang Üniversitesi Bilgisayar Bilimi ve Teknolojisi Fakültesi’nden Lin Chen, Tingwei Hu, Yuchen Mao ve Guochuan Zhang ikisini birden istedi: 2 çarpanı olmasın ve ikinci en büyük para korunsun. İki ya da daha fazla değerden oluşan her küme için geçerli yanıtları:

F ≤ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ − 1

Burada ⌈ ⌉ yukarı yuvarlama anlamına geliyor. Erdős ve Graham’ınkiyle karşılaştırıldığında 2 çarpanı ortadan kalkmış; bunun bedeli n yerine n − 1’e bölmek ve yukarı yuvarlamak. Dixmier’ninkiyle karşılaştırıldığında, ikinci en büyük para en büyüğün yanında küçük kaldığında yeni sınır kayda değer ölçüde daha küçük olabiliyor.

3, 4, 6 örneğinde Erdős ve Graham’ın sınırı 10, Dixmier’ninki 18, yenisi ise 4 × 3 − 6 − 1 = 5 veriyor; tam olarak gerçek değer. Bu şaşırtıcı değil: bu küme, aşağıda anlatılan ve sınıra tam olarak ulaşmak üzere kurulmuş uç durumlar ailesine ait; makale tipik kümeler üzerinde hiçbir karşılaştırma vermiyor.

Tutarları kalanlarına göre sıralamak

İspat, Erdős ve Graham’ın yolunu izliyor. Her tutarı, en büyük para aₙ’ye bölümünden kalana göre sıralayın. Daha küçük paraların bir toplamı belirli bir kalana ulaştığında, aₙ’nin kopyalarını eklemek o kalana sahip daha büyük her tutara ulaşmayı sağlar. Yapılması gereken, her kalana ucuza ulaşılabileceğini göstermek.

Kilit araç, bir toplamlar kümesinin ne kadar büyük olması gerektiğine dair Kneser teoremi. Erdős ve Graham bunu, yaklaşık aₙ/n paradan oluşan toplamların kalanların yarısından fazlasını kapsadığını göstermek için kullandı, ardından hepsini kapsamak için ikiye katladı. Bu toplamlardaki her para en fazla aₙ₋₁ değerinde, dolayısıyla para sayısını ikiye katlamak maliyeti de ikiye katlıyor: 2 çarpanı buradan geliyor.

Yeni ispat ⌈aₙ/(n − 1)⌉ paradan oluşan toplamlar kullanıyor. Bu toplamlar bazı kalanları kaçırdığında Kneser teoremi, eksik kalanların rastgele dağılmadığını söylüyor: düzenli aralıklarla dizilmiş kalanlardan oluşan bütün aileler oluşturuyorlar. Ne kadar çok aile eksikse, daha küçük paralar ulaşılan her aileye o kadar çok yığılmak zorunda; böylece bu ailelerin her biri birkaç küçük para içeriyor ve eksik ailelere ulaşmak için gereken birkaç ek para ucuz oluyor. Toplam hiçbir zaman ⌈aₙ/(n − 1)⌉ × aₙ₋₁’i aşmıyor.

Bu ilk adım, sınırı sondaki “− 1” olmadan veriyor. Son birim ayrı bir argümandan geliyor; bu argüman, yalnızca tek bir biçimde oluşturulabilen toplamlar hakkındaki bir Scherk ve Kemperman teoremine dayanıyor ve sınırdaki aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ tutarının kendisinin her zaman ödenebileceğini gösteriyor. Teşekkür bölümüne göre yazarlar önce daha zayıf sınırı kanıtladı; ardından GPT-6, onu bir birim düşüren argümanı bulmaya yardım etti, ayrıca sınırın daha aşağı çekilemeyeceğinin ispatına ve İngilizcenin düzeltilmesine de katkı sağladı. Yazarlar nihai metnin sorumluluğunu üstlendiklerini belirtiyor.

Sınıra tam olarak dayanan durumlar

Bu sınır daha aşağı çekilemez: her n ≥ 3 için yazarlar, F’nin sınıra tam olarak eşit olduğu sonsuz sayıda küme kuruyor. Herhangi bir q ≥ 2 alın ve q, 2q, …, (n − 1)q değerlerine (n − 2)q + 1’i ekleyin. Biri hariç hepsi q’nun katı, dolayısıyla q’nun tek başına ödeyemeyeceği hiçbir şeyi ödemiyorlar. Küme, q ve (n − 2)q + 1 olmak üzere iki para gibi davranıyor ve Sylvester formülü yeni sınırla tam olarak örtüşen bir F veriyor. n = 3 ve q = 3 ile bu tarif, yukarıdaki 3, 4, 6 örneğini tam olarak üretiyor.

Daha az para, daha alçak bir tavan

Sınır yoğunluk açısından da okunabilir. Sınır, i en küçük değer ile en büyük değerden oluşan herhangi bir indirgenmiş kümeye, bunların hâlâ ortak bir çarpanı olmadığı sürece uygulanıyor. Para çıkarmak ödemeyi ancak zorlaştırabilir; bu yüzden indirgenmiş küme için kanıtlanan bir tavan, tam küme için de geçerli. Sonucu belirleyen kabaca aᵢ/i, yani ilk i değerin 1’den aᵢ’ye kadarki sayıları ne kadar yoğun doldurduğunun tersi: en yoğun grup kazanıyor. Yazarların belirttiği gibi, özellikle geri kalan paraların hâlâ hepsinde ortak bir çarpanı yoksa ikinci en büyük para kenara konabilir.

Makale tamamen kuramsal kalıyor: yeni sınırın tipik para kümelerinde ne kadar küçük olduğuna dair hiçbir sayı vermiyor ve keskinliği yalnızca üç ya da daha fazla para değeri için kanıtlanmış.