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

गणित में, बहुपद विधि संयोजन समस्याओं के लिए एक बीजगणितीय दृष्टिकोण है जिसमें बहुपदों का उपयोग करके कुछ संयोजी संरचना पर कब्जा करना और उनके बीजगणितीय गुणों के बारे में बहस करना शामिल है। हाल ही में, बहुपद पद्धति ने कई लंबे समय से चली आ रही खुली समस्याओं के लिए उल्लेखनीय सरल समाधानों का विकास किया है। बहुपद पद्धति में बहुपदों का उपयोग करने के लिए विशिष्ट तकनीकों की एक विस्तृत श्रृंखला शामिल है और संयोजन समस्याओं को हल करने के लिए बीजगणितीय ज्यामिति जैसे क्षेत्रों से विचार। जबकि कुछ तकनीकें जो बहुपद पद्धति के ढाँचे का पालन करती हैं, जैसे कि अलोन का प्रतिबंधित योग#कॉम्बिनेटोरियल नलस्टेलनसैट्ज़, 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$.

हमने वह कर दिखाया है $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}$ क्रोट, लेव और पच द्वारा
• गुथ और काट्ज़ द्वारा एर्दो की अलग-अलग दूरी की समस्या* गुथ और काट्ज़ द्वारा 3डी में जोड़ों की समस्या। उनके तर्क को बाद में Elekes, Kaplan और Sharir द्वारा सरल किया गया

यह भी देखें

• प्रतिबंधित समसेट#कॉम्बिनेटरियल नलस्टेलनसैट्ज

बाहरी संबंध

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