Optimally Packing a Large Square by Unit Squares

기술 요약: 단위 정사각형을 이용한 큰 정사각형의 최적 충전

문제 정의
본 논문은 한 변의 길이가 $x$인 큰 정사각형 $S(x)$를 내부가 서로 겹치지 않는 단위 정사각형들로 채우는 문제를 다룬다. 목표는 단위 정사각형들이 덮지 못하는 면적인 낭비 공간 $W(x)$를 최소화하는 것이다. $x$가 정수일 때는 $W(x) = 0$이지만, $x$가 정수가 아닐 경우 문제는 비자명해진다. 단위 정사각형들을 $S(x)$의 변에 평행하게 정렬하는 단순한 방식은 $W(x) = O(x\{x\})$의 낭비 공간을 발생시키며, 이는 $\{x\}$가 0에서 멀리 떨어져 있을 경우 $O(x)$로 단순화된다. 핵심 과제는 단위 정사각형들을 약간의 각도로 기울여 배치함으로써 $W(x)$의 최적 점근적 성장률을 결정하는 것이다.

역사적 배경 및 기존 경계값
본 논문은 자신의 기여를 확립된 경계값들의 연대기 내에 위치시킨다:

• 하한(Lower Bound): Roth와 Vaughan(1978)은 $W(x) > 10^{-100}\sqrt{x - \lfloor x \rfloor}$임을 증명하여, 이 경계값이 $\Omega(x^{1/2})$보다 나아질 수 없음을 확립했다.
• 상한(Upper Bounds):
  • 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년의 오류가 있는 주장을 바로잡는 것이다. 증명은 네 가지 뚜렷한 단계로 진행된다:

1. 초기 자명한 충전(Initial Trivial Packing): 먼저 $S(x)$를 단위 정사각형들을 변에 평행하게 정렬하여 자명하게 채운 뒤, 폭이 $h$인 두 개의 좁은 직사각형 영역을 남긴다. 이 중 하나의 직사각형 $R$을 추가 처리를 위한 대상으로 선택한다.
2. 경사를 가진 적층(Stacking with Inclination): 직사각형 $R$은 각도 $\theta$로 기울어진 $n$개의 단위 정사각형 "스택(stacks)"을 사용하여 채워진다. 이 스택들은 직사각형의 수직 벽과 기울어진 벽에 모두 접한다. 이 과정은 양 끝에 사다리꼴 영역 $T$를 남긴다. 각도 $\theta$는 $\theta \asymp h^{-1/2}$가 되도록 선택된다.
3. 2단계 사다리꼴 충전(Two-Stage Trapezoidal Packing): 핵심 알고리즘은 두 가지 상보적인 하위 알고리즘을 사용하여 사다리꼴 $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'$)이 반복 과정에서 파괴적으로 누적되지 않음을 입증한다.
4. 매개변수 최적화: 사다리꼴 $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)$를 개선하는 구체적인 구성적 알고리즘을 제공했다는 점에 있다. 저자들은 이것이 각도 불일치와 사다리꼴 하위 영역 내의 오차 누적을 관리하는 두 가지 충전 전략의 상호작용을 포함하는 특정한 알고리즘을 통해 달성되었음을 강조한다. 본 논문은 이 특정 상한을 확립하는 것 외에 추가적인 응용이나 미래의 함의를 제안하지 않는다.