順列多項式

数学において、置換多項式（与えられた環に対して）は、環の元の置換として作用する多項式、すなわち写像が全単射である多項式である。環 が有限体である場合、チェビシェフ多項式と密接に関連しているディクソン多項式 が例となる。有限体上では、あらゆる関数、特にその体の元のあらゆる置換は、多項式関数として表すことができる。 ${\displaystyle x\mapsto g(x)}$

有限環Z / n Zの場合、このような多項式も研究され、誤り検出および訂正アルゴリズムのインターリーバコンポーネントに適用されている。^{[1] [2]}

F _q = GF( q )を特性 pの有限体、つまり素数pに対してq = p ^eとなるq個の元を持つ体とする。F _qに係数を持つ多項式f (記号的にはf ∈ F _q [ x ]と表記) は、 F _qからそれ自身への関数が F q の置換である場合に、F q_の置換多項式_である。 [ ^3]${\displaystyle c\mapsto f(c)}$

Fqの有限性により_、この定義はいくつかの同等の方法で表現できる: ^[4]

• 関数は全射である（全射である）。${\displaystyle c\mapsto f(c)}$
• 関数は1対1（単射）である。${\displaystyle c\mapsto f(c)}$
• f ( x ) = a はF _q内の各aに対してF _q内に解を持つ。
• f ( x ) = a は、 F _q内の各aに対してF _q内に一意の解を持ちます。

どの多項式が置換多項式であるかの特徴付けは次のように与えられる。

（エルミートの判定基準）^{[5] [6]} f ∈ F _q [ x ]がF _qの置換多項式であるためには、次の2つの条件が満たされなければならない。

1. f はF _q内にちょうど 1 つの根を持ちます。
2. 1 ≤ t ≤ q − 2かつ である各整数tに対して、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もGF( q )のすべてのa ≠ 0、b、cに対して正規化形式になります。置換多項式g ( x )が正規化形式であるとは、a、b、cを選択してg ( x )がモニック、g (0) = 0、および (特性p が多項式の次数nを割り切らない場合) x ^{n −1}の係数が0 であることを意味します。

有限体上で定義された置換多項式に関しては多くの未解決の問題が存在する。^{[7] [8]}

エルミートの基準は計算量が多く、理論的な結論を出すのが難しい場合があります。しかし、ディクソンはそれを使用して、すべての有限体上の次数5以下のすべての置換多項式を見つけることができました。その結果は次のとおりです。^{[9] [6]}

正規化された形式の6次のすべてのモニック置換多項式のリストは、Shallue & Wanless (2013)に掲載されています。^[10]

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

• xn^がGF( q )を置換するのは、 nとq −1が互いに素であるとき（表記上、 ( n , q −1)=1 ）に限ります。 ^[12]
• aがGF( q )に含まれ、n≥1のとき、ディクソン多項式（第一種）Dn ( 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 2 ⁻ 1) = 1が成立します。^[13] a = 0の場合、 D _n ( x , 0) = x ⁿとなり、前の結果が成立します。

• GF( q ^r ) がr次GF( q )の拡大である場合、GF( q ^r )内のα _sを持つ線型多項式は、GF ( q )上の GF( q r ) 上の線型^作用素である。線型多項式L ( x ) がGF( q r )を置換するのは、 0 がL ( x )のGF( q ^r )^内の唯一の根である場合に限る。^[12]この条件は代数的に次のように表現できる^[14] $${\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( qr ⁾上の置換多項式である線型化多項式は、合成を法とする群を_形成し、これはベティ・マシュー群として知られ、一般線型群GL( r , Fq )と同型である。^[14]${\displaystyle x^{q^{r}}-x}$

• g ( x ) が多項式環F _q [ x ]に含まれ、s がq − 1を割り切るときにg ( x ^s )はGF( q )に非零根を持たず、r > 1がq − 1と互いに素 (互いに素) である場合、x ^r ( g ( x ^s )) ^{( q - 1)/ s は}GF( q )を置換します。^[6]
• GF( q )上の置換多項式の他の特定のクラスは、いくつかしか特徴付けられていません。たとえば、次の 2 つは、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 _]上の多項式で、無限個のmに対してGF( qm )上の置換多項式となるものである。^[15]

GF( q )上の次数q = ^1/4以下の置換多項式はGF( q )上で例外的である。^[16]

GF( q )のあらゆる順列は例外的な多項式によって誘導される。^[16]

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

有限幾何学では、特定の点集合の座標記述は、より高次の置換多項式の例を提供することができます。特に、有限射影平面 PG(2, q )（q は 2 の累乗）上の楕円を形成する点は、座標間の関係がo多項式によって与えられるように座標化できます。o 多項式は、有限体GF( q )上の特殊なタイプの置換多項式です。

有限体上の与えられた多項式が置換多項式であるかどうかをテストする問題は、多項式時間で解くことができる。^[18]

多項式がn変数の 上の置換多項式であるとは、方程式が各 に対して でちょうど解を持つことを意味する。^[19]${\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に対して、 2次置換多項式を構築することができます。実際には、素数pに対してn がp ²で割り切れる場合にのみ可能です。構築は驚くほど簡単ですが、それでも優れた特性を持つ置換を生成できます。そのため、3GPP Long Term Evolutionモバイル通信規格のターボコードのインターリーバーコンポーネントで使用されています(3GPP 技術仕様 36.212 ^[20]の 8.8.0 バージョンの 14 ページなどを参照)。

環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がゼロでない 場合にのみ順列を定義します。したがって、多項式は 2 次ではなく線形です。

補題: 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について、この 2 次多項式の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}}.$

環Z / p ^k Zの多項式g ( x )が置換多項式となる必要十分条件は、有限体Z / p Zを置換し、Z / p ^k Z内のすべてのxに対して置換する場合である。ここでg ′( x )はg ( x )の形式微分である。^[21] ${\displaystyle g'(x)\neq 0{\bmod {p}}}$

K を代数体とし、R を整数環とする。「シューアの予想」という用語は、K上で定義された多項式fが、無限個の素イデアルPに対するR / P上の置換多項式である場合、f はディクソン多項式、次数 1 の多項式、および形式x ^kの多項式の合成であるという主張を指す。実際、シューアはこの方向で予想を立てていない。彼が予想を立てたという考えは、結果の誤ったバージョンについて不完全な証明を与えたフリード^{[22]によるものである。正しい証明は、ターンワルド[23]}とミュラー^[24]によって与えられている。

• ディクソン、LE（1958）[1901]。ガロア体理論の解説付き線型群。ニューヨーク：ドーバー。
• リドル、ルドルフ; マレン、ゲイリー L. (1988 年 3 月)。「有限体上の多項式が体の元を置換するのはいつですか?」アメリカ数学月刊誌95 (3): 243–246. doi :10.2307/2323626。
• リドル、ルドルフ; マレン、ゲイリー L. (1993 年 1 月)。「有限体上の多項式が体の元を置換するのはいつですか? II」。アメリカ数学月刊誌。100 (1): 71–74。doi :10.2307/2324822。
• リドル、ルドルフ、ニーダーライター、ハラルド(1997)。有限体。数学とその応用百科事典。第 20 巻 (第 2 版)。ケンブリッジ大学出版局。ISBN 0-521-39231-4.ZBL0866.11069  .​ 第7章。
• Mullen, Gary L.; Panario, Daniel (2013).有限体ハンドブック. CRC Press. ISBN 978-1-4398-7378-6。第8章。
• Shallue, CJ; Wanless, IM (2013年3 月)。「6 次順列多項式と正射多項式」有限体とその応用。20 : 84–92。doi : 10.1016/ j.ffa.2012.12.003。