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

$ C^{-1}d_X(x_1, x_2) \leq d_Y \big( f(x_1), f(x_2)\big ) \leq C d_X(x_1, x_2), \forall x_1, x_2\in X. $

我们称$ 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 $满足

$ \begin{eqnarray*} K = \bigcup\limits_{j = 1}^m\varphi_j(K), \end{eqnarray*} $

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

$ \varphi_i(U)\cap\varphi_j(U) = \emptyset, \forall i\neq j, $

我们称吸引子$ 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^{*} $, 记

$ \varphi_{x_1\cdots x_i} = \varphi_{x_1}\circ\cdots\circ\varphi_{x_i}. $

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

$ \{\pi({\bf x})\} = \bigcap\limits_{i\geq1}\varphi_{x_1\cdots x_i}(K), \forall {\bf x} = (x_i)_{i = 1}^{\infty}\in\Sigma^{\infty}, $

称$ \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 $, 都有

$ \begin{eqnarray*} |\varphi_j{(x)}| = r|x|, \forall x\in {{\Bbb R}} ^d, \end{eqnarray*} $

其中$ |\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}) $的分离数为

(2.1) $ \begin{equation} \Lambda_{K}({\bf x}, {\bf y}) = \max\{k;\varphi_{x_1\dots x_k}(K)\cap \varphi_{y_1\dots y_k}(K)\neq\emptyset\}. \end{equation} $

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

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

(2.2) $ \begin{equation} \rho_K({\bf x}, {\bf y}) = r^{\Lambda_{K}({\bf x}, {\bf y})}. \end{equation} $

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

(2.3) $ \begin{equation} \varphi_{I}(K)\cap \varphi_J(K)\neq\emptyset \ \rm{ 或 \ dist} \big(\varphi_I(K), \varphi_J(K)\big)\geq c r^{k}, \end{equation} $

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

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

$ \pi: (\Omega, \rho_K)\to (K, |\cdot|) $

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

$ \begin{eqnarray*} C^{-1}_1\rho_K({\bf x, y})\leq |\pi({\bf x})-\pi({\bf y})|\leq C_1\rho_K({\bf x, y}), \forall {\bf x, \bf y}\in\Omega. \end{eqnarray*} $

为了计算分离数, 我们引入邻居自动机. 设$ \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 $的邻居自动机. 它的状态集是

$ \begin{eqnarray*} {\cal N}^{\ast} = {\cal N}\cup\{Id\}\cup\{{ Exit}\}, \end{eqnarray*} $

其中$ 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} $如下

$ \delta(h, (i, j)) = \left\{ \begin{array}{cl} h', &x+h'\in{\cal N}\cup\{Id\};\\ Exit, \ &\rm{其它}. \end{array} \right. $

即: 如果$ 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 $ -自动机里的迹, 记为

$ (Id)\to h_1 \to h_2\to \cdots \to h_n \to Exit, $

其中, $ 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} $, 那么

$ \varphi_{y_1\cdots y_n}^{-1}\circ\varphi_{x_1\cdots x_n} = x-h_n\in{\cal N}\ {\rm {且}} \ \Lambda_{K}({\bf x, \bf y}) = \Lambda_{K}({\bf y, \bf x}). $

E -自动机和F -自动机

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

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

$ \begin{eqnarray*} \Omega = \{1, 2, 3\}^{\infty}\setminus\{\omega31^{\infty};\omega\in\{1, 2, 3\}^{*}\}, \end{eqnarray*} $

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

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

$ \begin{eqnarray*} {\cal N}_E = \big\{e_1, -e_1\big\}, \quad {\cal N}_E^{\ast} = {\cal N}_E\cup\big\{Id\big\}\cup\big\{Exit\big\}, \end{eqnarray*} $

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

$ {\cal N}_F^{\ast} = \big\{Id\big\}\cup\big\{Exit\big\}. $

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 $ -有效词的全体, 即

$ \begin{eqnarray*} {\cal A}_E = \big\{31^k;k\geq1\big\}\cup\big\{23^k21;k\geq 0\big\}\cup\big\{21, 1, 2, 3\big\}. \end{eqnarray*} $

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

(3.1) $ \begin{equation} {\bf x} = \prod\limits_{j = 1}^\infty X_j: = X_1X_2\cdots, \end{equation} $

其中$ 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 $ -有效词的全体, 即

$ \begin{eqnarray*} {\cal A}_F = \big\{23^k1;k\geq0\big\}\cup\big\{23^k11;k\geq 0\big\}\cup\big\{31, 1, 2, 3\big\}. \end{eqnarray*} $

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

$ \begin{eqnarray*} g_0:\left \{ \begin{array}{rl} 31^{k} &\mapsto 23^{k-1}1, k\geq 1;\\ 23^{k}21&\mapsto 23^{k}11, k\geq 0;\\ 21&\mapsto 31; \\ a&\mapsto a, \rm{若}\ a\in\{1, 2, 3\}. \end{array} \right . \end{eqnarray*} $

那么$ {\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} $, 如下

$ \begin{eqnarray*} g({\bf x}) = \prod\limits_{j = 1}^\infty g_0(X_j), \end{eqnarray*} $

其中$ (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实现, 它的状态集为

$ {\cal M} = \{I, II, II', III, III'\}, $

其中状态$ 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 $如下:

(3.2) $ \begin{equation} f(x) = \pi_{F}\circ g\circ\pi_E^{-1}(x). \end{equation} $

由引理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} $. 那么

(4.1) $ \begin{equation} |\Lambda_E({\bf x, \bf y})-\Lambda_F({\bf u, \bf v})|\leq 2. \end{equation} $

在这一节中, 不失一般性, 我们总记$ 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 $是强分离的, 所以

(4.2) $ \begin{equation} \Lambda_F(\bf u, \bf v) = |\bf u\wedge \bf v|. \end{equation} $

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

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

(4.3) $ \begin{equation} \Lambda_E({\bf x, \bf y})\leq|{\bf x}\wedge {\bf y}|+1. \end{equation} $

证  由引理的条件可知, $ 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 $ -自动机中的迹为

$ (Id)\to (Id)^{k}\to Exit(y_{k+1} = 1)\ { \rm{或}}\ (Id)\to (Id)^{k}\to e_1 \to Exit(y_{k+1} = 3). $

这是因为, 当$ 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 $. 故

$ \Lambda_E({\bf x, y})\leq k+1. $

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

$ \begin{eqnarray*} (Id)\to (Id)^{k}\to Exit(y_{k+1} = 1)\ {\rm {或}}\ (Id)\to (Id)^{k}\to (-e_1) \to Exit(y_{k+1} = 2). \end{eqnarray*} $

这是因为, 当$ 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 $. 故

$ \Lambda_E({\bf x, y})\leq k+1. $

证毕.

显然, 为了证明定理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\} $. 所以

$ \Lambda_F({\bf u, \bf v) = |\bf u\wedge \bf v}| = 0. $

引理得证.

引理 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 $. 从而

$ \Lambda_F({\bf u, \bf v) = |\bf u\wedge \bf v}| = 0. $

故(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.4) $ \begin{equation} |{\bf x}\wedge {\bf y}| = \min\{k, \ell\}+1, \quad |{\bf u}\wedge {\bf v}| = \min\{k, \ell\}. \end{equation} $

因此, 由引理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.5) $ \begin{equation} |{\bf x}\wedge {\bf y}| = \min\{k, \ell\}+1, \quad |{\bf u}\wedge {\bf v}| = \min\{k, \ell\}+1. \end{equation} $

因此, 由引理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\} $. 此时

$ {\bf V} = g({\bf y}) = g_0(2)(g_0(3))^{\ell-1}\cdots = 23^{\ell-1}\cdots. $

如果$ 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 $, 我们有

$ |{\bf u}\wedge {\bf v}| = \min\{k, \ell-1\}+1. $

因此, 由引理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 $, 即

$ \left(\begin{array}{cc}{\bf x}\\ {\bf y}\end{array}\right) = \left(\begin{array}{cc}{23^k21\cdots}\\ {23^{\ell}22\cdots}\end{array}\right) \rm{或} \left(\begin{array}{cc}{23^k21\cdots}\\ {23^{\ell}23\cdots}\end{array}\right). $

所以

$ |{\bf x}\wedge {\bf y}| = \left \{ \begin{array}{ll} \min\{k, \ell\}+1, & k\neq\ell, \\ \min\{k, \ell\}+2, & k = \ell. \end{array} \right . $

另一方面, 由$ 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 $ - 有效词), 所以

$ \left(\begin{array}{cc}{\bf u}\\ {\bf v}\end{array}\right) = \left(\begin{array}{cc}{g(\bf x)}\\ {g(\bf y)}\end{array}\right) = \left(\begin{array}{cc}{23^k11\cdots}\\ {23^{\ell}2\cdots}\end{array}\right). $

从而

$ |{\bf u}\wedge {\bf v}| = \min\{k, \ell\}+1. $

因此由引理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 $ -自动机中的迹一定为

$ (Id)\to (e_1)^{n}\to Exit, $

所以

$ \left(\begin{array}{c} x_1\cdots x_n\\ y_1\cdots y_n \end{array}\right) = \left(\begin{array}{c} 23^{n-1}\\ 31^{n-1}\end{array}\right) \; \rm{且}\; \left(\begin{array}{c} x_{n+1}\\ y_{n+1} \end{array}\right) \neq\left(\begin{array}{c} {3}\\ {1} \end{array}\right). $

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

$ \left(\begin{array}{c} u_1\cdots u_{n-1}\\ v_1\cdots v_{n-1} \end{array}\right) = \left(\begin{array}{c} 23^{n-2}\\ 23^{n-2} \end{array}\right), $

所以

$ \Lambda_F({\bf u, \bf v}) = |{\bf u\wedge \bf v}|\geq n-1 = \Lambda_E({\bf x, \bf y})-1. $

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

(4.6) $ \begin{equation} \Lambda_F({\bf u, \bf v})\geq \Lambda_E({\bf x, \bf y})-1. \end{equation} $

下面, 我们需要证明$ \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}) $). 此时

$ V_1 = 23^{k-1}1 <italic>\; 且\;</italic> v_{k+2}\neq1. $

(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 $, 我们有

(4.7) $ \begin{equation} |{\bf u}\wedge {\bf v}| = \min\{k, \ell+1\}>n+2. \end{equation} $

此时, 由$ 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})\geq\min\{\ell-1, k\}+1> n+1. $

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

综上, 我们有

$ \Lambda_E({\bf x, \bf y})-1\leq\Lambda_F({\bf u, \bf v})\leq \Lambda_E({\bf x, \bf y})+1. $

因此, (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映射.