Kombinatoriklerde polinom yöntemi - Polynomial method in combinatorics - Wikipedia

Matematikte, polinom yöntemi cebirsel bir yaklaşımdır kombinatorik polinomları kullanarak bazı kombinatoryal yapıları yakalamayı ve cebirsel özellikleri hakkında tartışmaya devam etmeyi içeren problemler. Son zamanlarda, polinom yöntemi, uzun süredir devam eden birkaç açık soruna dikkat çekici ölçüde basit çözümlerin geliştirilmesine yol açmıştır.[1]. Polinom yöntemi, kombinatorik problemleri çözmek için cebirsel geometri gibi alanlardan gelen polinomları ve fikirleri kullanmak için çok çeşitli spesifik teknikleri kapsar. Alon's gibi polinom yönteminin çerçevesini takip eden birkaç teknik Kombinatoryal Nullstellensatz[2], 1990'lardan beri biliniyor, polinom yöntemi için daha geniş bir çerçevenin geliştirilmesi 2010'lara kadar değildi.

Matematiksel genel bakış

Polinom yönteminin birçok kullanımı aynı yüksek seviyeli yaklaşımı takip eder. Yaklaşım aşağıdaki gibidir:

  • Bazı kombinatoryal problemleri bir vektör uzayına gömün.
  • Belirli bir kümede sıfır olan düşük dereceli bir polinom oluşturarak sorunun hipotezlerini yakalayın
  • Polinomu oluşturduktan sonra, orijinal konfigürasyonun istenen özellikleri karşılaması gerektiğine karar vermek için cebirsel özelliklerini tartışın.

Misal

Örnek olarak, Dvir'in Sonlu Alan Kakeya Varsayımı polinom yöntemini kullanarak[3].

Sonlu Alan Kakeya Varsayımı: İzin Vermek ile sınırlı bir alan olmak elementler. İzin Vermek bir Kakeya kümesi olun, yani her vektör için var öyle ki bir çizgi içerir . Sonra set en azından boyutu var nerede sadece bağlı olan bir sabittir .

Kanıt: Vereceğimiz kanıt bunu gösterecek en azından boyutu var . Sınırı biraz ek çalışma ile aynı yöntem kullanılarak elde edilebilir.

Bir Kakeya setimiz olduğunu varsayalım ile

Formun tek terimli kümesini düşünün derece tam olarak . Tam olarak var bu tür tek terimliler. Böylece sıfır olmayan bir homojen polinom derece tüm noktalarda kaybolan . Bunun nedeni, böyle bir polinom bulmanın, bir sistemi çözmeyi azaltmasıdır. katsayılar için doğrusal denklemler.

Şimdi bu özelliği kullanacağız bir Kakeya bunu göstermeye hazır mı? hepsinde yok olmalı . Açıkça . Sıradaki orada bir öyle ki çizgi içinde bulunur . Dan beri homojendir, eğer bazı sonra herhangi . Özellikle

sıfır olmayan herkes için . Ancak, bir derece polinomudur içinde ama en azından var sıfır olmayan öğelere karşılık gelen kökler bu yüzden aynı şekilde sıfır olmalıdır. Özellikle, fişe takmak sonuca vardık .

Biz gösterdik hepsi için fakat derecesi daha az değişkenlerin her birinde bu imkansızdır. Schwartz-Zippel lemma. Aslında sahip olmamız gerektiğini anlıyoruz

Polinom bölümleme

Genellikle polinom bölünme olarak adlandırılan polinom yönteminin bir varyasyonu, Guth ve Katz tarafından Erdős farklı mesafeler sorunu[4]. Polinom bölümleme, altta yatan alanı bölgelere ayırmak için polinomların kullanılmasını ve bölümün geometrik yapısı hakkında tartışmayı içerir. Bu argümanlar, çeşitli cebirsel eğriler arasındaki olayların sayısını sınırlayan cebirsel geometrinin sonuçlarına dayanır. Polinom bölümleme tekniği, yeni bir kanıt vermek için kullanılmıştır. Szemerédi – Trotter teoremi aracılığıyla polinom jambon sandviç teoremi ve insidans geometrisindeki çeşitli problemlere uygulanmıştır[5][6].

Başvurular

Polinom yöntemi kullanılarak çözülen uzun süredir devam eden açık problemlere birkaç örnek şunlardır:

Ayrıca bakınız

Referanslar

  1. ^ Guth, L. (2016). Kombinatoriklerde Polinom Yöntemleri. Üniversite Ders Serisi. Amerikan Matematik Derneği. ISBN  978-1-4704-2890-7. Alındı 2019-12-11.
  2. ^ Alon, Noga (1999). "Kombinatoryal Nullstellensatz". Kombinatorik, Olasılık ve Hesaplama. 8 (1–2): 7–29. doi:10.1017 / S0963548398003411. ISSN  0963-5483.
  3. ^ a b Dvir, Zeev (2008). "Sonlu alanlarda Kakeya setlerinin boyutu hakkında". Amerikan Matematik Derneği Dergisi. 22 (4): 1093–1097. doi:10.1090 / S0894-0347-08-00607-3. ISSN  0894-0347.
  4. ^ a b Guth, Larry; Katz, Ağlar (2015). "Erdőnin uçaktaki farklı mesafeler sorunu üzerine". Matematik Yıllıkları: 155–190. doi:10.4007 / yıllıklar.2015.181.1.2. hdl:1721.1/92873. ISSN  0003-486X.
  5. ^ Kaplan, Haim; Matoušek, Jiří; Sharir Micha (2012). "Guth-Katz Polinom Bölme Tekniği Yoluyla Ayrık Geometride Klasik Teoremlerin Basit İspatları". Ayrık ve Hesaplamalı Geometri. 48 (3): 499–517. arXiv:1102.5391. doi:10.1007 / s00454-012-9443-3. ISSN  0179-5376.
  6. ^ Dvir, Zeev (2012). "İnsidans Teoremleri ve Uygulamaları". Teorik Bilgisayar Biliminde Temeller ve Eğilimler. 6 (4): 257–393. arXiv:1208.5073. Bibcode:2012arXiv1208.5073D. doi:10.1561/0400000056. ISSN  1551-305X.
  7. ^ Ellenberg, Ürdün; Gijswijt Dion (2017). "Büyük alt kümelerde üç terimli aritmetik ilerleme olmadan ". Matematik Yıllıkları. 185 (1): 339–343. doi:10.4007 / yıllıklar.2017.185.1.8. ISSN  0003-486X.
  8. ^ Croot, Ernie; Lev, Vsevolod; Pach, Péter (2017). "İlerlemesiz setler katlanarak küçük " (PDF). Matematik Yıllıkları. 185 (1): 331–337. doi:10.4007 / yıllıklar.2017.185.1.7. ISSN  0003-486X.
  9. ^ Guth, Larry; Katz, Nets Hawk (2010). "Kakeya probleminin ayrık analoglarında cebirsel yöntemler". Matematikteki Gelişmeler. 225 (5): 2828–2839. arXiv:0812.1043. doi:10.1016 / j.aim.2010.05.015. ISSN  0001-8708.
  10. ^ Elekes, György; Kaplan, Haim; Sharir Micha (2011). "Üç boyuttaki çizgiler, eklemler ve olaylarda". Kombinatoryal Teori Dergisi, Seri A. 118 (3): 962–977. doi:10.1016 / j.jcta.2010.11.008. ISSN  0097-3165.

Dış bağlantılar