क्रमचय बहुपद: Difference between revisions

गणित में, क्रमचय [[बहुपद]] (किसी दिए गए वलय (गणित) के लिए) ऐसा बहुपद है जो वलय के तत्वों के क्रमचय के रूप में प्रदर्शित करता है, अर्थात मानचित्र के अनुसार <math>x \mapsto g(x)</math> का संचरण है। यदि वलय [[परिमित क्षेत्र]] है, तो [[डिक्सन बहुपद]], जो कि [[चेबिशेव बहुपद]] से निकटता से संबंधित हैं। इस प्रकार परिमित क्षेत्र पर, प्रत्येक कार्य, विशेष रूप से उस क्षेत्र के तत्वों के प्रत्येक क्रमचय को बहुपद फंक्शन के रूप में लिखा जा सकता है।

{{math|1='''F'''_''q'' = GF(''q'')}} की विशेषता का परिमित क्षेत्र (क्षेत्र सिद्धांत) {{mvar|p}}, अर्ताथ क्षेत्र {{mvar|q}}वाले  त्व जहां {{math|1=''q'' = ''p''^''e''}} कके कारण हैं। मुख्य रूप से इसके प्राइम मान के लिए {{mvar|p}} बहुपद {{mvar|f}} में गुणांक के साथ {{math|'''F'''_''q''}} प्रतीकात्मक रूप से लिखा गया है जहाँ पर {{math|''f'' ∈ '''F'''_''q''[''x'']}}) का क्रमचय बहुपद {{math|'''F'''_''q''}} है, इस प्रकार यदि फ़ंक्शन से {{math|'''F'''_''q''}} द्वारा ही परिभाषित किया गया है तो <math>c \mapsto f(c)</math> का क्रमपरिवर्तन {{math|'''F'''_''q''}} है।<ref>{{harvnb|Mullen|Panario|2013|loc=p. 215}}</ref> इसकी परिमितता के कारण {{math|'''F'''_''q''}}, इस परिभाषा को कई समान तरीकों से व्यक्त किया जा सकता है:<ref>{{harvnb|Lidl|Niederreiter|1997|loc=p. 348}}</ref>

* फंक्शन <math> c \mapsto f(c)</math> ऑन है ([[ विशेषण समारोह | विशेषण फंक्शन]] );

* फंक्शन <math>c \mapsto f(c)</math> एक-से-एक ([[इंजेक्शन समारोह|इंजेक्शन फंक्शन]]) है;

* {{math|1=''f''(''x'') = ''a''}} में मुख्य समाधान {{math|'''F'''_''q''}} है जिसमें प्रत्येक के लिए {{mvar|a}} में {{math|'''F'''_''q''}} सम्मिलित रहते हैं।

बहुपद क्रमचय बहुपद हैं जिसका लक्षण इसके वर्णन द्वारा दिया जाता है।

([[ एकांतवासी |एकांतवासी]] के सिद्धांत के अनुसार)<ref>{{harvnb|Lidl|Niederreiter|1997|loc= p. 349}}</ref><ref name="MP216">{{harvnb|Mullen|Panario|2013|loc=p. 216}}</ref> {{math|''f'' ∈ '''F'''_''q''[''x'']}} का क्रमचय बहुपद {{math|'''F'''_''q''}} है जिसके लिए निम्नलिखित दो शर्तें संलग्न की जाती हैं:

# {{mvar|f}} में आधार {{math|'''F'''_''q''}} रहता है ;

इस प्रकार यदि {{math|''f''(''x'')}} परिमित क्षेत्र पर परिभाषित क्रमचय बहुपद {{math|GF(''q'')}} है, तो {{math|1=''g''(''x'') = ''a'' ''f''(''x'' + ''b'') + ''c''}} इस प्रकार है कि सभी {{math|''a'' ≠ 0, ''b''}} और {{mvar|c}} में {{math|GF(''q'')}} के लिए क्रमपरिवर्तन बहुपद {{math|''g''(''x'')}} सामान्यीकृत रूप में है यदि {{math|''a'', ''b''}} और {{mvar|c}} को चुना जाता है जिससे कि {{math|''g''(''x'')}} [[मोनिक बहुपद]] के रूप में उपयोग में लाए जाते हैं, इस प्रकार {{math|1=''g''(0) = 0}} और (विशेषता प्रदान की {{mvar|p}} डिग्री को {{mvar|n}} बहुपद का विभाजित नहीं करता है) जिसका गुणांक {{math|1=''x''^{''n''&minus;1}}}0 है।

हर्मिट का मानदंड कम्प्यूटरीकृत रूप से गहनता से किया जाता हैं और सैद्धांतिक निष्कर्ष निकालने में इसका उपयोग करना मुश्किल हो सकता है। चूंकि, [[लियोनार्ड यूजीन डिक्सन]] सभी परिमित क्षेत्रों में अधिक से अधिक पांच डिग्री के सभी क्रमचय बहुपदों को खोजने के लिए इसका उपयोग करने में सक्षम थे। ये परिणाम हैं:<ref>{{harvnb|Dickson|1958|loc = pg. 63}}</ref><ref name="MP216" />

!{{math|'''F'''_''q''}} का सामान्यीकृत क्रमचय बहुपद

| <math>x^3 - ax</math> (<math>a</math> एक वर्ग नहीं हैं) || <math>q \equiv 0 \! \pmod 3</math>

| <math>x^4 + a_1 x^2 + a_2 x</math> (यदि इसकी केवल रूट {{math|'''F'''_''q''}} का मान 0 है ) || <math>q \equiv 0 \! \pmod 2</math>

| <math>x^5 - ax</math> (<math>a</math> चौथी पावर नहीं हैं) || <math>q \equiv 0 \! \pmod 5</math>

| <math>x^5 + ax^3 \pm x^2 + 3a^2 x</math> (<math>a</math> एक वर्ग नहीं हैं) || <math>q = 7</math>

| <math>x^5 + ax^3 + 5^{-1} a^2 x</math> (<math>a</math> आरबिटरी) || <math>q \equiv \pm 2 \! \pmod 5</math>

| <math>x^5 + ax^3 + 3a^2 x</math> (<math>a</math> एक वर्ग नहीं हैं) || <math>q = 13</math>

| <math>x^5 - 2ax^3 + a^2x</math> (<math>a</math> एक वर्ग नहीं हैं) || <math>q \equiv 0 \! \pmod 5</math>

सामान्यीकृत रूप में छह डिग्री के सभी मोनिक क्रमचय बहुपदों की सूची में {{harvtxt|शैलू|वानहीन|2013}} पाया जा सकता है।<ref>{{harvnb|Mullen|Panario|2013|loc=p. 217}}</ref>

यदि {{math|''a'' ≠ 0}} और {{math|''n'' > 1}} तब {{math|''D''_''n''(''x'', ''a'')}} GF(q) को अनुमति देता है यदि {{math|1=(''n'', ''q''² − 1) = 1}}.<ref>{{harvnb|Lidl|Niederreiter|1997|loc=p. 356}}</ref> यदि {{math|1=''a'' = 0}} तब {{math|1=''D''_''n''(''x'', 0) = ''x''^''n''}} और पिछला परिणाम धारण करता है।

* यदि {{math|GF(''q''^''r'')}} का [[फील्ड एक्सटेंशन]] है {{math|GF(''q'')}} डिग्री {{mvar|r}}, फिर रैखिककृत बहुपद <math display="block">L(x) = \sum_{s=0}^{r-1} \alpha_s x^{q^s},</math>इसके साथ {{math|α_''s''}} में {{math|GF(''q''^''r'')}}, पर रैखिक संकारक है {{math|GF(''q''^''r'')}} ऊपर {{math|GF(''q'')}}. रैखिक बहुपद {{math|''L''(''x'')}} क्रमपरिवर्तन {{math|GF(''q''^''r'')}} यदि और केवल यदि 0 का एकमात्र मूल {{math|''L''(''x'')}} में {{math|GF(''q''^''r'')}} है,<ref name="LN351" /> इस स्थिति को बीजगणितीय रूप में व्यक्त किया जा सकता है<ref name="LN362">{{harvnb|Lidl|Niederreiter|1997|loc=p. 362}}</ref> <math display="block"> \det\left ( \alpha_{i-j}^{q^j} \right ) \neq 0 \quad (i, j= 0,1,\ldots,r-1).</math>रैखिककृत बहुपद जो क्रमचय बहुपद हैं {{math|GF(''q''^''r'')}} रचना मोडुलो के संचालन के अनुसार [[समूह (गणित)]] <math>x^{q^r} - x</math> बनाते हैं, जिसे बेट्टी-मैथ्यू समूह के रूप में जाना जाता है, सामान्य रेखीय समूह के लिए समरूप {{math|GL(''r'', '''F'''_''q'')}} है।<ref name="LN362" />* यदि {{math|''g''(''x'')}} बहुपद वलय में है, जहाँ पर {{math|'''F'''_''q''[''x'']}} और {{math|''g''(''x''^''s'')}} का कोई अशून्य मूल नहीं है इस स्थिति में {{math|GF(''q'')}} तब {{mvar|s}} से विभाजित हो जाता हैं  जहाँ पर {{math|''q'' − 1}}, और {{math|''r'' > 1}} अपेक्षाकृत प्रधान (सह विभाज्य) {{math|''q'' − 1}} है, तब {{math|''x''^''r''(''g''(''x''^''s''))^{(''q'' - 1)/''s''}}} क्रमपरिवर्तन {{math|GF(''q'')}}.<ref name="MP216" />* क्रमचय बहुपदों के केवल कुछ अन्य विशिष्ट वर्ग समाप्त हुए {{math|GF(''q'')}} की विशेषता बताई जाती हैं। इनमें से दो, उदाहरण के लिए, हैं:<math display="block"> x^{(q + m - 1)/m} + ax </math>जहाँ {{mvar|m}} विभाजित करता है {{math|''q'' − 1}}, और<math display="block"> x^r \left(x^d - a\right)^{\left(p^n - 1\right)/d}</math>जहाँ {{mvar|d}} विभाजित करता है {{math|''p''^''n'' − 1}}.

एक असाधारण बहुपद {{math|GF(''q'')}} में बहुपद है {{math|'''F'''_''q''[''x'']}} जो क्रमचय बहुपद पर है {{math|GF(''q''^''m'')}} अपरिमित रूप से अनेकों के लिए {{mvar|m}}.<ref>{{harvnb|Mullen|Panario|2013|loc=p. 236}}</ref> को एक क्रमचय बहुपद ओवर {{math|GF(''q'')}} अधिकतम डिग्री {{math|''q''^1/4}} असाधारण ओवर है {{math|GF(''q'')}}<ref name="MP238">{{harvnb|Mullen|Panario|2013|loc=p. 238}}</ref> के हर क्रमपरिवर्तन {{math|GF(''q'')}} असाधारण बहुपद से प्रेरित है।<ref name="MP238" />

यदि पूर्णांक गुणांक वाला बहुपद (अर्थात, in {{math|ℤ[''x'']}}) क्रमपरिवर्तन बहुपद है {{math|GF(''p'')}} अपरिमित रूप से अनेक अभाज्य संख्याओं के लिए {{mvar|p}}, तो यह रैखिक और डिक्सन बहुपदों का संयोजन है।<ref>{{harvnb|Mullen|Panario|2013|loc=p. 239}}</ref> (नीचे शूर का अनुमान देखें)।

{{main|ओवल (प्रक्षेपी विमान)}}

[[परिमित ज्यामिति]] में कुछ बिंदुओं के समुच्चय का समन्वय वर्णन उच्च कोटि के क्रमचय बहुपदों के उदाहरण प्रदान कर सकता है। विशेष रूप से, परिमित प्रक्षेपी तल में एक अंडाकार (प्रक्षेपी तल) बनाने वाले बिंदु, {{math|PG(2,''q'')}} साथ {{math|''q''}} 2 की शक्ति के साथ, इस तरह से समन्वयित किया जा सकता है कि निर्देशांक के बीच संबंध एक [[ओ-बहुपद]] द्वारा दिया जाता है, जो एक है परिमित क्षेत्र पर विशेष प्रकार का क्रमचय बहुपद {{math|GF(''q'')}} है।

== कम्प्यूटरीकृत जटिलता ==

परिमित क्षेत्र पर दिया गया बहुपद क्रमचय बहुपद है या नहीं, यह जाँचने की समस्या को बहुपद समय में हल किया जा सकता है।<ref>{{cite journal | year = 2005 | id = {{ECCC|2005|05|008}} | first = Neeraj | last = Kayal | title=बहुपद समय में क्रमचय कार्यों को पहचानना| journal = Electronic Colloquium on Computational Complexity }} For earlier research on this problem, see: {{cite journal

किसी बहुपद <math>f \in \mathbb{F}_q[x_1,\ldots,x_n]</math> में क्रमचय बहुपद है जहाँ {{mvar|n}} चर ओवर <math>\mathbb{F}_q</math> हैं तब समीकरण <math>f(x_1,\ldots,x_n) = \alpha</math> प्राप्त होता है जहाँ <math>q^{n-1}</math> में परिणाम  <math>\mathbb{F}_q^n</math> के प्रत्येक मान के लिए <math>\alpha \in \mathbb{F}_q</math> प्राप्त होता हैं।<ref>{{harvnb|Mullen|Panario|2013|loc=p. 230}}</ref>

== परिमित वलय पर द्विघात क्रमचय बहुपद (QPP) ==

परिमित वलय Z/''n''Z के लिए द्विघात क्रमचय बहुपद का निर्माण किया जा सकता है। वास्तव में यह संभव है यदि ''n'' ''p²''  किसी अभाज्य संख्या p के लिए विभाज्य है। इस प्रकार निर्माण आश्चर्यजनक रूप से सरल है, फिर भी यह कुछ अच्छे गुणों के साथ क्रमपरिवर्तन उत्पन्न कर सकता है। यही कारण है कि इसका उपयोग [[3GPP लॉन्ग टर्म इवोल्यूशन]] मोबाइल दूरसंचार मानक में [[टर्बो कोड]] के इंटरलीवर घटक में किया गया है।<ref>[http://www.3gpp.org/ftp/Specs/html-info/36212.htm 3GPP TS 36.212]</ref>  

विचार करना <math> g(x) = 2x^2+x </math> अंगूठी Z/4Z के लिए देखता है: {{nowrap|<math> g(0) = 0</math>;}} {{nowrap|<math> g(1) = 3</math>;}} {{nowrap|<math> g(2) = 2</math>;}} {{nowrap|<math> g(3) = 1 </math>,}}

इसलिए बहुपद क्रमचय को परिभाषित करता है<math display="block">\begin{pmatrix}

\end{pmatrix} .</math>समान बहुपद पर विचार करें <math> g(x) = 2x^2+x </math> दूसरी वलय Z/''8''Z के लिए देखता है: {{nowrap|<math> g(0) = 0</math>;}} {{nowrap|<math> g(1) = 3</math>;}} {{nowrap|<math> g(2) = 2</math>;}} {{nowrap|<math> g(3) = 5</math>;}} {{nowrap|<math> g(4) = 4</math>;}} {{nowrap|<math> g(5) = 7</math>;}} {{nowrap|<math> g(6) = 6</math>;}} {{nowrap|<math> g(7) = 1</math>,}} तो बहुपद क्रमचय को परिभाषित करता है<math display="block">\begin{pmatrix}

<math> g(x) = ax^2+bx+c </math> वलय Z/''p<sup>k Z के लिए''

लेम्मा: ''k''=1 (अर्थात Z/''p''Z) के लिए ऐसा बहुपद केवल ''a''=0 और ''b'' शून्य के बराबर नहीं होने की स्थिति में क्रमपरिवर्तन को परिभाषित करता है। तो बहुपद द्विघात नहीं बल्कि रैखिक है।

लेम्मा: ''K''>1,  ''P''>2 (Z/''P^k''Z) ऐसा बहुपद क्रमचय को परिभाषित करता है यदि और केवल यदि <math>a \equiv 0 \pmod p</math> और <math>b \not \equiv 0 \pmod p</math>.

=== वलय Z/nZ ===

<math>n=p_1^{k_1}p_2^{k_2}...p_l^{k_l}</math>, जहां P_tअभाज्य संख्याएँ हैं।

लेम्मा: कोई भी बहुपद <math display="inline"> g(x) = a_0+ \sum_{0 < i \leq M} a_i x^i </math> वलय Z/''n''Z के लिए क्रमचय को परिभाषित करता है यदि और केवल यदि सभी बहुपद <math display="inline"> g_{p_t}(x) = a_{0,p_t}+ \sum_{0 < i \leq M} a_{i,p_t} x^i </math> सभी छल्लों के क्रमपरिवर्तन को परिभाषित करता है <math>Z/p_t^{k_t}Z</math>, कहाँ <math>a_{j,p_t}</math> के अवशेष हैं <math>a_{j}</math> मापांक <math>p_t^{k_t}</math> द्वारा प्रकट होता हैं।

 

एक परिणाम के रूप में निम्नलिखित सरल निर्माण का उपयोग करके बहुत से द्विघात क्रमचय बहुपदों का निर्माण कर सकते हैं।

<math>n = p_1^{k_1} p_2^{k_2} \dots p_l^{k_l}</math>, मान लीजिए कि K₁ > 1 पर विचार किया जाता हैं।

<math>ax^2+bx</math>, ऐसा है कि <math> a= 0 \bmod p_1</math>, लेकिन <math> a\ne 0 \bmod p_1^{k_1}</math>; ये मान लीजिए <math> a = 0 \bmod p_i^{k_i}</math>, i > 1. और मान लीजिए कि <math>b\ne 0 \bmod p_i</math> सभी के लिए {{math|1=''i'' = 1, ..., ''l''}}.

(उदाहरण के लिए, कोई ले सकता है <math> a=p_1 p_2^{k_2}...p_l^{k_l} </math> और <math>b=1</math> ह