Permutační polynom - Permutation polynomial

v matematika, a permutační polynom (pro daný prsten ) je polynomiální který funguje jako permutace prvků prstenu, tj. mapy ${ displaystyle x mapsto g (x)}$ je bijekce. V případě, že prsten je a konečné pole, Dicksonovy polynomy, které úzce souvisí s Čebyševovy polynomy, uveďte příklady. Přes konečné pole lze každou funkci, zejména pak každou permutaci prvků tohoto pole, zapsat jako polynomiální funkci.

V případě konečných kruhů Z/nZ, tyto polynomy byly také studovány a použity v prokládač součást detekce a oprava chyb algoritmy.^[1][2]

Jednotlivé proměnné permutační polynomy nad konečnými poli

Nechat F_q = GF (q) být konečné pole charakteristický str, to znamená, že pole má q prvky kde q = str^E pro některé prime str. Polynom F s koeficienty v F_q (symbolicky psáno jako F ∈ F_q[X]) je permutační polynom z F_q pokud je funkce z F_q sama o sobě definována ${ displaystyle c mapsto f (c)}$ je obměna F_q.^[3]

Vzhledem k konečnosti F_q, tuto definici lze vyjádřit několika ekvivalentními způsoby:^[4]

• funkce ${ displaystyle c mapsto f (c)}$ je na (surjektivní );
• funkce ${ displaystyle c mapsto f (c)}$ je jedna ku jedné (injekční );
• F(X) = A má řešení v F_q pro každého A v F_q;
• F(X) = A má unikátní řešení v F_q pro každého A v F_q.

Charakterizace polynomů, které jsou permutačními polynomy, je dána vztahem

(Poustevník Kritérium)^[5][6] F ∈ F_q[X] je permutační polynom o F_q pouze tehdy, pokud platí následující dvě podmínky:

1. F má právě jeden kořen F_q;
2. pro každé celé číslo t s 1 ≤ t ≤ q − 2 a ${ displaystyle t not equiv 0 ! { pmod {p}}}$, snížení o F(X)^t mod (X^q − X) má titul ≤ q − 2.

Li F(X) je permutační polynom definovaný přes konečné pole GF (q), pak také je G(X) = A F(X + b) + C pro všechny A ≠ 0, b a C v GF (q). Permutační polynom G(X) je v normalizovaná forma -li A, b a C jsou vybrány tak, aby G(X) je monic, G(0) = 0 a (za předpokladu charakteristiky str nerozděluje stupeň n polynomu) koeficient X^n-1 je 0.

Existuje mnoho otevřených otázek týkajících se permutačních polynomů definovaných přes konečná pole (viz Lidl & Mullen (1988) a Lidl & Mullen (1993) ).

Malý stupeň

Hermitovo kritérium je výpočetně náročné a může být obtížné ho použít při vytváření teoretických závěrů. Nicméně, Dicksone byl schopen ji použít k nalezení všech permutačních polynomů stupně nejvýše pěti přes všechna konečná pole. Tyto výsledky jsou:^[7][6]

Normalizovaný permutační polynom z Fq	q
${ displaystyle x}$	žádný ${ 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}$ ne čtverec)	${ displaystyle q equiv 0 ! { pmod {3}}}$
${ displaystyle x ^ {4} pm 3x}$	${ displaystyle q = 7}$
${ displaystyle x ^ {4} + a_ {1} x ^ {2} + a_ {2} x}$ (pokud je to jediný kořen v Fq je 0)	${ displaystyle q equiv 0 ! { pmod {2}}}$
${ displaystyle x ^ {5}}$	${ displaystyle q not equiv 1 ! { pmod {5}}}$
${ displaystyle x ^ {5} -ax}$ (${ displaystyle a}$ ne čtvrtá síla)	${ displaystyle q equiv 0 ! { pmod {5}}}$
${ displaystyle x ^ {5} + sekera , (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}$ ne čtverec)	${ displaystyle q = 7}$
${ displaystyle x ^ {5} + ax ^ {3} +5 ^ {- 1} a ^ {2} x}$ (${ displaystyle a}$ libovolný)	${ displaystyle q equiv pm 2 ! { pmod {5}}}$
${ displaystyle x ^ {5} + sekera ^ {3} + 3a ^ {2} x}$ (${ displaystyle a}$ ne čtverec)	${ displaystyle q = 13}$
${ displaystyle x ^ {5} -2ax ^ {3} + a ^ {2} x}$ (${ displaystyle a}$ ne čtverec)	${ displaystyle q equiv 0 ! { pmod {5}}}$

Seznam všech monických permutačních polynomů stupně šest v normalizované formě najdete v Shallue & Wanless (2013).^[8]

Některé třídy permutačních polynomů

Kromě výše uvedených příkladů obsahuje následující seznam, i když není vyčerpávající, téměř všechny známé hlavní třídy permutačních polynomů nad konečnými poli.^[9]

• Xⁿ permutuje GF (q) kdyby a jen kdyby n a q − 1 jsou coprime (notačně, (n, q − 1) = 1).^[10]
• Li A je v GF (q) a n ≥ 1 pak Dicksonův polynom (prvního druhu) D_n(X,A) je definováno

${ displaystyle D_ {n} (x, a) = součet _ {j = 0} ^ { lfloor n / 2 rfloor} { frac {n} {nj}} { binom {nj} {j} } (- a) ^ {j} x ^ {n-2j}.}$

Ty lze také získat z rekurze

${ displaystyle D_ {n} (x, a) = xD_ {n-1} (x, a) -aD_ {n-2} (x, a),}$

s původními podmínkami ${ displaystyle D_ {0} (x, a) = 2}$ a ${ displaystyle D_ {1} (x, a) = x}$Prvních několik Dicksonových polynomů je:

${ 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.}$

Li A ≠ 0 a n > 1 pak D_n(X, A) permutuje GF (q) právě tehdy (n, q² − 1) = 1.^[11] Li A = 0 pak D_n(X, 0) = Xⁿ a předchozí výsledek platí.

• Li GF (q^r) je rozšíření z GF (q) stupně r, pak linearizovaný polynom

${ displaystyle L (x) = Sigma _ {s = 0} ^ {r-1} alpha _ {s} x ^ {q ^ {s}},}$

s α_s v GF (q^r), je lineární operátor na GF (q^r) přes GF (q). Linearizovaný polynom L(X) permutuje GF (q^r) právě když je 0 jediným kořenem L(X) v GF (q^r).^[10] Tuto podmínku lze vyjádřit algebraicky jako^[12]

${ displaystyle { rm {{det} left ( alpha _ {ij} ^ {q ^ {j}} right) neq 0 quad (i, j = 0,1, ldots, r-1 ).}}}$

Linearizované polynomy, které jsou permutačními polynomy GF (q^r) tvoří a skupina za provozu složení modulo ${ displaystyle x ^ {q ^ {r}} - x}$, která je známá jako skupina Betti-Mathieu, je izomorfní s obecná lineární skupina GL (r, F_q).^[12]

• Li G(X) je v polynomiálním kruhu F_q[X] a G(X^s) nemá v kořenovém adresáři nenulový kořen GF (q) když s rozděluje q − 1, a r > 1 je relativně prime (coprime) na q − 1, pak X^r(G(X^s))^{(q - 1)/s} permutuje GF (q).^[6]
• Pouze několik dalších specifických tříd permutačních polynomů GF (q) byly charakterizovány. Dva z nich jsou například:

${ displaystyle x ^ {(q + m-1) / m} + sekera}$

kde m rozděluje q − 1, a

${ displaystyle x ^ {r} (x ^ {d} -a) ^ {(p ^ {n} -1) / d}}$

kde d rozděluje strⁿ − 1.

Výjimečné polynomy

An výjimečný polynom přes GF (q) je polynom v F_q[X] což je permutační polynom na GF (q^m) pro nekonečně mnoho m.^[13]

Permutační polynom nad GF (q) stupně nanejvýš q^1/4 je výjimečný GF (q).^[14]

Každá obměna GF (q) je indukován výjimečným polynomem.^[14]

Pokud je polynom s celočíselnými koeficienty (tj. V ℤ [X]) je permutační polynom nad GF (str) na nekonečně mnoho prvočísel str, pak jde o složení lineárních a Dicksonových polynomů.^[15] (Viz Shurova domněnka níže).

Geometrické příklady

v konečná geometrie popisy souřadnic určitých množin bodů mohou poskytnout příklady permutačních polynomů vyššího stupně. Zejména body tvořící ovál v konečném projektivní rovina, PG (2,q) s q mocninu 2 lze koordinovat takovým způsobem, že vztah mezi souřadnicemi je dán vztahem o-polynom, což je speciální typ permutačního polynomu nad konečným polem GF (q).

Výpočetní složitost

Problém testování, zda je daný polynom nad konečným polem permutační polynom, lze vyřešit v polynomiální čas.^[16]

Permutační polynomy v několika proměnných nad konečnými poli

Polynom ${ displaystyle f in mathbb {F} _ {q} [x_ {1}, ldots, x_ {n}]}$ je permutační polynom v n proměnné přes ${ displaystyle mathbb {F} _ {q}}$ pokud rovnice ${ displaystyle f (x_ {1}, ldots, x_ {n}) = alpha}$ má přesně ${ displaystyle q ^ {n-1}}$ řešení v ${ displaystyle mathbb {F} _ {q} ^ {n}}$ pro každého ${ displaystyle alpha in mathbb {F} _ {q}}$.^[17]

Kvadratické permutační polynomy (QPP) na konečných prstencích

Pro konečný prsten Z/nZ lze sestrojit kvadratické permutační polynomy. Ve skutečnosti je to možné právě tehdy n je dělitelné str² pro nějaké prvočíslo str. Konstrukce je překvapivě jednoduchá, přesto může vytvářet permutace s určitými dobrými vlastnostmi. Proto byl použit v prokládač součást turbo kódy v 3GPP Dlouhodobý vývoj mobilní telekomunikační standard (viz technická specifikace 3GPP 36.212 ^[18] např. strana 14 ve verzi 8.8.0).

Jednoduché příklady

Zvážit ${ displaystyle g (x) = 2x ^ {2} + x}$ pro prsten Z/4ZJeden vidí: ${ displaystyle g (0) = 0; ~ g (1) = 3; ~ g (2) = 2; ~ g (3) = 1}$, takže polynom definuje permutaci

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

Zvažte stejný polynom ${ displaystyle g (x) = 2x ^ {2} + x}$ pro druhý prsten Z/8ZJeden vidí: ${ Displaystyle g (0) = 0; ~ g (1) = 3; ~ g (2) = 2; ~ g (3) = 5; ~ g (4) = 4; ~ g (5) = 7; ~ g (6) = 6; ~ g (7) = 1;}$, takže polynom definuje permutaci

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

Prsteny Z /str^kZ

Zvážit ${ displaystyle g (x) = sekera ^ {2} + bx + c}$ pro prsten Z/str^kZ.

Lemma: pro k = 1 (tj. Z/strZ) takový polynom definuje permutaci pouze v případě a = 0 a b nerovná se nule. Polynom tedy není kvadratický, ale lineární.

Lemma: pro k> 1, p> 2 (Z/str^kZ) takový polynom definuje permutaci právě tehdy ${ displaystyle a equiv 0 { pmod {p}}}$ a ${ displaystyle b not equiv 0 { pmod {p}}}$.

Prsteny Z /nZ

Zvážit ${ displaystyle n = p_ {1} ^ {k_ {1}} p_ {2} ^ {k_ {2}} ... p_ {l} ^ {k_ {l}}}$, kde str_t jsou prvočísla.

Lema: jakýkoli polynom ${ displaystyle g (x) = a_ {0} + součet _ {0$definuje permutaci pro prsten Z/nZ právě když všechny polynomy ${ displaystyle g_ {p_ {t}} (x) = a_ {0, p_ {t}} + součet _ {0$ definuje permutace pro všechny prsteny ${ displaystyle Z / p_ {t} ^ {k_ {t}} Z}$, kde ${ displaystyle a_ {j, p_ {t}}}$ jsou zbytky ${ displaystyle a_ {j}}$modulo ${ displaystyle p_ {t} ^ {k_ {t}}}$.

Jako důsledek lze sestrojit mnoho kvadratických permutačních polynomů pomocí následující jednoduché konstrukce. Zvážit ${ displaystyle n = p_ {1} ^ {k_ {1}} p_ {2} ^ {k_ {2}} ... p_ {l} ^ {k_ {l}}}$, předpokládat, že k₁ >1.

Zvážit ${ displaystyle ax ^ {2} + bx}$, takový, že ${ displaystyle a = 0 ~ mod ~ p_ {1}}$, ale ${ displaystyle a neq 0 ~ mod ~ p_ {1} ^ {k_ {1}}}$; předpokládat, že ${ displaystyle a = 0 ~ mod ~ p_ {i} ^ {k_ {i}}}$,i> 1. A předpokládejme to ${ displaystyle b neq 0 ~ mod ~ p_ {i}}$ pro všechny i=1...l(Například lze vzít ${ displaystyle a = p_ {1} p_ {2} ^ {k_ {2}} ... p_ {l} ^ {k_ {l}}}$a ${ displaystyle b = 1}$Pak takový polynom definuje permutaci.

Abychom to viděli, pozorujeme to pro všechna prvočísla str_i,i> 1, redukce tohoto kvadratického polynomiálního modula str_i je ve skutečnosti lineární polynom, a proto je permutace triviálním důvodem. Pro první prvočíslo bychom měli použít výše diskutované lemma, abychom zjistili, že definuje permutaci.

Zvažte například Z/12Z a polynomiální ${ displaystyle 6x ^ {2} + x}$Definuje permutaci

${ displaystyle { begin {pmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & ... 0 & 7 & 2 & 9 & 4 & 11 & 6 & 1 & 8 & ... end {pmatrix}}}$.

Polynomy vyššího stupně nad konečnými prstenci

Polynom G(X) pro prsten Z/str^kZ je permutační polynom právě tehdy, pokud permutuje konečné pole Z/strZ a ${ displaystyle g '(x) neq 0 ~ mod ~ p}$ pro všechny X v Z/str^kZ, kde G′(X) je formální derivát z G(X).^[19]

Schurova domněnka

Nechat K. být algebraické číslo pole s R the kruh celých čísel. Termín „Schurova domněnka“ se vztahuje k tvrzení, že pokud jde o polynom F definováno přes K. je permutační polynom na R/P pro nekonečně mnoho hlavní ideály P, pak F je složení Dicksonových polynomů, polynomů prvního stupně a polynomů formy X^k. Ve skutečnosti, Schur nevytvořil v tomto směru žádné domněnky. Představa, kterou udělal, je způsobena Friedem,^[20] který poskytl chybný důkaz o falešné verzi výsledku. Turnwald podal správné důkazy ^[21]a Müller.^[22]

Poznámky

Reference

• Dickson, L. E. (1958) [1901]. Lineární skupiny s výkladem teorie pole Galois. New York: Dover.CS1 maint: ref = harv (odkaz)
• Lidl, Rudolf; Mullen, Gary L. (březen 1988). "Kdy polynom nad konečným polem dovoluje prvky pole?". Americký matematický měsíčník. 95 (3): 243–246. doi:10.2307/2323626.CS1 maint: ref = harv (odkaz)
• Lidl, Rudolf; Mullen, Gary L. (leden 1993). „Kdy polynom nad konečným polem dovoluje prvky pole ?, II“. Americký matematický měsíčník. 100 (1): 71–74. doi:10.2307/2324822.CS1 maint: ref = harv (odkaz)
• Lidl, Rudolf; Niederreiter, Harald (1997). Konečná pole. Encyklopedie matematiky a její aplikace. 20 (2. vyd.). Cambridge University Press. ISBN  0-521-39231-4. Zbl  0866.11069.CS1 maint: ref = harv (odkaz) Kapitola 7.
• Mullen, Gary L .; Panario, Daniel (2013). Příručka konečných polí. CRC Press. ISBN  978-1-4398-7378-6.CS1 maint: ref = harv (odkaz) Kapitola 8.
• Shallue, C.J .; Wanless, I.M. (březen 2013). „Permutační polynomy a polynomy ortomorfismu stupně šest“. Konečná pole a jejich aplikace. 20: 84–92. doi:10.1016 / j.ffa.2012.12.003.CS1 maint: ref = harv (odkaz)