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

From Vigyanwiki
No edit summary
No edit summary
 
(4 intermediate revisions by 3 users not shown)
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>\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>K</math> का आकार कम से कम <math>c_nq^{n-1}</math>है। और <math>c_nq^n</math> की सीमा आंशिक अतिरिक्त कार्य के साथ उसी विधि का उपयोग करके प्राप्त किया जा सकता है।


मान लें कि हमारे पास काकेया समुच्चय <math>K</math> है।  
मान लें कि हमारे पास काकेया समुच्चय <math>K</math> है।  
Line 19: Line 19:
<math>|K| < {q+n-3\choose n-1}</math>
<math>|K| < {q+n-3\choose n-1}</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>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>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>
सभी अशून्य के लिए <math>t \in \mathbb{F}_q</math>. हालाँकि, <math>P(tx+y) </math> डिग्री का बहुपद है <math>q-2</math> में <math>t</math> लेकिन यह कम से कम है <math>q-1</math> के अशून्य तत्वों के अनुरूप जड़ें <math>\mathbb{F}_q</math> तो यह समान रूप से शून्य होना चाहिए। विशेष रूप से, प्लग इन करना <math>t = 0</math> हम निष्कर्ष निकालते हैं <math>P(y) = 0</math>.


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


<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" />
*क्रोट, लेव और पाच द्वारा <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>
*क्रोट, लेव और पाच द्वारा <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"/>
* गुथ और काट्ज़ द्वारा एर्दो की अलग-अलग दूरी की समस्या दी गई।<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>
*गुथ और काट्ज़ द्वारा 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>




Line 57: Line 59:
*[https://arxiv.org/abs/1310.6482 Survey on the Polynomial Method] by Terence Tao
*[https://arxiv.org/abs/1310.6482 Survey on the Polynomial Method] by Terence Tao
*[http://math.mit.edu/~lguth/Exposition/erdossurvey.pdf Survey on the Polynomial Method] by Larry Guth
*[http://math.mit.edu/~lguth/Exposition/erdossurvey.pdf Survey on the Polynomial Method] by Larry Guth
[[Category: साहचर्य]]


[[Category: Machine Translated Page]]
[[Category:Created On 06/05/2023]]
[[Category:Created On 06/05/2023]]
[[Category:Machine Translated Page]]
[[Category:Templates Vigyan Ready]]
[[Category:साहचर्य]]

Latest revision as of 10:03, 18 May 2023

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

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

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

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

उदाहरण

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

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

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

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

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

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

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

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



बहुपद विभाजन

बहुपद पद्धति की एक भिन्नता जिसे प्रायः बहुपद विभाजन कहा जाता है, जिसको गुथ और काट्ज़ ने एर्दो की अलग-अलग दूरी की समस्या के समाधान में प्रस्तुत किया था।[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=162480’