Van der Waerdens teoremi - Van der Waerdens theorem - Wikipedia

Van der Waerden teoremi dalındaki bir teorem matematik aranan Ramsey teorisi. Van der Waerden'in teoremi, verilen herhangi bir pozitif tamsayılar r ve kbir numara var N öyle ki tam sayılar {1, 2, ..., N} renklidir ve her biri r farklı renkler, o zaman en azından k tamsayılar aritmetik ilerleme elemanları aynı renktedir. En az böyle N ... Van der Waerden numarası W(rk), Hollandalı matematikçinin adını almıştır B. L. van der Waerden.[1]

Misal

Örneğin, ne zaman r = 2, diyelim ki iki renk var kırmızı ve mavi. W(2, 3) 8'den büyüktür, çünkü {1, ..., 8} 'den tam sayıları şu şekilde renklendirebilirsiniz:

 1  2  3  4  5  6  7  8 
 B  R  R  B  B  R  R  B 

ve aynı renkteki üç tam sayı bir aritmetik ilerleme. Ancak böyle bir ilerleme yaratmadan sonuna dokuzuncu bir tam sayı ekleyemezsiniz. Eklerseniz kırmızı 9, sonra kırmızı 3, 6, ve 9 aritmetik ilerleme içindedir. Alternatif olarak, bir mavi 9, sonra mavi 1, 5, ve 9 aritmetik ilerleme içindedir.

Aslında böyle bir ilerleme yaratmadan 1'den 9'a kadar boyama yapmanın bir yolu yoktur (örnekler dikkate alınarak ispatlanabilir). Bu nedenle, W(2, 3) 9'dur.

Açık problem

Değerlerinin belirlenmesi açık bir problemdir. W(r, k) çoğu değer için r ve k. Teoremin ispatı yalnızca bir üst sınır sağlar. Durum için r = 2 ve k = 3, örneğin, aşağıda verilen argüman, {1, ..., 325} tam sayılarını iki renkle renklendirmenin 3'ün tek renkli aritmetik ilerlemesi olacağını garanti etmek için yeterli olduğunu göstermektedir. Ama aslında, 325'in sınırı çok gevşektir; gereken minimum tam sayı sayısı yalnızca 9'dur. {1, ..., 9} tam sayılarının herhangi bir renklendirmesi, bir renkten oluşan eşit aralıklı üç tam sayıya sahip olacaktır.

İçin r = 3 ve k = 3, teoremin verdiği sınır 7'dir (2 · 37 + 1)(2·37·(2·37 + 1) + 1) veya yaklaşık 4,22 · 1014616. Ama aslında, 3 uzunluğunun tek renkli ilerlemesini garanti etmek için bu kadar çok tam sayıya ihtiyacınız yok; yalnızca 27'ye ihtiyacınız var. (Ve {1, ..., 26} 'yı üç renkle renklendirmek mümkündür, böylece 3 uzunluğunun tek renkli aritmetik ilerlemesi olmaz; örneğin:

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26 
 R  R  G  G  R  R  G  B  G  B  B  R  B  R  R  G  R  G  G  B  R  B  B  G  B  G 

.)

Genel üst sınırı herhangi bir 'makul' işleve indirgeyen herkes büyük bir nakit para ödülü kazanabilir. Ronald Graham bir ödül teklif etti ABD$ Göstermek için 1000 W(2,k)<2k2.[2] Şu anda bilinen en iyi üst sınır, Timothy Gowers,[3] kim kurar

önce benzer bir sonuç belirleyerek Szemerédi teoremi, Van der Waerden teoreminin daha güçlü bir versiyonu. Daha önce en iyi bilinen sınır, Saharon Shelah ve ilk önce bir sonucu kanıtlayarak devam etti Hales-Jewett teoremi Van der Waerden teoreminin bir başka güçlendirmesidir.

Şu anda bilinen en iyi alt sınır bu her şey için olumlu mu sahibiz yeterince büyük herkes için .[4]

Van der Waerden teoreminin kanıtı (özel bir durumda)

Aşağıdaki kanıt kaynaklanmaktadır Ron Graham ve B.L. Rothschild.[5] Khinchin[6] Tahmin yapmadan teoremin oldukça basit bir kanıtını verir W(rk).

W (2, 3) durumunda kanıt

W (2, 3) tablosu
bc(n): tam sayıların rengi
012345
 R  R  B  R  B 
1678910
 B  R  R  B  R 
64321322323324325
 R  B  R  B  R 

Yukarıda belirtilen özel durumu kanıtlayacağız, W(2, 3) ≤ 325. Let c(n) {1, ..., 325} tam sayılarının rengi olabilir. Aritmetik ilerlemede aynı renkte olan üç {1, ..., 325} öğesi bulacağız.

{1, ..., 325} 'i 65 bloğa {1, ..., 5}, {6, ..., 10}, ... {321, ..., 325}, dolayısıyla her bloğa bölün {5 biçimindedirb + 1, ..., 5b Bazıları için + 5} b {0, ..., 64} içinde. Her tam sayı ya da renkli olduğundan kırmızı veya maviher blok 32 farklı yoldan biriyle renklendirilir. Tarafından güvercin deliği ilkesi ilk 33 blok arasında aynı renkte olan iki blok vardır. Yani iki tam sayı vardır b1 ve b2, her ikisi de {0, ..., 32}, öyle ki

c(5b1 + k) = c(5b2 + k)

hepsi için k {1, ..., 5} içinde. Üç tam sayı arasında 5b1 + 1, 5b1 + 2, 5b1 + 3, aynı renkten en az iki tane olmalıdır. (The güvercin deliği ilkesi tekrar.) Bunları 5 arayınb1 + a1 ve 5b1 + a2, nerede aben {1,2,3} içinde ve a1 < a2. Varsayalım (genellik kaybı olmadan) bu iki tamsayının her ikisi de kırmızı. (Eğer ikisi de iseler mavi, sadece takas et 'kırmızı' ve 'mavi' Akabinde.)

İzin Vermek a3 = 2a2 − a1. 5 iseb1 + a3 dır-dir kırmızı, sonra aritmetik ilerlememizi bulduk: 5b1 + aben hepsi kırmızı.

Aksi takdirde, 5b1 + a3 dır-dir mavi. Dan beri a3 ≤ 5, 5b1 + a3 içinde b1 blok ve bu yana b2 blok aynı renkte, 5b2 + a3 aynı zamanda mavi.

Şimdi izin ver b3 = 2b2 − b1. Sonra b3 64. 5 tamsayısını düşününb3 + a3, hangisi ≤ 325 olmalıdır. Ne renk?

Öyleyse kırmızı, sonra 5b1 + a1, 5b2 + a2ve 5b3 + a3 oluşturmak kırmızı aritmetik ilerleme. Ama eğer öyleyse mavi, sonra 5b1 + a3, 5b2 + a3ve 5b3 + a3 oluşturmak mavi aritmetik ilerleme. Her iki durumda da bitirdik.

W (3, 3) durumunda kanıt

W (3, 3) tablosu
g=2·37·(2·37 + 1) ,
m=7(2·37 + 1)
bc(n): tam sayıların rengi
0123m
 G  R  R  B 
1m+1m+2m+32a
 B  R  G  R 
ggm + 1gm + 2gm + 3(g + 1) m
 B  R  B  G 

Bunu göstermek için benzer bir argüman ileri sürülebilir. W(3, 3) ≤ 7(2·37+1)(2·37·(2·37+1)+1). Bir tam sayıları 2 3'e bölerek başlar7·(2·37 + 1) 7'li + 1 grup (2 · 37 +1) her biri tam sayı; ilk 3'ün7·(2·37 + 1) + 1 gruplardan ikisi aynı renkte olmalıdır.

Bu iki grubun her birini 2 3'e bölün7Her biri 7 tam sayıdan oluşan +1 alt grup; ilk 3'ün7 Her grupta + 1 alt grup, iki alt grup aynı renkte olmalıdır. Bu özdeş alt grupların her birinde, ilk dört tam sayıdan ikisi aynı renkte olmalıdır, örneğin kırmızı; bu ya a kırmızı diyelim ki ilerleme veya farklı renkteki bir öğe mavi, aynı alt grupta.

Aynı renkte iki alt grubumuz olduğundan, üçüncü bir alt grup var, yine aynı grupta, eğer biri varsa kırmızı veya mavi, tamamlar kırmızı veya mavi için olana benzer bir yapı ile ilerleme W(2, 3). Farz edin ki bu eleman yeşil. Aynı renkte bir grup olduğundan, kırmızı, mavi, ve yeşil tanımladığımız unsurlar; şimdi bir çift bulabiliriz kırmızı elemanlar, bir çift mavi öğeler ve bir çift yeşil Aynı tam sayıya 'odaklanan' öğeler, böylece renk ne olursa olsun, bir ilerlemeyi tamamlaması gerekir.

Genel durumda kanıt

Kanıtı W(2, 3) esasen şunu kanıtlamaya bağlıdır: W(32, 2) ≤ 33. {1, ..., 325} tam sayılarını, her biri 32 farklı şekilde renklendirilebilen 65 'bloğa' böler ve sonra ilk 33 bloğun iki bloğunun olması gerektiğini gösteririz. aynı renk ve tersi renkte bir blok var. Benzer şekilde, kanıtı W(3, 3) bunu kanıtlamaya bağlıdır

Bir çifte indüksiyon renk sayısı ve ilerlemenin uzunluğu üzerine teorem genel olarak kanıtlanmıştır.

Kanıt

Bir D boyutlu aritmetik ilerleme (AP) formun sayılarından oluşur:

nerede a temel noktadır, s'ler pozitif adım boyutlarıdır ve ben0 ile L-1. Bir dboyutlu AP homojen hepsi aynı renk olduğunda bazı renkler için.

Bir Dfaydalarla birlikte boyutsal aritmetik ilerleme yukarıdaki formun tüm sayılarıdır, ancak aritmetik ilerlemenin bazı "sınırlarını" eklediğiniz yer, yani bazı endeksler benşuna eşit olabilir L. Vurduğunuz taraflar, ilk k beneşittir Lve kalan ben's küçüktür L.

A'nın sınırları Dfaydaları olan boyutsal AP, boyutun bu ek aritmetik ilerlemeleridir 0-boyutlu aritmetik ilerleme, indeks değerindeki tek noktadır. . Bir Davantajlı boyutlu AP homojen sınırların her biri ayrı ayrı homojen olduğunda, ancak farklı sınırların mutlaka aynı renge sahip olması gerekmiyor.

Ardından miktarı tanımlayın MinN (L, D, N) en küçük tamsayı olmak için herhangi bir atama N uzunluk aralığı için renkler MinN veya daha fazlası zorunlu olarak homojen bir Dfaydalarla birlikte boyutsal aritmetik ilerleme.

Amaç, boyutunu sınırlamaktır. MinN. Bunu not et MinN (L, 1, N) Van der Waerden'in numarasının üst sınırıdır. Aşağıdaki gibi iki başlangıç ​​adımı vardır:

Lemma 1 — Varsaymak MinN belirli bir uzunlukta bilinir L aritmetik ilerlemelerin tüm boyutları için D. Bu formül bir sınır verir MinN boyutu artırdığınızda D + 1:

İzin Vermek , sonra

Kanıt —

İlk olarak, eğer varsa n1 aralığının renklendirilmesi ...ben, tanımlayabilirsin blok boyama nın-nin kboyutlu bloklar. Sadece her diziyi düşünün k her birinde renkler k benzersiz bir renk tanımlamak için blok. Bunu ara k-blocking bir n-boyama. k-blocking bir n uzunluk rengi l üretir nk uzunluk rengi l / k.

Yani verilen bir nbir aralığın renklendirilmesi ben boyut yapabilirsiniz M-block it into an nM uzunluk rengi . Ancak bu, tanımı gereği MinN, 1 boyutlu bir aritmetik dizi (faydaları olan) bulabileceğiniz L hepsi aynı blok renginde olan eşit aralıklı bloklar dizisi olan blok renklendirmesinde, yani bir sürü uzunluk bloğunuz var M İçeride tam olarak aynı renk dizisine sahip olan eşit aralıklı orijinal sırayla.

Şimdi, tanımına göre Mbulabilirsin dBu bloklardan herhangi birinde fayda sağlayan boyutlu aritmetik dizi ve tüm bloklar aynı renk dizisine sahip olduğundan, dfaydaları olan boyutsal AP, bloktan bloğa çevrilerek tüm bloklarda görünür. Bu a'nın tanımıdır d + 1 boyutsal aritmetik ilerleme, böylece homojen bir d + 1 boyutlu AP. Yeni adım parametresi sD + 1 bloklar arasındaki mesafe olarak tanımlanır.

Ama yardıma ihtiyacın var. Şimdi elde ettiğiniz sınırların tümü eski sınırlardır, artı bunların aynı renkteki bloklara çevrilmesidir, çünkü benD + 1 her zaman daha azdır L. Bunun gibi olmayan tek sınır, ne zaman 0 boyutlu noktadır? . Bu tek bir noktadır ve otomatik olarak homojendir.

Lemma 2 — Varsaymak MinN bir değeriyle bilinir L ve olası tüm boyutlar D. Ardından uzunluk için MinN'yi bağlayabilirsiniz L + 1.

Kanıt —

Verilen bir n- boyut aralığının renklendirilmesi MinN (L, n, n), tanım gereği, boyutun faydalarını içeren bir aritmetik dizi bulabilirsiniz n uzunluk L. Ama şimdi, "fayda" sınırlarının sayısı renklerin sayısına eşittir, bu nedenle homojen sınırlardan biri, örneğin boyut khomojen fayda sınırlarından bir diğeri ile aynı renge sahip olmalıdır, diyelim ki boyut p . Bu, bir uzunluğa izin verir L + 1 aritmetik dizi (boyut 1'in) içinde bir çizgi boyunca ilerleyerek inşa edilecek ksağda biten boyutsal sınır pboyutsal sınır ve içindeki son nokta dahil pboyutlu sınır. Formüllerde:

Eğer

ile aynı renge sahip

sonra

aynı renge sahip
yani sen uzunluk dizisi yapar L+1.

Bu, bir boyut 1 dizisi oluşturur ve "faydalar" otomatiktir, sadece hangi renkte olursa olsun başka bir noktaya ekleyin. Bu sınır noktasını dahil etmek için, aralık büyüklüğünden kesinlikle daha küçük olan adımın mümkün olan maksimum değeri ile aralığı uzatmak gerekir. Yani aralık boyutunu ikiye katlamak kesinlikle işe yarayacaktır ve bu iki faktörün sebebidir. Bu, indüksiyonu tamamlar L.

Temel durum: MinN (1, d, n) = 1yani eğer 1 uzunluğunun homojen olmasını istiyorsanız dfaydaları olsun ya da olmasın, boyutsal aritmetik dizi, yapacak hiçbir şeyiniz yok. Bu, tümevarımın temelini oluşturur. Van der Waerden teoreminin kendisi şu iddiadır: MinN (L, 1, N) sonludur ve temel durum ile tümevarım adımlarını takip eder.[5]

Ayrıca bakınız

Notlar

  1. ^ van der Waerden, B. L. (1927). "Beweis einer Baudetschen Vermutung". Nieuw. Arch. Wisk. (Almanca'da). 15: 212–216.
  2. ^ Graham, Ron (2007). "Ramsey Teorisinde En Sevdiğim Sorunlardan Bazıları". INTEGERS: Kombinatoryal Sayı Teorisinin Elektronik Dergisi. 7 (2): # A15.
  3. ^ Gowers, Timothy (2001). "Szemerédi teoreminin yeni bir kanıtı". Geom. Funct. Anal. 11 (3): 465–588. doi:10.1007 / s00039-001-0332-9.
  4. ^ Szabó, Zoltán (1990). "Lovász'ın yerel lemmasının bir uygulaması - van der Waerden numarası için yeni bir alt sınır". Random Struct. Algoritmalar. 1 (3): 343–360. doi:10.1002 / rsa.3240010307.
  5. ^ a b Graham, R.L.; Rothschild, B.L. (1974). "Van der Waerden'in aritmetik ilerlemeler üzerine teoreminin kısa bir kanıtı". Proc. Amer. Matematik. Soc. 42 (2): 385–386. doi:10.1090 / S0002-9939-1974-0329917-8.
  6. ^ Khinchin (1998), sayfa 11–17, bölüm 1)

Referanslar

Dış bağlantılar