최악의 타일링

Why Is This Shape So Terrible to Pack? | Quanta Magazine

Why Is This Shape So Terrible to Pack? | Quanta Magazine

 

수세기 동안 수학자들은 육각형이 공간을 채우는 최적의 타일링 방식일 것이라고 믿어왔습니다. 즉, 넓은 영역을 일정한 크기의 타일로 나누면서 타일의 둘레를 최소화하고 싶다면, 육각형이 가장 효율적이라는 의미입니다. 1999년, 피츠버그 대학교의 토마스 헤일스(Thomas Hales)가 이 사실을 엄밀하게 증명하면서, 육각형이 사각형이나 삼각형, 혹은 그 외의 다른 형태보다 효율적임을 입증했습니다.

 

하지만 모든 모양이 타일처럼 빈틈없이 공간을 채울 수 있는 것은 아닙니다. 예를 들어, 원은 타일처럼 배치할 수 없습니다. 원들을 최적의 방식으로 배치할 때, 가장 효율적인 육각형 배열을 사용해도 평면의 약 90.69%만 채울 수 있습니다.

 

1920년대에 이르러 수학자들은 반대로 이렇게 물었습니다. “가장 채우기 힘든 모양은 무엇인가?” 즉, 최적의 배열로 배치하더라도 가장 많은 빈 공간을 남기게 만드는 모양은 어떤 것일까? 이에 대해 최근 헤일스와 그의 제자였던 쿠운디냐 바자(Koundinya Vajjha)의 연구가 새로운 돌파구를 열었습니다. 바자는 현재 인텔에서 엔지니어로 활동 중입니다.

 

‘가장 나쁜 모양’을 정의하기 위해서는 몇 가지 규칙이 필요합니다. 구멍이 있거나 안쪽으로 들어간 모양처럼 엉성한 형태는 아주 나쁜 모양을 만들어낼 수 있지만, 이는 수학적으로 흥미롭지 않습니다. 예를 들어, 구멍이 난 사각형은 가장자리 두께를 매우 얇게 만들면 빈 공간의 비율을 극대화할 수 있습니다. 하지만 ’볼록성(convexity)’이라는 조건을 추가하면 상황이 달라집니다. 볼록성은 모양 안의 두 점을 선택했을 때 그 점을 잇는 선분이 모양 안에 완전히 포함되어야 함을 의미합니다. 따라서 이러한 조건 아래에서는 중간에 구멍이 나 있는 모양은 허용되지 않습니다.

 

수학자들이 흥미를 가지는 또 다른 조건은 ’중심 대칭(central symmetry)’입니다. 중심 대칭 조건이 없을 경우, 가장 나쁜 모양으로 알려진 것은 7변을 가진 정칠각형입니다. 이 모양은 약 89.27%의 공간만을 채울 수 있습니다. 하지만 이것이 가장 나쁜 모양인지 증명하기에는 여전히 갈 길이 멉니다. 헤일스와 바자는 이보다 간단하면서도 더 제한적인 문제, 즉 ‘볼록하고 중심 대칭인 경우에 가장 나쁜 배열을 가지는 모양’을 찾기 위해 연구를 진행했습니다.

 

처음에 수학자들은 원이 가장 채우기 힘든 모양일 것이라 여겼습니다. 그런데 1934년, 독일 수학자 칼 라인하르트(Karl Reinhardt)는 원보다 더 ‘비효율적인’ 모양을 발견했습니다. 바로 모서리가 둥글게 처리된 팔각형이었습니다. 이 모양에서 각 모서리의 둥근 부분은 쌍곡선으로 그려지며, 이를 이용한 배열의 총 채움 비율은 약 90.24%입니다. 원의 90.69%와의 차이는 미미해 보이지만, 수학적으로는 중요한 차이를 갖습니다.

 

하지만 라인하르트조차 자신의 둥근 팔각형이 가장 나쁜 모양임을 증명하지는 못했습니다. 그 누구도 이 문제를 해결하지 못했습니다. 구(球)를 고차원에서 채우는 연구로 잘 알려진 마이크로소프트 리서치의 수학자 헨리 코언(Henry Cohn)은 이렇게 말했습니다. “저는 늘 라인하르트가 맞다고 생각했지만, 이를 해결할 수 있는 이론적 기반이 없었습니다. 증명을 보게 될 날이 올까요? 제 평생에는 어려울 것 같았죠.”

 

아직 그 증명은 나오지 않았지만, 헤일스와 바자의 연구는 중요한 중간 추측을 해결하는 성과를 거두었습니다.

 

헤일스는 사실 육각형 타일링에 관한 결과보다는 1990년대 후반에 증명한 구 채우기 문제로 더 유명합니다. 이는 17세기 요하네스 케플러(Johannes Kepler)가 제시한 ‘세 차원에서의 구 채우기 최적 방법’이라는 추측을 다룬 것으로, 마치 시장에 쌓여 있는 과일 더미를 연상케 하기 때문에 ‘오렌지 쌓기 문제’라고도 불립니다. 당시 그의 증명은 컴퓨터 계산에 크게 의존했기에, 최초 발표 이후 수년간 수학계의 검증을 거쳐야 했습니다.

 

2007년, 베트남에서 연구 휴가를 보내던 중 헤일스는 케플러의 추측 증명에서 남은 문제를 마무리하던 중, 최적의 배열이 아닌 최악의 배열 문제로 관심을 돌렸습니다. 하지만 그 연구는 느리게 진전되었습니다.

 

최악의 채움 문제는 최대 밀도가 가장 낮은 형태를 찾는 문제입니다. 이러한 제약 조건은 ‘미니맥스(minimax) 문제’라 불리는 범주에 속하며, 본질적으로 해결하기 까다로운 성질을 지닙니다. 이를 접근하는 표준적인 방법 중 하나는 변분법(calculus of variations)을 사용하는 것인데, 라인하르트는 둥근 팔각형의 최적성을 증명하려고 이 방법을 적용했습니다. 팔각형 모서리를 쌍곡선으로 그려 최대한 면적을 줄이되, 배열에는 영향을 미치지 않도록 설계했습니다. 이로 인해 예상된 해법은 단순한 곡선뿐 아니라 곡선과 직선이 섞인 형태를 포함해야 했습니다.

 

헤일스는 라인하르트의 연구에서 시작하려 했지만, 곧 변분법만으로는 문제를 해결할 수 없음을 깨달았습니다. 그는 이 방법이 특정 조건에 맞춘 최적 곡선을 찾는 데는 탁월하지만, 그가 찾고자 하는 해답은 곡선 그 자체가 아니라고 판단했습니다. 만약 라인하르트의 예측이 맞다면, 그 해답은 곡선과 직선이 결합된 더 복잡한 구조일 것이었습니다.

 

2017년, 10여 년간 간헐적으로 연구한 끝에, 헤일스는 ‘증명의 청사진’을 담은 예비 논문을 발표했습니다. 그는 최적 제어 이론(optimal control theory)을 도입해 이 문제를 풀어내고자 했는데, 이는 반복적으로 직선과 곡선을 오가는 구조를 탐구하는 데 더 적합하다고 보았기 때문입니다. 수학계는 이 문제에 대해 새로운 가능성을 느꼈습니다. “저는 헤일스의 창의성에 깊은 인상을 받았습니다,”라고 코언은 말했습니다. “그러나 한편으로는, 정말 해내려면 엄청난 노력이 필요할 것 같다고 생각했죠.”

 

헤일스가 청사진을 제시한 지 얼마 지나지 않아 바자가 피츠버그에 왔습니다. 많은 대학원생처럼 갈피를 잡지 못한 상태였던 바자는 소프트웨어와 하드웨어를 검증하는 형식적 기법(formal methods)을 공부하고 싶었지만, 집중할 문제를 찾지 못해 여러 강연을 듣고 있었습니다. 그러던 중 최악의 채움 문제를 알게 되었고, 그 난해한 매력에 끌렸습니다. 그날 오후, 바자는 헤일스의 예비 논문을 발견했고, 문제에 대한 급진적인 접근 방식에 더욱 흥미를 느꼈습니다.

 

그들은 그다음 주에 만났습니다. “저는 헤일스에게 ‘이게 그렇게 쉬우면 직접 하시죠?’라고 말했습니다.” 바자는 회상했습니다. 헤일스는 그들이 함께 약 6개월 안에 문제를 해결할 수 있을 것이라고 답했습니다. 바자는 동의했지만, 이후 “세상 일이 그렇게 쉽지 않다”는 걸 실감하게 되었습니다.

 

둥근 팔각형이 최악의 채움 형태임을 증명하기 위해 헤일스와 바자는 다른 모든 가능한 형태를 배제해야 했습니다. 중심 대칭과 볼록성이라는 제약 조건이 있더라도, 무한히 많은 가능한 해답이 존재했으며, 그중 일부는 직선과 곡선을 무한히 번갈아가며 나타나는 ‘채터링(chattering)’ 구조를 포함했습니다. 이러한 모양은 모순처럼 보이지만, 원보다 더 나쁜 배열이 가능할지도 모릅니다. 혹시라도 라인하르트의 둥근 팔각형보다 나쁜 형태가 될 가능성도 염두에 두어야 했습니다.

 

헤일스는 케플러 추측을 증명할 때 컴퓨터 보조 접근법을 활용해 거의 무한에 가까운 배열을 배제해 나갔습니다. 이는 당시 혁신적이었으나 논란도 있었는데, 검토자들이 그 프로그램을 검증하기 어려웠기 때문입니다. 헤일스는 최악의 형태를 찾기 위해 유사한 방식을 사용하기를 희망했지만, 무한하게 반복되는 ‘채터링’ 구조는 큰 장애물이 되었습니다. “만약 무한히 전환하는 구조가 있다면, 컴퓨터로 해결하기는 어렵습니다.” 헤일스는 이렇게 설명했습니다.

 

이러한 구조들과 그 외의 복잡한 모양을 제거하기 위해서는 창의적인 방법이 필요했습니다. 그들은 문제를 단순화하기 위해 새로운 대칭 제약 조건을 도입하고, 그다음에 원래 문제로 되돌아가는 방식을 시도했습니다. “물리학에서 대칭이 있는 경우 보존 법칙이 따르는 것처럼, 수학에서도 대칭이 있으면 보존 법칙이 나타납니다.” 헤일스는 설명했습니다. 이러한 법칙들이 특정 구조를 배제하는 데 도움이 되었습니다.

 

그러나 새로운 가능성은 계속해서 나타났습니다. “이 문제가 어려울 거라는 건 알았지만, 항상 풀어낼 구조가 더 있었습니다.” 바자는 회상했습니다. “항상 ‘6개월만 더’라는 생각이 들었죠.” 5년이 흘러 학위 취득 시점은 지나갔고, 그는 서부로 이사해 결혼할 계획도 있었습니다. “이 문제가 반격이라도 하는 것처럼, 또다시 100년 동안 풀리지 않은 채 남을 수도 있겠다는 생각이 들었죠.” 미완성 증명을 남기는 것은 고통스러운 일이었지만, 그는 더 이상 연구를 지속할 여유가 없었습니다. 결국 바자는 2022년 8월에 졸업하고, 잠시 AI 스타트업에서 일한 뒤 인텔로 이직해 CPU를 공식 검증하는 일을 맡아 그의 원래 연구 분야로 돌아갔습니다.

 

이듬해 봄, 바자는 졸업식을 위해 피츠버그로 돌아왔습니다. 그와 헤일스는 많은 새로운 아이디어와 방법을 세세히 정리했지만, 여전히 견고한 정리를 도출하지 못한 점에 아쉬움을 표했습니다. 일주일 후, 헤일스는 한 가지 깨달음을 얻었습니다. 그들은 1946년에 라인하르트와는 별개로 문제를 연구하던 쿠르트 말러(Kurt Mahler)의 추측에 근접한 증명을 해낸 것이었습니다. 헤일스는 이렇게 말했습니다. “저는 늘 말러를 그저 라인하르트와 같은 일을 했던 사람으로 봤습니다. 단지 몇 년 늦게 했을 뿐이었죠.” 그러나 말러는 이 문제를 두 단계로 나눠 관찰함으로써 중요한 통찰을 제공했습니다. 그의 첫 번째 추측은 해답이 곡선과 직선이 결합된 평활한 다각형이라는 것이었고, 두 번째 추측은 둥근 팔각형이 최악의 형태라는 점에서 라인하르트와 동일했습니다. 헤일스는 그들이 첫 번째 단계에 매우 가까워졌음을 깨닫고 바자에게 한 달간 숙고할 시간을 달라고 요청했습니다.

 

그 한 달이 지나고, 둘은 이메일을 주고받기 시작했습니다. 새 구조를 발견하고는 배제하기를 반복하고, 의심과 피로를 인정하며 논의는 이어졌습니다. 한 달은 점점 길어져 마침내 1년이 되었습니다. 그러던 중 마침내 헤일스가 바자에게 메시지를 보냈습니다. “말러의 첫 번째 추측이 다시 가능해 보입니다. 거의 증명한 것 같아요.”

 

결국 6개월이 아니라 6년 만에 이룬 그들의 말러 첫 번째 추측의 증명은 260페이지에 달하는 방대한 작업이었고, 수많은 후보 구조를 탐구하며 헤일스가 처음 예상했던 것보다 훨씬 더 다양한 이론을 사용한 결과물이었습니다. 아직 동료 심사는 받지 않았지만, 비공식적으로 논문을 검토한 수학자들, 특히 헨리 코언과 캘리포니아 대학교 데이비스의 그렉 쿠퍼버그(Greg Kuperberg)는 헤일스의 신중한 작업 방식 덕분에 결과에 대한 신뢰를 표현했습니다.

 

하지만 쿠퍼버그는 “아직 결승선을 완전히 넘진 못했습니다”라고 덧붙였습니다. 때로는 이론이 발전하고 중간 단계를 해결하더라도, 문제는 수십 년간 해결되지 않은 채 남기도 합니다. 결국 헤일스의 케플러 추측 증명도 50년 전 헝가리 수학자 라슬로 페이예스 토트(László Fejes Tóth)가 개발한 접근법에 의존했습니다. “아마도 라인하르트를 완성하는 모든 아이디어가 갖춰져 있을 수도 있습니다. 아닐 수도 있죠.” 헤일스는 말했습니다. “그것은 여전히 의문 부호로 남겨둡니다.”