驯服中距离的数学技巧| 广达杂志

今年到目前为止， 广达 记录了拉姆齐理论的三大进展，即研究如何避免创建数学模式的理论。 这 第一个结果 对不包含三个均匀间隔的数字（例如 {2, 4, 6} 或 {21, 31, 41}）的整数集的大小设置新的上限。 这 第二 和 第三 类似地，对网络的大小设置了新的界限，没有点簇，这些点要么全部连接，要么全部彼此隔离。

这些证明解决了当涉及的数字无限大时会发生什么。 矛盾的是，这有时比处理烦人的现实世界数量更容易。

例如，考虑两个关于分母很大的分数的问题。 您可能会问，例如 1/42503312127361 的十进制展开式是多少。 或者您可能会问，随着分母的增加，这个数字是否会接近于零。 第一个问题是关于现实世界数量的具体问题，它比第二个问题更难计算，第二个问题询问数量 1/n 将“渐进”地改变为 n 成长。 （它越来越接近0。）

“这是困扰整个拉姆齐理论的一个问题，”说 威廉·加萨克，马里兰大学计算机科学家。 “拉姆齐理论因具有渐近非常好的结果而闻名。” 但分析小于无穷大的数字需要完全不同的数学工具箱。

加萨奇研究了拉姆齐理论中涉及有限数的问题，这些有限数太大而无法通过蛮力解决。 在一个项目中，他研究了今年第一个突破的有限版本——一篇 XNUMX 月份的论文 詹德·凯利，伊利诺伊大学厄巴纳-香槟分校的研究生， 拉古·梅卡 加州大学洛杉矶分校。 凯利和梅卡发现了 1 到 XNUMX 之间的整数数量的新上限 N 您可以放入一组，同时避免三项级数或均匀间隔的数字模式。

尽管凯利和梅卡的结果即使 N 相对较小，在这种情况下它没有给出特别有用的界限。 对于非常小的值 N，你最好坚持使用非常简单的方法。 如果 N 比如说 5，只需查看 1 到 XNUMX 之间所有可能的数字集 N，并选出最大的无级数：{1, 2, 4, 5}。

但不同可能答案的数量增长得非常快，使得采用如此简单的策略变得非常困难。 由 1 到 1 之间的数字组成的集合超过 20 万个。有超过 10 个⁶⁰ 使用 1 到 200 之间的数字。即使采用提高效率的策略，为这些情况找到最佳的无进展集也需要大量的计算能力。 “你需要能够从事物中榨取大量性能，”说 詹姆斯格伦，耶鲁大学计算机科学家。 2008 年，加萨奇、格伦和 克莱德·克鲁斯卡尔 马里兰大学 写了一个程序 找到最大的无进展设置 N 187 个。（之前的工作得到了 150 个以内的答案，以及 157 个以内的答案。）格伦说，尽管有一系列的技巧，他们的程序还是花了几个月的时间才能完成。

为了减轻计算负担，该团队使用了简单的测试来防止他们的程序进行死胡同搜索，并将他们的集合分成更小的部分，然后分别进行分析。

加萨奇、格伦和克鲁斯卡尔还尝试了其他几种策略。 一个有前途的想法依赖于随机性。 提出无级数集合的一个简单方法是将 1 放入集合中，然后始终添加下一个不会创建算术级数的数字。 遵循此过程，直到达到数字 10，您将得到集合 {1, 2, 4, 5, 10}。 但事实证明，这并不是一般的最佳策略。 “如果我们不从 1 开始怎么办？” 加萨奇说道。 “如果你从随机的地方开始，你实际上会做得更好。” 他补充说，研究人员不知道为什么随机性如此有用。

计算另外两个新的拉姆齐理论结果的有限版本甚至比确定无级数集的大小更令人烦恼。 这些结果涉及由称为边的线连接的节点组成的数学网络（称为图）。 拉姆齐数 r(s, t）是图在不可能避免包含一组节点之前必须具有的最小节点数 s 连接的节点或 t 断开连接的。 拉姆齐数的计算非常令人头疼，即使 r(5, 5) 未知——它在 43 到 48 之间。

1981年， 布伦丹·麦凯现在是澳大利亚国立大学的计算机科学家，他编写了一个名为 nauty 的软件程序，旨在简化拉姆齐数的计算。 Nauty 确保研究人员不会浪费时间检查两张刚刚翻转或旋转版本的图表。 “如果有人在该区域并且没有使用 nauty，那么游戏就结束了。 你必须使用它，”说 斯坦尼斯瓦夫·拉齐佐夫斯基，罗切斯特理工学院的数学家。 尽管如此，所涉及的计算量几乎是不可理解的。 2013 年，拉齐佐夫斯基和 简·戈德博尔 事实证明 r(3, 10) 最多为 42。 “我认为，这花了近 50 个 CPU 年的时间，”比利时 KU Leuven 大学的计算机科学家 Goedgebeur 说。

如果您无法计算精确的拉姆齐数，您可以尝试通过示例缩小其值范围。 如果你发现一个 45 节点图，没有五个节点全部连接，也没有五个节点全部断开，那就证明 r(5, 5) 大于 45。拉齐佐夫斯基说，研究拉姆齐数的数学家过去认为找到这些称为拉姆齐图的例子会很简单。 但事实并非如此。 “人们期望漂亮、酷的数学结构能够提供最好的结构，我们只是需要更多的人来研究它，”他说。 “我的感觉越来越混乱。”

随机性既是理解的障碍，也是有用的工具。 杰弗里·艾克苏印第安纳州立大学的计算机科学家花了数年时间改进生成拉姆齐图的随机方法。 在 一张2015纸 Exoo 和 Milos Tatarevic 宣布了数十种新的破纪录的拉姆齐图，他们生成了随机图，然后通过删除或添加边来逐渐调整它们，以减少不需要的簇的数量，直到他们找到拉姆齐图。 不过，Radziszowski 说，Exoo 的技术就像一门艺术一样。 有时需要他结合多种方法，或者对从哪种图表开始进行判断。 “很多很多人都尝试过，但他们做不到，”拉齐佐夫斯基说。

Goedgebeur 表示，为生成拉姆齐图而开发的技术有一天可能会有更广泛的用途。 从事 生成其他类型的图表，例如表示化合物的图表。 他在一封电子邮件中写道：“这些技术也可能被转移和调整，以帮助更有效地生成其他类别的图表（反之亦然）。”

然而，对于拉齐佐夫斯基来说，研究拉姆齐小数的原因要简单得多。 “因为它是开放的，因为没有人知道答案是什么，”他说。 “那些琐碎的案件我们都是手工做的； 大一点，就需要电脑，大一点，连电脑都不够好。 因此挑战就出现了。”