🔢 mathematics

Resolution of Erdős Problem #728: a writeup of Aristotle's Lean proof

이 논문은 GPT-5.2 Pro와 Aristotle 시스템의 결합을 활용하여 이항 계수의 새로운 소수별 분석을 통해 팩토리얼 가해성(factorial divisibility)에서의 로그 간격 현상을 입증하는 정식 Lean 증명을 생성함으로써, 에르되시 문제 #728에 대한 최초의 완전 자율 AI 해결책을 제시한다.

원저자: Nat Sothanaphan

게시일 2026-01-27

📖 4 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Nat Sothanaphan

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

개요: AI 수학자 팀

평생을 거대한 미해결 퍼즐인 '할 일 목록'을 남기며 살았던 유명하고 은퇴한 수학 천재 폴 에르되시(Paul Erdős)를 상상해 보세요. 이 퍼즐 중 하나인 #728은 수십 년 동안 손도 대지 못한 채 남아 있었습니다.

최근, 초지능 AI(GPT-5.2 Pro)와 특화된 수학 검증 로봇(Aristotle)으로 구성된 팀이 마침내 이 문제를 해결했습니다. 그들은 단순히 답을 추측한 것이 아니라, 컴퓨터가 100% 정확하다고 검증할 수 있는 엄밀하고 단계적인 증명을 구축했습니다. 이 논문의 저자들은 단순히 그 컴퓨터 코드를 인간이 읽을 수 있는 이야기로 번역하고 있는 것입니다.

퍼즐: 팩토리얼의 균형 잡기

이 문제는 팩토리얼(5! = 5 × 4 × 3 × 2 × 1과 같은 숫자들)에 관한 질문을 던집니다.

당신에게 $n!$ 을 나타내는 거대한 블록 더미가 있다고 상상해 보세요. 당신은 이 큰 더미 안에 두 개의 작은 탑 $a!$ 과 $b!$ , 그리고 세 번째 작은 탑 $k!$ 를 완벽하게 끼워 맞출 수 있는지 알고 싶습니다. 즉, 남는 블록 없이 딱 들어맞아야 합니다.

수학적으로 이는 다음과 같습니다: $a! \times b!$ 가 $n! \times k!$ 를 나누어 떨어지게 하는가?

퍼즐의 핵심은 다음과 같습니다: 그 "간격"( $k$ )은 얼마나 커질 수 있는가?

$k$ 가 아주 작다면, 블록을 끼워 맞추기가 쉽습니다.
$k$ 가 아주 크다면, 보통 불가능합니다.
비결은 $k$ 가 충분히 흥미로우면서도 블록이 들어맞지 않을 정도로 너무 크지는 않은, 이른바 "골디락스 존(Goldilocks zone, 적절한 지점)"을 찾는 것입니다.

AI 팀은 이 간격( $k$ )이 전체 숫자의 로그(logarithm) 크기 정도가 되는 상황이 무한히 많이 존재한다는 것을 증명했습니다. 쉬운 말로 설명하자면: 만약 전체 블록의 수가 백만 개라면, 간격은 약 14가 될 수 있습니다. 만약 숫자가 십억 개라면, 간격은 약 20이 될 수 있습니다. 매우 느리게 성장하지만, 분명히 성장합니다.

전략: "올림(Carry)" 게임

이 문제를 해결하기 위해 수학자들은 소수(2, 3, 5, 7 등)의 관점에서 문제를 바라봐야 했습니다. 그들은 더하기에서의 "올림"과 같은 규칙인 **쿠머의 정리(Kummer's Theorem)**를 사용했습니다.

비유: 넘치는 양동이
특정한 언어(진법 $p$ )로 숫자를 더하고 있다고 상상해 보세요.

두 자릿수를 더했을 때 결과가 한 칸에 담기에 너무 크면, 다음 칸으로 "올림(carry)"을 합니다.
목표: AI는 어떤 숫자( $m$ )를 두 배로 만들었을 때, 많은 올림이 발생하는(마치 양동이가 반복해서 넘치는 것과 같은) 상황을 찾아내야 했습니다.
장애물: 동시에, AI는 $m$ 바로 다음에 오는 숫자들( $m+1, m+2...$ )이 "스파이크(spike)"—즉, 균형을 깨뜨릴 정도로 특정 소수에 의해 갑자기 거대하게 나누어지는 현상—를 가지지 않도록 보장해야 했습니다.

이는 마치 외줄 타기와 같습니다:

외줄 타기 ("올림" 조건): 당신은 "올림이 풍부한" 숫자를 골라야 합니다. 그 숫자를 두 배로 만들었을 때, 양동이가 가능한 한 자주 넘쳐야 합니다. 이것이 방정식이 작동하도록 돕는 나누어 떨어짐의 "안전망"을 만들어 줍니다.
스파이크 ("나쁜" 조건): 당신은 다음 몇 개의 정수가 거대한 소수의 거듭제곱으로 나누어지는 "스파이크"를 피해야 합니다. 이러한 스파이크는 당신을 외줄에서 떨어뜨릴 수 있습니다.

어떻게 해결책을 찾았는가

AI는 단순히 무작위로 숫자를 고른 것이 아닙니다. 그것은 계수 논법(counting argument)(통계적 전략)을 사용했습니다.

탐색 영역: 그들은 거대한 범위( $M$ 에서 $2M$ 까지)를 살펴보았습니다.
필터링: 이 범위 내의 숫자 중 "나쁜" 숫자(올림이 충분하지 않거나 스파이크가 있는 숫자)가 얼마나 되는지 계산했습니다.
결과: 그들은 "나쁜" 후보의 수가 범위 내의 전체 후보 수보다 실제로 더 적다는 것을 증명했습니다.
결론: "나쁜" 숫자보다 "좋은" 숫자가 더 많기 때문에, 더미 안에는 반드시 적어도 하나의 "좋은" 숫자가 남아 있어야 합니다.

이는 마치 이렇게 말하는 것과 같습니다: "만약 당신에게 구슬 1,000개가 들어있는 병이 있고, 그중 900개가 빨간색(나쁜 것)이라면, 반드시 100개의 파란색(좋은 것)이 남아 있을 것입니다." AI는 충분히 큰 병이라면 언제나 "좋은" 구슬이 존재한다는 것을 증명했습니다.

이것이 왜 중요한가 (논문에 따르면)

최초의 AI 단독 증명: 이것은 AI 시스템이 에르되시의 유명한 문제 중 하나를 자율적으로 해결하고, 인간이 검증할 수 있는 형식적 증명을 만들어낸 첫 번째 사례입니다.
"로그 간격": 그들은 간격이 로그 크기가 될 수 있음을 확인했습니다. 논문은 수학자 테렌스 타오(Terence Tao)가 제안한 것처럼 간격이 잠재적으로 약간 더 커질 수도 있다고 언급하지만, 이 증명은 견고하고 보장된 기준선을 확립합니다.
방법론: 사용된 방법(올림을 계산하고 스파이크를 피하는 것)은 과거 에르되시가 사용했던 기술과 유사하지만, 여기서는 더 복잡하고 움직이는 목표물에 적용되었습니다.

요약

이 논문은 AI 팀이 40년 된 수학 퍼즐을 어떻게 해결했는지에 대한 보고서입니다. 그들은 복잡한 팩토리알 방정식이 완벽하게 균형을 이루는 특정 숫자 집합을 항상 찾을 수 있다는 것을 보여주었습니다. 그들은 숫자를 넘치는 양동이(올림)처럼 취급하였고, 잘못된 곳에 너무 많이 쏟아지지 않으면서도 유용할 만큼 충분히 넘치는 양동이를 항상 찾을 수 있다는 것을 증명함으로써 이 문제를 해결했습니다.

기술 요약: Erdős 문제 #728의 해결

문제 정의
본 논문은 팩토리얼 가분성(factorial divisibility) 조건 하에서 간격 $k := a + b - n$ 의 최대 가능 크기를 조사하는 Erdős 문제 #728을 다룬다:
$a! b! \mid n! (a + b - n)!$
추가적인 제약 조건이 없다면, $a$ 와 $b$ 를 매우 크게 잡음으로써(예: $a, b$ 를 매우 크게 설정) $k$ 가 임의로 커지는 자명한 해들이 존재한다. 이 문제를 비자명하게 만들기 위해, 저자들은 $a$ 와 $b$ 가 극단적인 값으로부터 떨어져 있어야 한다는 조건, 즉 어떤 $0 < \varepsilon < 1/2$ 에 대하여 $\varepsilon n \le a, b \le (1-\varepsilon)n$ 이라는 조건을 부과한다. 목표는 이러한 제약 조건 하에서 $k$ 가 $n$ 에 비해 얼마나 커질 수 있는지를 결정하는 것이다.

방법론 및 증명 전략
증명은 팩토리얼 가분성 조건을 이항 계수와 $p$ -진 발란션(p-adic valuation)에 관한 문제로 변환함으로써 진행된다.

이항 계수 가분성으로의 환원:
$n = 2m$ , $b = m$ , $a = m + k$ 로 설정함으로써, 원래의 조건은 다음과 동치이다:
$\binom{m+k}{k} \mid \binom{2m}{m}$
이는 모든 소수 $p$ 에 대하여, 좌변의 $p$ -진 발란션이 우변의 $p$ -진 발란션보다 작거나 같음을 보여야 함을 의미한다:
$\nu_p\left(\binom{m+k}{k}\right) \le \nu_p\left(\binom{2m}{m}\right)$
Kummer의 정리를 이용한 발란션 분석:
Kummer의 정리를 사용하여, $\nu_p\left(\binom{2m}{m}\right)$ 은 기저 $p$ 에서 $m + m$ 을 더할 때 발생하는 올림(carry)의 횟수와 동일함을 식별한다. $\nu_p\left(\binom{m+k}{k}\right)$ 은 연속된 블록 $m+1, \dots, m+k$ 내의 임의의 항의 최대 발란션인 $V_p(m, k)$ 에 의해 상한이 정해진다.
충족해야 하는 핵심 부등식은 다음과 같다:
$V_p(m, k) \le \kappa_p(m)$
여기서 $\kappa_p(m)$ 은 기저 $p$ 에서 $m+m$ 의 올림 횟수이다.
소수별 분석:
저자들은 소수 $p$ 의 크기와 $k$ 의 상대적 크기에 따라 두 가지 영역으로 분석을 나눈다:
- 큰 소수 ( $p > 2k$ ): 이 범위에서는 부등식이 자동으로 성립한다. 구간의 길이 $k$ 가 $p/2$ 보다 작기 때문에, 블록 $m+1, \dots, m+k$ 내에서 $p$ 로 나누어지는 수는 최대 하나뿐이다. 만약 어떤 항이 높은 거듭제곱 $p^J$ 로 나누어진다면, $m$ 의 기저 $p$ 전개는 $m$ 을 두 배로 만들 때 적어도 $J$ 번의 올림을 강제하여 조건을 만족시킨다.
- 작은 소수 ( $p \le 2k$ ): 이것이 주요 난관이다. 저자들은 큰 구간 $[M, 2M]$ $[M, 2 M]$ 내에서 모든 $p \le 2k$ $p \leq 2 k$ 에 대해 다음 두 조건을 동시에 만족하는 정수 $m$ $m$ 을 찾기 위해 확률적 카운팅 논법을 사용한다:
  - 올림이 풍부함 (Carry-Rich): $m$ 의 기저 $p$ 전개는 처음 $L_p$ 개의 자리에서 많은 숫자가 $\lceil p/2 \rceil$ 이상을 가진다. 이는 $m$ 을 두 배로 만들 때 높은 수의 올림( $\kappa_p(m)$ )을 강제한다.
  - 스파이크가 없음 (Spike-Free): 블록 $m+1, \dots, m+k$ 내의 어떤 정수도 비정상적으로 높은 $p$ 의 거듭제곱으로 나누어지지 않는다 (즉, $V_p(m, k)$ 가 임계값 $J_p + t(M)$ 미만으로 유지된다).
합집합 상한(Union Bound)을 통한 존재성 증명:
저자들은 올림 조건이나 스파이크 조건을 만족하지 못하는 정수 $m$ 들의 "나쁜(bad)" 집합을 정의한다. 큰 숫자의 분포에 대한 Chernoff bound와 스파이크 조건에 대한 단순 카운팅을 사용하여, 이 나쁜 집합들의 총 측도가 구간 $[M, 2M]$ 의 크기보다 엄격히 작음을 보인다. 결과적으로, 관련된 모든 소수에 대해 가분성 조건을 동시에 만족하는 "좋은(good)" $m$ 이 존재한다.

주요 결과
본 논문은 **정리 1 (로그 간격 창)**을 확립한다:
임의의 상수 $0 < C_1 < C_2$ 와 $0 < \varepsilon < 1/2$ 에 대하여, 다음을 만족하는 삼조 $(a, b, n) \in \mathbb{N}^3$ 가 무수히 많이 존재한다:

$\varepsilon n \le a, b \le (1-\varepsilon)n$
$a! b! \mid n! (a + b - n)!$
$C_1 \log n < a + b - n < C_2 \log n$

이 구성은 $n$ 에 대해 로그 함수적으로 성장하는 간격 $k$ 를 산출한다. 저자들은 현재의 증명이 $k \asymp \log n$ 을 도출하지만, 추가적인 정교화를 통해 $k = \exp(c\sqrt{\log n})$ 까지 확장될 가능성이 있음을 언급하였으나, 현재의 서술은 로그 영역에 집중하고 있다.

의의 및 주장

최초의 AI 해결 Erdős 문제: 저자들은 이것이 "AI 시스템에 의해 완전히 자율적으로 해결된 최초의 Erdős 문제"라고 주장한다. 사용된 시스템은 GPT-5.2 Pro와 Harmonic의 정리 증명기인 "Aristotle"의 조합이다.
형식 검증: 증명은 Lean 정리 증명기에서 형식적 증명으로 생성되었으며, 이후 본 서술에 제시된 비형식적 수학 체계로 번역되었다.
방법론적 기여: 이 연구는 중심 이항 계수(central binomial coefficients)의 약수와 관련하여 Erdős와 Pomerance가 수행했던 기존 기법을 확장한다. "올림이 적은(carry-poor)" 정수(올림이 적은 경우)나 고정된 간격 크기에 초점을 맞춘 이전 연구들과 달리, 이 증명은 $k \asymp \log n$ 크기의 성장하는 창을 다루기 위해 "올림이 풍부한(carry-rich)" 정수를 구성한다.
독립성: 저자들은 자신들의 작업 이후, Carl Pomerance가 독립적으로 유사한 결과를 도출하였으며, Erdős 문제 #729 및 #401을 해결하기 위해 이 논증의 수정된 형태가 사용되었음을 언급하였다.

본 논문은 (더 큰 간격의 가능성을 언급하며) 절대적인 최강의 형태의 문제를 해결한다고 주장하는 것이 아니라, Erdős가 제기한 특정 로그 간격 질문을 성공적으로 해결했음을 주장한다.