你在这里

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

让我们先从两个小问题开始说起。第一个问题是,是否存在某个无限不循环的 01 串,使得对于任意一个正整数 n ,该 01 串中长度为 n 的子串都有且仅有 n + 1 种?
或许这个问题来得有些突然。让我们慢慢解释一下,这个问题是怎么来的。衡量一个 01 串的复杂程度有很多办法,比方说,我们可以去考察它的“子串复杂度”(subword complexity),即子串的种类有多丰富。我们用 pw(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 ,使得 pw(n) 的值存在上限呢?不可能!下面我们就来说明,对于任意一个无限不循环的 01 串 w 来说,不管 n 是多少,不等式 pw(n) ≥ n + 1 始终成立。

容易想到,在任意一个无限 01 串 w 当中,长度为 n + 1 的子串种数都不会少于长度为 n 的子串种数。换句话说,在序列 pw(1), pw(2), pw(3), … 中,从第二项开始,每一项都一定大于等于前一项。不过,如果无限 01 串 w 不是循环的,那么后一项必然会严格地大于前一项,不可能等于前一项。为什么呢?想一想,如果存在某个 m 使得 pw(m) = pw(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 来说, pw(1), pw(2), pw(3), … 中的后一项都严格大于前一项。然而,在一个无限不循环 01 串当中,一定既有 0 出现,又有 1 出现,因而 pw(1) = 2 。于是, pw(2) 至少是 3 , pw(3) 至少是 4 ,等等。换句话说, pw(n) ≥ n + 1 始终成立。
于是就有了本文开头提出的问题:是否存在某个无限不循环 01 串 w ,使得对于所有正整数 n 来说, pw(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 串。令 S0 = 0, S1 = 01, Sn = Sn-1Sn-2 :
S0 = 0
S1 = 01
S2 = 010
S3 = 01001
S4 = 01001010
S5 = 0100101001001
S6 = 010010100100101001010
S7 = 0100101001001010010100100101001001
……
像这样无限地迭代下去,最终所得的串就叫做 Fibonacci 串。这就是一个可以同时回答上述两个问题的 01 串。很容易看出它和 Fibonacci 数的关系:它们拥有相同的递推关系,只不过一个是作用在数字串的连接运算上的,另一个是作用在正整数的加法运算上的。
Fibonacci 串有很多有趣的性质,比方说,对于任意正整数 n ≥ 1 , Sn 都可以看作是在 Sn-1 的基础上按照替换规则 {0 → 01, 1 → 0} 变换得来的。利用数学归纳法可以迅速证明这一点。显然,当 n = 1 和 n = 2 时,结论是成立的。另外,假设结论对于所有小于 k 的正整数都成立,现在对 Sk-1 使用替换规则,这实质上相当于是对 Sk-2Sk-3 使用替换规则,其结果相当于 Sk-1Sk-2 ,也就是 Sk 。至此我们便完成了全部归纳证明。
因此,我们得到了 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 都有 pw(n) = n + 1 ;
(2) w 是一个无限不循环的平衡 01 串;
(3) w 是一个 Sturmian 串。

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