一个比较初级的整理, 本篇中我们主要考虑两个问题.
生成子群问题
对于某一族群 \(G\), 给定一个子集 \(S\subset G\), 问生成的子群 \(\langle S\rangle\) 的如下信息:
- 给定 \(g\in G\), 判定 \(g\in \langle S\rangle\)?
- 计算生成子群的大小 \(|\langle S \rangle|\)?
- ...
如果我们有一个陪集数量的子群 \(H\leq G\), 可以如下考虑第一个问题.
对于输入的一个 \(g\in G\), 我们首先想要经过一番操作使得 \(s_n \cdots s_1 g\in H\), 也就是作为 \(H\) 的左陪集的部分正确归位. 然后转换成解 \(H\) 里的问题.
如果有过一点点玩魔方的经验的话, 容易类比第一层和第二层的情况. 在做第一层的时候我们并没有太多顾虑, 很容易就能把第一层还原. 而处理第二层的时候就有一个固定的几步流程, 使得原先的第一层虽然被动用, 却又在最后复位, 并且最后把第二层的角也复位. 反映在一般情况上, 就是我们需要得到 \(\langle S \rangle \cap H\) 的一个生成集.
记 \(X\) 为 \(H\) 的所有左陪集, \(G\) 自然以左乘作用于 \(X\) 上. 第一部分的想法是简单的, 我们很容易通过已有的生成元通过 bfs 的方式处理出一个 \(Y\subset X\), 表示对于每个 \(yH \in Y\) 存在 \(s\in \langle S \rangle\) 使得 \(syH = H\).
第二步是考虑如果 \(y\in H \cap \langle S\rangle\) 的话, 它将如何被我们计算出的一些生成集给出.
根据 \(y\in \langle S\rangle\), 我们有 \(s_n\cdots s_1 y = 1\), 其中 \(s_i \in S\), 但 \(s_i\) 不一定在 \(H\) 里. 我们依然不妨考虑它们将陪集操作成什么样子. 记 \(a_i = s_i s_{i-1} \cdots s_1 y H = s_i s_{i-1} \cdots s_1 H\), 那么我们考虑 \(s_i\), 它的作用是把 \(a_{i-1}\) 作用成 \(a_i\). 注意本质不同的 \(a_i, a_{i-1}\) 只有 \([G:H]^2\) 种可能. 我们实际上可以考虑所有如下元素:
\[x^{-1} s y, \]其中 \(s\in S\), 而 \(x, y\) 是选取的 \(S\) 可达的 \(xH, yH\) 对应的代表元. 那么如果 \(s(yH)=xH\), 也即有 \(x^{-1}sy \in H\), 这些都确实是 \(H\) 里的元素. 最后, 如果
\(s_n \cdots s_1 a_0 = 1\), 记 \(\overline y\) 是 \(yH\) 选取的一个代表元, 并且要求 \(\overline 1 = 1\), 我们有
这说明, \(\{x^{-1} s y\}\) 确实组成了子群部分的生成集.
为了让复杂度正确, 我们最后梳理一遍过程.
固定群 \(G\), 我们首先找到一个子群链 \(\{1\} = G_0 \leq G_1 \leq \dots \leq G_m = G\), 然后以增量的方式一点点增加 \(S\).
每次加一个元素 \(g\) 的时候, 我们首先解它到底是否在 \(G\) 里. 尝试用 \(G_m / G_{m-1}\) 层维护的信息消掉这部分, 如果 \(g\in G_{m-1}\) 了, 就递归到下面检查, 否则 \(g\) 直接用于继续这层的 bfs 过程.
如果 bfs 得到了新的东西, 也说明有新的元素要插到子群里, 这个时候也需要递归下去.
看起来递归下去的时候会让集合膨胀, 实际不然, 每个向下递归都是 \(S\) 增大或者 bfs 到新的节点产生的, 所以复杂度是 \(\operatorname{poly}(\sum_i [G_i:G_{i-1}], |S|)\).
例子
取 \(G = \prod (\mathbb Z / m_i \mathbb Z)\), 不妨直接取 \(G_k\) 是只有前 \(k\) 个分量可以非零的子群. 那么 \(G_i : G_{i-1}\) 这部分就是试图考虑第 \(i\) 个分量抵消的贡献. 并且由于交换律, 往下插只需要乘以适当的倍数把第 \(i\) 个分量置零.
取 \(G = S_n\), 固定后 \(n-m\) 各元素的置换得到嵌入 \(S_i \leq S_{i+1}\). 这就是所谓的 Schreier–Sims 算法.
有限群 DFT 问题
对于有限群 \(G\), 设 \(\operatorname{Irr}(G)\) 为 \(G\) 的全体 (同构意义下) 的 \(\mathbb C\) 上的不可约表示. 我们知道, 有 \(\mathbb C\)-代数的同构
\[\mathbb C[G] \cong \bigoplus_{i} \operatorname{End}(V_i), \]其中 \(V_i\) 跑遍不可约表示, 由
\[g_i \mapsto \bigoplus_{\rho\in \operatorname{Irr}(G)} \rho(g) \]给出.
有限群 DFT 意即给定一个 \(\sum_g a_g g \in \mathbb C[G]\) 这一系数表示下的群代数, 计算不可约表示各自某组基下的矩阵系数, 也即对每个 \(V_i\) 计算出
\[\sum_g a_g \rho(g) \]这个矩阵.
对于这个问题而言, 单子群规约已经能够概括很多思路了.
考虑子群 \(H\), 每个 \(G\) 的表示自然都是一个 \(H\) 的表示, 所以一个 \(\rho \in \operatorname{Irr}(G)\) 亦能表示成一些 \(\operatorname{Irr}(H)\) 的直和.
所以我们先把 \(\sum a_g g\) 写成 \(H\) 的每个陪集的形式 $$\sum_{gH} \sum_h a_{gh}(gh) = \sum_{gH} g\left(\sum_h a_{gh} h \right),$$
那么我们可以先把这 \([G:H]\) 个 \(H\) 上的 DFT 问题解决, 然后再乘以 \(\rho(g)\) 求和. 那么时间复杂度可以写作
\[T(G) = [G:H]\left(T(H) + O\left( \sum_{i} (\dim V_i)^{\omega} \right)\right). \]例子
当 \(G = \mathbb Z / 2^n\mathbb Z\) 的时候, 就是常见的 FFT, 子群 \(2G \cong \mathbb Z / 2^{n-1}\mathbb Z\).
当 \(G=S_n\) 的时候, 取 \(H=S_{n-1}\) 这样递降下去. 实际上这就是算法 \(O(|G| \log^{O(1)} |G|)\) 做法的算法部分的思路. 大多数笔墨在于构造出 \(S_n\) 的不可约表示和 \(S_{n-1}\) 的不可约表示的关系.
Chris Umans 通过 三子群规约 最终实现了 \(G^{1+o(1)}\) 的一般群 DFT 算法. 值得一提的是, 这一算法的论述过程甚至调用了重炮之 有限单群分类定理, 所以这个 \(o(1)\) 隐含一些巨大的常数, 包括但不限于, 魔群 的大小是 \(O(1)\).
标签：mathbb,规约,sum,overline,cdots,子群,rangle,单一 From： https://www.cnblogs.com/Elegia/p/single-subgroup-reduction.html