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 ${ displaystyle mathbb {F} _ {q}}$ ile sınırlı bir alan olmak ${ displaystyle q}$ elementler. İzin Vermek ${ displaystyle K subseteq mathbb {F} _ {q} ^ {n}}$ bir Kakeya kümesi olun, yani her vektör için ${ displaystyle y in mathbb {F} _ {q} ^ {n}}$var ${ displaystyle x in mathbb {F} _ {q} ^ {n}}$ öyle ki ${ displaystyle K}$ bir çizgi içerir ${ displaystyle {x + ty, t in mathbb {F} _ {q} }}$. Sonra set ${ displaystyle K}$ en azından boyutu var ${ displaystyle c_ {n} q ^ {n}}$nerede ${ displaystyle c_ {n}> 0}$ sadece bağlı olan bir sabittir ${ displaystyle n}$.

Kanıt: Vereceğimiz kanıt bunu gösterecek ${ displaystyle K}$ en azından boyutu var ${ displaystyle c_ {n} q ^ {n-1}}$. Sınırı ${ displaystyle c_ {n} q ^ {n}}$ biraz ek çalışma ile aynı yöntem kullanılarak elde edilebilir.

Bir Kakeya setimiz olduğunu varsayalım ${ displaystyle K}$ ile

${ displaystyle | K | <{q + n-3 n-1'i seç}}$

Formun tek terimli kümesini düşünün ${ displaystyle x_ {1} ^ {d_ {1}} x_ {2} ^ {d_ {2}} noktalar x_ {n} ^ {d_ {n}}}$ derece tam olarak ${ displaystyle q-2}$. Tam olarak var ${ displaystyle {q + n-3 n-1'i seç}}$ bu tür tek terimliler. Böylece sıfır olmayan bir homojen polinom ${ displaystyle P (x_ {1}, x_ {2}, noktalar, x_ {n})}$ derece ${ displaystyle q-2}$ tüm noktalarda kaybolan ${ displaystyle K}$. Bunun nedeni, böyle bir polinom bulmanın, bir sistemi çözmeyi azaltmasıdır. ${ displaystyle | K |}$ katsayılar için doğrusal denklemler.

Şimdi bu özelliği kullanacağız ${ displaystyle K}$ bir Kakeya bunu göstermeye hazır mı? ${ displaystyle P}$ hepsinde yok olmalı ${ displaystyle mathbb {F} _ {q} ^ {n}}$. Açıkça ${ displaystyle P (0,0 noktalar, 0) = 0}$. Sıradaki ${ displaystyle y neq 0}$orada bir ${ displaystyle x}$ öyle ki çizgi ${ displaystyle {x + ty, t in mathbb {F} _ {q} }}$ içinde bulunur ${ displaystyle K}$. Dan beri ${ displaystyle P}$ homojendir, eğer ${ displaystyle P (z) = 0}$ bazı ${ displaystyle z in mathbb {F} _ {q} ^ {n}}$ sonra ${ displaystyle P (cz) = 0}$ herhangi ${ displaystyle c in mathbb {F} _ {q}}$. Özellikle

${ displaystyle P (tx + y) = P (t (x + t ^ {- 1} y)) = 0}$

sıfır olmayan herkes için ${ displaystyle t in mathbb {F} _ {q}}$. Ancak, ${ displaystyle P (tx + y)}$ bir derece polinomudur ${ displaystyle q-2}$ içinde ${ displaystyle t}$ ama en azından var ${ displaystyle q-1}$ sıfır olmayan öğelere karşılık gelen kökler ${ displaystyle mathbb {F} _ {q}}$ bu yüzden aynı şekilde sıfır olmalıdır. Özellikle, fişe takmak ${ displaystyle t = 0}$ sonuca vardık ${ displaystyle P (y) = 0}$.

Biz gösterdik ${ displaystyle P (y) = 0}$ hepsi için ${ displaystyle y in mathbb {F} _ {q} ^ {n}}$ fakat ${ displaystyle P}$ derecesi daha az ${ displaystyle q-1}$ değişkenlerin her birinde bu imkansızdır. Schwartz-Zippel lemma. Aslında sahip olmamız gerektiğini anlıyoruz

${ displaystyle | K | geq {q + n-3 seçin n-1} sim { frac {q ^ {n-1}} {(n-1)!}}}$

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:

• sonlu alan Kakeya varsayımı^[3] Dvir tarafından
• şapka seti Ellenberg ve Gijswijt'in sorunu^[7] benzer problem üzerine geliştirilen orijinal çerçeve ile ${ displaystyle mathbb {Z} _ {4} ^ {n}}$ Hazırlayan: Croot, Lev ve Pach^[8]

• Erdős farklı mesafeler sorunu Guth ve Katz tarafından^[4]
• Guth ve Katz'dan 3D Eklem Problemi^[9]. Argümanları daha sonra Elekes, Kaplan ve Sharir tarafından basitleştirildi.^[10]

Ayrıca bakınız

• Kombinatoryal Nullstellensatz

Referanslar

Dış bağlantılar

• Polinom Yöntemi Üzerine Araştırma Terence Tao tarafından
• Polinom Yöntemi Üzerine Araştırma Larry Guth tarafından