Nielsen–Schreier 定理与自由基重写

为什么可以选到生成树 ​

有限连通图可以从基点开始逐个纳入新顶点：每次选一条通往尚未纳入顶点的边。这样不产生回路，最终得到生成树。BFS或DFS都可以完成这一步。

对一般可能无限的图，考虑所有含基点的连通无圈子图，按包含排序。任意链的并仍连通且无圈，因为一个圈只有有限条边，若它出现在并中，就已经出现在链的某个成员中。由Zorn引理理路佐恩引理Zorn's lemma若偏序集中每条链都有上界，则该偏序集存在极大元。存在极大者。如果它还漏掉一个顶点，沿通往该顶点的有限边路取第一条离开现有子图的边，就能再添一个顶点且不产生圈，矛盾。因此极大者包含全部顶点。

这一存在论证与有限输入的图搜索是两回事。定理允许无限子群，公共有限表算法则只能在给定的有限数据上运行。

树路径把每条剩余边接成一个闭路 ​

从基点沿 $t_v$ 到达边的起点，穿过 $e$，再沿 $t_w$ 反向返回，就读得 $c_e$。它闭合，所以属于 $H$。若 $e$ 本身在树中，这个闭路完全位于树内，反复退掉往返边后为空词；因此树边不贡献新的基元。

现在任取 $h\in H$，选一个代表词，沿陪集图读成基点闭路。设依次经过的顶点为 $v_0,v_1,\dots ,v_m=v_0$，字母为 $s_1^{{ϵ}_1},\dots ,s_m^{{ϵ}_m}$。插入每个顶点的树路径及逆路径，得到

中间相邻的 $t_{v_j}^{-1}{t}_{v_j}$ 全部约掉，两端树路径为空。每一因子若走树边就是一；若正向或反向走非树边，就是相应的 $c_e$ 或 $c_e^{-1}$。所以这些词确实生成整个 $H$。

为什么它们之间没有隐藏关系 ​

为每条非树正边引入一个新形式字母 $C_e$。对任一从基点出发的闭合边路，按行走次序记录：树边不记，非树边正向记 $C_e$，反向记 $C_e^{-1}$，最后作自由约化。记所得词为 $R(h)$。

这个输出只依赖原自由群元素 $h$。在原词中删除相邻逆字母，会在Schreier图里删除同一条边的往返，因为每个方向的边唯一。若该边为树边，记录原本就为空；若为非树边，记录删除一对相邻逆字母。因此原词的任何约化都不改变最终记录。

两个属于 $H$ 的词都在基点闭合，可以连续读完；故 $R$ 保持乘法，给出同态

另一方面，将 $C_e$ 送到 $c_e$，由自由群泛性质得到满同态 $\mathrm{\Phi }:F(\{C_e\})\to H$。走 $c_e$ 时两端是树路径，中间只经过这条非树边，所以

满同态 $\mathrm{\Phi }$ 又有左逆，因而单射，最终是同构。这同时证明了生成性和无关系，不能仅凭“找到若干闭词”就宣布它们是自由基。

数一数非树边 ​

有限指数时，陪集图有 $n$ 个顶点，每个顶点、每个生成元各给一条独立正边，共 $nr$ 条。生成树恰有 $n-1$ 条边，故非树边数为

先证明它们是自由基，再数它们，才得到秩公式。若误把相反的两条正边合并成一条，这个计算与前面的自由基都会出错。

三层子群的四个自由基元 ​

采用三顶点作用 $a=(12)$、$b=(123)$，基点为1。选择两条 $b$ 边 $1\to 2$、$2\to 3$ 为生成树，于是

六条正边中，这两条在树上；其余四条给出：

每个词都从1出发又回到1。定理证明它们不只是生成集，而是自由基。指数为三、母群秩为二，因此 $\mathrm{rank}(H)=1+3(2-1)=4$，与表中四条非树边一致。

逐边重写一条新词 ​

读 $w=b^2{a}^{2}b$，顶点依次为

前两步在树上，接着两次走 $c_3$ 对应自环，最后走 $c_4$ 对应边。所以

直接代入也可复算：

对 $a^2$，相应重写为 $c_1{c}_2$，因为 $a{b}^{-1}ba=a^2$。这类乘积约消是原自由群中的精确等式，不能只用两个词具有同一纤维置换来代替；不同自由词可能给相同置换。

无限指数不能直接读成无限秩 ​

$F(a,b)$ 中的 $⟨a⟩$ 是秩一的自由群，却有无限指数。右陪集 $⟨a⟩b^k$ 两两不同，因为非零次 $b$ 幂不可能约化为 $a$ 的幂。

另一边，令 $H$ 为指数和同态 $a\mapsto 1,b\mapsto 0$ 的核。其Schreier图为整数直线，每点挂一条 $b$ 自环。取整条直线为生成树，顶点 $k$ 的树词为 $a^k$，得到无限自由基

所以有限生成自由群的子群未必有限生成；普通有限指数秩公式没有覆盖这一情形。

不闭合的词还留有一个陪集代表 ​

对任意词 $w$，即使它不属于 $H$，同样的逐边插入仍给出

其中 $v$ 是最终顶点，$h$ 为非树基元重写的乘积。只有终点为基点时，末尾的 $t_v$ 才为空。

例如三顶点图中读 $ab$ 到达3，非树记录只有 $C_1$，因此正确等式是

不能省掉 $t_3$ 后错说 $ab=c_1\in H$。先验证闭合，再把记录当作子群表达式，是算法必须保留的顺序。

有限表怎样交付一份自由基证书 ​

先交置换表及其逆，验证图确为连通覆叠；再交一组包含全部顶点、无圈的树边。保存每个顶点的父边即可隐式记录树词，非树边按固定顺序编号，最后输出基词或保留其“去程树路、当前边、返回树路”表示。

当有 $n$ 个顶点、$r$ 个生成元时，寻找生成树和标记非树边需 $O(n(r+1))$ 次图操作。若把每个基词全部展开，单词长度至多 $2n-1$，总输出长度可达 $O(n+n^{2}r)$；不能把这种显式输出成本漏掉。写成含 $n$ 的界也涵盖 $r=0$：此时母群平凡，连通陪集图只有一个顶点，仍须交付空自由基证书。已有表和边编号后，读长度 $m$ 的输入并用栈约化非树记录，需要 $O(m)$ 次查表与栈操作。

这个证书与覆叠的子群分类理路覆叠空间的子群分类Classification of covering spaces · Subgroup classification of connected coverings · 覆叠分类定理在明确局部条件下把带基点连通覆叠与基本群子群双向对应，构造每个子群的覆叠，并区分忘基点的共轭分类、覆叠同构和总空间同胚。配合，既说明子群位于母群的什么位置，又提供其内部独立坐标。只报告抽象秩四，不能区分三层覆叠对应的不同子群；自由基嵌入词保留了这种位置信息。