कॉम्बिनेटरिक्स में बहुपद विधि

गणित में, बहुपद विधि मे साहचर्य समस्याओं के लिए एक बीजगणितीय दृष्टिकोण है जिसमें बहुपदों का उपयोग करके कुछ मिश्रित संरचना पर प्रग्रहण करना और उनके बीजगणितीय गुणों के बारे में तर्क करना सम्मिलित है। हाल ही में, बहुपद पद्धति ने कई लंबे समय से उपस्थित विवृत समस्या के लिए उल्लेखनीय सरल समाधानों का विकास किया है। बहुपद पद्धति में बहुपदों का उपयोग करने के लिए विशिष्ट तकनीकों की एक विस्तृत श्रृंखला सम्मिलित है, और संयोजन संबंधी समस्याओं को संशोधित करने के लिए बीजगणितीय ज्यामिति जैसे क्षेत्रों के विचार सम्मिलित हैं। जबकि कुछ तकनीकें जो बहुपद पद्धति की रूपरेखा का अनुसरण करती हैं, जैसे कि एलोन का सांयोगिक शून्य समष्टि प्रमेय, 1990 के दशक से जाना जाता है, यह 2010 के आसपास तक नहीं था कि बहुपद पद्धति के लिए एक व्यापक रूपरेखा विकसित की गई थी।

गणितीय अवलोकन

बहुपद पद्धति के कई उपयोग समान उच्च-स्तरीय दृष्टिकोण का अनुसरण करते हैं। अतः दृष्टिकोण इस प्रकार है:

• सदिश समष्टि में कुछ मिश्रित समस्याओ को प्रयुक्त करें।
• एक निश्चित समुच्चय पर शून्य-डिग्री के बहुपद का निर्माण करके समस्या की परिकल्पना को प्रग्रहण करे।
• बहुपद का निर्माण करने के बाद, इसके बीजगणितीय गुणों के बारे में विचार करें ताकि यह निष्कर्ष निकाला जा सके कि मूल विन्यास को वांछित गुणों को पूरा करना चाहिए।

उदाहरण

एक उदाहरण के रूप में, हम बहुपद विधि का उपयोग करते हुए परिमित क्षेत्रों में सदिश समष्टि में काकेया अनुमान के दविर के प्रमाण को रेखांकित करते हैं।

परिमित क्षेत्र काकेया अनुमान: मान लीजिए $\mathbb {F} _{q}$, $q$ तत्वों के साथ एक परिमित क्षेत्र हो। मान लीजिए $K\subseteq \mathbb {F} _{q}^{n}$ एक काकेया समुच्चय है, अर्थात प्रत्येक सदिश के लिए $y\in \mathbb {F} _{q}^{n}$ मे $x\in \mathbb {F} _{q}^{n}$ सम्मिलित है, जैसे कि $K$ मे $\{x+ty,t\in \mathbb {F} _{q}\}$ एक रेखा है। तब समुच्चय $K$ का आकार कम से कम $c_{n}q^{n}$ है, जहाँ $c_{n}>0$ एक स्थिरांक है। जिस पर $n$ केवल निर्भर करता है।

प्रमाण: हम जो प्रमाण देते हैं वह दर्शाता है कि $K$ का आकार कम से कम $c_{n}q^{n-1}$है। और $c_{n}q^{n}$ की सीमा आंशिक अतिरिक्त कार्य के साथ उसी विधि का उपयोग करके प्राप्त किया जा सकता है।

मान लें कि हमारे पास काकेया समुच्चय $K$ है।

$|K|<{q+n-3 \choose n-1}$

घात के $x_{1}^{d_{1}}x_{2}^{d_{2}}\dots x_{n}^{d_{n}}$ रूप के एकपदी के समुच्चय $q-2$ पर विचार करें। वास्तव में ऐसे एकपदी ${q+n-3 \choose n-1}$ हैं। इस प्रकार, एक शून्येतर सजातीय बहुपद $P(x_{1},x_{2},\dots ,x_{n})$ की घात $q-2$ सम्मिलित है, जो $K$ के सभी बिंदुओं पर शून्य हो जाता है। ध्यान दें कि ऐसा इसलिए है क्योंकि इस तरह के बहुपद को खोजने से गुणांकों के लिए $|K|$ रैखिक समीकरणों की एक प्रणाली को हल करना कम हो जाता है।

अब हम उस गुण का उपयोग करेंगे जो $K$ एक काकेया समुच्चय है। यह दिखाने के लिए कि $P$ को सभी $\mathbb {F} _{q}^{n}$ पर शून्य हो जाता है। स्पष्ट रूप से $P(0,0\dots ,0)=0$ उसके बाद $y\neq 0$ के लिए $x$ है जिसकी रेखा $\{x+ty,t\in \mathbb {F} _{q}\}$ में $K$ निहित है। चूँकि $P$ सजातीय है, यदि $P(z)=0$ कुछ के लिए $z\in \mathbb {F} _{q}^{n}$है। तब $P(cz)=0$ किसी $c\in \mathbb {F} _{q}$ के लिए समुच्चय समान है। विशेष रूप से

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

सभी अशून्य $t\in \mathbb {F} _{q}$ के लिए है। हालाँकि $P(tx+y)$ घात का बहुपद $q-2$ में $t$ है। लेकिन यह कम से कम $q-1$ के अशून्य तत्वों $\mathbb {F} _{q}$ के अनुरूप जुड़े है, तो यह समान रूप से शून्य होना चाहिए। विशेष रूप से $t=0$ जोड़ने पर हम $P(y)=0$ प्राप्त करते हैं I

हमने दिखाया है कि सभी $P(y)=0$ के लिए $y\in \mathbb {F} _{q}^{n}$ प्राप्त होता है। लेकिन प्रत्येक चर में $P$ की घात $q-1$ से कम है। इसलिए श्वार्ट्ज-ज़िप्पल लेम्मा द्वारा यह असंभव है। हम यह निष्कर्ष निकालते हैं कि हमारे पास वास्तव में होना चाहिए

$|K|\geq {q+n-3 \choose n-1}\sim {\frac {q^{n-1}}{(n-1)!}}$

बहुपद विभाजन

बहुपद पद्धति की एक भिन्नता जिसे प्रायः बहुपद विभाजन कहा जाता है, जिसको गुथ और काट्ज़ ने एर्दो की अलग-अलग दूरी की समस्या के समाधान में प्रस्तुत किया था। बहुपद विभाजन में अंतर्निहित समष्टि को क्षेत्रों में विभाजित करने और विभाजन की ज्यामितीय संरचना के बारे में विचार करने के लिए बहुपदों का उपयोग करना सम्मिलित है। ये तर्क विभिन्न बीजगणितीय वक्रों के बीच घटनाओं की संख्या को सीमित करने वाले बीजगणितीय ज्यामिति के परिणामों पर निर्भर करते हैं। बहुपद विभाजन की तकनीक का उपयोग हैम सैंडविच प्रमेय सामान्यीकरण के माध्यम से ज़ेमेरीडी-ट्रॉटर प्रमेय का एक नया प्रमाण देने के लिए किया गया है और घटना ज्यामिति में विभिन्न समस्याओं पर प्रयुक्त किया गया है।

अनुप्रयोग

दीर्घकालीन विवृत समस्याओं के कुछ उदाहरण जिन्हें बहुपद विधि का उपयोग करके संशोधित किया गया है:

• डीविर द्वारा परिमित क्षेत्र काकेया अनुमान करना।
• क्रोट, लेव और पाच द्वारा $\mathbb {Z} _{4}^{n}$ पर समान समस्या पर विकसित मूल रूपरेखा के साथ एलेनबर्ग और गिजस्विज्ट द्वारा शीर्ष समुच्चय समस्या दी गई।
• गुथ और काट्ज़ द्वारा एर्दो की अलग-अलग दूरी की समस्या दी गई।
• गुथ और काट्ज़ द्वारा 3D में जोड़ों की समस्या उनके तर्क को बाद में एलेकेस, कपलन और शारीर द्वारा सरल किया गया।

यह भी देखें

• सांयोगिक शून्य समष्टि प्रमेय

बाहरी संबंध

• Survey on the Polynomial Method by Terence Tao
• Survey on the Polynomial Method by Larry Guth