无平方词与幂等半群

· · 算法·理论

无平方词与幂等半群

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

2.1 预备知识

定义 2.1.1 (不交, 相邻, 重叠)

设 A 为字母表，w, u \in A^+，当 u 在 w 中作为子词出现至少两次：

\exists x, y, x', y' \in A^*, \text{s.t. } x \neq x', w = xuy = x' uy'

不妨设 |x| < |x'|，则有三种可能：

引理 2.1.2

设 w \in A^+，则 w 包含某一 u \in A^+ 的两个重叠出现当且仅当 w 包含形如 avava 的子词，其中 a \in A, v \in A^*。

Proof. 充分性显然，因为 u = ava 在 w 中有两个重叠的出现。

下证必要性。设 w = xuy = x' uy'，其中 u \in A^+ 的这两次出现重叠，则 |x| < |x'| < |xu| < |x' u|，从而：

\exists s, z, t \in A^+, \text{s.t. } x' = xs, xu = x' z, x' u = xut

故有 u = sz = zt。设 a 为 s 的首字母，则 a 也为 z 的首字母。

令 s = av, z = az'，则有 u = avaz'，最终给出：

w = xavavaz' y'

定义 2.1.3 (无限词)

设 A 为字母表，A 上的无限词是一个函数 \mathbf{a} : \mathbb{N} \to A，我们使用记号

\mathbf{a} = a_0 a_1 \cdots a_n \cdots

表达，其中 a_n = \mathbf{a}(n)。记其长为 k \in \mathbb{N} 的前缀为

\mathbf{a}^{(k)} = a_0 a_1 \cdots a_{k - 1} \in A^*

设 u \in A^+，当 u = \mathbf{a}^{(k)}, k = |u|，记 u < \mathbf{a}，此时称 \mathbf{a} = u \mathbf{b}，其中 \mathbf{b}(m) = \mathbf{a}(m + k), \forall m \in \mathbb{N}。

#### 定义 2.1.4 (对子词稳定) 称对有限词而言的性质 $P$ 对子词稳定，若： $$ \forall x, u, y \in A^*, P(xuy) \Rightarrow P(u) $$ 进一步地，称无限词 $\mathbf{a}$ 满足性质 $P$，若其所有子词都满足性质 $P$。 留意到“无平方词”也是一个对子词稳定的性质，因此讨论“无限无平方词”是有意义的。 #### 引理 2.1.5 > 设 $A$ 为**有限**字母表，$P$ 是 $A^*$ 中元素的一个对子词稳定的性质，则下列条件等价：\ > (1) $L_P = \{w \in A^* \mid P(w)\}$ 为无限集。\ > (2) $\exists \mathbf{a} : \mathbb{N} \to A, \text{s.t. } P(\mathbf{a})$。 _Proof._ $(2) \Rightarrow (1)$：$L_P$ 中显然包含 $\mathbf{a}$ 的所有前缀，故包含至少可数个元素。 $(1) \Rightarrow (2)$：由 $A$ 有限可知 $L_P$ 中有无限多个词以同一字母开头，设为 $a_0$，并令 $L_0 = L_P \cap a_0 A^*$。归纳假设 $\exists a_0, a_1, \cdots, a_n \in A, \text{s.t. } L_n = L_P \cap a_0 a_1 \cdots a_n A^*$ 为无限集，则可再选取 $a_{n + 1}$ 使得如此得到的 $L_{n + 1}$ 仍无限。 这样，存在 $A$ 中的一列字母 $a_0, a_1, \cdots, a_n, \cdots$ 使得其每个前缀都满足 $P$，这就构造出了一个 $\mathbf{a} : \mathbb{N} \to A$，其中 $\mathbf{a}(n) = a_n$。明所欲证。 ------ 上面的证明蕴含了一种直观的从有限词序列出发构造无限词的方法。 设 $w_0, w_1, \cdots, w_n, \cdots \in A^*$ 是 $A^*$ 中长度无界的一列词，满足每个 $w_n$ 都是 $w_{n + 1}$ 的前缀，则可定义 $A$ 上的一个无限词 $\mathbf{a}$： $$ \mathbf{a}^{(k)} = w_n^{(k)}, \quad |w_n| \geq k $$ 良定义性显然，这样定义出来的无限词称为这一列有限词的极限，记作： $$ \mathbf{a} = \lim_{n \to \infty} w_n $$ #### 例子 2.1.6 设 $\alpha : A^* \to A^*$ 为非抹除的幺半群同态，满足： $$ \exists a_0 \in A, u \in A^+, \text{s.t. } \alpha(a_0) = a_0 u $$ 则 $\forall n \in \mathbb{N}, \alpha^{n + 1}(a_0) = \alpha^n(a_0 u) = \alpha^n(a_0) \alpha^n(u)$，故每个 $\alpha^n(a_0)$ 都是 $\alpha^{n + 1}(a_0)$ 的真前缀，进而极限 $$ \alpha^{\omega}(a_0) = \lim_{n \to \infty} \alpha^n(a_0) $$ 存在，称这一无限词由 $\alpha$ 在 $a_0$ 上**迭代**得到。 下面将 $\alpha$ 延拓到无限词上。对于 $\mathbf{b} = b_0 b_1 \cdots b_n \cdots$，令 $\alpha(\mathbf{b}) = \alpha(b_0) \alpha(b_1) \cdots \alpha(b_n) \cdots$，(i) 则确保 $\alpha(\mathbf{b})$ 为无限词。 由此注意到 $\mathbf{a} = \alpha^{\omega}(a_0)$ 为 $\alpha$ 的不动点，即 $\alpha(\mathbf{a}) = \mathbf{a}$：考虑 $\alpha(\mathbf{a}^{|\alpha^n(a_0)|}) = \alpha(\alpha^n(a_0)) = \alpha^{n + 1}(a_0) = \mathbf{a}^{|\alpha^{n + 1}(a_0)|}$，可见 $\alpha(\mathbf{a})$ 的前 $|\alpha^{n + 1}(a_0)|$ 位与 $\mathbf{a}$ 一致，再由其无界性立即可得。 ### 2.2 Thue-Morse 无限词 #### 定义 2.2.1 (Thue-Morse 无限词) 设 $A = \{a, b\}$，定义幺半群同态 $\mu : A^* \to A^*$，满足 $\mu(a) = ab, \mu(b) = ba$。 由 **例子 2.1.6** 可知，将 $\mu$ 在 $a, b$ 上分别迭代将得到两个无限词 $\mathbf{t} = \mu^{\omega}(a), \overline{\mathbf{t}} = \mu^{\omega}(b)$，二者前几项为： $$ \begin{cases} \mathbf{t} = abbabaabbaababba \cdots \\ \overline{\mathbf{t}} = baababbaabbabaab \cdots \end{cases} $$ 可以发现 $\mathbf{t}, \overline{\mathbf{t}}$ 间似乎就是把 $a, b$ 互换了。下面加以探究。 ------ 考察 $\bar{a} = b, \bar{b} = a$ 所定义的幺半群同态 $w \mapsto \bar{w}$，显见 $\overline{\overline{w}} = w$。注意与字符串反转的 $w \mapsto \tilde{w}$ 相区分。 #### 命题 2.2.2 > 设 $u_0 = a, v_0 = b$，并有递推式 $u_{n + 1} = u_n v_n, v_{n + 1} = v_n u_n, \forall n \in \mathbb{N}$，则：\ > (1) $u_n = \mu^n(a), v_n = \mu^n(b)$。\ > (2) $v_n = \overline{u_n}, u_n = \overline{v_n}$。\ > (3) $u_{2n}, v_{2n}$ 为回文词，$\tilde{u}_{2n + 1} = v_{2n + 1}$。 _Proof._ 归纳即得。 有趣的是，$\mathbf{t}$ 也有一种不依赖于 $\mu$ 的构造；尽管与主线无关，仍在此记录如下。 #### 命题 2.2.3 > 设 $n \in \mathbb{N}$，则： $$ t_n = \begin{cases} a, &\quad d_2(n) \equiv 0 \pmod 2 \\ b, &\quad d_2(n) \equiv 1 \pmod 2 \end{cases} $$ > 其中 $d_2(n)$ 表示 $n$ 的二进制表示中 $1$ 的数量。 _Proof._ 考虑对 $n$ 归纳，首先 $n = 0$ 时显然成立。 由 **例子 2.1.6** 可知 $\mathbf{t} = \mu(\mathbf{t}) = \mu(t_0) \mu(t_1) \cdots \mu(t_n) \cdots$，故 $\mu(t_n) = t_{2n} t_{2n + 1}$，则有 $t_{2n} = t_n, t_{2n + 1} = \overline{t_n}$。 当 $n > 0$：若 $n = 2m$，则 $t_n = t_m, d_2(n) = d_2(m)$，命题成立；若 $n = 2m + 1$，则 $t_n = \overline{t_m}, d_2(n) = d_2(m) + 1$，命题成立。进而容易推知等式对 $n$ 仍成立。 ------ 尽管 $\mathbf{t}$ 并非是无平方词（如其有子词 $bb$），但仍有下列结论。 #### 引理 2.2.4 > 设 $X = \{ab, ba\}$，若 $x \in X^*, c \in A$，则 $cxc \not\in X^*$。 _Proof._ $X^*$ 中的项都满足 $a, b$ 出现次数之差为 $0$，$x \in X^*$ 时 $cxc \in X^*$ 显然不满足条件。 #### 引理 2.2.5 > 设 $w \in A^+$，若 $w$ 没有重叠出现的子词，则 $\mu(w)$ 也没有重叠出现的子词。 _Proof._ 考虑反证法：设 $\mu(w)$ 有重叠出现的子词，欲证 $w$ 也有重叠出现的子词。 由 **引理 2.1.2** 可知： $$ \exists x, v, y \in A^*, c \in A, \text{s.t. } \mu(w) = xcvcvcy $$ 取 $X$ 如 **引理 2.2.4** 所示，则 $\mu(w) \in X^*$，故 $|\mu(w)|$ 为偶数而 $|xy|$ 为奇数，因而： - (i) 要么 $|x|$ 为偶数，$x, cvcv, cy \in X^*$。 - (ii) 要么 $|x|$ 为奇数，$xc, vcvc, y \in X^*$。 若 $|v|$ 为偶数，则由 $cvcv \in X^* / vcvc \in X^*$ 可知 $v, cvc \in X^*$，与 **引理 2.2.4** 矛盾！故 $|v|$ 为奇数。 - (i) 当 $|x|$ 为偶数，有 $cv \in X^*, w = rsst$，其中 $\mu(r) = x, \mu(s) = cv, \mu(t) = cy$，可见 $s, t$ 以同一字母 $c$ 开头，故 $sc$ 在 $w$ 中重叠出现。 - (ii) 当 $|x|$ 为奇数，有 $vc \in X^*, w = rsst$，其中 $\mu(r) = xc, \mu(s) = vc, \mu(t) = y$，可见 $r, s$ 以同一字母 $\bar{c}$ 结尾，故 $\bar{c} s$ 在 $w$ 中重叠出现。 #### 定理 2.2.6 > $\mathbf{t}$ 没有重叠出现的子词。 _Proof._ 若有重叠出现的子词，则必然包含于某一 $\mu^k(a)$ 中；但由于 $a$ 没有重叠出现的子词，据 **引理 2.2.5** 归纳可知 $\mu^k(a)$ 没有重叠出现的子词，矛盾！ #### 推论 2.2.7 > $\mathbf{t}$ 是无立方词。 _Proof._ 若 $c \in A, w \in A^*$ 使得 $cwcwcw$ 为 $\mathbf{t}$ 的子词，则 $cwcwc$ 也为 $\mathbf{t}$ 的子词，由 **引理 2.1.2** 可知 $\mathbf{t}$ 有重叠出现的子词，与 **定理 2.2.6** 矛盾！故 $\mathbf{t}$ 是无立方词。 ### 2.3 无限无平方词 上一节中讨论的 Thue-Morse 无限词有平方子词；先来稍微探究一下是否存在字母表大小为 $2$ 的无限无平方词。 #### 命题 2.3.1 > 设 $A = \{a, b\}$，则无平方的 $w \in A^+$ 只有 $a, b, ab, ba, aba, bab$ 六个。 _Proof._ $|w| \leq 3$ 的情况可以直接枚举验证；当 $|w| > 3$，无平方要求相邻字母不同，故只能形如 $abab \cdots, baba \cdots$，则长为 $4$ 的前缀已然构成平方词。 #### 推论 2.3.2 > 设 $A = \{a, b\}$，则不存在 $A$ 上的无限无平方词。 _Proof._ 由 $A$ 上的有限无平方词长度有界立即可得。 ------ 与字母表大小为 $2$ 的情况不同，事实上存在字母表大小为 $3$ 的无限无平方词，下面加以讨论。 设 $A = \{a, b\}, B = \{a, b, c\}$，通过 $\delta(c) = a, \delta(b) = ab, \delta(a) = abb$ 定义幺半群同态 $\delta : B^* \to A^*$。 任给 $B$ 上的无限词 $\mathbf{b}$，$\delta(\mathbf{b}) = \delta(b_0) \delta(b_1) \cdots \delta(b_n) \cdots$ 是一个良定义的 $A$ 上的无限词，且以 $a$ 开头。 反之，任给没有重叠出现的子词的 $A$ 上的无限词 $\mathbf{a}$，且以 $a$ 开头，则 $\mathbf{a}$ 可被分解为 $\mathbf{a} = y_0 y_1 \cdots y_n \cdots$，其中 $y_n \in \delta(B)$，这是因为 $bbb$ 有重叠出现的子词 $bb$。进一步地，容易证明这样的分解是唯一的，故有： $$ \exists ! \mathbf{b} : \mathbb{N} \to B, \text{s.t. } \delta(\mathbf{b}) = \mathbf{a} $$ #### 定理 2.3.3 > 设 $A$ 上的无限词 $\mathbf{a}$ 没有重叠出现的子词，其以 $a$ 开头，并令 $\mathbf{b}$ 为唯一满足 $\delta(\mathbf{b}) = \mathbf{a}$ 的 $B$ 上的无限词，则 $\mathbf{b}$ 为无限无平方词。 _Proof._ 假设 $\mathbf{b}$ 中包含平方词 $uu$，$d$ 为 $uu$ 在 $\mathbf{b}$ 中的某个出现的下一个字母，则 $\delta(uud)$ 为 $\mathbf{a}$ 的子词。设 $\delta(u) = av, \delta(d) = aw$，则 $\delta(uud) = avavaw$ 包含重叠出现的子词 $ava$，矛盾！ 将该定理应用于 Thue-Morse 词 $\mathbf{t}$，得到无限无平方词： $$ \mathbf{m} = abcacbabcbacabc \cdots $$ 还有其他得到 $\mathbf{m}$ 的方式，这里仅举一例。 #### 命题 2.3.4 > 通过 $\varphi(a) = abc, \varphi(b) = ac, \varphi(c) = b$ 定义幺半群同态 $\varphi : B^* \to B^*$，则 $\mathbf{m} = \varphi^{\omega}(a)$。 _Proof._ 归纳可知 $\delta(\varphi^k(a)) = u_{k + 1} v_k, \delta(\varphi^k(b)) = u_{k + 1}, \delta(\varphi^k(c)) = u_k$，旋即易证。 不过值得一提的是 **定理 2.3.3** 的逆命题并不成立；一个修改后正确的叙述如下。 #### 定理 2.3.5 (Thue, 1912) > $\mathbf{b}$ 是一个不含子词 $aba, acbca$ 的无限无平方词当且仅当 $\delta(\mathbf{b})$ 没有重叠出现的子词。 _Proof._ 先证充分性。设 $\delta(\mathbf{b})$ 没有重叠出现的子词。由 $\delta$ 的定义可知 $\mathbf{a} = \delta(\mathbf{b})$ 以 $a$ 开头，而 $\mathbf{b}$ 为唯一的词 $\tilde{\mathbf{b}}$ 使得 $\mathbf{a} = \delta(\tilde{\mathbf{b}})$，故由 **定理 2.3.3** 可知 $\mathbf{b}$ 为无限无平方词。 同时若 $\mathbf{b}$ 含子词 $aba / acbca$，则 $\delta(\mathbf{b})$ 含子词 $ab \textbf{babab} b / ab \textbf{baabaab} b$，与 $\delta(\mathbf{b})$ 没有重叠出现的子词矛盾！明所欲证。 再证必要性。假设 $\delta(\mathbf{b})$ 有重叠出现的子词，则由 **引理 2.1.2** 可知其包含形如 $dvdvd$ 的串，其中 $d \in A, v \in A^*$。 设 $\mathbf{b}$ 有前缀 $x$ 满足 $\delta(x) = pdvdvdq$，其中 $p, q \in A^*$。 若 $d = a$ 则 $x = rsst$，其中 $\delta(r) = p, \delta(s) = av, \delta(t) = aq$，与 $\mathbf{b}$ 是无平方词矛盾！ 故 $d = b$，则 $\delta(x) = pbvbvbq$，显见 $v \neq \varepsilon, b$、$v$ 的开头结尾至多只有一个 $b$，且 $v$ 不可能同时以 $b$ 开头结尾。对剩余情况分类讨论： - (i) $v = a$：此时 $\delta(x) = pbababq$，则 $x = rbs$，其中 $\delta(r) = pb, \delta(s) = abq$，当 $q = \varepsilon$ 或以 $a$ 开头时 $s$ 将以 $b$ 开头，与 $\mathbf{b}$ 是无平方词矛盾！ - - 故 $s$ 以 $a$ 开头。显然 $p \neq \varepsilon$：当 $p$ 以 $a$ 结尾时 $r$ 将以 $b$ 结尾，与 $\mathbf{b}$ 是无平方词矛盾；当 $p$ 以 $b$ 结尾时 $r$ 将以 $a$ 结尾，与 $\mathbf{b}$ 不含子词 $aba$ 矛盾！ - (ii) $v = av' a, v' \in A^*$：此时 $\delta(x) = pbav' abav' abq$，则 $x = rsbst$，其中 $\delta(r) = pb, \delta(s) = av', \delta(t) = abq$，当 $q = \varepsilon$ 或以 $a$ 开头时 $t$ 将以 $b$ 开头，与 $\mathbf{b}$ 是无平方词矛盾！ - - 故 $q$ 以 $b$ 开头。显然 $p \neq \varepsilon$：当 $p$ 以 $a$ 结尾时 $r$ 将以 $b$ 结尾，与 $\mathbf{b}$ 是无平方词矛盾！ - - 故 $p$ 以 $b$ 结尾，则 $r$ 将以 $a$ 结尾，此时 $\mathbf{b}$ 包含子词 $asbsa$，其中 $s \neq \varepsilon$。若 $s$ 以 $a, b$ 之一开头或结尾都将出现 $aa$ 或 $bb$ 连续出现的情况，与 $\mathbf{b}$ 是无平方词矛盾！ - - 故 $s$ 以 $c$ 开头结尾，下面分类讨论： - - - I. $s = c$：此时 $asbsa = acbca$，与 $\mathbf{b}$ 不含子词 $acbca$ 矛盾！ - - - II. $s = cs' c$：此时 $asbsa = acs' cbcs' ca$，显见 $s' \neq \varepsilon$（不然引入平方子词 $cc$）；由 $\mathbf{b}$ 为无平方词可知 $s'$ 不以 $b, c$ 开头（不然引入平方子词 $cbcb, cc$）、也不以 $b, c$ 结尾（不然引入平方子词 $bcbc, cc$），故只能以 $a$ 开头结尾，与 $\mathbf{b}$ 不含子词 $acbca$ 矛盾！ - (iii) $v = av' b, v' \in A^*$：此时 $\delta(x) = pbav' bbav' bbq$，则 $x = rsasat$，其中 $\delta(r) = pb, \delta(s) a = av', \delta(t) = q$，与 $\mathbf{b}$ 是无平方词矛盾！ - (iv) $v = bv' a, v' \in A^*$：此时 $\delta(x) = pbbv' abbv' abq$，则 $x = rasast$，其中 $\delta(r)a = p, \delta(s) = v', \delta(t) = abq$，与 $\mathbf{b}$ 是无平方词矛盾！ ------ 下面 $A, B$ 等重新用于表示任意的字母表。 #### 定义 2.3.6 (无平方) 称幺半群同态 $\alpha : A^* \to B^*$ 是无平方的，若 $\alpha(A) \neq \{\varepsilon\}$，且当 $w \in A^*$ 为无平方词时 $\alpha(w)$ 也为无平方词。 例如 **命题 2.3.4** 中的 $\varphi$ 不是无平方的，因为 $\varphi(aba) = ab \textbf{caca} bc$。 #### 定理 2.3.7 > 若幺半群同态 $\alpha : A^* \to B^*$ 满足：\ > (1) $\alpha(A) \neq \{\varepsilon\}$；\ > (2) $\forall$ 长度 $\leq 3$ 的无平方词 $u$，$\alpha(u)$ 为无平方词；\ > (3) $\forall a, b \in A, \alpha(a)$ 不为 $\alpha(b)$ 的真子词；\ > 则 $\alpha$ 是无平方的。 _Proof._ 由 (1) 可知 $\exists a_0 \in A, \text{s.t. } \alpha(a_0) \neq \varepsilon$，若 $a \in A$ 使得 $\alpha(a) = \varepsilon$ 则与 (3) 矛盾，故 $\varepsilon \not\in \alpha(A)$，进而由 (3) 可知 $\alpha(A)$ 既是前缀码又是后缀码。 由 (2) 可知 $\alpha$ 在字母上单射：若 $a \neq b$ 而 $\alpha(a) = \alpha(b)$，则 $ab$ 为无平方词而 $\alpha(ab) = \alpha(a)^2$ 为平方，矛盾。 > **引理 2.3.8** > > 在 **定理 2.3.7** 的条件下，若 $a_i, a \in A$ 使得 $\alpha(a_1 \cdots a_n) = x \alpha(a) y$，则 $\exists 1 \leq i \leq n, \text{s.t. } a = a_i, x = \alpha(a_1 \cdots a_{i - 1}), y = \alpha(a_{i + 1} \cdots a_n)$。 > > _Proof._ 设 $x = \alpha(a_1 \cdots a_{i - 1}) x'$，其中 $1 \leq i \leq n$ 且 $x'$ 为 $\alpha(a_i)$ 的真前缀；同理设 $y = y' \alpha(a_{j + 1} \cdots a_n)$，其中 $1 \leq j \leq n$ 且 $y'$ 为 $\alpha(a_j)$ 的真后缀。显见 $i - 1 \leq j$。 > > (i) 若 $i - 1 = j$，则只能有 $\alpha(a) = \varepsilon, x = \alpha(a_1 \cdots a_j), y = \alpha(a_{j + 1} \cdots a_n)$，矛盾！\ > > (ii) 若 $i = j$，则 $x' \alpha(a) y' = \alpha(a_i)$，要么 $\alpha(a) = \alpha(a_i) \Rightarrow a = a_i, x' = y' = \varepsilon$，命题成立；要么 $\alpha(a)$ 为 $\alpha(a_i)$ 的真子词，与 (3) 矛盾！\ > > (iii) 若 $i = j - 1$，设 $x' p = \alpha(a_i), qy' = \alpha(a_{i + 1})$，则 $p, q \neq \varepsilon$ 且 $\alpha(a) = pq$。 > > > I. 若 $a_i \neq a$ 或 $a_{i + 1} \neq a$，不妨设为前者，则 $a_i a$ 无平方但 $\alpha(a_i a) = x' p^2 q$ 不是无平方的，与 (2) 矛盾！\ > > > II. 若 $a_i = a_{i + 1} = a$，则 $\alpha(a) = pq = qp$，由 **命题 1.3.3** 可知 $p, q$ 为同一词的幂，则 $a$ 不为平方词但 $\alpha(a)$ 不是无平方的，与 (2) 矛盾！ > > > > (iv) 若 $i < j - 1$，则 $\alpha(a_{i + 1})$ 为 $\alpha(a)$ 的真子词，与 (3) 矛盾！ > > 综上，只可能是 $a = a_i, x = \alpha(a_1 \cdots a_{i - 1}), y = \alpha(a_{i + 1} \cdots a_n)$，明所欲证。 假设 $\alpha$ 不是无平方的，取长度最小的无平方词 $w = a_1 \cdots a_n \in A^+$ 使得 $\alpha(w) = yu^2 z \ (u \in B^+)$，由 (2) 可知 $n \geq 4$。 由最小性可知 $y$ 必为 $\alpha(a_1)$ 的真前缀，$z$ 必为 $\alpha(a_n)$ 的真后缀（不然更短的无平方词 $a_2 \cdots a_n$ 或 $a_1 \cdots a_{n - 1}$ 导出矛盾），故设 $\alpha(a_1) = yy', \alpha(a_n) = z'z \ (y', z' \in B^+)$。 取 $1 \leq j \leq n$ 为满足 $yu = \alpha(a_1 \cdots a_{j - 1}) s, \alpha(a_j) = st \ (s \in B^+, y, t \in B^*)$ 的最小下标。 若 $j = 1$，分类讨论： > (i) 若 $|u| \leq |t \alpha(a_2)|$，则 $u^2$ 为 $\alpha(a_1 a_2)$ 的平方子词，最短性指出 $n \leq 2$，与 (2) 矛盾！\ > (ii) 若 $|u| > |t \alpha(a_2)|$，则 $\alpha(a_2)$ 作为 $u$ 的真子词亦为 $\alpha(a_1)$ 的真子词，同时 $w$ 的无平方性要求 $a_1 \neq a_2$，但这与 (3) 矛盾！ 总之 $j = 1$ 不成立，同理可知 $j = n$ 不成立。故 $1 < j < n$，进而有： $$ u = y' \alpha(a_2 \cdots a_{j - 1}) s = t \alpha(a_{j + 1} \cdots a_{n - 1}) z' $$ 若 $yt = \varepsilon$ 即 $y = t = \varepsilon$，则 $u = \alpha(a_1 \cdots a_j) = \alpha(a_{j + 1} \cdots a_{n - 1}) z'$，由前缀码的性质可以推知： > (i) 要么 $a_1 = a_{j + 1}, \cdots, a_j = a_{2j}, \varepsilon = \alpha(a_{2j + 1} \cdots a_{n - 1}) z' \Rightarrow 2j + 1 = n, z' = \varepsilon$，则 $w = (a_1 \cdots a_j)^2 a_n$ 不是无平方的，矛盾！\ > (ii) 要么 $a_1 = a_{j + 1}, \cdots, a_k = a_{j + k}, \alpha(a_{k + 1} \cdots a_j) = z' \ (0 \leq k < j)$，于是 $\alpha(a_j)$ 为 $\alpha(a_n)$ 的真子词，与 (3) 矛盾！ 故 $yt \neq \varepsilon$，同理有 $sz \neq \varepsilon$。在上式两侧分别以 $y, t$ 和 $s, z$ 包夹，得到： $$ \begin{cases} yut = \alpha(a_1 \cdots a_j) = (y t) \alpha(a_{j + 1} \cdots a_{n - 1}) (z' t) \\ suz = (sy') \alpha(a_2 \cdots a_{j - 1}) (sz) = \alpha(a_j \cdots a_n) \end{cases} $$ 由 **引理 2.3.8** 可知： $$ \begin{cases} \exists \beta_1, \beta_2 \in A^+, \text{s.t. } a_1 \cdots a_j = \beta_1 a_{j + 1} \cdots a_{n - 1} \beta_2 \\ \exists \gamma_1, \gamma_2 \in A^+, \text{s.t. } \gamma_1 a_2 \cdots a_{j - 1} \gamma_2 = a_j \cdots a_n \end{cases} $$ 于是根据前缀码的性质有不等式： $$ \begin{cases} j \geq n - j + 1 \\ j \leq n - j + 1 \end{cases} \Rightarrow j = n - j + 1 $$ 进而据长度推知： $$ \begin{cases} \alpha(a_1) = \alpha(\beta_1) = yt, \alpha(a_j) = \alpha(\beta_2) = z' t \\ \alpha(a_j) = \alpha(\gamma_1) = sy', \alpha(a_n) = \alpha(\gamma_2) = sz \\ L \triangleq a_2 \cdots a_{j - 1} = a_{j + 1} \cdots a_{n - 1} \end{cases} $$ 这意味着 $st = z' t = sy' \Rightarrow s = z', t = y'$，于是 $\alpha(a_1 a_j a_n) = y(ts)^2 z$ 不是无平方的，由 (2) 可知 $a_1 a_j a_n$ 也不是无平方的，于是 $a_1 = a_j$ 或 $a_j = a_n$。 前者导出 $w = (a_1 L)^2 a_n$、后者导出 $w = a_1 (La_j)^2$，皆可说明 $w$ 不是无平方的。明所欲证。 #### 例子 2.3.9 设 $A = \{a, b, c\}$，通过 $\alpha(a) = abcab, \alpha(b) = acabcb, \alpha(c) = acbcacb$ 定义幺半群同态 $\alpha : A^* \to A^*$，则可以验证其满足上面定理的条件，故 $\alpha$ 是无平方的。 ### 2.4 幂等半群 设 $A$ 为至少包含 $3$ 种字母的字母表，则由 **定理 2.3.3** 可知 $A^*$ 中有无穷多个有限无平方词。另一种基于等价类的表述则是说，向 $A^*$ 添加零元 $0$（_一个更形象的称呼或许是 消没子 (annihilator)？_）得到幺半群 $A^* \sqcup \{0\}$，并考虑其中由 $$ uu \sim 0, \quad u \in A^+ $$ 生成的同余关系 $\sim$，则每个无平方词自身构成模去该同余的一个等价类，上面的结论无非是说商幺半群 $(A^* \sqcup \{0\}) / \sim$ 包含无穷多个元素。 接下来考虑另一种与无平方词有关的同余关系：取定 $n, m \in \mathbb{N}_{\geq 2} \land n \neq m$，并考虑 $A^*$ 中由 $$ u^n \equiv u^m, \quad u \in A^* $$ 生成的同余关系 $\equiv$，则每个无平方词自身同样构成模去该同余的一个等价类，因此商幺半群 $A^* / \equiv$ 同样包含无穷多个元素。 上面的讨论与经典的 Burnside 问题（_的半群版本_）有关： > 每个有限生成挠半群都只包含有限个元素吗？ 此处挠半群指每个元素都生成一个有限子半群的半群，而上面给出的同余关系则给出了否定的答案；但在一种特别的情形下，答案是肯定的，下面加以讨论。 #### 定义 2.4.1 (自由幂等幺半群) 设 $A$ 为任意的有限字母表，考虑其中由 $$ ww \sim w, \quad w \in A^* $$ 生成的同余关系 $\sim$，称商幺半群 $A^* / \sim$ 为 $A$ 上的自由幂等幺半群。 与前面给出的同余关系 $\equiv$ 不同，这里两个无平方词可能是同余的。 #### 例子 2.4.2 下面给出一个不平凡的例子：验证无平方词 $x = bacbcabc$ 与 $y = bacabc$ 同余。 令 $u = abcaca$，则有 $uy = abc \textbf{acabacab} c \sim ab \textbf{caca} bc \sim \textbf{abc}$、$x = (bacbc) abc \sim bacbcuy = vy$，其中 $v = bacbcu$。 对于 $r = bcabacbcacbcbac$，有 $xr = ba \textbf{cbcabcbcab} acbcacbcbac \sim \textbf{bacbcabacbca} cbcbac \sim b \textbf{acbcacbc} cbac \sim ba \textbf{cbcb} ac \sim \textbf{bacbac} \sim bac$。 对于 $s = rabc$，有 $y = (bac) abc \sim x (rabc) \sim xs$。 最终得到 $x \sim vy \sim vyy \sim xy \sim xxs \sim xs \sim y$。 #### 定理 2.4.3 (Green-Rees) > 设 $n = |A| \in \mathbb{N}$，则 $A$ 上的自由幂等幺半群恰有 $$ \sum_{k = 0}^n \binom{n}{k} \prod_{i = 1}^k (k - i + 1)^{2^i} $$ > 个元素。 _Proof._ 易见 $x \sim y \Rightarrow \text{alph}(x) = \text{alph}(y)$。下面先证明两个引理。 > **引理 2.4.4** > > 若 $\text{alph}(y) \subseteq \text{alph}(x)$，则 $\exists u \in A^*, \text{s.t. } x \sim xyu$。\ > > 完全对称地，有 $\exists v \in A^*, \text{s.t. } x \sim vyx$，不再赘述。 > > _Proof._ 考虑对 $|y|$ 归纳，当 $|y| = 0$ 时命题显然成立，下面讨论 $|y| > 0$ 的情况。\ > 设 $y = y' a, a \in A$，由归纳假设可知 $\exists u' \in A^*, \text{s.t. } x \sim xy' u'$，同时设 $x = zaz'$，令 $u = z' y' u'$，得到 $xyu = z \textbf{a z' y' az' y' u'} \sim zaz' y' u' = xy' u' \sim x$，明所欲证。 对于 $x \in A^+$，设 $x'$ 为其最短前缀使得 $\text{alph}(x') = \text{alph}(x)$，令 $x' = pa$，其中 $p \in A^*, a \in A$；对称地设 $x''$ 为其最短后缀使得 $\text{alph}(x'') = \text{alph}(x)$，令 $x'' = bq$，其中 $b \in A, q \in A^*$。如此，我们从 $x$ 生成了唯一的四元组 $(p, a, b, q)$，记作 $x \hat{=} (p, a, b, q)$。 > **引理 2.4.5** > > 若 $x \hat{=} (p, a, b, q)$，则 $x \sim pabq$。 > > _Proof._ 令 $x = pay = zbq, \tilde{x} = pabq$，由 **引理 2.4.4** 可知： > $$ > \begin{cases} > \exists u \in A^*, \text{s.t. } pa \sim payu = xu \\ > \exists v \in A^*, \text{s.t. } bq \sim vpabq = v \tilde{x} > \end{cases} > $$ > 则有： > $$ > \begin{cases} > \tilde{x} = pabq \sim xubq = xw > x = zbq \sim zv \tilde{x} = t \tilde{x} > \end{cases} > $$ > 其中 $w = ubq, t = zv$，最终得到： > $$ > x \sim t \tilde{x} \sim t \tilde{x} \tilde{x} \sim x \tilde{x} \sim xxw \sim xw \sim \tilde{x} > $$ 最后用四元组来重新刻画这一同余关系，即以下引理。 > **引理 2.4.6** > > 设 $x \hat{=} (p, a, b, q), x' \hat{=} (p', a', b', q')$，则 $x \sim x'$ 当且仅当 $p \sim p', a = a', b = b', q \sim q'$。 > > _Proof._ 充分性显然，下证必要性。由于 $\sim$ 由形如 $ww \sim w$ 的操作生成（_或者可以说是“归纳构造”_），只需证明 **单步** 操作的情形。\ > 设 $x = \alpha \beta \gamma, x' = \alpha \beta^2 \gamma \ (\alpha, \beta, \gamma \in A^*)$，显然 $\text{alph}(x) = \text{alph}(x')$。\ > 设 $x$ 的包含其所有字母的最短前缀为 $pa$，考察 $|pa|$ 与 $|\alpha \beta|$ 的长度关系： > > (i) 若 $|pa| \leq |\alpha \beta|$，则 $p' = p, a' = a$，自然有 $p \sim p'$。\ > > (ii) 若 $|pa| > |\alpha \beta|$，设 $p = \alpha \beta s \ (s \in A^*)$，则 $x = \alpha \beta sa \delta$ 且 $a$ 没有在 $\alpha, \beta, s$ 中出现。\ > > 对于 $x' = \alpha \beta^2 sa \delta$，显见包含其所有字母的最短前缀为 $\alpha \beta^2 sa$，因此 $p' = \alpha \beta^2 s, a' = a$，进而得到 $p \sim p'$。 > > 综上可知 $p \sim p', a = a'$，同理亦可证 $q \sim q', b = b'$。 现在对 $M = A^* / \sim$ 计数，设 $\pi : A^* \to M$ 为典范态射，并对 $B \subseteq A$ 令： $$ \bar{B} = \{x \in A^* \mid \text{alph}(x) = B\} $$ 则 $A^* = \displaystyle\bigsqcup_{B \subset A} \bar{B}$。由于 $x \sim x'$ 蕴含 $\text{alph}(x) = \text{alph}(x')$，可见每个 $\bar{B}$ 都是若干模 $\sim$ 的等价类的并，而 $M = \displaystyle\bigsqcup_{B \subset A} \pi(\bar{B})$。 由 **引理 2.4.6** 可见，当 $B \neq \varnothing$，存在双射： $$ \begin{aligned} \pi(\bar{B}) &\to \bigsqcup_{a, b \in B} \pi(\overline{B \backslash \{a\}}) \times \{a\} \times \{b\} \times \pi(\overline{B \backslash \{b\}}) \\ \bar{x} &\mapsto (\bar{p}, a, b, \bar{q}), \quad x \hat{=} (p, a, b, q) \end{aligned} $$ 当 $k = |B| \in \mathbb{N}$，令 $c_k = |\pi(\bar{B})|$，则有： $$ \begin{cases} c_0 = 1 \\ c_k = k^2 c_{k - 1}^2, &\quad k \in \mathbb{N}_+ \end{cases} $$ 解递推得到 $c_k = \displaystyle\prod_{i = 1}^k (k - i + 1)^{2^i}$，故有： $$ |M| = \sum_{k = 0}^n \binom{n}{k} c_k = \sum_{k = 0}^n \binom{n}{k} \prod_{i = 1}^k (k - i + 1)^{2^i} $$ ### References 1. M. Lothaire, _Combinatorics on Words_, Cambridge Mathematical Library, Cambridge University Press, 1997 reprint of the 1983 edition, Chapter 2.