🔢 mathematics

The lonely runner conjecture holds for nine runners

이 논문은 여덟 명의 주자에 대해 결과를 입증하는 데 이전에 사용되었던 방법을 개선함으로써 아홉 명의 주자에 대해 외로운 러너 추측이 참임을 증명한다.

원저자: Matthieu Rosenfeld

게시일 2026-01-28

📖 4 분 읽기🧠 심층 분석

원저자: Matthieu Rosenfeld

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

원형 달리기 트랙을 상상해 보세요. 이 트랙 위에는 각기 다른 속도를 가진 여러 명의 주자들이 달리고 있습니다. 어떤 이는 빠르고, 어떤 이는 느리며, 그들 중 누구도 정확히 같은 속도를 공유하지 않습니다.

**외로운 주자 추측(Lonely Runner Conjecture)**은 이 주자들에 관한 수학적 질문입니다. 이 질문은 다음과 같이 묻습니다: 모든 주자가 동시에 "외로워지는" 순간이 과연 존재할까요?

이 맥락에서 "외롭다"는 것은 모든 주자가 다른 모든 사람으로부터 멀리 떨어져 있음을 의미합니다. 구체적으로, 트랙의 둘레를 1이라고 할 때, 어떤 주자가 다른 모든 주자로부터 최소 $1/(k+1)$ 만큼의 거리를 두고 있다면 그 주자는 외로운 상태입니다 (여기서 $k$ 는 주자의 수입니다). 이 추측은 속도가 어떻게 정해지든, 모든 주자가 동시에 이 상태가 되는 특정한 시점이 반드시 존재한다고 주장합니다.

오랫동안 수학자들은 3, 4, 5, 6, 7, 8명의 주자에 대해서는 이것이 참임을 증명해 왔습니다. 하지만 9명의 주자에 대해서는 여전히 미스터리로 남아 있었습니다.

돌파구: 9명의 주자 사례 해결

이 논문에서 저자 마티외 로젠펠드(Matthieu Rosenfeld)는 이 추측이 9명의 주자에 대해서도 실제로 참임을 증명합니다.

그가 이를 어떻게 수행했는지, 간단한 비유를 통해 설명하겠습니다.

1. "불가능한" 시나리오

추측을 증명하기 위해 저자는 고전적인 논리 기법인 **귀류법(Proof by Contradiction)**을 사용합니다.
그는 반대의 상황을 가정하며 시작합니다: 만약 특정 속도를 가진 9명의 주자 집단이 존재하여, 그들이 결코 동시에 외로워질 수 없다고 가정해 봅시다.

만약 이런 "나쁜" 주자 집단이 존재한다면, 그들의 속도는 매우 특정한 숫자여야 합니다. 이 논문은 수학적 "울타리(공식)"를 사용하여, 만약 이 나쁜 집단이 존재한다면 그들의 속도의 곱이 너무 커질 수 없음을 보여줍니다. 즉, 이 숫자들의 크기에 대한 **상한선(upper limit)**을 설정하는 것입니다.

려 2. "배수" 탐정 작업

다음으로 저자는 탐정이 되어 단서를 찾습니다. 그는 다음과 같이 묻습니다: 만약 이 "나쁜" 주자 집단이 존재한다면, 그들의 속도는 어떤 숫자들에 의해 나누어떨어져야 하는가?

그는 일련의 논리적 규칙(보조 정리)을 사용하여, 가상의 주자들의 속도가 매우 긴 특정 숫자들의 목록(예: 17, 19, 23, 29 등, 그리고 64와 81 같은 숫자의 거듭제곱들)에 의해 나누어떨어져야 함을 찾아냅니다.

이를 다음과 같이 생각해 보세요: 만약 당신에게 비밀 코드(속도의 곱)가 있다면, 저자는 이 코드가 반드시 17을 위한 "열쇠", 19를 위한 "열키", 23을 위한 "열쇠" 등을 포함하고 있어야 한다고 증명하는 것입니다.

3. 모순

여기서 마법이 일어납니다.

상한선: 1단계의 "울타리"는 속도의 총 곱이 특정 거대한 숫자 $X$ 보다 작아야 한다고 말합니다.
하한선: 2단계의 "탐정 작업"은 속도의 곱이 너무나 큰 숫자들의 목록에 의해 나누어떨어져야 하므로, 그 결합된 곱이 $X$ 보다 커야 한다고 말합니다.

이는 마치 이렇게 말하는 것과 같습니다: "이 병은 구슬 100개만 담을 수 있다"라고 해놓고, 곧이어 "이 안에 있는 구슬의 무게는 구슬 200개를 담을 수 있는 병을 채울 만큼 무거워야 한다"라고 증명하는 것과 같습니다.

곱이 동시에 $X$ 보다 작으면서 동시에 $X$ 보다 클 수는 없으므로, 최초의 가정은 틀렸습니다. 그런 "나쁜" 9명의 주자 집단은 존재하지 않습니다. 따라서 9명의 주자에 대한 외로운 주자 추측은 참입니다.

컴퓨터의 역할

"그 많은 숫자를 어떻게 다 확인했나요?"라고 궁금할 수 있습니다.
논문은 모든 가능한 속도의 조합을 손으로 일일이 확인하는 것이 불가능하다고 인정합니다. 저자는 힘든 작업을 대신 수행할 특화된 컴퓨터 프로그램을 작성했습니다.

문제: 컴퓨터는 특정 복잡한 숫자 패턴이 틈(외로운 지점)을 남기지 않고 트랙을 "덮을" 수 있는지 확인해야 했습니다.
혁신: 저자는 단순히 표준 컴퓨터 솔버(마치 견과류를 깨기 위해 망치를 사용하는 것과 같은 방식)를 사용하지 않았습니다. 그는 맞춤형의 매우 효율적인 "백트래킹(backtracking)" 알고리즘을 구축했습니다.
- 미로에서 길을 찾는 것을 상상해 보세요. 그의 프로그램은 모든 경로를 다 걸어보는 대신, "여기서 왼쪽으로 꺾으면 10단계 뒤에 막다른 길에 부딪힐 것이니, 아예 그 길까지 가지 않겠다"라고 똑똑하게 판단합니다.
- 이러한 최적화를 통해 그의 프로그램은 이전의 시도들보다 훨씬 빠르게 작동했으며, 유사한 문제에 걸리는 시간을 32시간에서 50분으로 단축했습니다.

10명의 주자는 어떻게 되나요?

이 논문은 이 방법이 이론적으로 10명의 주자에게도 적용될 수 있지만, 수학적으로 매우 어려워진다는 점을 짧게 언급합니다. "울타리"는 훨씬 높아지며, 컴퓨터는 단일 컴퓨터 코어로 약 2년 동안 작업을 완료해야 할 정도로 거대한 숫자를 확인해야 합니다.

저자는 또 다른 연구자가 약간 더 빠른 "체 거르기(sieving)" 방법을 사용하여 10명의 주자 사례를 독립적으로 해결했다는 점을 언급하지만, 이 논문은 엄격하게 9명의 주자에 대한 증명과 그 과정에서 개선된 논리 및 코드에 초점을 맞춥니다.

요약

요약하자면, 이 논문은 다음 과정을 통해 수십 년 된 9명의 주자 문제를 해결했습니다:

"나쁜" 주자 집단이 존재한다고 가정합니다.
그러한 집단이 존재하려면 수학적으로 불가능한 숫자(허용된 공간에 담기에는 너무 큰 숫자)가 필요함을 증명합니다.
이러한 모순으로 이어지는 수학적 규칙을 검증하기 위해 영리하게 제작된 맞춤형 컴퓨터 프로그램을 사용합니다.

그 결과, 서로 다른 속도를 가진 9명의 주자가 달리는 어떤 트랙에서도 모두가 완벽하게 혼자가 되는 순간이 반드시 존재한다는 사실이 확인되었습니다.

기술 요약: 9명의 주자를 위한 외로운 주자 추측(The Lonely Runner Conjecture for Nine Runners)

문제 정의
본 논문은 1967년 윌스(Wills)가 처음 제안한 조합론적 수론의 오랜 미해결 문제인 **외로운 주자 추측(Lonely Runner Conjecture)**을 다룬다. 이 추측은 임의의 정수 $k \ge 1$ 과 $k$ 개의 서로 다른 정수 집합(주자의 속도를 나타냄) $v_1, \dots, v_k$ 에 대하여, 모든 주자가 "외로운" 상태가 되는 실수 시간 $t$ 가 존재한다고 가정한다. 수학적으로 이는 모든 $i$ 에 대해 $\|t v_i\| \ge 1/(k+1)$ 을 만족하여, 각 주자가 단위 원 위에서 원점으로부터 최소 $1/(k+1)$ 만큼 떨어져 있는 $t$ 가 존재함을 의미한다.

이 추측은 작은 값의 $k$ ( $k=7$ 까지)에 대해서는 검증되었으나, 일반적인 경우에는 여전히 미해결 상태로 남아 있다. 본 논문은 특히 9명의 주자( $k=9$ )인 경우를 목표로 한다.

방법론
증명 전략은 8명의 주자에 대한 추측을 확립한 저자의 이전 연구를 기반으로 구축되었다. 핵심 논거는 가상의 "최소 반례(minimal counterexample)"의 성질을 이용한 귀류법에 기초한다.

가분성 제약 조건으로의 환원:
증명은 말리키오시스(Malikiosis), 산토스(Santos), 슈뮈라(Schymura)가 도출한 경계값(정리 1)을 활용하며, 이는 만약 $k$ 에 대해 추측이 성립한다면, 최소 반례에 포함된 속도들의 곱이 특정 임계값을 초과할 때 $k+1$ 에 대해서도 추측이 성립함을 시사한다. 결과적으로 $k+1$ 에 대해 추측을 증명하기 위해서는, 특정 경계값에 의해 부과된 가분성 제약을 만족하면서 "외로운 주자 성질(LR property)"을 위반하는 $k$ 개의 속도 집합이 존재하지 않음을 보여주는 것으로 충분하다.
제수(Divisors)를 위한 일반화된 보조정리:
저자들은 이전의 보조정리(보조정리 3)를 강화하고 일반화한 보조정리 6을 도입한다. 이 보조정리는 특정 정수 $d$ 가 LR 성질을 결여한 8개 정수의 속도 곱을 반드시 나누어야 한다는 조건을 설정한다.
- 이 보조정리는 계수 $c$ 를 도입하고 $9cd$에 대한 속도들을 고려한다.
- 이는 3과 9로 나누어지는 속도의 개수에 관한 특정 가분성 조건(보조정리 5로부터 유도됨)을 포함한다.
- 이 조건은 특정 GCD 및 가분성 제약을 만족하는 8개 속도 집합에 대하여, LR 성질을 만족하는 시간 $t$ 가 존재함을 검증할 것을 요구한다.
컴퓨터 보조 검증 (집합 커버 재정의):
보조정리 6의 조건을 검증하는 것은 계산 집약적이다. 저자들은 이 문제를 집합 커버(set cover) 문제로 재정의하였다(보조정리 7).
- 정수 $v$ 는 정수 $j$ 를 "커버(cover)"한다, 만약 $\| \frac{jv}{9cd} \| < 1/8$ 이면 그러하다.
- 목표는 필요한 정수들을 모두 커버하면서 가분성 제약을 만족하는 "나쁜(bad)" 8-튜플이 존재하지 않음을 검증하는 것이다.
- 저자들은 이전의 $k=7$ $k = 7$ 작업보다 크게 최적화된 백트래킹 알고리즘을 구현하였다:
  - 커버된 위치를 위한 비트셋(bitsets) 사전 계산.
  - 후보 원소가 새로 커버할 수 있는 최대 정수 개수에 기반한 가지치기(pruning) 전략.
  - 중복된 탐색 경로를 제거하기 위한 메모이제이션(memoization).
- 저자들은 SAT 솔버 접근 방식(Cardinality-CDCL 및 Minicard 사용)도 테스트하였으나, 이 특정 문제 구조에서는 자체 개발한 백트래킹 구현이 훨씬 더 빠르다는 것을 발견하였다.

주요 기여 및 결과

9명의 주자에 대한 증명: 본 논문은 9명의 주자에 대해 외로운 주자 추측이 성립한다는 완전한 증명을 제공한다.
제수의 식별: 컴퓨터 프로그램을 통해 보조정리 6을 적용함으로써, 저자들은 9명의 주자에 대한 임의의 최소 반례의 속도 곱을 반드시 나누어야 하는 정수 집합 $S$ (64, 81, 25와 같은 소수의 거듭제곱 및 191까지의 소수 포함)를 식별하였다.
모순: 집합 $S$ 의 원소들(서로소인)의 곱은 약 $9.09 \times 10^{79}$ 이다. 그러나 최소 반례에서의 속도 곱에 대한 이론적 상한값(결론 2로부터 도출됨)은 약 $8.47 \times 10^{79}$ 이다. 요구되는 제수들의 곱이 속도의 최대 가능한 곱을 초 exceed하므로, 그러한 반례는 존재할 수 없다.
알고리즘 개선: 본 논문은 $k=7$ 검증 실행 시간을 32시간에서 50분으로 단축시킨 구체적인 구현 개선 사항을 상세히 기술하며, 이를 통해 더 복잡한 $k=9$ 검증을 가능하게 하였다.

의의 및 주장
저자들은 이 결과가 알려진 외로운 주자 추측의 범위를 7명에서 9명으로 확장했다고 밝힌다. 그들은 사용된 기법이 특정 주자 수에 대해 이론적으로 적용 가능하지만, 계산 비용이 급격히 증가한다는 점을 언급한다.

독립성: 저자들은 제출 직전 트라쿨통차이(Trakulthongchai)가 $k=9$ 와 $k=10$ 에 대한 증명을 독립적으로 발표했음을 인정한다. 트라쿨통차이의 작업 역시 $k=7$ 증명을 기반으로 하며, 본 논문의 방법보다 대략 100배 빠른 "영리한 체질(sieving) 접근 방식"을 사용하는 것으로 보인다.
향 향후 전망: 본 논문은 $k=10$ 으로의 확장이 가능한지에 대해 논의한다. 방법론은 적응 가능하지만, 약 263까지의 소수를 검증하는 데 드는 계산 비용은 단일 코어에서 2년이 걸릴 것으로 예상된다. 저자들은 작은 소수의 거듭제곱을 고려하는 등의 자신들의 개선 사항을 트라쿨통차이의 체질 접근 방식과 결래하면 $k=10$ 케이스를 더 다루기 쉽게 만들 수 있다고 제안하지만, 이를 직접 해결했다고 주장하지는 않는다.

요약하자면, 본 논문은 정교한 이론적 보조정리와 고도로 최적화된 컴퓨터 검증의 결합을 통해 $k=9$ 케이스를 성공적으로 해결하였으며, 더 높은 $k$ 를 해결하기 위한 광범위한 노력에 기여함과 동시에 그로부터 도움을 받는 방식으로 연구를 위치시키고 있다.