क्रमचय बहुपद

गणित में, क्रमचय बहुपद (किसी दिए गए वलय (गणित) के लिए) बहुपद है जो वलय के तत्वों के क्रमचय के रूप में कार्य करता है, अर्थात मानचित्र $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 है।

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

छोटी डिग्री

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

Normalized Permutation Polynomial of Fq	q
$x$	any $q$
$x^{2}$	$q\equiv 0\!{\pmod {2}}$
$x^{3}$	$q\not \equiv 1\!{\pmod {3}}$
$x^{3}-ax$ ($a$ not a square)	$q\equiv 0\!{\pmod {3}}$
$x^{4}\pm 3x$	$q=7$
$x^{4}+a_{1}x^{2}+a_{2}x$ (if its only root in Fq is 0)	$q\equiv 0\!{\pmod {2}}$
$x^{5}$	$q\not \equiv 1\!{\pmod {5}}$
$x^{5}-ax$ ($a$ not a fourth power)	$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$ not a square)	$q=7$
$x^{5}+ax^{3}+5^{-1}a^{2}x$ ($a$ arbitrary)	$q\equiv \pm 2\!{\pmod {5}}$
$x^{5}+ax^{3}+3a^{2}x$ ($a$ not a square)	$q=13$
$x^{5}-2ax^{3}+a^{2}x$ ($a$ not a square)	$q\equiv 0\!{\pmod {5}}$

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

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

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

• xⁿ क्रमपरिवर्तन GF(q) अगर और केवल अगर n और q − 1 Coprime पूर्णांक हैं (विशेष रूप से, (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. एक क्रमचय बहुपद over GF(q) अधिकतम डिग्री q^1/4 असाधारण ओवर है GF(q). का हर क्रमपरिवर्तन GF(q) असाधारण बहुपद से प्रेरित है।

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

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

Main article: Oval (projective plane)

परिमित ज्यामिति में कुछ बिंदुओं के समुच्चय का समन्वय वर्णन उच्च कोटि के क्रमचय बहुपदों के उदाहरण प्रदान कर सकता है। विशेष रूप से, परिमित प्रक्षेपी तल में अंडाकार (प्रक्षेपी तल) बनाने वाले बिंदु, 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 लॉन्ग टर्म इवोल्यूशन मोबाइल दूरसंचार मानक में टर्बो कोड के इंटरलीवर घटक में किया गया है (3GPP तकनीकी विनिर्देश 36.212 देखें) उदा. संस्करण 8.8.0 में पृष्ठ 14)।

सरल उदाहरण

विचार करना $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}}.$$

रिंग्स जेड/P^kजेड

विचार करना $g(x)=ax^{2}+bx+c$ रिंग Z/p के लिए^{क</सुप>}ज़ेड.

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

लेम्मा: के>1, पी>2 (जेड/पी^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}}$, जहां प_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}}$, मान लीजिए कि के₁ > 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$). तब ऐसा बहुपद क्रमचय को परिभाषित करता है।

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

उदाहरण के लिए विचार करें Z/12Z और बहुपद $6x^{2}+x$. यह क्रमचय को परिभाषित करता है <गणित डिस्प्ले = ब्लॉक'>\शुरू {बीमैट्रिक्स} 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 डिक्सन बहुपदों, डिग्री-एक बहुपदों और बहुपदों की संरचना है। फॉर्म एक्स^{क</सुप>. वास्तव में, कुछ नहीं ने इस दिशा में कोई अनुमान नहीं लगाया। उसने जो धारणा की वह फ्राइड के कारण है, जिसने परिणाम के झूठे संस्करण का त्रुटिपूर्ण प्रमाण दिया। टर्नवाल्ड द्वारा सही प्रमाण दिए गए हैं और मुलर।}

संदर्भ

• 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.