置換多項式

エルミートの判定法は計算負荷が高く、理論的な結論を出すのに使うのが難しい場合があります。しかし、ディクソンはそれを使って、すべての有限体上の次数が最大で 5 のすべての置換多項式を見つけることができました。これらの結果は次のとおりです。^{[ 10 ] [ 7 ]}

正規化された形式の次数 6 のすべての単項置換多項式のリストはShallue & Wanless (2013)に記載されています。^{[ 11 ]}

上記の例以外にも、以下のリストは網羅的ではないものの、有限体上の既知の主要な置換多項式のクラスのほとんどすべてを含んでいます。^{[ 12 ]}

• x ^{n が}GF( q )を置換するのは、 nとq − 1が互いに素である場合(表記上、 ( n , q − 1) = 1 ) に限る。 ^{[ 13 ]}
• aがGF( q )に属し、n ≥ 1の場合、ディクソン多項式(第 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 )は( n , q ² − 1) = 1の場合に限り GF( q ) を置換します。^{[ 14 ]} a = 0の場合、 D _n ( x , 0) = x ⁿとなり、前述の結果が成り立ちます。

• GF( q ^r )が次数rのGF( q )の拡張である場合、線形化された多項式$${\displaystyle L(x)=\sum _{s=0}^{r-1}\alpha _{s}x^{q^{s}},}$$α _{s が}GF( q ^r )に含まれる場合、 はGF( q )上のGF( q r ⁾上の線形演算子です。線形化された多項式L ( x )がGF( q ^r )を置換するのは、0 がGF( q ^r )におけるL ( x )の唯一の根である場合のみです。^{[ 13 ]}この条件は代数的に次のように表現できます。^{[ 15 ]}$${\displaystyle \det \left(\alpha _{i-j}^{q^{j}}\right)\neq 0\quad (i,j=0,1,\ldots ,r-1).}$$

GF( q ^r )上の置換多項式である線形化多項式は、モジュロ合成演算の下で群を形成する。${\displaystyle x^{q^{r}}-x}$これはベティ・マチュー群として知られており、一般線形群GL( r , Fq ₎と同型である。^{[ 15 ]}

• g ( x )が多項式環Fq [ x ]に属し、 s_がq -1を割り切るときにg ( xs ⁾がGF( q )に非零根を持たず、r >1がq - 1と互いに素（互いに素）である場合、xr ( ^g ( xs ⁾ ) ^{( q -1)/ s}はGF( q )を置換する。^{[ 7 ]}
• GF( q )上の置換多項式の特定のクラスはごく少数しか特徴付けられていない。例えば、そのうちの2つは次のとおりである。$${\displaystyle x^{(q+m-1)/m}+ax}$$ここで、m はq − 1を割り切り、$${\displaystyle x^{r}\left(x^{d}-a\right)^{\left(p^{n}-1\right)/d}}$$ここで、d はp ⁿ − 1を割り切る。

GF( q )上の例外的な多項式とは^、無限に多くのmに対して_GF ( qm )上の置換多項式であるFq [ x ]の多項式のことである。^{[ 16 ]}

GF( q )上の次数が高々q ^1/4の置換多項式はGF( q )上で例外的なものである。^{[ 17 ]}

GF( q )のすべての順列は、例外的な多項式によって誘導される。^{[ 17 ]}

整数係数を持つ多項式（すなわち、ℤ[ x ]の）が、無限個の素数pに対してGF( p )上の置換多項式である場合、それは線形多項式とディクソン多項式の合成である。^{[ 18 ]}（下記のシュールの予想を参照）。

考慮する${\displaystyle g(x)=2x^{2}+x}$環Z /4 Zについては、次のようになる。${\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}}.}$$

同じ多項式を考えてみましょう${\displaystyle g(x)=2x^{2}+x}$もう一方のリングZ / 8 Zについては、次のようになります。${\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}}.}$$

考慮する${\displaystyle g(x)=ax^{2}+bx+c}$環Z / p ^k Zの場合。

補題：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}}}$。

考慮する${\displaystyle 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 / n Zの置換を定義するのは、すべての多項式が${\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}}}$。

その結果として、次の簡単な構成法を用いて多数の二次置換多項式を構成できる。${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\dots p_{l}^{k_{l}}}$k ₁ > 1と仮定します。

考慮する${\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}}}$、i > 1。そして、${\displaystyle b\neq 0{\bmod {p}}_{i}}$すべてのi = 1, ..., lについて。（例えば、${\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}}.$