Dedekind numarası - Dedekind number

Sırasıyla 2, 3, 6 ve 20 elemanlı, 0, 1, 2 ve 3 bağımsız değişkenlerde monotonik Boole fonksiyonlarının serbest dağılımlı kafesleri ( açıklamayı görmek için fareyi sağ diyagramın üzerine getirin)

In matematik , Dedekind sayılar hızla büyüyen vardır tamsayılar dizisi adını Richard Dedekind Dedekind sayı 1897 yılında onları tanımlanan, M ( n ) sayar monoton boole fonksiyonları arasında n değişkenleri. Aynı şekilde, bu sayar antichains bir alt kümeleri arasında , n -eleman grubu, bir elemanların sayısı serbest dağıtım kafes ile N üreticiler veya sayısının Anahtar simpleksel kompleksleri ile N elemanları.

M ( n ) ' nin doğru asimptotik tahminleri ve bir toplam olarak kesin bir ifade bilinmektedir. Ancak Dedekind sorun değerlerini hesaplama M ( n No:) güçtür kapalı bir şekilde ifade için M ( n ) olarak bilinir ve kesin değerler M ( n ) sadece bulunmuştur n  ≤ 8.

Tanımlar

Bir Boole fonksiyonu girdi olarak alan bir fonksiyonudur , n Boolean değişkenleri (olduğunu ya sahte ya da gerçek veya eşdeğer olabilir değerleri değerleri ikili ya da 0 ya da 1 olabilir), ve çıktı olarak, başka bir Boolean değişkeni üretir. Her giriş kombinasyonu için, girişlerden birini yanlıştan doğruya değiştirmek yalnızca çıktının yanlıştan doğruya geçmesine ve doğrudan yanlışa geçmesine neden olmazsa monotondur . Dedekind sayısı M ( n ), n değişken üzerindeki farklı monotonik Boolean fonksiyonlarının sayısıdır .

Setlerden oluşan bir antikain ( Sperner ailesi olarak da bilinir ), hiçbiri başka bir sette bulunmayan bir set ailesidir. Eğer V bir dizi n bir antichain Boolean değişkenleri, bir alt kümelerinin V monoton Boole fonksiyonu tanımlayan f değeri, f doğru girişlerin bir alt grubunu, girişlerin, belirli bir dizi için de geçerlidir f ait A ve aksi takdirde false. Tersine, her monoton Boole işlevi, bu şekilde, işlev değerini doğru olmaya zorlayabilen Boole değişkenlerinin minimum alt kümelerinin bir antikainini tanımlar. Bu nedenle, Dedekind sayısı M ( n ), bir n- element kümesinin alt kümelerinin farklı antikainlerinin sayısına eşittir .

Aynı nesne sınıfını tanımlamanın üçüncü, eşdeğer bir yolu kafes teorisini kullanır . Herhangi iki monoton mantıksal fonksiyonların kaynaktan f ve g diğer iki monoton Boole fonksiyonlar bulunmaktadır f ∧ g ve f ∨ g , bunların mantıksal birlikte ve mantıksal ayırma sırasıyla. Tüm monoton mantıksal fonksiyonların aile n girişler, bu iki işlemleri ile meydana dağıtım kafes ile verilir, kafes Birkhoff temsil teoremi gelen kısmen sıralı bir setin alt kümelerinin n kısmi sipariş olarak grubu dahil olan değişkenler. Bu yapı üretir ücretsiz dağıtıcı kafes ile n jeneratörleri. Böylece, Dedekind sayıları, serbest dağılımlı kafeslerdeki elemanların sayısını sayar.

Dedekind sayıları, aynı zamanda , ailedeki bir kümenin herhangi bir alt kümesinin de aileye ait olduğu özelliğe sahip küme aileleri olan n eleman üzerindeki soyut basit komplekslerin sayısını sayar (bir veya daha fazla) . Herhangi bir antikain, basit bir kompleksi, antikain üyelerinin alt kümelerinin ailesini ve tersine, karmaşık bir formdaki maksimum basitleri bir antikain belirler.

Misal

İçin n = 2, altı tekdüze Boole fonksiyonları ve iki eleman seti {altkümelerinden altı antichains vardır x , y }:

• Fonksiyonu f ( x , y , her zaman kendi giriş değerleri göz ardı eder ve) = kapalı yanlış tekabül döner boş antichain Ö.
• Mantıksal birlikte f ( x , y ) =  x  ∧  y antichain karşılık gelir {{ x , y }} tek dizi {ihtiva eden x , y }.
• Fonksiyonu f ( x , y ) =  x ikinci bağımsız değişken sayar ve antichain ilk argümanı tekabül döndüren {{ x }} tek bir dizi içeren { x }
• Fonksiyonu f ( x , y ) =  y antichain {{için ilk bağımsız değişken ve döner ikinci bağımsız tekabül göz ardı y }} tek bir dizi içeren { y }
• Mantıksal ayırma f ( x , y ) =  x  ∨  y antichain karşılık gelir {{ X }, { y }} iki bloklu { x } ve { y }.
• Fonksiyonu f ( x , y , her zaman kendi giriş değerleri göz ardı eder ve) = doğru sadece boş kümesini içeren antichain {O} doğru tekabül döndürür.

Değerler

Dedekind sayılarının kesin değerleri 0 ≤ n ≤ 8 ile bilinir :

2, 3, 6, 20, 168, 7581, 7.828.354, 2414682040998, 56130437228687557907788 (dizi A000372 olarak OEIS ).

Bu sayıların ilk altı'sı Kilise (1940) tarafından verilmektedir . M (6) Ward (1946) , M (7) Church (1965) ve Berman & Köhler (1976) ve M (8) Wiedemann (1991) tarafından hesaplandı .

Eğer n, hatta, daha sonra M ( n ) de düz olmalıdır. Beşinci Dedekind sayısının hesaplanması M (5) = 7581 tr bir varsayım yanlışlığı Garrett Birkhoff bu K ( n ) her zaman (2 ile bölünebilen n  - 1) (2 , n  - 2).

Toplama formülü

Kisielewicz (1988) , antikainlerin mantıksal tanımını Dedekind sayıları için aşağıdaki aritmetik formüle yeniden yazdı:

${\ displaystyle M (n) = \ toplam _ {k = 1} ^ {2 ^ {2 ^ {n}}} \ prod _ {j = 1} ^ {2 ^ {n} -1} \ prod _ { i = 0} ^ {j-1} \ left (1-b_ {i} ^ {k} b_ {j} ^ {k} \ prod _ {m = 0} ^ {\ log _ {2} i} ( 1-b_ {m} ^ {i} + b_ {m} ^ {i} b_ {m} ^ {j}) \ sağ),}$

burada bir inci bit sayısının kullanılarak yazılabilir, zemin işlevi olarak ${\ displaystyle b_ {i} ^ {k}}$${\ displaystyle i}$${\ displaystyle k}$

${\ displaystyle b_ {i} ^ {k} = \ sol \ lfloor {\ frac {k} {2 ^ {i}}} \ sağ \ rfloor -2 \ sol \ lfloor {\ frac {k} {2 ^ { i + 1}}} \ sağ \ rfloor.}$

Bununla birlikte, bu formül, toplamdaki çok sayıda terim nedeniyle büyük n için M ( n ) değerlerini hesaplamak için yararlı değildir .

Asimptotik

Logaritma Dedekind sayıların sınırları yoluyla doğru tahmin edilebilir

${\ displaystyle {n \ \ lfloor n / 2 \ rfloor} \ leq \ log _ {2} M (n) \ leq {n \ seç \ lfloor n / 2 \ rfloor} \ sol (1 + O \ sol ( {\ frac {\ log n} {n}} \ sağ) \ doğru).}$

Burada sol eşitsizlik, her bir kümenin tam olarak unsurlara sahip olduğu antikain sayısını sayar ve sağ eşitsizlik Kleitman ve Markowsky (1975) tarafından kanıtlanmıştır . ${\ displaystyle \ lfloor n / 2 \ rfloor}$

Korshunov (1981) daha da doğru tahminler sağladı

${\ Displaystyle M (n) = (1 + o (1)) 2 ^ {n \ \ lfloor n / 2 \ rfloor} \ seçin a (n)}$

n için bile ve

${\ Displaystyle M (n) = (1 + o (1)) 2 ^ {n \ \ lfloor seçin n / 2 \ rfloor +1} \ exp (b (n) + c (n))}$

garip n için , nerede

${\ displaystyle a (n) = {n \ seçin n / 2-1} (2 ^ {- n / 2} + n ^ {2} 2 ^ {- n-5} -n2 ^ {- n-4} ),}$

${\ displaystyle b (n) = {n \ (n-3) / 2} (2 ^ {- (n + 3) / 2} + n ^ {2} 2 ^ {- n-6} -n2 ^ seçin {-n-3}),}$

ve

${\ displaystyle c (n) = {n \ (n-1) / 2} (2 ^ {- (n + 1) / 2} + n ^ {2} 2 ^ {- n-4}) seçin.}$

Bu tahminlerin arkasındaki ana fikir, çoğu antikanda, tüm setlerin n / 2'ye çok yakın boyutlara sahip olmasıdır . İçin n = 2, 4, 6, 8 Korshunov formülü% 9.8,% 10.2,% 4.1 bir faktör ile tutarlı bir tahmin sağlar ve -3.3% sırasıyla.

Notlar

Referanslar

• Berman, Joel; Köhler, Peter (1976), "Sonlu dağılım kafeslerinin kardinaliteleri", Mitt. Matematik. Sem. Giessen , 121 : 103–124, MR   0485609 .
• Church, Randolph (1940), "Belirli serbest dağıtım yapılarının sayısal analizi", Duke Mathematical Journal , 6 : 732–734, doi : 10.1215 / s0012-7094-40-00655-x , MR   0002842 .
• Church, Randolph (1965), "7 jeneratörlü serbest dağıtım kafesinin derecesine göre numaralandırma", Amerikan Matematik Derneği Bildirileri , 11 : 724 . Wiedemann (1991) tarafından aktarıldığı gibi .
• Dedekind, Richard (1897), "Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler", Gesammelte Werke , 2 , s. 103–148 .
• Kahn, Jeff (2002), "Entropi, bağımsız kümeler ve antikainler: Dedekind sorununa yeni bir yaklaşım", Amerikan Matematik Derneği Proceedings of the American Mathematical Society , 130 (2): 371–378 , doi : 10.1090 / S0002-9939-01-06058 -0 , MR   1862115 .
• Kisielewicz, Andrzej (1988), "Dedekind'in izoton Boole fonksiyonlarının sayısı üzerindeki probleminin bir çözümü", Journal für die Reine ve Angewandte Mathematik , 386 : 139–144, doi : 10.1515 / crll.1988.386.139 , MR   0936995
• Kleitman, D .; Markowsky, G. (1975), "Dedekind problemi üzerine: izoton Boole fonksiyonlarının sayısı. II", Amerikan Matematik Derneği İşlemleri , 213 : 373–390, doi : 10.2307 / 1998052 , MR   0382107 .
• Korshunov, AD (1981), "Monoton Boolean fonksiyonlarının sayısı", Problemy Kibernet. , 38 : 5–108 , MR   0640855 .
• Ward, Morgan (1946), "Serbest dağıtım kafeslerinin sırası hakkında not", Amerikan Matematik Derneği Bülteni , 52 : 423, doi : 10.1090 / S0002-9904-1946-08568-7 .
• Wiedemann, Doug (1991), "Sekizinci Dedekind sayısının hesaplanması", Order , 8 (1): 5–6, doi : 10.1007 / BF00385808 , MR   1129608 .
• Yamamoto, Koichi (1953), "Serbest dağıtım kafeslerinin sırası hakkında not", Kanazawa Üniversitesi Bilim Raporları , 2 (1): 5–6, MR   0070608 .
• Zaguia, Nejib (1993), "İzotone haritaları: numaralandırma ve yapı", Sauer, NW; Woodrow, RE; Sands, B. (ed.), Kümeler ve Mantıkta Sonlu ve Sonsuz Kombinatorikler (Proc. NATO Advanced Study Inst., Banff, Alberta, Kanada, 4 Mayıs 1991) , Kluwer Academic Publishers, s. 421–430, MR   1261220 .