क्रमचय बहुपद

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

परिमित वलय Z/nZ की स्थिति में, ऐसे बहुपदों का भी अध्ययन किया गया है और त्रुटि का पता लगाने और सुधार एल्गोरिदम के इंटरलीवर घटक में लागू किया गया है।

परिमित क्षेत्रों पर एकल चर क्रमचय बहुपद

F_q = GF(q) की विशेषता का परिमित क्षेत्र (क्षेत्र सिद्धांत) p, अर्ताथ क्षेत्र qवाले त्व जहां q = p^e कके कारण हैं। मुख्य रूप से इसके प्राइम मान के लिए p बहुपद f में गुणांक के साथ F_q प्रतीकात्मक रूप से लिखा गया है जहाँ पर f ∈ F_q[x]) का क्रमचय बहुपद F_q है, इस प्रकार यदि फ़ंक्शन से F_q द्वारा ही परिभाषित किया गया है तो $c\mapsto f(c)$ का क्रमपरिवर्तन F_q है। इसकी परिमितता के कारण F_q, इस परिभाषा को कई समान तरीकों से व्यक्त किया जा सकता है:

• फंक्शन $c\mapsto f(c)$ ऑन है ( विशेषण फंक्शन );
• फंक्शन $c\mapsto f(c)$ एक-से-एक (इंजेक्शन फंक्शन) है;
• f(x) = a में समाधान है F_q प्रत्येक के लिए a में F_q;
• f(x) = a में मुख्य समाधान F_q है जिसमें प्रत्येक के लिए a में F_q सम्मिलित रहते हैं।

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

(एकांतवासी के सिद्धांत के अनुसार) f ∈ F_q[x] का क्रमचय बहुपद F_q है जिसके लिए निम्नलिखित दो शर्तें संलग्न की जाती हैं:

1. f में आधार F_q रहता है ;
2. प्रत्येक पूर्णांक के लिए t साथ 1 ≤ t ≤ q − 2 और $t\not \equiv 0\!{\pmod {p}}$, की कमी f(x)^t mod (x^q − x) की डिग्री है ≤ q − 2.

इस प्रकार यदि f(x) परिमित क्षेत्र पर परिभाषित क्रमचय बहुपद GF(q) है, तो g(x) = a f(x + b) + c इस प्रकार है कि सभी a ≠ 0, b और c में GF(q) के लिए क्रमपरिवर्तन बहुपद g(x) सामान्यीकृत रूप में है यदि a, b और c को चुना जाता है जिससे कि g(x) मोनिक बहुपद के रूप में उपयोग में लाए जाते हैं, इस प्रकार g(0) = 0 और (विशेषता प्रदान की p डिग्री को n बहुपद का विभाजित नहीं करता है) जिसका गुणांक xⁿ⁻¹0 है।

परिमित क्षेत्रों पर परिभाषित क्रमपरिवर्तन बहुपदों से संबंधित कई प्रश्न हैं।

छोटी डिग्री

हर्मिट का मानदंड कम्प्यूटरीकृत रूप से गहनता से किया जाता हैं और सैद्धांतिक निष्कर्ष निकालने में इसका उपयोग करना मुश्किल हो सकता है। चूंकि, लियोनार्ड यूजीन डिक्सन सभी परिमित क्षेत्रों में अधिक से अधिक पांच डिग्री के सभी क्रमचय बहुपदों को खोजने के लिए इसका उपयोग करने में सक्षम थे। ये परिणाम हैं:

Fq का सामान्यीकृत क्रमचय बहुपद	q
$x$	any $q$
$x^{2}$	$q\equiv 0\!{\pmod {2}}$
$x^{3}$	$q\not \equiv 1\!{\pmod {3}}$
$x^{3}-ax$ ($a$ एक वर्ग नहीं हैं)	$q\equiv 0\!{\pmod {3}}$
$x^{4}\pm 3x$	$q=7$
$x^{4}+a_{1}x^{2}+a_{2}x$ (यदि इसकी केवल रूट Fq का मान 0 है )	$q\equiv 0\!{\pmod {2}}$
$x^{5}$	$q\not \equiv 1\!{\pmod {5}}$
$x^{5}-ax$ ($a$ चौथी पावर नहीं हैं)	$q\equiv 0\!{\pmod {5}}$
$x^{5}+ax\,(a^{2}=2)$	$q=9$
$x^{5}\pm 2x^{2}$	$q=7$
$x^{5}+ax^{3}\pm x^{2}+3a^{2}x$ ($a$ एक वर्ग नहीं हैं)	$q=7$
$x^{5}+ax^{3}+5^{-1}a^{2}x$ ($a$ आरबिटरी)	$q\equiv \pm 2\!{\pmod {5}}$
$x^{5}+ax^{3}+3a^{2}x$ ($a$ एक वर्ग नहीं हैं)	$q=13$
$x^{5}-2ax^{3}+a^{2}x$ ($a$ एक वर्ग नहीं हैं)	$q\equiv 0\!{\pmod {5}}$

सामान्यीकृत रूप में छह डिग्री के सभी मोनिक क्रमचय बहुपदों की सूची में शैलू & वानहीन (2013) पाया जा सकता है।

क्रमपरिवर्तन बहुपदों के कुछ वर्ग

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

• xⁿ क्रमपरिवर्तन GF(q) यदि n और q − 1 सह अभाज्य पूर्णांक हैं (विशेष रूप से, (n, q − 1) = 1)
• यदि a में है GF(q) और n ≥ 1 फिर डिक्सन बहुपद (पहली तरह का) D_n(x,a) द्वारा परिभाषित किया गया है।
  $$D_{n}(x,a)=\sum _{j=0}^{\lfloor n/2\rfloor }{\frac {n}{n-j}}{\binom {n-j}{j}}(-a)^{j}x^{n-2j}.$$
  इन्हें पुनरावर्ती संबंध से भी प्राप्त किया जा सकता है
  $$D_{n}(x,a)=xD_{n-1}(x,a)-aD_{n-2}(x,a),$$
  प्रारंभिक शर्तों के साथ $D_{0}(x,a)=2$ और $D_{1}(x,a)=x$, इसके पहले कुछ डिक्सन बहुपद हैं:

• $D_{2}(x,a)=x^{2}-2a$
• $D_{3}(x,a)=x^{3}-3ax$
• $D_{4}(x,a)=x^{4}-4ax^{2}+2a^{2}$
• $D_{5}(x,a)=x^{5}-5ax^{3}+5a^{2}x.$

यदि a ≠ 0 और n > 1 तब D_n(x, a) GF(q) को अनुमति देता है यदि (n, q² − 1) = 1. यदि a = 0 तब D_n(x, 0) = xⁿ और पिछला परिणाम धारण करता है।

• यदि GF(q^r) का फील्ड एक्सटेंशन है GF(q) डिग्री r, फिर रैखिककृत बहुपद
  $$L(x)=\sum _{s=0}^{r-1}\alpha _{s}x^{q^{s}},$$
  इसके साथ α_s में GF(q^r), पर रैखिक संकारक है GF(q^r) ऊपर GF(q). रैखिक बहुपद L(x) क्रमपरिवर्तन GF(q^r) यदि और केवल यदि 0 का एकमात्र मूल L(x) में GF(q^r) है, इस स्थिति को बीजगणितीय रूप में व्यक्त किया जा सकता है
  $$\det \left(\alpha _{i-j}^{q^{j}}\right)\neq 0\quad (i,j=0,1,\ldots ,r-1).$$
  रैखिककृत बहुपद जो क्रमचय बहुपद हैं GF(q^r) रचना मोडुलो के संचालन के अनुसार समूह (गणित) $x^{q^{r}}-x$ बनाते हैं, जिसे बेट्टी-मैथ्यू समूह के रूप में जाना जाता है, सामान्य रेखीय समूह के लिए समरूप GL(r, F_q) है।* यदि g(x) बहुपद वलय में है, जहाँ पर F_q[x] और g(x^s) का कोई अशून्य मूल नहीं है इस स्थिति में GF(q) तब s से विभाजित हो जाता हैं जहाँ पर q − 1, और r > 1 अपेक्षाकृत प्रधान (सह विभाज्य) q − 1 है, तब x^r(g(x^s))^{(q - 1)/s} क्रमपरिवर्तन GF(q).* क्रमचय बहुपदों के केवल कुछ अन्य विशिष्ट वर्ग समाप्त हुए GF(q) की विशेषता बताई जाती हैं। इनमें से दो, उदाहरण के लिए, हैं:
  $$x^{(q+m-1)/m}+ax$$
  जहाँ m विभाजित करता है q − 1, और
  $$x^{r}\left(x^{d}-a\right)^{\left(p^{n}-1\right)/d}$$
  जहाँ d विभाजित करता है pⁿ − 1.

असाधारण बहुपद

एक असाधारण बहुपद GF(q) में बहुपद है F_q[x] जो क्रमचय बहुपद पर है GF(q^m) अपरिमित रूप से अनेकों के लिए m. को एक क्रमचय बहुपद ओवर GF(q) अधिकतम डिग्री q^1/4 असाधारण ओवर है GF(q) के हर क्रमपरिवर्तन GF(q) असाधारण बहुपद से प्रेरित है।

यदि पूर्णांक गुणांक वाला बहुपद (अर्थात, in ℤ[x]) क्रमपरिवर्तन बहुपद है GF(p) अपरिमित रूप से अनेक अभाज्य संख्याओं के लिए p, तो यह रैखिक और डिक्सन बहुपदों का संयोजन है। (नीचे शूर का अनुमान देखें)।

ज्यामितीय उदाहरण

Main article: ओवल (प्रक्षेपी विमान)

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

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

परिमित क्षेत्र पर दिया गया बहुपद क्रमचय बहुपद है या नहीं, यह जाँचने की समस्या को बहुपद समय में हल किया जा सकता है।

परिमित क्षेत्रों पर कई चरों में क्रमचय बहुपद

किसी बहुपद $f\in \mathbb {F} _{q}[x_{1},\ldots ,x_{n}]$ में क्रमचय बहुपद है जहाँ n चर ओवर $\mathbb {F} _{q}$ हैं तब समीकरण $f(x_{1},\ldots ,x_{n})=\alpha$ प्राप्त होता है जहाँ $q^{n-1}$ में परिणाम $\mathbb {F} _{q}^{n}$ के प्रत्येक मान के लिए $\alpha \in \mathbb {F} _{q}$ प्राप्त होता हैं।

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

परिमित वलय Z/nZ के लिए द्विघात क्रमचय बहुपद का निर्माण किया जा सकता है। वास्तव में यह संभव है यदि n p² किसी अभाज्य संख्या p के लिए विभाज्य है। इस प्रकार निर्माण आश्चर्यजनक रूप से सरल है, फिर भी यह कुछ अच्छे गुणों के साथ क्रमपरिवर्तन उत्पन्न कर सकता है। यही कारण है कि इसका उपयोग 3GPP लॉन्ग टर्म इवोल्यूशन मोबाइल दूरसंचार मानक में टर्बो कोड के इंटरलीवर घटक में किया गया है।

सरल उदाहरण

विचार करना $g(x)=2x^{2}+x$ अंगूठी Z/4Z के लिए देखता है: $g(0)=0$; $g(1)=3$; $g(2)=2$; $g(3)=1$, इसलिए बहुपद क्रमचय को परिभाषित करता है

$${\begin{pmatrix}0&1&2&3\\0&3&2&1\end{pmatrix}}.$$

समान बहुपद पर विचार करें $g(x)=2x^{2}+x$ दूसरी वलय Z/8Z के लिए देखता है: $g(0)=0$; $g(1)=3$; $g(2)=2$; $g(3)=5$; $g(4)=4$; $g(5)=7$; $g(6)=6$; $g(7)=1$, तो बहुपद क्रमचय को परिभाषित करता है

$${\begin{pmatrix}0&1&2&3&4&5&6&7\\0&3&2&5&4&7&6&1\end{pmatrix}}.$$

वलय Z/P^kZ

$g(x)=ax^{2}+bx+c$ वलय Z/p^{k Z के लिए}

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

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

वलय Z/nZ

$n=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{l}^{k_{l}}$, जहां P_tअभाज्य संख्याएँ हैं।

लेम्मा: कोई भी बहुपद ${\textstyle g(x)=a_{0}+\sum _{0<i\leq M}a_{i}x^{i}}$ वलय Z/nZ के लिए क्रमचय को परिभाषित करता है यदि और केवल यदि सभी बहुपद ${\textstyle g_{p_{t}}(x)=a_{0,p_{t}}+\sum _{0<i\leq M}a_{i,p_{t}}x^{i}}$ सभी छल्लों के क्रमपरिवर्तन को परिभाषित करता है $Z/p_{t}^{k_{t}}Z$, कहाँ $a_{j,p_{t}}$ के अवशेष हैं $a_{j}$ मापांक $p_{t}^{k_{t}}$ द्वारा प्रकट होता हैं।

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

$n=p_{1}^{k_{1}}p_{2}^{k_{2}}\dots p_{l}^{k_{l}}$, मान लीजिए कि K₁ > 1 पर विचार किया जाता हैं।

$ax^{2}+bx$, ऐसा है कि $a=0{\bmod {p}}_{1}$, लेकिन $a\neq 0{\bmod {p}}_{1}^{k_{1}}$; ये मान लीजिए $a=0{\bmod {p}}_{i}^{k_{i}}$, i > 1. और मान लीजिए कि $b\neq 0{\bmod {p}}_{i}$ सभी के लिए i = 1, ..., l.

(उदाहरण के लिए, कोई ले सकता है $a=p_{1}p_{2}^{k_{2}}...p_{l}^{k_{l}}$ और $b=1$ होने पर ऐसा बहुपद क्रमचय को परिभाषित करता है।

इसे देखने के लिए हम देखते हैं कि सभी प्राइम P के लिए_i, i > 1, इस द्विघात बहुपद मॉड्यूलो P_i की कमी वास्तव में रैखिक बहुपद है और इसलिए तुच्छ कारण से क्रमचय है। पहली अभाज्य संख्या के लिए हमें पहले चर्चा की गई लेम्मा का उपयोग यह देखने के लिए करना चाहिए कि यह क्रमचय को परिभाषित करती है।

उदाहरण के लिए विचार करें Z/12Z और बहुपद $6x^{2}+x$. यह क्रमचय को परिभाषित करता है

<math> {b आव्यूह} 0 और 1 और 2 और 3 और 4 और 5 और 6 और 7 और 8 और \cdots \\ 0 और 7 और 2 और 9 और 4 और 11 और 6 और 1 और 8 और \cdots \end{pmatrix} </math>

परिमित रिंगों पर उच्च डिग्री बहुपद

वलय 'Z'/p के लिए बहुपद g(x)।^kZ क्रमचय बहुपद है, यदि यह परिमित क्षेत्र Z/pZ की अनुमति देता है और $g'(x)\neq 0{\bmod {p}}$ सभी x in 'Z'/p के लिए^kZ, जहाँ g'(x) g(x) का औपचारिक व्युत्पन्न है।

शूर का अनुमान

K एक बीजगणितीय संख्या क्षेत्र है जिसमें R पूर्णांकों का वलय है। शब्द "शूर का अनुमान" इस अभिकथन को संदर्भित करता है कि, यदि K पर परिभाषित बहुपद f को मुख्य रूप से कई प्रमुख आदर्श P के लिए R/P पर क्रमचय बहुपद है, तो f डिक्सन बहुपदों, डिग्री-एक बहुपदों और बहुपदों की संरचना है। फॉर्म x^{k वास्तव में, शूर ने इस दिशा में कोई अनुमान नहीं लगाया जा सकता हैं। उसने जो धारणा की वह फ्राइड के कारण है, जिसने परिणाम के असत्य संस्करण का त्रुटिपूर्ण प्रमाण दिया हैं। टर्नवाल्ड और मुलर द्वारा सही प्रमाण दिए गए हैं।}

संदर्भ

• Dickson, L. E. (1958) [1901]. Linear Groups with an Exposition of the Galois Field Theory. New York: Dover.
• Lidl, Rudolf; Mullen, Gary L. (March 1988). "When Does a Polynomial over a Finite Field Permute the Elements of the Field?". The American Mathematical Monthly. 95 (3): 243–246. doi:10.2307/2323626.
• Lidl, Rudolf; Mullen, Gary L. (January 1993). "When Does a Polynomial over a Finite Field Permute the Elements of the Field?, II". The American Mathematical Monthly. 100 (1): 71–74. doi:10.2307/2324822.
• Lidl, Rudolf; Niederreiter, Harald (1997). Finite fields. Encyclopedia of Mathematics and Its Applications. Vol. 20 (2nd ed.). Cambridge University Press. ISBN 0-521-39231-4. Zbl 0866.11069. Chapter 7.
• Mullen, Gary L.; Panario, Daniel (2013). Handbook of Finite Fields. CRC Press. ISBN 978-1-4398-7378-6. Chapter 8.
• Shallue, C.J.; Wanless, I.M. (March 2013). "Permutation polynomials and orthomorphism polynomials of degree six". Finite Fields and Their Applications. 20: 84–92. doi:10.1016/j.ffa.2012.12.003.