कॉम्बिनेटरिक्स में बहुपद विधि: Difference between revisions
From Vigyanwiki
(Created page with "गणित में, बहुपद विधि संयोजन समस्याओं के लिए एक बीजगणितीय दृष्टिको...") |
No edit summary |
||
| (5 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="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>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> के लिए समुच्चय समान है। विशेष रूप से | |||
<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> प्राप्त करते हैं 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="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> | ||
* गुथ और काट्ज़ द्वारा एर्दो की अलग-अलग दूरी की समस्या<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> | |||
== यह भी देखें == | == यह भी देखें == | ||
* | *सांयोगिक शून्य समष्टि प्रमेय | ||
== संदर्भ == | == संदर्भ == | ||
| Line 53: | 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: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]
यह भी देखें
- सांयोगिक शून्य समष्टि प्रमेय
संदर्भ
- ↑ Guth, L. (2016). कॉम्बिनेटरिक्स में बहुपद तरीके. University Lecture Series. American Mathematical Society. ISBN 978-1-4704-2890-7. Retrieved 2019-12-11.
- ↑ Alon, Noga (1999). "संयोजन शून्य प्रमेय". Combinatorics, Probability and Computing. 8 (1–2): 7–29. doi:10.1017/S0963548398003411. ISSN 0963-5483.
- ↑ 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.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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
बाहरी संबंध
- Survey on the Polynomial Method by Terence Tao
- Survey on the Polynomial Method by Larry Guth
