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

From Vigyanwiki
(Created page with "गणित में, बहुपद विधि संयोजन समस्याओं के लिए एक बीजगणितीय दृष्टिको...")
 
No edit summary
Line 1: Line 1:
गणित में, बहुपद विधि संयोजन समस्याओं के लिए एक बीजगणितीय दृष्टिकोण है जिसमें बहुपदों का उपयोग करके कुछ संयोजी संरचना पर कब्जा करना और उनके बीजगणितीय गुणों के बारे में बहस करना शामिल है। हाल ही में, बहुपद पद्धति ने कई लंबे समय से चली आ रही खुली समस्याओं के लिए उल्लेखनीय सरल समाधानों का विकास किया है।<ref name="Guth 2016 p. ">{{cite book | last=Guth | first=L. | title=कॉम्बिनेटरिक्स में बहुपद तरीके| publisher=American Mathematical Society | series=University Lecture Series | year=2016 | isbn=978-1-4704-2890-7 | url=https://books.google.com/books?id=t9ZTDAAAQBAJ | access-date=2019-12-11 | page=}}</ref> बहुपद पद्धति में बहुपदों का उपयोग करने के लिए विशिष्ट तकनीकों की एक विस्तृत श्रृंखला शामिल है और संयोजन समस्याओं को हल करने के लिए बीजगणितीय ज्यामिति जैसे क्षेत्रों से विचार। जबकि कुछ तकनीकें जो बहुपद पद्धति के ढाँचे का पालन करती हैं, जैसे कि अलोन का प्रतिबंधित योग#कॉम्बिनेटोरियल नलस्टेलनसैट्ज़,<ref name="Alon1999">{{cite journal|last1=Alon|first1=Noga|title=संयोजन शून्य प्रमेय|journal=Combinatorics, Probability and Computing|volume=8|issue=1–2|year=1999|pages=7–29|issn=0963-5483|doi=10.1017/S0963548398003411}}</ref> 1990 के दशक से जाना जाता है, यह 2010 के आसपास तक नहीं था कि बहुपद पद्धति के लिए एक व्यापक ढांचा विकसित किया गया था।
गणित में, बहुपद विधि साहचर्य समस्याओं के लिए एक बीजगणितीय दृष्टिकोण है जिसमें बहुपदों का उपयोग करके कुछ मिश्रित संरचना पर प्रग्रहण करना और उनके बीजगणितीय गुणों के बारे में तर्क  करना सम्मिलित है। हाल ही में, बहुपद पद्धति ने कई लंबे समय से उपस्थित विवृत समस्या के लिए उल्लेखनीय सरल समाधानों का विकास किया है।<ref name="Guth 2016 p. ">{{cite book | last=Guth | first=L. | title=कॉम्बिनेटरिक्स में बहुपद तरीके| publisher=American Mathematical Society | series=University Lecture Series | year=2016 | isbn=978-1-4704-2890-7 | url=https://books.google.com/books?id=t9ZTDAAAQBAJ | access-date=2019-12-11 | page=}}</ref> बहुपद पद्धति में बहुपदों का उपयोग करने के लिए विशिष्ट तकनीकों की एक विस्तृत श्रृंखला सम्मिलित है और संयोजन संबंधी समस्याओं को हल करने के लिए बीजगणितीय ज्यामिति जैसे क्षेत्रों के विचार सम्मिलित हैं। जबकि कुछ तकनीकें जो बहुपद पद्धति की रूपरेखा  का अनुसरण करती हैं, जैसे कि एलोन का सांयोगिक शून्य समष्टि प्रमेय,<ref name="Alon1999">{{cite journal|last1=Alon|first1=Noga|title=संयोजन शून्य प्रमेय|journal=Combinatorics, Probability and Computing|volume=8|issue=1–2|year=1999|pages=7–29|issn=0963-5483|doi=10.1017/S0963548398003411}}</ref> 1990 के दशक से जाना जाता है, यह 2010 के आसपास तक नहीं था कि बहुपद पद्धति के लिए एक व्यापक रूपरेखा विकसित की गई थी।


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


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


=== उदाहरण ===
=== उदाहरण ===
एक उदाहरण के रूप में, हम बहुपद विधि का उपयोग करते हुए परिमित क्षेत्रों में वेक्टर रिक्त स्थान में काकेया सेट#काकेया सेट के दविर के प्रमाण को रेखांकित करते हैं।<ref name="Dvir2008">{{cite journal|last1=Dvir|first1=Zeev|year=2008|title=कैकेय के आकार पर परिमित क्षेत्रों में सेट होता है|journal=Journal of the American Mathematical Society|volume=22|issue=4|pages=1093–1097|doi=10.1090/S0894-0347-08-00607-3|issn=0894-0347|doi-access=free}}</ref>
एक उदाहरण के रूप में, हम बहुपद विधि का उपयोग करते हुए परिमित क्षेत्रों में सदिश  समष्टि में काकेया अनुमान के दविर के प्रमाण को रेखांकित करते हैं।<ref name="Dvir2008">{{cite journal|last1=Dvir|first1=Zeev|year=2008|title=कैकेय के आकार पर परिमित क्षेत्रों में सेट होता है|journal=Journal of the American Mathematical Society|volume=22|issue=4|pages=1093–1097|doi=10.1090/S0894-0347-08-00607-3|issn=0894-0347|doi-access=free}}</ref>
परिमित क्षेत्र काकेया अनुमान: मान लीजिए <math>\mathbb{F}_q</math> के साथ एक परिमित क्षेत्र हो <math>q</math> तत्व। होने देना <math>K \subseteq \mathbb{F}_q^n</math> एक काकेया सेट हो, यानी प्रत्येक वेक्टर के लिए <math>y \in \mathbb{F}_q^n</math>वहां मौजूद <math>x \in \mathbb{F}_q^n</math> ऐसा है कि <math>K</math> एक रेखा है <math>\{x + ty, t \in \mathbb{F}_q \}</math>. फिर सेट <math>K</math> आकार कम से कम है <math>c_nq^n</math>कहाँ <math>c_n > 0</math> एक स्थिरांक है जिस पर केवल निर्भर करता है <math>n</math>.


सबूत: हम जो सबूत देते हैं वह दिखाएगा <math>K</math> आकार कम से कम है <math>c_nq^{n-1}</math>. की सीमा <math>c_nq^n</math> थोड़े अतिरिक्त काम के साथ उसी विधि का उपयोग करके प्राप्त किया जा सकता है।
'''परिमित क्षेत्र काकेया अनुमान''': मान लीजिए <math>\mathbb{F}_q</math>,  <math>q</math> तत्वों के साथ एक परिमित क्षेत्र हो। मान लीजिए  <math>K \subseteq \mathbb{F}_q^n</math> एक काकेया समुच्चय है, अर्थात प्रत्येक सदिश के लिए <math>y \in \mathbb{F}_q^n</math> मे  <math>x \in \mathbb{F}_q^n</math> सम्मिलित है, जैसे कि <math>K</math> मे  <math>\{x + ty, t \in \mathbb{F}_q \}</math> एक रेखा है।  फिर समुच्चय  <math>K</math> का आकार कम से कम <math>c_nq^n</math> है। जहाँ <math>c_n > 0</math> एक स्थिरांक है जिस पर  <math>n</math> केवल निर्भर करता है।  


मान लें कि हमारे पास काकेया सेट है <math>K</math> साथ
'''प्रमाण''': हम जो प्रमाण देते हैं वह दिखाएगा <math>K</math> का आकार कम से कम  <math>c_nq^{n-1}</math>है।  और  <math>c_nq^n</math> की सीमा आंशिक अतिरिक्त काम के साथ उसी विधि का उपयोग करके प्राप्त किया जा सकता है।
 
मान लें कि हमारे पास काकेया समुच्चय <math>K</math> है।


<math>|K| < {q+n-3\choose n-1}</math>
<math>|K| < {q+n-3\choose n-1}</math>
फॉर्म के मोनोमियल्स के सेट पर विचार करें <math>x_1^{d_1}x_2^{d_2} \dots x_n^{d_n}</math> डिग्री का बिल्कुल <math>q-2</math>. बिल्कुल हैं <math>{q+n-3\choose n-1}</math> ऐसे मोनोमियल। इस प्रकार, एक शून्येतर [[सजातीय बहुपद]] का अस्तित्व है <math>P(x_1,x_2, \dots , x_n)</math> डिग्री का <math>q-2</math> जो सभी बिंदुओं पर गायब हो जाता है <math>K</math>. इस पर ध्यान दें क्योंकि इस तरह के बहुपद को खोजने से एक प्रणाली को हल करने में कमी आती है <math>|K|</math> गुणांकों के लिए रैखिक समीकरण।


अब हम उस संपत्ति का उपयोग करेंगे <math>K</math> यह दिखाने के लिए एक काकेया सेट है <math>P</math> सभी पर गायब हो जाना चाहिए <math>\mathbb{F}_q^n</math>. स्पष्ट रूप से <math>P(0,0 \dots , 0) = 0</math>. अगला, के लिए <math>y \neq 0</math>, वहाँ है एक <math>x</math> ऐसा है कि लाइन <math>\{x + ty, t \in \mathbb{F}_q \}</math> में निहित है <math>K</math>. तब से <math>P</math> सजातीय है, अगर <math>P(z) = 0</math> कुछ के लिए <math>z \in \mathbb{F}_q^n</math> तब <math>P(cz) = 0</math> किसी के लिए <math>c \in \mathbb{F}_q</math>. विशेष रूप से
'''EDIT''' फॉर्म के मोनोमियल्स के सेट पर विचार करें <math>x_1^{d_1}x_2^{d_2} \dots x_n^{d_n}</math> डिग्री का बिल्कुल <math>q-2</math>. बिल्कुल हैं <math>{q+n-3\choose n-1}</math> ऐसे मोनोमियल। इस प्रकार, एक शून्येतर [[सजातीय बहुपद]] का अस्तित्व है <math>P(x_1,x_2, \dots , x_n)</math> डिग्री का <math>q-2</math> जो सभी बिंदुओं पर गायब हो जाता है <math>K</math>. इस पर ध्यान दें क्योंकि इस तरह के बहुपद को खोजने से एक प्रणाली को हल करने में कमी आती है <math>|K|</math> गुणांकों के लिए रैखिक समीकरण।
 
अब हम उस संपत्ति का उपयोग करेंगे <math>K</math> यह दिखाने के लिए एक काकेया सेट है <math>P</math> सभी पर गायब हो जाना चाहिए <math>\mathbb{F}_q^n</math>. स्पष्ट रूप से <math>P(0,0 \dots , 0) = 0</math>. अगला, के लिए <math>y \neq 0</math>, वहाँ है एक <math>x</math> जैसे कि लाइन <math>\{x + ty, t \in \mathbb{F}_q \}</math> में निहित है <math>K</math>. तब से <math>P</math> सजातीय है, अगर <math>P(z) = 0</math> कुछ के लिए <math>z \in \mathbb{F}_q^n</math> तब <math>P(cz) = 0</math> किसी के लिए <math>c \in \mathbb{F}_q</math>. विशेष रूप से


<math>P(tx + y) = P(t(x+t^{-1}y)) = 0</math>
<math>P(tx + y) = P(t(x+t^{-1}y)) = 0</math>
Line 27: Line 29:


<math>|K| \ge {q+n-3\choose n-1} \sim \frac{q^{n-1}}{(n-1)!}</math>
<math>|K| \ge {q+n-3\choose n-1} \sim \frac{q^{n-1}}{(n-1)!}</math>




=== बहुपद विभाजन ===
=== बहुपद विभाजन ===
बहुपद पद्धति की एक भिन्नता, जिसे अक्सर बहुपद विभाजन कहा जाता है, को गुथ और काट्ज़ ने एर्दो की अलग-अलग दूरी की समस्या के समाधान में पेश किया था।<ref name="GuthKatz2015">{{cite journal|last1=Guth|first1=Larry|last2=Katz|first2=Nets|year=2015|title=On the Erdős distinct distances problem in the plane|journal=Annals of Mathematics|pages=155–190|doi=10.4007/annals.2015.181.1.2|issn=0003-486X|hdl=1721.1/92873|hdl-access=free}}</ref> बहुपद विभाजन में अंतर्निहित स्थान को क्षेत्रों में विभाजित करने और विभाजन की ज्यामितीय संरचना के बारे में बहस करने के लिए बहुपदों का उपयोग करना शामिल है। ये तर्क विभिन्न बीजगणितीय वक्रों के बीच घटनाओं की संख्या को सीमित करने वाले बीजगणितीय ज्यामिति के परिणामों पर निर्भर करते हैं। बहुपद विभाजन की तकनीक का उपयोग हैम सैंडविच प्रमेय#सामान्यीकरण के माध्यम से ज़ेमेरीडी-ट्रॉटर प्रमेय का एक नया प्रमाण देने के लिए किया गया है और घटना ज्यामिति में विभिन्न समस्याओं पर लागू किया गया है।<ref name="KaplanMatoušek2012">{{cite journal|last1=Kaplan|first1=Haim|last2=Matoušek|first2=Jiří|authorlink2=Jiří Matoušek (mathematician)|last3=Sharir|first3=Micha|authorlink3= Micha  Sharir|title=गुथ-काट्ज़ बहुपद विभाजन तकनीक के माध्यम से असतत ज्यामिति में शास्त्रीय प्रमेय के सरल प्रमाण|journal=[[Discrete & Computational Geometry]]|volume=48|issue=3|year=2012|pages=499–517|issn=0179-5376|doi=10.1007/s00454-012-9443-3|arxiv=1102.5391}}</ref><ref name="Dvir2012">{{cite journal|last1=Dvir|first1=Zeev|year=2012|title=घटना प्रमेय और उनके अनुप्रयोग|journal=Foundations and Trends in Theoretical Computer Science|volume=6|issue=4|pages=257–393|doi=10.1561/0400000056|issn=1551-305X|bibcode=2012arXiv1208.5073D|arxiv=1208.5073}}</ref>
बहुपद पद्धति की एक भिन्नता, जिसे अक्सर बहुपद विभाजन कहा जाता है, जिसको गुथ और काट्ज़ ने एर्दो की अलग-अलग दूरी की समस्या के समाधान में प्रस्तुत किया था।<ref name="GuthKatz2015">{{cite journal|last1=Guth|first1=Larry|last2=Katz|first2=Nets|year=2015|title=On the Erdős distinct distances problem in the plane|journal=Annals of Mathematics|pages=155–190|doi=10.4007/annals.2015.181.1.2|issn=0003-486X|hdl=1721.1/92873|hdl-access=free}}</ref> बहुपद विभाजन में अंतर्निहित समष्टि को क्षेत्रों में विभाजित करने और विभाजन की ज्यामितीय संरचना के बारे में विचार करने के लिए बहुपदों का उपयोग करना सम्मिलित है। ये तर्क विभिन्न बीजगणितीय वक्रों के बीच घटनाओं की संख्या को सीमित करने वाले बीजगणितीय ज्यामिति के परिणामों पर निर्भर करते हैं। बहुपद विभाजन की तकनीक का उपयोग हैम सैंडविच प्रमेय सामान्यीकरण के माध्यम से ज़ेमेरीडी-ट्रॉटर प्रमेय का एक नया प्रमाण देने के लिए किया गया है और घटना ज्यामिति में विभिन्न समस्याओं पर प्रयुक्त किया गया है।<ref name="KaplanMatoušek2012">{{cite journal|last1=Kaplan|first1=Haim|last2=Matoušek|first2=Jiří|authorlink2=Jiří Matoušek (mathematician)|last3=Sharir|first3=Micha|authorlink3= Micha  Sharir|title=गुथ-काट्ज़ बहुपद विभाजन तकनीक के माध्यम से असतत ज्यामिति में शास्त्रीय प्रमेय के सरल प्रमाण|journal=[[Discrete & Computational Geometry]]|volume=48|issue=3|year=2012|pages=499–517|issn=0179-5376|doi=10.1007/s00454-012-9443-3|arxiv=1102.5391}}</ref><ref name="Dvir2012">{{cite journal|last1=Dvir|first1=Zeev|year=2012|title=घटना प्रमेय और उनके अनुप्रयोग|journal=Foundations and Trends in Theoretical Computer Science|volume=6|issue=4|pages=257–393|doi=10.1561/0400000056|issn=1551-305X|bibcode=2012arXiv1208.5073D|arxiv=1208.5073}}</ref>




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


* काकेया सेट#काकेया परिमित क्षेत्रों में सदिश स्थानों में सेट होता है<ref name="Dvir2008" />डविर द्वारा
* डीविर द्वारा परिमित क्षेत्र काकेया अनुमान<ref name="Dvir2008" />
*एलेनबर्ग और गिजस्विज द्वारा [[ टोपी सेट ]] समस्या<ref name="EllenbergGijswijt20172">{{cite journal|last1=Ellenberg|first1=Jordan|last2=Gijswijt|first2=Dion|year=2017|title=On large subsets of <math>\mathbb{F}_q^n </math> with no three-term arithmetic progression|journal=Annals of Mathematics|volume=185|issue=1|pages=339–343|doi=10.4007/annals.2017.185.1.8|issn=0003-486X|url=http://resolver.tudelft.nl/uuid:24934b91-cb43-49ef-9423-731dd1fb9306}}</ref> समान समस्या पर विकसित मूल ढांचे के साथ <math>\mathbb{Z}_4^n</math> क्रोट, लेव और पच द्वारा<ref name="CrootLev2017">{{cite journal|last1=Croot|first1=Ernie|last2=Lev|first2=Vsevolod|last3=Pach|first3=Péter|title=Progression-free sets in <math>\mathbb{Z}_4^n</math> are exponentially small|journal=Annals of Mathematics|volume=185|issue=1|year=2017|pages=331–337|issn=0003-486X|doi=10.4007/annals.2017.185.1.7|url=http://real.mtak.hu/62116/1/prog_free.pdf}}</ref>
*क्रोट, लेव और पाच द्वारा <math>\mathbb{Z}_4^n</math> पर समान समस्या पर विकसित मूल रूपरेखा के साथ एलेनबर्ग और गिजस्विज्ट <ref name="EllenbergGijswijt20172">{{cite journal|last1=Ellenberg|first1=Jordan|last2=Gijswijt|first2=Dion|year=2017|title=On large subsets of <math>\mathbb{F}_q^n </math> with no three-term arithmetic progression|journal=Annals of Mathematics|volume=185|issue=1|pages=339–343|doi=10.4007/annals.2017.185.1.8|issn=0003-486X|url=http://resolver.tudelft.nl/uuid:24934b91-cb43-49ef-9423-731dd1fb9306}}</ref> द्वारा शीर्ष  समुच्चय समस्या दी गई।<ref name="CrootLev2017">{{cite journal|last1=Croot|first1=Ernie|last2=Lev|first2=Vsevolod|last3=Pach|first3=Péter|title=Progression-free sets in <math>\mathbb{Z}_4^n</math> are exponentially small|journal=Annals of Mathematics|volume=185|issue=1|year=2017|pages=331–337|issn=0003-486X|doi=10.4007/annals.2017.185.1.7|url=http://real.mtak.hu/62116/1/prog_free.pdf}}</ref>
* गुथ और काट्ज़ द्वारा एर्दो की अलग-अलग दूरी की समस्या<ref name="GuthKatz2015"/>* गुथ और काट्ज़ द्वारा 3डी में जोड़ों की समस्या।<ref name="GuthKatz2010">{{cite journal|last1=Guth|first1=Larry|authorlink1=Larry Guth|last2=Katz|first2=Nets Hawk|title=कैकेय समस्या के असतत अनुरूपों में बीजगणितीय तरीके|journal=[[Advances in Mathematics]]|volume=225|issue=5|year=2010|pages=2828–2839|issn=0001-8708|doi=10.1016/j.aim.2010.05.015|doi-access=free|arxiv=0812.1043}}</ref> उनके तर्क को बाद में Elekes, Kaplan और Sharir द्वारा सरल किया गया<ref name="ElekesKaplan2011">{{cite journal|last1=Elekes|first1=György|last2=Kaplan|first2=Haim|last3=Sharir|first3=Micha|authorlink3=Micha Sharir|year=2011|title=तीन आयामों में लाइनों, जोड़ों और घटनाओं पर|journal=[[Journal of Combinatorial Theory]] | series=Series A|volume=118|issue=3|pages=962–977|doi=10.1016/j.jcta.2010.11.008|doi-access=free|issn=0097-3165}}</ref>
* गुथ और काट्ज़ द्वारा एर्दो की अलग-अलग दूरी की समस्या दी गई।<ref name="GuthKatz2015"/>
*गुथ और काट्ज़ द्वारा 3D में जोड़ों की समस्या<ref name="GuthKatz2010">{{cite journal|last1=Guth|first1=Larry|authorlink1=Larry Guth|last2=Katz|first2=Nets Hawk|title=कैकेय समस्या के असतत अनुरूपों में बीजगणितीय तरीके|journal=[[Advances in Mathematics]]|volume=225|issue=5|year=2010|pages=2828–2839|issn=0001-8708|doi=10.1016/j.aim.2010.05.015|doi-access=free|arxiv=0812.1043}}</ref> उनके तर्क को बाद में एलेकेस, कपलन और शारीर  द्वारा सरल किया गया।<ref name="ElekesKaplan2011">{{cite journal|last1=Elekes|first1=György|last2=Kaplan|first2=Haim|last3=Sharir|first3=Micha|authorlink3=Micha Sharir|year=2011|title=तीन आयामों में लाइनों, जोड़ों और घटनाओं पर|journal=[[Journal of Combinatorial Theory]] | series=Series A|volume=118|issue=3|pages=962–977|doi=10.1016/j.jcta.2010.11.008|doi-access=free|issn=0097-3165}}</ref>




== यह भी देखें ==
== यह भी देखें ==
*प्रतिबंधित समसेट#कॉम्बिनेटरियल नलस्टेलनसैट्ज
*सांयोगिक शून्य समष्टि प्रमेय


== संदर्भ ==
== संदर्भ ==

Revision as of 20:46, 9 May 2023

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

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

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

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

उदाहरण

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

परिमित क्षेत्र काकेया अनुमान: मान लीजिए , तत्वों के साथ एक परिमित क्षेत्र हो। मान लीजिए एक काकेया समुच्चय है, अर्थात प्रत्येक सदिश के लिए मे सम्मिलित है, जैसे कि मे एक रेखा है। फिर समुच्चय का आकार कम से कम है। जहाँ एक स्थिरांक है जिस पर केवल निर्भर करता है।

प्रमाण: हम जो प्रमाण देते हैं वह दिखाएगा का आकार कम से कम है। और की सीमा आंशिक अतिरिक्त काम के साथ उसी विधि का उपयोग करके प्राप्त किया जा सकता है।

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

EDIT फॉर्म के मोनोमियल्स के सेट पर विचार करें डिग्री का बिल्कुल . बिल्कुल हैं ऐसे मोनोमियल। इस प्रकार, एक शून्येतर सजातीय बहुपद का अस्तित्व है डिग्री का जो सभी बिंदुओं पर गायब हो जाता है . इस पर ध्यान दें क्योंकि इस तरह के बहुपद को खोजने से एक प्रणाली को हल करने में कमी आती है गुणांकों के लिए रैखिक समीकरण।

अब हम उस संपत्ति का उपयोग करेंगे यह दिखाने के लिए एक काकेया सेट है सभी पर गायब हो जाना चाहिए . स्पष्ट रूप से . अगला, के लिए , वहाँ है एक जैसे कि लाइन में निहित है . तब से सजातीय है, अगर कुछ के लिए तब किसी के लिए . विशेष रूप से

सभी अशून्य के लिए . हालाँकि, डिग्री का बहुपद है में लेकिन यह कम से कम है के अशून्य तत्वों के अनुरूप जड़ें तो यह समान रूप से शून्य होना चाहिए। विशेष रूप से, प्लग इन करना हम निष्कर्ष निकालते हैं .

हमने वह कर दिखाया है सभी के लिए लेकिन से कम डिग्री है प्रत्येक चर में इसलिए श्वार्ट्ज-जिपेल लेम्मा द्वारा यह असंभव है। हम यह निष्कर्ष निकालते हैं कि हमारे पास वास्तव में होना चाहिए


बहुपद विभाजन

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


अनुप्रयोग

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

  • डीविर द्वारा परिमित क्षेत्र काकेया अनुमान[3]
  • क्रोट, लेव और पाच द्वारा पर समान समस्या पर विकसित मूल रूपरेखा के साथ एलेनबर्ग और गिजस्विज्ट [7] द्वारा शीर्ष समुच्चय समस्या दी गई।[8]
  • गुथ और काट्ज़ द्वारा एर्दो की अलग-अलग दूरी की समस्या दी गई।[4]
  • गुथ और काट्ज़ द्वारा 3D में जोड़ों की समस्या[9] उनके तर्क को बाद में एलेकेस, कपलन और शारीर द्वारा सरल किया गया।[10]


यह भी देखें

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

संदर्भ

  1. ↑ Guth, L. (2016). कॉम्बिनेटरिक्स में बहुपद तरीके. University Lecture Series. American Mathematical Society. ISBN 978-1-4704-2890-7. Retrieved 2019-12-11.
  2. ↑ Alon, Noga (1999). "संयोजन शून्य प्रमेय". Combinatorics, Probability and Computing. 8 (1–2): 7–29. doi:10.1017/S0963548398003411. ISSN 0963-5483.
  3. ↑ 3.0 3.1 Dvir, Zeev (2008). "कैकेय के आकार पर परिमित क्षेत्रों में सेट होता है". Journal of the American Mathematical Society. 22 (4): 1093–1097. doi:10.1090/S0894-0347-08-00607-3. ISSN 0894-0347.
  4. ↑ 4.0 4.1 Guth, Larry; Katz, Nets (2015). "On the Erdős distinct distances problem in the plane". Annals of Mathematics: 155–190. doi:10.4007/annals.2015.181.1.2. hdl:1721.1/92873. ISSN 0003-486X.
  5. ↑ Kaplan, Haim; Matoušek, Jiří; Sharir, Micha (2012). "गुथ-काट्ज़ बहुपद विभाजन तकनीक के माध्यम से असतत ज्यामिति में शास्त्रीय प्रमेय के सरल प्रमाण". Discrete & Computational Geometry. 48 (3): 499–517. arXiv:1102.5391. doi:10.1007/s00454-012-9443-3. ISSN 0179-5376.
  6. ↑ Dvir, Zeev (2012). "घटना प्रमेय और उनके अनुप्रयोग". Foundations and Trends in Theoretical Computer Science. 6 (4): 257–393. arXiv:1208.5073. Bibcode:2012arXiv1208.5073D. doi:10.1561/0400000056. ISSN 1551-305X.
  7. ↑ Ellenberg, Jordan; Gijswijt, Dion (2017). "On large subsets of with no three-term arithmetic progression". Annals of Mathematics. 185 (1): 339–343. doi:10.4007/annals.2017.185.1.8. ISSN 0003-486X.
  8. ↑ Croot, Ernie; Lev, Vsevolod; Pach, Péter (2017). "Progression-free sets in are exponentially small" (PDF). Annals of Mathematics. 185 (1): 331–337. doi:10.4007/annals.2017.185.1.7. ISSN 0003-486X.
  9. ↑ Guth, Larry; Katz, Nets Hawk (2010). "कैकेय समस्या के असतत अनुरूपों में बीजगणितीय तरीके". Advances in Mathematics. 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). "तीन आयामों में लाइनों, जोड़ों और घटनाओं पर". Journal of Combinatorial Theory. Series A. 118 (3): 962–977. doi:10.1016/j.jcta.2010.11.008. ISSN 0097-3165.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=कॉम्बिनेटरिक्स_में_बहुपद_विधि&oldid=161646’