ในทางคณิตศาสตร์พหุนามการเรียงสับเปลี่ยน (สำหรับวงแหวน ที่กำหนด ) คือพหุนามที่ทำหน้าที่เป็นการเรียงสับเปลี่ยนขององค์ประกอบของวงแหวน กล่าวคือ แผนที่นั้นเป็นการจับคู่แบบหนึ่งต่อหนึ่งในกรณีที่วงแหวนเป็นฟิลด์จำกัดพหุนามดิกสันซึ่งมีความสัมพันธ์อย่างใกล้ชิดกับพหุนามเชบิเชฟเป็นตัวอย่างหนึ่ง ^{[ 1 ]} บนฟิลด์จำกัด ฟังก์ชันทุกฟังก์ชัน โดยเฉพาะอย่างยิ่งการเรียงสับเปลี่ยนขององค์ประกอบของฟิลด์นั้น สามารถเขียนได้เป็นฟังก์ชันพหุนาม ${\displaystyle x\mapsto g(x)}$

ในกรณีของวงแหวนจำกัดZ / n Zพหุนามดังกล่าวได้รับการศึกษาและนำไปใช้ใน ส่วนประกอบ ตัวสลับของอัลกอริธึมการตรวจจับและแก้ไขข้อผิดพลาด ด้วยเช่นกัน ^{[ 2 ] [ 3 ]}

ให้F _q = GF( q )เป็นฟิลด์จำกัดที่มีลักษณะเฉพาะpนั่นคือฟิลด์ที่มีสมาชิกq ตัว โดยที่ q = p ^eสำหรับจำนวนเฉพาะp บางตัว พหุนามfที่มีสัมประสิทธิ์ในF _q (เขียนเชิงสัญลักษณ์เป็นf ∈ F _q [ x ] ) เป็นพหุนามการเรียงสับเปลี่ยนของF _qถ้าฟังก์ชันจากF _{q ไปยังตัวมันเอง} ^ที่กำหนดโดยเป็นการเรียงสับเปลี่ยนของF _q [ ^{4 ]}${\displaystyle c\mapsto f(c)}$

เนื่องจากF _q มีค่าจำกัด คำจำกัดความนี้จึงสามารถแสดงได้หลายวิธีที่เทียบเท่ากัน: ^{[ 5 ]}

• ฟังก์ชันนี้เป็น ฟังก์ชัน ทั่วถึง ( surjective )${\displaystyle c\mapsto f(c)}$
• ฟังก์ชันนี้เป็น ฟังก์ชัน หนึ่งต่อหนึ่ง ( ฟังก์ชัน หนึ่งต่อหนึ่ง )${\displaystyle c\mapsto f(c)}$
• f ( x ) = aมีคำตอบใน F _qสำหรับแต่ละ aใน F _q ;
• f ( x ) = aมีที่ไม่ซ้ำกันใน F _qสำหรับแต่ละ aใน F _q

ลักษณะเฉพาะของพหุนามที่เป็นพหุนามการเรียงสับเปลี่ยนนั้นกำหนดโดย

( เกณฑ์ของHermite ) ^{[ 6 ] [ 7 ]} f ∈ F _q [ x ]เป็นพหุนามการเรียงสับเปลี่ยนของF _qก็ต่อเมื่อเงื่อนไขสองข้อต่อไปนี้เป็นจริง:

1. fมีรากเพียงหนึ่งเดียวในFq _;
2. สำหรับจำนวนเต็มt แต่ละตัว ที่มี1 ≤ t ≤ q − 2และการลดรูปของf ( x ) ^t mod ( x ^q − x )จะมีดีกรี≤ q − 2${\displaystyle t\not \equiv 0\!{\pmod {p}}}$

ถ้า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 ^{n −1}เท่ากับ 0

ยังมีคำถามเปิดอีกมากมายเกี่ยวกับพหุนามการเรียงสับเปลี่ยนที่กำหนดไว้เหนือฟิลด์จำกัด^{[ 8 ] [ 9 ]}

เกณฑ์ของ Hermite ต้องใช้การคำนวณอย่างมากและอาจใช้ได้ยากในการสรุปทางทฤษฎี อย่างไรก็ตามDicksonสามารถใช้เกณฑ์นี้เพื่อค้นหาพหุนามการเรียงสับเปลี่ยนทั้งหมดที่มีดีกรีไม่เกินห้าเหนือฟิลด์จำกัดทั้งหมด ผลลัพธ์เหล่านี้คือ: ^{[ 10 ] [ 7 ]}

พหุนามการเรียงสับเปลี่ยนมาตรฐานของF q	q
${\displaystyle x}$	ใดๆ${\displaystyle q}$
${\displaystyle x^{2}}$	${\displaystyle q\equiv 0\!{\pmod {2}}}$
${\displaystyle x^{3}}$	${\displaystyle q\not \equiv 1\!{\pmod {3}}}$
${\displaystyle x^{3}-ax}$( ไม่ใช่รูปสี่เหลี่ยมจัตุรัส)${\displaystyle a}$	${\displaystyle q\equiv 0\!{\pmod {3}}}$
${\displaystyle x^{4}\pm 3x}$	${\displaystyle q=7}$
${\displaystyle x^{4}+a_{1}x^{2}+a_{2}x}$(ถ้ารากเดียวในFq คือ 0)	${\displaystyle q\equiv 0\!{\pmod {2}}}$
${\displaystyle x^{5}}$	${\displaystyle q\not \equiv 1\!{\pmod {5}}}$
${\displaystyle x^{5}-ax}$( ไม่ใช่กำลังสี่)${\displaystyle a}$	${\displaystyle q\equiv 0\!{\pmod {5}}}$
${\displaystyle x^{5}+ax\,(a^{2}=2)}$	${\displaystyle q=9}$
${\displaystyle x^{5}\pm 2x^{2}}$	${\displaystyle q=7}$
${\displaystyle x^{5}+ax^{3}\pm x^{2}+3a^{2}x}$( ไม่ใช่รูปสี่เหลี่ยมจัตุรัส)${\displaystyle a}$	${\displaystyle q=7}$
${\displaystyle x^{5}+ax^{3}+5^{-1}a^{2}x}$( ตามอำเภอใจ)${\displaystyle a}$	${\displaystyle q\equiv \pm 2\!{\pmod {5}}}$
${\displaystyle x^{5}+ax^{3}+3a^{2}x}$( ไม่ใช่รูปสี่เหลี่ยมจัตุรัส)${\displaystyle a}$	${\displaystyle q=13}$
${\displaystyle x^{5}-2ax^{3}+a^{2}x}$( ไม่ใช่รูปสี่เหลี่ยมจัตุรัส)${\displaystyle a}$	${\displaystyle q\equiv 0\!{\pmod {5}}}$

รายการพหุนามการเรียงสับเปลี่ยนโมโนนิกทั้งหมดที่มีดีกรีหกในรูปแบบมาตรฐานสามารถพบได้ในShallue & Wanless (2013 ) ^{[ 11 ]}

นอกเหนือจากตัวอย่างข้างต้นแล้ว รายการต่อไปนี้แม้จะไม่ครบถ้วนสมบูรณ์ แต่ก็มีคลาสหลักเกือบทั้งหมดของพหุนามการเรียงสับเปลี่ยนที่รู้จักบนฟิลด์จำกัด^{[ 12 ]}

• x ⁿสลับ GF( q ) ก็ต่อ เมื่อ nและ q − 1เป็น จำนวนเฉพาะ สัมพัทธ์ (ในเชิงสัญลักษณ์ ( n , q − 1) = 1 ) ^{[ 13 ]}
• ถ้าaอยู่ในGF( q )และn ≥ 1แล้วพหุนามดิกสัน (ชนิดแรก) D _n ( x , a )จะถูกกำหนดโดย$${\displaystyle D_{n}(x,a)=\sum _{j=0}^{\lfloor n/2\rfloor }{\frac {n}{nj}}{\binom {nj}{j}}(-a)^{j}x^{n-2j}.}$$

ค่าเหล่านี้สามารถหาได้จากการคำนวณแบบเวียนเกิด โดยใช้เงื่อนไขเริ่มต้นและพหุนามดิกสันชุดแรกๆ มีดังนี้: $${\displaystyle D_{n}(x,a)=xD_{n-1}(x,a)-aD_{n-2}(x,a),}$$${\displaystyle D_{0}(x,a)=2}$${\displaystyle D_{1}(x,a)=x}$

• ${\displaystyle D_{2}(x,a)=x^{2}-2a}$
• ${\displaystyle D_{3}(x,a)=x^{3}-3ax}$
• ${\displaystyle D_{4}(x,a)=x^{4}-4ax^{2}+2a^{2}}$
• ${\displaystyle 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 [ ^{14 ] ถ้า} a = 0แล้วD _n ( x , 0) = x ⁿและผลลัพธ์ก่อนหน้านี้เป็นจริง

• ถ้าGF( q ^r )เป็นส่วนขยายของGF( q )ที่มีดีกรีrแล้วพหุนามเชิงเส้น ที่มีα _sในGF( q ^r )จะเป็นตัวดำเนินการเชิงเส้นบนGF( q ^r )เหนือGF( q )พหุนามเชิงเส้นL ( x )สลับGF( q ^r )ก็ต่อเมื่อ 0 เป็นรากเดียวของL ( x )ในGF( q ^r ) [ ^{13 ]}เงื่อนไขนี้สามารถแสดงเป็นพีชคณิตได้^{ดังนี้[ 15 ]}$${\displaystyle L(x)=\sum _{s=0}^{r-1}\alpha _{s}x^{q^{s}},}$$$${\displaystyle \det \left(\alpha _{i-j}^{q^{j}}\right)\neq 0\quad (i,j=0,1,\ldots ,r-1).}$$

พหุนามเชิงเส้นที่เป็นพหุนามการเรียงสับเปลี่ยนเหนือ^GF ( q ^r )ก่อให้เกิดกลุ่มภายใต้การดำเนินการประกอบโมดูลซึ่งเรียกว่ากลุ่ม Betti-Mathieu ซึ่งสมมาตรกับกลุ่มเชิงเส้นทั่วไปGL( r , F _q ) [ ^{15 ]}${\displaystyle x^{q^{r}}-x}$

• ถ้าg ( x )อยู่ในวงแหวนพหุนาม_Fq [ x ]และ g ( xs ) ^{ไม่มี}รากที่ไม่เป็นศูนย์ในGF ( q )เมื่อs หาร q − 1ลงตัวและr > 1เป็นจำนวนเฉพาะสัมพัทธ์ (เป็นจำนวนเฉพาะร่วม) กับq − 1แล้วxr ( ^g ( xs ⁾ ) ^{( q - 1)/ s จะ}สลับGF ⁽ q ) [ ⁷ ]
• มีเพียงไม่กี่คลาสเฉพาะของพหุนามการเรียงสับเปลี่ยนบนGF( q ) เท่านั้น ที่ได้รับการระบุลักษณะไว้แล้ว ตัวอย่างเช่น สองคลาสนี้ได้แก่: โดยที่mหารq − 1 ลงตัว และโดยที่d หาร p ⁿ − 1 ลงตัว$${\displaystyle x^{(q+m-1)/m}+ax}$$$${\displaystyle x^{r}\left(x^{d}-a\right)^{\left(p^{n}-1\right)/d}}$$

พหุนามพิเศษเหนือGF( q )คือพหุนามในFq _[ x ]ซึ่งเป็นพหุนามการเรียงสับเปลี่ยนบนGF ( qm ) ^{สำหรับ} mจำนวนอนันต์^{[ 16 ]}

พหุนามการเรียงสับเปลี่ยนเหนือGF( q ) ที่มี ^{ดีกรี}ไม่เกินq ^1/4ถือเป็นข้อยกเว้นเหนือGF( q ) [ ^{17 ]}

การเรียงสับเปลี่ยนทุกแบบของGF( q )เกิดจากพหุนามพิเศษ^{[ 17 ]}

ถ้าพหุนามที่มีสัมประสิทธิ์จำนวนเต็ม (เช่น ในℤ[ x ] ) เป็นพหุนามการเรียงสับเปลี่ยนเหนือGF( p )สำหรับจำนวนเฉพาะp ที่ไม่มีที่สิ้นสุด แสดงว่ามันคือการประกอบกันของพหุนามเชิงเส้นและพหุนามดิกสัน^{[ 18 ]} (ดูข้อสันนิษฐานของชูร์ด้านล่าง)

ในเรขาคณิตจำกัดคำอธิบายพิกัดของเซตจุดบางเซตสามารถให้ตัวอย่างของพหุนามการเรียงสับเปลี่ยนที่มีดีกรีสูงกว่าได้ โดยเฉพาะอย่างยิ่ง จุดที่ประกอบกันเป็นรูปวงรีในระนาบเชิงโปรเจกทีฟ จำกัด PG (2, q )โดยที่qเป็นกำลังของ 2 สามารถกำหนดพิกัดได้ในลักษณะที่ความสัมพันธ์ระหว่างพิกัดนั้นกำหนดโดยพหุนาม o ซึ่งเป็นพหุ นาม การเรียงสับเปลี่ยนชนิดพิเศษบนฟิลด์จำกัดGF( q )

ปัญหาการทดสอบว่าพหุนามที่กำหนดเหนือฟิลด์จำกัดเป็นพหุนามการเรียงสับเปลี่ยนหรือไม่ สามารถแก้ไขได้ในเวลาพหุนาม^{[ 19 ]}

พหุนามคือพหุนามการเรียงสับเปลี่ยนในตัวแปรn ตัวเหนือ ถ้าสมการมีคำตอบที่แน่นอนในสำหรับแต่ละ^{[ 20 ]}${\displaystyle f\in \mathbb {F} _{q}[x_{1},\ldots ,x_{n}]}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle f(x_{1},\ldots ,x_{n})=\alpha }$${\displaystyle q^{n-1}}$${\displaystyle \mathbb {F} _{q}^{n}}$${\displaystyle \alpha \in \mathbb {F} _{q}}$

สำหรับวงแหวนจำกัดZ / n Zสามารถสร้างพหุนามการเรียงสับเปลี่ยนกำลังสองได้ อันที่จริงแล้วเป็นไปได้ก็ต่อเมื่อnหารลงตัวด้วยp ²สำหรับจำนวนเฉพาะp บางตัว การสร้างนั้นเรียบง่ายอย่างน่าประหลาดใจ ถึงกระนั้นก็สามารถสร้างการเรียงสับเปลี่ยนที่มีคุณสมบัติที่ดีบางประการได้ นั่นเป็นเหตุผลที่มันถูกนำไปใช้ใน ส่วนประกอบ ตัวสลับของรหัสเทอร์โบใน มาตรฐานการสื่อสารเคลื่อนที่ 3GPP Long Term Evolution (ดูข้อกำหนดทางเทคนิค 3GPP 36.212 ^{[ 21 ]}เช่น หน้า 14 ในเวอร์ชัน 8.8.0)

พิจารณาวงแหวนZ /4 Zจะเห็นได้ว่า: ; ; ; ดังนั้น พหุนามจึงกำหนดการเรียงสับเปลี่ยน ${\displaystyle g(x)=2x^{2}+x}$${\displaystyle g(0)=0}$${\displaystyle g(1)=3}$${\displaystyle g(2)=2}$${\displaystyle g(3)=1}$$${\displaystyle {\begin{pmatrix}0&1&2&3\\0&3&2&1\end{pmatrix}}.}$$

พิจารณาพหุนามเดียวกันสำหรับวงแหวนอีกวงหนึ่งZ / 8 Zจะเห็นได้ว่า: ; ; ; ; ; ; ; ดังนั้นพหุนามจึงกำหนดการเรียงสับเปลี่ยน ${\displaystyle g(x)=2x^{2}+x}$${\displaystyle g(0)=0}$${\displaystyle g(1)=3}$${\displaystyle g(2)=2}$${\displaystyle g(3)=5}$${\displaystyle g(4)=4}$${\displaystyle g(5)=7}$${\displaystyle g(6)=6}$${\displaystyle g(7)=1}$$${\displaystyle {\begin{pmatrix}0&1&2&3&4&5&6&7\\0&3&2&5&4&7&6&1\end{pmatrix}}.}$$

พิจารณาวงแหวนZ / p ^k Z​ ${\displaystyle g(x)=ax^{2}+bx+c}$

บทตั้ง:สำหรับk = 1 (นั่นคือZ / p Z ) พหุนามดังกล่าวจะกำหนดการเรียงสับเปลี่ยนได้เฉพาะในกรณีที่a = 0 และbไม่เท่ากับศูนย์เท่านั้น ดังนั้นพหุนามนี้จึงไม่ใช่พหุนามกำลังสอง แต่เป็นพหุนามเชิงเส้น

บทตั้ง:สำหรับk > 1, p > 2 ( Z / p ^k Z ) พหุนามดังกล่าวจะกำหนดการเรียงสับเปลี่ยนก็ต่อเมื่อ และ${\displaystyle a\equiv 0{\pmod {p}}}$${\displaystyle b\not \equiv 0{\pmod {p}}}$

พิจารณาโดยที่p และ_tเป็นจำนวนเฉพาะ ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{l}^{k_{l}}}$

บทตั้ง: พหุนามใดๆกำหนดการเรียงสับเปลี่ยนสำหรับวงแหวนZ / n Zก็ต่อเมื่อพหุนามทั้งหมดกำหนดการเรียงสับเปลี่ยนสำหรับวงแหวนทั้งหมดโดยที่เป็นเศษเหลือของโมดูลัส ${\textstyle g(x)=a_{0}+\sum _{0<i\leq M}a_{i}x^{i}}$${\textstyle g_{p_{t}}(x)=a_{0,p_{t}}+\sum _{0<i\leq M}a_{i,p_{t}}x^{i}}$${\displaystyle Z/p_{t}^{k_{t}}Z}$${\displaystyle a_{j,p_{t}}}$${\displaystyle a_{j}}$${\displaystyle p_{t}^{k_{t}}}$

ผลที่ตามมาคือ เราสามารถสร้างพหุนามการเรียงสับเปลี่ยนกำลังสองได้มากมายโดยใช้การสร้างแบบง่ายๆ ดังต่อไปนี้ พิจารณา โดยสมมติว่าk ₁ >1 ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\dots p_{l}^{k_{l}}}$

พิจารณาพหุนาม โดยที่แต่; สมมติว่าi > 1 และสมมติว่าสำหรับทุกi = 1, ..., l (ตัวอย่างเช่น สามารถเลือกและ ได้) จากนั้นพหุนามดังกล่าวจะกำหนดการเรียงสับเปลี่ยน ${\displaystyle ax^{2}+bx}$${\displaystyle a=0{\bmod {p}}_{1}}$${\displaystyle a\neq 0{\bmod {p}}_{1}^{k_{1}}}$${\displaystyle a=0{\bmod {p}}_{i}^{k_{i}}}$${\displaystyle b\neq 0{\bmod {p}}_{i}}$${\displaystyle a=p_{1}p_{2}^{k_{2}}...p_{l}^{k_{l}}}$${\displaystyle b=1}$

เพื่อให้เห็นเช่นนี้ เราสังเกตว่าสำหรับจำนวนเฉพาะp _i , i > 1 ทั้งหมด การลดรูปของพหุนามกำลังสองนี้มอดูลp _i นั้นแท้จริงแล้วเป็นพหุนามเชิงเส้น และด้วยเหตุนี้จึงเป็นการเรียงสับเปลี่ยนด้วยเหตุผลที่ชัดเจน สำหรับ จำนวนเฉพาะตัวแรกเราควรใช้บทพิสูจน์ย่อยที่กล่าวถึงก่อนหน้านี้เพื่อดูว่ามันกำหนดการเรียงสับเปลี่ยนนั้น

ตัวอย่างเช่น พิจารณาZ /12 Zและพหุนามซึ่งกำหนดการเรียงสับเปลี่ยน ${\displaystyle 6x^{2}+x}$${\begin{pmatrix}0&1&2&3&4&5&6&7&8&\cdots \\0&7&2&9&4&11&6&1&8&\cdots \end{pmatrix}}.$

พหุนามg ( x ) สำหรับวงแหวนZ / pkZ เป็นพหุนามการ เรียงสับเปลี่ยนก็ต่อเมื่อมันเรียงสับเปลี่ยน^{ฟิลด์จำกัด} Z / pZ และสำหรับxทั้งหมดในZ / pkZโดยที่g ′( x ) คืออนุพันธ์อย่างเป็น^{ทางการ}ของg ( x ) ^{[ 22} ]${\displaystyle g'(x)\neq 0{\bmod {p}}}$

ให้Kเป็นฟิลด์จำนวนพีชคณิตโดยที่Rเป็นวงแหวนของจำนวนเต็มคำว่า "ข้อสันนิษฐานของชูร์" หมายถึงการยืนยันว่า ถ้าพหุนามfที่กำหนดบนKเป็นพหุนามการเรียงสับเปลี่ยนบนR / Pสำหรับอุดมคติ เฉพาะ P จำนวนอนันต์ แล้วfจะเป็นการประกอบกันของพหุนามดิกสัน พหุนามดีกรีหนึ่ง และพหุนามในรูปแบบx ^kอันที่จริงชูร์ไม่ได้ตั้งข้อสันนิษฐานในทิศทางนี้ ความคิดที่ว่าเขาทำเช่นนั้นมาจากฟรีด^{[ 23 ]}ซึ่งให้การพิสูจน์ที่ผิดพลาดของผลลัพธ์เวอร์ชันที่ผิด การพิสูจน์ที่ถูกต้องได้รับการให้โดยเทิร์นวาลด์^{[ 24 ]}และมุลเลอร์^{[ 25 ]}