|
在50年的搜索中，数学家只发现了一个符合他们标准的“子空间设计”的例子。一个新的证明表明，那里还有无限多的东西。 作者：Jordana Cepelewicz 2023-4-12 译者：zzllrr小乐 2023-4-13 2017年秋天，当时是麻省理工学院本科生的Mehtaab Sawhney加入了一个研究生阅读小组，该小组开始在一个学期内研习一篇论文。但Sawhney回忆说，到学期结束时，他们决定继续前进，因为对证明的复杂性感到困惑。“这真是太神奇了，”他说。
这篇论文是由牛津大学的Peter Keevash撰写的。它的主题：称为“设计”的数学对象。 对设计design的研究可以追溯到1850年，当时英格兰北部一个教区的牧师托马斯·柯克曼（Thomas Kirkman）涉足数学，他在一本名为《女士和绅士日记》（Lady's and Gentleman's Diary）的杂志上提出了一个看似简单的问题。假设 15 个女生每天3人一组步行上学，持续一周。你能设计一个排列，确保在这七天里，没有两个女孩会不止一次在同一组吗？
（参阅小乐数学科普：超图（Hypergraph）揭示了50年问题的解——译自Quanta Magazine量子杂志） 很快，数学家们开始问柯克曼问题的更一般版本：如果你在一个集合中有n个元素（我们的15个女生），你能不能总是将它们分成k大小的小组（3人一组），以便每个较小（t < k）的组（每两个女孩）出现在这些组中？
(每个节点代表一个女生，15 个节点之间的所有可能连接) 这种配置被称为(n, k, t) 设计，已被用于帮助开发纠错码，设计实验，测试软件以及赢得体育比赛对阵表和彩票。 但是随着k和t变大，它们也变得非常难以构建。事实上，数学家还没有找到一个t值大于5的设计。因此，在2014年Keevash证明 https:///abs/1401.3665 ，即使你不知道如何构建这样的设计，只要n足够大并满足一些简单的条件，它们总是存在的，这令人感到非常惊讶。 现在，Keevash，Sawhney和麻省理工学院的研究生Ashwin Sah已经证明，更难以捉摸的对象，称为子空间设计（subspace designs），也总是存在的。https:///abs/2212.00870 “他们已经证明了存在性不都明显的对象的存在，”加州理工学院的数学家David Conlon说。 为此，他们不得不修改Keevash的原始方法——其中涉及随机性和精心构造的近乎神奇的混合——以使其在更严格的环境中工作。因此，目前也在麻省理工学院攻读博士学位的Sawhney，他发现自己正面对几年前难倒他的论文。“完全理解这些技术，真正忍受和克服它们并发展它们，这真的非常非常愉快，”他说。 什么是设计design？ 数学家想按指定规则将元素进行分到集合和子集中。 一个(n, k, t)设计的例子——(9, 3, 2)设计：将9个点分到3个3-元素的集合中，确保每种2-元素的子集，只会出现在其中一个集合中。 此时：总数n=9，集合大小k=3，子集大小t=2。 第1步：画一个9顶点的图，以及相应所有边。
第2步：用三角形（3顶点的集合）覆盖所有边，确保没有两个三角形共边（2顶点的集合），或者说，共两个顶点。
(9, 3, 2) 设计的一个例子： 下列12个三角形覆盖了所有的边，但没有两个三角形共边。
“超越我们的想象” 几十年来，数学家们已经将关于集合和子集的问题——比如设计问题——转化为关于所谓的向量空间（也即矢量空间，线性空间）和子空间的问题。 向量空间是一种特殊的集合，其元素（向量）以比简单的点集合更严格的方式相互关联。一个点告诉你你的位置。而一个向量告诉你移动了多远，以及移动的方向。向量可以加减，变大或变小。 考虑一下你所在的房间。它包含无限数量的点和无限数量的向量——从你所在的位置延伸到房间中的每个点。所有这些向量都可以由三个基本向量构成：一个向量水平指向你面前，另一个向量指向你的右边，还有另一个指向上方。通过添加这些向量，将它们乘以实数，或两者的某种倍数组合（线性组合），你可以生成你居住的三维向量空间。（生成整个空间所需的向量数是向量空间的维度）。 每个向量空间内都有各种子空间。例如只取指向你右侧和前面的向量。这些定义了二维子空间 - 平行于地板的平面。 数学家经常使用有限向量空间和子空间，其中向量不能指向每个可能的方向（并且没有相同的长度概念）。在此世界中，每个向量空间只有有限数量的向量。 子空间设计问题处理 n 维向量空间及其子空间。在这样的向量空间中——同样，只要n足够大并且满足简单条件——你能找到一个k维子空间的集合，使得任何t维子空间都恰好包含在其中一个子空间中吗？这样的对象称为(n, k, t) 子空间设计。它在概念上类似于普通设计问题，但它涉及更严格约束的排列。
这个有限的3D三维向量空间由八个向量组成。它的2D二维子空间是四个向量的特定子集。 “这是一个重要的问题，因为它一方面是集合和子集之间非常深刻的类比，另一方面是向量空间和子空间的类比，”苏格兰圣安德鲁斯大学的Peter Cameron说。 在数学家开始思考这个问题的50年里，他们只发现了一个不平凡的例子 https://www./core/journals/forum-of-mathematics-pi/article/existence-of-qanalogs-of-steiner-systems/CCA4E791C28A449903101CF467CBB0D3 （尽管他们知道存在更通用的子空间设计）：在13维向量空间中，可以用三维子空间覆盖二维子空间恰好一次。结果需要一个基于计算机的大量证明，因为即使对于如此小的n，k和t值，你最终也会使用数百万个子空间。这种系统的复杂性“不仅超越了我们的想象，而且比超越我们想象的东西还要更超越，“以色列理工学院的Tuvi Etzion，帮助发现了这个例子，说道。 但是，对于任何k和t，子空间设计总是存在的吗？一些数学家推测，总的来说，这样的对象是不可能的。其他人对多年来在设计上所做的工作感到鼓舞，他们认为“这可能很难证明，但如果没有明显的理由说它们不存在，那么它们应该存在，”Keevash说。
与设计领域相比，“对于这个问题，一无所获，”Sah说。“我想每当这种情况发生时，这都会引发一些好奇心。” 吸收误差的海绵 Sah和Sawhney于2017年在麻省理工学院读本科时相识（并最终参加了同一个阅读小组）。几个月后，“他们开始一起工作，从未停止过，”Conlon 说。“他们正在以我甚至无法眨眼的速度进行高质量的研究”。 这两位年轻的数学家很感兴趣，因为写出一个明确的子空间设计的例子是如此困难，他们认为这个问题是探索组合数学中重要技术边界的完美方法。
在证明称为“子空间设计”的特殊物体的存在时，数学家Mehtaab Sawhney，Ashwin Sah和Peter Keevash（从左到右）测试了组合数学中几种著名方法的极限。 与此同时，Keevash自2014年的结果以来一直将这个问题放在脑后。去年，当Sah和Sawhney在一次会议上找到他时，三人决定去做。 他们遵循了Keevash在他的设计工作中制定的相同总体策略 - 但由于手头有更严格的限制，“在实践中，所有步骤最终在实施中都非常不同，”Keevash说。首先，他们留出一组精心挑选的子空间，称为模板template。该模板后来将充当随机海洋中的结构岛。 然后，他们应用了一个基本随机过程的修改版本，称为Rödl nibble（Vojtěch Rödl是捷克裔美国数学家，nibble表示小口咬，其方法接近随机贪婪算法，zzllrr小乐译注），以覆盖大多数剩余的子空间。这也留下了他们仍需处理的子空间稀疏的大杂烩。从表面上看，这些子空间看起来完全是非结构化的；似乎不可能将它们排列成可以适当覆盖的集群。 这就是模板的用武之地。他们将模板分解成碎片，并将其中的一些子空间与大杂烩中的子空间组合在一起 - 将它们紧密地塞入可以适当覆盖的更大排列中。他们必须仔细跟踪他们是如何做到这一点的，以确保他们所做的每一个举动都会导致更整体的结构。但最终，他们能够使用模板来填补 Rödl nibble 无法覆盖的所有漏洞。就像海绵一样，模板吸收了设计中的所有误差。（因此，这种通用技术称为“吸收”absorption）。“这就好像你试图在角落里放一块地毯，”Sawhney说。“它突然出现在别的地方，你推它，不知怎地，推了20次后，地毯就平了”。 这样就完成了证明。重要的是要注意，与设计工作一样，这个结果至少在理论上可以用来构造这些对象——但仅限于非常大的n。寻找具体的、实际的例子仍然是未来的任务。 最后，这项工作说明了另一种违反直觉的方法，即数学家可以利用随机性的力量来寻找隐藏的结构。“各种意想不到的结构都是可能的，”西澳大利亚大学的数学家Cheryl Praeger说。 “这个证明表明，Keevash的技术比他们原先设计更广泛的背景下有效，”Cameron 说。这意味着其他难题可以通过巧妙地结合随机性randomness和吸收absorption来解决。 当Sawhney在本科生时第一次在Keevash的论文中读到这些技术时，他感觉很神奇。即使现在他对它们有了更深入的了解，“这种印象也不会消失。” 参考资料
让数学 更加 易学易练， 易教易研， 易赏易玩， 易见易得， 易传易及。 欢迎评论、点赞、 在看、收藏、分享， |
|
|
