早前讀 The Mathematics of Logic 時其中一條題目（Exercise 1.16 (c)）與 Thue-Morse 數列有關（題目本身沒提這名字，我後來查到的）。題目如下：

Define an operation on finite 2-sequences σ such that $\sigma (0) = 01, \sigma (1) = 10$, and $\sigma (u_0 u_1 \ldots u_m) = \sigma (u_0) \sigma (u_1) \ldots \sigma (u_m)$, where this is concatenation of sequences. Let $\sigma^n (s) = \sigma (\sigma (\ldots (\sigma (s)) \ldots))$, i.e. $\sigma$ iterated $n$ times. Show that each of the finite sequences $\sigma^n(0)$ is $x^3$-free, and hence there is an infinite $x^3$-free 2-sequence.

題目要求證明任何一個 $\sigma^n(0)$ 都不存在連續重複三次的數字串。我最初嘗試證明的時候，因為懶得寫下來而不想分成不同情況去證明，但發現有點難度，就先把證明寫出來再研究。

後來看了 Thue-Morse 數列有不同定義，又參考了其他人的證明，我便嘗試證明這些定義等價以及簡化原來的證明。

（按：除題目外其餘三個定義是在《維基百科》的 Thue-Morse Sequence 頁面看到。最後證明不會出現形如 $aYaYa$ 的數列時，點算 $0$ 及 $1$ 數量的方法來自 Stanford University Mathematical Organization 這個PDF檔案第11頁​。圖1的SVG碼使用ChatGPT生成再作修改，因為我覺得《維基百科》的圖片太醜，然後改成圖2。）

Thue-Morse 數列的多種定義

為方便及統一寫法，以下先界定一些符號用法，再逐一介紹 Thue-Morse 數列的不同定義並證明等價。

符號及基本定義

本文中的數列只有0和1兩個數字，以小寫字母 $a, b, c$ 代表數字（0或1），以大寫字母 $X, Y, Z$ 代表有限數列（即數字串）。兩個數列連起來寫就代表其連接（concatenation），例如設 $X = 000, Y = 10$，那麼 $XY = 00010$。

另外定義 $\overline{a} = 1-a$，即$\overline{0} = 1$, $\overline{1} = 0$。而且對於任何$X$及$Y$，$\overline{XY} = \overline{X}\overline{Y}$。這個運算把數列中的0和1互換，例如 $\overline{01001} = 10110$。

定義1：改寫數列

函數 $\sigma(x)$ 的定義如下：$\sigma (0) = 01, \sigma (1) = 10$ 以及對於任何 $X$及$Y$，$\sigma(XY) = \sigma(X)\sigma(Y)$。透過對 $X$ 的長度作歸納論證，可得出 $\sigma(\overline{X}) = \overline{\sigma(X)}$。

定義數列 $S_n = \sigma^n(0)$（由$n=0$開始），這個數列的首五項分別是 $0, 01, 0110, 01101001, 0110100110010110$。

從這種使用Lindenmayer系統（透過規則不斷​改寫字串）的定義方式可畫出以下無限延伸的樹狀圖，第$n$層就是$S_n$：

注意 $S_{n+1} = S_n\overline{S_n}$ 的模式，這個觀察揭示了另一種定義方式（下一節會證明）。

定義2︰鏡像反射

定義 $T_0 = 0, T_{n+1}=T_n\overline{T_n}$，以下證明對於任何$n$，$T_n = S_n$。

定義2跟定義1等價

當 $n = 0$ 及 $n=1$ 時，$T_0 = 0 = S_0$ 及 $T_1 = 01 = S_1$。

假設 $T_{n-1} = S_{n-1}$ 及 $T_n = S_n$，那麼：

$$\begin{align} S_{n+1} &= \sigma(S_n) = \sigma(T_n) \\ &= \sigma(T_{n-1}\overline{T_{n-1}}) = \sigma(S_{n-1}\overline{S_{n-1}}) \\ &= \sigma(S_{n-1})\sigma(\overline{S_{n-1}}) = \sigma(S_{n-1})\overline{\sigma(S_{n-1})} \\ &= S_n\overline{S_n} = T_n\overline{T_n} \\ &= T_{n+1} \end{align}$$

（第三行需要用到定義 $\sigma(XY) = \sigma(X)\sigma(Y)$ 和上面提及的 $\sigma(\overline{X}) = \overline{\sigma(X)}$。）

透過這個定義，不難看出對於任何$m<n$，$T_m$是$T_n$的首$2^m$長的數列。我們亦可由此定義一個無限長的數列 $T = T_0\overline{T_0}\overline{T_1}\overline{T_2} \ldots$，並以 $t_n$ 表示這個數列的第$n$項。$T$的首$2^n$項即為$T_n$（及$S_n$）。

（如想嚴謹一點，可定義對任何$n$及$k<2^{n-1}$，$t_{2^{n-1}+k}$為$\overline{T_{n-1}}$的第$n$項，另外$t_0=0$。）

這個數列即為 Thue-Morse 數列。

接下來兩個定義則直接計算 $t_n$。

定義3：遞歸定義

從圖1（以及定義1的規則）我們可以看到 $t_n$ 跟其生成的下一層左邊數字相同，而下一層右邊的數字則是 $\overline{t_n}$。

由於 $t_n$ 前共有 $n$ 個數字，每個數字在下一層都改寫成兩個數字，即共有 $2n$ 個數字，所以 $t_n$ 下一層的左邊數字就是 $t_{2n}$，右邊數字則為 $t_{2n+1}$（由 $0$ 開始數起）。當然我們也不能忘掉 $t_0 = 0$。

所以 $t_n$ 可以用以下方式定義：

$$\begin{align} t_0 &= 0 \\ t_{2n} &= t_n \\ t_{2n+1} &= \overline{t_n} \end{align}$$

這個遞歸定義涵蓋了所有自然數。例如想知道 $t_{13}$ 的話，我們可以從定義推算：

$$\begin{align} t_{13} & = t_{2 \times 6 +1} = \overline{t_6} \\ &= \overline{t_{2 \times 3}} = \overline{t_3} \\ &= \overline{t_{2 \times 1+1}} = \overline{\overline{t_1}} = t_1 \\&= t_{2\times 0 +1} = \overline{t_0} = \overline{0} \\ &= 1 \end{align}$$

假如以上討論不能說服你定義3跟定義1等價，以下將會透過定義4去把上述定義串連起來。

定義4：二進制表示

我們亦可從圖1看到定義1跟二進制的關係。

在完整的二叉樹（binary tree）中，第 $n$ 層（從 $0$ 開始）的節點均對應一個 $n$ 位長的數列，由左至右第 $k$ 個節點（從 $0$ 開始）對應的數列，基本上就是 $k$ 的二進制表示（binary representation）再加上相應數量的 $0$ 在前方（使其成為 $n$ 位長）。可以參考下圖：

每個節點的數列同時對應由樹狀圖的根（最頂端的 $0$ 那一點）前往該節點的唯一路徑—— $0$ 代表左轉、$1$ 代表右轉。例如前往 $010$ 代表先左轉、右轉、再左轉。現在我們再看一次圖1：

圖1的樹狀結構跟圖2相同，分別僅在於每個節點的數字。在圖1中，當節點數字為 $0$ 時，​左轉的節點仍然為 $0$，​右轉的節點則為 $1$；而當節點數字為 $1$ 時，左​轉節點仍然為 $1$，右轉的節點則為 $0$。而在圖2中，左轉代表數列最右邊加一個 $0$，右轉代表數列最右邊右一個1。

對比兩個樹狀圖，我們可以看到​圖1中每一層第 $n$ 個節點（由左至右，由 $0$ 開始）的數字，代表 $n$ 的二進制表達中 $1$ 的數量是偶數（$0$）抑或奇數（$1$）。

設 $n$ 的二進制表示為 $a_0a_1 \ldots a_k$，如果 $a_0 + a_1 + \ldots + a_k$ 是偶數的話，定義 $r_n = 0$，否則定義 $r_n = 1$。另外定義 $R_k = r_0r_1 \ldots r_{2^k-1}$，即首 $2^k$ 個 $r_n$ 組成的數列。

以下證明用這個方式定義出來的數列，跟上述定義相同。

定義3跟定義4等價

不難看出 $r_n$ 符合定義3中 $t_n$ 的所有條件：

• $0$ 的二進制表示就是 $0$，所以 $r_0 = 0$；
• $2n$ 的二進制表示就是 $n$ 最右邊多加一個 $0$，當中 $1$ 的總數不變，所以 $r_{2n} = r_n$；
• $2n$ 跟 $2n+1$ 的二進制表示僅個位有別，前者是 $0$ 後者是 $1$，所以如果 $r_{2n} = 0$ 則 $r_{2n} = 1$，反之亦然，從而得出 $r_{2n+1} = \overline{r_{2n}} = \overline{r_n}$。

由此可見，定義4的 $r_n$ 跟定義3的 $t_n$ 相同。

定義4跟定義2等價

以下證明 $R_k = T_k$。

當 $k = 0$ 時，$R_0 = r_0 = 0 = T_0$。

假設 $R_n = T_n$，則 $T_{n+1} = T_n\overline{T_n} = R_n\overline{R_n}$，此處先暫停一下，我們需要一條引理去繼續證明。

對於任何 $0 \leq m < 2^n$，$m$ 的二進制表示最多只有 $n$ 個位，而 $2^n$ 的二進制表示為 $1\overbrace{0 \ldots 0}^n$，所以 $2^n+m$ 的二進制表示跟 $m$ 大致相同，分別僅為在第 $n+1$ 位（從個位數起）為 $1$ 及中間或需要補回一些 $0$。（例如設 $m = 5$ 及 $n = 3$，$5 = 101_2$，$2^3+5 = 13 = 1101_2$。）

我們從而得知 $r_{2^n+m} = \overline {r_m}$，所以 $r_{2n}r_{2n+1} \ldots r_{2^{n+1}-1} = \overline{r_0r_1 \ldots r_{2^n-1}} = \overline{R_n}$。

繼續上面暫停的歸納證明：$R_n\overline{R_n} = r_0r_1 \ldots r_{2^n-1}r_{2n}r_{2n+1} \ldots r_{2^{n+1}-1} = R_{n+1}$，故 $T_{n+1} = R_{n+1}$。

由此可見，定義4的 $R_n$ 跟定義2的 $T_n$ 相同，而 $r_n$ 亦跟 $t_n$ 相同，以上四個定義等價，同樣可推導出 Thue-Morse 數列。

為統一起見，以下只使用 $T_n$ 及 $t_n$，但有需要時會註明使用哪一個定義。

自我重複的模式

透過定義2，我們知道 $T_{n+1} = T_n\overline{T_n}$，所以：

$$\begin{align} T_{n+1} &= T_n\overline{T_n} \\
&= T_{n-1}\overline{T_{n-1}}\overline{T_{n-1}}T_{n-1} \\
&= T_{n-2}\overline{T_{n-2}}\overline{T_{n-2}}T_{n-2}\overline{T_{n-2}}T_{n-2}T_{n-2}\overline{T_{n-2}} \\
&= \dots \end{align}$$

出現跟 $0, 01, 0110, 01101001, \ldots$ 相似的模式。

定義 $Sub(X, Y)$ 為把 $Y$ 中的 $0$ 替換成 $X$、$1$ 替換成 $\overline{X}$，則可知對於任何 $m$ 及 $n$，$Sub (T_m, T_n) = T_{m+n}$。（只需要就 $m+n$ 用數學歸納法便可證明，其中一步應需要 $Sub(X, \overline{Y}) = \overline{Sub (X, Y)}$。）

對於每個 $T_n$，不僅起首包含了 $T_0, T_1, \ldots, T_{n-1}$，如果按每 $2^k$ 個數字分成 $2^{n-k}$ 部分（$k<n$），便是由 $T_k$（作為 $0$）及 $\overline{T_k}$（作為 $1$）所構成的 $T_{n-k}$。

這一點可以看到 Thue-Morse 數列 $T$ 有一種類似碎形的自我重複特質。另外，在圖1中每個數字為 $0$ 的節點下截斷出來的樹狀圖，都跟整個樹狀圖相同。

數列不會連續重複三次

這一節證明 Thue-Morse 數列中不會包含連續重複三次出現的數列。首先我們需要一個方便證明的定義。

對任何在 $T$ 中的數列 $X$，如果 $X$ 在 $t_x$ 開始而且 $x$ 為偶數，則稱 $X$ 出現在偶數位置，否則稱 $X$ 出現在奇數位置。留意這個定義同時適用於任何 $T_n$。

從定義1可見，如果數列 $X$ 出現在偶數位置，而且長度為偶數，則 $\sigma^{-1}(X)$ 亦在 $T$ 之中而且出現特較早（因為若 $X$ 在 $T_n$ 之中，則 $\sigma^{-1}(X)$ 在 $T_{n-1}$ 之中）。

從定義3可見，若 $a$ 出現在偶數位置，其下一個數字必然是 $\overline{a}$；若 $a$ 出現在奇數位置，其上一個數字必然是 $\overline{a}$。

不會出現形如 $aYaYa$ 的數列

以下先證明一條引理：

$T$ 當中不存在形如 $aYaYa$ 的數列，當中 $a$ 為數字，$Y$ 為長度大於 $1$ 的數列。

證明：使用反證法。假設 $aYaYa$ 為 $T$ 當中首個及最短具此模式的數列，而最先出現在數列 $T_n$（即 $T_{n-1}$ 當中並無形如 $aYaYa$ 的數列）。

如果 $aYaYa$ 出現在偶數位置，則 $aYaY$ 出現在偶數位置，因為其長度為偶數，必然由 $T_1$ 或 $\overline{T_1}$（即 $01$ 或 $10$）組成，所以 $aYaY$ 當中 $0$ 及 $1$ 的數量必然相同，而 $aY$ 當中 $0$ 及 $1$ 的數量亦相同，故 $Y$ 的長度必須是奇數。

如果 $aYaYa$ 出現在奇數位置，則 $YaYa$ 出現在偶數位置，按上述點算 $0$ 及 $1$ 數量的方法可證 $Y$ 的長度必須是奇數。

由此可知 $Y$ 的長度為奇數。

由於 $aYaYa$ 可能出現在偶數位置或奇數位置，故可分為兩種情況：

1. $aYaY$ 在偶數位置
2. $YaYa$ 在偶數位置

情況1：$aYaY$ 在偶數位置。

由於 $aYaYa$ 當中三個 $a$ 均出現在偶數位置，其下一個數字必定為 $\overline{a}$。另外 $aYaYa$ 不會在 $T_n$ 的結尾，因為最後一個 $a$ 在奇數位置，不會位於 $T_n$ 的最後一位（最後一個數字為 $t_{2^n-1}$，屬偶數位置）。所以 $T_n$ 包含 $aYaYa\overline{a}$。

$Y$ 的長度大於 $1$ 而且是奇數，所以 $Y$ 可寫成 $\overline{a}W$，其中 $W$ 為長度大於 $1$ 的數列。即 $T_n$ 包含 $a\overline{a}Wa\overline{a}Wa\overline{a}$，而這個數列出現在偶數位置。

留意 $\sigma^{-1}(a\overline{a}) = a$ 並設 $W^{\star} = \sigma^{-1}(W)$，可得出 $\sigma^{-1}(a\overline{a}Wa\overline{a}Wa\overline{a}) = aW^{\star}aW^{\star}a$ 在 $T_{n-1}$ 之中。這與 $aYaYa$ 為最早在 $T$ 出現而且具此模式的數列的假設矛盾。

情況2：$YaYa$ 在偶數位置。

由於 $aYaYa$ 當中三個 $a$ 均出現在奇數位置，其前一個數字必定為 $\overline{a}$。另外 $aYaYa$ 不會在 $T_n$ 的起首，因為 $aYaYa$ 在奇數位置，首個 $a$ 不會位於 $T_n$ 的第一個位（第一個數字為 $t_0$，屬偶數位置）。所以 $T_n$ 包含 $\overline{a}aYaYa$。

$Y$ 的長度大於 $1$ 而且是奇數，所以 $Y$ 可寫成 $W\overline{a}$，其中 $W$ 為長度大於 $1$ 的數列。即 $T_n$ 包含 $\overline{a}aW\overline{a}aW\overline{a}a$，而這個數列出現在偶數位置。

留意 $\sigma^{-1}(\overline{a}a) = a$ 並設 $W^{\star} = \sigma^{-1}(W)$，可得出 $\sigma^{-1}(\overline{a}aW\overline{a}aW\overline{a}a) = \overline{a}W^{\star} \overline{a}W^{\star} \overline{a}$ 在 $T_{n-1}$ 之中。這與 $aYaYa$ 為最早在 $T$ 出現而且具此模式的數列的假設矛盾。

不會出現形如 $XXX$ 的數列

最後我們證明 $T$ 中不會出現連續重複三次的數列。

證明：使用反證法。假設 $T$ 包含連續重複三次的數列 $X$，即 $XXX$ 出現在 $T$ 當中。

由於 $t_{2n}$ 及 $t_{2n+1}$ 必然不相同，故 $T$ 當中不存在連續三個相同的數字，從而得出 $X$ 的長度大於 $1$。

假如 $X$ 長度為 $2$，由於不可能是 $00$ 或 $11$（否則重複三次後出現 $000000$ 或 $111111$），故只可能是 $T_1$ 或 $\overline{T_1}$。然而 $Sub(T_{n-1}, T_1) = T_n$，代表 $T_{n-1}$ 中包含 $000$ 或 $111$，產生矛盾。由此得出 $X$ 的長度大於 $2$。

由於 $X$ 的長度大於 $2$，故 $X$ 可以寫成 $aY$，其中 $Y$ 的長度大於 $1$。 $XXX$ 出現在 $T$ 當中，代表 $aYaYa$ 出現在 $T$ 當中，即 $T$ 包含 $aYaYa$ 而且 $Y$ 的長度大於 $1$，與上述引理矛盾。

所以 $T$ 當中不存在連續重複三次的數列 $X$。

P.S. 著名數學網誌作者Matrix67也曾經寫過Thue-Morse數列。