Aritmetik ilerlemeler üzerine Roths teoremi - Roths theorem on arithmetic progressions

Roth'un aritmetik ilerlemeler üzerine teoremi sonuçtur katkı kombinasyonu varlığıyla ilgili aritmetik ilerlemeler alt kümelerinde doğal sayılar. İlk olarak kanıtlandı Klaus Roth 1953'te.[1] Roth'un Teoremi özel bir durumdur Szemerédi Teoremi Dava için .

Beyan

Bir alt küme Bir doğal sayıların% 90'ının pozitif üst yoğunluğa sahip olduğu söylenir.

.

Roth'un aritmetik ilerlemeler üzerine teoremi (sonsuz versiyon): Pozitif üst yoğunluğa sahip doğal sayıların bir alt kümesi, 3 terimli aritmetik ilerleme içerir.

Teoremin alternatif, daha nitel bir formülasyonu, maksimum boyutuyla ilgilidir. Salem-Spencer seti hangi alt kümesidir . İzin Vermek en büyük alt kümenin boyutu 3 terimli aritmetik ilerleme içermeyen.

Roth'un aritmetik ilerlemeler üzerine teoremi (sonlu versiyon): .

Üst ve alt sınırların iyileştirilmesi hala açık bir araştırma problemidir.

Tarih

Bu yöndeki ilk sonuç, Van der Waerden teoremi 1927'de, yeterince büyük N için tam sayıların renklendirildiğini belirtir. ile renkler bir terim aritmetik ilerleme.[2]

Daha sonra 1936'da Erdős ve Turán, pozitif yoğunluğa sahip tam sayıların herhangi bir alt kümesinin keyfi olarak uzun aritmetik ilerlemeler içerdiğine dair çok daha güçlü bir sonuç çıkardılar. 1942'de, Raphaël Salem ve Donald C. Spencer 3-AP içermeyen bir setin (yani 3 terimli aritmetik ilerlemelerin olmadığı bir set) yapısını sağladı [3], Erdős ve Turán'ın ek bir varsayımını çürüten bazı .[4]

1953'te Roth, Fourier analitik yöntemlerini kullanarak uzunluk 3'ün aritmetik ilerlemesini içermesi gerektiğini kanıtlayarak ilk varsayımı kısmen çözdü. Sonunda, 1975'te Szemerédi Szemerédi teoremi kombinatoryal teknikleri kullanarak, orijinal varsayımı tam olarak çözme.

İspat teknikleri

Roth tarafından verilen orijinal kanıt, Fourier analitik yöntemlerini kullandı. Daha sonra kullanılarak başka bir kanıt verildi Szemerédi'nin düzenlilik lemması.

Fourier analizi yoluyla prova taslağı

1953'te Roth kullandı Fourier analizi üst sınırını kanıtlamak . Aşağıda bu kanıtın bir taslağı var.

Tanımla Fourier dönüşümü bir fonksiyonun işlev olmak doyurucu

,

nerede .

İzin Vermek 3 AP içermeyen bir alt kümesi olun . İspat 3 adımda ilerler.

  1. Göster büyük bir Fourier katsayısı kabul ediyor.
  2. Bir alt ilerleme olduğunu çıkarsınız. öyle ki bu alt ilerleme ile sınırlandırıldığında bir yoğunluk artışına sahiptir.
  3. Bir üst sınır elde etmek için 2. Adımı yineleyin .

Aşama 1

Fonksiyonlar için, tanımlamak

Lemma Sayma İzin Vermek tatmin etmek . Tanımlamak . Sonra .

Sayma lemması bize şunu söyler: ve "yakın" ise, ikisi arasındaki 3-terimli aritmetik ilerlemelerin sayısı da "yakın" olmalıdır. İzin Vermek yoğunluğu olmak . Fonksiyonları tanımlayın (yani gösterge işlevi ), ve . Adım 1, daha sonra Sayma Lemmasını uygulayarak çıkarılabilir. ve bize bazılarının olduğunu söyleyen öyle ki

.

Adım 2

Verilen 1. adımdan, ilk önce ayrılmanın mümkün olduğunu gösteriyoruz görece büyük alt ilerlemelere böylelikle karakter her bir alt ilerlemede kabaca sabittir.

Lemma 1: İzin Vermek . Varsayalım ki evrensel bir sabit için . Sonra bölümlemek mümkündür aritmetik ilerlemelere uzunluk ile öyle ki hepsi için .

Daha sonra, alt ilerlemelere bir bölüm elde etmek için Lemma 1'i uyguluyoruz. Daha sonra gerçeğini kullanırız bu alt ilerlemelerden birinin yoğunluk artışına sahip olması gerektiğini göstermek için 1. adımda büyük bir katsayı üretti:

Lemma 2: İzin Vermek 3 AP'siz bir alt kümesi olun , ile ve . Sonra, bir alt ilerleme var öyle ki ve .

Aşama 3

Şimdi 2. adımı yineliyoruz. yoğunluğu olmak sonra inci yineleme. Bizde var ve İlk önce şunu gör çiftler (yani erişim öyle ki ) en çok sonra adımlar. İkiye katlıyoruz tekrar (yani ulaşmak ) en çok sonra adımlar. Dan beri , bu işlem en geç adımlar.

İzin Vermek şu andaki ilerlememizin boyutu yinelemeler. Lemma 2 ile, sürece her zaman her zaman devam edebiliriz ve bu nedenle süreç sona erdiğinde buna sahibiz Ayrıca, bir alt ilerlemeye geçtiğimizde, kümemizin boyutunun bir küp kökü kadar azaldığını unutmayın. Bu nedenle

Bu nedenle yani istediğiniz gibi.

Ne yazık ki, bu teknik, Szemerédi'nin teoremini kanıtlamak için doğrudan daha büyük aritmetik ilerlemelere genellemez. Bu ispatın bir uzantısı, matematikçilerden 1998 yılına kadar yıllarca kaçtı. Timothy Gowers Szemerédi'nin teoremini kanıtlamak için özellikle yukarıdaki ispatı genelleştirmek için yüksek dereceli Fourier Analizi alanını geliştirdi.[5]

Grafik düzenliliği ile prova çizimi

Aşağıda bir ispatın ana hatları verilmiştir. Szemerédi düzenlilik lemma.

İzin Vermek bir grafik ol ve . Biz ararız bir -düzenli çift eğer herkes için ile , birinde var .

Bir bölüm nın-nin bir -düzenli bölüm eğer

.

Sonra Szemerédi düzenlilik lemması şunu söylüyor: bir sabit var öyle ki her grafiğin bir -düzenli bölüm en fazla parçalar.

Ayrıca, arasındaki üçgenleri de ispatlayabiliriz. -düzenli köşe kümeleri diğer birçok üçgenle birlikte gelmelidir. Bu, üçgen sayan lemma olarak bilinir.

Üçgen Sayma Lemması: İzin Vermek bir grafik ol ve köşelerinin alt kümeleri olmak öyle ki hepsi -bazıları için düzenli çiftler . İzin Vermek kenar yoğunluklarını gösterir sırasıyla. Eğer , sonra üçlü sayısı öyle ki üçgen oluşturmak en azından

.

Üçgen sayma lemasını ve Szemerédi düzenlilik lemmasını kullanarak, üçgen çıkarma lemasını, özel bir durum olan grafik kaldırma lemma.[6]

Üçgen Kaldırma Lemması: Hepsi için var öyle ki herhangi bir grafik küçük veya eşit olan köşeler üçgenler en fazla kaldırılarak üçgensiz yapılabilir kenarlar.

Bunun grafiklerle ilgili ilginç bir sonucu var açık her köşesinin olduğu köşeler benzersiz bir üçgende yatıyor. Spesifik olarak, bu grafiklerin tümü, kenarlar.

Bir set al 3 terimli aritmetik ilerlemeler olmadan. Şimdi, üçlü bir grafik oluşturun kimin parçaları hepsi kopyaları . Bir köşe bağlayın bir tepe noktasına Eğer . Benzer şekilde, bağlan ile Eğer . Son olarak bağlanın ile Eğer .

Bu yapı, eğer bir üçgen oluşturduktan sonra öğeler elde ederiz hepsi ait . Bu sayılar, listelenen sırada aritmetik bir ilerleme oluşturur. Varsayım sonra bize bu ilerlemenin önemsiz olması gerektiğini söyler: yukarıda listelenen unsurların hepsi eşittir. Ancak bu koşul şu iddiaya eşdeğerdir: aritmetik bir ilerlemedir . Sonuç olarak, her kenarı tam olarak bir üçgende yer alır. İstenilen sonuç aşağıdadır.

Uzantılar ve Genellemeler

Szemerédi'nin teoremi orijinal varsayımı çözdü ve Roth'un teoremini rastgele uzunluktaki aritmetik ilerlemelere genelleştirdi. O zamandan beri, yeni ve ilginç sonuçlar yaratmak için birden fazla moda genişletildi.

Furstenberg ve Katznelson[7] Kullanılmış ergodik teori çok boyutlu bir versiyonu ve Leibman'ı kanıtlamak ve Bergelson[8] bunu polinom ilerlemelerine de genişletti. En son Yeşil ve Tao kanıtladı Green-Tao Teoremi bu, asal sayıların rastgele uzun aritmetik ilerlemeler içerdiğini söyler. Asal sayılar 0 yoğunluğunun bir alt kümesi olduğundan, belirli sözde rasgele koşullarını karşılayan 0 yoğunluğuna sahip alt kümeler için geçerli olan "göreceli" bir Szemerédi teoremini tanıttılar. Daha sonra Conlon, Tilki ve Zhao[9][10] bu teoremi, gerekli sözde raslantısallık durumunu zayıflatarak güçlendirdi. 2020'de Bloom ve Sisask[11] herhangi bir set olduğunu kanıtladı öyle ki diverges 3 uzunluğunda aritmetik ilerlemeler içermelidir; bu başka birinin önemsiz olmayan ilk durumu varsayım nın-nin Erdős böyle herhangi bir kümenin aslında keyfi olarak uzun aritmetik ilerlemeler içermesi gerektiğini varsaymak.

Sınırları İyileştirme

Roth'un teoremindeki bağı geliştirmek için de çalışmalar yapılmıştır. Roth'un teoreminin orijinal kanıtının sınırı şunu gösterdi:

bazı sabitler için . Yıllar geçtikçe bu sınır Szemerédi tarafından sürekli olarak düşürülmüştür.[12], Heath-Brown[13], Bourgain[14][15], ve Sanders[16][17]. Akımın (Temmuz 2020) en iyi sınırı Bloom ve Sisask'tan kaynaklanıyor[11] c> 0 mutlak sabitinin varlığını gösteren

Diğer tarafta da, üç terimli aritmetik ilerlemelere sahip olmayan en büyük kümenin oluşturulması için çalışmalar yapılmıştır. En iyi yapı, 1946 yılından beri geliştirilmemiştir. Behrend[18] Salem ve Spencer tarafından yapılan ilk inşaatta geliştirildi ve kanıtlandı

bu nedenle iki sınır arasındaki boşluk hala oldukça büyük.

Sonlu Alanlarda Roth Teoremi

Bir varyasyon olarak, sonlu alanlar üzerindeki benzer problemi düşünebiliriz. Sonlu alanı düşünün ve izin ver en büyük alt kümenin boyutu 3 terimli aritmetik ilerleme içermeyen. Bu problem aslında eşdeğerdir şapka seti en büyük alt kümesini isteyen sorun öyle ki bir doğru üzerinde 3 nokta bulunmaz. Kapak takımı problemi, kart oyununun bir genellemesi olarak görülebilir. Ayarlamak.

1982'de Brown ve Buhler[19] bunu ilk gösteren 1995'te Roy Mesuhlam[20] Roth'un teoreminin Fourier-analitik kanıtına benzer bir teknik kullandı. Bu sınır iyileştirildi 2012'de Bateman ve Katz tarafından.[21]

2016 yılında Ernie Croot, Vsevolod Lev, Péter Pál Pach, Jordan Ellenberg ve Dion Gijswijt, bunu kanıtlamak için polinom yöntemine dayalı yeni bir teknik geliştirdi. .[22][23][24]

En iyi bilinen alt sınır yaklaşık olarak , 2004 yılında Eden tarafından verildi.[25]

Popüler farklılıklarla Roth'un Teoremi

Roth'un Teoreminin başka bir genellemesi, pozitif yoğunluk alt kümeleri için sadece 3 terimli aritmetik ilerleme olmadığını, aynı ortak farka sahip birçok 3-AP var olduğunu gösterir.

Roth'un teoremi popüler farklılıklarla: Hepsi için , biraz var öyle ki her biri için ve ile biraz var öyle ki

Eğer rastgele seçilir o zaman orada olmasını beklerdik her değeri için ilerlemeler . Popüler farklılıklar teoremi böylece her biri için pozitif yoğunlukta bazı öyle ki ortak farka sahip 3-AP sayısı beklediğimize yakın.

Bu teorem ilk olarak 2005 yılında Green tarafından kanıtlanmıştır.[26]kim bir sınır verdi nerede kule işlevidir. 2019'da Fox ve Pham, yakın zamanda [27]

İlgili bir ifade de doğrudur hem 3-AP'ler hem de 4-AP'ler için[28]. Ancak, iddianın 5-AP'ler için yanlış olduğu gösterilmiştir.[29]

Referanslar

  1. ^ Roth Klaus (1953). "Belirli tam sayı kümelerinde". Journal of the London Mathematical Society. 28 (1): 104–109. doi:10.1112 / jlms / s1-28.1.104.
  2. ^ van der Waerden, B.L. (1927). "Beweis einer Baudetschen Vermutung". Nieuw. Arch. Wisk. 15: 212–216.
  3. ^ Salem, Raphaël; Spencer, Donald C. (1942). "Aritmetik ilerlemede üç terim içermeyen tamsayı kümelerinde". Amerika Birleşik Devletleri Ulusal Bilimler Akademisi Bildirileri. 28 (12): 561–563. Bibcode:1942PNAS ... 28..561S. doi:10.1073 / pnas.28.12.561. BAY  0007405. PMC  1078539. PMID  16588588.
  4. ^ Erdös, Paul; Turan, Paul (1936). "Bazı Tamsayı Dizilerinde". Journal of the London Mathematical Society. 4 (4): 261–264. doi:10.1112 / jlms / s1-11.4.261. BAY  1574918.
  5. ^ Gowers, W.T. (1998). "Szemerédi'nin dört uzunluğundaki aritmetik ilerlemeler için teoreminin yeni bir kanıtı". Geometrik ve Fonksiyonel Analiz. 8 (3): 529–551. doi:10.1007 / s000390050065.
  6. ^ Fox, Jacob (2011), "Grafik kaldırma lemasının yeni bir kanıtı", Matematik Yıllıkları İkinci Seri, 174 (1): 561–579, arXiv:1006.1300, doi:10.4007 / yıllıklar.2011.174.1.17, BAY  2811609
  7. ^ Furstenberg, Hillel; Katznelson, Yitzhak (1978). "Dönüşümleri değiştirmek için ergodik bir Szemerédi teoremi". Journal d'Analyse Mathématique. 38 (1): 275–291. doi:10.1007 / BF02790016. BAY  0531279.
  8. ^ Bergelson, Vitaly; Leibman, Alexander (1996). "Van der Waerden ve Szemerédi teoremlerinin polinom uzantıları". Amerikan Matematik Derneği Dergisi. 9 (3): 725–753. doi:10.1090 / S0894-0347-96-00194-4. BAY  1325795.
  9. ^ Conlon, David; Fox, Jacob; Zhao, Yufei (2015). "Bağıl Szemerédi teoremi". Geometrik ve Fonksiyonel Analiz. 25 (3): 733–762. arXiv:1305.5440. doi:10.1007 / s00039-015-0324-9. BAY  3361771.
  10. ^ Zhao, Yufei (2014). "Göreli Szemerédi teoreminin aritmetik aktarım kanıtı". Cambridge Philosophical Society'nin Matematiksel İşlemleri. 156 (2): 255–261. arXiv:1307.4959. Bibcode:2014MPCPS.156..255Z. doi:10.1017 / S0305004113000662. BAY  3177868.
  11. ^ a b Thomas F. Bloom, Olof Sisask, Roth'un aritmetik ilerlemeler üzerine teoremindeki logaritmik engeli aşmak, arXiv: 2007.03528, 2020
  12. ^ Szemerédi, Endre (1990). "Aritmetik ilerleme içermeyen tamsayı kümeleri". Açta Math. Macarca. 56 (1–2): 155–158. doi:10.1007 / BF01903717. BAY  1100788.
  13. ^ Heath-Brown, Roger (1987). "Aritmetik ilerleme içermeyen tamsayı kümeleri". Journal of the London Mathematical Society. 35 (3): 385–394. doi:10.1112 / jlms / s2-35.3.385. BAY  0889362.
  14. ^ Bourgain, Jean (1999). "Aritmetik ilerlemede üçlülerde". Geom. Funct. Anal. 9 (5): 968–984. doi:10.1007 / s000390050105. BAY  1726234.
  15. ^ Bourgain, Jean (2008). "Roth'un ilerlemeler üzerine teoremi yeniden gözden geçirildi". Journal d'Analyse Mathématique. 104 (1): 155–192. doi:10.1007 / s11854-008-0020-x. BAY  2403433.
  16. ^ Sanders, Tom (2012). "Diğer belirli tam sayı kümelerinde". Matematik Yıllıkları. 185 (1): 53–82. arXiv:1007.5444. doi:10.1007 / s11854-012-0003-9. BAY  2892617.
  17. ^ Sanders, Tom (2011). "Roth'un ilerlemeler üzerine teoremi üzerine". Matematik Yıllıkları. 174 (1): 619–636. arXiv:1011.0104. doi:10.4007 / yıllıklar.2011.174.1.20. BAY  2811612.
  18. ^ Behrend, F.A. (1946). "Aritmetik ilerlemede üç terim içermeyen tamsayı kümelerinde". Amerika Birleşik Devletleri Ulusal Bilimler Akademisi Bildirileri. 32 (12): 331–332. Bibcode:1946PNAS ... 32..331B. doi:10.1073 / pnas.32.12.331. PMC  1078964. PMID  16578230.
  19. ^ Brown, T. C .; Buhler, J. P. (1982). "Geometrik bir Ramsey teoreminin yoğunluk versiyonu". Kombinatoryal Teori Dergisi, Seri A. 32 (1): 20–34. doi:10.1016/0097-3165(82)90062-0.
  20. ^ Mesuhlam Roy (1995). "3 terimli aritmetik ilerleme içermeyen sonlu değişmeli grupların alt kümelerinde". Kombinatoryal Teori Dergisi, Seri A. 71 (1): 168–172. doi:10.1016/0097-3165(95)90024-1.
  21. ^ Bateman, M .; Katz, N. (2012). "Sınır kümelerinde yeni sınırlar". Amerikan Matematik Derneği Dergisi. 25 (2): 585–613. doi:10.1090 / S0894-0347-2011-00725-X.
  22. ^ Ellenberg, Jordan S .; Gijswijt Dion (2016). "Büyük alt kümelerde üç terimli aritmetik ilerleme olmadan ". Annals of Mathematics, İkinci Seri. 185 (1): 339–343. arXiv:1605.09223. doi:10.4007 / yıllıklar.2017.185.1.8.
  23. ^ Croot, Ernie; Lev, Vsevolod; Pach, Peter (2016). "İlerlemesiz setler katlanarak küçüktür ". arXiv:1605.01506. Alıntı dergisi gerektirir | günlük = (Yardım)
  24. ^ Klarreich, Erica (31 Mayıs 2016). "Basit Set Oyun Kanıtı Matematikçileri Sersemletiyor". Quanta.
  25. ^ Edel, Y. (2004). "Genelleştirilmiş ürün başlıklarının uzantıları". Tasarımlar, Kodlar ve Kriptografi. 31 (1): 5–14. doi:10.1023 / A: 1027365901231.
  26. ^ Yeşil Ben (2005). "Değişmeli gruplarda uygulamalarla birlikte Szemerédi tipi bir düzenlilik lemması". Geometrik ve Fonksiyonel Analiz. 15 (2): 340–376. doi:10.1007 / s00039-005-0509-8. BAY  2153903.
  27. ^ Fox, Jacob; Pham, Huy Tuan (28 Ağustos 2017). "Vektör uzaylarında popüler ilerleme farklılıkları". arXiv:1708.08482. Bibcode:2017arXiv170808482F. Alıntı dergisi gerektirir | günlük = (Yardım)
  28. ^ Green, Ben; Tao, Terrence (2010). "Bir Aritmetik Düzenlilik Lemması, İlişkili Sayma Lemması ve Uygulamalar". Düzensiz Bir Zihin. Bolyai Topluluğu Matematiksel Çalışmalar. 21. Bolyai Topluluğu Matematiksel Çalışmalar. s. 261–334. arXiv:1002.2028. Bibcode:2010arXiv1002.2028G. doi:10.1007/978-3-642-14444-8_7. ISBN  978-3-642-14443-1.
  29. ^ Bergelson, Vitaly; Sunucu, Bernard; Kra, Bryna (2005). "Çoklu yineleme ve sıfır diziler. Imre Ruzsa'dan bir ek ile". Buluşlar Mathematicae. 160 (2): 261–303. doi:10.1007 / s00222-004-0428-6.