🔢 mathematics

A Salem-Spencer-Type Construction for Large Subsets of Integer Grids with No Isosceles Right Triangles

本文提出了一种基于高斯整数的改进型 Salem–Spencer 型构造方法，用以证明不包含非退化等腰直角三角形的 $n \times n$ 整数网格的最大子集大小至少为 $\Omega(n^{1.3})$ ，从而缩小了与当前最佳上界之间的差距。

原作者： Gyula Károlyi, Jozsef Solymosi

发布于 2026-07-28

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Gyula Károlyi, Jozsef Solymosi

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你是一名侦探，正试图在一个完全由网格交点构成的巨大、无限的城市中破解一个谜题。这座城市就是数学的世界，具体来说是**组合数学（Combinatorics）**的一个分支，它研究的是如何计数、排列和寻找离散对象的模式。在这座城市里，“街道”仅仅是数字，而“建筑”是两个数字相遇的点，就像地图上的 $(x, y)$ 坐标一样。

这个谜题涉及一个非常具体的规则：你想建造一个尽可能大的“邻里”（即一个点的子集），其中一个特定的形状是被严格禁止的。那个形状是等腰直角三角形。你对这些三角形了如指掌：它们有一个角是完美的 90 度（就像纸张的角），且与其相连的两条边长度完全相等。问题在于，数学家们一直在问：在不经意间构建出这样一个禁止三角形之前，一个邻里的规模最大能达到多少？

这不仅仅是一个几何游戏；它是一个深刻的谜题，连接着数字的行为方式、数据加密技术，甚至是人类对宇宙结构的理解。几十年来，数学家们知道答案介于“非常大”和“几乎占据整个城市”之间，但这种最小可能的“大邻里”与最大的可能邻里之间的差距是巨大的。这就像你知道宝箱就在沙漠中的某个地方，但不知道它究竟是埋在了一粒沙子下，还是在一座金山之下。

论文的大发现：一种构建“无三角形”城市的新方法

在这篇论文中，两位数学家 Gyula Károlyi 和 József Solymosi 构建了一个巨大的新邻里，其规模比人们之前认为的要大得多。他们成功地在网格中构建了一个避免了等腰直角三角形的点的子集，并且他们的构造如此之大，以至于证明了这种邻里的规模增长率大约为 $n^{1.3}$ （其中 $n$ 是网格的大小）。

为了理解他们是如何做到的，想象你正在尝试用积木搭建一座塔，但你有一个严格的规则：你不能以特定的“坏形状”来堆叠积木。在过去，数学家们试图通过挑选那些本身完全安全的积木来建造这些塔。但 Károlyi 和 Solymosi 意识到他们可以做得更聪明。他们使用了一种被称为**“剥离”（peeling）**的技术，这就像是一场 Jenga（叠叠乐）游戏，只要你可以按照特定的顺序一个接一个地移除积木，即使你的塔稍微有些摇晃也是可以接受的，直到整个结构变得安全。

魔法成分

作者使用了几个聪明的技巧来实现这一目标：

高斯整数（“魔法网格”）： 他们没有使用普通的数字，而是使用了一种被称为**高斯整数（Gaussian integers）**的特殊数字。你可以将它们看作是网格上的点，每个点都有一个 $x$ 坐标和一个 $y$ 坐标，但它们被视为一个单一的魔法数字。这使得他们能够以普通数字无法实现的方式旋转和移动他们的“积木”。
“无进位”字母表： 当你进行加法运算时，有时会产生“进位”（比如 $9 + 1 = 10$ ，其中 1 向前进位）。作者发现了一组特殊的“数字”（一组点集），如果用它们来构成一个三角形，数学运算永远不会“进位”到下一个层级。这保持了局部规则的简单性。
剥离顺序（“秘密武器”）： 这是最具有原创性的部分。他们发现了一组包含 281 个点，如果同时观察这些点，它们会包含三角形。然而，他们发现了一种移除这些点的特定顺序。如果你移除第一个点，剩下的点与该点作为顶点时就不会再形成三角形。接着你移除下一个，以此类推。当你完成时，剩余的集合就是完美安全的。这就像一个房间里坐满了人，大家手拉手围成一个圈，但如果你要求他们按特定顺序离开，这个圆圈会在任何人受伤之前就瓦解。

结果：巨大的飞跃

利用一个名为 AlphaEvolve 的强大 AI 工具（它帮助他们在数百万种可能性中搜索，从而找到了完美的排列方式），他们找到了一个包含 281 个点的“剥离顺序”。

当他们将这种方法应用于大小为 $n$ 的网格时，他们证明了可以找到一个大小至少为 $n^{1.3178...}$ 的无三角形子集。

为了让你有直观的感受：

在此之前，已知的最佳下界要小得多（大约为 $n^{1.05}$ ）。
已知的最佳上界（即理论上的最大极限）大约是 $n^2$ 除以某些对数因子。
他们的结果 $n^{1.3}$ 填补了显著的空白，表明这些无三角形的邻里比之前怀疑的要大得多。

他们并没有做的事情

需要注意的是，这篇论文并未声称其结论是绝对的。他们并没有证明 $n^{1.3}$ 是可能的最大尺寸。他们也没有找到那个在数学上尽可能大的“完美”邻里。他们也没有证明 281 是他们这种特定方法中所能使用的最大点数；他们只是找到了一个非常好的数值。

论文明确指出，在他们的全新下界（ $n^{1.3}$ ）与上界（ $n^2$ ）之间仍然存在着“巨大的差距”。这个谜题尚未完全解决，但他们确实比以往任何人都更深入地找到了这块拼图的一大块。

总结

这篇论文是传统数学逻辑与现代 AI 搜索相结合的胜利。通过将数字视为网格上的点，寻找一个特殊的“无进位”区域，并使用一种巧妙的“剥离”策略来逐一移除危险的点，作者展示了我们可以构建出比我们想象中大得多的“无三角形”城市。这是一个生动的例子，说明了全新的视角——不再将问题视为一个静态的墙壁，而是一个动态的移除过程——如何能开启数字世界的新可能。

技术摘要：一种用于构建包含大规模整数网格中无等腰直角三角形子集的 Salem–Spencer 型构造法

问题陈述
本文研究了确定整数网格 $\{0, 1, \dots, n-1\}^2$ 中不包含非退化等腰直角三角形（IRT）的最大子集大小 $F(n)$ 的问题。虽然已知该量的上界为 $F(n) \ll n^2 / (\log n)^{1+c}$ （通过对 Bloom–Sisask 方法的扩展得出），但已知的最佳下界在历史上一直较弱。作者旨在利用一种经过修改的、适用于高斯整数的 Salem–Spencer 型构造法，建立一个超线性的下界，即 $F(n) = \Omega(n^\alpha)$ ，其中 $\alpha > 1$ 。

方法论
作者利用高斯整数 $\mathbb{Z}[i]$ 进行基于数字的构造，将格点 $(x, y)$ 识别为 $x + iy$。该构造依赖于四个主要部分：

IRT 的线性编码： 一个顶点为 $a, b, c \in \mathbb{Z}[i]$ 的等腰直角三角形（其中 $b$ 是直角顶点）由线性方程 $a + ic = (1+i)b $编码。退化解对应于$ a=b=c$。
IRT 无进位字母表： 作者定义了一个字母表 $P \subset \mathbb{Z}[i]$ ，它是关于非平凡高斯整数 $\beta$ 的部分剩余系。若 $P$ 是“IRT 无进位”的，则意味着方程 $a + ic = (1+i)b $在模$ \beta$ 下成立，当且仅当它在精确意义下成立（即不会发生导致产生假阳性三角形的“进位”）。
IRT 剥离序（Peeling Orders）： 与经典的 Salem–Spencer 构造不同（后者要求字母表本身不包含禁忌构型），这种方法允许字母表 $P$ 包含 IRT。相反， $P$ 被赋予了一个“剥离序” $p_1, \dots, p_q$ 。这是一个序列，使得对于任何后缀 $R_t = \{p_t, \dots, p_q\}$ ，方程 $a + ic = (1+i)p_t$ 在 $a, c \in R_t$ 下的唯一解是平凡解 $a=c=p_t$ 。这一性质确保了在通过数字展开构造大集合时，任何潜在的 IRT 都可以通过从最高有效位开始“剥离”数字来消除。
组合类（Composition Classes）： 最终的集合是通过选取所有在字母表 $P$ 上具有特定“组合”（即每个数字的出现频率计数）的长度为 $m$ 的“词”来构造的。通过限制在一个大的组合类中，剥离序会传播到所有数字位置，从而确保生成的集合是无 IRT 的。

核心贡献与结果

通用定理 (Theorem 2.6)： 作者证明，如果存在一个基数为 $\beta$ 且具有有效剥离序的规模为 $q$ 的 IRT 无进位字母表 $P$ ，则 $F(n) \gg \frac{n^{\log q / \log |\beta|}}{(\log n)^{(q-1)/2}}$ 。
小型示例： 利用 $\beta = 2+2i$ 和 $P=\{0, 1, i\}$ ，作者展示了一个产生指数 $\alpha \approx 1.0566$ 的构造。
优化构造 (Theorem 4.2)： 主要结果利用基数 $\beta = 51 + 51i$ $β = 51 + 51 i$ 以及从基本域中心位置的菱形区域导出的无进位区域 $C$ $C$ 。通过使用 AI 代理 AlphaEvolve，作者发现了一个包含 281 个不同点的特定排序，该排序构成了一个有效的 IRT 剥离序。
- 这得出了界限：
  $F(n) \gg \frac{n^\alpha}{(\log n)^{140}}$
  其中 $\alpha = \frac{\log 281}{\log |51+51i|} \approx 1.317865$ 。
- 这确立了 $F(n) = \Omega(n^{1.3})$ 。

重要性与声明
本文声称通过提供第一个指数显著大于 1 的超线性下界，填补了 $F(n)$ 已知上界与下界之间的差距。其重要性在于：

新颖技术： “剥离序”的引入允许字母表本身不具备 IRT 自由性，从而将搜索空间从以往的方法扩展到了更大的数字集。
计算发现： 使用 AlphaEvolve 寻找特定的 281 点证书，展示了一种混合方法，即 AI 辅助发现组合结构，而数学有效性由确定性证书进行严格验证（附录 B）。
声明的审慎性： 作者明确指出，其结果并未证明 281 是所选基数下可能的最大字母表大小，也未证明该基数是全局最优的。“优化”一词严格指代计算搜索的目标。论文将几何论证（无进位区域的存在性）与有限搜索（寻找剥离序）分离，使得结果可以被独立检查。

本研究并未提出新的应用或不同于建议扩展至不同高斯基数、非对称区域和块数字的未来实验方向。

论文的大发现：一种构建“无三角形”城市的新方法

魔法成分

结果：巨大的飞跃

他们并没有做的事情

总结

技术摘要：一种用于构建包含大规模整数网格中无等腰直角三角形子集的 Salem–Spencer 型构造法

类似论文