哇哦……我获得了首届卢卡·特雷维桑理论计算机科学阐释性工作奖！这对我来说意义非凡，因为我与卢卡·特雷维桑相识25年——他曾是我的教授和论文委员会成员，我的博客与他的博客密切相关，我从他在理论计算机科学领域的阐释性工作中受益匪浅——直到两年前卢卡不幸因癌症去世。
正如我告诉委员会的那样，获得这个奖项让我想要更多地利用我的博客来阐述真正的计算机科学理论，而不是发泄情绪，以便将来能够更配得上这份荣誉。
我无比感激整个 TCS 社区——我的伙伴们，我的兄弟们——感谢他们容忍我做我所做的事。
如果你感兴趣，这里是官方引用：
首届卢卡·特雷维桑理论计算机科学阐释奖授予斯科特·阿伦森，以表彰他为向广大受众阐释和推广该领域所做出的持续而卓有成效的贡献。二十多年来，他的博客“Shtetl-Optimized”发表了大量内容详实、更新频繁的文章，已成为理论计算机科学和物理学界广泛交流的中心平台。斯科特·阿伦森的博客文章清晰明了、信息丰富，对激动人心的新成果进行了阐述，对技术主张进行了客观评估，并对这些领域乃至更广泛的主题进行了深刻分析。他独特的热情和诙谐的写作风格（包括他的著作《自德谟克利特以来的量子计算》以及其他讲义和综述）、演讲和访谈，使他成为大众和专业场合的热门嘉宾，吸引了众多听众。这些特质激励了许多学生进入这个领域，也使 Scott Aaronson 成为记者和科学家们寻求有关 TCS 和量子计算领域最新科学活动的权威见解的首选对象。
在本文的剩余部分，我将开始践行我之前所倡导的——也就是将博客的更多篇幅用于真正的阐述，这或许正是特雷维森奖（Trevisan Award）的初衷所在。首先，我想谈谈过去几个月我一直搁置的事情：那就是我今年春天在德克萨斯大学奥斯汀分校本科生数学俱乐部所作演讲的（略作编辑的）文字稿。那么，废话不多说，谨以此文纪念卢卡……
2 的幂的十进制数字
作者：斯科特·阿伦森
大家好！我之前在德克萨斯大学数学俱乐部做过六次演讲，其中一些主题比较“重要”——哥德尔定理、时间旅行、黄氏对灵敏度猜想的证明等等。
今天，我想谈谈一个无关紧要的问题，这个问题是我儿子丹尼尔（当时 8 岁，现在就坐在前排，和他的妹妹莉莉一起）几个月前问我的。
丹尼尔问道：哪些 2 的幂可以乘以 2 而不进位？显然，1、2、4、32 和 1024 都满足这个条件，它们的倍数分别是 2、4、8、64 和 2048。还有其他的吗？
由于我从小就牢记 2 的幂直到2²⁰ = 1,048,576，我确认在此之前没有其他例子：128、256、512、2048 等等都需要进位。所以我告诉丹尼尔：我找不到任何其他例子，基于此，我推测没有更多了。但如果这个推测是正确的，我不知道它是否会被人类甚至人工智能证明！
然后我用谷歌搜索了一下，发现这是一个 已知问题（虽然不算广为人知，但StackExchange上确实有相关的帖子）。而且确实有人用两百万次搜索验证过，没有找到其他反例。
为什么我如此迅速地确信，1024可能是最后一个可以不进位就翻倍的 2 的幂的例子？
由于 2^ n的十进制数字大致是“随机的”（除了一些与此无关的约束，例如最后一位数字总是在 2、4、6 和 8 之间循环），因此 2^ n大约有 n/ log₂¹⁰位十进制数字。由于只有 0、1、2、3、4 可以不进位地乘以 2，因此 2^ n是反例的概率约为 $$ (\frac{1}{2} )^{n / \log_2¹⁰}. $$
所以，如果我们已经检查到（比如）n=1000，那么出现更大反例的概率至多应该是
$$ \sum_{n=1001}^{\infty} (\frac{1}{2} )^{n / \log_2 10} $$
当我们把等比数列求和时，会发现它非常接近于 0。
啊，但我为什么说我不知道这个猜想是否最终会被证明呢？因为它似乎属于一大类类似的命题，而数学家们至今都不知道该如何证明这类命题。
Jeffrey Shallit 的一个猜想的变体： 65,536 是唯一一个十进制数字中没有 2 的幂的 2 的幂。
弗里曼·戴森猜想（2005 年）：不存在 2 的幂，当它的十进制数字反转时，会得到 5 的幂。
保罗·埃尔德什的猜想（1979）：对于每个 n≥9，2n 的 3进制表示中至少有一个“2”。
或者更广泛地来看：
猜想： π 的十进制展开式在某个有限点之后并非全是 6 和 7。
（这可以从更强的猜想中得出，即π是十进制正规数——也就是说，任何有限的十进制数字模式都会以你预期的极限频率出现在π中。）
或者：
猜想： π+e 是一个无理数。
以上所有猜想的共同之处，也是我觉得它们最引人入胜的地方，在于它们似乎根本无法证明，而原因恰恰是它们几乎肯定为真的原因。也就是说，它们似乎“仅仅”是正确的，因为如果它们是假的，那就太巧合了！
问题在于，这种理由似乎难以转化为证明。费马大定理是一个有趣的例外，它恰恰证明了这条规则。当n≥3时，方程xⁿ + yⁿ = zⁿ没有非平凡整数解，而当n≥4时，从统计学角度来看，这个结论几乎肯定成立（至于n=3的情况，欧拉的证明可以追溯到n=3）。当然，费马大定理最终是可以证明的。但怀尔斯的最终证明巧妙地利用了费马方程与模形式、椭圆曲线等深奥概念之间的联系。证明过程中，他从未正式阐述过一个12岁孩子都能理解的、关于定理“几乎肯定成立”的统计论证。它与统计论证本身毫无关系。
所以，如果你想证明像我儿子丹尼尔的猜想，或者像上面提到的沙利特、戴森或埃尔德什的猜想，问题就变成了：这些关于十进制表示的“娱乐性”问题，是否有可能与任何类似深奥的事物联系起来？目前来看，很难看出它们如何能联系起来。
不过，希望尚未完全破灭！我在研究这个问题时发现了一个令人震惊的定理：
定理（James Maynard，2016）：对于从 0 到 9 的每个数字 a，都有无穷多个素数，它们的十进制表示中没有 a。
这个证明运用了大量的傅里叶分析技巧。同样地，可以推测存在无穷多个素数，它们的乘积可以不进位——例如 2、3、11、13、23、31……——因为素数的密度远大于 2 的幂！而且可以推测存在无穷多个素数，它们的小数部分缺少任意两位数字，甚至有些素数的小数部分完全由 0 和 1 组成。但是，梅纳德的技巧目前还不足以证明这些。
尽管我今天承诺要讲一个无关紧要的话题，但我还是忍不住要指出，这与目前地球上最大的问题之一，也是我过去四年来一直很感兴趣的一个问题，可能存在某种联系：那就是如何使强大的人工智能与人类价值观保持一致，并防止它们毁灭世界。
保罗·克里斯蒂亚诺和他创立的伯克利对齐研究中心开发了一整套使人工智能安全的方案，该方案依赖于形式化“启发式论证”的可能性——也就是说，即使没有证明，也能让我们确信上述猜想几乎肯定是正确的论证类型。
这里的直觉是，我们永远无法严格证明，例如，现实世界中的神经网络在任何情况下都能安全运行——这太复杂了。我们所能期望的最好结果是，例如，“要让这个模型对人类进行阴谋，就需要其权重中存在一种无法解释的巧合”。但是，我们如何才能将这样的论证形式化呢？作为初步的测试用例，我们能否至少以某种原则性的方式，将我们对π为什么是正态分布，或者丹尼尔猜想为什么成立的直觉形式化呢？
ARC 已经尝试过：Christiano、Neyman 和 Xu 在2022 年发表了一篇题为“形式化独立性假设”的论文。但这很棘手，ARC 本身也会首先承认，现有的结果并不令人满意。例如，我们该如何形式化“你应该愿意以 1:1 的赔率打赌 π 的第10位数字不是 5”这种直觉呢？
在本次演讲的剩余部分，我想回到丹尼尔最初关于 2 的幂的问题，并向大家展示一些可以证明的事情——感谢 Greg Kuperberg 和我在 Facebook 上的其他朋友，在某些情况下还要感谢 GPT5Pro。
让我们先从下面这个更简单的问题开始。是否存在一个 2 的幂，其十进制数字以 31415开头？或者，是否存在一个 2 的幂，其十进制数字包含莎士比亚的全部作品，并以某种合适的方式用字母值编码？或者，是否存在一个 googolplex 的幂，其所有数字都可以翻倍而不进位（就像丹尼尔想要的那样）？
我认为答案是肯定的！我们如何证明这一点？
我们将用到的关键事实是：log 10 2 是一个无理数。（如果你不记得证明过程：假设 log 10 2 = a/b。那么 10 a/b = 2，所以 10 a = 2 b 。但除了 a=b=0 之外，这个等式没有其他整数解。）
假设我们想要 k 作为前缀，其中10d-1 ≤ k ≤ 10d 。那么我们想要整数 n 和 r，使得
$$ k 10^r \le 2^n \le (k+1) 10^r, $$
即取以 10 为底的对数，
$$ \log_{10}k + r \le n \log_{10}2 \le \log_{10}(k+1) + r。 $$
换句话说，n log 10 2 的小数部分需要位于 log 10 (k) 的小数部分和 log 10 (k+1) 的小数部分之间（其中 k 是给定的）。
但现在我们可以利用以下关键事实：如果 α 是任意无理数，则集合
{nα 的小数部分 : n∈N}
在区间 [0,1] 内稠密。或者等价地，如果我绕单位圆旋转 2απ 弧度，那么如果 α 是无理数，我最终将任意接近单位圆上的任何给定点。
为什么这个关键事实成立？答案就在于鸽巢原理！显然，对于任意 ε>0，α 为无理数意味着必然存在两个点 xα 和 yα，它们的分数部分互不相同，但比 ε 更接近。然而，通过叠加 (xy)α 的倍数，我们可以使分数部分与 [0,1] 中的任意值都接近 ε。
综上所述，这就是为什么一定存在一个 2 的幂，它的十进制表示以莎士比亚全集开头，或者以古戈尔普勒克斯的无进位数字开头！（事实上，从上面的讨论中，我们甚至可以提取出一个构造这个 2 的幂的高效算法。）
以上就是2n的前几位小数。现在让我们来看看2n的后几位小数！
这里存在一些复杂情况，源于以下两个事实：
（a）10是合数，并且
（b）2 是它的因子之一。
但是我们可以应对这些复杂情况！
首先： 2n的最后几位小数可能是什么？
1、2、4、8、6、2、4、8、6、…
所以，初始值为 1，然后我们会无限循环使用偶数非零数字。
2n的最后两位数字是什么？如果你以前从未尝试过，计算一下会很有启发性：
01、02、04、08、16、32、64、28、56、12、24、48、96、92、84、68、36、72、44、88、76、52、04、…
所以，最初有 01 和 02，但之后，我们会无限循环 20=4×5 种可能性，即所有个位数非零的 4 的倍数。
你可以验证一下，一般规律是：2^ n的最后 k 个十进制数字的初始段看起来像 001, 002, 004, 008, …, 2 ^k-1 。然后是一个长度为 4×5 ^k-1的无限循环，其中最后一位可以是 2、4、6 或 8 中的任意一个，而其他每一位可以是任意偶数或任意奇数，具体取决于它右边的数字——（如果你想用更专业的说法）这是 2 的模 5^ k的幂递归地嵌入到循环群 Z/10 ^k中。因此，当你填满所有需要的 2 的幂时，会有一个初始的“上升”，但一旦完成，你就会在 Z/5^ k到 Z/10 ^k的嵌入中无限循环，因为
（a）对于任意 k，2 恰好是 Z/5 k的一个本原元素，并且
（b）5 能整除 10。
特别地，与丹尼尔的猜想相关的是：存在一个 2 的幂，它的最后几位googolplex 数字都可以乘以 2 而不进位。为什么呢？最后一位数字可以是 2 或 4。然后，对于倒数第二位 googolplex 数字，如果它们必须是奇数，则可以选择 1 或 3；如果它们必须是偶数，则可以选择 0、2 或 4。有很多选择都可行！
所以，我们可以避免 2^ n最左边的数字出现进位，也可以避免最右边的数字出现进位……这样“仅仅”就剩下中间的数字了，至于这些数字在哪儿，谁也说不准！经验表明，这些数字似乎通过了所有你能想到的标准随机性测试。例如，数字 {0,1,2,3,4} 所占的比例似乎不可避免地趋近于 50%，因此，我们完全可以推测，对于有限个 n 值，这个比例小于 49% 或大于 51%。当然，这大概比丹尼尔最初的猜想更难证明。
好的，最后一个话题。假设我们想编写一个程序，让计算机验证丹尼尔猜想在 2^ n范围内成立，其中 n 是一个很大的数。哪种算法效率最高？一个简单的算法会计算 1, 2, 4, …, 2^ n ，并逐个检查它们的每一位数字。这需要 O(n^ 2 ) 的时间复杂度，因为每个 2^ k （k=0,1,…,n）都有约klog10 ^2 = O(k) 位十进制数字。
我们可以通过注意到，对于每个 2 的幂，我们只需要检查 O(1) 位数字（假设如此），直到找到第一个需要进位的数字，就可以将时间复杂度提高到大约 O(n)。然后我们甚至不需要计算剩余的数字：我们可以直接跳到下一个 2 的幂。（这种技巧在快速算法的设计中被广泛应用。）
但当我在 Facebook 上发布关于丹尼尔问题的帖子时，我的朋友格雷格·库珀伯格（加州大学戴维斯分校的数学家）注意到还有进一步改进的空间。例如：8×6 = 48，它同样以 8 结尾。因此，8×16 以 8 结尾，8× 16k也以 8 结尾，对于所有 k≥0 都是如此。这意味着：不存在任何2n，其中 n=3+4k，它们都不可能成为丹尼尔猜想的反例。它们都被排除了！
同样，64×1,048,576 的末尾是 64，所以不存在形如 n=6+20k 的2n可以作为反例。它们也都被排除在外了。
我们可以继续这样做，通过广度优先搜索来填充丹尼尔猜想潜在反例的“搜索树”。在搜索树的根节点，我们尝试最后一位数字的所有可能性。再往下一层，我们尝试倒数第二位数字的所有可能性，依此类推。随着搜索的进行，我们会根据不断发现和添加的约束条件（例如上述约束）来修剪子树。
当我解决这个问题时，我得到了一个算法，用于检验丹尼尔猜想到2n的情况，在合理的假设下，该算法的时间复杂度仅为 O( nα )，其中 α = 1-log 52 ≈ 0.569，空间复杂度仅为 polylog(n)。
Paul Crowley （我的 Facebook 好友）随后实现了这个算法，他告诉我，他用这个算法在一台 128 核的机器上花了 40 分钟，验证了 Daniel 的猜想在 $$2^{10^{21}}$$ 范围内都成立（！！）。
所以，最后回到我告诉丹尼尔的第一件事：是的，我认为他的猜想几乎肯定是正确的，尽管我不知道人类或其后代何时（如果有的话）才能得到证明。