自由幺半群的分解

· · 算法·理论

自由幺半群的分解

可能需要的前置知识：词理论基础。

5.1 Lyndon 词与 Lyndon 分解

定义 5.1.1 (字典序)

给定全序 (A, \leq)，递归定义 A^* 上的序 (A^*, \leq) 如下：

设 x, y \in A^*：

(1) 当 x = \varepsilon，令 x \leq y 恒成立。\ (2) 当 x \neq \varepsilon, y = \varepsilon，令 x \leq y 恒不成立。\ (3) 当 x, y \neq \varepsilon，设 x = ax', y = by'，其中 a, b \in A, x', y' \in A^*，令 x \leq y 当且仅当 a < b \lor (a = b \land x' \leq y')。

称 (A^*, \leq) 为 A^* 上的字典序，容易验证其也为全序。

命题 5.1.2 (字典序的基本性质)

(1) \forall u, v, w \in A^*, u < v \Leftrightarrow wu < wv。\ (2) \forall u, w, x \in A^*, v \in A^+, v \not\in uA^* \Rightarrow (u < v \Leftrightarrow uw < vx)。\ (3) \forall u, v \in A^+, w, x \in A^*, |u| = |v|, u \neq v \Rightarrow (u < v \Leftrightarrow uw < vx)。

Proof. (1) 对 |w| 归纳即得。

(2) 对 |u| 归纳。当 u = \varepsilon，前件 v \not\in uA^* 不可能成立；下面讨论 u \neq \varepsilon 的情形。

设 u = au' \ (a \in A)，对 v \not\in uA^* 分类讨论：

综上明所欲证。

(3) 由 |u| = |v|, u \neq v 可见 v \not\in uA^*，进而由 (2) 即证。

定义 5.1.3 (Lyndon 词)

称 w \in A^+ 为 Lyndon 词，若其本原且在共轭类中字典序最小。这两个条件可以统摄为：

\forall u, v \in A^+, w = uv \Rightarrow w < vu

记所有 Lyndon 词构成集合 L \subset A^+。显然 A \subset L。

当 k = |A| 有限，由共轭类计数公式可知，长为 n 的 Lyndon 词的数量为：

\Psi_k(n) = \frac{1}{n} \sum_{d \mid n} \mu(d) k^{\frac{n}{d}}

例子 5.1.4

设 A = \{a, b\} \ (a < b)，则按长度列出的前若干个 Lyndon 词形如：

L = \{a, b, ab, aab, abb, aaab, aabb, abbb, \cdots\}

命题 5.1.5

设 w \in A^+，则 w 为 Lyndon 词当且仅当 w 小于其所有非空真后缀。或者形式化地说：

\forall w \in A^+, w \in L \Leftrightarrow (\forall u, v \in A^+, w = uv \Rightarrow w < v)

Proof. 先证充分性。由条件立即得到：

\forall u, v \in A^+, w = uv \Rightarrow w < v < vu

再证必要性。首先说明 v 不为 w 的前缀：若不然则 \exists t \in A^+, \text{s.t. } w = uv = vt，命题 1.3.6 指出：

\exists p, q \in A^*, i \in \mathbb{N}, \text{s.t. } u = pq, t = qp, v = p(qp)^i = (pq)^i p

进而有 w = p(qp)^{i + 1} = (pq)^{i + 1} p。由 w 为 Lyndon 词可知其本原性，随后易证 p, q \in A^+。再由其最小性可知：

\begin{aligned} & w = (pq)^{i + 1} p < p(pq)^{i + 1} \\ \Rightarrow \ & (qp)^{i + 1} < (pq)^{i + 1} \\ \Rightarrow \ & (qp)^{i + 1} p < (pq)^{i + 1} p = w \end{aligned}

这与最小性矛盾，故证得 v 不为 w 的前缀。

由 |w| = |u| + |v| > |v| 显见 w \neq v。若 w > v，则 w > vu，与最小性矛盾。总之有 w < v。

推论 5.1.6

若 w \in A^+ 为 Lyndon 词，则其没有非空边界。

Proof. 考虑反证法：设 v 为 w 的非空边界，则一方面由真前缀的性质可知 v < w，另一方面由 命题 5.1.5 可知 w < v，矛盾！

命题 5.1.7

Proof. 先证充分性，只需讨论 w = lm 的情况。首先说明 w < m：

接下来分类讨论 w 的真后缀 v \neq m 的形态：

总之 w 小于其所有真后缀，故 w 为 Lyndon 词。

再证必要性，同样只需讨论 w \in L \backslash A 的情况。

设 m 为 w 的最长真 Lyndon 后缀（合法性：w 的最后一个字母为其真 Lyndon 后缀），w = lm，只需证明 l \in L。

设 v 为 l 的任一真后缀，m 的最长性指出 vm \not\in L。取 t 为 vm 的满足 t < vm 的一个真后缀（由 vm \notin L 及 命题 5.1.5 知其存在，且 t 也是 w = lm 的真后缀）。

若 v < t，则由 v < t < vm 可对 |v| 归纳得 \exists s \in A^+, \text{s.t. } t = vs, s < m，随后由 t 为 vm 的真后缀可见 s 为 m 的真后缀。然而由 命题 5.1.5 可见这与 m \in L 矛盾，因此 v \geq t。

进而据 命题 5.1.5 可知 l < lm = w < t \leq v，因而 v 的任意性和 命题 5.1.5 指出 l \in L。

最终，w \in L 指出 w < m，接下来分类讨论 l 与 m 的关系：

总之，我们给出了分解 w = lm，且满足 l, m \in L, l < m。

上述命题的必要性证明也给出了一个递归构造 Lyndon 词的方法；同时，对于每个 w \in L \backslash A 也提供了一种分解为 Lyndon 词之积的方式。下面给它一个名称。

定义 5.1.8 (标准分解)

设 w \in L \backslash A，m 为 w 的最长真 Lyndon 后缀，w = lm，则 l, m \in L, l < m，称 \sigma(w) = (l, m) 为 w 的标准分解。

Rmk. Lyndon 词按照 命题 5.1.7 的叙述分解时所得结果未必唯一，例如 aababb = (a)(ababb) = (aab)(abb) = (aabab)(b)，其中前者为标准分解。

命题 5.1.9

设 w \in L \backslash A，\sigma(w) = (l, m)，则 \forall n \in L \land w < n，\sigma(wn) = (w, n) 当且仅当 n \leq m。

Proof. 由 w, n \in L, w < n 和 命题 5.1.7 可知 wn \in L，欲证 n 为 wn 的最长真 Lyndon 后缀当且仅当 n \leq m。

先证必要性。假设 n > m，则由 命题 5.1.7 可知 mn \in L，故 n 不为 wn 的最长真 Lyndon 后缀，矛盾！

再证充分性。考虑 wn 的比 n 长的后缀 pn，其中 p 为 w 的非空真后缀。断言 m \leq p：

Proof. 若 p 不为 m 的非空后缀，由 m 的最长性可知 p \not\in L，由 命题 5.1.5 可知存在 p 的非空真后缀 t_1 使得 t_1 \leq p。\ 若 t_1 不为 m 的非空后缀，同样有 t_1 \not\in L，并能给出 t_1 的非空真后缀 t_2 使得 t_2 \leq t_1。\ 依此类推构造出一列 t_0 = p, t_1, \cdots, t_k，使得其为长度递降的一列 w 的非空真后缀，且 t_k \leq \cdots \leq t_1 \leq t_0 = p。此列依递降性终止于 t_k 为 m 的非空后缀即 |t_k| \leq |m| 之时，则 |t_k| \leq |m| < \cdots < |t_1| < |p|。\ 链尾的 t_k 为 m 的非空后缀，由 命题 5.1.5 可知 m \leq t_k，最终得到 m \leq p。明所欲证。

再由 n \leq m 可知 n \leq p < pn，由 命题 5.1.5 可知 pn \not\in L。故 n 为 wn 的最长真 Lyndon 后缀。

定理 5.1.10 (Lyndon 分解定理)

设 w \in A^*，则其可唯一表作不增的 Lyndon 词之积。或者形式化地说：

\exists ! (n \in \mathbb{N}, [l_1, \cdots, l_n] \in L^n), \text{s.t. } w = l_1 \cdots l_n, l_1 \geq \cdots \geq l_n

Proof. 先证存在性。首先由于 w 的每个单字母都是 Lyndon 词，w 总能表作若干 Lyndon 词之积，故可选取一种分解方式，使得 n 最小。

断言这种分解满足 l_1 \geq \cdots \geq l_n：不然，设 l_i < l_{i + 1}，由 命题 5.1.7 可知 l_i l_{i + 1} \in L，则把 l_i, l_{i + 1} 合起来也是一种合法的分解，与 n 的最小性矛盾。

再证唯一性。设 (n, [l_1, \cdots, l_n]), (n', [l'_1, \cdots, l'_{n'}]) 都满足条件，考虑对 n 归纳：

为了求解 Lyndon 分解，一个自然的想法是“剥洋葱”——即逐步析出分解中的首项或末项。下面阐述了有关这两项的一些性质。

命题 5.1.11

设 w \in A^+ 的 Lyndon 分解为 w = l_1 \cdots l_n，则：\ (1) l_n 为 w 的最小非空后缀。\ (2) l_n 为 w 的最长 Lyndon 后缀。\ (3) l_1 为 w 的最长 Lyndon 前缀。

Proof. (1) 设 v 为 w 的最小非空后缀，w = uv。v 的所有非空真后缀也是 w 的非空真后缀，由 v 是 w 的最小后缀可知 v 严格小于其所有非空真后缀，由 命题 5.1.5 可知 v \in L。

若 u = \varepsilon，则 w \in L 即 Lyndon 分解只含一项，命题成立。否则，令 v' 为 u 的最小非空后缀，u = sv'。

若 v' < v，则由 命题 5.1.7 可知 v' v \in L，故由 命题 5.1.5 可知 v' v < v，与 v 的最小性矛盾。

故有 v' \geq v，据此可以递归拆解出 w = v_1 \cdots v_n，满足 v_1 \geq \cdots \geq v_n，再根据 定理 5.1.10 的唯一性可见这无非是 l_i = v_i，遂得证。

(2) 设 s 为 w 的任一 Lyndon 后缀，则由 (1) 可知 l_n \leq s。

若 |l_n| < |s|，则 l_n 为 s 的后缀，由 s \in L 和 命题 5.1.5 可知 s < l_n，矛盾！

故 |l_n| \geq |s|，由 s 的任意性即得 l_n 为 w 的最长 Lyndon 后缀。

(3) 设 p 为 w 的任一 Lyndon 前缀。

若 |p| > |l_1|，设 p = l_1 \cdots l_i u，其中 1 \leq i < n，u 为 l_{i + 1} 的非空前缀。

由 p \in L 和 命题 5.1.5 可知 p < u，而 u \leq l_{i + 1} \leq l_1 \leq p，矛盾！

故 |p| \leq |l_1|，由 p 的任意性即得 l_1 确为最长的 Lyndon 前缀。

上面命题 (1) 给出了一种直截了当但效率不高——每次拆出一个最小非空后缀；接下来讨论另一种思路——增量式维护前缀，这正是大名鼎鼎的 Duval 算法。

让我们来刻画 Lyndon 词的前缀。记 P 为所有作为某个 Lyndon 词的前缀的词的集合：

P = \{w \in A^+ \mid wA^* \cap L \neq \varnothing\}

显见 L \subset P。下面来研究一种特殊的、在后端添加单字母的情况。

推论 5.1.12

设 u, v \in L, u < v，则 \forall k, k' \in \mathbb{N}_+, u^k v^{k'} \in L。

Proof. 由 命题 5.1.7 立即可得。

命题 5.1.13

设 u \in A^*, v \in A^+, uv \in L，若 a \in A, v < a，则 ua \in L。

Proof. u = \varepsilon 的情况是显然的，下设 u \neq \varepsilon。

设 s = u' a 为 ua 的真后缀，则 u' 为 u 的后缀且 u' \neq u，故 u' v 为 uv 的真后缀。

由 uv \in L 和 v < a 可知 uv < u' v < u' a，若 u \in u' aA^*，则有 u' a < uv，矛盾。

故 u \not\in u' aA^*，则由 命题 5.1.2 (2) 可知 u < u' a，进而再由 命题 5.1.2 (2) 可知 ua < u' a，最终由 u' 的任意性证得 ua \in L。

引理 5.1.14

设 w = (uav')^k u，其中 u, v' \in A^*, a \in A, k \in \mathbb{N}_+, uav' \in L，则：\ (1) \forall a' \in A, a' > a \Leftrightarrow wa' \in L。

Proof. (1) 先证必要性。假设 a' \leq a：当 a' < a 时有 wa' = (uav')^k ua' > ua'，则由 命题 5.1.5 可知 wa' \not\in L；当 a' = a 时可见 ua 为 wa' = wa 的非空边界，故由 推论 5.1.6 可知 wa' \not\in L。

再证充分性。由 a < a' 可知 av' < a'，再由 命题 5.1.13 可知 ua' \in L，并有 uav' < ua'。据 uav' \in L 和 推论 5.1.12 即得 wa' = (uav')^k (ua') \in L。

Motivation. 那么压力给到了 a' \leq a 的情况，我们需要讨论何时能够将其保留为某个 Lyndon 词的前缀。\ 当 a' = a，若 uav' 中不止含 A 的最大元（如果存在的话），只需在非最大元下一次周期出现的地方插入最大元，就能使之成为一个 Lyndon 词。\ 否则，uav' 必须恰好为最大元这一个单字符。方便起见，我们对 P 的定义稍加扩展。

下面先对 P 的定义加以扩展，定义 P'：

P' = \begin{cases} P, &\quad A \text{ 中无最大元} \\ P \sqcup \{c^k \mid k \in \mathbb{N}_{\geq 2}\}, &\quad A \text{ 中有最大元 } c \end{cases}

在此基础上阐述 a' \leq a 时的结论：

(2) wa \in P' \backslash L。\ (3) \forall a' \in A, a' < a \Rightarrow wa' \not\in P'。

Proof. (2) 当 A 中无最大元，取 c \in A 使之大于 uav' 中出现过的所有字母，则容易验证 (uav')^{k + 1} c \in L。

当 A 中有最大元 c，若 uav' 退化为 c 则 wa = c^{k + 1} \in P'，否则断言 uav' < c（不然其以 c 开头，这将导出其只含 c，矛盾），由 推论 5.1.12 即得 (uav')^{k + 1} c \in L。

(3) \forall h \in A^*，由 a > a' 可知 wa' h = (uav')^k ua' h > ua' h，由 命题 5.1.5 即得 wa' \not\in P'。

上面引理的结论提示我们，P' 中的元素似乎总能表示为某一 Lyndon 词重复多次、再加上一个不完整的周期。形式化地说，记 S 为所有 Lyndon 词的 严格半幂 (strict sesquipower) 构成的集合：

S = \{(uv)^k u \mid u \in A^*, v \in A^+, uv \in L, k \in \mathbb{N}_+\}

命题 5.1.15 (前缀候选集 \Leftrightarrow 严格半幂集)

Proof. S \subset P' 部分的证明同 引理 5.1.14 (2)，不再赘述。

下证 P' \subset S。首先显见 L \subset S，其次需证 P' \backslash L \subset S，考虑对长度归纳：

综上，明所欲证。

命题 5.1.16 (前缀增量时标准分解式的变化)

设 u, v' \in A^*, a \in A, k \in \mathbb{N}_+, uav' \in L，记 \text{CFL}(x) 为 x \in A^* 的标准分解式。\ (1)

\text{CFL}((uav')^k u) = (uav')^k \cdot \text{CFL}(u)

(2) 设 w = (uav')^k ua' h，其中 a' \in A, h \in A^*, a' < a，则：

\text{CFL}(w) = (uav')^k \cdot \text{CFL}(ua' h)

Proof. (1) 设 (uav')^i s 为 (uav')^k u 的 Lyndon 前缀，其中 1 \leq i \leq k，s 为 uav' 的真前缀。

综上，在 (uav')^k u 的长度 \geq |uav'| 的前缀中只有 uav' 这一个为 Lyndon 词，故其最长 Lyndon 前缀为 uav'。由 命题 5.1.11 (3) 可知 \text{CFL}((uav')^k u) 的首项恰为 uav'，剥去后剩余 (uav')^{k - 1}u，于是

\text{CFL}((uav')^k u) = uav' \cdot \text{CFL}((uav')^{k - 1} u),

而 k = 0 的情形平凡地成立，故对 k 归纳即得 \text{CFL}((uav')^k u) = (uav')^k \cdot \text{CFL}(u)。

(2) 由 引理 5.1.14 (3) 可知 (uav')^k ua' \not\in P'，于是 w 的最长 Lyndon 前缀无异于 (uav')^k u 的最长 Lyndon 前缀，同 (1) 可见这无非是 uav'，故再由 命题 5.1.11 (3) 可知 w 的标准分解式的首项正是 uav'。随后同样对 k 归纳即得。

算法 5.1.17 (Duval 算法)

输入：词 w \in A^+。\ 输出：分解式序列 [l_1, \cdots, l_n] \in L^n，满足 w = l_1 \cdots l_n, l_1 \geq \cdots \geq l_n。\ 状态类别：三元组 ([l_1, \cdots, l_n], \text{null}, w) 或 ([l_1, \cdots, l_n], (u, av', k), w)。\ 初始状态：([], \text{null}, w)。\ 转移 I / 析出：([l_1, \cdots, l_n], \text{null}, aw') \Rightarrow ([l_1, \cdots, l_n], (\varepsilon, a, 1), w')\ 转移 II / 大字移进：当 a' > a，([l_1, \cdots, l_n], (u, av', k), a' w') \Rightarrow ([l_1, \cdots, l_n], (\varepsilon, (uav')^k ua', 1), w')\ 转移 III / 同字移进：([l_1, \cdots, l_n], (u, av', k), aw') \Rightarrow ([l_1, \cdots, l_n], (ua, v', k), w')\ 转移 IV / 周期更新：([l_1, \cdots, l_n], (u, \varepsilon, k), w) \Rightarrow ([l_1, \cdots, l_n], (\varepsilon, u, k + 1), w)\ 转移 V / 词尾：([l_1, \cdots, l_n], (u, av', k), \varepsilon) \Rightarrow ([l_1, \cdots, l_n] + [uav']^k, \text{null}, u)\ 转移 VI / 小字移进：当 a' < a，([l_1, \cdots, l_n], (u, av', k), a' w') \Rightarrow ([l_1, \cdots, l_n] + [uav']^k, \text{null}, ua' w')\ 终止状态：([l_1, \cdots, l_n], \text{null}, \varepsilon)，此时输出 [l_1, \cdots, l_n]。

正确性证明： 算法维护的不变式为，当状态为 ([l_1, \cdots, l_n], (u, av', k), a' w') 时，已输出的部分 [l_1, \cdots, l_n] 满足 l_1, \cdots, l_n \in L，未输出部分的前缀 (uav')^k u 满足 uav' \in L；输出序列的单调不增性则由下文输出时的论证保证。各转移规则的正确性依据如下：

下面证明每次改变分解式序列后，输出序列仍单调不增。设 n \in \mathbb{N}_+，l_n 为最近一次输出所加入的因子，记当时加入的因子为 l_n = u_0 a_0 v_0'，输出后剩余部分为 r：转移 V 时 r = u_0，转移 VI 时 r = u_0 a_0' w_0'（a_0' < a_0 为当时读入的字母）。

而自那以来未发生输出，仅经转移 I–IV 演化，设当前未输出的前缀为 (uav')^k u（其为 r 的前缀）。对接下来加入因子的转移分类讨论：

故新加入的 k 个因子 uav' 均不超过已输出末项 l_n，输出序列保持单调不增。

时间复杂度： 将比较分为两类：

综上，总比较次数 \leq 2|w|，而周期更新的次数不会超过同字移进的次数故也 \leq |w|，因而总时间复杂度为 O(|w|)。

实现中，可以用指针 i 指示未输出部分的开头，用指针 j 指示当前匹配到周期中对应位置的下标，用指针 k 指示当前未处理的首个字符的下标，详见代码。

实现（Luogu P6114 【模板】Lyndon 分解）：

#include <stdio.h>
#include <string.h>

int pos[5000001];
char s[5000001];

int lyndon_decompose(char s[], int ans[]){
    int n = strlen(s), m = 0;
    int i = 0;
    while (i < n){
        int j = i, k = i + 1;
        while (k < n && s[k] >= s[j]){
            if (s[k] > s[j]){
                j = i;
            } else {
                j++;
            }
            k++;
        }
        int d = k - j;
        while (i <= j){
            i += d;
            ans[m++] = i;
        }
    }
    return m;
}

int main(){
    scanf("%s", s);
    int m = lyndon_decompose(s, pos), ans = 0;
    for (int i = 0; i < m; i++){
        ans ^= pos[i];
    }
    printf("%d", ans);
    return 0;
}

5.2 自由幺半群的二分

定义 5.2.1 (二分)

称 (X, Y) \in \mathcal{P}(A^+)^2 为 A^* 的一个二分，若任一 w \in A^* 均可唯一表作：

w = x_1 \cdots x_r y_1 \cdots y_s

其中 r, s \in \mathbb{N}, x_i \in X, y_i \in Y。

命题 5.2.2

w = xy, \quad x \in X^*, y \in Y^*

Proof. 由定义立即可得。

例子 5.2.3

设 A = \{a, b\}，令 X = a^* b, Y = \{a\}，容易验证 (X, Y) 为 A^* 的一个二分。

命题 5.2.4 (二分条件的形式级数表示 I)

Proof. 考虑形式级数的组合意义，由定义立即可得。

命题 5.2.5 (二分条件的形式级数表示 II)

Proof. 两个方向都有 X, Y 为码的前提，在此基础上：

\begin{array}{l} & (X, Y) \text{ 为 } A^* \text{ 的一个二分} \\ \Leftrightarrow & \underline{A}^* = \underline{X}^* \underline{Y}^* &\quad (\textbf{命题 5.2.4}) \\ \Leftrightarrow & \underline{A}^* (1 - \underline{Y})(1 - \underline{X}) = 1 &\quad (\textbf{命题 1.4.2}) \\ \Leftrightarrow & (1 - \underline{Y})(1 - \underline{X}) = 1 - \underline{A} &\quad (\textbf{命题 1.4.2}) \\ \Leftrightarrow & \underline{Y} \cdot \underline{X} + \underline{A} = \underline{X} + \underline{Y} \end{array}

明所欲证。

例子 5.2.3 [续]

在此例中，上面命题给出的等式为：

\underline{a} \cdot \underline{a^* b} + (\underline{a} + \underline{b}) = \underline{a} + \underline{a^* b}

可见其显然成立。

命题 5.2.6

> (1) $YX \cup A \subset X \cup Y$。\ > (2) $X \cap Y = \varnothing$。\ > (3) 任一 $w \in (X \cup Y) \backslash A$ 均可唯一表作 $w = yx \ (y \in Y, x \in X)$ 的形式。

Proof. 先证必要性。若 X \cap Y \neq \varnothing 则交集中的词至少有两种分解方式，矛盾，故 (2) 成立。进而 (1)(3) 由 命题 5.2.5 等式的组合意义立即可得。

再证充分性。由 命题 5.2.5 欲证 \underline{Y} \cdot \underline{X} + \underline{A} = \underline{X} + \underline{Y}，据 命题 1.4.3 (1)(2) 可知这无非是说：

由 (1) 可知 YX \subset X \cup Y，又注意到 YX 中的词均非单字母，故 YX \cap A = \varnothing，进而 YX \subset (X \cup Y) \backslash A，再结合 (3) 就证得了 (i)。

(i) 的证明和 (2) 给出 (ii) 中两个并无交，再结合 (1) 只需证明 X \sqcup Y \subset YX \sqcup A，而 (3) 指出 (X \sqcup Y) \backslash A \subset YX，明所欲证。

命题 5.2.7

设 X, Y \subset A^+, X \cap Y = \varnothing，则 (X, Y) 为 A^* 的一个二分当且仅当 YX \cup A = X \cup Y。

Proof. 必要性由 命题 5.2.5 等式的组合意义立即可得。

再证充分性，无非是分为存在和唯一两步。

存在性： 由 A \subset X \cup Y 可知任一 w \in A^* 均可写成若干 X \cup Y 片段的组合 z_1 \cdots z_n。

取 n 最小的分解方式，若 z_i \in Y \ (1 \leq i < n)，假设 z_{i + 1} \in X，由 YX \subset X \cup Y 可知 z_i z_{i + 1} 可以替换为一个 X \cup Y 片段，与 n 的最小性矛盾！故 z_{i + 1} \in Y，进而可以推知 z_i, \cdots, z_n \in Y。故而这一分解方式由若干 X 片段和若干 Y 片段依次拼接而成，满足条件。

唯一性： 首先证明下列引理：

引理 5.2.8

(1) \forall u, v \in A^*, uv \in X \Rightarrow v \in X^*。\ (2) \forall u, v \in A^*, uv \in Y \Rightarrow u \in Y^*。

Proof. 下面只证明 (1)，(2) 是同理的。\ 设 x = uv \in X，若 v = \varepsilon 或 v = x 命题显然成立，下面讨论 v 为 x 的真后缀的情况。\ 考虑对 |x| 归纳。|x| = 1 显然，下面讨论 |x| > 1 的情况。\ 由 YX \cup A = X \cup Y 可知 X \subset YX \cup A，而此时 x \not\in A，故 x \in YX，则可以写成 x = yx_1 \ (y \in Y, x_1 \in X) 的形式。\ 下面对 |y| 归纳证明 y 总能写成 y = y' x_k \cdots x_2 \ (y' \in Y \cap A, x_i \in X) 的形式：

(i) 当 |y| = 1，有 y \in Y \cap A。 (ii) 当 |y| > 1，此时亦有 y \in YX，则可以写成 y = y' x_2 \ (y' \in Y, x_2 \in X) 的形式，根据归纳假设展开 y' 即得。

因此 x 可以表作 x = y' x_k \cdots x_1，则 v 为 x_k \cdots x_1 的后缀。\ 设 v = p x_{i - 1} \cdots x_1，其中 1 \leq i \leq k 且 p 为 x_i 的后缀，由 |x_i| < |x|，据归纳假设即得 p \in X^*，故 v \in X^*，明所欲证。

并给出一个拓展到 X^*, Y^* 上的简单推论：

推论 5.2.9

(1) \forall u, v \in A^*, uv \in X^* \Rightarrow v \in X^*。\ (2) \forall u, v \in A^*, uv \in Y^* \Rightarrow u \in Y^*。

Proof. 照例只证明 (1)，(2) 是同理的。\ 设 uv = x_1 \cdots x_n \ (x_i \in X)，则 v 可以表作 p x_{i + 1} \cdots x_n，其中 1 \leq i \leq n，p 为 x_i 的后缀。\ 在 引理 5.2.8 (1) 中取 uv = x_i 即得 p \in X^*，故有 v \in X^*。

首先说明精确到 X^*, Y^* 的分解唯一。设 w \in A^* 有两种分解 w = xy = x' y' \ (x, x' \in X^*, y, y' \in Y^*)，不妨设 x 为 x' 的前缀，x' = xu，则由 推论 5.2.9 (1) 可知 u \in X^*；同时注意到 y = uy'，则由 推论 5.2.9 (2) 可知 u \in Y^*。

欲证 u = \varepsilon，只需证明下面的引理：

引理 5.2.10\

_Proof._ 只需证明 $\forall n \in \mathbb{N}_+, X^* \cap Y^* \cap A^n = \varnothing$，考虑对 $n$ 归纳。\ 假设 $w = x_1 \cdots x_p = y_1 \cdots y_q \in A^n \ (p, q \in \mathbb{N}_+, x_i \in X, y_j \in Y)$。\ 由 **推论 5.2.9 (1)** 可知 $y_2 \cdots y_q \in X^*$，然而 $y_2 \cdots y_q \in Y^*$，由归纳假设可知 $y_2 \cdots y_q = \varepsilon$，即 $q = 1$。\ 同理，由 **推论 5.2.9 (2)** 可知 $x_1 \cdots x_{p - 1} \in Y^*$，然而 $x_1 \cdots x_{p - 1} \in X^*$，由归纳假设可知 $x_1 \cdots x_{p - 1} = \varepsilon$，即 $p = 1$。\ 综上有 $p = q = 1$，故 $w = x_1 = y_1$，与 $X \cap Y = \varnothing$ 矛盾，明所欲证。

接下来说明 X, Y 自身分别是码，这里只证前者，后者依然是同理的。

设 w \in X^* 有两种分解 w = x_1 \cdots x_n = x'_1 \cdots x'_m \ (n, m \in \mathbb{N}, x_1, \cdots, x_n, x'_1, \cdots, x'_m \in X)，考虑对 w 的长度归纳。|w| = 0 显然，下面讨论 |w| > 0 的情况，此时 n, m \in \mathbb{N}_+。

不妨设 x_1 为 x'_1 的前缀，若 x_1' \in A 则必有 x_1 = x_1'；否则由 X \subset YX 将 x'_1 表作 yz \ (y \in Y, z \in X)，若 x_1 为 y 的前缀则由 推论 5.2.9 (2) 可知 x_1 \in Y^*，与 引理 5.2.10 矛盾！故 y 为 x_1 的前缀，设 x_1 = ys，则由 引理 5.2.8 (1) 可知 s \in X^*，并有 sx_2 \cdots x_n = zx_2' \cdots x_m'。

由 x_1 为 x'_1 的前缀可知 s 为 z 的前缀，设 z = sw，由 引理 5.2.8 (1) 可知 w \in X^*。据归纳假设可知 z 有唯一分解为其自身，则 s = \varepsilon, w = z 或 s = z, w = \varepsilon。

若为前者则 x_1 = y \in X \cap Y，矛盾！故为后者，则 x_1 = x_1'。对 x_2 \cdots x_n = x'_2 \cdots x'_m 应用归纳假设即可。

推论 5.2.11

设 (P, Q) 为 A^+ 的划分（即 P \sqcup Q = A^+），则 \exists ! (X, Y) 为 A^* 的二分，\text{s.t. } X \subset P, Y \subset Q。

Proof. 先证存在性，考虑按照长度从小到大依次构造。

设 X_n = X \cap A^n, Y_n = Y \cap A^n，则 X = \displaystyle\bigsqcup_{n \in \mathbb{N}_+} X_n, Y = \bigsqcup_{n \in \mathbb{N}_+} Y_n。

当 n = 1，令 X_n = P \cap A, Y_n = Q \cap A 即可。

当 n > 1，为满足 YX \cup A = X \cup Y，X_n, Y_n 中的词只能来源于（所欲构造的 X, Y 对应的）YX \cap A^n，用已构造的部分来说就是 S_n \triangleq \displaystyle\left( \bigsqcup_{n' < n} Y_{n'} \right) \left( \bigsqcup_{n' < n} X_{n'} \right) \cap A^n，而其自然地也被 P, Q 不交地划分，令 X_n = S_n \cap P, Y_n = S_n \cap Q 即可。

再证唯一性。对 n 归纳即可说明各对 (X_n, Y_n) 即得，细节略去。

该推论表明，为构造 A^* 的一个二分，可先将 A 分配给 X, Y，再按 n 从小到大依次将当前的 YX \cap A^n 分配给 X, Y 即可。

例子 5.2.12

设 A = \{a, b\}，下面给出了一个 A^* 的二分：

n X Y
1 a b
2 ba
3 b^2 a
\geq 4 S

其中 S = (\{b, b^2 a\} (S \cup \{a, ba\})) \cap A^{\geq 4} = b^2 a \{a, ba\} \cup \{b, b^2 a\} S，解得显式表示：

S = \{b, b^2 a\}^* (b^2 a \{a, ba\})

即 X = \{a, ba\} \cup \{b, b^2 a\}^* (b^2 a \{a, ba\}), Y = \{b, b^2 a\}。

接下来讨论：当给定一个二分 (X, Y)，我们如何将一个给定的词切分为若干 X 中的词和若干 Y 中的词依次拼接的形式？一个自然的想法是构造自动机来“识别”这个给定的词。下面的命题则给出了一个精妙的构造。

命题 5.2.13

Proof. 先证必要性。构造 Q = \{u^{-1} X^* \mid u \in A^*\}，其中 u^{-1} X^* \triangleq \{v \in A^* \mid uv \in X^*\}。

由 推论 5.2.9 (1) 可知 u^{-1} X^* \subset X^*。通过集合的包含关系为 Q 赋予偏序，则其有最大元为 q_+ = X^* = \varepsilon^{-1} X^*。

接下来对任一 w \in A^* 定义 \forall u \in A^*, \alpha(w)(u^{-1} X^*) = (uw)^{-1} X^*：

然后证明 \alpha 为幺半群同态，即证 \forall u, v \in A^*, \alpha(uv) = \alpha(v) \circ \alpha(u)：这无非是定义的操演。

易证 x \in X^* 时有 \alpha(x) X^* = X^*，而当 x \not\in X^* 时 \varepsilon \not\in x^{-1} X^*、故 \alpha(x) X^* \neq X^*。总之 X^* = \{x \in A^* \mid \alpha(x) q_+ = q_+\}。

由 \underline{X}^* \underline{Y}^* = \underline{A}^* 可知 \underline{Y}^* = (1 - \underline{X}) \underline{A}^* = \underline{A}^* - \underline{X} \underline{A}^* = \underline{A^* \backslash XA^*}，故 Y^* = A^* \backslash XA^*。

再证充分性。任给 w \in A^*，在其有限多个前缀中取满足 \alpha(x)q_+ = q_+ 的最长者 x，令 w = xy；则由 x 的最长性，对 y 的任一非空前缀 u 都有 \alpha(u)(q_+) < q_+。

令 P = A^* \backslash XA^* = \{y \in A^* \mid \forall u \in A^+, v \in A^*, y = uv \Rightarrow u \not\in X\}，则易证 P = \{y \in A^* \mid \forall u \in A^+, v \in A^*, y = uv \Rightarrow u \not\in X^*\} = \{y \in A^* \mid \forall u \in A^+, v \in A^*, y = uv \Rightarrow \alpha(u) q_+ < q_+\}，随后考察 P 的性质：

综上可知 P 为自由幺半群。取 Y 为其基，则有 \underline{Y}^* = \underline{A^* \backslash XA^*} = \underline{A}^* - \underline{X} \underline{A}^* = (1 - \underline{X}) \underline{A}^*，进而有 \underline{X}^* \underline{Y}^* = \underline{A}^*，即 (X, Y) 为 A^* 的二分。

基于上面的命题，可以构造如下（可能无限的）确定性自动机：

状态空间：Q。\ 字符集：A。\ 转移函数：\delta(q, a) = \alpha(a)(q)。\ 起始状态：q_+。\ 接受状态集合：\{q_+\}。

- (i) 由幺半群同态的性质立即可得 $x \in X^*$。 - (ii) 若 $y \not\in Y^*$ 则存在 $u \in X$ 为 $y$ 的前缀，于是 $xu \in X^*$，与 $x$ 的最长性矛盾！故 $y \in Y^*$。 #### 例子 5.2.12 [续] 在此例中，取 $Q = \{1, 2, 3, 4\}$，定义偏序 $3 < 2 < 1, 4 < 1$，有 $q_+ = 1$，作出状态图 ([1] Figure 5.1) 如下： ![](https://cdn.luogu.com.cn/upload/image_hosting/9bgqiv55.png) #### 例子 5.2.14 设 $\sigma : A^* \to (\mathbb{Z}, +)$ 为幺半群同态，定义： $$ \begin{cases} P = \{p \in A^* \mid \sigma(p) > 0\} \cup \{\varepsilon\} \\ N = \{n \in A^* \mid \sigma(n) \leq 0\} \end{cases} $$ 进一步地，定义： $$ \begin{cases} R = \{r \in A^* \mid \forall u, v \in A^*, r = uv \Rightarrow v \in P\} \\ S = \{s \in A^* \mid \forall u, v \in A^*, s = uv \Rightarrow u \in N\} \end{cases} $$ 显然 $R$ 中包含其每个元素的所有后缀、$S$ 中包含其每个元素的所有前缀，由 **命题 1.2.3** 可知 $R, S$ 是自由的。记 $X, Y$ 分别为 $R, S$ 的基。 断言 $(X, Y)$ 为 $A^*$ 的二分：任给 $w \in A^*$，取 $r$ 为 $w$ 的最短前缀使其 $\sigma$ 值最大，令 $w = rs$，则 $r \in R, s \in S$；同时容易验证 $r, s$ 的选取唯一。 下面通过这个例子来解决一个概率论中的经典问题。 #### 定理 5.2.15 (Sparre-Andersen 等价原理, 1971) > 对 $w \in A^*$ 记： > $$ > \begin{cases} > L(w) = \#\{u \in P \backslash \{\varepsilon\} \mid w \in uA^*\} \\ > \Pi(w) = |r|, &\quad w = rs, r \in R, s \in S > \end{cases} > $$ > 则存在**双射** $\rho : A^* \to A^*$，使得 $L(w) = \Pi(\rho(w))$。 _Proof._ 如下归纳定义 $\rho$： $$ \begin{cases} \rho(\varepsilon) = \varepsilon \\ \rho(wa) = a \rho(w), &\quad w \in A^*, a \in A, wa \in P \\ \rho(wa) = \rho(w) a, &\quad w \in A^*, a \in A, wa \in N \end{cases} $$ 可见其有逆映射 $\tau$： $$ \begin{cases} \tau(\varepsilon) = \varepsilon \\ \tau(aw) = \tau(w) a, &\quad w \in A^*, a \in A, aw \in P \\ \tau(wa) = \tau(w) a, &\quad w \in A^*, a \in A, wa \in N \end{cases} $$ 故 $\rho$ 为双射。 设 $w \in A^*$，$w = \varepsilon$ 时显然，下面讨论 $w \neq \varepsilon$ 的情况： - (i) 若 $w \in P$，设 $u$ 为 $w$ 的长度最大且在 $N$ 中的前缀，$w = uv$，则归纳可知 $\rho(w) = \tilde{v} \rho(u)$，其中 $\tilde{v}$ 为 $v$ 的反转，则 $L(w) = L(u) + |v|, \Pi(\rho(w)) = |v| + \Pi(\rho(u))$。 - (ii) 若 $w \in N$，设 $u$ 为 $w$ 的长度最大且在 $P$ 中的前缀，$w = uv$，则归纳可知 $\rho(w) = \rho(u) v$，则 $L(w) = L(u), \Pi(\rho(w)) = \Pi(\rho(u))$。 由于此时 $|u| < |w|$，对 $|w|$ 归纳即可。 ------ 将 $w = a_1 \cdots a_n \in A^*$ 视作 $s = (\sigma(a_1), \cdots, \sigma(a_n)) \in \mathbb{Z}^n$，则 $L(w)$ 表示 $s$ 的求和为正的前缀数量，$\Pi(w)$ 表示 $s$ 的首个求和最大的前缀长度（允许为 $0$），而二者借由 $\rho$ 具有了某种“等价的分布”，这正是定理名称的由来。 ### 5.3 自由 Lie 代数 #### 定义 5.3.1 (交换环上的代数, Lie 代数, 自由 Lie 代数) 设 $K$ 为交换幺环，$K$-结合代数指一个兼具环与 $K$-模结构的集合 $R$，使得环的加法等于 $K$-模的加法、且环的乘法满足： $$ (rx)y = x(ry) = r(xy), \quad \forall x, y \in R, r \in K $$ $K$ 上的 Lie 代数 $\mathfrak{L}$ 指这样的一种 $K$-代数，其乘法用 Lie 括号 $[\cdot, \cdot] : \mathfrak{L} \times \mathfrak{L} \to \mathfrak{L}$ 表示，且满足如下两个性质： - (1) 交替性：$\forall x \in \mathfrak{L}, [x, x] = 0$。 - (2) Jacobi 恒等式：$\forall x, y, z \in \mathfrak{L}, [[x, y], z] + [[y, z], x] + [[z, x], y] = 0$。 由交替性与双线性可推出反对称性 $[x, y] = -[y, x]$（对 $[x+y, x+y] = 0$ 展开即得），(2) 可以移项为 $[[x, y], z] = [x, [y, z]] - [y, [x, z]]$。注意在一般交换环上（含 $2$-挠元或特征 $2$ 时）反对称性不能反过来推出交替性，故必须把交替性作为定义条件。 特别地，任给 $K$-结合代数 $R$，容易验证 Lie 括号 $$ [x, y] = xy - yx $$ 使 $K$-模 $R$ 成为 $K$ 上的 Lie 代数，记作 $R_L$。 当 $R$ 为 $A$ 上的自由结合代数 $K \langle A \rangle$（可视作变量不交换的多项式环），称 $R_L$ 的由 $A$ 生成（即只能使用加法、数乘和 Lie 括号进行有限次运算）的子代数为 $A$ 上的自由 Lie 代数，记作 $\mathfrak{L}_K(A)$ 或简称 $\mathfrak{L}(A)$。 > _Rmk._ 这里的“自由”二字将在后面予以证明。 对于 $n \in \mathbb{N}$，记 $R_n, \mathfrak{L}_n(A)$ 分别表示 $R, \mathfrak{L}(A)$ 中由 $n$ 次齐次元素生成的子模，则有： $$ \begin{cases} \mathfrak{L}(A) = \displaystyle\bigoplus_{n \geq 1} \mathfrak{L}_n(A) \\ \mathfrak{L}_0(A) = 0, \mathfrak{L}_1(A) = R_1 \\ \mathfrak{L}_{n + 1}(A) = \displaystyle\sum_{i = 1}^n [\mathfrak{L}_i(A), \mathfrak{L}_{n - i + 1}(A)], &\quad \forall n \in \mathbb{N}_+ \end{cases} $$ 其中对子模 $M_1, M_2$ 而言，$[M_1, M_2]$ 表示由所有 $[m_1, m_2], m_i \in M_i$ 生成的子模。 #### 命题 5.3.2 > $\forall n \in \mathbb{N}_+, \mathfrak{L}_{n + 1}(A) = [\mathfrak{L}_1(A), \mathfrak{L}_n(A)]$。 _Proof._ 考虑对 $n$ 归纳，$n = 1$ 的情况由定义直接给出（$\mathfrak{L}_2(A) = [\mathfrak{L}_1(A), \mathfrak{L}_1(A)]$），下面考虑 $n > 1$。 易见只需证明 $\forall 1 \leq i \leq n, [\mathfrak{L}_i(A), \mathfrak{L}_{n - i + 1}(A)] \subset [\mathfrak{L}_1(A), \mathfrak{L}_n(A)]$。考虑对 $i$ 归纳，$i = 1$ 的情况显然，下面考虑 $1 < i \leq n$。 考虑 $p \in \mathfrak{L}_i(A), q \in \mathfrak{L}_{n - i + 1}(A)$ 对应的 $[p, q]$，由归纳假设可知 $p \in [\mathfrak{L}_1(A), \mathfrak{L}_{i - 1}(A)]$，令 $p = [p_1, p_2] \ (p_1 \in \mathfrak{L}_1(A), p_2 \in \mathfrak{L}_{i - 1}(A))$，则有： $$ [p, q] = [[p_1, p_2], q] = [p_1, [p_2, q]] - [p_2, [p_1, q]] \in [\mathfrak{L}_1(A), \mathfrak{L}_n(A)] + [\mathfrak{L}_{i - 1}(A), \mathfrak{L}_{n - i + 2}(A)] $$ 由归纳假设即得 $[p, q] \in [\mathfrak{L}_1(A), \mathfrak{L}_n(A)]$。明所欲证。 ------ 下面通过给出一组基的方式证明 $K$-模 $\mathfrak{L}(A)$ 是自由的。 #### 定理 5.3.3 > 设 $A$ 上有全序 $\leq$，$L$ 为 $A$ 上的 Lyndon 词构成的集合，递归定义映射 $\lambda : L \to \mathfrak{L}(A)$： > $$ > \begin{cases} > \lambda(a) = a, &\quad a \in A \\ > \lambda(l) = [\lambda(m), \lambda(n)], &\quad l \in L \backslash A, \sigma(l) = (m, n) > \end{cases} > $$ > 则 $K$-模 $\mathfrak{L}(A)$ 自由，且以 $\lambda(L)$ 为一组基。 _Proof._ 先证下面两个引理。 > **引理 5.3.4** > > $\forall k \in \mathbb{N}_+, l \in L \cap A^k$，设 $\lambda(l) = l + r$，则 $r$ 属于 $A^k$ 中大于 $l$ 的词所生成的 $K \langle A \rangle$ 的子模。 > > _Proof._ 考虑对 $k$ 归纳，$k = 1$ 的情况显然，下面考虑 $k > 1$ 的情况。\ 设 $\sigma(l) = (m, n)$，由归纳假设 $\lambda(m) = m + r, \lambda(n) = n + s$，其中 $r, s$ 分别属于 $A^{|m|}$ 中大于 $m$ 的词、$A^{|n|}$ 中大于 $n$ 的词所生成的 $K \langle A \rangle$ 的子模，则有： > $$ > \lambda(l) = [m + r, n + s] = l + ms + r(n + s) - nm - nr - s(m + r) > $$ > 由于 $l = mn < n$，容易验证 $\lambda(l) - l$ 中各项都属于 $A^k$ 中大于 $l$ 的词所生成的子模，明所欲证。 为声明下一引理，首先对 $k \in \mathbb{N}_{\geq 2}$ 定义： $$ X_k = \{(m, n) \in L^2 \mid m < n, mn \in A^k\} $$ 并给出其上的全序：称 $(m, n) < (m', n')$ 当且仅当 $mn > m' n'$ 或 $mn = m' n' \land m < m'$。 > **引理 5.3.5** > > $\forall (m, n) \in X_k$，$[\lambda(m), \lambda(n)]$ 属于 $\{\lambda(l) \mid l \in L \cap A^k, \sigma(l) \leq (m, n)\}$ 所生成的 $\mathfrak{L}(A)$ 的子模。 > > _Proof._ 首先对 $k$ 归纳、然后对 $X_k$ 按照上面的全序归纳。 > 设结论对所有满足 $j < k$ 或 $j = k \land (u, v) < (m, n)$ 的 $(u, v) \in X_j$ 都成立。 > - (i) 若 $m \in A$，容易验证 $(m, n)$ 为标准分解，故 $[\lambda(m), \lambda(n)] = \lambda(mn)$，命题成立。 > - (ii) 若 $m \in L \backslash A$，设 $\sigma(m) = (u, v)$，若 $n \leq v$ 则由 **命题 5.1.9** 可知 $(m, n)$ 为标准分解，命题成立。 > - 下面讨论 $v < n$ 的情况，有： > $$ [\lambda(m), \lambda(n)] = [\lambda(u), [\lambda(v), \lambda(n)]] - [\lambda(v), [\lambda(u), \lambda(n)]] $$ > - 对于前者，由于 $|vn| < k$，据归纳假设可将 $[\lambda(v), \lambda(n)]$ 表作： > $$ [\lambda(v), \lambda(n)] = \sum_{i = 1}^s \alpha_i \lambda(w_i), \quad \alpha_i \in K, w_i \in L \cap A^{|vn|}, \sigma(w_i) \leq (v, n) $$ > - 故有： > $$ [\lambda(u), [\lambda(v), \lambda(n)]] = \sum_{i = 1}^s \alpha_i [\lambda(u), \lambda(w_i)] $$ > - 此处 $|uw_i| = k$；同时 $\sigma(w_i) \leq (v, n)$ 指出 $vn \leq w_i$，则 $uvn \leq uw_i$；又由 **定义 5.1.8** 可知 $u < v$，且 $v$ 为 $vn$ 的真前缀，故 $u < w_i$，即 $(u, w_i) \in X_k$。而 $u < uv = m$ 恒成立，故 $(u, w_i) < (m, n)$。 > - 因此据归纳假设可将 $[\lambda(u), \lambda(w_i)]$ 表作： > $$ [\lambda(u), \lambda(w_i)] = \sum_{j = 1}^{t_i} \beta_{i, j} \lambda(x_{i, j}), \quad \beta_{i, j} \in K, x_{i, j} \in L \cap A^k, \sigma(x_{i, j}) \leq (u, w_i) $$ > - 此处 $\sigma(x_{i, j}) \leq (u, w_i) < (m, n)$，故可将 $[\lambda(u), [\lambda(v), \lambda(n)]]$ 表作： > $$ [\lambda(u), [\lambda(v), \lambda(n)]] = \sum_{i = 1}^s \sum_{j = 1}^{t_i} \alpha_i \beta_{i, j} \lambda(x_{i, j}) $$ > - 其属于目标子模。类似地，可以证明 $[\lambda(v), [\lambda(u), \lambda(n)]]$ 也属于目标子模。明所欲证。 综上，**引理 5.3.4** 指出 $\lambda(L)$ 中元素的非零线性组合的表示中一定含有原本最小的一项故而非零、进而导出 $\lambda(L)$ 线性无关，**引理 5.3.5** 指出 $\lambda(L)$ 生成的子模是 $\mathfrak{L}(A)$ 的一个子代数，又由于其包含 $A$ 故恰好为 $\mathfrak{L}(A)$。明所欲证。 #### 例子 5.3.6 这里展示 **引理 5.3.5** 中分解的一个例子。设 $A = \{a, b, c\}$ 并给定全序 $a < b < c$，且有： $$ [[a, b], c] = [a, [b, c]] - [b, [a, c]] = [a, [b, c]] + [[a, c], b] $$ 其中 $abc, acb \in L$ 且 $\sigma(abc) = (a, bc), \sigma(acb) = (ac, b)$，二者都 $\leq (ab, c)$，并有 $[\lambda(ab), \lambda(c)] = \lambda(abc) + \lambda(acb)$。 #### 推论 5.3.7 (Witt 公式) > 设 $k = |A|$ 有限，则 $\text{dim} \mathfrak{L}_n(A) = \Psi_k(n)$。 _Proof._ $\text{dim} \mathfrak{L}_n(A) = |L \cap A^n| = \Psi_k(n)$。 ------ 在 Lie 代数中，Lie 括号没有结合律，使得计算不便，现考虑找一个**结合**的代数，将 Lie 代数嵌入其中，使得 Lie 括号恰好表现为交换子 $[x, y] = xy - yx$ ——这正是反 $R \to R_L$ 之道而行之。 #### 定义 5.3.8 (包络代数) 设 $\mathfrak{L}$ 为交换幺环 $K$ 上的 Lie 代数，定义其包络代数为结合代数 $U$ 和态射 $\varphi : \mathfrak{L} \to U_L$，使得对于所有结合代数 $S$ 和态射 $\psi : \mathfrak{L} \to S_L$，存在唯一态射 $\theta : U \to S$，使得下图交换： ![](https://cdn.luogu.com.cn/upload/image_hosting/o4nq2yxs.png) ------ 下面假设 $\mathfrak{L}$ 为自由 $K$-模：我们已知当 $K$ 为域或 $\mathfrak{L}$ 为自由 Lie 代数 $\mathfrak{L}(A)$（**定理 5.3.3**）时如此。 设 $E$ 为 $\mathfrak{L}$ 的一组基，考察双射 $\varphi : E \to B$，诱导出自由模的同构 $K(\varphi) : \mathfrak{L} \to K[B]$，这就在 $K[B]$ 上确立了一个 $K$ 上的 Lie 代数的结构： $$ [x, y] = K(\varphi)([p, q]), \quad x, y \in K[B], x = K(\varphi)(p), y = K(\varphi)(q) $$ 给 $B$ 赋予全序，并考虑 $B^*$ 的如下子集： $$ F = \{b_1 \cdots b_n \mid n \in \mathbb{N}, b_i \in B, b_1 \geq \cdots \geq b_n\} $$ 对 $w \in B^*$ 定义 $\nu(w)$ 为 $w$ 的顺序数，或者形式化地说：即三元组 $(r, s, t)$ 的数量，使得 $w = rasbt$，其中 $a, b \in B, a < b$。显然有如下性质： - (1) $\nu(w) = 0 \Leftrightarrow w \in F$。 - (2) 当 $a, b \in B, a < b$，由 $\nu(uabv) = \nu(ubav) + 1$。 #### 引理 5.3.9 > 存在唯一的 $K \langle B \rangle$ 的 $K$-模自同态 $\lambda$，使得： > > (1) $\forall f \in F, \lambda(f) = f$。\ > > (2) $\forall u, v \in B^*, a, b \in B, \lambda(uabv) = \lambda(u [a, b] v) + \lambda(ubav)$。 > > 进一步地，$\text{Im}(\lambda) = K[F]$，且有： > > (3) $\forall u, v \in K \langle B \rangle, \lambda(uv) = \lambda(\lambda(u) v) = \lambda(u \lambda(v))$。 _Proof._ 先证唯一性和 $\text{Im}(\lambda) = K[F]$。对 $(|w|, \nu(w))$ 递增归纳： - (i) 当 $w \in F$，(1) 确定 $\lambda(w) = w \in K[F]$。 - (ii) 当 $w \not\in F$，存在 $u, v \in B^*, a, b \in B$ 使得 $w = uabv$ 但 $a < b$，由 (2) 可知 $\lambda(w) = \lambda(u [a, b] v) + \lambda(ubav)$，由 $[a, b] \in K[B]$ 可见前者是若干长度为 $|w| - 1$ 的词的 $\lambda$ 值之和、后者长度为 $|w|$ 但顺序数为 $\nu(w) - 1$，总之皆确定，故 $\lambda(w) \in K[F]$ 随之确定。 总之 $\text{Im}(\lambda) \subset K[F]$，同时 (1) 指出 $K[F] \subset \text{Im}(\lambda)$，故 $\text{Im}(\lambda) = K[F]$。 再证存在性。依唯一性的证明思路归纳构造，而 (2) 中 $a \geq b$ 的对称情况可以直接通过反对称性移项得到。 只需证明 (ii) 给出的 $\lambda(w)$ 良定义（即不依赖于 $u, v, a, b$ 的选取）。 设 $u', v' \in B^*, a', b' \in B$ 也使得 $w = u' a' b' v'$ 但 $a' < b'$，若二者不同则不妨设 $|u'| < |u|$，分类讨论： - (i) 若二者不重叠即 $u = u' a' b' p \ (p \in B^*)$，则由归纳假设可知：$(u, v, a, b)$ 给出 $$ \lambda(u' a' b' p [a, b] v) + \lambda(u' a' b' pbav) = (\lambda(u' [a', b'] p [a, b] v) + \lambda (u' b' a' p [a, b] v)) + (\lambda(u' [a', b'] pbav) + \lambda (u' b' a' pbav)) $$ - 同时 $(u', v', a', b')$ 给出 $$ \lambda(u' [a', b'] pabv) + \lambda(u' b' a' pabv) = (\lambda(u' [a', b'] p [a, b] v) + \lambda(u' [a', b'] pbav)) + (\lambda (u' b' a' p [a, b] v) + \lambda (u' b' a' pbav)) $$ - (ii) 若二者重叠即 $u = u' c \ (c \in B, c < a < b)$，则由归纳假设可知：二者之差为 $$ \begin{aligned} & (\lambda(u' c [a, b] v) + \lambda(u' cbav)) - (\lambda(u' [c, a] bv) + \lambda(u' acbv)) \\ = \ & (\lambda(u' [c, [a, b]] v) + \lambda(u' [a, b] cv)) + (\lambda(u' [c, b] av) + (\lambda(u' b [c, a] v) + \lambda(u' bacv))) \\ - \ & (\lambda(u' [[c, a], b] v) + \lambda(u' b [c, a] v)) - (\lambda(u' a [c, b] v) + (\lambda(u' [a, b] cv) + \lambda(u' bacv))) \\ = \ & \lambda(u' [c, [a, b]] v) + (\lambda(u' [c, b] av) - \lambda(u' a [c, b] v)) - \lambda(u' [[c, a], b] v) \\ = \ & -(\lambda(u' [[a, b], c] v) + \lambda(u' [[b, c], a] v) + \lambda(u' [[c, a], b] v)) \\ = \ & -\lambda(u' ([[a, b], c] + [[b, c], a] + [[c, a], b]) v) \\ = \ & 0 \end{aligned} $$ 总之二者相等，良定义性得证。再将上面构造的 $\lambda$ 自 $B^*$ 按 $K$-线性延拓到 $K \langle B \rangle$ 上即可。 最后证明 (3)，易见只需证明 $\forall u, v \in B^*, \lambda(uv) = \lambda(\lambda(u) v)$ 和 $\forall u, v \in B^*, \lambda(uv) = \lambda(u \lambda(v))$。对前者依唯一性的证明思路归纳： - (i) 当 $u \in F$，(1) 确定 $\lambda(u) = u$，命题显然成立。 - (ii) 当 $u \not\in F$，存在 $x, y \in B^*, a, b \in B$ 使得 $u = xaby$ 但 $a < b$，由归纳假设可知： $$ \begin{aligned} & \lambda(\lambda(u) v) \\ = \ & \lambda(\lambda(x [a, b] y) v) + \lambda(\lambda(xbay) v) \\ = \ & \lambda(x [a, b] yv) + \lambda(xbayv) \\ = \ & \lambda(uv) \end{aligned} $$ 而后者是同理的。明所欲证。 #### 定理 5.3.10 (包络代数存在, Poincare, Birkhoff & Witt) > 定义代数 $U$：其元素为 $K[F]$，其加法为 $K$-模的加法，其乘法 $* : U \times U \to U$ 定义为 $u * v = \lambda(uv)$。\ > 由 $K[B] \subset U$，取 Lie 态射 $K(\varphi) : \mathfrak{L} \to U_L$，则 $(U, K(\varphi))$ 为 $\mathfrak{L}$ 的包络代数。 _Proof._ 先证 $\varepsilon$ 为 $U$ 的幺元。易见 $\forall u \in K[F], \varepsilon * u = \lambda(\varepsilon u) = \lambda(u) = u$，同理 $u * \varepsilon = u$。 再证 $*$ 具有结合律。由 **引理 5.3.9 (3)** 即得： $$ (u * v) * w = \lambda((u * v) w) = \lambda(\lambda(uv) w) = \lambda(uvw) = \lambda(u \lambda(vw)) = \lambda(u (v * w)) = u * (v * w) $$ 接着说明 $*$ 是具有双线性性。由 $\lambda$ 的线性性即得： $$ \begin{cases} (u_1 + u_2) * v = \lambda((u_1 + u_2) v) = \lambda(u_1 v) + \lambda(u_2 v) = u_1 * v + u_2 * v \\ u * (v_1 + v_2) = \lambda(u (v_1 + v_2)) = \lambda(uv_1) + \lambda(uv_2) = u * v_1 + u * v_2 \end{cases} $$ 然后证明 $K(\varphi)$ 为 Lie 态射。任取 $a, b \in E$，记 $x = \varphi(a), y = \varphi(b) \in B$，由 **引理 5.3.9 (2)** 可知 $\lambda(xy) = \lambda([x, y]) + \lambda(yx)$，再由 **引理 5.3.9 (1)** 可知 $U$ 中的等式 $$ x * y - y * x = \lambda(xy) - \lambda(yx) = \lambda([x, y]) = [x, y] $$ 于是有 $K[B]$ 中的等式 $$ K(\varphi)([a, b]) = [x, y] = \varphi(a) * \varphi(b) - \varphi(b) * \varphi(a) $$ 故 $K(\varphi)$ 为 Lie 态射。 最后证明 $(U, K(\varphi))$ 的泛性质，现给定态射 $\psi : \mathfrak{L} \to S_L$。 一是唯一性。由 $\theta \circ K(\varphi) = \psi$ 和 $\varphi$ 为双射可知 $$ \forall b \in B, \theta(b) = \theta(K(\varphi)(\varphi^{-1}(b))) = \psi(\varphi^{-1}(b)) $$ 又由于当 $uv \in F$ 有 $\theta(uv) = \theta(\lambda(uv)) = \theta(u * v) = \theta(u) \theta(v)$，对长度归纳可见 $\theta|_F$ 被 $\theta|_B$ 唯一确定；进而可以通过加性唯一确定 $\theta$ 在 $K[F]$ 上的取值。总之 $\theta$ 唯一。 二是存在性。在 $B$ 上令 $\theta(b) = \psi(\varphi^{-1}(b))$，由 $K \langle B \rangle$ 的自由性将其延拓为代数同态 $\theta : K \langle B \rangle \to S$。 断言 $\forall w \in B^*, \theta(\lambda(w)) = \theta(w)$。对 $(|w|, \nu(w))$ 递增归纳： - (i) 当 $w \in F$，由 (1) 可知 $\theta(\lambda(w)) = \theta(w)$。 - (ii) 当 $w \not\in F$，存在 $u, v \in B^*, a, b \in B$ 使得 $w = uabv$ 但 $a < b$，由 (2) 及归纳假设可知： $$ \begin{aligned} \theta(\lambda(w)) &= \theta(\lambda(uabv)) \\ &= \theta(\lambda(u [a, b] v)) + \theta(\lambda(ubav)) \\ &= \theta(u [a, b] v) + \theta(ubav) \\ &= \theta(u) \theta([a, b]) \theta(v) + \theta(u) \theta(ba) \theta(v) \\ &= \theta(u) (\theta([a, b]) + \theta(ba)) \theta(v) \\ &= \theta(u) (\psi(K(\varphi)^{-1} ([a, b])) + \theta(ba)) \theta(v) \\ &= \theta(u) (\psi([\varphi^{-1}(a), \varphi^{-1}(b)]) + \theta(ba)) \theta(v) \\ &= \theta(u) ([\psi(\varphi^{-1}(a)), \psi(\varphi^{-1}(b))] + \theta(ba)) \theta(v) \\ &= \theta(u) ([\theta(a), \theta(b)] + \theta(ba)) \theta(v) \\ &= \theta(u) (\theta(a) \theta(b) - \theta(b) \theta(a) + \theta(b) \theta(a)) \theta(v) \\ &= \theta(u) \theta(ab) \theta(v) \\ &= \theta(w) \end{aligned} $$ 由线性性可知在 $K \langle B \rangle$ 上也成立 $\theta(\lambda(w)) = \theta(w)$，故有： $$ \forall u, v \in F, \theta(u * v) = \theta(\lambda(uv)) = \theta(uv) = \theta(u) \theta(v) $$ 故 $\theta$ 限制在 $U = K[F]$ 上为代数同态，又由 $$ \forall e \in E, \theta(\varphi(e)) = \psi(\varphi^{-1}(\varphi(e))) = \psi(e) $$ 延拓到 $\mathfrak{L}$ 上可见 $\theta \circ K(\varphi) = \psi$。明所欲证。 #### 推论 5.3.11 > 设 $(U, \varphi)$ 为 $\mathfrak{L}$ 的包络代数，则 $\varphi$ 为单射。 _Proof._ 始对象的性质指出，此处的 $U$ 与 **定理 5.3.10** 所构造的 $U$ 存在唯一的同构，则只需证明其中所取的 $K(\varphi)$ 为单射，而这由 $K(\varphi) : \mathfrak{L} \to K[B]$ 为自由模间的同构立即可得。 > _Rmk._ $\varphi$ 保留了 $\mathfrak{L}$ 的所有信息，同时包络代数的泛性质意味着 $U$ 应当是最自由的那一个结合代数。\ > 这构成了包络代数的直觉：由 $\mathfrak{L}$ 生成、把 Lie 括号实现为交换子的、且是最自由的结合代数。 #### 推论 5.3.12 > (1) 自由结合代数 $K \langle A \rangle$ 是自由 Lie 代数 $\mathfrak{L}(A)$ 的包络代数。\ > (2) 设 $\mathfrak{L}$ 为任一 Lie 代数，则对任意映射 $\beta : A \to \mathfrak{L}$，存在唯一态射 $\gamma : \mathfrak{L}(A) \to \mathfrak{L}$ 使得下图交换： ![](https://cdn.luogu.com.cn/upload/image_hosting/m5eku4x9.png) _Proof._ (1) 取嵌入态射 $\varphi : \mathfrak{L}(A) \to K \langle A \rangle_L$，欲证 $(K \langle A \rangle, \varphi)$ 为 $\mathfrak{L}(A)$ 的包络代数。 任给结合代数 $S$ 和态射 $\psi : \mathfrak{L}(A) \to S_L$，欲证在 $\mathfrak{L}(A)$ 上与 $\psi$ 取值一致的态射 $\theta : K \langle A \rangle \to S$ 存在且唯一。 先证唯一性。易见 $\theta$ 只能是 $\forall a \in A, \theta(a) = \psi(a)$ 在 $K \langle A \rangle$ 上的唯一延拓。 再证存在性。将 $\forall a \in A, \theta(a) = \psi(a)$ 唯一延拓到 $K \langle A \rangle$ 上，由代数同态的性质显见 $\theta$ 保持交换子，故对 $n \in \mathbb{N}$ 归纳可知 $\theta$ 在各 $\mathfrak{L}_n(A)$ 上的取值均与 $\psi$ 一致，再由加性得到 $\mathfrak{L}(A)$ 上的结论。 (2) 先证唯一性。$\mathfrak{L}(A)$ 由 $A$ 经有限次 Lie 括号生成而 $\gamma$ 保持括号，故 $\gamma$ 由其在 $A$ 上的取值唯一决定，即将 $\forall a \in A, \gamma(a) = \beta(a)$ 唯一延拓到 $\mathfrak{L}(A)$ 上即得。 再证存在性。由 **定理 5.3.10** 和 **推论 5.3.11** 将 $\mathfrak{L}$ 视同其包络代数 $U$ 的子代数，视 $\beta : A \to U$ 并将其唯一延拓为态射 $\gamma : K \langle A \rangle \to U$。 首先 $\gamma(A) = \beta(A) \subset \mathfrak{L}$，而 $\mathfrak{L}(A)$ 中的元素均是由 $A$ 中元素经有限次交换子生成的，同时 $\mathfrak{L}$ 对交换子封闭。总之有 $\gamma(\mathfrak{L}(A)) \subset \mathfrak{L}$。同时由代数同态的性质显见 $\gamma$ 保持交换子，故 $\gamma|_{\mathfrak{L}(A)} : \mathfrak{L}(A) \to \mathfrak{L}$ 为满足条件的态射。 #### 注记 5.3.13 若 $k = |A|$ 有限且承认 $\mathfrak{L}(A)$ 为 $L \subset A^*$ 生成的自由 $K$-模，这里给出 **推论 5.3.7 (Witt 公式)** 的另一种推导。 取 **定理 5.3.10** 和 **推论 5.3.12 (1)** 所给出的 $\mathfrak{L}(A)$ 的包络代数 $K \langle A \rangle \cong K[F]$，取定 $L$ 上的一个全序并视 $$ F = \{l_1 \cdots l_n \mid n \in \mathbb{N}, l_i \in L, l_1 \geq \cdots \geq l_n\} $$ 设 $a_n = \text{dim} \mathfrak{L}_n(A)$，令 $z$ 为自由元，构造以词长为指标的生成函数等式 $$ \sum_{w \in A^*} z^{|w|} = \prod_{l \in L} \frac{1}{1 - z^{|l|}} $$ 化简得 $$ \frac{1}{1 - kz} = \prod_{n \in \mathbb{N}_+} \frac{1}{(1 - z^n)^{a_n}} $$ 两边取对数得到 $$ \sum_{d \in \mathbb{N}_+} \frac{k^d}{d} z^d = \sum_{n \in \mathbb{N}_+} a_n \sum_{j \in \mathbb{N}_+} \frac{z^{nj}}{j} $$ 对比系数可知 $$ \frac{k^d}{d} = \sum_{n \mid d} a_n \cdot \frac{1}{\frac{d}{n}} = \frac{1}{d} \sum_{n \mid d} na_n $$ 最后莫比乌斯反演即得 $$ a_n = \frac{1}{n} \sum_{d \mid n} \mu \left( \frac{n}{d} \right) k^d = \Psi_k(n) $$ #### 定义 5.3.14 (Lie 理想, 商 Lie 代数) 设 $\mathfrak{L}$ 为交换幺环 $K$ 上的 Lie 代数，称 $I \subset \mathfrak{L}$ 为 Lie 理想，若 $I$ 为 $K$-子模且 $[I, \mathfrak{L}] \subset I$。 然后得到商集 $\mathfrak{L} / I$ 为 $K$-商模，再定义 Lie 括号 $[\bar{x}, \bar{y}] = \overline{[x, y]}$，现验证其良定义性： - 若 $\bar{x} = \overline{x'}, \bar{y} = \overline{y'}$，则 $[x, y] - [x', y'] = [x - x', y] + [y' - y, x'] \in I$，故 $\overline{[x, y]} = \overline{[x', y']}$。 而其双线性性、反对称性、Jacobi 恒等式显然成立。称这样得到的 Lie 代数 $(\mathfrak{L} / I, [\cdot, \cdot])$ 为商 Lie 代数。 #### 引理 5.3.15 > 设 $X \subset A^+$ 为码，则 $X$ 生成的 $K \langle A \rangle_L$ 的子 Lie 代数是自由的，记作 $\mathfrak{L}(X)$。 _Proof._ 由 $X$ 为码可知 $X^*$ 为 $A^*$ 的自由子幺半群，则 $K \langle X \rangle$ 自然嵌入为 $K \langle A \rangle$ 的自由结合子代数。 视 $X$ 为字母表，由 **定理 5.3.3** 即得相应的 $K \langle X \rangle_L$ 中由 $X$ 生成的子 Lie 代数 $\mathfrak{L}(X)$ 是自由的，同时显见 $\mathfrak{L}(X) \subset K \langle X \rangle_L \subset K \langle A \rangle_L$。明所欲证。 #### 引理 5.3.16 > 设 $B \subset C$，则存在 **单 Lie 同态** $\iota : \mathfrak{L}(B) \hookrightarrow \mathfrak{L}(C)$。 _Proof._ 由 **推论 5.3.12 (2)** 将单字母嵌入 $B \hookrightarrow \mathfrak{L}(C)$ 唯一延拓为 Lie 同态 $\iota : \mathfrak{L}(B) \to \mathfrak{L}(C)$。 接下来只需证明 $\iota$ 为单射。一方面，由 **推论 5.3.12 (1)** 有 单 Lie 同态 $\mathfrak{L}(B) \hookrightarrow K \langle B \rangle_L$，$B \subset C$ 诱导出唯一的结合代数单同态 $K \langle B \rangle \hookrightarrow K \langle C \rangle$ ——易见其作为映射同样是 单 Lie 同态 $K \langle B \rangle_L \hookrightarrow K \langle C \rangle_L$，复合得到 单 Lie 同态 $$ \mathfrak{L}(B) \hookrightarrow K \langle B \rangle_L \hookrightarrow K \langle C \rangle_L $$ 另一方面，由 **推论 5.3.12 (1)** 也有 单 Lie 同态 $\mathfrak{L}(C) \hookrightarrow K \langle C \rangle_L$，复合 $\iota$ 得到 Lie 同态 $$ \mathfrak{L}(B) \xrightarrow{\iota} \mathfrak{L}(C) \hookrightarrow K \langle C \rangle_L $$ 观察以上两者在 $B$ 上的取值可见其是一致的，这迫使 $\iota$ 为单射。明所欲证。 #### 命题 5.3.17 (二分诱导 Lie 直和分解) > 设 $(X, Y)$ 为 $A^*$ 的二分，$Z = X \cup Y$，递归定义映射 $\lambda : Z \to \mathfrak{L}(A)$： > $$ > \begin{cases} > \lambda(a) = a, &\quad a \in A \\ > \lambda(yx) = [\lambda(y), \lambda(x)], &\quad y \in Y, x \in X > \end{cases} > $$ > 将其分别延拓为 $\mathfrak{L}(X), \mathfrak{L}(Y)$ 上的 Lie 同态，最后延拓为模同态 $\lambda : \mathfrak{L}(X) \oplus \mathfrak{L}(Y) \to \mathfrak{L}(A)$，则可以给 $\mathfrak{L}(X) \oplus \mathfrak{L}(Y)$ 赋予 Lie 代数结构使得 $\lambda$ 成为 Lie 同构。 _Proof._ 由 **引理 5.3.15** 及 $X, Y$ 为码可知 $\mathfrak{L}(X), \mathfrak{L}(Y)$ 均为自由 Lie 代数，由 **引理 5.3.16** 及 $X, Y, A \subset Z$ 将 $\mathfrak{L}(X), \mathfrak{L}(Y), \mathfrak{L}(A)$ 嵌入为 **自由 Lie 代数** $\mathfrak{L}(Z)$ 的子代数。 > _Rmk._ 这里并没有将 $\mathfrak{L}(Z)$ 嵌入为 $K \langle A \rangle_L$ 的子代数，因为 $Z$ 并不是码。 又由于 $\mathfrak{L}(X) \cap \mathfrak{L}(Y) \subset K \langle X \rangle_L \cap K \langle Y \rangle_L = K \langle X \rangle \cap K \langle Y \rangle = \mathrm{span}(X^* \cap Y^*) = K \varepsilon$，但留意到 $\mathfrak{L}(X), \mathfrak{L}(Y)$ 的生成元不含 $\varepsilon$，故 $\mathfrak{L}(X) \cap \mathfrak{L}(Y) = \{0\}$，即 $\mathfrak{L}(X) \oplus \mathfrak{L}(Y)$ 确为直和，并构成 $\mathfrak{L}(Z)$ 的 $K$-子模。 设 $I$ 为 $S = \{[y, x] - yx \mid y \in Y, x \in X\}$ 生成的 $\mathfrak{L}(Z)$ 的 Lie 理想（此处 $[y, x]$ 是 $\mathfrak{L}(Z)$ 中的 Lie 括号），即 $$ [y, x] \equiv yx \pmod I, \quad y \in Y, x \in X $$ 生成的同余关系。 令 $\pi : \mathfrak{L}(Z) \to \mathfrak{L}(Z) / I$ 为商同态。现断言 $\pi' = \pi|_{\mathfrak{L}(X) \oplus \mathfrak{L}(Y)}$ 为模同构： - (i) 单射：只需证明 $\ker \pi' = I \cap (\mathfrak{L}(X) \oplus \mathfrak{L}(Y)) = \{0\}$。 - 设 $J$ 为 $S$ 生成的 $K \langle Z \rangle$ 的双边理想，则 $I \subset J$。 - 区别起见，记 $K \langle Z \rangle$ 中的乘法为 $\circ$，则 $K \langle Z \rangle / J$ 给出局部重写规则： $$ y \circ x \to x \circ y + yx, \quad y \in Y, x \in X $$ - 下面证明这个重写系统的两条性质： - - I. **终止性**：对 $w \in Z^*$ 设 $\nu(w) = \#\{(r, s, t) \mid w = r \circ y \circ s \circ x \circ t; r, s, t \in Z^*; y \in Y, x \in X\}$。 - - 只需对 $(|w|, \nu(w))$ 归纳证明每个 $K \langle Z \rangle$ 中的项都可通过有限次重写得到这样的项，支撑集中每个 $w \in Z^*$ 都满足 $\nu(w) = 0$： - - - [i] $|p \circ x \circ y \circ q| = |p \circ y \circ x \circ q|$ 但 $\nu(p \circ x \circ y \circ q) = \nu(p \circ y \circ x \circ q) - 1$。 - - - [ii] $|p \circ yx \circ q| = |p \circ y \circ x \circ q| - 1$。 - - II. **局部汇合性**：两处单步重写若重合则是显然的，若并非作用于同一单项式则接下来交换操作一次即可，若作用于同一单项式的不相交位置则接下来同样交换操作一次即可。 - - 最后由 $X \cap Y = \varnothing$ 可见其不可能作用于同一单项式的相交但不重合的位置。明所欲证。 - 综上，由 **Newman 引理** [3] 可知这个重写系统具有 **汇合性**，进而得到任给 $w \in K \langle Z \rangle$ 在其中皆具有唯一 **规范形** $$ \text{NF}(w) = \sum_{i = 1}^n k_i w_i, \quad k_i \in K \backslash \{0\}, w_i \in Z^* \text{ 两两不同}, \nu(w_i) = 0 $$ - 其中 $\nu(w_i) = 0$ 无非是说 $w_i \in X^* Y^*$。 - 当 $w \in I \cap (\mathfrak{L}(X) \oplus \mathfrak{L}(Y))$，一方面有 $w \in J \Rightarrow \text{NF}(w) = 0$，另一方面设 $w = w_X + w_Y \ (w_X \in \mathfrak{L}(X), w_Y \in \mathfrak{L}(Y))$，则 $w_X \in \mathfrak{L}(X) \subset \text{span}(X^+), w_Y \in \mathfrak{L}(Y) \subset \text{span}(Y^+)$，于是 $w_X, w_Y$ 的支撑词分别为 $X^+, Y^+$ 的子集。 - 但由 $X^+ \cap Y^+ = \varnothing, X^+ \cup Y^+ \subset X^* Y^*$ 可知 $X^+, Y^+$ 中的词自身已为互异的规范形，这迫使 $w_X = w_Y = 0$，故 $w = 0$。明所欲证。 - (ii) 满射：先证命题 $\mathcal{P} : [\mathfrak{L}_1(X), \mathfrak{L}(Y)] / I \subset (\mathfrak{L}(X) \oplus \mathfrak{L}(Y)) / I$ 和对称的命题 $\mathcal{Q} : [\mathfrak{L}_1(Y), \mathfrak{L}(X)] / I \subset (\mathfrak{L}(X) \oplus \mathfrak{L}(Y)) / I$。 - 只需对 $\mathfrak{L}(Y), \mathfrak{L}(X)$ 中各个齐次项归纳证明 $\forall n \in \mathbb{N}_+, \mathcal{P}_n : [\mathfrak{L}_1(X), \mathfrak{L}_n(Y)] / I \subset (\mathfrak{L}_{\leq n}(X) \oplus \mathfrak{L}_{\leq n}(Y)) / I, \mathcal{Q}_n : [\mathfrak{L}_1(Y), \mathfrak{L}_n(X)] / I \subset (\mathfrak{L}_{\leq n}(X) \oplus \mathfrak{L}_{\leq n}(Y)) / I$： - - I. 当 $n = 1$，由线性性可见无非是证明 $$ \forall y \in Y, x \in X, \overline{[y, x]} \in (\mathfrak{L}_1(X) \oplus \mathfrak{L}_1(Y)) / I $$ - - 由 $Z = X \sqcup Y = YX \sqcup A$ 可知 $[y, x] \equiv yx \in Z \pmod I$ 必恰在 $X, Y$ 之一中，故 $\overline{[y, x]}$ 也在 $(\mathfrak{L}_1(X) \oplus \mathfrak{L}_1(Y)) / I$ 中。 - - II. 当 $n > 1$，同样由线性性可见无非是证明 $$ \begin{cases} \forall x \in X, u_Y \in \mathfrak{L}_n(Y), \overline{[x, u_Y]} \in (\mathfrak{L}_{\leq n}(X) \oplus \mathfrak{L}_{\leq n}(Y)) / I \\ \forall y \in Y, u_X \in \mathfrak{L}_n(X), \overline{[y, u_X]} \in (\mathfrak{L}_{\leq n}(X) \oplus \mathfrak{L}_{\leq n}(Y)) / I \end{cases} $$ - - 由对称性可知只需证明前者。由 **命题 5.3.2** 可知 $\mathfrak{L}_n(Y) = [\mathfrak{L}_1(Y), \mathfrak{L}_{n - 1}(Y)]$，再由线性性不妨假设 $u_Y = [y, v_Y] \ (y \in Y, v_Y \in \mathfrak{L}_{n - 1}(Y))$，则有 $$ [x, u_Y] = [y, [x, v_Y]] - [[y, x], v_Y] \equiv [y, [x, v_Y]] - [yx, v_Y] \pmod I $$ - - 一方面，由归纳假设可知 $\overline{[x, v_Y]} \in (\mathfrak{L}_{\leq n - 1}(X) \oplus \mathfrak{L}_{\leq n - 1}(Y)) / I$，再由线性性和 $\mathcal{Q}_{\leq n - 1}$ 即得 $\overline{[y, [x, v_Y]]} \in (\mathfrak{L}_{\leq n - 1}(X) \oplus \mathfrak{L}_{\leq n}(Y)) / I$。 - - 另一方面，由 $Z = X \sqcup Y = YX \sqcup A$，当 $yx \in X$ 时由 $\mathcal{P}_{n - 1}$ 可知 $\overline{[yx, v_Y]} \in (\mathfrak{L}_{\leq n - 1}(X) \oplus \mathfrak{L}_{\leq n - 1}(Y)) / I$，当 $yx \in Y$ 时有 $[yx, v_Y] \in \mathfrak{L}_n(Y)$。 - - 总之有 $\overline{[x, u_Y]} \in (\mathfrak{L}_{\leq n}(X) \oplus \mathfrak{L}_{\leq n}(Y)) / I$，命题 $\mathcal{P}_n$ 成立。 - 然后对 $\mathfrak{L}(Z)$ 中各个齐次项归纳证明 $\forall n \in \mathbb{N}_+, \mathfrak{L}_n(Z) / I \subset (\mathfrak{L}(X) \oplus \mathfrak{L}(Y)) / I$： - - I. 当 $n = 1$，由 $Z = X \sqcup Y$ 可知 $\mathfrak{L}_1(Z) = K[Z] = K[X] \oplus K[Y] \subset \mathfrak{L}(X) \oplus \mathfrak{L}(Y)$，命题成立。 - - II. 当 $n > 1$，由 **命题 5.3.2** 可知 $\mathfrak{L}_n(Z) = [\mathfrak{L}_1(Z), \mathfrak{L}_{n - 1}(Z)]$，则由线性性可见无非是证明 $$ \forall z \in Z, u \in \mathfrak{L}_{n - 1}(Z), \overline{[z, u]} \in (\mathfrak{L}(X) \oplus \mathfrak{L}(Y)) / I $$ - - 由归纳假设可知 $\exists u_X \in \mathfrak{L}(X), u_Y \in \mathfrak{L}(Y), \text{s.t. } u \equiv u_X + u_Y \pmod I$。对 $z$ 分类讨论： - - - [i] 当 $z = x \in X$，有 $[z, u] \equiv [x, u_X] + [x, u_Y] \pmod I$，一方面显然有 $[x, u_X] \in \mathfrak{L}(X)$，另一方面由命题 $\mathcal{P}$ 可知 $\overline{[x, u_Y]} \in (\mathfrak{L}(X) \oplus \mathfrak{L}(Y)) / I$，故 $\overline{[z, u]} \in (\mathfrak{L}(X) \oplus \mathfrak{L}(Y)) / I$。 - - - [ii] 当 $z = y \in Y$，由命题 $\mathcal{Q}$ 同理可知 $\overline{[z, u]} \in (\mathfrak{L}(X) \oplus \mathfrak{L}(Y)) / I$。 - - 总之命题对 $n$ 也成立。 - 综上，取各齐次项之直和即得 $\mathfrak{L}(Z) / I \subset (\mathfrak{L}(X) \oplus \mathfrak{L}(Y)) / I$，故 $\pi'$ 为满射。 由此构造出 Lie 代数 $\mathfrak{L} = (\mathfrak{L}(X) \oplus \mathfrak{L}(Y), (\cdot, \cdot))$，其中 Lie 括号定义为 $$ (u, v) \mapsto \pi'^{-1}([\pi'(u), \pi'(v)]) $$ 由于当 $u, v$ 同属 $\mathfrak{L}(X)$ 或 $\mathfrak{L}(Y)$ 时，由定义容易验证 $(u, v)$ 无非就是原本的 Lie 括号，故 $\mathfrak{L}$ 由 $Z$ 生成。 将 $\lambda|_Z$ 先延拓为 Lie 同态 $\mathfrak{L}(Z) \to \mathfrak{L}(A)$，再经 **引理 5.3.16** 的嵌入 $\mathfrak{L}(A) \hookrightarrow \mathfrak{L}(Z)$ 复合，得到 Lie 同态 $\mu : \mathfrak{L}(Z) \to \mathfrak{L}(Z)$。一方面由 $$ \forall y \in Y, x \in X, \mu([y, x] - yx) = [\mu(y), \mu(x)] - [\mu(y), \mu(x)] = 0 $$ 可知 $I \subset \ker \mu$，另一方面再依 $|z|$ 归纳证明 $\mu(z) \equiv z \pmod I$： - (i) 当 $z \in A$，显然有 $\mu(z) = z \equiv z \pmod I$。 - (ii) 当 $z = yx \ (y \in Y, x \in X)$，有 $\mu(z) - z = [\mu(y), \mu(x)] - yx \equiv [\mu(y), \mu(x)] - [y, x] = [\mu(y) - y, \mu(x)] + [y, \mu(x) - x] \pmod I$。 - 由归纳假设可知 $\mu(y) - y, \mu(x) - x \in I$，再由 **定义 5.3.14** 可知和式中的两项均在 $I$ 中，故 $\mu(z) - z \equiv 0 \pmod I$ 即 $\mu(z) \equiv z \pmod I$。 随后由同态的性质立刻得到 $\forall u \in \mathfrak{L}(Z), \mu(u) \equiv u \pmod I$，因而 $u \in \ker \mu \Leftrightarrow \mu(u) = 0 \Rightarrow u \equiv 0 \pmod I \Leftrightarrow u \in I$，可见 $\ker \mu \subset I$。总之有 $I = \ker \mu$。 同时由 $\mu(A) = A$ 可见 $\text{im } \mu = \iota(\mathfrak{L}(A))$，则由 **模的第一同构定理** 可知存在唯一的模同构 $\varphi : \mathfrak{L}(Z) / I \to \mathfrak{L}(A)$，使得 $\iota^{-1} \circ \mu = \varphi \circ \pi$。随后还需证明 $\varphi$ 为 Lie 同构，即 $$ \forall z_1, z_2 \in \mathfrak{L}(Z), \varphi([\bar{z_1}, \bar{z_2}]) = \varphi(\overline{[z_1, z_2]}) = \iota^{-1}\mu([z_1, z_2]) = \iota^{-1}[\mu(z_1), \mu(z_2)] = [\varphi(\bar{z_1}), \varphi(\bar{z_2})] $$ 由双射可见 $\pi' : \mathfrak{L} \to \mathfrak{L}(Z) / I$ 为 Lie 同构，故 $\lambda' = \varphi \circ \pi' : \mathfrak{L} \to \mathfrak{L}(A)$ 也为 Lie 同构。 > _Rmk._ $\mathfrak{L}$ 正是由 $\lambda'^{-1}(A) = A$ **自由生成** 的 Lie 代数。 容易验证 $\lambda'|_X = \lambda|_X, \lambda'|_Y = \lambda|_Y$，而后 $\lambda'|_{\mathfrak{L}(X)} = \lambda|_{\mathfrak{L}(X)}, \lambda'|_{\mathfrak{L}(Y)} = \lambda|_{\mathfrak{L}(Y)}$，最终有 $\lambda' = \lambda$，故 $\lambda$ 为 Lie 同构。明所欲证。 #### 例子 5.3.18 (Lazard 消去法) 设 $a \in A$，取 $A^*$ 的二分 $(X, Y)$ 如下： $$ X = a^* (A \setminus \{a\}), \quad Y = a $$ 则由 **命题 5.3.17** 可通过给 $K$-模的直和 $Ka \oplus \mathfrak{L}(B)$ 赋予 Lie 代数结构使得 $$ \mathfrak{L}(A) \cong Ka \oplus \mathfrak{L}(B) $$ 其中 $B$ 为 $X$ 对应的所有有限 Lie 括号结构 $$ [a, \cdots [a, b] \cdots] \quad (b \in A \backslash \{a\}) $$ 构成的集合。 #### 定义 5.3.19 (自由结合代数的张量积, 对角映射) 设 $R = K \langle A \rangle = K[A^*]$，定义其张量积 $R \otimes R = K[A^* \times A^*]$ 为形式和 $$ \sum_{i = 1}^n k_i (u_i \otimes v_i) $$ 其中 $k_i \in K, u_i, v_i \in A^*$。逐分量定义乘法 $$ (u \otimes v)(r \otimes s) = (ur \otimes vs) $$ 则 $R \otimes R$ 成为 $K$-结合代数。 定义 **对角映射** 为如下唯一确定的代数同态 $$ \begin{aligned} \delta : R &\to R \otimes R \\ a &\mapsto a \otimes \varepsilon + \varepsilon \otimes a, &\quad a \in A \end{aligned} $$ 例如 $\forall a, b \in A, \delta(ab) = ab \otimes \varepsilon + a \otimes b + b \otimes a + \varepsilon \otimes ab$。 #### 定理 5.3.20 (Friedrichs) > 设整环 $K$ 满足 $\text{char } K = 0$，则 $u \in K \langle A \rangle$ 在 $\mathfrak{L}(A)$ 中当且仅当 $\delta(u) = u \otimes \varepsilon + \varepsilon \otimes u$。 _Proof._ 令 $P = \{u \in K \langle A \rangle \mid \delta(u) = u \otimes \varepsilon + \varepsilon \otimes u\}$，欲证 $\mathfrak{L}(A) = P$： - (i) $\mathfrak{L}(A) \subset P$：首先由定义可知 $A \subset P$；其次当 $u, v \in P$，有 $$ \delta([u, v]) = \delta(u) \delta(v) - \delta(v) \delta(u) = (uv - vu) \otimes \varepsilon + \varepsilon \otimes (uv - vu) $$ - 故 $[u, v] \in P$ 即 $P$ 对 Lie 括号封闭。明所欲证。 - (ii) $P \subset \mathfrak{L}(A)$：由 **定理 5.3.10** 和 **推论 5.3.11** 将 $\mathfrak{L}(A)$ 视同 $K[F]_L$ 的子 Lie 代数，对 $f \in F$ 分类讨论： - - I. 当 $|f| = 1$，显见 $f \in P$。 - - II. 当 $|f| > 1$，设 $f = c_1^{e_1} \cdots c_k^{e_k} \ (k \in \mathbb{N}_+, c_i \in B, c_1 > \cdots > c_k, e_i \in \mathbb{N}_+)$，则 $$ \delta(f) = \prod_{i = 1}^k \delta(c_i^{e_i}) = \prod_{i = 1}^k \sum_{j = 0}^{e_i} C_{e_i}^j (c_i^j \otimes c_i^{e_i - j}) $$ - - 展开式整理后必有既不是 $f \otimes \varepsilon$ 也不是 $\varepsilon \otimes f$ 的系数非零的项：$k = 1$ 时可取 $e_1 (c_1 \otimes c_1^{e_1 - 1})$（由 $\text{char } K = 0$ 可见 $e_1 \cdot 1_K \neq 0$），$k > 1$ 时可取 $c_1^{e_1} \otimes \displaystyle\prod_{i = 2}^k c_i^{e_i}$（系数为 $1$）。总之 $f \not\in P$。 - 又留意到不同 $f \in F$ 给出的交叉项 $u \otimes v$ 能够唯一确定其源头 $f$、不同 $f$ 对应的交叉项互不相同，且每个 $f_i$ 都有一个系数为 $n\cdot 1_K \ (n \in \mathbb{N}_+)$ 的交叉项。 - 由 $\text{char } K = 0$ 可见 $n \cdot 1_K \neq 0$，故整性给出 $v_i (n \cdot 1_K) \neq 0$，各交叉项互不抵消；故 $u = \displaystyle\sum_{i = 1}^n v_i f_i \ (v_i \in K \backslash \{0\}, f_i \in F \text{ 两两不同}) \in K[F]$ 在 $P$ 中当且仅当 $\forall 1 \leq i \leq n, f_i \in P$。 - 总之当 $u \in P \subset K[F]$，其必可写成 $\displaystyle\sum_{i = 1}^n v_i b_i \ (v_i \in K \backslash \{0\}, b_i \in B \text{ 两两不同}) \in \mathfrak{L}(A)$ 的形式，故 $P \subset \mathfrak{L}(A)$。 ------ 下面这一部分默认 **域** $K$ 满足 $\text{char } K = 0$，$A$ 为有限字母表，$M$ 为有限个自由幺半群的直积，$N$ 则为若干自由幺半群的之积，令 $S = K^M, T = K^N$；请留意 $S$ 未必指代 $K \langle \langle A \rangle \rangle$。 #### 定义 5.3.21 (形式级数的指对运算) 取 $S$ 的理想 $$ S^{(1)} = \{\sigma \in S \mid \langle \sigma, \varepsilon \rangle = 0\} $$ 则 $\forall \sigma \in S^{(1)}$，$(\sigma^n)_{n \in \mathbb{N}}$ 局部有限（$\sigma^n$ 的最低次数 $\geq n$，则固定次数只对应有限项），故指对运算 $$ \begin{aligned} \exp(\sigma) &= \sum_{n = 0}^{+\infty} \frac{\sigma^n}{n!} \\ \log(1 + \sigma) &= \sum_{n = 1}^{+\infty} \frac{(-1)^{n - 1}}{n} \sigma^n \end{aligned} $$ 良定义。 由定义易知其符合指对运算的一般性质如下： - (1) $\log(\exp(\sigma)) = \sigma, \exp(\log(1 + \sigma)) = 1 + \sigma$，即 $\exp : S^{(1)} \to 1 + S^{(1)}, \log : 1 + S^{(1)} \to S^{(1)}$ 为互逆双射。 - (2) 若 $\sigma_1 \sigma_2 = \sigma_2 \sigma_1$，则 $\exp(\sigma_1) \exp(\sigma_2) = \exp(\sigma_1 + \sigma_2), \log((1 + \sigma_1)(1 + \sigma_2)) = \log(1 + \sigma_1) + \log(1 + \sigma_2)$。 #### 定义 5.3.22 (连续态射) 称态射 $\alpha : M \to T$ 连续，若 $\alpha(M \backslash \{\varepsilon\}) \subset T^{(1)}$。 此时 $(\alpha(m))_{m \in M}$ 局部有限，故可将 $\alpha$ 延拓为 $$ \begin{aligned} \alpha : S &\to T \\ \sigma &\mapsto \sum_{m \in M} \langle \sigma, m \rangle \alpha(m) \end{aligned} $$ 容易验证此时对 $\sigma \in S^{(1)}$ 有 $$ \begin{aligned} \exp(\alpha(\sigma)) &= \alpha(\exp(\sigma)) \\ \log(\alpha(1 + \sigma)) &= \alpha(\log(1 + \sigma)) \end{aligned} $$ ------ 现在回到 $S = K \langle \langle A \rangle \rangle$ 的情形。 #### 定义 5.3.23 (Lie 元素) 将 $\sigma \in S$ 齐次分解为 $\sigma = \displaystyle\sum_{n \in \mathbb{N}} \sigma_n$，其中 $\sigma_n$ 为 $n$ 次齐次项。 称 $\sigma$ 为 Lie 元素，若 $\forall n \in \mathbb{N}, \sigma_n \in \mathfrak{L}_n(A)$。记 $\bar{\mathfrak{L}}(A)$ 为 $S$ 中所有 Lie 元素构成的集合。 #### 定理 5.3.24 (Campbell, Baker, Hausdorff) > $\forall a, b \in A, \log(\exp a \exp b) \in \bar{\mathfrak{L}}(A)$。 _Proof._ 考虑连续态射 $$ \begin{aligned} \underline{\delta} : A^* &\to T \\ w &\mapsto \delta(\underline{w}) \end{aligned} $$ 其中 $T = K^{A^* \times A^*} \supset R \otimes R$。 据 **定义 5.3.22** 将连续态射 $\underline{\delta}$ 延拓为 $\delta : S \to T$，易见新的 $\delta$ 在 $R$ 上与原本的 $\delta$ 是兼容的。 > **引理 5.3.25** > > $\sigma \in \bar{\mathfrak{L}}(A)$ 当且仅当 $\delta(\sigma) = \varepsilon \otimes \sigma + \sigma \otimes \varepsilon$。 > > _Proof._ 将 $\sigma$ 齐次分解为 $\sigma = \displaystyle\sum_{n \in \mathbb{N}} \sigma_n$，若 $\sigma \in \bar{\mathfrak{L}}(A)$，则 > $$ > \delta(\sigma) = \sum_{n \in \mathbb{N}} \delta(\sigma_n) = \sum_{n \in \mathbb{N}} (\sigma_n \otimes \varepsilon + \varepsilon \otimes \sigma_n) = \sigma \otimes \varepsilon + \varepsilon \otimes \sigma > $$ > 反之若 $\delta(\sigma) = \sigma \otimes \varepsilon + \varepsilon \otimes \sigma$，依照交叉项 $u \otimes v$ 的次数 $\deg u + \deg v$ 分离得到 > $$ > \forall n \in \mathbb{N}, \delta(\sigma_n) = \sigma_n \otimes \varepsilon + \varepsilon \otimes \sigma_n > $$ > 则 $\forall n \in \mathbb{N}, \sigma_n \in \mathfrak{L}(A)$，故 $\sigma \in \bar{\mathfrak{L}}(A)$。明所欲证。 > **引理 5.3.26** > > 设 $\sigma \in 1 + S^{(1)}$，则 $\log \sigma \in \bar{\mathfrak{L}}(A)$ 当且仅当 $\delta(\sigma) = \sigma \otimes \sigma$。 > > _Proof._ 展开 $\log$ 易见 > $$ > \begin{cases} > \log \sigma \otimes \varepsilon = \log(\sigma \otimes \varepsilon) \\ > \varepsilon \otimes \log \sigma = \log(\varepsilon \otimes \sigma) > \end{cases} > $$ > 总成立，于是由 **引理 5.3.25** 可知 $\log \sigma \in \bar{\mathfrak{L}}(A)$ 当且仅当 > $$ > \begin{aligned} > \delta(\log \sigma) &= \log \sigma \otimes \varepsilon + \varepsilon \otimes \log \sigma \\ > &= \log(\sigma \otimes \varepsilon) + \log(\varepsilon \otimes \sigma) > \end{aligned} > $$ > 又由于 $(\sigma \otimes \varepsilon)(\varepsilon \otimes \sigma) = (\varepsilon \otimes \sigma)(\sigma \otimes \varepsilon) = \sigma \otimes \sigma$，据 **定义 5.3.21** 可知其等价于 > $$ > \delta(\log \sigma) = \log (\sigma \otimes \sigma) > $$ > 再由 **定义 5.3.22** 可知其等价于 > $$ > \log \delta(\sigma) = \log (\sigma \otimes \sigma) > $$ > 最后由 **定义 5.3.21** 两边同时取 $\exp$ 即证得其等价于 > $$ > \delta(\sigma) = \sigma \otimes \sigma > $$ 对于 $a, b \in A \subset \bar{\mathfrak{L}}(A)$，由 **引理 5.3.26** 可展开 $\delta(\exp a), \delta(\exp b)$ 得 $$ \begin{aligned} \delta(\exp a \exp b) &= \delta(\exp a) \delta(\exp b) \\ &= (\exp a \otimes \exp a)(\exp b \otimes \exp b) \\ &= (\exp a \exp b) \otimes (\exp a \exp b) \end{aligned} $$ 再由 **引理 5.3.26** 即证得 $\log(\exp a \exp b) \in \bar{\mathfrak{L}}(A)$。 > _Rmk._ $\log(\exp a \exp b)$ 称为 **Hausdorff 级数**，其前几项为： > $$ > \log(\exp a \exp b) = a + b + \frac{1}{2} [a, b] + \frac{1}{12} [[a, b], b] + \frac{1}{12} [a, [a, b]] + \cdots > $$ ------ 设 $S'$ 为这样的 $\sigma \in S$ 构成的集合：做齐次分解 $\sigma = \displaystyle\sum_{n \in \mathbb{N}} \sigma_n$，要求 $\sigma_n \in R' = [R, R]$ 即所有交换子生成的子模。 由定义可见 $\overline{\mathfrak{L}}(A) \subset R_1 \oplus S'$，这意味着 $S'$ 的性质比 Lie 元素“差”。 #### 推论 5.3.27 > $\forall \sigma, \tau \in 1 + S^{(1)}, z = \log(\sigma \tau) - \log \sigma - \log \tau \in S'$。 _Proof._ 若 $|A| = 1$，显见 $\sigma \tau = \tau \sigma$，进而 $z = 0 \in S'$。 否则取连续态射 $\alpha : A^* \to S$ 使得 $\alpha(a) = \log \sigma, \alpha(b) = \log \tau \ (a, b \in A, a \neq b)$，则由 Hausdorff 级数的展开式可知 $$ y = \log(\exp a \exp b) - a - b \in S' $$ 由 **定义 5.3.22** 延拓得到 $\alpha : S \to S$，可知 $$ \begin{aligned} \alpha(y) &= \alpha(\log(\exp a \exp b)) - \log \sigma - \log \tau \\ &= \log(\alpha(\exp a \exp b)) - \log \sigma - \log \tau \\ &= \log(\alpha(\exp a) \alpha(\exp b)) - \log \sigma - \log \tau \\ &= \log(\exp(\log \sigma) \exp(\log \tau)) - \log \sigma - \log \tau \\ &= \log \sigma \tau - \log \sigma - \log \tau \\ &= z \end{aligned} $$ 由于 $\alpha$ 保持交换子，容易验证 $\alpha(S') \subset S'$，故 $z = \alpha(y) \in S'$。 ------ 作为这一节的结尾，来对 **推论 5.3.27** 做一点简单的推广。 设 $I$ 为全序集，$(\tau_i)_{i \in I} \subset S^{(1)}$ 局部有限，定义（无限）积 $$ \prod_{i \in I} (1 + \tau_i) \triangleq \sum_{J \subset I \text{ 有限}} \prod_{i \in J} \tau_i $$ 其中 $\displaystyle\prod_{i \in J} \tau_i$ 按 $I$ 上的全序取积。 #### 推论 5.3.28 > 设 $I$ 为全序集，$(\sigma_i)_{i \in I} \subset 1 + S^{(1)}$ 局部有限，则 > $$ > z = \log \prod_{i \in I} \sigma_i - \sum_{i \in I} \log \sigma_i \in S' > $$ _Proof._ 将 $z$ 拆成各齐次分量，由局部有限性可见各分量仅涉及 $I$ 的有限子集，继承 $I$ 上的全序即约化为 $I$ 有限的情形，此时直接对 $|I|$ 归纳即可。最后由 $z$ 的各齐次分量属于 $S'$ 即得 $z \in S'$。 ### 5.4 自由幺半群的分解定理 #### 定义 5.4.1 (循环码) 设 $X \subset A^+$，称 $X$ 为循环码，若任给 $n, m \in \mathbb{N}_+$，$x_1, \cdots, x_n, y_1, \cdots, y_m \in X$，$p \in A^*, s \in A^+$，都有 $$ \begin{cases} x_1 = ps \\ s x_2 \cdots x_n p = y_1 \cdots y_m \end{cases} $$ 蕴含 $n = m, p = \varepsilon; \forall 1 \leq i \leq n, x_i = y_i$。 > _Rmk._ 循环码必为码：取 $p = \varepsilon$ 即得码的定义。 #### 命题 5.4.2 > 设 $X \subset A^+$ 为循环码，则： > > (1) $X$ 的元素两两不共轭，且皆为本原词。\ > > (2) 特别地，单点集 $\{x\} \ (x \in A^+)$ 为循环码当且仅当 $x$ 本原。 _Proof._ 先证 (1)。若 $x, y \in X$ 共轭，设 $x = ps, y = sp \ (p \in A^*, s \in A^+)$，则 $sxp = y^2$，由循环码的定义可知 $p = \varepsilon, x_1 = y_1$，即 $x = y$，故 $X$ 的元素两两不共轭。 若 $u \in X$，设 $u = t^n \ (n \in \mathbb{N}_+)$ 且 $t$ 本原，取 $x_1 = x_2 = y_1 = y_2 = t^n, s = t, p = t^{n - 1}$，则 $x_1 = ps, sx_2 p = t^{2n} = y_1 y_2$，由循环码的定义可知 $p = t^{n - 1} = \varepsilon$，故 $u = t$ 本原，即 $X$ 的元素皆为本原词。 再证 (2)。必要性由 (1) 立即可得，下证充分性。设 $x \in A^+$ 本原，若 $n, m \in \mathbb{N}_+, p \in A^*, s \in A^+$ 使得 $x = ps, s x^{n - 1} p = x^m$，对比长度可见必有 $n = m$。 假设 $p \neq \varepsilon$，令 $y = sp$，则可见 $x^n = y^n \Rightarrow x = y$，再由 **命题 1.3.3** 可知 $p, s \in z^+ \ (z \in A^+)$，则 $x$ 为 $z$ 的幂且其指数 $\geq 2$，与 $x$ 本原矛盾！故 $p = \varepsilon$，明所欲证。 #### 定义 5.4.3 (纯, 极纯) 设 $M$ 为 $A^*$ 的子幺半群。称 $M$ **纯**，若 $$ \forall x \in A^*, n \in \mathbb{N}_+, x^n \in M \Rightarrow x \in M $$ 称 $M$ **极纯**，若 $$ \forall u, v \in A^*, uv, vu \in M \Rightarrow u, v \in M $$ #### 引理 5.4.4 > 设 $M$ 为 $A^*$ 的子幺半群，$X$ 为其极小生成集，则 $M$ 极纯当且仅当 $X$ 为循环码。 _Proof._ 先证充分性。设 $X$ 为循环码，任取 $u, v \in A^+$ 使得 $uv, vu \in M$，由码的性质取唯一分解 $uv = x_1 \cdots x_n, vu = y_1 \cdots y_m \ (x_i, y_j \in X)$。 由 $u$ 是 $uv$ 的前缀，取 $1 \leq i \leq n, p \in A^*, s \in A^+$ 使得 $$ \begin{cases} u = x_1 \cdots x_{i - 1} p \\ x_i = ps \\ v = s x_{i + 1} \cdots x_n \end{cases} $$ 于是 $vu$ 可表作 $$ vu = y_1 \cdots y_m = sx_{i + 1} \cdots x_n x_1 \cdots x_{i - 1} p $$ 由循环码的定义可知 $p = \varepsilon$，故 $u = x_1 \cdots x_{i - 1}, v = x_i x_{i + 1} \cdots x_n \in M$，即 $M$ 极纯。 再证必要性。设 $M$ 极纯，先证 $X$ 为码。任给 $w \in A^*$，设 $p, q \in M$ 使得 $pw, wq \in M$，则 $(qp)w, w(qp) \in M$，由极纯的定义可知 $w \in M$，故由 **命题 1.2.3** 可知 $X$ 为码。 再证 $X$ 为循环码。任给 $n, m \in \mathbb{N}_+; x_1, \cdots, x_n, y_1, \cdots, y_m \in X; p \in A^*, s \in A^+$，若 $$ \begin{cases} x_1 = ps \\ s x_2 \cdots x_n p = y_1 \cdots y_m \in M \end{cases} $$ 则 $p(sx_2 \cdots x_n) = x_1 \cdots x_n \in M$ 且 $(sx_2 \cdots x_n)p = y_1 \cdots y_m \in M$，由极纯的定义可知 $p, sx_2 \cdots x_n \in M$；同理由 $s(x_2 \cdots x_n p) = y_1 \cdots y_m \in M$ 且 $(x_2 \cdots x_n p)s = x_2 \cdots x_n x_1 \in M$，据极纯的定义得到 $s, x_2 \cdots x_n p \in M$。 若 $p \neq \varepsilon$ 则 $x_1$ 可被 $X$ 中长度 $< |x_1|$ 的词表出，矛盾！故 $p = \varepsilon$，再由 $X$ 为码即证得 $X$ 为循环码。 #### 定义 5.4.5 ($X$-共轭, $X$-本原, $X$-指数) 设 $X \subset A^+$ 为码，考察双射 $\beta : B \to X$，诱导出自由幺半群的同构 $\beta : B^* \to X^*$： - 称 $w, w' \in X^*$ 是 $X$-共轭的，若 $\beta^{-1}(w), \beta^{-1}(w')$ 在 $B^*$ 中共轭。 - 称 $x \in X^*$ 是 $X$-本原的，若 $\beta^{-1}(x)$ 本原。 - 称 $x \in X^*$ 的 $X$-指数为 $\beta^{-1}(x)$ 的指数。显见 $x$ 的 $X$-指数不超过其指数。 则与 $A^*$ 上的情形一致，$X$-共轭类的大小正是 $X$-词长与 $X$-指数之比。 #### 引理 5.4.6 > 设 $X \subset A^+$ 为码，则 $X^*$ 极纯当且仅当 $X^*$ 纯且在 $X^*$ 中共轭者也必 $X$-共轭。 _Proof._ 先证必要性。设 $X^*$ 极纯： - 一方面，若 $x^n \in X^*$，取 $u = x, v = x^{n - 1}$ 即得 $x \in X^*$，故 $X^*$ 纯。 - 另一方面，若 $w = uv, w' = vu \in X^*$ 共轭，由极纯的定义可知 $u, v \in X^*$，则 $w = u \cdot v, w' = v \cdot u$ 正是其 $X$-共轭的见证。 再证充分性。设 $X^*$ 纯且在 $X^*$ 中共轭者也必 $X$-共轭，任给 $u, v \in A^*$ 使得 $uv, vu \in X^*$。若 $u = \varepsilon$ 或 $v = \varepsilon$ 则命题显然成立，下设 $u, v \neq \varepsilon$。 设 $t, t'$ 为 $uv, vu$ 的本原根，由 **命题 1.3.5** 可知 $uv = t^p, vu = t'^p \ (p \in \mathbb{N}_+)$，由纯的定义可知 $t, t' \in X^*$。由 $u$ 为 $uv = t^p$ 的前缀可知 $\exists 0 \leq i < p, r \in A^*, s \in A^+, \text{s.t. } u = t^i r, t = rs, v = st^{p - i - 1}$，则 $t' = sr$。 由在 $X^*$ 中共轭者也必 $X$-共轭可知 $\exists r' \in X^*, s' \in X^+, \text{s.t. } t = r' s', t' = s' r'$，由 **命题 1.3.5** 即得 $r = r', s = s' \in X^*$，故 $u, v \in X^*$。明所欲证。 #### 命题 5.4.7 > 设 $X \subset A^+$ 为码，$C \subset A^n \ (n \in \mathbb{N}_+)$ 为共轭类，$p$ 为 $C$ 中词的指数，则： > > (1) > > $$ > > \langle \log (1 - \underline{X})^{-1}, C \rangle = \sum_{k \in \mathbb{N}_+} \frac{1}{k} |X^k \cap C| > > $$ > > (2) 进一步地，当 $C \cap X^* \neq \varnothing$，有 > > $$ > > \langle \log (1 - \underline{X})^{-1}, C \rangle \geq \frac{1}{p} > > $$ > > 且 $X$ 为循环码当且仅当只要 $C \cap X^* \neq \varnothing$ 上述不等式就取等。 _Proof._ (1) 由 $X$ 为码可知 $\log (1 - \underline{X})^{-1} = \displaystyle\sum_{k \in \mathbb{N}_+} \frac{1}{k} \underline{X}^k$，且 $\underline{X}^k$ 中每个词的系数恰为该词的 $X$-拆分数 $1$，明所欲证。 (2) 先证不等式成立。由 $X$ 为码可见 $C \cap X^*$ 可表作若干 $X$-共轭类的无交并，任取其中一个共轭类 $D$，令 $C' = C \backslash D$。 设 $D$ 中的词均落在 $X^d$ 中且 $X$-指数同为 $q$，此时 $D$ 由某个 $X$-本原词的循环移位构成，故 $|D| = \dfrac{d}{q}$，则有 $$ \sum_{k \in \mathbb{N}_+} \frac{1}{k} |C \cap X^k| = \sum_{k \in \mathbb{N}_+} \frac{1}{k} |C' \cap X^k| + \frac{1}{d} |D \cap X^d| \geq \frac{1}{q} \geq \frac{1}{p} $$ ……其中等号成立当且仅当 $C' \cap X^* = \varnothing$ 且 $q = p$，也即 $C \cap X^*$ 构成一个 $X$-共轭类，且其中词的指数均为 $p$。 再说明取等的等价条件。由 **引理 5.4.4** 可知 $X$ 为循环码当且仅当 $X^*$ 极纯，而由 **引理 5.4.6** 可知这又等价于 $X^*$ 纯且在 $X^*$ 中共轭者也必 $X$-共轭。而易见 $X^*$ 纯等价于其中词的指数与其 $X$-指数一致、且在 $X^*$ 中共轭者也必 $X$-共轭等价于 $C \cap X^*$ 为一个 $X$-共轭类。对比上面等号成立的条件，明所欲证。 #### 定义 5.4.8 (分解) 设 $I$ 为全序集，$(X_i)_{i \in I}$ 为一族 $A^+$ 的子集，称一族集合是 $A^*$ 的一个分解，若任给 $w \in A^+$ 都有唯一不增分解 $$ w = x_1 \cdots x_n, \quad n \in \mathbb{N}_+, x_i \in X_{j_i}, j_1 \geq \cdots \geq j_n $$ #### 定理 5.4.9 (Schützenberger, 1965) > 设 $I$ 为全序集，$(X_i)_{i \in I}$ 为一族 $A^+$ 的子集，则这一族集合是 $A^*$ 的一个分解当且仅当以下三项中任意两项均蕴含第三项（因而任意两项成立当且仅当三项全部成立）： > > (i) 每个词至少有一个分解；\ > > (ii) 每个词至多有一个分解；\ > > (iii) 每个 $X_i$ 都为循环码，且 $A^+$ 中的每个共轭类恰与一个子幺半群 $X_i^*$ 相交。 _Proof._ 显然 $(\text{i}) + (\text{ii})$ 就是分解的定义，故只需证明三者中任意两者可以推出另一者。 $(\text{i}) + (\text{ii}) \Rightarrow (\text{iii})$：显见 $X_i$ 均为码。在 $\mathbb{Q}$ 中有特征级数等式 $$ \underline{A}^* = \prod_{i \in I} \underline{X_i}^* \Leftrightarrow (1 - \underline{A})^{-1} = \prod_{i \in I} (1 - \underline{X_i})^{-1} $$ 对等式两边同时取对数，由 **推论 5.3.28** 可知 $$ \log (1 - \underline{A})^{-1} = \sum_{i \in I} \log (1 - \underline{X_i})^{-1} + z \quad (\textbf{E1}) $$ 其中 $z \in S'$。 设 $C$ 为 $A^*$ 中的一个共轭类，令 $n$ 为其中词的长度，$p$ 为指数，则 $C$ 中有 $\dfrac{n}{p}$ 个互不相同的共轭词，则有 $$ \langle \log (1 - \underline{A})^{-1}, C \rangle = \frac{1}{n} \langle \underline{A}^n, \underline{C} \rangle = \frac{1}{p} \quad (\textbf{E2}) $$ 留意到交换子零化与共轭类的配对：因为 $\langle \underline{uv}, \underline{C} \rangle = \langle \underline{vu}, \underline{C} \rangle \in \{0, 1\}$，得到 $\langle [u, v], \underline{C} \rangle = 0$，进而可见 $\langle z, \underline{C} \rangle = 0$，故 $$ \sum_{i \in I} \langle \log (1 - \underline{X_i})^{-1}, C \rangle = \frac{1}{p} \quad (\textbf{E3}) $$ 由 **命题 5.4.7** 可知 $C \cap X_i^* \neq \varnothing \Rightarrow \langle \log (1 - \underline{X_i})^{-1}, C \rangle \geq \dfrac{1}{p}$。对比 $\textbf{E3}$ 可见每个 $C$ 恰与一个 $X_i^*$ 相交，且对相交的 $i$ 等号成立；再由 **命题 5.4.7** 的等号刻画可知每个 $X_i$ 都为循环码。明所欲证。 $(\text{iii}) \Rightarrow ((\text{i}) \Leftrightarrow (\text{ii}))$：记 $M_i = X_i^*$。固定共轭类 $C$，设其中词的指数为 $p$： - 一方面，由 (iii) 可知恰有一个 $i \in I$ 使得 $C \cap M_i \neq \varnothing$，再由 **命题 5.4.7 (2)** 即得 $\langle \log (1 - \underline{X_i})^{-1}, C \rangle = \dfrac{1}{p}$。 - 另一方面，由 (iii) 可知 $\forall j \in I \backslash \{i\}, C \cap M_j = \varnothing$，再由 **命题 5.4.7 (1)** 即得 $\langle \log (1 - \underline{X_j})^{-1}, C \rangle = 0$。 总之有 $\displaystyle\sum_{i \in I} \langle \log (1 - \underline{X_i})^{-1}, C \rangle = \frac{1}{p}$ 即 $\mathbf{E3}$ 成立。令 $z = \log(1 - \underline{A})^{-1} - \displaystyle\sum_{i \in I} \log(1 - \underline{X_i})^{-1}$，再由 $\textbf{E2}$ 可知 $\langle z, \underline{C} \rangle = 0$。 下面根据 $C$ 的任意性证明 $z \in S'$： - 做共轭分解 $z = \displaystyle\sum_C \sum_{w \in C} a_w w$，由 $\langle z, \underline{C} \rangle = 0$ 可知 $\displaystyle\sum_{w \in C} a_w = 0$，任取代表元 $\text{rep}_C \in C$，则 $$ \sum_{w \in C} a_w w = \sum_{w \in C} a_w (w - \text{rep}_C) + \left( \sum_{w \in C} a_w \right) \text{rep}_C = \sum_{w \in C} a_w (w - \text{rep}_C) $$ - 由 $w, \text{rep}_C$ 共轭可知 $w - \text{rep}_C$ 可以表示为交换子，进而 $z \in S'$。明所欲证。 设 $\alpha : \mathbb{Q} \langle \langle A \rangle \rangle \to \mathbb{Q}[[A]]$ 为典范交换化态射，其中 $\mathbb{Q}[[A]] = \mathbb{Q}^{\mathbb{N}^A}$ 为 **交换形式幂级数环**。由 $\alpha(z) = 0$ 可知 $$ \alpha(\log(1 - \underline{A})^{-1}) = \sum_{i \in I} \alpha(\log(1 - \underline{X_i})^{-1}) $$ 由于 $\alpha$ 连续，有 $$ \log(1 - \alpha(\underline{A}))^{-1} = \sum_{i \in I} \log(1 - \alpha(\underline{X_i}))^{-1} $$ 也即 $$ (1 - \alpha(\underline{A}))^{-1} = \prod_{i \in I} (1 - \alpha(\underline{X_i}))^{-1} $$ 令 $R = \underline{A}^* - \displaystyle\prod_{i \in I} \underline{X_i}^*$，则 $(\text{i}) \Leftrightarrow R$ 的系数非正，$(\text{ii}) \Leftrightarrow R$ 的系数非负，而上文已由 $(\text{iii})$ 证得 $\alpha(R) = 0$。 因此 $(\text{iii}) + (\text{i}) / (\text{ii}) \Rightarrow R = 0$。明所欲证。 #### 例子 5.4.10 (二分) 设 $(X, Y)$ 为 $A^*$ 的二分，可直接验证 **定理 5.4.9** 的 (iii) 成立： > I. 由 $YX \subset X^* \cup Y^*$ 可反复合并 $yx$ 而证得 $Y^* X^* \subset X^* \cup Y^*$，故任何 $w = xy \ (x \in X^*, y \in Y^*)$ 的共轭 $yx$ 都落在 $X^* \cup Y^*$ 中。即每个共轭类至少与一个子幺半群相交。\ > II. 若 $uv \in X^+, vu \in Y^+$，由 **推论 5.2.9 (1)** 得 $v \in X^*$，由 **推论 5.2.9 (2)** 得 $v \in Y^*$，故由 **引理 5.2.10** 得到 $v \in X^* \cap Y^* = \{\varepsilon\}$，$v = \varepsilon$，进而 $uv = u \in X^+, vu = u \in Y^+ \Rightarrow u \in X^+ \cap Y^+ = \varnothing$，矛盾。即每个共轭类至多与一个子幺半群相交。\ > III. 由 **推论 5.2.9** 可知 $uv, vu \in X^* \Rightarrow u, v \in X^*$，即 $X^*$ 极纯，故由 **引理 5.4.4** 可知 $X$ 为循环码。$Y$ 的情形是同理的。 #### 例子 5.4.11 (Lyndon 分解) Lyndon 词族 $(l)_{l \in L}$ 的 (iii) 来自其定义：由 $l$ 本原及 **命题 5.4.2 (2)** 可知单点集 $\{l\}$ 皆为循环码，而 $L$ 恰为本原词共轭类的代表系。 因此由 **定理 5.4.9** 可知：若要证明 Lyndon 分解存在且唯一，只须再证 (i) 或 (ii) 之一。 #### 定义 5.4.12 (完全) 称 $A^*$ 的分解 $(X_i)_{i \in I}$ 完全，若每个 $X_i$ 都是单点集。 #### 推论 5.4.13 > 若 $A^*$ 的分解 $(X_i)_{i \in I}$ 完全，则 $\displaystyle\bigsqcup_{i \in I} X_i$ 恰为本原词共轭类的代表系。 _Proof._ 由 **定理 5.4.9** 的 (iii) 可知每个共轭类恰与一个 $x_i^* \ (X_i = \{x_i\})$ 相交，且每个 $\{x_i\}$ 为循环码，故由 **命题 5.4.2 (2)** 可知 $x_i$ 本原。 一方面，由存在性设本原词 $u$ 的共轭类与 $x_i^*$ 有交，取 $m \in C_u \cap x_i^*$，设 $m = x_i^k$，由 $m \sim u$ 本原可知 $k = 1$，故 $x_i$ 可取为 $u$ 所在共轭类的代表；另一方面，由唯一性可知这样的 $x_i$ 对每个本原词 $u$ 唯一。明所欲证。 #### 定理 5.4.14 (Spitzer) > 设 $\varphi : A^* \to \mathbb{R}$ 为幺半群同态，对 $r \in \mathbb{R}$ 令 > $$ > C_r = \{w \in A^+ \mid \varphi(w) = r |w|\}, > \qquad > B_r = C_r \setminus \bigcup_{s \geq r} C_s A^+. > $$ > 等价地，$w \in B_r$ 当且仅当 $w$ 的平均值为 $r$，且 $w$ 的每个非空真前缀 $u$ 都满足 $\varphi(u) < r |u|$。则 $(B_r)_{r \in \mathbb{R}}$（按 $\mathbb{R}$ 的通常全序）为 $A^*$ 的一个分解。 _Intuition._ 设 $w \in A^+$，将词 $w = a_1 \cdots a_n \ (a_i \in A)$ 画成“随机游走折线图”——即点集 $\{(i, \varphi(a_1 \cdots a_i)) \mid 0 \leq i \leq n\}$，取这些点构成的上凸壳，将落在其上边界的顶点作为切点，每一段的平均斜率即该段所属 $B_r$ 的下标。由上凸壳的性质可见这样的分解是唯一的。 _Proof._ 参见 [4]。 #### 定理 5.4.15 (Viennot) > 设 $X$ 为 $A^+$ 的全序子集，满足： > > (i) $X = A \cup \{xy \mid x, y \in X, x < y\}$；\ > > (ii) $\forall x, y \in X, x < y \Rightarrow x < xy < y$。 > > 则 $(x)_{x \in X}$ 为 $A^*$ 的一个分解。 _Rmk._ 易见 Lyndon 分解是 Viennot 分解的特例。 _Proof._ 对 $s \in \mathbb{N}_+$ 归纳证明：任给字母表 $A$ 和全序子集 $X \subset A^+$，每个长度为 $s$ 的 $w \in A^+$ 可唯一表作 $w = x_1 \cdots x_n \ (n \in \mathbb{N}_+, x_i \in X, x_1 \geq \cdots \geq x_n)$ 的形式。 当 $|w| = 1$，由 $w \in A \subset X$ 立即可得。下面讨论 $|w| > 1$ 的情形。 不妨设 $A = \text{alph}(w)$（若不然，令 $A' = \text{alph}(w), X' = X \cap A'^*$，其与 $A, X$ 具有相似的性质），则 $A$ 为有限集。 设 $a = \min A$，下面归纳证明 $a$ 亦为 $X$ 中的最小元。设 $w \in X$： - I. 当 $w = a' \in A$，由定义有 $a \leq a' = w$。 - II. 当 $w = xy \ (x, y \in X, x < y)$，由归纳假设可知 $a \leq x$，故 $a \leq x < xy = w$。 令 $Z = a^* (A \setminus \{a\})$，由 $Z \sqcup \{a\} = aZ \sqcup A$ 可知 $(Z, \{a\})$ 为 $A^*$ 的一个二分，则每个 $w \in A^*$ 可唯一表作 $$ w = za^l, \quad z \in Z^*, l \in \mathbb{N} $$ 若 $z = \varepsilon$ 则命题显然成立；下面讨论 $z \neq \varepsilon$ 的情形。 > **命题 5.4.16** > > $Z \subset X \subset Z^* \cup \{a\}$。 > > _Proof._ 先证 $Z \subset X$。也即证 $\forall b \in A \backslash \{a\}, i \in \mathbb{N}, a^i b \in X$，由 $b \in X$ 且 $\forall i \in \mathbb{N}_+, a^i b = a \cdot a^{i - 1} b, a < a^{i - 1} b$ 对 $i$ 归纳即得。\ > 再证 $\forall w \in X \backslash Z \backslash \{a\}, \exists x, y \in X \backslash \{a\}, \text{s.t. } w = xy, x < y$。对 $|w|$ 归纳：先由 (i) 取 $x, y \in X$ 使得 $w = xy, x < y$ 且 $|x|$ 最大。 > > I. 若 $x \in X \backslash \{a\}$，命题成立。\ > > II. 若 $x = a$，则 $y \not\in Z \cup \{a\}$（否则 $w \in Z$ 或 $w = a^2 \in X$ 皆矛盾），由归纳假设取 $p, q \in X \backslash \{a\}$ 使得 $y = pq, p < q$，则有 $a < p < q$。\ > > 故由 (i) 可知 $ap \in X \backslash \{a\}$ 且由 (ii) 可知 $a < ap < p$，于是还有 $ap < p < q$。但 $|ap| > |a| = |x|$，与 $|x|$ 最大矛盾！ > > 最后证明 $X \subset Z^* \cup \{a\}$。也即证 $\forall w \in X, w \in Z^* \cup \{a\}$，对 $|w|$ 归纳： > > I. 若 $|w| = 1$，则 $w = a' \in A$，若 $a' \neq a$ 则 $a' \in Z$，故总有 $w = a' \in Z \cup \{a\} \subset Z^* \cup \{a\}$，命题成立。\ > > II. 若 $|w| > 1$，由上取 $w = xy$ 使得 $x, y \in X \backslash \{a\}, w = xy, x < y$，由归纳假设可知 $x, y \in Z^* \cup \{a\}$，但由 $x, y \neq a$ 可知 $x, y \in Z^*$，故 $w = xy \in Z^* \subset Z^* \cup \{a\}$，命题成立。 考察双射 $\beta : B \to Z$，诱导出自由幺半群的同构 $\beta : B^* \to Z^*$，给 $Y = \beta^{-1}(X \backslash \{a\})$ 赋予全序 $$ y < y' \Leftrightarrow \beta(y) < \beta(y') $$ 依 **命题 5.4.16** 之葫芦画瓢可见 $(B, Y)$ 亦满足 (i)(ii)。 设 $\beta^{-1}(z) = b_1 \cdots b_k \ (k \in \mathbb{N}_+)$，则 $|\beta^{-1}(z)|_B \leq \displaystyle\sum_{i = 1}^k |\beta(b_i)|_A = |z|_A$，于是 $|\beta^{-1}(z)|_B \leq |z|_A \leq |w|_A$，断言两个不等号不能同时取等： - I. 若前者取等，则 $\forall 1 \leq i \leq k, |\beta(b_i)|_A = 1$，即 $\beta(b_i) \in A \backslash \{a\}$。 - II. 若后者取等，则 $l = 0$。 - 总之若两者同时取等，有 $a \not\in \text{alph}(w)$，矛盾！ 故有 $|\beta^{-1}(z)|_B < |w|_A$，长度减小，由归纳假设可知有 $B^*$ 中的唯一不增分解 $$ \beta^{-1}(z) = t_1 \cdots t_m, \quad m \in \mathbb{N}_+, t_i \in Y, t_1 \geq \cdots \geq t_m $$ 这与 $Z^*$ 中的唯一不增分解 $$ z = \beta(t_1) \cdots \beta(t_m), \quad \beta(t_i) \in X, \beta(t_i) \geq \cdots \geq \beta(t_m) $$ 一一对应，因此 $w$ 有唯一的不增分解 $$ w = \beta(t_1) \cdots \beta(t_m) a \cdots a, \quad (l \text{ 个 } a) $$ 明所欲证。 ### References 1. M. Lothaire, _Combinatorics on Words_, Cambridge Mathematical Library, Cambridge University Press, 1997 reprint of the 1983 edition, Chapter 5. 2. J.-P. Duval, "Factorizing Words over an Ordered Alphabet," _Journal of Algorithms_ 4(4) (1983), 363-381. <https://www.sciencedirect.com/science/article/pii/0196677483900172> 3. M. H. A. Newman, "On Theories with a Combinatorial Definition of Equivalence," _Annals of Mathematics_ 43(2) (1942), 223-243. <https://doi.org/10.2307/1968867> 4. F. Spitzer, "A Combinatorial Lemma and Its Application to Probability Theory," _Transactions of the American Mathematical Society_ 82 (1956), 323-339. <https://doi.org/10.1090/S0002-9947-1956-0079851-X> 5. J. Berstel, D. Perrin, C. Reutenauer, _Codes and Automata_, Encyclopedia of Mathematics and its Applications 129, Cambridge University Press, 2010, §§7.1, 8.1.