置换多项式群

第三节 置换多项式群 设 是上次数小于的置换多项式 则多项式和的合成 f x g x q Fqfg 模后仍为上次数小于的置换多项式 f g x q xx q Fq 因此 在合成运算下 的所有次数小于的置换多项式作成一个群 该该 q Fq 群同构于群同构于个字母上的对称群个字母上的对称群 q q S 首先 对的任一次数小于的置换多项式 导出的一个 q Fq f x f x q F 置换 做映射 f f f 则是从的所有次数小于的置换多项式到的全体置换的映射 不同的 q Fq q F 导出不同的置换 因此是单射 f x f 其次 对的任一置换 有拉格朗日插值公式知 存在上的一个 q F q F 次数小于的多项式使对所有均成立 于是导出q f x c c f c q F f x 是满射 进一步可直接验证满足 所以是 g g fgfg ff AA 一个同构映射 因此对称群及其子群可用的置换多项式群来表示 q S q F 定理定理 7 18 设设 则 则由由及及上所有线性多项式生成 上所有线性多项式生成 2q q S 2q x q F 证明 首先 证明 首先 由定理 7 8 可知以及所有的线性多项式均是的置换 2q x q F q F 多项式 因此都是中的元 q S 其次 其次 从对换的性质可知和由所有对换生成这两个事 bc 0b 0c 0b q S 实 只需证明对换可被及线性多项式的合成所表出 0 a 2q x 0 x 多项式正好表出对换即 22122 qqq a fxaxaaa 0 a 当时有 因为由和线性多项式合成 0 0fa f a 0 ca c c a f a fx 2q x 而来 所以定理结论成立 A 定理定理 7 19 设设 是是的一个固定的本原根 则的一个固定的本原根 则由由 以及以及2q c q F q Scx1x 所生成 所生成 2q x 证明 证明 令则存在整数使得 该定理的结论可由 q a b F1st st ac bc 定理 7 8 和得到 1 sss tt axc xcxaxbcxxcx A 类似的 可以得到交错群的生成元 这里交错群是由的所有偶置 q A q A q S 换组成的 与偶置换相对应 如果的置换多项式导出的一个偶置换 就 q Ff q F 称是的偶置换多项式偶置换多项式 f q F 定理定理 7 20 设设 则 则和和是是的偶置换多项式 的偶置换多项式 2q q a Fxa 22 qq xa q F 是偶置换多项式当且仅当是偶置换多项式当且仅当是是中的平方元 中的平方元 是偶置换多项式当且仅当是偶置换多项式当且仅当axa q F 2q x 3 mod4 q 证明 证明 导出的置换由个形如的长度为的xa 1e p p 1 a aaaa p 轮换组成 其中为的特征 所以 当为奇数或而时p q F e qp p2eq 1e 是偶置换多项式 xa 因此也是偶置换多项式 2222 qqqq xaxxax 22 qq xa 是置换多项式 当且仅当 设 则由 个合成而来 ax0a s ac axscx 导出的置换是一长度为的圈 因而当为奇数时为偶 s axcx cx1q qcx 置换 当为偶数时中的每个元都是平方元 q q F 由此推出是中的偶置换当且仅当且是的平方元 ax q F0a a q F 最后把的所有元素依对换双双配对 2q x 0 1 1 q F 当为奇数时共有个对换 当为偶数时有个对换 此时 1 1 q 3 2 q q 2 2 q 所以是偶置换多项式当且仅当 2q x 3 mod4 q A 设 定义下列置换多项式的集 2q b qqq Laxb a FF 2 b qqq ALa xb a FF 22 qq qq Qxaa F 这些集在模的合成运算下构成群 且有 当为奇数时 q xx 1 q Lq q q 当为偶数时 同构于的加法 1 1 2 q ALq q q 1 q ALq q q Qq q Q q F 群 定理定理 7 21 设设 是是的一个固定的本原根 则的一个固定的本原根 则2q c q F 由由和和生成生成 定理 定理 7 19 过程 过程 Lqcx1x 由由和和生成生成 由定理 由定理 7 20 ALq 2 c x1x 由它的子群由它的子群和和生成生成 由定理 由定理 7 20 和和 AqALqQq 由由 和和生成生成 由 由 和和 Aq 2 c x1x 22 qq xa 给定一个对复合运算封闭的置换多项式类给定一个对复合运算封闭的置换多项式类 那么 这个类所表示的是那么 这个类所表示的是的的 q S 哪个子群呢哪个子群呢 对于固定的 对于固定的 我们首先来研究 我们首先来研究 的置换多项式的所有的置换多项式的所有 q a F q F Dickson多项式多项式的集合的集合 亦即 亦即 k gx aP a 2 P 0 g 0 kN gcd k q 1 1 P g kN gcd k q1 1 0 k k x ax aa 对于 定理定理 7 22 在多项式合成的运算下构成一个群 当且仅当在多项式合成的运算下构成一个群 当且仅当或或 P a0 1a 1 证明 证明 对于 由可知 q ak mN F y y k k k k aa ga yy g y y y y mkm mmmkm kmkkm mkm aaaa ga agaga yyyy 因此 有 g g m kmkm gx ax a a 1 如果且对复合封闭 则由可知0a P a 22 gcd k q1 gcd m q1 1 因此 且由 1 式有 g g P km x a aa g g kmkm gx a ax a g g g m kmkm gx a ax a a 因为不是常数 所以 g m x a g m kk gx ax a 对于比较的系数 对所有满足的得到 k1 2k x 2 gcd m q1 1 m m aa 因而 即得 1 aa 1a 反之 如果 则由 1 式 对复合封闭 0 1a P aA 由此在这三种情形 的多项式所表示的的所有置0 11aaa 和P a q F 换的集合是的 Abel 子群 G a q S 下面研究下面研究的结构 的结构 G a 设设 对 对可找到可找到使得使得 1a q c F 2 q F 1 ca 因此 对因此 对 由 由式有 式有 2 mod q1 km y y k k k k aa ga yy 11 c c km km kkmm km aa gagaagaaga 所以所以 若若 则 则和和诱导出诱导出的同一置换 的同一置换 2 gcd k q1 1 k gx a m gx a q F 因此因此 如果对剩余类如果对剩余类指定指定导出的导出的的置换的置换 则得到一个则得到一个 2 mod q1 k k gx a q F 映成映成的满射的满射 映上的同态映上的同态 其中的其中的是模是模的约化剩余的约化剩余 2 R q1 G a 2 R q1 2 q1 类群类群 亦即是剩余类环亦即是剩余类环的单位元素群 由同态基本定理的单位元素群 由同态基本定理 现只需确定这现只需确定这 2 Z q1 个满射的个满射的核核 K a 如果如果 则对所有 则对所有 kK a qk cgc ac F 因此因此 令令如上如上 则则 因 因得到得到 所以 所以 k k k aa k aa k k aa 或者或者 k k a 从而从而 对满足对满足的所有的所有 1 1 q a F 2 1 1 1 kk q a 或F 这个条件对于这个条件对于中的中的也是充分的 而也是充分的 而当且仅当当且仅当 K ak q a F q aa 这又等价于这又等价于或或 1 1q 1 q a 设设 令 令是是的一本原元的一本原元 则则 1a 2 q F q 1 n q 1 m m n 或Z Z 因此因此当且仅当当且仅当是下列四个同余式组之一的一个解是下列四个同余式组之一的一个解 1 kK k 1mod q 1 1mod q 1 k k 1mod q 1 1mod q 1 k k 1mod q 1 1mod q 1 k k 1mod q 1 1mod q 1 k k 模模下解这些同余式组得到下解这些同余式组得到 2 1q 2222 1 1 1 1 1 q1 2 q q1 2 q q1 2 1 q1 2q K 1 qqq qq 为偶数 为奇数 类似处理类似处理的情形 得的情形 得1a 22 1 3 mod4 1 1 q1 2 q q1 2q 1 mod4 K 1 qq q 上面这些结果总结如下 上面这些结果总结如下 定理定理 7 23 时 群时 群同构于同构于 其中 其中如上 并且如上 并且1a G a 2 q1 K Ra K a 有 如果有 如果 即偶数 即偶数 则 则 如果 如果 即奇数 则 即奇数 则 如 如q2 1 2K q2 1 8K 果果则则 如果 如果则则 另外群 另外群同构同构q3 mod4 1 2K q1 mod4 1 4K 0 G 于模于模的约化剩余类群的约化剩余类群 q 1 R q 1 下面给出另外一类有趣的置换多项式 设是的一个扩张 考虑形如 r q F q F 1 0 s r r q s q s L xxx F 2 的线性化多项式 由定理 7 9 是的置换多项式 当且仅当在 L x L x r q F L x 中仅有根 0 亦即 导出的上向量空间的线性算子 变换 是非 r q F L x q F r q F 奇异的 即线性算子的矩阵的行列式不为 0 这个线性算子是非奇异的当且仅 当只要在上是线性独立的 则 011 r r q F q F 在上也线性独立 1111 rr LL q F 以下求线性算子的矩阵 对由 将 将0 1i jr 1 0 s r r q s q s L xxx F 带入 带入 可以得到进而有 ii L 1 0 s r q isi s 1 0 jjsj r qqq isi s 利用且时 有 所以 r q ii mod tsr st 1 0 jsj r qqq iisj s 设分别是和的行列式 则 其 12 A A 011 r 011 r 21det A AA 中阶矩阵是 rr A 1 1 1 011 102 120 r r r qq r qq qq rr