- 고차원 구형 적재 문제에서 Boaz Klartag가 1947년 Claude Ambrose Rogers 이후 가장 큰 폭의 효율 개선을 담은 짧은 원고를 4월 온라인에 공개함
- 새 방법은 임의의 격자에서 출발해 더 큰 타원체를 만든 뒤 Rogers의 절차로 조밀한 구형 적재를 구성하며, 한동안 밀려났던 기하학적 접근을 되살림
- Klartag의 구성은 차원 d에서 기존 다수 결과보다 약 d배 많은 구를 적재할 수 있어, 100차원에서는 약 100배, 100만 차원에서는 약 100만 배에 해당함
- 2023년 비격자적 기록 이후 커졌던 무질서한 적재 가능성 논의와 달리, 이번 결과는 고차원 최적 적재에서 질서와 대칭이 여전히 유력할 수 있음을 보여줌
- 암호학과 통신 응용에서 구형 적재 문제는 중요하지만, 이번 결과가 곧바로 응용되는 것은 아니며 볼록기하학과 격자 이론을 다시 잇는 계기가 될 수 있음
고차원 구형 적재에서 나온 큰 폭의 진전
- 구형 적재 문제는 공을 고차원 공간 안에 가능한 한 효율적으로 채우는 방법을 찾는 문제임
- 이 문제는 수세기 동안 수학자들을 끌어왔고, 암호학과 장거리 통신에도 중요한 응용 가능성이 있음
- 17세기 초 Johannes Kepler는 3차원 구를 식료품점의 오렌지처럼 쌓으면 공간의 약 74% 를 채울 수 있음을 보였고, 이것이 최적이라고 추측함
- 이 추측은 거의 400년이 지나서야 증명됨
- 더 높은 차원에서는 8차원과 24차원을 제외하면 최적 답을 아직 모름
- 수학자들은 오랫동안 더 나은 적재를 찾아왔지만, 개선은 작고 드물었음
- Boaz Klartag는 4월 공개한 짧은 원고에서 기존 기록을 큰 폭으로 넘어섰고, 일부 연구자들은 이 결과가 최적에 가까울 수 있다고 봄
격자에서 타원체로 이어진 오래된 아이디어
- 1905년 Hermann Minkowski는 격자(lattice) 로 구형 적재를 생각하는 방식을 세움
- 공간에 반복되는 점 배열을 만들고, 각 점 주위에 구를 그리는 방식임
- 특정 차원에서 최적 구형 적재를 찾는 문제는 점들이 가장 효율적으로 배치된 격자를 찾는 문제로 바뀜
- 2차원에서는 육각형 격자가 최적임
- 1947년 Claude Ambrose Rogers는 다른 관점을 내놓음
- 최적이 아닌 임의의 격자에서도 시작할 수 있음
- 각 점에 구를 그리는 대신, 한 점 주위에 타원체를 그려 표면이 격자의 다른 점에 닿되 넘어가지 않게 함
- 이 타원체를 출발점으로 조밀한 구형 적재를 만드는 알고리듬을 제시함
- Rogers 방식의 장점은 시작 격자가 특별히 효율적일 필요가 없다는 점임
- 올바른 타원체만 고르면 효율적인 구형 적재를 만들 수 있음
- 하지만 타원체는 구보다 다루기 어려움
- 구는 반지름 하나로 정해지지만, 타원체는 길이가 다른 여러 축으로 정해짐
- 차원이 높아질수록 늘릴 수 있는 방향과 가능한 모양이 급격히 늘어남
- 수학자들은 결국 Minkowski식 격자 접근으로 돌아갔고, 격자 이론에 더 집중하면서 Rogers의 기하학적 접근에서는 멀어짐
- 이 전략도 고차원 구형 적재를 개선했지만, 대부분 Rogers의 적재보다 작은 폭의 개선에 그침
볼록기하학 연구자가 되살린 Rogers 접근
- Klartag는 Weizmann Institute of Science의 수학자로, 주로 볼록기하학(convex geometry) 을 연구함
- 볼록한 도형은 안쪽으로 움푹 들어가지 않는 도형임
- 고차원에서 다양한 대칭을 포함하며, Klartag는 이런 도형을 강력한 수학적 도구로 봄
- 그는 격자와 구형 적재에 관심이 있었지만, 그 분야를 깊게 배울 시간이 없었음
- 지난해 11월 주요 프로젝트를 마친 뒤 일정이 비자, Tel Aviv University의 Barak Weiss에게 새 분야를 배우기 위한 멘토링을 요청함
- Weiss는 Klartag와 몇 명이 함께 문헌을 읽는 작은 세미나를 시작함
- Klartag는 Minkowski와 Rogers의 구형 적재 방법을 자세히 읽음
- Rogers가 타원체를 구형 적재로 바꾸는 방법을 읽은 뒤, Klartag는 수학자들이 왜 그 방법을 포기했는지 의문을 가짐
- 타원체는 볼록한 도형이므로, Klartag에게는 이를 조작하는 정교한 방법들이 있었음
- Rogers가 사용한 출발 타원체는 직관적이지만 비효율적이라고 판단함
- 더 큰 부피의 타원체를 만들 수 있다면 Rogers의 원래 절차로 새 적재 기록을 세울 수 있었음
무작위 성장으로 더 큰 타원체 만들기
- Klartag는 각 축을 따라 타원체 경계를 무작위 과정으로 키우고 줄이는 자신에게 익숙한 방법에서 출발함
- 경계가 충분히 확장되어 격자의 새 점에 닿으면, 그 방향의 성장을 멈춤
- 해당 점이 타원체 안으로 들어오지 않게 됨
- 다른 방향에서는 계속 부풀어 오르며 또 다른 점에 닿을 때까지 성장함
- 이 과정에서 타원체는 덜컥거리듯 멈추고 움직이며 주변 공간을 점진적으로 탐색함
- 시간이 지나면 평균적으로 타원체의 부피가 증가함
- Klartag의 핵심 질문은 이 부피 증가가 Rogers의 직관적 타원체를 넘어설 만큼 충분한지였음
- 무작위 과정은 실행할 때마다 다른 타원체를 만들었기 때문에, Klartag는 가능한 타원체 부피의 범위를 평가함
- 처음에는 Rogers의 타원체보다 충분히 큰 단일 타원체를 찾지 못함
- 무작위 성장 과정의 세부를 조정한 뒤, 1~2주 만에 때때로 새 기록을 세울 만큼 큰 타원체가 나온다는 사실을 증명함
약 d배 개선이 갖는 수학적 의미
- Klartag의 증명은 검증되었고, 새 출발 타원체를 구형 적재로 바꾸면 Rogers의 1947년 논문 이후 가장 큰 폭의 효율 개선을 냄
- 주어진 차원 d에서 Klartag의 방법은 기존 다수 결과보다 약 d배 많은 구를 적재할 수 있음
- 100차원 공간에서는 대략 100배 많은 구를 적재함
- 100만 차원 공간에서는 대략 100만 배 많은 구를 적재함
- Klartag는 구형 적재 분야를 몇 달 공부하고, 증명을 몇 주 작성한 뒤 중심 문제 하나를 크게 진전시킴
- 그의 볼록기하학 경험은 보통 별도 분야로 다뤄지던 기법을 구형 적재 문제에 적용하는 데 직접 작용함
- Gil Kalai는 이 결과를 “정말 놀라운 돌파구”라고 평가했고, 수학자들을 거의 100년 동안 흥분시킨 문제와 관련된 성과라고 봄
질서와 무질서를 둘러싼 논쟁
- Klartag의 결과는 고차원 최적 적재의 성격을 둘러싼 논쟁을 다시 살림
- 한동안 수학자들은 높은 대칭성을 가진 격자 기반 적재가 구를 가장 조밀하게 배열하는 최선의 방법이라고 여김
- 2023년에는 반복 격자에 깔끔하게 의존하지 않는 적재가 발견됐고, Klartag 이전의 기록이 됨
- 일부 수학자들은 이를 최적 구형 적재 탐색에서 더 많은 무질서가 필요하다는 증거로 봄
- Klartag의 작업은 다시 질서와 대칭이 유력할 수 있다는 생각을 뒷받침함
- 구형 적재가 얼마나 조밀해질 수 있는지는 여전히 논쟁 중임
- 일부 수학자들은 Klartag의 적재가 최적에 아주 가깝다고 봄
- 다른 수학자들은 아직 개선 여지가 있다고 봄
- University of Illinois, Chicago의 Marcus Michelen은 현재 무엇을 믿어야 할지 모르겠고 모든 가능성이 열려 있다고 말함
당장 응용보다 큰 분야 간 연결
- 구형 적재 문제의 답은 암호학과 통신 응용 가능성 때문에 중요함
- Hebrew University의 정보 이론가 Or Ordentlich는 이 문제가 엔지니어에게 크지만 진전이 적었기 때문에 이번 결과가 흥분을 불러온다고 말함
- 다만 Klartag의 결과가 그런 응용에 즉시 유용한 것은 아님
- Klartag는 자신의 작업이 Rogers 시대처럼 볼록기하학과 격자 이론이 더 연결되던 방식으로 돌아가는 계기가 되기를 바람
- 그는 볼록체에 대한 현재의 이해가 구형 적재를 넘어 격자 문제에도 유용할 수 있다고 봄
- Klartag의 목표는 두 분야가 지금보다 덜 단절되게 만드는 것임