Optimally Packing a Large Square by Unit Squares

技術的要約：大きな正方形への単位正方形の最適充填

問題の定義
本論文は、一辺の長さ $x$ の大きな正方形 $S(x)$ を、内部が互いに重ならない単位正方形で充填する問題を取り扱う。目的は、単位正方形によって覆われていない $S(x)$ の面積として定義される、無駄な領域 $W(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年の主張に含まれていた誤りを修正している。証明は、以下の4つの明確な段階で進行する：

1. 初期の自明な充填: 正方形 $S(x)$ は、まず単位正方形を辺に対して平行に配置して自明に充填され、幅 $h$ の2つの細い長方形領域を残す。そのうちの1つの長方形 $R$ が、さらなる処理のために選択される。
2. 傾斜を用いたスタッキング: 長方形 $R$ は、角度 $\theta$ で傾いた $n$ 個の単位正方形の「スタック（積み重ね）」を用いて充填される。これらのスタックは、長方形の垂直な壁と傾斜した壁の両方に接する。このプロセスにより、端の部分に台形領域 $T$ が残される。角度 $\theta$ は $\theta \asymp h^{-1/2}$ となるように選択される。
3. 2段階の台形充填: アルゴリズムの核心は、2つの相補的なサブアルゴリズムを用いて台形 $T$ を充填することである：
   • アルゴリズム1: 減少していく長さ（$m, m-1, \dots$）を持つ、ほぼ水平および垂直なスタックを用いて $T$ を充填する。このアルゴリズムは、特定の角度シフトを導入し、底部の傾斜 $\psi$ から上部の $\phi$ への変化をもたらす。ここで、差 $\phi - \psi \approx \theta$ である。
   • アルゴリズム2: アルゴリズム1によって導入された角度シフトを「取り消す」ように設計されている。これはアルゴリズム1が終了した地点から始まり、長さ $m+1$ および $m$ のスタックを充填することで、アルゴリズム1を再開するために必要な幾何学的構造を復元する。
   • 反復適用: これら2つのアルゴリズムが、サイクルの中で背中合わせに適用される。本論文は、パラメータ（$\phi, \psi, \theta, m$）を固定または調整することで、誤差項（$\epsilon, \epsilon'$）が反復過程において破壊的に蓄積しないことを示している。
4. パラメータの最適化: 台形 $T$ の幅 $w$ と反復回数が最適化される。台形を覆うために、アルゴリズムは約 $\sqrt{h}$ 回適用される。

主要な結果と分析
本論文は、垂直スタックからの無駄と、台形領域内で発生する無駄を合計することによって、総無駄領域 $W(x)$ を導出する：

• スタックからの無駄: 傾斜 $\theta$ を持つ $O(x)$ 個の垂直スタックを充填することは、$O(x\theta)$ に比例する無駄を生じさせる。
• 台形からの無駄: 台形 $T$ に対するこれら2つの充填アルゴリズムの反復適用は、$O(h^{3/4})$ の総無駄を生じさせる。
• 最適化: 総無駄は $W(x) \ll \frac{x}{\sqrt{h}} + h^{3/4}$ によって抑えられる。これら2つの項を等置することで（$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)$ を改善し、この特定の漸近境界を実現したことにある。著者らは、角度の不一致と台形の部分領域内での誤差の蓄積を管理する、2つの充填戦略の相互作用を含む、具体的な構成的アルゴリズムを通じてこれが達成されたことを強調している。本論文は、この特定の漸近上界を確立することを超えて、さらなる応用や将来的な示唆を提案するものではない。