称两个度量空间$(X, d_X)$和$(Y, d_Y)$是Lipschitz等价的, 记为$X\simeq Y$, 如果存在双射$f:X\to Y$和正常数$C>0$, 使得

我们称$f$是{双Lipschitz映射}, $C$为{Lipschitz常数}.

分形集的Lipschitz等价问题是几何测度论和分形几何的重要课题. 该问题起始于Copper和Pignataro^[1], Falconer和Marsh^[2-3], David和Semmes^[4]的一系列工作. 我们可以认为两个Lipschitz等价的分形集有相同的几何结构, 因为在双Lipschitz映射下, 一些重要的集合性质保持不变, 比如: 分形维数、测度性质、度量性质, 等等. 将分形集按照双Lipschitz映射分类正如将拓扑空间按同胚映射分类一样重要.

我们称${{\Bbb R}} ^d$上的一族压缩映射$\{\varphi_j\}_{j = 1}^m$是一个{迭代函数系}(IFS). 此时存在唯一的非空紧集$K$满足

我们称$K$是这个迭代函数系$\{\varphi_j\}_{j = 1}^m$的吸引子. 如果每个压缩映射$\varphi_j$都是相似映射, 我们称吸引子$K$是自相似集\textsuperscript{^[5]}. 如果存在非空开集$U$, 使得

我们称吸引子$K$满足{开集条件}(OSC). 一个众所周知的结论是, 如果自相似集$K$满足OSC, 那么$\sum\limits_{j = 1}^{m}\rho_j^{s} = 1$, 其中$\rho_j$是$\varphi_j$的压缩比, $s$是$K$的Hausdorff维数. 如果$\{\varphi_j(K)\}_{j = 1}^{m}$中的元素是互不相交的, 我们称$K$满足{强分离条件}(SSC).

Lipschitz等价问题的研究主要有两种类型. 第一类由Falconer和Marsh^[2]提出: 假设两个自相似集满足SSC, 那么它们的压缩比满足什么条件时, 它们是Lipschitz等价的, 这类问题主要的研究方法是构造Lipschitz不变量(参见文献[6-9]); 第二类由David和Semmes^[4]提出: 假设两个自相似集有相同的压缩比, 那么它们分支的几何结构是如何影响Lipschitz等价性的, 这类问题主要的研究方法是直接构造它们之间的双Lipschitz映射. 由于这类问题的研究非常困难, 目前只有较少的结果, 参见文献[10-18], 而这类问题的第一个实质性进展是饶辉, 阮火军和奚李峰^[10]取得的, 即{1, 3, 5}-{1, 4, 5} 问题.

定理 1.1  设$\varphi_i(x) = x/5+(i-1)/5, (1\leq i\leq 5)$. 设自相似集$E$和$F$分别是IFS$\{\varphi_1, \varphi_4, \varphi_5\}$和$\{\varphi_1, \varphi_3, \varphi_5\}$的吸引子, 则$E\simeq F$.

请注意, 这里$F$是满足SSC条件的自相似集, 而$E$有两个分支粘连(见图 1). David和Semme^[4]猜测它们不是Lipschitz等价的. 但饶辉, 阮火军和奚李峰^[10]通过研究吸引子的图递归结构证明了$F\simeq E$.

饶辉和朱云颉在研究非全不连通的自相似集的Lipschitz等价问题时, 引入邻居自动机的概念, 从而解决了一类非全不连通的自相似集的Lipschitz等价问题^{[15, 17-18]}. 本文的目的, 是给出定理1.1的一个新证明.

本文的结构如下: 第2节, 我们介绍了符号空间, 分离数, 急速分离条件和邻居自动机等概念, 它们在证明映射是Lipschitz等价的过程中起到了重要的作用; 第3节, 我们引入了词分解等概念, 利用词分解来构造符号空间上的双射$g$; 第4节, 证明由$g$构成的映射$f$是双Lipschitz映射.

在本节中, 我们将引入分离数和邻居自动机等概念.

设$\Sigma = \{1, \ldots, m\}$是一个字母集, 设$\Sigma^{\infty}$和$\Sigma^{k}$分别是$\Sigma$上的无穷词和长度为$k$的有限词的全体. 设$\Sigma^{*} = \bigcup\limits_{k\geq0}\Sigma^{k}$是所有有限词的全体. 对于$\sigma = \sigma_1\cdots\sigma_k\in\Sigma^{*}$, 我们用$|\sigma|$来表示词$\sigma$的长度. 如果$\rho = \rho_1\cdots\rho_{\ell}\in\Sigma^{*}$, 记$\sigma\rho = \sigma_1\cdots\sigma_k\rho_1\cdots\rho_{\ell}$, ${\sigma\wedge\rho}$是词$\sigma$和$\rho$最大的共同前缀. 为了方便, 我们用$a^{\ell}$来表示由$\ell$个$a$组成的词. 对于任意词$\omega\in\Sigma^{*}$, 记$\omega|_j = \omega_1\omega_2\dots \omega_j$为长度为$j$的$\omega$的前缀, 这里$\omega|_0 = a^0$表示空词.

设$\{\varphi_j\}_{j = 1}^{m}$是吸引子为$K$的一个迭代函数系(IFS), 对于任意有限词$x_1\cdots x_i\in\Sigma^{*}$, 记

定义映射$\pi:\Sigma^{\infty}\to K$, 如下

称$\pi$为从符号空间到$K$的投影(如果有多个自相似集, 我们用$\pi_K$来表示$\pi$). 如果$\pi({\bf x}) = x$, 我们称词$\bf x$是点$x$的一个编码. 由于点$x\in K$可能有多个编码, 从而可以在$\Sigma^{\infty}$上定义等价关系如下：${\bf x}\sim{\bf x'}$当且仅当$\pi({\bf x}) = \pi({\bf x'})$. 若$\Omega\subset \Sigma^{\infty}\setminus\sim$是一个商空间(仅包含每个等价类中一个元素), 那么$\pi_K:\Omega\to K$是一个双射.

下面进一步假设$\{\varphi_j\}_{j = 1}^{m}$中的映射均为压缩比为$r$的相似映射, 即$\forall 1\leq j\leq m$, 都有

其中$|\cdot|$表示欧氏距离.

定义 2.1  设${\bf x} = (x_i)_{i = 1}^{\infty}, {\bf y} = (y_i)_{i = 1}^{\infty}\in \Sigma^{\infty}$. 如果$\pi({\bf x})\neq \pi({\bf y})$, 我们定义$({\bf x}, {\bf y})$的分离数为

如果$\pi({\bf x}) = \pi({\bf y})$, 我们定义$({\bf x}, {\bf y})$的分离数为$+\infty$.

通过分离数, 我们可以在$\Omega\in\Sigma^{\infty}$上诱导了一个拟度量函数$\rho$:

定义 2.2  设$\{\varphi_j\}_{j = 1}^{m}$是吸引子为$K$的一个迭代函数系(IFS), $\varphi_j$压缩比均为$r$. 我们称$K$是{急速分离的}, 如果存在常数$c$, 使得对于任意一对有限词的$I, J\in {\Sigma}^k(k\geq1)$, 都有

其中dist$(A, B)$表示集合$A, B$之间的欧氏距离.

引理 2.1  设自相似集$K$有一致压缩比. 如果$K$是急速分离的, 那么投影映射

是双Lipschitz映射. 即, 存在一个常数$C_1>0$, 使得

为了计算分离数, 我们引入邻居自动机. 设$\Phi = \{\varphi_i\}_{i = 1}^{m}$是$K$的一个迭代函数系且$\Phi$压缩比一致. 设$I = i_1\dots i_n, J = j_1\dots j_n\in \Sigma^{*}$且$i_1\neq j_1$. 我们称$\varphi_{I}^{-1}\circ \varphi_J$是一个邻居映射\textsuperscript{^[19]}, 如果$\varphi_{I}(K)\cap \varphi_J(K)\neq\emptyset$. 我们用${\cal N} = {\cal N}_{\Phi}$或者${\cal N}_K$来表示$\Phi$的邻居映射的全体. 注意到一个邻居映射$\tau$一定形如$\tau(x) = x+h, h\in {{\Bbb R}} ^d$. 为了方便, 我们用$h$表示邻居映射$\tau(x) = x+h$.

现在, 我们构造$\Phi$的邻居自动机. 它的状态集是

其中$Id$表示恒等映射. 自动机的初始状态是$Id$, 终止状态是$Exit$.

其次, 设$\Sigma^2$为指令集, 设$h\in {\cal N}\cup\{Id\}$, 对于任意的$(i, j)\in\Sigma^2$, 记$x+h': = \varphi_i^{-1}\circ(x+h)\circ\varphi_j(x)$, 我们定义转移函数$\delta:{\cal N}^{\ast}\times \Sigma^2\to {\cal N}^{\ast}$如下

即: 如果$x+h'\in {\cal N}\cup\{Id\}$, 那么, 我们定义了在指令$(i, j)$下，我们从状态'$h$'转移到'$h'$'; 否则, 我们定义了在指令$(i, j)$下，我们从状态'$h$'转移到'Exit', 并记为$(h, (i, j), h')$或者$(h, (i, j), Exit)$. 我们称上述自动机为$K$ -自动机.

设${\bf x} = (x_i)_{i = 1}^{\infty}, {\bf y} = (y_i)_{i = 1}^{\infty}\in \Sigma^{\infty}$, 从初始状态$Id$开始, 我们依次输入指令$({x_i}, {y_i})$$(i\geq1)$, 记第$j$步到达状态$h_j$, 那么, 在第$\Lambda_K({\bf x, \bf y})+1$步到达$Exit$状态. 我们称$h_0 = Id, h_1, \cdots, h_n$, $Exit$为$(\bf x, y)$在$K$ -自动机里的迹, 记为

其中, $n = \Lambda_K({\bf x, \bf y})$且$x+h_i = \varphi_{x_1\cdots x_i}^{-1}\circ\varphi_{y_1\cdots y_i}(x)(1\leq i\leq n)$.

由上述定义, 下面的引理显然成立.

引理 2.2  设${\bf x, \bf y}\in\Sigma^{\infty}$. 如果$\varphi_{x_1\cdots x_n}^{-1}\circ\varphi_{y_1\cdots y_n}(x) = x+h_n\in {\cal N}$, 那么

E -自动机和F -自动机

定理1.1中的自相似集$E, F$均为5分均匀Cantor集, 如图 1所示.

对于集合$E$, $\pi_{E}(23^{\infty}) = \pi_{E}(31^{\infty})$. 显然, 如果自相似集$E$中的点$x$的编码是以$23^{\infty}$或$31^{\infty}$结尾的, 那么, 该点有两个编码, 否则, 有唯一编码. 令

那么, $\pi_E:(\Omega, \rho_E)\to (E, |\cdot|)$是双Lipschitz的, 其中$\rho_E$的定义参考(2)式.

邻居映射集和$E$ -自动机的状态集如下:

其中$e_1 = x+1, -e_1 = x-1$. $E$ -自动机如图 2(a)所示. 对于5分Cantor集$F$, 因为它是强分离的, 所以, 它的邻映射集合是空集, 从而, $F$ -自动机的状态集为

F -自动机如图 2(b)所示.

在本节中, 我们将通过翻译机构造一个符号空间之间的双射.

现在, 我们介绍$\Omega$中有效词分解, 这个概念是Lipschitz映射构造的关键.

定义 3.1  ($E$ -特殊词) 设${\bf x} = (x_i)_{i = 1}^{\infty}\in\Omega$. 我们称$\bf x$的一个因子$x_j\cdots x_{j+k}(k\geq1)$是一个$E$ -特殊词, 如果下列条件有一个成立：

$\rm(i)$$x_j\cdots x_{j+k} = 31^k$且$x_{j+k+1} \neq 1$;

$\rm(ii)$$x_j\cdots x_{j+k} = 23^{k-2}21(k\geq2)$;

$\rm(iii)$$x_j\cdots x_{j+k} = 21(k = 1)$且$x_{i}\cdots x_{j-1}\neq 23^{j-i-1}$.

由定义3.1容易证明, 一个词的任何字母是不可能同时属于两个不同的特殊词, 这点是词的分解唯一性的保证.

$\bf x$中的一个因子$x_j$被称为$E$ -简单词, 如果它不落在任何$\bf x$的$E$ -特殊词上. $E$ -简单段和$E$ -特殊词统称为$E$ -有效词. 用${\cal A}_E$来表示$\Omega$中$E$ -有效词的全体, 即

定义 3.2  设${\bf x} = (x_i)_{i = 1}^{\infty} \in \Omega$. $\bf x$能被唯一的表示为

其中$X_j$是$\bf x$的$E$ -有效词. 称(4)式右边是$\bf x$的{$E$ -有效词分解}.

例 3.1  词$231^323^42132112^{\infty}$的$E$ -有效词分解是$(2)(31^3)(23^421)(3)(21)(1)(2)^{\infty}$.

定义 3.3  ($F$ -特殊词) 设${\bf u} = (u_i)_{i = 1}^{\infty}\in\{1, 2, 3\}^{\infty}$. 我们称$\bf u$的一个因子$u_j\cdots u_{j+k}(k\geq1)$是一个$F$ - 特殊词, 如果下列条件有一个成立:

${\rm (i)}$$u_j\cdots u_{j+k} = 23^{k-1}1$且$u_{j+k+1} \neq 1$;

${\rm (ii)}$$u_j\cdots u_{j+k} = 23^{k-2}11$;

${\rm (iii)}$$u_j\cdots u_{j+k} = 31$且$u_{i}\cdots u_{j-1}\neq 23^{j-i-1}$.

$\bf u$中的一个因子$u_j$被称为{$F$ -简单词}, 如果它不落在任何$\bf u$的$F$ -特殊词上. 类似地, 对于任意的${\bf u}\in\{1, 2, 3\}^{\infty}$, 它都有一个$F$ -有效词分解, 且是唯一的. 用${\cal A}_F$来表示$F$ -有效词的全体, 即

接下来, 我们定义映射$g:\Omega\to \{1, 2, 3\}^{\infty}$. 首先, 我们定义映射$g_0:{\cal A}_E\to\{1, 2, 3\}^{\ast}$, 如下

那么${\cal A}_F = g_0\big({\cal A}_E\big)$. 显然, $g_0:{\cal A}_E\to{\cal A}_F$是一个双射.

定义映射$g: \Omega\to\{1, 2, 3\}^{\infty}$, 如下

其中$(X_j)_{j = 1}^\infty$是$\bf x$的$E$ -有效词分解.

例3.1中的词在映射$g$下的像为$g\big((2)(31^3)(23^421)(3)(21)(1)(2)^{\infty}\big) = 223^2123^41133112^{\infty}.$

引理 3.1  如果$(X_j)_{j = 1}^{\infty}$是${\bf x}$的$E$ -有效词分解, 那么$g({\bf x})$的$F$ -有效词分解是$\prod\limits_{j = 1}^\infty g_0(X_j)$.

证  令${\bf u} = g({\bf x})$, 我们仅需证$g_0(X_j)(j\geq1)$是${\bf u}$的$F$ -有效词.

首先, 证明$\bf x$的$E$ -特殊词在$g$下的像$g_0(X_j)$是一个$F$ -特殊词. 如果$X_j = 23^k21(k\geq0)$, 那么, $g_0(X_j) = 23^k11$是一个$F$ -特殊词; 如果$X_j = 21$, 那么, $g_0(X_j) = 31$也是一个$F$ -特殊词; 如果$X_j = 31^k$, 用$x_m$来表示$X_j$后面的首字母, 那么$x_m\neq1$. 所以, $g_0(X_j) = 23^{k-1}1$, 并且$g_0(X_{j+1})$的首字母是$g(x_m\cdots)$的首字母. 由$g_0$的定义可知, $g_0(X_{j+1})$的首字母不等于1, 从而, $g_0(X_j) = 23^{k-1}1$也是一个$F$ -特殊词.

其次, 证明${\bf u}$中的$F$ -特殊词只能是${\bf x}$中某个的$E$ -特殊词的像. 用反证法, 假设$X_j\in\{1, 2, 3\}$, 且$g_0(X_j)$是$F$ -特殊词$u_p\cdots u_{p+k}$的一个因子. 由上段可知, 每一个$u_i(p\leq i\leq p+k)$都是$E$ -中简单词在$g_0$下的像, 所以, $x_p\cdots x_{p+k} = u_p\cdots u_{p+k}$是$E$中简单词组成的因子, 并且, 它包含了31或者21, 这是不可能的. 从而, ${\bf u}$中的$F$ -特殊词只能是${\bf x}$中某个的$E$ -特殊词的像.

定理 3.1  $g(\Omega) = \{1, 2, 3\}^{\infty}$并且$g:\Omega\to \{1, 2, 3\}^{\infty}$是一个双射.

证  首先, 由引理3.1可知, $g:\Omega\to \{1, 2, 3\}^{\infty}$是一个单射. 其次, 类似于引理3.1证明, 我们可以证明, 如果$(U_j)_{j = 1}^{\infty}$是$\bf u$的$F$ -有效词分解, 那么, $\big(g_0^{-1}(U_j)\big)_{j = 1}^{\infty}$是${\bf x} = \prod\limits_{j = 1}^{\infty}g_0^{-1}(U_j)$的$E$ -有效词分解. 因此, ${\bf u} = g({\bf x})$, 从而, 它是一个满射.

映射$g$可以由图 3实现, 它的状态集为

其中状态$I$是初始状态. 翻译机的边由$x/\omega$来表示, 其中, $x$是输入的字母, $\omega$是输出的词. 对于任意一个状态, 随着分别输入1, 2, 3, 使得每个状态都含有三条出去的边. 输入一个序列$(x_i)_{i = 1}^{\infty}$, 那么, 在翻译机中决定了唯一的一条道路, 记为$(x_i/\omega_i)_{i = 1}^{\infty}$且输出的序列为$\omega_1\omega_2\cdots \omega_i\cdots$.

引理 3.2  设${\bf x} = (x_i)_{i = 1}^{\infty}\in \Omega$, $g({\bf x}) = {\bf u} = (u_i)_{i = 1}^{\infty}$, 那么, $u_1\cdots u_n$能由$x_1\cdots x_{n+1}$所确定.

证  根据图 3, 观察到, 除了离开状态$I$($|x| = 1, |\omega| = 0$)进入其它状态的边, 或者从其它状态进入状态$I$的边($|x| = 1, |\omega| = 2$)之外, 其它边$x/\omega$都满足$|x| = |\omega| = 1$. 引理得证.

定义映射$f:E\to F$如下:

由引理2.1, 映射$\pi_{F}:\{1, 2, 3\}^{\infty}\to F$和$\pi_E^{-1}:E\to \Omega$均是双Lipschitz的. 在第四节, 我们将证明下述定理.

定理 3.2  映射$f:E\to F$是双Lipschiz的.

在这一节中, 我们将证明定理4.1, 并且根据它我们可以直接得到定理3.2.

定理 4.1  设${\bf x, y}\in \Omega$, 并记$g({\bf x}) = {\bf u}, g({\bf y}) = {\bf v}$. 那么

在这一节中, 不失一般性, 我们总记$g({\bf x}) = {\bf u}, g({\bf y}) = {\bf v}$, 并设$(X_j)_{j = 1}^{\infty}$, $(Y_j)_{j = 1}^{\infty}$分别是${\bf x, \bf y}$的$E$ -有效词分解, $(U_j)_{j = 1}^{\infty}$, $(V_j)_{j = 1}^{\infty}$分别是${\bf u, \bf v}$的$F$ -有效词分解.

我们将经常用到下述简单事实: 对于任意的${\bf x} = (x_i)_{i = 1}^{\infty}\in \Omega$, 如果$x_1 = 2$, 那么$X_1 = 2, 21$或$23^k21(k\geq0)$; 如果$x_1 = 3$, 那么$X_1 = 3$或$31^k(k\geq1)$.

由分离数的定义可知, $\Lambda_K({\bf x, \bf y})\geq |{\bf x}\wedge {\bf y}|$. 特别地, 因为Cantor集$F$是强分离的, 所以

下面引理给出了$\Lambda_E({\bf x, \bf y})$的一个上界估计.

引理 4.1  设${\bf x, \bf y}\in\Omega$, 若$x_1 = y_1$且$X_1\neq Y_1$, 那么

证  由引理的条件可知, $X_1, Y_1$中至少有一个是$E$ -特殊词, 不失一般性, 假设$X_1$是$E$ -特殊词. 设$|{\bf x}\wedge {\bf y}| = k\geq 1$, 那么$x_1\cdots x_k = y_1\cdots y_k$且$x_{k+1}\neq y_{k+1}$.

若$|X_1|\leq k$, 那么, $X_1$是$Y_1$的前缀, 则$X_1 = 31^{k-1}$, $Y_1 = 31^{\ell}(\ell\geq k)$. 从而, $y_{k+1} = 1\neq x_{k+1}$, 所以, 边$\big(Id, (x_{k+1}, y_{k+1})\big)$指向终止状态Exit, 故$\Lambda_E(\bf x, \bf y) = |\bf x\wedge \bf y|.$

若$|X_1|>k$, 则$X_1 = 21, 31^{\ell}(\ell\geq k)$或$23^{\ell}21(\ell+2\geq k)$. 当$X_1 = 21$或$31^{\ell}(\ell\geq k)$, 此时, $x_{k+1} = 1\neq y_{k+1}$, 所以, 边$\big(Id, (x_{k+1}, y_{k+1})\big)$指向状态$Exit$, 故$\Lambda_E(\bf x, \bf y) = |\bf x\wedge \bf y|.$

假设$X_1 = 23^{\ell}21(\ell+2\geq k)$, 此时, $x_{k+1} = 1$或$x_{k+1}x_{k+2}\in \{21, 32, 33\}$. 若$x_{k+1} = 1$, 引理显然成立;

(i) 当$x_{k+1}x_{k+2} = 21$, 那么$y_{k+1}\in\{1, 3\}$, 则$(\bf x, \bf y)$在$E$ -自动机中的迹为

这是因为, 当$y_{k+1} = 1$, 则$(x_{k+1}, y_{k+1}) = (2, 1)$, 那么$(\bf x, y)$在第(k+1)步由状态$Id$转向终止状态$Exit$; 当$y_{k+1} = 3$, 则$(x_{k+1}, y_{k+1}) = (2, 3)$且$(x_{k+1}, y_{k+1})\ne(3, 1)$, 那么$(\bf x, y)$在第(k+1)步由状态$Id$转向状态$e_1$, 在第(k+2) 步由状态$e_1$转向终止状态$Exit$. 故

(ii) 当$x_{k+1}x_{k+2}\in\{32, 33\}$, 那么$y_{k+1}\in\{1, 2\}$, 则$(\bf x, \bf y)$在$E$ -自动机中的迹为

这是因为, 当$y_{k+1} = 1$, 则$(x_{k+1}, y_{k+1}) = (3, 1)$, 那么$(\bf x, y)$在第(k+1)步由状态$Id$转向终止状态$Exit$; 当$y_{k+1} = 2$, 则$(x_{k+1}, y_{k+1}) = (3, 2)$且$(x_{k+1}, y_{k+1})\ne(1, 3)$, 那么$(\bf x, y)$在第(k+1)步由状态$Id$转向状态$-e_1$, 在第(k+2) 步由状态$e_1$转向终止状态$Exit$. 故

证毕.

显然, 为了证明定理4.1, 我们仅须证明该定理在$X_1\neq Y_1$时成立即可. 设$h$是$(\bf x, \bf y)$的迹经过的第二个状态, 根据状态$h = Exit, Id$或$\pm e_1$, 我们将证明下面三个引理.

引理 4.2  如果$h = Exit$且$X_1\neq Y_1$, 那么, (4.1)式成立.

证  $h = Exit$意味着$\Lambda_E({\bf x, \bf y}) = 0$, 所以, $x_1\neq y_1$且$x_1, y_1$有且必有一个等于1. 不妨设$x_1 = 1$, 那么$X_1 = 1$且$y_1 = 2$或3. 由函数$g_0$的定义, $u_1 = U_1 = g_0(X_1) = 1$且$v_1\in\{2, 3\}$. 所以

引理得证.

引理 4.3  如果$h = Id$且$X_1\neq Y_1$, 那么(4.1)式成立.

证  $h = Id$意味着$x_1 = y_1$, 由$X_1\neq Y_1$可知, $X_1$和$Y_1$中至少有一个是$E$ -特殊词. 不妨设$X_1$是$E$ -特殊词, 那么$X_1 = 21, 31^k(k\geq1)$或$23^k21(k\geq0)$.

Case 1. $X_1 = 21$.

此时, $y_1 = x_1 = 2$且$y_2\neq 1$. 所以$Y_1 = 2$或$23^{\ell}21(\ell\geq0)$. 从而, $\Lambda_E({\bf x, \bf y}) = 1$. 另一方面, 由$g_0$的定义, 我们有$U_1 = g_0(X_1) = 31$, $V_1 = g_0(Y_1) = 2$或$23^k11$. 从而

故(4.1)式成立.

Case 2. $X_1 = 31^k$.

此时, $y_1 = x_1 = 3$, 那么, $Y_1 = 3$或$31^{\ell}(\ell\neq k)$. 若$Y_1 = 3$, 那么$y_2\neq 1$(否则, $Y_1$不是简单段). 所以, $\Lambda_E({\bf x, \bf y}) = 1$. 另一方面, 由$g_0$的定义, 我们有$U_1 = g_0(X_1) = 23^{k-1}1$, $V_1 = g_0(Y_1) = 3$, 那么, $\Lambda_F({\bf u, \bf v) = |\bf u\wedge \bf v}| = 0.$从而, (4.1)式成立.

若$Y_1 = 31^{\ell}(\ell\geq1, \ell\neq k)$, 那么$U_1 = 23^{k-1}1$且$V_1 = 23^{\ell-1}1$, 所以

因此, 由引理4.1可知, (4.1)式成立.

Case 3. $X_1 = 23^k21(k\geq0)$.

此时, $U_1 = 23^k11$且$y_1 = 2$, 所以$Y_1 = 2, 21$或$23^{\ell}21(\ell\neq k)$. $Y_1 = 21$的情况在{Case 1}中已经证明. 若$Y_1 = 23^{\ell}21(\ell\neq k)$, 那么$U_1 = 23^k11$且$V_1 = 23^{\ell}11$, 所以

因此, 由引理4.1可知, (4.1)式成立. 下面我们考虑$Y_1 = 2$的情况.

若$Y_1 = 2$, 令$y_1\cdots y_{\ell+1} = 23^{\ell}$$(\ell\geq0)$且$y_{\ell+2}\neq3$, 即$y_{\ell+2}\in\{1, 2\}$. 此时

如果$y_{\ell+2} = 1$, 那么, $|{\bf x}\wedge {\bf y}| = \min\{k, \ell\}+1$且${\bf V} = g({ 23^{\ell}1\cdots}) = 23^{\ell-1}2\cdots$ (因为$g_0(31^p) = 23^{p-1}1, p\geq1$). 由$U_1 = 23^k11$, 我们有

因此, 由引理4.1可知, (4.1)式成立.

如果$y_{\ell+2} = 2$, 那么$y_{\ell+2}y_{\ell+3}\neq21$ (否则$Y_1 = 23^{\ell}21$是特殊词), 从而, $y_{\ell+2}y_{\ell+3} = 22, 23$, 即

所以

另一方面, 由$g$和$g_0$的定义, 一定有$v_1\cdots v_{\ell+1} = g_0(Y_1)\cdots g_0(Y_{\ell+1}) = 23^{\ell}2$且$v_{\ell+2} = 2$ (因为$Y_{\ell+2}$是首字母为2的$E$ - 有效词), 所以

从而

因此由引理4.1可知, (4.1)式成立. 引理得证.

引理 4.4  如果$h = \pm e_1$, 那么(4.1)式成立.

证  由对称性, 不妨设$h = e_1$. 记$n = \Lambda_E({\bf x}, {\bf y})$, 那么${(\bf x}, {\bf y})$在$E$ -自动机中的迹一定为

所以

如果$n\geq2$, 由$g$和$g_0$的定义, 一定有

所以

显然, 当$n = 1$时, 上式也成立. 故

下面, 我们需要证明$\Lambda_F({\bf u, \bf v})\leq\Lambda_E({\bf x, \bf y})+1 = n+1$. 反证法, 假设$\Lambda_F({\bf u, \bf v})>n+2$, 那么$|{\bf u\wedge\bf v}|>n+2$. 如果$Y_1 = 3$, 那么$v_1 = 3, v_2\neq 1$, 且$u_1 = 3$(因为$u_1 = v_1$). 由$g_0$的定义和$x_1 = 2$, 我们有$X_1 = 21$, 从而$u_1u_2 = 31$, 这与$|{\bf u\wedge\bf v}|>n+2\geq3$矛盾. 故$Y_1$是一个$E$ -特殊词. 设$Y_1 = 31^k(k\geq 1)$, $y_{k+2}\neq1$, 那么$k\geq n-1$ (因为$n = \Lambda_E({\bf x}, {\bf y})$). 此时

(i) 若$|{\bf u\wedge\bf v}|\geq |V_1| = k+1$, 那么$U_1 = 23^{k-1}11$. 此时, $X_1 = 23^{k-1}21$. 由$Y_1 = 31^k$可知, $\Lambda_E({\bf x, \bf y})\geq\min\{k-1, k\}+1 = k.$所以$n\geq k$. 另一方面, 由$U_1 = 23^{k-1}11$和$V_1 = 23^{k-1}1$, 我们有$\Lambda_F({\bf u, \bf v}) = |{\bf u\wedge \bf v}| = k+1\leq n+1.$这与假设$\Lambda_F({\bf u, \bf v})>n+2$相矛盾.

(ii) 若$|{\bf u\wedge\bf v}|< |V_1| = k+1$, 那么$\bf u$必有形如$23^{\ell}$的前缀. 令$u_1\dots u_{\ell+1} = 23^{\ell}$和$u_{\ell+2}\neq 3$, 结合$V_1 = 23^{k-1}1$, 我们有

此时, 由$g_0$定义可知和$x_1 = 2$, 我们有$x_1\dots x_{\ell} = 23^{\ell-1}$. 由$Y_1 = 31^{k}$和(4.7)式, 可得

这与假设$\Lambda_E({\bf x, \bf y}) = n$相矛盾.

综上, 我们有

因此, (4.1)式成立.

定理3.2的证明  由定理4.1可知, 映射$g:(\Omega, \rho_E)\to (\{1, 2, 3\}^{\infty}, \rho_F)$是双Lipschitz的, 其中$\rho_K({\bf x, y}) = 3^{-\Lambda_K({\bf x, y})}$. 因此, $f = \pi_F\circ g\circ \pi_E^{-1}$是双Lipschitz映射.