子串复杂度、平衡 01 串与 Sturmian 串

让我们先从两个小问题开始说起。第一个问题是，是否存在某个无限不循环的 01 串，使得对于任意一个正整数 n ，该 01 串中长度为 n 的子串都有且仅有 n + 1 种？

或许这个问题来得有些突然。让我们慢慢解释一下，这个问题是怎么来的。衡量一个 01 串的复杂程度有很多办法，比方说，我们可以去考察它的“子串复杂度”（subword complexity），即子串的种类有多丰富。我们用 p_w(n) 来表示，在一个（有可能无限长的）数字串 w 当中，长度为 n 的子串一共有多少种。例如，对于无限 01 串 α = 000000… 来说，不管 n 是多少， p_α(n) 永远都等于 1 ；而对于无限 01 串 β = 001001001… 来说，我们有 p_β(1) = 2 ，并且 p_β(2) = p_β(3) = p_β(4) = … = 3 。

注意，虽然 α 和 β 这两个 01 串都是无限的，但是当 n 的值变得很大时， p_α(n) 和 p_β(n) 的值始终很小。当然，这一点也不奇怪，因为 α 和 β 是一种特殊的无限 01 串——无限循环 01 串。对于那些无限不循环的 01 串来说，这种事情就不大可能了。在数字串 γ = 01001000100001… 里，长度为 1 的子串只有 {0, 1} 共 2 种，长度为 2 的子串有 {00, 01, 10} 共 3 种，长度为 3 的子串有 {000, 001, 010, 100} 共 4 种，长度为 4 的子串有 {0000, 0001, 0010, 0100, 1000, 1001} 共 6 种……像这样继续计算下去，我们可以得到序列 p_γ(1), p_γ(2), p_γ(3), p_γ(4), … 的前面若干项：

2, 3, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, 49, 56, 64, 72, 81, 90, 100, 110, …

趋势非常明显：随着 n 的增加， p_γ(n) 的值也会跟着增加，最终可以增加到任意大。换句话说， p_γ(n) 的值没有一个上限。那么，能否找到某个无限不循环的 01 串 w ，使得 p_w(n) 的值存在上限呢？不可能！下面我们就来说明，对于任意一个无限不循环的 01 串 w 来说，不管 n 是多少，不等式 p_w(n) ≥ n + 1 始终成立。

容易想到，在任意一个无限 01 串 w 当中，长度为 n + 1 的子串种数都不会少于长度为 n 的子串种数。换句话说，在序列 p_w(1), p_w(2), p_w(3), … 中，从第二项开始，每一项都一定大于等于前一项。不过，如果无限 01 串 w 不是循环的，那么后一项必然会严格地大于前一项，不可能等于前一项。为什么呢？想一想，如果存在某个 m 使得 p_w(m) = p_w(m + 1) ，这会意味着什么？这意味着，在无限 01 串 w 当中，每一种长度为 m 的子串都满足：它在 w 中的每一次出现，后面跟着的数字都是相同的（要么都是 0 ，要么都是 1 ）。现在，找出 w 中的两个相同的并且长度都为 m 的子串（由于 w 的长度是无限的，而 m 的值是有限的，因此这是一定能办到的），比如说第 i 个数字到第 i + m – 1 个数字所组成的子串，以及第 j 个数字到第 j + m – 1 个数字所组成的子串（无妨假设 i < j）。于是，第 i + m 个数字也就必然和第 j + m 个数字相同，进而第 i + m + 1 个数字必然和第 j + m + 1 个数字相同，进而第 i + m + 2 个数字必然和第 j + m + 2 个数字相同……不断这样下去，直到我们最后推出，第 i + m + (j – i) 个数字，也就是第 j + m 个数字，和第 j + m + (j – i) 个数字相同，此时循环产生。可见， w 将会成为一个循环长度为 j – i 的无限循环 01 串。

我们证明了，对于任意一个无限不循环 01 串 w 来说， p_w(1), p_w(2), p_w(3), … 中的后一项都严格大于前一项。然而，在一个无限不循环 01 串当中，一定既有 0 出现，又有 1 出现，因而 p_w(1) = 2 。于是， p_w(2) 至少是 3 ， p_w(3) 至少是 4 ，等等。换句话说， p_w(n) ≥ n + 1 始终成立。

于是就有了本文开头提出的问题：是否存在某个无限不循环 01 串 w ，使得对于所有正整数 n 来说， p_w(n) 正好都等于 n + 1 ？如果真的存在这样的无限不循环 01 串，那么可以想象，它将会是一个非常基本、非常简约的无限不循环 01 串！

在这里，我们规定一下无限 01 串、无限循环 01 串、无限不循环 01 串的意思。大家知道，小数分为有限小数和无限小数，其中无限小数分为循环小数和不循环小数，而循环小数又分为两种：纯循环小数和混循环小数。举些例子： 1/4 = 0.25 就是有限小数， 1/7 = 0.142857142857142857… 就是无限循环小数中的纯循环小数， 57/110 = 0.5181818… 就是无限循环小数中的混循环小数， π/10 = 0.31415926… 则是无限不循环小数。我们不妨借用这个概念来描述 01 串。因此， 110110 就是有限 01 串， 110110110110… 就是无限循环 01 串当中的纯循环 01 串， 0000000110110110110… 就是无限循环 01 串当中的混循环 01 串， 01001000100001… 则是无限不循环 01 串。因此，那些刚开始不循环，后来才开始发生循环的 01 串，也归为了无限循环 01 串当中。

等等，本文开头说到“让我们先从两个小问题开始说起”，第二个小问题是什么呢？第二个小问题是：是否存在某个无限不循环的 01 串，使得在任意两个长度相等的子串当中，数字 1 的个数最多只差一个？

这个问题似乎也来得比较突然。让我们也稍作一番讨论吧。

如果在某个（有可能无限长的） 01 串当中，对于任意两个长度相同的子串，它们当中数字 1 的个数都最多相差一个，我们就说这个 01 串是一个“平衡 01 串”（balanced word）。比方说， 01010 就是一个平衡 01 串，而 00011 就不是一个平衡 01 串。一个无限长的 01 串有可能是平衡 01 串吗？当然有可能，比如在无限循环 01 串 01010101… 当中，任意一个长度为 2k 的子串总是含有 k 个 1 ，任意一个长度为 2k + 1 的子串总是含有 k 或 k + 1 个 1 ，因而这个无限 01 串显然是平衡的。我们还能构造出一些更复杂的例子，比如无限循环 01 串 110101101011010… （以 11010 为循环节），可以验证，它也是平衡的。

注意，并不是所有循环的无限 01 串都是平衡的，比如 000111000111… 就是一例。那么反过来，是否所有平衡的无限 01 串都是循环的呢？这个问题就不太好回答了。其实，这个问题就等价于我们刚才提出的问题二：能否找到某个无限不循环的 01 串，使得它也满足平衡性？

不可思议的是，第一个问题的答案是肯定的：确实有这么一个无限不循环的 01 串 w ，使得 w 的子串复杂度的每一项都能达到理论下限。不可思议的是，第二个问题的答案也是肯定的：确实有这么一个无限不循环的 01 串 w ，使得 w 同时也是一个平衡 01 串。更加不可思议的是：居然有这么一个无限不循环的 01 串 w ，它同时满足上面这两个条件！天哪，这该是一个多么精致有型的 01 串呀！

这确实是一个非常美妙的 01 串。令 S₀= 0, S₁= 01, S_n= S_n-1S_n-2：

S₀= 0

S₁= 01

S₂= 010

S₃= 01001

S₄= 01001010

S₅= 0100101001001

S₆= 010010100100101001010

S₇= 0100101001001010010100100101001001

……

像这样无限地迭代下去，最终所得的串就叫做 Fibonacci 串。这就是一个可以同时回答上述两个问题的 01 串。很容易看出它和 Fibonacci 数的关系：它们拥有相同的递推关系，只不过一个是作用在数字串的连接运算上的，另一个是作用在正整数的加法运算上的。

Fibonacci 串有很多有趣的性质，比方说，对于任意正整数 n ≥ 1 ， S_n都可以看作是在 S_n-1的基础上按照替换规则 {0 → 01, 1 → 0} 变换得来的。利用数学归纳法可以迅速证明这一点。显然，当 n = 1 和 n = 2 时，结论是成立的。另外，假设结论对于所有小于 k 的正整数都成立，现在对 S_k-1使用替换规则，这实质上相当于是对 S_k-2S_k-3使用替换规则，其结果相当于 S_k-1S_k-2，也就是 S_k。至此我们便完成了全部归纳证明。

因此，我们得到了 Fibonacci 串的另一种更简洁的定义方式：从数字 0 出发，不断套用替换规则 {0 → 01, 1 → 0} ，最终得到的就是 Fibonacci 串。事实上，我们甚至可以把 Fibonacci 串等价地定义为：唯一一个在替换规则 {0 → 01, 1 → 0} 下保持不变的无限 01 串。首先，这样的 01 串必然以 0 开头，否则一经替换，第一位就已经变了。接下来，这个 01 串必然以 01 开头，否则一经替换，第二位将会不同。由此又可推出，这个 01 串必然以 010 开头，进而必然以 01001 开头，进而必然以 01001010 开头……最终你会发现，如果整个串在替换规则 {0 → 01, 1 → 0} 下保持不变，那么 Fibonacci 串是唯一的可能。

Fibonacci 数与黄金比例 (√5– 1) / 2 ≈ 0.618 有着密不可分的联系， Fibonacci 串也不例外。 Fibonacci 串还有一个非常神奇的等价定义。作出正比例函数 y = k · x 的图像，其中斜率 k = (√5– 1) / 2 。每次图像穿过一条竖直的网格线，就记一个数字 0 ；每次图像穿过一条水平的网格线，就记一个数字 1 。由此得到一个无限 01 串，它就是 Fibonacci 串！

让我们简单解释一下这是为什么。首先考虑这么一个问题：如果函数图像的斜率从 k 变为了 k + 1 ，由此所得的 01 串会发生怎样的变化？你会发现，原来函数图像与第 i 条竖直线交于 (i, k · i) ，现在函数图像与第 i 条竖直线就交于了 (i, (k + 1) · i) = (i, k · i + i) 。也就是说，函数图像与第 1 条直线的交点升高了 1 个单位，与第 2 条直线的交点升高了 2 个单位，与第 3 条直线的交点升高了 3 个单位，以此类推。容易看出，这将会导致，每两个相邻的 0 之间都会多出一个 1 。举个例子，假如原函数图像与第 3 条竖直线和第 4 条竖直线分别交于 (3, 1.854) 和 (4, 2.472) ，由于 1.854 和 2.472 之间夹着一个整数，因而在这里会产生一个 1 ；然而，在新的函数图像中，交点 (3, 1.854) 变成了 (3, 4.854) ，交点 (4, 2.472) 变成了 (4, 6.472) ，现在 4.854 和 6.472 之间夹着两个整数了，因而在这里产生的是两个 1 。我们可以总结一下：如果函数图像的斜率从 k 变为了 k + 1 ，那么原来 01 串当中的每个 0 前面都会多一个 1 ，或者说，原来 01 串当中的每个 0 都会变成 10 。

然后我们来考虑这么一个问题：如果函数图像的斜率从 k 变为了 1/k ，由此得到的 01 串会发生怎样的变化？很简单：所有的 0 都会变成 1 ，所有的 1 都会变成 0 。这是因为，前后两个函数图像一定是关于直线 y = x 轴对称的，因此原函数图像每次穿过一条水平线，新函数图像都会穿过一条竖直线，原函数图像每次穿过一条竖直线，新函数图像都会穿过一条水平线。这就意味着，在前后两个函数图像所对应的 01 串当中， 0 和 1 的角色正好互换。

那么，如果把函数图像的斜率从 k 变为 1/(k + 1) ，对应的 01 串会怎么样呢？根据刚才的讨论，这个 01 串会分两步发生变化：首先，所有的 0 都变成 10 ，所有的 1 都不变 ；然后，所有的 0 变成 1 ，所有的 1 变成 0 。最终的效果便相当于把所有的 0 都变成 01 ，并把所有的 1 都变成 0 。有趣的是，如果 k 正好等于 1/(k + 1) ，换句话说 k = (√5– 1) / 2 时（舍去负数解），那么函数 y = k · x 的图像所对应的 01 串就会满足这么一个神奇性质：把所有的 0 变成 01 ，并把所有的 1 变成 0 后，整个 01 串保持不变。然而，之前我们已经说过了， Fibonacci 串是唯一满足上述性质的 01 串。至此我们便证明了，斜率为 (√5– 1) / 2 的正比例函数图像切割网格线所得的 01 串，确实就是 Fibonacci 串。

我们刚才介绍了 Fibonacci 串的诸多等价定义。 Fibonacci 串的很多重要性质，都可以由其中一种或者几种定义很快得出。比如说， Fibonacci 串当中的每个子串都会出现无穷多次；再比方说， Fibonacci 串当中不会出现连续两个 1 ，也不会出现连续三个 0 ；再比方说， Fibonacci 串当中数字 0 的个数所占比例就是黄金比例 (√5– 1) / 2 ≈ 0.618 。最后一点可以顺便告诉我们， Fibonacci 串是无限不循环的，因为很容易证明，在任何一个无限循环的 01 串当中，数字 0 的个数所占的比例都应该是一个有理数。

不过，前面还有两个巨大的坑没有填上：为什么 Fibonacci 串当中，长度为 n 的子串恰好有 n + 1 种？为什么 Fibonacci 串当中，任意两个长度相同的子串里数字 1 的数目最多只差一个？由于这两件事情证明起来并不容易，因此我就省略了。不但如此，接下来，我还要挖一个更大的坑。

回想一下 Fibonacci 串的最后一种定义，你会发现它有一种很自然的扩展。任取一个大于 0 的无理数 k 作为斜率 ，任取一个大于等于 0 小于 1 的实数 b 作为截距，我们都会得到一个一次函数 y = k · x + b ，它的图像是一条直线。这条直线将会穿过一条一条的网格线，和刚才一样，如果穿过了一条竖直线，我们就写下一个数字 0 ，如果穿过了一条水平线，我们就写下一个数字 1 。这样，我们便会得到一个无限 01 串。下图所示的就是当 k = π / 2 并且 b = 2 / 3 的情况，这将会生成一个以 11010110 开头的无限 01 串。注意，这里的 k 值必须是一个无理数，这保证了 01 串不是循环的。我们把这样的 01 串通通叫做 Sturmian 串（这种叫法最早出自 Marston Morse 和 Gustav Hedlund 在 1940 年发表的一篇论文）。

最令人震撼的地方到了。不但 Fibonacci 串满足上面两个性质，事实上所有的 Sturmian 串都满足上面两个性质。 Jean-Paul Allouche 和 Jeffrey Shallit 把这一切总结为下面这个精彩的定理。

如果 w 是一个仅由 0 和 1 组成的数字串，那么下面三个条件是完全等价的：

(1) 对于所有正整数 n 都有 p_w(n) = n + 1 ；

(2) w 是一个无限不循环的平衡 01 串；

(3) w 是一个 Sturmian 串。

我打算略去证明过程，因为结论本身远比证明过程更加激动人心。感兴趣的读者可以参考 Automatic Sequences: Theory, Applications, Generalizations 的第 10 章。