🔢 mathematics

Optimally Packing a Large Square by Unit Squares

该论文证明了边长为 $x$ 的大正方形可以用单位正方形进行填充，使得产生的浪费空间被限制在 $O(x^{3/5})$ 范围内。

原作者： Rory McClenagan

发布于 2026-02-03

📖 1 分钟阅读🧠 深度阅读

原作者： Rory McClenagan

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

想象一下，你有一个巨大的正方形房间（我们称之为 Room X），以及一大堆完全相同的、一英尺乘一英尺的正方形地板砖。你的目标是用这些瓷砖尽可能多地覆盖地面，且不能让它们重叠。

如果房间正好是 10 英尺宽，你可以完美地铺设 10 行 10 列的瓷砖，没有任何缝隙。但如果房间是 10.3 英尺 宽呢？

问题所在：“天真”的空隙

如果你尝试将瓷砖垂直向上铺设（平行于墙壁），你会遇到一个问题。你可以铺满 10 块完整的瓷砖，但会剩下一条长达整个房间长度的、仅 0.3 英尺宽的窄条空隙。

如果房间有 1,000 英尺宽，这条缝隙就有 1,000 英尺长。
“浪费的空间”（你无法覆盖的空余面积）是非常巨大的。

几十年来，数学家们一直试图寻找一种更好的铺设方式来减少这种浪费空间。之前最好的方法是将瓷砖稍微倾斜放置，这虽然减少了浪费，但浪费仍然相当大。

解决方案：“角度的阶梯”

Rory McClenagan 的这篇论文介绍了一种全新的、巧妙的铺设方法，可以显著减少浪费的空间。作者并没有仅仅倾斜一次瓷砖，而是使用了一种由两个角度组成的“两步舞步”，通过这种方式来抵消误差。

以下是其工作原理的比喻：

第一步：“倾斜堆叠”

想象一下，你不是按直线排列瓷砖，而是将它们建成对角线堆叠。

你让这些堆叠的部分稍微向墙壁倾斜。
因为它们是倾斜的，它们以一种方式组合在一起，在边缘处形成了一种锯齿状的阶梯图案。
这会在房间的最顶端和最底端留下一些微小的三角形间隙，但它非常高效地填充了中间部分。

第二步：“角度修正”（两种算法）

这里是难点所在。如果你在整个房间的过程中都保持同样的倾斜角度，这种“锯齿感”会变得越来越严重，导致末端出现一个巨大的缝隙。

作者的突破在于使用两种不同的填充模式，它们像剪刀或拉链一样协同工作：

第一种模式： 你通过向一个方向倾斜瓷砖来填充房间的一个区域。这会在该区域的顶部产生一个特定的“浪费”角度。
第二种模式： 紧接着，你切换到第二种模式，将瓷砖向相反的方向倾斜（或者仅仅是微调角度），以此来“撤销”第一种模式所造成的错误。

想象一下，你先走上一个坡，然后立即走下一个坡度完全相同的下坡。你会回到原来的高度，在没有上升或下降的情况下完成了这段距离。

通过不断重复交替这两种模式，作者确保了“浪费的空间”（即缝隙）保持极小，并且不会随着房间变大而增长。

结果：一场数学魔术

论文证明，通过使用这种特定的“倾斜堆叠”法结合“角度修正”舞步：

浪费的空间不再与房间的长度成正比。
相反，浪费空间增长得要慢得多。

在数学上，如果房间的边长为 $x$ ，那么浪费的空间大约是 $x^{3/5}$ 。

旧方法： 浪费的空间大约是 $x$ （一条直线）。
新方法： 浪费的空间大约是 $x^{0.6}$ （一条趋于平缓的曲线）。

对于一个巨大的房间来说，这种差异是巨大的。这意味着你可以用单位正方形来覆盖一个巨大的正方形地面，并留下的空余空间比以往的方法要少得多。

总结

这篇论文不仅仅是说“把瓷砖倾斜一下”。它提供了一个精确的配方，告诉你在多大程度上倾斜以及何时切换倾斜方向，从而使误差相互抵消。这使得我们能够比以往更高效地用单位正方形填充一个大的正方形，从而留下比这种方法在数学上可能实现的最小的“浪费”地面空间。

技术摘要：用单位正方形最优地填充大正方形

问题陈述
本文研究了用边长为 1 的单位正方形填充边长为 $x$ 的大正方形 $S(x)$ 的问题，要求单位正方形的内部不相交。目标是最小化浪费的空间 $W(x)$ ，即 $S(x)$ 中未被单位正方形覆盖的面积。虽然当 $x$ 为整数时 $W(x) = 0$ ，但当 $x$ 不是整数时，该问题变得具有挑战性。将单位正方形平行于 $S(x)$ 的边进行朴素排列会产生 $W(x) = O(x\{x\})$ 的浪费空间；如果 $\{x\}$ 远离零，这可以简化为 $O(x)$ 。核心挑战在于，通过允许单位正方形以微小的角度倾斜，确定 $W(x)$ 的最优渐近增长率。

历史背景与先前的界限
本文将其贡献置于一系列已确立的界限时间线中：

下界： Roth 和 Vaughan (1978) 证明了 $W(x) > 10^{-100}\sqrt{x - \lfloor x \rfloor}$ ，从而确立了该界限不可能优于 $\Omega(x^{1/2})$ 。
上界：
- Erdős 和 Graham (1975) 表明 $W(x) = O(x^{7/11})$ 。
- Montgomery 将其改进为 $O(x^{(3-\sqrt{3})/2})$ 。
- Chung 和 Graham (2009) 进一步将界限精炼为 $O(x^{(3+\sqrt{2})/7} \log x)$ 。
- 2020 年，Chung 和 Graham 声称得到了 $O(x^{3/5})$ 的界限，但本文指出该结果包含一个错误，使得在当前工作出现之前，已知的最佳界限一直维持在 2009 年的结果。

方法论
本文提出了一个新的算法来达到 $O(x^{3/5})$ 的界限，并修正了 2020 年声称中的错误。证明过程分为四个截然不同的阶段：

初始平凡填充： 首先使用与边平行的单位正方形对正方形 $S(x)$ 进行平凡填充，留下两个宽度为 $h$ 的狭窄矩形区域。其中一个矩形 $R$ 被选作进一步处理的对象。
带倾角的堆叠： 矩形 $R$ 使用以角度 $\theta$ 倾斜的 $n$ 个单位正方形“堆栈”进行填充。这些堆栈同时接触矩形的垂直壁和倾斜壁。这一过程在末端留下了梯形区域 $T$ 。选择角度 $\theta$ 使得 $\theta \asymp h^{-1/2}$ 。
两阶段梯形填充： 算法的核心在于使用两个互补的子算法填充梯形 $T$ $T$ ：
- 算法 1： 使用长度递减（ $m, m-1, \dots$ ）的近水平和垂直堆栈来填充 $T$ 。该算法引入了一个特定的角度偏移，使倾角从底部的 $\psi$ 变为顶部的 $\phi$ ，其中差值 $\phi - \psi \approx \theta$ 。
- 算法 2： 设计用于“撤销”算法 1 中引入的角度偏移。它从算法 1 结束的地方开始，通过填充长度为 $m+1$ 和 $m$ 的堆栈，来恢复所需的几何结构，以便重新启动算法 1。
- 迭代应用： 这两个算法被前后结合地应用于一个循环中。论文证明了参数（ $\phi, \psi, \theta, m$ ）可以被固定或调整，使得误差项（ $\epsilon, \epsilon'$ ）不会在迭代过程中发生破坏性的累积。
参数优化： 优化梯形 $T$ 的宽度 $w$ 和迭代次数。算法应用约 $\sqrt{h}$ 次以覆盖整个梯形。

关键结果与分析
本文通过对垂直堆栈产生的浪费和梯形区域内产生的浪费进行求和，推导出总浪费空间 $W(x)$ ：

来自堆栈的浪费： 以倾角 $\theta$ 填充 $O(x)$ 个垂直堆栈会产生比例为 $O(x\theta)$ 的浪费。
来自梯形的浪费： 在梯形 $T$ 上迭代应用这两个填充算法会产生 $O(h^{3/4})$ 的总浪费。
优化： 总浪费空间由 $W(x) \ll \frac{x}{\sqrt{h}} + h^{3/4}$ 给出。通过令两项相等（ $x h^{-1/2} \sim h^{3/4}$ ），得到最优选择为 $h \sim x^{4/5}$ 。

将 $h = x^{4/5}$ 代入界限得：
$W(x) = O(x^{3/5})$

意义与主张
本文声称严谨地证明了用单位正方形填充大正方形的浪费空间被限制在 $O(x^{3/5})$ 。这一结果验证了 Chung 和 Graham 在 2020 年提出的说法，此前该说法因错误而被撤回。其重要性在于提供了一个针对该特定渐近界限的修正证明，改进了之前已知的最佳界限 $O(x^{(3+\sqrt{2})/7} \log x)$ 。作者强调，这是通过一种特定的构造性算法实现的，该算法涉及两种通过管理角度差异和误差累积来处理梯形子区域的填充策略之间的相互作用。本文并未提出超出建立这一特定上界之外的其他应用或未来影响。