A note on the partition function of a rectangle

기술 요약: 직사각형의 분할 함수에 관한 노트

문제 정의
본 논문은 $m \times n$ 크기의 직사각형을 정수 측면을 가진 직사각형 블록들의 다중 집합(multiset)으로 분할하는 방법의 수를 세는 직사각형 분할 함수 $p(m, n)$의 점근적 거동을 조사한다. 두 분할은 동일한 블록 유형의 다중 집합으로 구성되어 있다면 동일한 것으로 간주하며, 블록 $a \times b$는 $b \times a$와 구별되지 않는다. 블록들의 기하학적 배치는 개수에 영향을 미치지 않으며, 오직 블록 유형의 다중 집합만이 중요하며, 단 해당 블록들이 $m \times n$ 면적을 이론적으로 채울 수 있어야 한다.

저자들은 다음 두 가지 특정 사례에 집중한다:

1. 정사각형 분할: 두 차원이 모두 무한대로 향하는 $p(n, n)$.
2. 고정 높이 직사각형: 높이가 3으로 고정되고 너비 $n$이 무한대로 향하는 $p(3, n)$.

이 문제들은 $p(1, n)$에 해당하는 고전적인 정수 분할 함수 $p(n)$을 일반화한다. $m$이 고정되고 $n$이 큰 경우 $p(m, n)$의 점근적 거동이 조화수(harmonic numbers)를 포함하는 특정 형태를 따를 것이라는 저자와 Robin Visser의 추측이 있었으나, 정사각형 사례($m=n$)의 정확한 거동은 별개의 점근적 난제를 제시한다.

방법론
본 논문은 해석적 정수론, 생성 함수, 그리고 조합론적 패킹(packing) 구성을 결합하여 사용한다.

• 생성 함수를 통한 상한(Upper Bounds): 저자들은 기하학적 타일링 조건(정의 1.1의 조건 3)을 완화하여 상한을 도출한다. 이들은 블록들이 물리적으로 직사각형을 타일링할 수 있는지 여부와 상관없이 총 면적이 $mn$인 직사각형들의 다중 집합의 수를 고려한다. 이는$\prod (1-x^{ab})^{-r(ab)}$형태의 생성 함수를 사용하여 모델링된다 (여기서$r(ab)$는 면적이$ab$인 직사각형 유형의 수를 센다).

  • $p(n, n)$의 경우, 저자들은 생성 함수를 약수 함수 $d(s)$와 관련된 다중 집합으로부터의 분할과 비교하며, 이를 위해 Berndt, Robles, Zaharescu, Zeindler의 결과를 활용한다.
  • $p(3, n)$의 경우, 높이가 3인 블록을 포함하는 분할과 포함하지 않는 분할로 문제를 분해하고, 생성 함수의 합성(convolution)과 점근 계수를 추출하기 위해 Ingham의 타우베리안 정리(Bringmann Jennings–Shaffer와 Mahlburg에 의해 정교화된 버전)를 사용한다.

• 패킹 구성을 통한 하한(Lower Bounds): 하한을 설정하기 위해 저자들은 특정 타일링을 구축한다.

  • $p(n, n)$의 경우, "색칠된 분할(colored partition)" 접근법과 탐욕적 패킹(greedy packing) 알고리즘을 활용한다. 정사각형을 다양한 높이를 가진 수평 스트립으로 나누고, 제한된 정수 분할으로부터 유도된 직사각형들로 채운다.
  • $p(3, n)$의 경우, "계단식(staircase)" 구성을 사용하여 $3 \times n$ 직사각형을 높이가 3, 2, 1인 수평 스트립으로 나누고, 제한된 부분을 가진 정수 분할로부터 유도된 해당 높이의 직사각형들로 채운다.

• 점근 분석: 증명은 Hardy–Ramanujan의 $p(n)$ 점근 공식, Dedekind eta 함수의 성질, 그리고 조화 합(harmonic sums) 및 약수 함수의 정밀한 추정에 크게 의존한다.

주요 기여 및 결과

1. 정사각형 분할($p(n, n)$)에 대한 점근 공식:
   저자들은 정사각형 분할 함수의 주요 점근 항을 확립한다:
   $$p(n, n) = \exp\left( \left(\frac{\pi}{\sqrt{3}} + o(1)\right) n \sqrt{\log n} \right)$$
   이 결과는 고정된 $m$에 대한 추측된 형태(가 $\sqrt{n}$에 비례함)와 다르다는 점에서 중요하다. 정사각형 사례는 $n\sqrt{\log n}$으로 스케일링된다. 또한 본 논문은 문제의 난이도를 보여주기 위해 두 개의 더 약한 초등적 상한과 하나의 단순한 하한을 제공한다.

2. $p(3, n)$에 대한 점근 공식:
   본 논문은 $3 \times n$ 직사각형에 대한 정확한 점근적 거동을 증명한다:
   $$p(3, n) = \exp\left( \pi \sqrt{\frac{11n}{3}} + O(\log n) \right)$$
   이는 이전의 휴리스틱 논증과 수치적 증거를 확인하며, 기존에 알려진 것보다 더 강력한 오차 항($\exp$ 내부의 $O(\log n)$)과 함께 $m=3$에 대한 추측을 입증한다. $\pi\sqrt{11/3}$ 상수는 크기가 3 이상인 부분들로의 분할과 $3 \times n$ 기하 구조에서 허용되는 특정 블록 유형 사이의 상호작용으로부터 유도된다.

3. 독립적인 상한:
   저자들은 $p(3, n)$에 대해 주 결과보다는 약하지만 다른 해석적 접근 방식을 통해 유도된 독립적인 상한을 제시하여 문제에 대한 대안적인 관점을 제공한다.

4. 일반적인 $m$에 대한 추측:
   $m \ge 4$인 고정된 $m$에 대한 저자들의 추측을 재차 언급한다:
   $$p(m, n) = \exp\left( \pi \sqrt{\frac{2m H_m}{3} n} + o(\sqrt{n}) \right)$$
   여기서 $H_m$은 $m$번째 조화수이다. 저자들은 정사각형 사례($m=n$)가 두 차원이 모두 성장하는 별개의 문제임을 명시한다.

의의 및 주장
본 논문은 작은 $n$에 대한 알려진 값들에도 불구하고 열려 있었던 정사각형 분할 함수 $p(n, n)$의 정밀한 로그 점근적 거동을 해결했다고 주장한다. 저자들은 정사각형 사례가 고정된 높이의 직사각형과 비교하여 근본적으로 다른 점근적 문제를 야기한다는 점을 강조하는데, 이는 두 변의 길이가 모두 무한대로 향하기 때문이다.

$3 \times n$ 사례의 경우, 본 논문은 휴리스틱 논증과 수치적 증거를 엄밀한 오차 항과 함께 처음으로 증명하였다. 저자들은 $m=4$에 대한 구성이 추측과 일치함을 언급하면서도, $m=3$ 및 $m=4$를 위해 사용된 "계단식" 구성이 $m=5$에 대해서는 추측된 지수 항을 산출하지 못한다는 점을 지적하며, 더 높은 고정 높이를 위해서는 다른 기하학적 배치가 필요할 수 있음을 시사한다.

이 연구는 정수 분할 이론을 확장하여 기하학적 분할 문제로 점근적 분석을 연결함으로써, 블록의 순서가 무관한 타일링 문제와 고전적 분할 이론 사이의 간극을 메우는 데 기여한다.