順列多項式

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

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

有限体上の一変数置換多項式

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

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

• 関数は全射である（全射的）。${\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内に一意の解を持ちます。

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

（エルミートの判定基準）^{[ 6 ] [ 7 ]} f∈Fq [ x ]_がFqの置換多項式であるためには、次 の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 となるように選択されることを意味する。

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

小さな学位

エルミートの基準は計算量が多く、理論的な結論を導き出すのが難しい場合がある。しかし、ディクソンはこれを用いて、すべての有限体上の次数5以下のすべての置換多項式を見つけることができた。その結果は以下の通りである。^{[ 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}$ （ F qにおける唯一の根が 0 の場合）	${\displaystyle q\equiv 0\!{\pmod {2}}}$
${\displaystyle x^{5}}$	${\displaystyle q\not \equiv 1\!{\pmod {5}}}$
${\displaystyle x^{5}-ax}$ （4乗ではない）${\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}}}$

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

順列多項式のいくつかのクラス

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

• x ^{n が}GF( q )を並べ替えるには、 nとq − 1が互いに素である必要がある（表記上、 ( n , q − 1) = 1）。 ^{[ 13 ]}
• 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ならば、Dn ( x , a )_はGF( q )を置換するため、n , q2−1 ) =1が成り立つ。^{[ 14 ]} a =0ならばDn ₍ x ,0)= xnとなり^、前の結果が成り立つ ^。

• GF( q ^r )がr次GF( q )の拡大である場合、α _sをGF( q ^r )に持つ線型多項式は、GF( q )上のGF ( q ^r )上の線型作用素である。線型多項式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( qr )上の置換多項式である線型多項式は、^合成を法とする群を形成し、これはベッティ・マシュー群として知られ、一般線型群GL( r , Fq )と同型で_ある。^{[ 15 ]}${\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 )を置換する。^{[ 7 ]}
• 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 )上の置換多項式となるものである。^{[ 16 ]}

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

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

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

幾何学的な例

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

計算の複雑さ

有限体上の与えられた多項式が置換多項式であるかどうかをテストする問題は、多項式時間で解くことができる。^{[ 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}}$

有限環上の二次置換多項式（QPP）

有限環Z / n Zに対して、二次置換多項式を構成することができます。実際には、ある素数pに対してn がp ²で割り切れる場合にのみ可能です。構成は驚くほど単純ですが、優れた特性を持つ置換を生成することができます。そのため、この構成は3GPP Long Term Evolutionモバイル通信規格のターボ符号のインターリーバー要素に使用されています（3GPP技術仕様 36.212 ^{[ 21 ]}、例えばバージョン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

環Z / p ^k Zについて考えます。 ${\displaystyle g(x)=ax^{2}+bx+c}$

補題：k = 1（すなわちZ ​​/ p Z ）のとき、そのような多項式は、 a = 0かつbが0でない場合にのみ順列を定義する。したがって、この多項式は二次ではなく一次である。

補題: k >1, p >2 ( Z / p ^k Z )の場合、そのような多項式は、かつの場合にのみ順列を定義します。 ${\displaystyle a\equiv 0{\pmod {p}}}$ ${\displaystyle b\not \equiv 0{\pmod {p}}}$

リングZ/ nZ

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

有限環上の高次多項式

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

シュアーの予想

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

注記

1. Li, Chengqing; Lu, Xiaoxiong (2025). 「環上のチェビシェフ置換多項式のグラフ構造」. IEEE Transactions on Information Theory . 71 : 1419–1433 . doi : 10.1109/TIT.2024.3522095 .${\displaystyle Z_{p^{k}}}$
2. Takeshita, Oscar (2006). 「順列多項式インターリーバ：代数幾何学的観点」. IEEE Transactions on Information Theory . 53 (6): 2116– 2132. arXiv : cs/0601048 . doi : 10.1109/TIT.2007.896870 .
3. LDPC符号の新たな構成」arXiv : cs/0506091 .
4. マレン & パナリオ 2013、p. 215
5. Lidl & Niederreiter 1997、p. 348
6. Lidl & Niederreiter 1997、p. 349
7. マレン＆パナリオ 2013、p. 216
8. リドル＆マレン（1988）
9. リドル＆マレン（1993）
10. ディクソン 1958、63ページ
11. マレン & パナリオ 2013、p. 217
12. リドル＆マレン 1988、244ページ
13. Lidl & Niederreiter 1997、p. 351
14. Lidl & Niederreiter 1997、p. 356
15. Lidl & Niederreiter 1997、p. 362
16. マレン & パナリオ 2013、p. 236
17. マレン＆パナリオ 2013、p. 238
18. マレン & パナリオ 2013、p. 239
19. Kayal, Neeraj (2005). 「多項式時間で順列関数を認識する」.計算複雑性に関する電子コロキウム. ECCC TR05-008 . この問題に関する先行研究については、Ma, Keju; von zur Gathen, Joachim (1995). 「順列関数の認識における計算複雑性」. Computational Complexity . 5 (1): 76– 97. doi : 10.1007/BF01277957 . MR 1319494 .を参照。 Shparlinski, IE (1992). 「順列多項式の決定論的検定」.計算複雑性. 2 (2): 129– 132. doi : 10.1007/BF01202000 . MR  1190826 .
20. マレン & パナリオ 2013、p. 230
21. 3GPP TS 36.212
22. Sun, Jing; Takeshita, Oscar (2005). 「整数環上の順列多項式を用いたターボ符号のインターリーバ」IEEE Transactions on Information Theory . 51 (1): 102.
23. Fried, M. (1970). 「シュアー予想について」ミシガン数学ジャーナル: 41–55 .
24. Turnwald, G. (1995). 「シュアーの予想について」. J. Austral. Math. Soc . 58 (3): 312– 357. doi : 10.1017/S1446788700038349 .
25. Müller, P. (1997). 「シュアー予想のヴァイル境界自由証明」有限体とその応用. 3 : 25–32 . doi : 10.1006/ffta.1996.0170 .

参考文献

• ディクソン, LE (1958) [1901].線型群とガロア体理論の解説. ニューヨーク: ドーバー.
• リドル, ルドルフ; マレン, ゲイリー L. (1988年3月). 「有限体上の多項式が体の元を置換するのはどのような場合か?」アメリカ数学月刊誌. 95 (3): 243– 246. doi : 10.2307/2323626 . JSTOR  2323626 .
• リドル, ルドルフ; マレン, ゲイリー L. (1993年1月). 「有限体上の多項式が体の元を置換するのはいつか？ II」.アメリカ数学月刊誌. 100 (1): 71– 74. doi : 10.2307/2324822 . JSTOR  2324822 .
• リドル、ルドルフ；ニーダーライター、ハラルド（1997年）有限体．数学とその応用百科事典第20巻（第2版）．ケンブリッジ大学出版局．ISBN 0-521-39231-4. Zbl  0866.11069 . 第7章。
• マレン、ゲイリー・L.; パナリオ、ダニエル (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 .