Wielomian permutacyjny

W matematyce wielomian permutacyjny ( $który$ danego pierścienia ) jest , jako permutacja pierścienia, tj. bijekcją . W przypadku gdy pierścień jest ciałem skończonym , wielomiany Dicksona , które są blisko spokrewnione z wielomianami Czebyszewa , podaj przykłady. W ciele skończonym każdą funkcję, a w szczególności każdą permutację elementów tego ciała, można zapisać jako funkcję wielomianową.

W przypadku pierścieni skończonych Z / n Z , takie wielomiany były również badane i stosowane w składniku przeplotu algorytmów wykrywania i korekcji błędów .

Wielomiany permutacyjne pojedynczej zmiennej na ciałach skończonych

Niech F _q = GF( q ) będzie ciałem skończonym o charakterystyce p , czyli ciałem mającym q elementów, gdzie q = p ^e dla pewnej liczby pierwszej p . Wielomian f ze współczynnikami w F _q (symbolicznie zapisany jako f ∈ F _q [ x ] ) jest wielomianem permutacyjnym F _q , jeśli funkcja z fa _q $_$ sobie przez fa q _{_}

Ze względu na skończoność F _q definicję tę można wyrazić na kilka równoważnych sposobów:

• funkcja jest na ( surjective $) {\ Displaystyle c \ mapsto f ($ do
• funkcja jest ${\ Displaystyle c \ mapsto f (c)$ do jednego ( iniekcyjny ) do
• f ( x ) = a ma rozwiązanie w F _q dla każdego a w F _q ;
• f ( x ) = a ma unikalne rozwiązanie w F _q dla każdego a w F _q .

Charakterystykę, które wielomiany są wielomianami permutacyjnymi, podaje wzór

( Kryterium Hermite'a ) f ∈ F q _[ x ] jest wielomianem permutacyjnym F _q wtedy i tylko wtedy, gdy spełnione są następujące dwa warunki:

1. f ma dokładnie jeden pierwiastek w F _q ;
2. dla każdej liczby całkowitej t z 1 ≤ t ≤ q - 2 i ${\ Displaystyle t \ nie \ równoważnik 0 \! {\ pmod {p}}}$ , redukcja fa ( x ) ^t mod ( x ^q - x ) ma stopień ≤ q - 2 .

Jeśli f ( x ) jest wielomianem permutacyjnym zdefiniowanym w ciele skończonym GF( q ) , to także g ( x ) = a f ( x + b ) + c dla wszystkich a ≠ 0, b i c w GF ( q ) . Wielomian permutacyjny g ( x ) ma postać znormalizowaną, jeśli a , b i c są tak dobrane, że g ( x ) jest moniczne , g (0) = 0 i (pod warunkiem, że charakterystyka p nie dzieli stopnia n wielomianu) współczynnik x ^{n −1} wynosi 0.

Istnieje wiele otwartych pytań dotyczących wielomianów permutacyjnych zdefiniowanych na ciałach skończonych.

Mały stopień

Kryterium Hermite'a wymaga intensywnych obliczeń i może być trudne w użyciu przy wyciąganiu wniosków teoretycznych. Jednak Dickson był w stanie użyć go do znalezienia wszystkich wielomianów permutacyjnych stopnia co najwyżej piątego we wszystkich skończonych ciałach. Te wyniki to:

Znormalizowany wielomian permutacyjny F q	Q
${\ displaystyle x}$	dowolny ${\ displaystyle q}$
${\ displaystyle x ^ {2}}$	${\ Displaystyle q \ równoważnik 0 \! {\ pmod {2}}}$
${\ displaystyle x ^ {3}}$	${\ Displaystyle q \ nie \ równoważnik 1 \! {\ pmod {3}}}$
${\ Displaystyle x ^ {3} -ax}$ ( ${\ Displaystyle a}$ nie kwadrat)	${\ Displaystyle q \ równoważnik 0 \! {\ pmod {3}}}$
${\ displaystyle x ^ {4} \ pm 3x}$	${\ displaystyle q = 7}$
${\ Displaystyle x ^ {4} + a_ {1} x ^ {2} + a_ {2} x}$ (jeśli jego jedyny pierwiastek w F q wynosi 0)	${\ Displaystyle q \ równoważnik 0 \! {\ pmod {2}}}$
${\ displaystyle x ^ {5}}$	${\ Displaystyle q \ nie \ równoważnik 1 \! {\ pmod {5}}}$
${\ Displaystyle x ^ {5} -ax}$ ( ${\ Displaystyle a}$ nie czwarta potęga)	${\ Displaystyle q \ równoważnik 0 \! {\ pmod {5}}}$
${\ Displaystyle x ^ {5} + topór \ (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}$ nie kwadrat)	${\ displaystyle q = 7}$
${\ Displaystyle x ^ {5} + ax ^ {3} + 5 ^ {- 1} a ^ {2} x}$ ( ${\ Displaystyle a}$ arbitralnie)	${\ Displaystyle q \ równoważnik \ pm 2 \! {\ pmod {5}}}$
${\ Displaystyle x ^ {5} + ax ^ {3} + 3a ^ {2} x}$ ( ${\ Displaystyle a}$ nie kwadrat)	${\ displaystyle q = 13}$
${\ Displaystyle x ^ {5} -2ax ^ {3} + a ^ {2} x}$ ( ${\ Displaystyle a}$ nie kwadrat)	${\ Displaystyle q \ równoważnik 0 \! {\ pmod {5}}}$

Listę wszystkich monicznych wielomianów permutacyjnych stopnia szóstego w postaci znormalizowanej można znaleźć w Shallue & Wanless (2013) .

Niektóre klasy wielomianów permutacyjnych

Poza powyższymi przykładami poniższa lista, choć nie jest wyczerpująca, zawiera prawie wszystkie znane główne klasy wielomianów permutacyjnych na ciałach skończonych.

• x ⁿ permutuje GF( q ) wtedy i tylko wtedy, gdy n i q − 1 są względnie pierwsze (notacyjnie, ( n , q − 1) = 1 ).
• Jeśli a jest w GF( q ) i n ≥ 1 , to wielomian Dicksona (pierwszego rodzaju) D _n ( x , a ) jest zdefiniowany przez
  $${\ Displaystyle D_ {n} (x, a) = \ suma _ {j = 0} ^ {\ lfloor n/2 \ rfloor} {\ Frac {n} {nj}} {\ binom {nj} {j}} (-a) ^ {j} x ^ {n-2j}.}$$

Można je również uzyskać z rekurencji

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

z warunkami początkowymi $\ Displaystyle D_ {1}$ re $=$ . Kilka pierwszych wielomianów Dicksona to:

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

Jeśli a ≠ 0 i n > 1 wtedy D _n ( x , a ) permutuje GF( q ) wtedy i tylko wtedy, gdy ( n , q ² − 1) = 1 . Jeśli a = 0 , to D _n ( x , 0) = x ⁿ i poprzedni wynik jest zachowany.

• Jeśli GF( q ^r ) jest rozszerzeniem GF ( q ) stopnia r , to zlinearyzowany wielomian
  $${\ Displaystyle L (x) = \ suma _ {s = 0} ^ {r-1} \ alfa _ {s} x ^ {q ^ {s}}}$$
  gdzie α _s w GF( q ^r ) , jest operatorem liniowym na GF ( q ^r ) nad GF ( q ) . Zlinearyzowany wielomian L ( x ) permutuje GF( qr ^{) wtedy i tylko wtedy,} gdy if and only if 0 is the only root of L(x) in GF(q^r). This condition can be expressed algebraically as
  $${\ Displaystyle \ det \ lewo (\ alfa _ {ij} ^ {q ^ {j}} \ prawej) \ neq 0 \ quad (i, j = 0,1, \ ldots, r-1).}$$

Zlinearyzowane wielomiany, które są wielomianami permutacyjnymi nad $GF$ r ) ^tworzą grupę działającą na kompozycji modulo znana jako Betti- Grupa Mathieu, izomorficzna z ogólną grupą liniową GL( r , F _q ) .

• Jeśli g ( x ) jest w pierścieniu wielomianowym F _q [ x ] i g ( x ^s ) nie ma pierwiastka niezerowego w GF ( q ) , gdy s dzieli q − 1 , a r > 1 jest względnie pierwsze (względnie pierwsze) z q − 1 , to x ^r ( g ( x ^s )) ^{( q - 1)/ s} permutuje GF( q ) .
• Scharakteryzowano tylko kilka innych specyficznych klas wielomianów permutacyjnych nad GF( q ) . Dwa z nich to na przykład:
  $${\ Displaystyle x ^ {(q + m-1) / m} + topór}$$
  gdzie m dzieli q - 1 , i
  $${\ Displaystyle x ^ {r} \ lewo (x ^ {d} -a \ prawo) ^ {\ lewo (p ^ {n} -1 \ prawo) / d}}$$
  gdzie d dzieli p ⁿ - 1 .

Wyjątkowe wielomiany

Wyjątkowy wielomian nad GF( q ) to wielomian w F _q [ x ] , który jest wielomianem permutacyjnym na GF ( q ^m ) dla nieskończenie wielu m .

Wielomian permutacyjny na GF( q ) stopnia co najwyżej q ^1/4 jest wyjątkowy na GF( q ) .

Każda permutacja GF( q ) jest indukowana przez wyjątkowy wielomian.

Jeśli wielomian o współczynnikach całkowitych (tj. w ℤ[ x ] ) jest wielomianem permutacyjnym nad GF( p ) dla nieskończenie wielu liczb pierwszych p , to jest to złożenie wielomianów liniowych i wielomianów Dicksona. (Patrz przypuszczenie Schura poniżej).

Przykłady geometryczne

Główny artykuł: Owal (płaszczyzna rzutowa)

W geometrii skończonej opisy współrzędnych pewnych zbiorów punktów mogą dostarczać przykładów wielomianów permutacyjnych wyższego stopnia. W szczególności punkty tworzące owal na skończonej płaszczyźnie rzutowej PG(2, q ) z q potęgą 2, mogą być skoordynowane w taki sposób, że związek między współrzędnymi jest określony przez o- wielomian , który jest specjalnym rodzajem wielomianu permutacyjnego nad polem skończonym GF( q ) .

Złożoność obliczeniowa

Problem sprawdzenia, czy dany wielomian nad polem skończonym jest wielomianem permutacyjnym, można rozwiązać w czasie wielomianowym .

Wielomiany permutacyjne w kilku zmiennych nad ciałami skończonymi

wielomian ${\ Displaystyle f \ in \ mathbb {F} _ {q} [x_ {1}, \ ldots, x_ {n}]} jest wielomianem permutacyjnym w n zmiennych nad fa q {\ Displaystyle \ mathbb {F} _ {q}} jeśli równanie fa ( x 1 , … , x n ) = α {\$ dis styl gry f ${1}$ , $ma$ dokładnie ${\ Displaystyle q ^ {n-1}}$ rozwiązania w ${\ Displaystyle \ mathbb {F} _ {q} ^ {n}}$ dla każdego ${\ Displaystyle \ alfa \ w \ mathbb {F} _ {q}}$ .

Kwadratowe wielomiany permutacyjne (QPP) na skończonych pierścieniach

Dla skończonego pierścienia Z / n Z można skonstruować kwadratowe wielomiany permutacyjne. Właściwie jest to możliwe wtedy i tylko wtedy, gdy n jest podzielne przez p ² dla pewnej liczby pierwszej p . Konstrukcja jest zaskakująco prosta, niemniej jednak może tworzyć permutacje o pewnych dobrych właściwościach. Dlatego został użyty w komponencie przeplotu kodów turbo w 3GPP Long Term Evolution standard telefonii komórkowej (patrz specyfikacja techniczna 3GPP 36.212 np. strona 14 w wersji 8.8.0).

Proste przykłady

Rozważ ${\ Displaystyle g (x) = 2x ^ {2} + x}$ dla pierścienia Z / 4 Z . Widzi się: sol $\ displaystyle g (0) = 0}$ ; ${\ Displaystyle g (1) = 3}$ ; ${\ Displaystyle g (2) = 2}$ ; ${\ Displaystyle g (3) = 1}$ , więc wielomian definiuje permutację

$${\ Displaystyle {\ początek {pmatrix} 0 i 1 i 2 i 3 \\ 0 i 3 i 2 i 1 \ koniec {pmatrix}}.}$$

Rozważmy ten sam wielomian dla drugiego pierścienia Z / 8 Z ${\ Displaystyle g (x) = 2x ^ {2} + x}$ . Widzi się: sol $\ 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}$ , więc wielomian definiuje permutację

$${\ Displaystyle {\ początek {pmatrix} 0&1&2&3&4&5&6&7\\0&3&2&5&4&7&6&1\koniec {pmatrix}}.}$$

Pierścienie Z/ p ^k Z

Rozważ ${\ Displaystyle g (x) = ax ^ {2} + bx + c}$ dla pierścienia Z / p ^k Z .

Lemat: dla k =1 (tj. Z / p Z ) taki wielomian definiuje permutację tylko w przypadku, gdy a =0 i b nie są równe zeru. Więc wielomian nie jest kwadratowy, ale liniowy.

Lemat: dla k > 1, p > 2 ( Z / p ^k Z ) taki wielomian definiuje permutację wtedy i tylko wtedy, gdy za ≡ $\ Displaystyle a \ równoważnik 0 {\ pmod {p}}}$ i ${\ Displaystyle b \ nie \ równoważnik 0 {\ pmod {p}}}$

Pierścienie Z/ n Z

Rozważmy $_$ p _t . _

Lemat: dowolny wielomian $) = a_ {0} + \ suma _ {0 <i \ równoważnik M} a_ {i} x ^ {i}} definiuje permutację dla pierścienia Z / n Z wtedy i$ tylko wtedy , gdy wszystkie wielomiany ${\ textstyle g_ {p_ {t}} (x) = a_ {0, p_ {t}} + \ suma _ {0 <i \ równoważnik M} a_ {i, p_ {t}} x ^ {i}}$ definiuje permutacje dla wszystkich pierścieni ${\ Displaystyle Z/p_ {t} ^ {k_ {t}} Z}$ , gdzie ${\ Displaystyle a_ {j , p_ {t}}}$ są pozostałościami za ${\ displaystyle a_ {j}}$ modulo $displaystyle p_ {t} ^ {k_ {t}}}$ .

Jako wniosek można skonstruować wiele kwadratowych wielomianów permutacyjnych przy użyciu następującej prostej konstrukcji. Załóżmy, ${2} ^ {k_ {2}} \ kropki p_ {l} ^ {k_ {l}}}$ p_ k ₁ > 1.

Za ${\ Displaystyle ax ^ {2} + bx}$ tak, że $\ Displaystyle a = 0 {\ bmod {p}} _ {1}}$ , ale ${\ Displaystyle a \ neq 0 {\ bmod {p}} _ {1} ^ {k_ {1}}}$ ; za ${i} ^ {k_ {i}}}$ , ja > 1. I załóżmy, że ${\ Displaystyle b \ neq 0 {\ bmod {p}} _ {i}}$ dla wszystkich ja = 1, ..., l . (Na przykład można wziąć ${k_ {2}} ... p_ {l} ^ {k_ {l}}}$ i ${\ displaystyle b = 1}$ ). Wtedy taki wielomian definiuje permutację.

Aby to zobaczyć, zauważamy, że dla wszystkich liczb pierwszych pi _. , i > 1 redukcja tego wielomianu kwadratowego modulo _pi jest w rzeczywistości wielomianem liniowym, a zatem jest permutacją z trywialnego powodu Dla pierwszej liczby pierwszej powinniśmy skorzystać z omówionego wcześniej lematu, aby zobaczyć, że definiuje on permutację.

Rozważmy na przykład Z / 12 Z i wielomian . ${\ Displaystyle 6x ^ {2} + x}$ . Definiuje permutację ${\begin{pmatrix}0&1&2&3&4&5&6&7&8&\cdots \\0&7&2&9&4&11&6&1&8&\cdots \end{pmatrix}}.$

Wielomiany wyższego stopnia nad skończonymi pierścieniami

Wielomian g ( x ) dla pierścienia Z / p ^k Z jest wielomianem permutacyjnym wtedy i tylko wtedy, gdy permutuje pole skończone Z / p Z i ${\ Displaystyle g' (x) \ neq 0 {\ bmod {p}}}$ dla wszystkich x w Z / p ^k Z , gdzie g ′ ( x ) to formalna pochodna g ( x ) .

przypuszczenie Schura

Niech K będzie algebraicznym ciałem liczbowym, gdzie R będzie pierścieniem liczb całkowitych . Termin „hipoteza Schura” odnosi się do twierdzenia, że ​​jeśli wielomian f zdefiniowany przez K jest wielomianem permutacyjnym na R / P dla nieskończenie wielu ideałów pierwszych P , to f jest złożeniem wielomianów Dicksona, wielomianów stopnia pierwszego i wielomianów postaci x ^k . A właściwie Schur nie poczynił żadnych przypuszczeń w tym kierunku. Pomysł, że to zrobił, jest spowodowany przez Frieda, który przedstawił wadliwy dowód fałszywej wersji wyniku. Prawidłowe dowody podali Turnwald i Müller.

Notatki

• Dickson LE (1958) [1901]. Grupy liniowe z ekspozycją teorii pola Galois . Nowy Jork: Dover.
• Lidla, Rudolfa; Mullen, Gary L. (marzec 1988). „Kiedy wielomian nad polem skończonym permutuje elementy pola?”. Amerykański miesięcznik matematyczny . 95 (3): 243–246. doi : 10.2307/2323626 .
• Lidla, Rudolfa; Mullen, Gary L. (styczeń 1993). „Kiedy wielomian nad polem skończonym permutuje elementy pola?”, II. Amerykański miesięcznik matematyczny . 100 (1): 71–74. doi : 10.2307/2324822 .
•    Lidla, Rudolfa; Niederreiter, Harald (1997). Pola skończone . Encyklopedia matematyki i jej zastosowań . Tom. 20 (wyd. 2). Wydawnictwo Uniwersytetu Cambridge . ISBN 0-521-39231-4 . Zbl 0866.11069 . Rozdział 7.
•   Mullen, Gary L.; Panario, Daniel (2013). Podręcznik pól skończonych . Prasa CRC. ISBN 978-1-4398-7378-6 . Rozdział 8.
• Shallue, CJ; Wanless, komunikator (marzec 2013). „Wielomiany permutacyjne i wielomiany ortomorficzne stopnia szóstego” . Pola skończone i ich zastosowania . 20 : 84–92. doi : 10.1016/j.ffa.2012.12.003 .