Square Packing

1. 개요

2. 문제 정의

2.1. 정의

2.2. 기본 성질

2.3. 기울이면 이득인 이유

2.4. 값의 모양

3. 용어

• 상한과 하한: [math(s(n) \le a)]를 보이면 [math(a)]를 상한, [math(s(n) \ge b)]를 보이면 [math(b)]를 하한이라 한다. 상한은 실제로 들어가는 배치 하나를 보이면 되지만, 하한은 '어떤 배치도 그보다 작은 정사각형에는 들어가지 않는다'를 증명해야 한다. 두 값이 같아지면 정확한 값이 정해진다.
• 최선 배치와 최적 배치: 최선 배치(best known packing)는 지금까지 찾은 배치 가운데 가장 작은 정사각형을 쓰는 배치이고, 최적 배치는 가능한 모든 배치 가운데 가장 작은 정사각형을 쓰는 배치다. 최선 배치가 최적임을 증명해야 [math(s(n))]이 정해진다.
• 바둑판 배치: 정사각형을 하나도 기울이지 않고 가로세로로 줄 맞춰 늘어놓은 배치다. 한 변이 [math(k)]인 정사각형에 [math(k^2)]개까지 들어간다. 아래 표에서 최선 배치가 정수라는 것은 바둑판 배치(에서 몇 개를 뺀 것)를 아직 아무도 이기지 못했다는 뜻이다.
• L자 줄과 원시 배치: 배치의 두 변을 따라 단위 정사각형을 한 줄씩 둘러 크기를 1 키운 것이 L자 줄을 덧붙인 배치이고, 이런 줄을 떼어 낼 수 없는 배치가 원시 배치다(위 '기본 성질').
• 대각선 띠: 45° 기울인 정사각형을 대각선 방향으로 이어 놓은 줄이다. 너비 1인 띠는 Frits Göbel이, 너비 2인 띠는 Charles Cottingham이 처음 썼고, 너비 3과 4인 띠도 쓰인다[DS7].
• 강성 배치: 큰 정사각형의 크기를 바꾸지 않고서는 정사각형들을 연속해서 움직여 다른 배치로 바꿀 수 없는 배치다. 조금도 흔들리지 않게 꽉 끼인 배치라고 보면 된다. 최선 배치 가운데 강성 배치는 드물다. 기록표에 따르면 324 이하에서 최선 배치 자체가 강성인 것은 바둑판으로 꽉 찬 [math(n=k^2)]을 빼면 [math(n=5, 11, 28, 40)]뿐이고, [math(n=52, 149, 296)]에는 최선 배치와 크기가 같은 강성 배치가 따로 있다. [math(n=28)]에는 이와 별도로 2023년에 찾은 반쯤 강성인 다른 배치(한 변 [math(3+2\sqrt{2})])도 있다. [math(n=18, 50, 200, 203, 233, 265, 299)]에도 강성 배치가 있지만 최선 배치보다 크다[3].
• 다른 배치와 재배열: 같은 크기의 정사각형에 들어가지만 연속해서 움직여서는 서로 바꿀 수 없는 배치를 다른 배치(alternative)라 하고, 연속해서 움직여 바꿀 수 있으면 재배열(rearrangement)이라 한다. 기록표는 같은 크기의 다른 배치도 따로 모아 보여 준다.
• 국소 최적: 배치를 조금씩 움직여서는 큰 정사각형을 더 줄일 수 없는 상태다. 국소 최적인 배치라도 전혀 다른 모양의 배치가 더 작을 수 있으므로 최적이라는 보장은 없다.
• 해석적 최적화: 컴퓨터 탐색으로 찾은 배치에서 어느 꼭짓점이 어느 변에 닿는지를 읽어 방정식으로 적고, 이를 정확히 풀어 국소 최적점까지 줄이는 작업이다. 기록표에서는 'Optimized'로 적는다.
• 인증서: 결과를 누구나 프로그램으로 다시 검사할 수 있게 적어 둔 자료다. 상한 인증서는 큰 정사각형의 변과 모든 정사각형의 중심·각도를 담고, 하한 인증서는 큰 정사각형 안에 깔 무게의 위치와 크기를 담는다. 좌표를 정확한 유리수로 적으면 반올림 오차 없이 검사할 수 있다. 이때 각도 [math(\theta)]는 [math(t=\tan\frac{\theta}{2})]로 적고 방향을 [math(\left(\frac{1-t^2}{1+t^2}, \frac{2t}{1+t^2}\right))]로 계산하는데, 이 벡터의 길이는 정확히 1이므로 유리수만으로 크기가 정확히 1인 정사각형을 나타낼 수 있다[MS].
• 피할 수 없는 점 집합: 큰 정사각형 안에 찍은 점들로, 단위 정사각형을 어디에 어떻게 놓아도 그중 적어도 하나를 품게 되는 것이다. 아래 '최적임을 증명하는 방법' 참고.
• 구간 산술: 수 대신 그 수가 들어 있는 구간을 들고 계산해, 컴퓨터의 반올림 오차까지 엄밀하게 다루는 계산법이다. 컴퓨터 보조 증명에 널리 쓰인다.
• 증명 보조기: 증명의 각 단계를 컴퓨터가 검사하는 프로그램이다. 이 분야에서는 주로 Lean이 쓰인다. Lean은 Leonardo de Moura가 Microsoft Research에서 개발해 2013년 처음 내놓은 오픈 소스 증명 보조기이고, 2021년 새로 만든 Lean 4가 나왔다[5].
• 대수적 수와 차수: 정수 계수 다항식의 근이 되는 수를 대수적 수라 하고, 그런 다항식 가운데 차수가 가장 낮은 것의 차수를 그 수의 차수라 한다. 예를 들어 [math(2+\frac{\sqrt{2}}{2})]는 [math(2x^2-8x+7=0)]의 근이고 유리수가 아니므로 차수가 2다. 기록표에는 변의 길이가 수백 차 다항식의 근으로 적힌 배치도 있다.
• 분리축 정리: 볼록한 두 도형의 내부가 겹치지 않으면 둘 사이를 가르는 직선이 있다는 정리다. 두 도형이 다각형이면 각 변에 수직인 방향으로만 비춰 보면 충분하므로, 정사각형 두 개가 겹치는지는 방향 네 개만 보면 알 수 있다. 배치를 검사하거나 다듬을 때 바탕이 되는 사실이다.
• 선형계획법: 일차 부등식으로 된 조건 아래에서 일차식의 최댓값이나 최솟값을 구하는 방법이다. 하한 인증서의 무게를 정하거나, 정사각형의 각도를 고정한 채 배치를 다듬는 데 쓰인다.
• 분지(basin): 같은 다듬기 프로그램을 여러 곳에서 출발시켰을 때, 같은 국소 최적 배치에 도착하는 출발점들의 모임이다. 새 배치를 찾는 탐색은 다른 분지로 건너가는 일이고, 다듬기는 지금 분지의 바닥까지 내려가는 일이라 할 수 있다[MS].
• 헐거운 정사각형(rattler): 배치 안에서 다른 정사각형이나 벽에 눌리지 않아 조금 움직일 수 있는 정사각형이다. 배치를 다듬을 때는 이런 정사각형을 따로 다룬다.
• KKT 조건: 부등식 조건이 있는 최적화에서 최적점이 만족해야 하는 조건이다. 이 문제에서는 큰 정사각형을 줄이려는 힘과 정사각형들이 맞닿은 곳에서 받는 힘이 균형을 이룬다는 뜻으로 읽을 수 있다. 다만 이 조건을 만족한다고 해서 최솟값이라는 보장은 없다[MS].

4. 역사

4.1. 1970년대: 문제의 출발

4.2. 1980~2000년대: 기록표와 첫 증명들

4.3. 2010년대 이후

5. 알려진 값

#!if (문단 == null) == (앵커 == null)
를

#!if 문단 != null & 앵커 == null
의 [[Square Packing/알려진 값#s-|]]번 문단을

#!if 문단 == null & 앵커 != null
{{{#!if 문서명 = 문서명 != null ? 문서명 : calleeTitle
의 [[Square Packing/알려진 값#|]] 부분을}}}

6. 좋은 배치를 찾는 방법

6.1. 왜 어려운가

6.2. 직접 설계하기

6.3. 배치 고쳐 쓰기

6.4. 무작위 탐색

6.5. 다듬기

6.6. 검증

7. 최적임을 증명하는 방법

7.1. 무게(측도) 논법

7.2. 예: 정사각형 5개와 8개

7.3. 조사 논문의 증명들

7.3.1. 증명의 틀

• 1단계: 한 변이 [math(k)]인 정사각형 [math(S)] 안에 점 [math(n-1)]개로 된 집합 [math(P)]를 잡는다. 이때 [math(S)] 안의 단위 정사각형은 어디에 어떻게 놓든 [math(P)]의 점을 적어도 하나 품어야 하며, 점이 정사각형의 경계 위에 있어도 품은 것으로 친다. 이런 [math(P)]가 [math(S)]의 피할 수 없는 점 집합이다.
• 2단계: 작은 양수 [math(\varepsilon)]을 잡아 [math(S)]와 [math(P)]를 함께 [math(1-\frac{\varepsilon}{k})]배로 줄인다. 그러면 한 변이 [math(k-\varepsilon)]인 정사각형 [math(S')]과 그 안의 점 [math(n-1)]개로 된 집합 [math(P')]이 생긴다.
• 3단계: 이제 [math(S')] 안의 단위 정사각형 [math(u)]는 [math(P')]의 점을 경계가 아닌 안쪽에 품는다. [math(u)]를 [math(S')]과 함께 [math(\frac{k}{k-\varepsilon})]배로 늘리면 [math(S)] 안에 한 변이 1보다 조금 긴 정사각형이 생긴다. 그 안에 중심과 기울기가 같은 단위 정사각형을 그리면 1단계에 따라 [math(P)]의 점을 하나 품는데, 이 단위 정사각형은 늘린 정사각형의 안쪽에 들어 있다. 그래서 다시 줄이면 그 점에 해당하는 [math(P')]의 점이 [math(u)]의 안쪽에 온다.
• 4단계: 단위 정사각형들은 내부가 서로 겹치지 않으므로, [math(P')]의 점 하나를 안쪽에 품는 정사각형은 많아야 하나다. [math(S')]에 넣은 정사각형은 저마다 [math(P')]의 점을 하나씩 따로 차지하므로 [math(n-1)]개까지만 들어간다. 따라서 [math(s(n)>k-\varepsilon)]이다.
• 5단계: [math(\varepsilon)]은 얼마든지 작게 잡을 수 있으므로 [math(s(n) \ge k)]다.

7.3.2. 보조정리

• 보조정리 1: 제1사분면 안에 놓인 단위 정사각형의 중심이 [math([0,1]^2)]에 있으면, 그 정사각형은 점 [math((1, 1))]을 품는다. 논문은 정사각형이 두 축에 모두 닿은 경우만 보이면 충분하다고 하고 이 경우를 계산한다(그림 17). 정사각형이 [math(\theta)]만큼 기울어 두 축에 닿아 있으면 두 꼭짓점이 [math((\sin\theta, 0))]과 [math((0, \cos\theta))]에 있고, 원점에서 먼 쪽 변은 나머지 두 꼭짓점 [math((\cos\theta, \cos\theta+\sin\theta))]와 [math((\cos\theta+\sin\theta, \sin\theta))]를 잇는다. 이 변이 직선 [math(x=1)]과 만나는 높이는 [math(\frac{(1-\sin\theta)(1-\cos\theta)+\sin\theta}{\sin\theta})]인데, [math((1-\sin\theta)(1-\cos\theta))]가 0 이상이므로 이 높이는 1 이상이다. 곧 점 [math((1, 1))]은 먼 쪽 변을 넘지 않아 정사각형 안에 있다. 이 보조정리에서 바로 따라 나오는 사실도 있다. [math(a, b \le 1)]일 때 제1사분면 안에 놓이고 중심이 [math([0,a] \times [0,b])]에 있는 단위 정사각형을 [math((1-a, 1-b))]만큼 옮기면, 여전히 제1사분면 안에 있고 중심은 [math([0,1]^2)]에 들어가므로 원래 정사각형은 점 [math((a, b))]를 품는다. 귀퉁이 쪽 점이 한쪽 벽에서 0.9만큼 떨어진 아래 정리 3과 정리 6에서 이 사실을 쓸 수 있다.
• 보조정리 2: [math(0<x \le 1)], [math(0<y \le 1)], [math(x+2y<2\sqrt{2})]라 하자. 제1사분면 안에 놓인 단위 정사각형의 중심이 직사각형 [math([1, 1+x] \times [0, y])]에 있으면, 그 정사각형은 점 [math((1, y))]와 [math((1+x, y))] 가운데 하나를 품는다. 벽에서 높이 [math(y)]인 곳에 간격 [math(x)]로 점 두 개를 찍어 두면, 벽과 두 점 사이에 중심을 둔 정사각형은 두 점을 모두 피할 수 없다는 뜻이다. 논문은 중심이 이 직사각형에 있으면서 두 점을 모두 경계 위에 둔 단위 정사각형이 [math(x)]축에 닿거나 그 아래로 내려간다는 것을 보이면 된다고 한다(그림 18). 두 점이 정사각형의 같은 변 위에 있으면 그 변이 가로로 놓이므로 정사각형은 축에 나란하고, 중심이 두 점보다 낮으니 그 변은 윗변이어서 아랫변의 높이가 [math(y-1 \le 0)]이다. 두 점이 서로 다른 변 위에 있고 정사각형이 [math(\theta)]만큼 기울어 있으면, 가장 낮은 꼭짓점의 높이는 [math(y-f(\theta))]이고 [math(f(\theta)=\cos\theta+\sin\theta-x\sin\theta\cos\theta)]다. [math(f'(\theta)=(\cos\theta-\sin\theta)\{1-x(\cos\theta+\sin\theta)\})]이므로 극값은 [math(\theta=45^\circ)]이거나 [math(\cos\theta+\sin\theta=\frac{1}{x})]인 곳에서 생긴다. 이 값들을 양 끝값과 비교하면, [math(x+2y<2\sqrt{2})]이고 [math(y \le 1)]인 한 가장 낮은 꼭짓점은 [math(x)]축보다 높을 수 없다. 조건에 나오는 [math(2\sqrt{2})]는 [math(\theta=45^\circ)]일 때의 값 [math(f(45^\circ)=\sqrt{2}-\frac{x}{2})]에서 온다.
• 보조정리 3: 단위 정사각형 [math(u)]의 중심이 세 변의 길이가 모두 1 이하인 삼각형 [math(ABC)] 안에 있으면, [math(u)]는 [math(A)], [math(B)], [math(C)] 가운데 하나를 품는다. [math(u)]의 두 대각선을 길게 늘이면 평면이 네 영역으로 나뉘고, 영역마다 [math(u)]의 변 하나를 마주 본다(그림 19). 세 꼭짓점이 한 대각선의 같은 쪽에 몰려 있으면 삼각형이 [math(u)]의 중심을 품을 수 없으므로, 서로 마주 보는 두 영역에 꼭짓점이 하나씩 있다. 이 두 꼭짓점이 모두 [math(u)] 밖에 있다면 각각 [math(u)]의 마주 보는 두 변 바깥에 있게 되어, 둘 사이의 거리가 두 변 사이의 거리인 1보다 크다. 그런데 삼각형의 변은 1 이하이므로 둘 가운데 하나는 [math(u)]에 들어 있다.
• 보조정리 4: 단위 정사각형 [math(u)]의 중심이 직사각형 [math(R=[0,1] \times [0, 0.4])] 안에 있으면, [math(u)]는 [math(R)]의 꼭짓점 가운데 하나를 품는다. 이 직사각형은 대각선의 길이가 [math(\sqrt{1.16})] = 1.0770…으로 1보다 길어서, 대각선으로 잘라 보조정리 3을 쓸 수는 없다. 꼭짓점을 [math(A=(0, 0))], [math(B=(0, 0.4))], [math(C=(1, 0))], [math(D=(1, 0.4))]라 하면, 논문은 중심이 [math(R)] 안에 있으면서 [math(A)]와 [math(B)]를 경계 위에 둔 [math(u)]가 [math(C)]나 [math(D)]를 품는다는 것만 보이면 된다고 한다(그림 20). [math(A)]와 [math(B)]가 [math(u)]의 같은 변 위에 있으면 [math(u)]는 축에 나란하게 놓여 [math(R)] 전체를 덮으므로 [math(C)]와 [math(D)]를 모두 품는다. 그렇지 않을 때는 [math(u)]의 기울기 [math(\theta)]가 45°이면 [math(C)]와 [math(D)]를 모두 품고, 45°보다 작으면 [math(D)]를, 크면 [math(C)]를 품는다. 이 마지막 부분은 그림을 보면 쉽게 알 수 있다고만 적혀 있다.
• 보조정리 5: 중심이 직선 [math(y=1)]보다 아래에 있고 [math(x)]축 아래로 내려가지 않는 단위 정사각형은, 직선 [math(y=1)]과 길이가 [math(2\sqrt{2}-2)] = 0.8284… 이상인 선분에서 겹친다. 중심이 직선보다 아래에 있으므로 직선보다 위로 올라간 꼭짓점은 많아야 2개다. 2개이면 직선이 정사각형의 마주 보는 두 변을 가로지르므로 겹친 선분의 길이가 1 이상이다. 하나도 없으면 정사각형이 높이 1인 띠 [math(0 \le y \le 1)] 안에 들어가야 하는데, 그런 단위 정사각형은 축에 나란한 것뿐이므로 윗변이 직선과 겹쳐 길이가 꼭 1이다. 꼭짓점 하나만 위로 튀어나온 경우에는 정사각형을 아래로 내릴수록 겹친 선분이 짧아지므로, 꼭짓점 하나가 [math(x)]축에 닿을 때까지 내린 경우만 보면 된다(그림 21). 이때 기울기를 [math(\theta)]라 하면 튀어나온 높이가 [math(\sin\theta+\cos\theta-1)]이고, 겹친 선분의 길이는 [math(D=\frac{\sin\theta+\cos\theta-1}{\sin\theta\cos\theta})]다. [math(\frac{dD}{d\theta}=\frac{(\sin\theta-\cos\theta)(1-\cos\theta)(1-\sin\theta)}{\sin^2\theta\cos^2\theta})]는 [math(\theta)]가 45°보다 작을 때 음수, 클 때 양수이므로 [math(D)]는 [math(\theta=45^\circ)]에서 가장 작고, 그 값이 [math(2\sqrt{2}-2)]다.
• 보조정리 6: 중심이 [math([0,1]^2)]에 있고, 점 [math((0, 1))]과 [math((1, 1))]을 둘 다 품지 않으며, [math(x)]축 아래로 내려가지 않는 단위 정사각형은 [math(\frac{1}{2} \le y \le 1)]인 점 [math((0, y))]를 하나 품고, [math(\frac{1}{2} \le y \le 1)]인 점 [math((1, y))]도 하나 품는다. 곧 이 정사각형은 직선 [math(x=0)]과 [math(x=1)]을 모두 높이 [math(\frac{1}{2})]과 1 사이에서 만난다. 정사각형을 [math(x)]축에 닿을 때까지 내리면 직선 [math(x=0)]과 만나는 부분도 내려가고, 점 [math((1, 1))]에 닿을 때까지 오른쪽으로 밀면 그 부분이 줄어든다. 그래서 [math(x)]축과 점 [math((1, 1))]에 모두 닿은 정사각형만 보면 된다(그림 22). 이 정사각형이 [math(\theta)]만큼 기울어 있으면 직선 [math(x=0)]과 만나는 가장 높은 점의 높이는 [math(D=\frac{\cos^3\theta+\sin\theta(1-\cos\theta)(1-\sin\theta)}{\cos^2\theta})]다. [math(\frac{dD}{d\theta}=\frac{(1-\cos\theta-\sin\theta)(1-\sin\theta)}{\cos^3\theta})]가 음수이므로 [math(D)]는 [math(\theta)]가 커질수록 줄고, 가장 작은 값은 [math(\theta)]가 90°에 다가갈 때의 극한이다. 로피탈의 정리로 이 극한을 구하면 [math(\frac{1}{2})]이다. 점 [math((1, y))] 쪽은 좌우 대칭으로 같다.
• 보조정리 7: 보조정리 6과 조건이 같은 단위 정사각형은 점 [math(\left(0, \sqrt{2}-\frac{1}{2}\right))]과 [math(\left(1, \sqrt{2}-\frac{1}{2}\right))] 가운데 하나를 품는다. 여기서 [math(\sqrt{2}-\frac{1}{2})] = 0.9142…다. 논문은 중심의 높이로 경우를 나눈다. 중심의 높이가 [math(\sqrt{2}-\frac{1}{2})] 이하이면 보조정리 2를 간격 1, 높이 [math(\sqrt{2}-\frac{1}{2})]로 써서 두 점 가운데 하나를 품게 한다. 중심이 그보다 높으면, 중심은 이 두 점과 [math((0, 1))], [math((1, 1))]을 꼭짓점으로 하는 세로 [math(\frac{3}{2}-\sqrt{2})] = 0.0857…짜리 납작한 직사각형 안에 있다. 논문은 여기에 보조정리 4를 써서, 정사각형이 이 직사각형의 꼭짓점 가운데 하나를 품는데 위쪽 두 꼭짓점은 품지 않으므로 아래쪽 두 점 가운데 하나를 품는다고 결론짓는다. 앞의 경우에는 [math(x=1)], [math(y=\sqrt{2}-\frac{1}{2})]이어서 [math(x+2y=2\sqrt{2})]이므로, 보조정리 2의 조건 [math(x+2y<2\sqrt{2})]에서 등호인 경계의 경우다. 논문은 이 점을 따로 짚지 않았다(보조정리 2의 계산에서 등호는 정사각형이 45°로 기울어 [math(x)]축에 꼭 닿을 때만 생긴다).

7.3.3. 점 집합 하나로 끝나는 증명

• 정리 1: [math(s(2)=s(3)=2)]. 위 '무게(측도) 논법'에서 본 증명이다. 한 변이 2인 정사각형 [math([0,2]^2)]에서는 중심 하나만 찍은 [math(P=\{(1, 1)\})]로 충분하다(그림 23). 큰 정사각형을 한 변이 1인 네 칸으로 나누면, 어느 칸에서나 점 [math((1, 1))]은 큰 정사각형의 귀퉁이와 마주 보는 꼭짓점이어서 보조정리 1을 그대로 쓸 수 있다. 점이 하나이므로 [math(s(2) \ge 2)]이고, [math(s(3) \ge s(2))]이므로 [math(s(3) \ge 2)]도 나온다.
• 정리 2: [math(s(5)=2+\frac{\sqrt{2}}{2})]. 위 '예: 정사각형 5개와 8개'에서 본 네 점과 보조정리 1, 2, 3으로 증명한다(그림 24). 본문은 귀퉁이 쪽, 벽 가까이, 삼각형 안이라는 말로만 영역을 가리키지만, 좌표를 보면 그 뜻이 분명하다. 네 점의 좌표는 1과 [math(1+\frac{\sqrt{2}}{2})]뿐이므로 이 두 값에서 가로세로로 선을 그으면 큰 정사각형이 9칸으로 나뉜다. 귀퉁이의 4칸은 한 변이 1인 정사각형이어서 보조정리 1이 그대로 맞는다. 벽 쪽의 4칸은 두 변이 [math(\frac{\sqrt{2}}{2})]와 1인 직사각형인데, 보조정리 2에 [math(x=\frac{\sqrt{2}}{2})], [math(y=1)]을 넣으면 [math(x+2y=2+\frac{\sqrt{2}}{2})] = 2.7071…이 [math(2\sqrt{2})] = 2.8284…보다 작아 조건이 맞는다. 한가운데 칸은 한 변이 [math(\frac{\sqrt{2}}{2})]인 정사각형이어서 대각선의 길이가 꼭 1이므로, 대각선으로 자른 삼각형 두 개에 보조정리 3을 쓸 수 있다.
• 정리 3: [math(s(8)=3)]. 한 변이 3인 정사각형 [math([0,3]^2)]에서, 가로줄 [math(y=1)]과 [math(y=2)] 위에 [math(x=0.9, 1.5, 2.1)]인 점을 세 개씩 찍고 한가운데 점 [math((1.5, 1.5))]를 더한 7개가 피할 수 없는 점 집합이다(그림 25). 본문은 보조정리 1, 2, 3을 쓴다고만 적는다. 귀퉁이 쪽 네 점은 옆 벽에서 0.9, 위나 아래 벽에서 1만큼 떨어져 있어, 보조정리 1에서 따라 나오는 사실을 [math(a=0.9)], [math(b=1)]로 쓸 수 있는 자리다. 벽을 따라 이웃한 점 사이의 간격은 위아래 벽 쪽에서 0.6, 옆 벽 쪽에서 1이며, 보조정리 2의 [math(x+2y)]를 계산하면 각각 2.6과 2.8로 [math(2\sqrt{2})]보다 작다.
• 정리 4: [math(s(15)=4)]. [math([0,4]^2)]에서 가로줄 [math(y=1)]과 [math(y=3)] 위의 [math(x=1, 1.6, 2.4, 3)]인 점 8개와 가로줄 [math(y=1.8)]과 [math(y=2.2)] 위의 [math(x=1, 2, 3)]인 점 6개, 모두 14개가 피할 수 없는 점 집합이다(그림 26). 이번에는 보조정리 1~4를 모두 쓴다. 귀퉁이 쪽 네 점 [math((1, 1))], [math((3, 1))], [math((1, 3))], [math((3, 3))]은 두 벽에서 1씩 떨어져 있어 보조정리 1의 점과 같은 자리다. 세로 간격이 0.4인 가운데 두 줄의 점은 [math((1, 1.8))], [math((2, 1.8))], [math((1, 2.2))], [math((2, 2.2))]처럼 가로 1, 세로 0.4인 직사각형을 이루는데, 보조정리 4의 직사각형이 바로 이 꼴이다. 벽을 따라 놓인 점의 간격은 0.4, 0.6, 0.8이고, 가장 넓은 0.8에서도 보조정리 2의 [math(x+2y)]가 2.8이어서 [math(2\sqrt{2})]보다 작다.
• 정리 5: [math(s(24)=5)]. [math([0,5]^2)]에서 다섯 가로줄에 찍은 점 23개가 피할 수 없는 점 집합이다(그림 27). [math(y=1)]과 [math(y=4)]에는 [math(x=1, 1.7, 2.5, 3.3, 4)], [math(y=1.7)]과 [math(y=3.3)]에는 [math(x=1, 2, 3, 4)], [math(y=2.5)]에는 [math(x=1, 1.5, 2.5, 3.5, 4)]인 점을 찍는다. 쓰는 보조정리는 1, 2, 3이다. 귀퉁이 쪽 네 점은 두 벽에서 1씩 떨어져 있고, 벽을 따라 놓인 점의 간격은 0.7과 0.8이어서 정리 4와 마찬가지로 보조정리 2의 조건이 맞는다.
• 정리 6: [math(s(35)=6)]. 한 변이 6인 정사각형에서 여섯 가로줄에 찍은 점 34개가 피할 수 없는 점 집합이다(그림 28)[39]. [math(y=0.9)], [math(y=2.55)], [math(y=4.2)]에는 [math(x=1, 2, 3, 4, 5)], [math(y=1.725)]와 [math(y=3.375)]에는 [math(x=1, 1.5, 2.5, 3.5, 4.5, 5)], [math(y=5)]에는 [math(x=1, 1.6, 2.4, 3, 3.6, 4.4, 5)]인 점을 찍는다. 쓰는 보조정리는 1, 2, 3이다. 맨 아래 줄은 아래 벽에서 0.9, 맨 위 줄은 위 벽에서 1만큼 떨어져 있어 위아래가 대칭이 아니다. 왼쪽과 오른쪽 벽을 따라 놓인 점의 간격은 대부분 0.825인데, 벽까지의 거리 1과 함께 보조정리 2의 조건에 넣으면 [math(x+2y)]가 2.825로 한계인 [math(2\sqrt{2})] = 2.8284…에 아주 가깝다.

7.3.4. 경우를 나누는 증명

• 정리 7: [math(s(7)=3)]. 한 변이 [math(3-\varepsilon)]인 정사각형에 단위 정사각형 7개를 넣었다고 하자. 점 하나를 두 정사각형이 함께 품을 수는 없으므로, 그림 29의 거의 피할 수 없는 점 5개를 품는 정사각형은 많아야 5개다. 따라서 적어도 2개는 점을 하나도 품지 않고, 그런 정사각형은 중심이 물음표 영역에 있어야 한다. 이 두 정사각형을 놓는 방법은 돌리기와 뒤집기를 빼면 두 가지이고, 그림 30이 두 경우를 보여 준다. 그림에 색칠한 사다리꼴은 보조정리 5, 6, 7 때문에 이 두 정사각형이 반드시 덮는 부분이다. 사다리꼴은 보조정리 6의 [math(y)]를 [math(\frac{1}{2})]로 잡아 그렸는데, 논문은 이것이 뒤의 논증에서 가장 불리한 경우이기 때문이라고 적는다. 각 경우의 그림에는 피할 수 없는 점 3개가 더 찍혀 있고, 본문은 이것으로 증명을 마친다.
• 정리 8: [math(s(14)=4)]. 방식은 같지만 경우가 더 많다. 한 변이 [math(4-\varepsilon)]인 정사각형에 14개를 넣었다고 하면, 그림 31의 거의 피할 수 없는 점 12개를 품는 정사각형은 많아야 12개이므로 적어도 2개는 중심이 물음표 영역에 있다. 이 두 정사각형을 놓는 방법은 돌리기와 뒤집기를 빼면 다섯 가지이고(그림 32), 각 경우의 그림에는 피할 수 없는(또는 거의 피할 수 없는) 점 11개가 더 찍혀 있다. 그중 몇몇 경우는 다시 하위 경우로 나뉘며, 이것은 그림 33에 실려 있다.

7.4. 무한히 많은 경우를 한꺼번에

7.5. 경우 나누기

7.6. 증명 보조기

7.7. 일반 하한

7.8. 방법 한눈에 보기

8. 제곱수에 가까운 개수

8.1. 바둑판 배치를 이기는 배치

8.2. 바둑판을 이기는 가장 큰 개수

8.3. Friedman의 추측

8.4. 뺄 수 있는 최대 개수의 증가 속도

9. 큰 정사각형과 낭비 면적

9.1. 낭비 면적의 정의

9.2. 위쪽 한계

9.3. 아래쪽 한계

10. 최근 동향

10.1. 한눈에 보는 2026년

10.2. 기록 배치의 갱신

10.2.1. 기록표의 대규모 갱신(2024년 9월~2025년 3월)

10.2.2. 시뮬레이티드 어닐링(2025년 12월~2026년 5월)

10.2.3. AI 도구를 쓴 다듬기(2026년 6월~9월)

10.2.4. 정확한 유리수 인증서(2026년 9월 말~10월 초)

10.2.5. 새 탐색법과 10월의 경쟁

10.2.6. 최선 배치를 만든 사람

10.3. 하한의 갱신

10.3.1. 정사각형 17개의 하한

10.3.2. 정사각형 11개와 12개

10.3.3. 그 밖의 하한

10.4. 새로 증명된 값

10.5. 오래된 증명의 재검토

10.5.1. Nagamochi의 보조정리

10.5.2. Green의 하한

• [math(k \le 3)]: 정확한 값 [math(s(2))], [math(s(5))], [math(s(10))]이 Green의 값보다 크므로 참이다.
• [math(4 \le k \le 10)]: 2026년 다른 방법으로 증명되어 Squares Project가 확인한 하한이 Green의 값보다 커서, 값 자체는 참이다(위 '아직 모르는 경우'의 표). [math(k=4)]에서는 4.66044275가 증명되었고, 2026년 8월에는 Mira와 Stanislav Fort가 Green의 그림과 다른 16개 점으로 4.450837~4.468292의 하한을 얻었다.
• [math(k=11)]([math(n=122)]): 10월 10일 wand125가 낸 [math(s(122) \ge 11.26)]의 인증서가 맞다면 참이다(Green의 값은 11.2292…). 이 인증서는 아직 다른 사람이 다시 검증하지 않았다.
• [math(12 \le k \le 17)]: Green의 값이 지금까지 증명된 하한(Karakuş의 일반 하한)보다 커서, 참인지 아닌지 모른다. 참이라면 정사각형 145~148, 170~174, 197~201, 226~230, 257~261, 290~294개인 경우의 하한이 올라가지만, 이 문서의 표에는 쓰지 않았다. [math(k \ge 18)]([math(n \ge 325)])은 이 문서가 다루는 범위 밖이라 따지지 않았다.

10.5.3. 그 밖의 재검토

10.6. Squares Project

11. 남은 문제

• [math(s(12))]의 값: 정확한 값을 모르는 가장 작은 경우로, 3.9715 이상 4 이하다. 바둑판 배치보다 작은 배치가 있는지, 곧 [math(s(12)<4)]인지가 핵심인데, 아직 그런 배치는 하나도 알려져 있지 않다.
• [math(s(17))]의 값: 가장 유명한 미해결 경우로, 4.66044275보다 크고 4.6755300936… 이하다. Bidwell의 1998년 배치가 최적인지는 알려져 있지 않다.
• [math(s(k^2-k)<k)]가 성립하는 [math(k)]: [math(k \ge 11)]에서는 성립하고 [math(k=2, 3)]에서는 성립하지 않지만, [math(4 \le k \le 10)]에서는 모른다.
• Friedman의 추측: 바둑판 배치를 이기려고 빼야 하는 최소 개수가 [math(k)]가 커질 때 한 번도 줄지 않는지는, 빼는 개수가 4 이하인 경우만 확인되었다.
• 뺄 수 있는 최대 개수의 증가 속도: 바둑판 배치가 여전히 최선인, 뺄 수 있는 최대 개수는 2026년 프리프린트들에 따르면 [math(k^{1/3})]과 [math(k^{3/8})] 사이의 빠르기로 자란다. 정확한 지수는 모른다.
• 낭비 면적의 지수: [math(W(x)=O(x^\alpha))]가 성립하는 [math(\alpha)]를 얼마나 작게 잡을 수 있는지 모른다. [math(\alpha=\frac{3}{5})]까지 내려왔다는 증명이 arXiv에 공개되어 있고(학술지에 실린 2020년 증명은 오류가 지적되었다), [math(\frac{1}{2})]보다 작게는 잡을 수 없다.
• Green의 정리 9: Trevor Green이 2000년에 알린 [math(s(k^2+1))]의 하한은 공개된 근거가 틀린 것으로 드러났다. [math(k \le 10)]에서는 다른 증명으로 값이 맞음이 확인되었고 [math(k=11)]도 10월 10일 나온 인증서가 맞다면 참이지만(아직 다른 사람이 다시 검증하지 않았다), [math(12 \le k \le 17)]에서는 맞는지 모른다. 맞다면 정사각형 145~148, 170~174, 197~201, 226~230, 257~261, 290~294개인 경우의 하한이 올라간다.
• Soifer의 덮기 추측: 가장 기본적인 경우인 '단위 정사각형 [math(k^2+1)]개로는 한 변이 [math(k)]보다 큰 정사각형을 덮을 수 없다'도 [math(k=2, 3)]에서 증명되었고 [math(k=4)]는 2026년 증명이 발표되었을 뿐, 일반적인 [math(k)]에서는 열려 있다(아래 '덮기').
• [math(k^2-5)]개: 324 이하에서 [math(s(k^2-5)=k)]가 증명된 것은 [math(k=8)]인 [math(s(59)=8)]뿐이다. [math(k=5, 6, 7)]인 20개, 31개, 44개와 [math(k \ge 9)]인 76개, 95개 등은 모두 열려 있다.
• 큰 [math(n)]의 하한: 106 이상에서는 개별 하한 인증서가 거의 없어, 대부분 일반 하한에 기대고 있다.

11.1. Evan Daniel의 열린 문제 목록

11.1.1. 바둑판 배치는 언제 최적인가

• 단조성: [math(c^*(k+1) \ge c^*(k))]라는 추측으로, 모든 [math(k)]에 대한 것이다. [math(k \times k)] 바둑판에서 [math(c)]개를 빼도 더 작은 정사각형에 넣을 수 없다면, 그보다 큰 바둑판에서 [math(c)]개를 빼도 넣을 수 없다는 뜻이다(위 'Friedman의 추측'). Erich Friedman이 1998년 조사 논문(Dynamic Survey DS7)에 추측 1로 실으며 '알려진 최선 배치에서는 모두 성립한다'고 적었는데, 2026년 10월 11일 기준으로도 그렇다. 위 표의 상한 줄은 표 밖의 [math(k=18)]까지 한 번도 줄지 않는다. 하한 줄은 [math(k=9)]에서처럼 줄기도 하는데, [math(c^*)] 자체가 아니라 증명된 값을 적은 줄이기 때문이다. [math(c \le 4)]인 각 경우에는 추측이 증명되었다. [math(c \le 2)]는 Hiroshi Nagamochi(2005년)가 다뤘지만 2026년 그 증명에서 빈틈이 드러났고(목록은 Hakan Karakuş가 찾았다고 적었다. 위 '오래된 증명의 재검토'), [math(c=3, 4)]에 대한 2026년 결과(심사 전)에서 [math(c \le 2)]인 경우도 어차피 따라 나온다.
• 끝없이 커지는가: [math(c^*(k) \to \infty)]인가, 곧 모든 [math(c)]에 대해 [math(k)]가 충분히 크면 [math(s(k^2-c)=k)]인가 하는 물음으로, 큰 [math(n)]에 대한 것이다. 목록은 이 항목에 '주장됨(claimed)'이라고 표시했다. 2026년 유성준(squarepacker)이 DOI를 받아 공개한 프리프린트(GitHub 저장소 squarepacker/k2-minus-c, 심사 전)가 일부를 컴퓨터 계산에 기대어 모든 [math(k \ge 2)]에 대해 [math(c^*(k) \ge 0.0353\log k-1)]임을 증명했다고 밝혔기 때문이다. 다만 이 결과에서는 특정한 [math(c)]에 쓸 만한 문턱값이 나오지 않는다. Daniel은 이 프리프린트의 일부를 읽고 빈틈을 찾지 못했지만 전부 확인하지는 않았다고 적었고, 그 전까지는 이 물음을 공략한 출판물을 찾지 못했다고 했다. [math(c \le 4)]에서는 문턱값까지 명시해 증명되어 있다. 이 물음은 단조성 추측에서 따라 나오지 않는다. [math(c^*)]가 단조롭더라도 어느 값에서 멈출 수 있기 때문이다. 목록은 둘 가운데 이 물음이 더 다루기 쉬울 것이라고 본다.
• 한 칸씩 오르는가: [math(c^*(k+1) \le c^*(k)+1)]인가 하는 물음으로, 모든 [math(k)]에 대한 것이며 Daniel의 목록이 처음 내놓았다. [math(c^*(k+1) \le c^*(k)+2)]까지는 쉽게 나온다. 한 변이 [math(k)]보다 작은 정사각형에 들어가는 좋은 배치에 L자 줄을 두르면, 그 줄에는 [math(2k-1)]개가 들어가 바둑판 테두리의 [math(2k+1)]개보다 2개 적을 뿐이기 때문이다. 이 부분은 Lean으로 검사되었다(cStarStepsOfTwo). 앞의 두 항목과 이 물음의 답이 모두 '그렇다'라면, [math(c^*)]는 한 단계마다 0 또는 1씩 끝없이 오른다. 빨리 오를 수는 없어서, 아래 '낭비 면적의 크기'의 상한에서 [math(c^*(k)=O(k^{3/5}))]임이 나온다.
• [math(s(k^2-k)=k)]가 성립하는 마지막 [math(k)]: 유한히 많은 [math(k)]에 대한 물음이다. Friedman의 조사 논문은 '[math(k)]가 작으면 늘 [math(s(k^2-k)=k)]'라는 추측을 소개했다. 이 등식은 [math(k=2, 3)]에서 성립하고, [math(k=11)]과 [math(k \ge 12)]인 모든 [math(k)]에서는 성립하지 않는다. [math(k=11)]에서는 2025년 David W. Cantrell이 정사각형 110개를 한 변이 약 10.99679인 정사각형에 넣었고(심사 전), [math(k \ge 12)]에서는 2021년 M. Z. Arslanov, S. A. Mustafin, Z. K. Shangitbayev의 논문이 이를 보였다. 물음은 [math(4 \le k \le 10)] 가운데 어느 [math(k)]에서 성립하느냐는 것이다. 따라서 성립하는 마지막 [math(k)]는 3 이상 10 이하다. 알려진 사실만으로는 중간에 빈 곳이 생길 가능성을 막을 수 없지만([math(k=4)]에서 성립하지 않아도 [math(k=5)]는 정해지지 않는다), '한 칸씩 오르는가'의 답이 '그렇다'라면 빈 곳은 생기지 않는다. 가장 작은 경우가 바로 [math(s(12)=4)]이고, 배치 쪽에서는 [math(s(90)<10)]이 자연스러운 다음 시도다(아래 '개별 값').

11.1.2. 낭비 면적의 크기

• 제곱근 크기의 낭비: [math(W(x)=O(x^{1/2}))]일 것이라는 추측으로, 큰 [math(n)]에 대한 것이다. Friedman의 조사 논문 가운데 1998년판에만 추측 2로 실렸고, 그보다 앞서 Erdős와 Graham도 1975년 논문에서 '아마 올바른 한계는 [math(O(\alpha^{1/2}))]일 것'이라고 적었다. 이미 증명된 사실로는, 상한이 [math(O(x^{7/11}))](Erdős·Graham, 1975년)에서 여러 번 줄어 [math(O(x^{3/5}))]까지 내려왔다. 이 마지막 상한은 Fan Chung과 Ronald Graham이 2020년에 주장했지만 M. Z. Arslanov와 Hong Duc Bui가 오류를 찾았고, Bui(2025년)와 Rory McClenagan(2026년)이 프리프린트로 증명했다. 하한은 [math(x)]와 가장 가까운 정수 사이의 거리를 [math(\|x\|)]라 할 때 [math(W(x) \ge c\sqrt{x\|x\|})]이다(Klaus Roth, Robert Vaughan, 1978년). 그래서 지수는 [math(\frac{1}{2})]과 [math(\frac{3}{5})] 사이에 있다. 이 추측에 모두가 동의하지는 않는다. Chung과 Graham(2020년)은 낭비 면적이 [math(O(x^{1/2}))]일 것이라고 짐작할 수도 있다면서 '저자들은 이를 믿지 않는다'고 덧붙였고, [math(W(x)=o(x^{3/5}))]에 100달러, [math(O(x^{3/5-c}))]에 250달러, [math(W(N+\frac{1}{2}) \gg N^{1/2+c})]에 500달러의 상금을 걸었다(반증해도 상금을 받는다).

11.1.3. 평탄 구간과 배치 계열

• 정수가 아닌 평탄 구간이 있는가: [math(s(n)=s(n+1))]이면서 [math(s(n))]이 정수가 아닌 [math(n)]이 있는가 하는 물음으로, [math(n)]마다 따로 따져야 한다. 최선 배치 표로는 그렇다. [math(n=147, 264, 290)]이 그런 곳으로, 세 경우 모두 [math(n)]의 최선 배치가 [math(n+1)]의 기록 배치에서 정사각형 하나를 뺀 것이다. 어느 것도 증명되지는 않았다. 후보가 둘 더 있었지만 2026년 10월 [math(n=232, 295)]에 각자의 새 배치가 나와 깨졌다. 232는 Nate Chaoweeraprasit, 295는 Ryan Xu의 배치로, 각각 Squares Project 저장소(jlevy/squares)의 481번, 432번 이슈에 올라왔다. 2026년에 나온 컴퓨터 검증 하한(심사 전)으로 [math(n<28)]에서는 평탄 구간이 모두 배제되었고, 처음 남는 경우는 [math(s(28)=s(29))]다. 목록은 마지막 단계로 wand125가 2026년 10월 6일 보인 [math(s(19) \ge \frac{193}{40})] = 4.825를 꼽고, 이 값을 Squares Project가 다시 확인할 때 인증서를 만든 쪽의 구성 요소를 일부 함께 썼다는 단서를 달았다. 그러나 wand125가 같은 날 먼저 낸 [math(s(19) \ge 4.8229)]도 이미 정사각형 18개를 넣은 최선 배치의 한 변 [math(\frac{7+\sqrt{7}}{2})](약 4.82288)보다 커서 [math(s(18)<s(19))]를 보이며, 이 값은 Squares Project가 따로 짠 검사 프로그램으로 확인했다(위 '아직 모르는 경우').
• 유한히 많은가, 그리고 그보다 약한 꼴: 모든 [math(n)]에 대한 추측으로, Daniel의 목록이 처음 내놓았다. 앞 물음에 대한 가장 강한 답은 '없다'이고, 그 아래로 점점 약한 명제가 사다리처럼 놓인다. 각 명제는 위 명제로 가는 디딤돌이면서 위 명제가 틀렸을 때의 대안이다. 첫째는 정수가 아닌 평탄 구간이 유한히 많다는 것이다. 둘째는 평탄 구간이 짧다는 것으로, 어떤 [math(L)]이 있어 [math(s(n))]이 정수가 아니면 늘 [math(s(n)<s(n+L))]이라는 명제다. 목록에 오른 후보는 모두 길이가 2이고, 이 명제는 첫째에서 따라 나온다. 셋째는 소수 부분마다 유한히 많다는 것으로, 각 [math(\beta)]에 대해 [math(s(n)-\lfloor s(n) \rfloor=\beta)]인 평탄 구간이 유한히 많다는 명제이며, 역시 첫째에서 따라 나온다. 첫째는 셋째에 '평탄 구간이 나타나는 소수 부분은 유한히 많다'는 명제 하나를 더한 것과 정확히 같다. 이와 다른 방향으로 강화하면, 평탄 구간뿐 아니라 모든 [math(n)]에 대해 같은 것을 물어 '각 소수 부분은 유한히 많은 [math(n)]에서만 나타난다'고 할 수 있다. 이 명제는 셋째를 함의하지만 첫째는 함의하지 않는다. 평탄 구간이 무한히 많되 저마다 소수 부분이 다를 수 있기 때문이다. 이 함의 관계들은 Lean으로 검사되었다(저장소의 ConjecturesProofs.lean). 근거는 구조적인 것으로, 셋째를 직접 뒷받침한다. 다섯 후보(남은 셋과 깨진 둘)는 모두 고정된 모양의 계열, 곧 같은 45° 구성을 여러 [math(k)]에서 한 변 [math(k+\beta)]로 되풀이해 소수 부분 [math(\beta)]가 같은 배치들에 속한다. 각 계열의 낭비 면적은 [math(k)]에 비례해 늘어나므로 [math(O(x^{3/5}))]의 구성이 결국 이긴다. 따라서 어느 계열이든 최적인 구성원은 유한히 많다. David Ellsworth도 자료를 보고 '되풀이되는 것으로 알려진 패턴들조차 유한히 이어지다가 최적이 아니게 된다'며 같은 점을 짚었다. 여기서 첫째로 가려면 평탄 구간들이 유한히 많은 계열에서만 나온다는 것을 보여야 하는데, 이것이 진짜 빈틈이다. 모든 [math(n)]에 대한 꼴도 만만한 물음이 아니다. 낭비 면적이 [math(k)]보다 느리게 늘어나는 계열이 불가능하다는 것이 분명하지 않기 때문이다.

11.1.4. 최적 배치는 얼마나 복잡한가

• 대수적 차수: 큰 [math(n)]에 대한 물음으로, Daniel의 목록이 처음 내놓았다. 정수가 아닌 값만 따라가면 [math(s(n))]의 대수적 차수는 끝없이 커지는가? 최적 배치의 한 변이 제곱근만으로 나타나는 마지막 [math(n)]이 있는가? 정수가 아닌 최적값 가운데 유리수가 있는가? 목록이 드는 자료는 두 가지다. 2026년 컴퓨터 보조 증명으로 정해진 [math(s(11))]은 기울인 각도가 하나(약 40.18°)뿐이고, 한 변은 기약인 8차 다항식의 근이다. Ellsworth가 2025년에 찾은 [math(s(28))]의 최선 배치도 각도가 하나(약 30.29°)뿐인데, 그 6차 다항식의 갈루아 군이 [math(S_6)]이어서 한 변을 거듭제곱근으로는 아예 나타낼 수 없다. 그런데도 제곱근만으로 된 값이 [math(n=626)]([math(\frac{27}{2}+\frac{17\sqrt{2}}{2})])처럼 큰 곳에서도 기록을 지키고 있다. 목록은 유리수 기록으로 [math(n=50, 230, 261, 293)]을 든다. 다만 [math(n=261)]의 기록은 2026년 10월 Ryan Xu의 배치로 바뀌었는데 이 배치의 정확한 값은 알려져 있지 않아 유리수인지 알 수 없고, 이 문서의 표로는 [math(n=171, 198)]의 기록([math(\frac{95}{7})]과 [math(\frac{102}{7})])도 한 변이 유리수다(위 '최선 배치의 정확한 값'). 모두 피타고라스 세 수로 정해지는 각도를 쓰지만, 어느 것도 최적으로 증명되지는 않았다. 목록은 이 물음들을 다룬 문헌을 찾지 못했다고 적었다.
• 각도의 수: 큰 [math(n)]에 대한 물음으로, Daniel의 목록이 처음 내놓았다. [math(n)]이 커질수록 최적 배치는 서로 다른 기울기 각도를 점점 더 많이 써야 하는가? 큰 [math(n)]에서 더 깔끔하게 적으면 다음과 같다. 서로 다른 각도를 [math(m)]개 이하로 쓸 때의 가장 작은 낭비 면적을 [math(W_m(x))]라 하자. 축에 나란한 배치만으로는 [math(W_1 \approx 2x(x-\lfloor x \rfloor))]로 [math(x)]에 비례한다. 소수 부분을 고정하면, 고정된 모든 [math(m)]에 대해 [math(W_m)]도 [math(x)]에 비례하는가? 답이 '그렇다'라면 일반적인 [math(O(x^{3/5}))] 상한 때문에 최적 배치는 갈수록 더 많은 각도를 써야 한다. 목록에 따르면 낭비가 [math(x)]보다 느리게 자라는 구성은 Erdős·Graham 이후 모두 정사각형 더미마다 기울기를 바꾸며, 각도의 수가 제한된 배치에 대한 결과는 찾지 못했다. 기록표에서 보이는 모습은 아래 '작은 개수와 큰 개수가 만나는 곳'에 있다.
• 이어 붙인 배치는 최적이 아니다: 모든 [math(n)]에 대한 추측으로, Daniel의 목록이 처음 내놓았다. [math(s(n))]이 정수가 아니면 모든 [math(k \ge 2)]에 대해 [math(s(k^2n)<k\,s(n))]이라는 것이다. 곧 바둑판 배치를 이기는 최적 배치를 [math(k \times k)]로 늘어놓으면, 그 배치는 정사각형 [math(k^2n)]개의 최적 배치가 결코 아니라는 뜻이다. 목록은 이 명제를 Friedman의 조사 논문에서도, Ellsworth의 기록표에서도, 낭비 면적 논문들에서도 찾지 못했다고 적었다. 이어 붙이면 늘 [math(s(k^2n) \le k\,s(n))]이고(Lean으로 검사됨, tilingBound), 배치를 [math(k)]배로 키운 뒤 정사각형마다 [math(k^2)]개로 잘라도 같은 부등식이 나오므로, 추측은 이 부등식에서 등호가 성립하지 않는다는 것이다. 가정은 꼭 필요하다. [math(s(n))]이 정수이면 이어 붙인 바둑판 배치가 최적일 수 있어서 [math(s(32)=6=2s(8))]이다(Daniel 사이트의 'Proofs & results' 페이지). 이미 증명된 사실로, [math(k \ge K(n))]인 모든 [math(k)]에서는 추측이 성립한다. 이어 붙인 배치의 낭비 면적 [math(k^2(s(n)^2-n))]은 [math(k^2)]에 비례해 늘지만, 한 변이 [math(k\,s(n))]인 정사각형의 최선 배치는 [math(O(k^{3/5}))]만 낭비하기 때문이다(위 '낭비 면적의 크기'. Erdős·Graham의 지수 [math(\frac{7}{11})]로도 충분하다). [math(k)]가 크면 줄어드는 폭이 [math(k)]에 비례해 커지기까지 한다. Lean에서는 이것이 조건부 정리 tilingsEventuallyNotOptimal_of로 적혀 있어, 낭비 면적의 상한과 '한 변이 정수가 아니면 낭비가 양수'라는 사실에서 결론이 나온다. [math(K(n))]은 계산할 수는 있지만 커서, 추측의 실질적인 내용은 작은 [math(k)], 무엇보다 [math(k=2)]에 있다. 최선 배치 표는 확인할 수 있는 모든 곳에서 추측과 맞는다. [math(4n \le 323)]인, 정수가 아닌 기록 28개 모두에서 [math(4n)]의 기록이 [math(n)]의 기록의 두 배보다 작고, 그 차이는 가장 작은 [math(n=5, 65)]에서도 약 0.41이다. 목록이 계산한 바로는 [math(k=3, 4)]에서 가장 작은 차이가 각각 약 1.04와 1.59였다(이 문서의 표로는 [math(k=4)]에서 [math(n=19)]일 때 약 1.61이다). 다만 이것은 최적값이 아니라 최선 배치끼리 비교한 것이다. 시험할 만한 경우는 표 바로 바깥에 있다. 목록이 든 [math(n=241, 273, 307)]의 기록(Francisco Couzo, 2026년, Squares Project 등록부)을 두 배로 늘리면 정사각형 964개, 1092개, 1228개를 각각 한 변이 약 31.9763, 33.9679, 35.9621인 정사각형에 넣게 되는데([math(n=307)]의 기록은 그 뒤 2026년 10월 9일 Nate Chaoweeraprasit의 배치로 조금 더 줄었다), Ellsworth의 기록표와 Squares Project의 등록부 어디에도 이 개수는 없다. 2026년 10월 Daniel의 프로젝트는 세 경우 모두 이를 이겼다. 기록을 2×2로 이어 붙인 배치에서 출발해 짧게 탐색하여 [math(s(964) \le 31.8595)], [math(s(1092) \le 33.8406)], [math(s(1228) \le 35.8474)]를 얻었고, 각각 따로 짠 두 검사 프로그램으로 정확히 확인했다(저장소의 TILINGS.md). 줄어든 폭은 0.115~0.127이다. 가장 좋은 출발점은 배치를 2배로 키우고 정사각형마다 2×2 묶음으로 자른 배치로, 이 묶음들은 자른 선을 따라 어긋나며 미끄러질 수 있다. 그냥 이어 붙이거나 바람개비 모양으로 이어 붙인 배치는 이음매가 풀리면서 0.008~0.038 줄었고, 거울상으로 뒤집어 이어 붙여 이음매가 자기 거울상과 맞닿는 배치는 거의 움직이지 않았다. 이는 증명이 아니라 최선 배치에 대한 근거다. [math(s(4n))]이 [math(n)]의 기록의 두 배보다 작다는 것을 보였을 뿐이고, 추측은 참값 [math(s(n))]에 대한 것이기 때문이다. 이와 관련해 Ellsworth는 더 작은 배치에 L자 줄을 덧붙인 것이 아닌 배치를 원시 배치라 부른다. 기록 가운데 몇몇은 더 작은 기록 두 개에 바둑판 줄을 채워 만든 것인데, 이는 이어 붙이기와 다른 구성이다. [math(s(171))]은 [math(s(50))]의 배치 두 개로, [math(s(290))]과 [math(s(291))]은 [math(s(65))]의 배치 두 개로 만든다.
• 대칭: 최적 배치는 결국 대칭을 잃는가 하는 물음으로, 큰 [math(n)]에 대한 것이다. Daniel 사이트의 Explore 페이지는 기록마다 대칭을 보여 준다.

11.1.5. 작은 개수와 큰 개수가 만나는 곳

• 일부러 Göbel의 띠를 이기기: 명시적인 계열에 대한 물음으로, Daniel의 목록이 처음 내놓았다. Göbel의 대각선 띠는 대략 한 변의 길이만큼 낭비한다(낭비 [math(\approx x)]). 소수 부분이 0.707 근처일 때 [math((1-\varepsilon)x)]보다 적게 낭비하는 구성은 무엇이든 이 띠를 이긴다. 그래서 위 '낭비 면적의 크기'에 나온, 낭비가 [math(x)]보다 느리게 자라는 구성들은 충분히 큰 띠를 모두 이기지만, 그 상수는 적힌 적이 없고 그로부터 나오는 역전 지점은 천문학적으로 클 것이다. 기록표에서 [math(a=3)]을 빼고 처음 밀려난 띠([math(n=2043)])도 계열이 아니라 따로 최적화한 배치 하나에 졌다. 물음은 주어진 소수 부분에서 고정된 모양의 계열이 얻을 수 있는 가장 좋은 낭비 계수 [math(\kappa)](낭비 [math(\approx \kappa x)])가 얼마냐는 것이다. Göbel의 띠는 [math(\kappa \approx 1)]이고, 소수 부분 0.707에서 바둑판 배치는 [math(\kappa \approx 1.41)]이다. [math(\kappa<1)]이면서 그리 크지 않은 [math(n)], 되도록 2043보다 작은 [math(n)]부터 띠를 이기는 명시적인 계열이 있는가? 또 두 각도(축 방향과 45°)만 쓰는 계열 가운데서는 이 띠가 최적인가? 목록은 띠를 이기는 명시적인 계열이 있다는 것 자체는 의심할 여지가 없고, 발표된 구성의 역전 지점을 계산하는 일은 연구라기보다 셈하기라고 덧붙였다.
• 각도가 많은 배치는 어디서 시작되는가: 기록표 자료에 대한 물음이다. 기록표에서 각도가 다섯 종류 이상인 배치는 대개 제곱수 바로 아래, 곧 한 변의 소수 부분이 대략 0.87 이상인 곳에 있다. 조금만 기울이는 구성들이 쓰이는 곳이다. 예외는 [math(n=68, 103, 123, 297)]이다. 각도가 세 종류 이하인 배치는 [math(k=17)]까지 제곱수 사이의 각 구간에서 절반쯤을 여전히 차지하고, 줄어드는 기미가 보이지 않는다. [math(k)]가 커지면서 각도가 많은 배치의 영역이 각 구간의 위쪽에서 아래로 퍼지는가, 퍼진다면 얼마나 빨리 퍼지는가?
• 기록표의 패턴은 어디서 깨지는가: 기록표 자료에 대한 물음이다. 목록은 두 예를 든다. 첫째, Göbel의 띠는 [math(a=43)]까지 기록을 지킨다([math(a=3)]은 예외이고, [math(n=84)]의 띠도 2026년 10월 밀려났다. 위 '평탄 구간과 배치 계열'). [math(a=3)]을 빼고 처음 밀려난 띠는 [math(n=2043)]이지만 그보다 큰 띠 가운데 몇 개(2938개 근처)는 Göbel의 띠를 모은 페이지의 HTML 주석에 밀려나지 않은 것으로 적혀 있어, 최선 배치에서 띠가 어디서 끝나는지는 정해지지 않았다. 둘째, Ellsworth의 기록표에 따르면 [math(k<42)]인 모든 [math(k)]에서 [math(s(k^2+1))]의 최선 배치는 소수 부분이 [math(\frac{1}{2})] 이상인데, [math(k=42)]에서 Károly Hajba가 낸 기록(정사각형 1765개, 한 변 약 42.488)이 처음으로 [math(\frac{1}{2})] 아래로 내려갔다. 이런 패턴은 그 뒤에 있는 탐색만큼만 믿을 수 있으므로, 패턴이 깨지는 곳은 배치에 대한 사실이면서 탐색이 어려워진 곳에 대한 사실이기도 하다.

11.1.6. 국소 최적성

• 보통의 정의가 너무 약한 이유: 물음이나 추측이 아니라 개념을 다듬는 설명이다. 한 변이 정수이면 [math(k \times k)] 정사각형 안에서 미끄러져 다닐 수 있는 배치가 모두 같은 크기여서, 큰 정사각형의 크기가 일정한 거대한 집합을 이룬다. 이를 평평한 집합이라 하자. 이 집합의 한 점은 국소 최적이면서도, 같은 평평한 집합 안에서 크게 움직이면 더 작은 정사각형에 이를 수 있다. 가로 한 줄과 세로 한 줄이 꽉 차 있기만 해도 국소 최적이 된다. 정사각형 [math(k)]개로 된 한 줄을 함께 작은 각 [math(\theta)]만큼 기울이면 폭이 [math(k\cos\theta+\sin\theta \approx k+\theta-\frac{k\theta^2}{2})]로 바뀌는데, 이 값은 [math(\theta)]가 [math(\frac{2}{k})] 가까이 될 때까지 [math(k)]보다 크기 때문이다. 그래서 [math(4 \times 4)] 정사각형 안에 L자로 놓인 정사각형 7개는 국소 최적이지만, 미끄러뜨리면 [math(3 \times 3)] 귀퉁이에 들어간다. 구멍이 [math(c>c^*(k))]개인 바둑판 배치도 가로 한 줄과 세로 한 줄이 꽉 차 있으면 마찬가지다. 이 문제는 평평한 집합 전체를 보면 풀린다. 큰 정사각형을 한 번도 키우지 않는 연속 운동으로는 더 작은 정사각형에 이를 수 없는 배치를 평탄 최적(plateau-optimal)이라 하자. 여기서 plateau는 앞 갈래의 평탄 구간이 아니라 평평한 집합을 가리킨다. 평탄 최적은 같은 크기 안에서 그 배치로부터 닿을 수 있는 모든 배치가 보통의 뜻으로 국소 최적이라는 것과 같다. 배치들은 반대수적 집합을 이루므로, 곡선 선택 보조정리에 따라 '얼마든지 가까운 곳에 더 작은 정사각형이 있다'가 '더 작은 정사각형으로 가는 경로가 있다'로 바뀌기 때문이다. 따라서 평탄 최적성은 평평한 집합의 연결된 조각에만 달려 있는데, 보통의 국소 최적성은 그렇지 않다. 평탄 최적성은 이런 성질을 가지면서 보통의 국소 최적성을 함의하는 가장 약한 조건이다. 그렇다고 전역 최적성을 달리 말한 것은 아니다. 한 크기의 정사각형에 들어가는 배치들이 하나로 이어져 있을 필요는 없기 때문이다. 실제로 [math(n=38)]과 [math(n=149)](한 변 [math(k+\frac{\sqrt{2}}{2})])의 최선 배치에는 서로 다른 배치들이 있다. Göbel의 1979년 대각선 띠, [math(n=38)]에 대한 David W. Cantrell의 2005년 다른 배치, [math(n=149)]에 대한 Ellsworth의 2024년 강성 다른 배치가 그것이다(Ellsworth의 Göbel strips 페이지).
• 평탄 최적이지만 최적은 아닌 배치: [math(n)]마다 따로 따지는 물음이다. 강성 배치는 닿을 수 있는 배치가 자기 하나뿐이므로 저절로 평탄 최적이다. 그러니 최적이 아닌 강성 배치만 있어도 물음의 가장 단순한 꼴에는 답이 된다. 예를 들어 Ellsworth의 [math(n=18)] 강성 다른 배치는 한 변이 [math(2+2\sqrt{2})](약 4.8284)로, 최선 배치의 약 4.8229보다 크다. 열린 물음은 움직일 수 있는 배치에 대한 것이다. 자유롭게 움직일 수 있으면서 평탄 최적이고, 한 변이 [math(s(n))]보다 큰 배치가 있는가? 자연스러운 후보는 더는 기록이 아닌 [math(n=2043)]의 Göbel 띠(Ellsworth는 [math(n=149)]에서 Göbel의 배치가 강성이 아니라고 적었다)와 구멍이 [math(c>c^*(k))]개인 바둑판 배치다.
• 다른 배치는 몇 개나 있는가: 큰 [math(n)]에 대한 물음으로, Daniel의 목록이 처음 내놓았다. 서로 닿을 수 없는 배치가 몇 개까지 같은 최선의 변을 가질 수 있고, 그 수는 [math(n)]에 따라 얼마나 빨리 늘 수 있는가? [math(n=149)]에서 이미 수백 개가 나온다. Ellsworth의 강성 다른 배치는 기울인 정사각형을 다섯 개만 쓰고, 그 하나하나가 [math(s(5))]의 묶음 안에 있다. 이 묶음은 축에 나란한 정사각형 넷이 45° 기울인 정사각형 하나를 둘러싼, 한 변 [math(2+\frac{\sqrt{2}}{2})]의 배치다. Daniel은 축에 나란한 정사각형마다 각 좌표를 0 또는 [math(\frac{\sqrt{2}}{2})]만큼 옮길 수 있게 한 정수계획 모형으로 이런 배치를 정확히 다뤘다. 이 모형에서 정사각형 149개의 배치는 모두 묶음을 정확히 다섯 개 쓴다. 묶음들의 [math(x)] 방향 귀퉁이 좌표는 0에서 10까지 2나 3씩 오르는 사슬을 이루고 [math(y)] 방향도 마찬가지여서, 사슬이 방향마다 6가지 나온다. 묶음들은 두 사슬을 순열로 짝짓는다. 모든 짝짓기가 되는 것은 아니지만(이웃한 묶음에 대한 간단한 규칙으로는 어느 것이 되는지 알 수 없다) 470가지가 넘게 된다. 각 경우 모형 안에서 나머지 정사각형의 자리가 하나로 정해지므로, 저마다 강성이고 서로 다른 배치일 것으로 보인다. 반면 [math(n=38)]에서는 묶음 두 개가 미끄러질 여유가 있어서, 그곳의 다른 배치들은 자유롭게 움직일 수 있다. 이 계산은 탐색 단계의 것으로, 정리로 증명된 것은 아니다(저장소의 goebel_alt).
• 더 나은 배치는 얼마나 먼가: 모든 [math(k)]에 대한 물음이다. [math(c>c^*(k))]일 때 한 변 [math(k)]를 이기려면 바둑판 배치를 얼마나 크게 바꿔야 하는가? 이기는 배치는 Erdős·Graham의 구성처럼 [math(\frac{2}{k})] 가까이만 기울인 작은 변형인가, 아니면 45° 묶음으로 만든 전혀 다른 구조인가?
• 안정성: 모든 [math(n)]에 대한 물음이다. 한 변이 [math(s(n))]에 가까운 배치는, 자유롭게 움직일 수 있는 정사각형을 빼면, 늘 어떤 최적 배치에 가까운가? 배치의 공간을 잘게 나누는 컴퓨터 증명은 사실상 이 명제를 증명하는 셈이다. 이것이 성립하지 않는 경우, 곧 변의 길이는 거의 같지만 서로 멀리 떨어진 배치가 여럿인 경우에 그런 증명이 고전한다. [math(n=149)]처럼 같은 변에 다른 배치가 여럿 있는 경우가 그 극단으로, 증명이 하나하나를 따로 다뤄야 한다.

11.1.7. 개별 값

• [math(s(12)=4)]: 하나의 [math(n)]에 대한 추측으로, 목록은 이를 가장 알고 싶은 정확한 값으로 꼽는다. [math(s(k^2-k)=k)] 가운데 열려 있는 가장 작은 경우이고, [math(c^*(4))]가 3인지 4인지를 정한다. 증명된 하한은 3.9715로, 유성준(squarepacker)이 2026년 10월 5일 Daniel의 3.9686… 인증서에 쓰인 점들의 무게를 다시 정해 얻었다(위 '정사각형 11개와 12개'). Daniel의 사이트에는 정사각형 12개만 다룬 해설 페이지가 따로 있다.

• [math(s(90)<10)]: [math(c)]를 고정하고 최선 배치의 여유 [math(k-s(k^2-c))]를 따라가 보면(아래 표), [math(k)]가 커질수록 꾸준히 줄다가 어떤 배치도 [math(k)]를 이기지 못하는 곳에 이른다. [math(c=10)]이면 여유가 [math(k=8)]에서 약 0.153, [math(k=9)]에서 약 0.056이어서, 직선으로 이어 보면 [math(k=10)]에서 0이거나 0보다 조금 작아진다. 그런 배치가 나오면 [math(s(k^2-k)=k)]가 성립하는 마지막 [math(k)]가 9 이하임이 밝혀진다.
• 다음 경계 사례: 같은 방식으로 읽으면, [math(k)]마다 알려진 어떤 배치도 이기지 못한 바둑판 배치 가운데 구멍이 가장 많은 것이 다음 후보다. [math(s(133)<12)], [math(s(157)<13)], [math(s(183)<14)], [math(s(212)<15)], [math(s(242)<16)], [math(s(274)<17)]이 그것이다. [math(k=18)]의 후보였던 [math(s(308)<18)]은 2026년 10월 10일 이루어졌다. Kevin Fang이 정사각형 308개를 한 변이 약 17.99931인 정사각형에 넣었고(Squares Project 저장소 484번 이슈), Daniel이 이를 약 17.99827로 줄였다(489번 이슈. 둘 다 목록을 쓸 때는 등록되기 전이었다). 이 경우가 속한 [math(c=16)]의 열은 [math(k=15, 16, 17)]에서 여유가 각각 약 0.054, 0.030, 0.016으로 줄어 왔다. [math(k=15)]의 경계는 이보다 앞서 한 칸 옮겨졌다. Joost de Winter가 2026년 9월 16일 정사각형 211개를 한 변이 14.99796…인 정사각형에 넣었기 때문인데(Squares Project에서 검증), 이 배치는 Ellsworth의 기록표에 실려 있지 않다(10월 11일에는 Daniil Ostashev가 이를 14.99633…으로 더 줄였다). 가장 유망한 것은 [math(s(133)<12)]로, 그 열([math(c=11)])은 [math(k=9, 10, 11)]에서 약 0.119, 0.050, 0.003으로 줄어 왔다. 나머지 경우의 여유는 직선보다 느리게 줄어서 가능성이 낮다.
• 고정된 모양 계열의 마지막 구성원: 계열마다 [math(k)]가 가장 큰 구성원, 예를 들어 [math(\sqrt{7})] 계열의 [math(s(299))]와 [math(s(234))]도 더 나은 배치가 나올 법한 곳이다. 계열은 결국 모든 구성원을 잃어야 하는데, [math(\sqrt{7})] 계열은 이미 [math(k=5, 6, 8, 9, 10, 11, 13, 16)]에서 기록을 갖지 못한다. 이 가운데 [math(k=9, 11)]인 [math(n=86, 127)]은 2026년 10월 기록을 잃었고, [math(k=13)]인 [math(n=176)]은 목록이 나온 뒤인 10월 11일에 기록을 잃었다.
• [math(s(147))]: 정수가 아닌 평탄 구간으로 추측되는 첫 경우다. 정사각형 147개를 148개의 기록 배치에서 하나를 뺀 것보다 작은 정사각형에 넣는 배치가 하나라도 나오면 이 평탄 구간은 사라진다.

11.1.8. 이웃한 문제

• 직사각형에서 한 변씩: 모든 [math(a)], [math(b)]에 대한 추측으로, Daniel의 목록이 처음 내놓았다. [math(a \times b)] 바둑판 배치에서 정사각형을 빼도 여전히 최적인(더 작은 [math(a' \times b')] 직사각형에 들어가지 않는), 뺄 수 있는 최대 개수를 [math(c^*(a, b))]라 하자. [math(c^*(a, b))]는 [math(a)]와 [math(b)] 각각에 대해 따로 보아도 줄지 않는가? 이는 Friedman 추측의 반 걸음에 해당한다. 높이를 고정하고 너비만 늘리는 경우는 이와 관련된, 더 쉬워 보이는 경우다. 바둑판 배치보다 작은 직사각형에 들어가는 경우는 알려져 있다(M. Z. Arslanov, S. A. Mustafin, Z. K. Shangitbayev, 2021년). Nagamochi의 직사각형 하한(2005년)에는 빈틈이 있다(2026년 chelokot과 Hakan Karakuş가 반례를 냈다. 위 '오래된 증명의 재검토').
• 변의 길이의 합: 이미 증명된 사실로, 맥락을 위해 실린 항목이다. Erdős 문제 106번은 단위 정사각형 안에 정사각형 [math(n)]개를 넣을 때 변의 길이의 합이 최대 얼마일 수 있는지([math(f(n))])를 묻는다. 목록에 따르면 그 추측 [math(f(k^2+1)=k)]는 2026년 반증되었다([math(f(17)>4)], Lean으로 검증. Erdős 문제 모음의 106번 항목). Erdős는 [math(f(n+1)=f(n))]이 언제 성립하는지도 물었는데, 이는 평탄 구간에 해당하는 물음이다.
• 정육면체: 큰 [math(n)]에 대한 물음이다. 고정된 [math(c)]마다, [math(k)]가 충분히 크면 [math(s_3(k^3-c)=k)]인가? 여기서 [math(s_3)]은 단위 정육면체를 넣을 정육면체의 가장 작은 한 변이다. 단위 정육면체를 정육면체에 넣는 문제에서는 [math(c=1)]인 경우조차 출판된 적이 없는 듯하다. Friedman의 'Cubes in Cubes' 페이지는 배치만 모아 두었다.

12. 관련 문제

12.1. 원 채우기

12.2. 다른 도형에 넣기

12.3. 덮기

12.4. 완전 정사각형 분할

13. 기타

14. 관련 사이트

14.1. 기록표와 자료

• Squares in Squares: 최선 배치 기록표. David Ellsworth가 Erich Friedman의 원본을 이어 관리한다.
• Squares in Squares: Triangular Table View: 같은 기록 배치들을 삼각형 모양의 표로 늘어놓은 페이지
• Packing Unit Squares in Squares (David Ellsworth 편집판): Friedman의 조사 논문을 Ellsworth가 고쳐 쓴 판
• Erich's Packing Center: 정사각형 외에도 여러 도형의 채우기 기록을 모은 원조 사이트
• Erich Friedman, "Packing Unit Squares in Squares: A Survey and New Results": Electronic Journal of Combinatorics, Dynamic Survey DS7
• Square Packing: Bounds, Results and Best Packings: Squares Project 사이트. n=1~324의 상한·하한 표, 결과별 검증 기록, 직접 배치해 보는 도구가 있다.
• How Record Square Packings Are Found: Squares Project가 정리한 기록 배치 탐색·검증 방법 해설
• Square Packing Atlas: Evan Daniel의 사이트. 기록 배치 탐색, n≤100의 최선 배치와 하한 비교, 열린 문제 목록, 증명 해설이 있다.
• MathWorld
• 영어 위키백과

14.2. 연구 저장소

• jlevy/squares: Squares Project 저장소. 기록 등록, 검증 도구, 논문 자료
• evand/square-packing: Evan Daniel의 증명·인증서·Lean 코드와 배치 탐색 프로그램
• evand/square-packing의 k2m3: [math(s(k^2-3)=k)] 증명 설명과 인증서
• evand/square-packing의 k2m4: [math(s(k^2-4)=k)] 증명 설명과 인증서
• wand125/valid7-independent-check: Daniel의 [math(s(k^2-3)=k)] 증명에 쓰인 유한한 명제를 따로 짠 프로그램으로 확인한 저장소(지금은 wand125/square-packing의 checks/valid7로 옮겨져 보관만 된다)
• wand125/square-packing: wand125(Hiroaki Hosono)의 하한 인증서, 검사 프로그램, Lean 형식화를 모은 저장소. 따로 있던 저장소 열 개를 이곳으로 모았다
• wand125/square-packing-bounds: 2026년 9월 22일~10월 6일에 낸 하한 인증서(지금은 wand125/square-packing으로 옮겨져 보관만 된다)
• Queuingtheorydotcom/11SquaresOptimal: [math(s(11))] 증명
• Queuingtheorydotcom/11SquaresFormalized: [math(s(11))] 증명의 Lean 4 형식화
• Kleddamag/11-squares-certified-bound: [math(s(11) > 3.875)] 인증서
• chelokot/square-packing-archive: [math(s(k^2-2)=k)], [math(s(6))], [math(s(10))], [math(s(13))], [math(s(22))], [math(s(33))]의 Lean 증명과 Nagamochi 보조정리 1의 반례
• Guzhou0806/n17-square-packing, Kleddamag/17-squares-certified-bound: [math(s(17))] 하한
• Guzhou0806/n40-square-packing: [math(s(40))] 하한
• tokoharu/square-packing-density-bounds: 직사각형 밀도 인증서로 하한을 증명하는 도구
• ry-xu/square_packing: Ryan Xu가 LLM을 이용한 탐색으로 찾은 기록
• franciscouzo/square-packing: Francisco Couzo의 기록 배치와 정확한 인증서
• itsnaka/squish-certs: SQUISH로 찾은 기록 배치의 인증서(10월 11일의 9개 포함)
• dostashev/square-packing: Daniil Ostashev의 [math(n=155, 156, 211)] 기록 배치와 정확한 인증서, 검사 프로그램
• SidG2k1/square-packing-refinements: Siddharth Gupta가 다듬은 배치의 인증서
• lollipoll/couzo-five-exact-certificates: Seth Rehwaldt가 다듬은 배치의 인증서
• Mishapolk/square-packing-records: Mishapolk의 기록
• ebdeleeuw/square-packing-n70: Eric Deleeuw가 다듬은 [math(n=70)] 배치의 인증서
• TheSnakeFang/squarepack-certs: Kevin Fang의 [math(s(308))], [math(s(343))], [math(s(344))] 배치 인증서
• griffcass/square-packing: Griffin Casson이 GPU로 돌린 시뮬레이티드 어닐링과 국소 최적화로 찾은 기록
• Davidebyzero/packing_squares_in_squares__tools: David Ellsworth가 기록표 관리에 쓰는 도구

14.3. 주요 논문

• P. Erdős, R. L. Graham, "On packing squares with equal squares", Journal of Combinatorial Theory, Series A 19, 1975
• K. F. Roth, R. C. Vaughan, "Inefficiency in packing squares with unit squares", Journal of Combinatorial Theory, Series A 24, 1978
• F. Göbel, "Geometrical packing and covering problems", Packing and Covering in Combinatorics(A. Schrijver 엮음), Mathematical Centre Tracts 106, 179~199쪽, 1979
• S. El Moumni, "Optimal packings of unit squares in a square", Studia Scientiarum Mathematicarum Hungarica 35, 1999
• M. Kearney, P. Shiu, "Efficient packing of unit squares in a square", Electronic Journal of Combinatorics 9, 2002
• W. Stromquist, "Packing 10 or 11 unit squares in a square", Electronic Journal of Combinatorics 10, 2003
• H. Nagamochi, "Packing unit squares in a rectangle", Electronic Journal of Combinatorics 12, 2005
• T. Gensane, P. Ryckelynck, "Improved dense packings of congruent squares in a square", Discrete & Computational Geometry 34, 2005
• F. Chung, R. Graham, "Packing equal squares into a large square", Journal of Combinatorial Theory, Series A 116, 2009
• W. Bentz, "Optimal packings of 13 and 46 unit squares in a square", Electronic Journal of Combinatorics 17, 2010
• W. Bentz, "Optimal packings of 22 and 33 unit squares in a square", arXiv, 2016
• T. Montanher, A. Neumaier, M. C. Markót, "Rigorous packing of unit squares into a circle", Journal of Global Optimization 73, 2019
• F. Chung, R. Graham, "Efficient packings of unit squares in a large square", Discrete & Computational Geometry 64, 2020
• M. Z. Arslanov, S. A. Mustafin, Z. K. Shangitbayev, "Improved packings of n(n−1) unit squares in a square", Electronic Journal of Combinatorics 28, 2021
• M. C. Markót, "Improved interval methods for solving circle packing problems in the unit square", Journal of Global Optimization 81, 2021
• M. Z. Arslanov, H. D. Bui, "Note on 'efficient packings of unit squares in a large square'", Discrete & Computational Geometry, 2025
• H. D. Bui, "Square Packing with O(x^0.6) Wasted Area", arXiv, 2025
• R. McClenagan, "Optimally Packing a Large Square by Unit Squares", arXiv, 2026
• H. Karakuş, "A counterexample to Nagamochi's scoring lemma and a new rectangle packing bound", arXiv, 2026
• 유성준(Sungjoon Ryu), "Packing k^2-c unit squares: a lower bound of order k^{1/3} for the deficiency", Zenodo, 2026
• 유성준(Sungjoon Ryu), "Packing k^2-c unit squares: an upper bound of order k^{3/8} for the deficiency", Zenodo, 2026