요약
AI가 내놓은 o(n log n) 정수 곱셈 알고리즘을 기존 기록 보유자가 "그럴듯하다"고 평가했습니다.
2021년 O(n log n) 정수 곱셈 알고리즘을 발표한 UNSW 시드니의 수학자 데이비드 하비가 쓴 메모입니다. 미국의 한 기술 기업이 AI 모델이 쓴 수학 논문을 GitHub에 대량으로 올렸고, 그중 한 편이 이 기록을 깼다고 주장했습니다.
왜 중요한가
- O(n log n)은 최적이라고 널리 믿어졌기에, 결과가 맞다면 정수 곱셈의 한계에 대한 통념이 뒤집힙니다.
- log n의 지수를 2^-182만큼 줄인 작은 차이지만, 하비는 이전의 어떤 개선보다 지수적으로 큰 진전이라고 봤습니다.
- 하비는 이런 결과가 잦아지면 사람이 수학 논문의 저자로 인정받기 어려워질 것이라고 내다봤습니다.
핵심 내용
- 하비는 논문을 읽다 포기하고, Claude Fable 5.1에게 질문을 거듭하며 2주 동안 논증을 따라갔다고 밝혔습니다.
- 공략 대상은 FFT(고속 푸리에 변환)의 기본 연산인 버터플라이로, 그는 이 비용을 빛의 속도 같은 한계로 여겨 왔다고 했습니다.
- 배열 하나는 못 줄여도 여러 배열을 함께 변환하면 연산을 조금 아끼는 장치를 만들고, 이를 재귀로 키워 지수를 1 아래로 내립니다.
- 하비는 이 장치를 꼼꼼히 확인했지만, 튜링 기계 모델의 데이터 재배치 비용은 아직 살펴보지 못했다고 했습니다.
- 지수는 벌써 약 0.9983까지 내려갔고, 지금의 방식으로는 1/2 아래로 가기 어렵다고 봤습니다.
HN 반응
- 맨 위 댓글은 Lean(증명을 컴퓨터로 검증하는 언어)으로 이 결과를 이미 형식화했고 지수를 더 낮추는 중이라고 알렸습니다.
- 사람이 이해하지도 못한 AI 산출물에 무보수로 기여할 이유가 있느냐는 비판에, 와일스의 페르마 증명도 이해되기까지 몇 년 걸렸다는 반론이 나왔습니다.
이 결과는 @platypii와 제가 Lean(Mathlib의 TM2 기계 기준)으로 완전히 형식화했습니다. 지수는 계속 개선하고 있으며 현재 1-2^-14.38입니다. https://github.com/platypii/integer-mult-bounds-lean
기여는 언제든 환영합니다!
그럼 이 모델들한테 대형 과제를 하나 내 보죠.
저는 진짜 증가율이 O(n(log(n))^(1-f(n)))일 거라고 추측해요. 여기서 f(n)은 n이 커질수록 천천히 증가하는 함수고요.
그러니까 정수가 클수록 곱셈이 더 효율적이 된다는 거죠.
전 세계의 AI들이여, 이걸 목표로 삼아서 앞으로 몇 세기 동안 실컷 즐겨 보세요!!
f(n)이 1로 수렴한다는 조건을 빼먹으셨네요. 그러면 쉬운 과제가 되겠는데요.
네, n이 무한대로 갈 때 f(n)이 1로 간다는 게 목표로 삼을 만한 거죠. 거기에 얼마나 천천히 가느냐에 따라 증가율이 사실상 O(n)이 될지, 그보다 약간 큰 무언가가 될지 갈리겠지만, 그런 다듬기는 나중에 해도 돼요.
이거 건강한 상황 같지가 않네요.
바로 다음 줄에 이렇게 나옵니다.
그러니까 이 글은 통째로 저자가 이해한 내용에 관한 것입니다. (참고로 저자 David Harvey는 2014년과 2019/2021년에 정수 곱셈의 큰 진전을 이끈 사람입니다.)
이건 교과서적인 갤만 기억상실(Gell-Mann amnesia)이에요. 저자가 논문을 읽지 않았는데 그걸 어떻게 알 수 있죠? 관련 지식이 있는 사람이라 해도, 지금 듣는 말이 정말 논문에 있는 내용인지 어떻게 압니까? LLM은 틀린 소리를 자신만만하게 늘어놓는 일이 늘 있어요. 맞는 답을 내놓을 때와 틀린 답을 내놓을 때의 방식에 차이가 없으니까요. LLM은 사람들한테 이제 자기가 모든 분야의 전문가라고 믿게 만드는 데 놀랄 만큼 능해 보여요. "파고든다"는 건 그런 일이 벌어질 기회를 점점 더 많이 주는 것일 뿐이고요.
저자는 이미 이 주제에서 세계 최고의 전문가입니다.
Fable이 OpenAI 논문에 없는 다른 o(n log n) 알고리즘을 만들어 냈을 수도 있다는 말씀은 맞습니다. 하지만 (가능성이 낮기도 하거니와) 그건 중요하지 않습니다. 저자가 말하는 건 "주된 결과가 어쩌면 옳을 수도 있다"는 믿음이지, OpenAI의 논문이 반드시 옳다는 게 아니기 때문입니다. 논증이 논문에서 나왔든 Fable에게서 나왔든, 관심사는 곱셈이 정말 o(n log n) 시간에 가능하느냐입니다. 요점은 OpenAI의 논문과 그것에 대한 Fable의 설명, 그리고 저자의 이해 사이 어딘가에 진짜 아이디어가 있다는 것입니다.
수학자들은 수십 년 동안 바로 이런 식으로 논문을 평가해 왔습니다. 이 결과가 참일 수 있는 길이 있는가? 여기에 도움이 될 만한 실질적인 아이디어가 있는가? 몇몇 세부 사항만 채우면 참일 가능성이 높다고 확신할 만큼 논증을 이해했는가? 마지막 단계, 즉 세부 사항을 실제로 채우는 일은 그것을 다른 사람에게 가르치거나 자기 말로 다시 쓸 때 이루어집니다.
갤만 기억상실은 자기 연구를 토대로 한 논문을 논하는 해당 분야 세계 최고 전문가에게는 사실 해당되지 않습니다. 자기가 전문가가 아닌 주제를 논하는 전문가라면 해당될 수 있겠지만요.
제가 David Harvey를 개인적으로 알지 못했다면(10년 전 일이지만) 저도 동의했을 겁니다. 요즘 AI에 대한 제 입장을 다시 생각하는 중인데, 여전히 불안한 구석이 많긴 해도 "논문을 다른 모델에 넣고 기술적인 부분을 완전히 이해할 때까지 설명하게 한다"는 그의 접근법이 수학을 소화하는 방법으로서 점점 유효해지고 있다는 점은 마지못해 인정합니다. 이 방식을 쓰려면 엄청나게 원칙을 지켜야 합니다. 그런데 David가 바로 그런 사람입니다.
이게 여러모로 흥미롭게 정곡을 찔렀나 보네요!
아주 그럴듯한 수학 박사 사칭범이 있다고 해 봅시다. 이 사람이 미리 준비한 똑똑해 보이는 말로 증명을 이해했고 맞는 것 같다고 맞장구친다면, 그 증명이 맞는 게 되나요?
대부분은 아니라고 하겠죠. 이 사람이 사칭범이라는 걸 아니까요. 그걸 모르는 다른 사람들은 증명이 타당하다고 믿을지도 모르고요.
아주 간단한 사고 실험이지만, 누군가가 "이해했다"고 말하거나 동의한다는 사실은 그 주장의 타당성에 아무런 무게도 싣지 못한다는 결론을 내릴 수 있습니다.
OpenAI의 증명이 가짜라는 생각은 수학자들의 반응과 어긋납니다. 가짜였다면 수학자들이 이번 발표를 언급할 만큼 중요하게 여기지 않았을 겁니다[1,2]. vixra에는 그런 글이 늘 꾸준히 올라오니까요. 해설과 단순화를 쓰는 일도 못 했을 거고요. 그런 글이 arxiv에 매일 여러 편 올라옵니다(arxiv에서 OpenAI를 검색해 보세요).
어쩌면 수학자들이 더는 증명이 타당한지 가장 잘 판단하는 사람이 아닐 수도 있습니다. 하지만 무엇이 해결됐다는 건지 이해할 수 있는 사람은 그들뿐입니다.
최고 수준의 수학자들이 이 결과를 진지하게 받아들이고[3] 강연까지 열어 설명하는데도, 여기서는 집단 정신병이라며 일축되는 걸 보니 정말 이상합니다. [1] https://smf.emath.fr/actualites-smf/20-10-26-communique-sur-lavenir-de-la-recherche-mathematique [2] https://www.mathsoc.jp/publicity/news20261016.html [3] https://terrytao.wordpress.com/2026/10/19/a-sketch-of-the-proof-of-non-existence-of-siegel-zeroes/
그래도 증명이 쓸모 있는지, 통찰을 주는지 판단하는 데는 여전히 수학자들이 최고인 것 같아요. AI는 보상 해킹(reward hacking)을 하면서 무슨 수를 써서라도 이기려고 들 텐데, 이 문제들을 따내야 할 트로피로 본다면 상관없겠지만, 원래 의도한 정신으로 대한다면 그렇게 좋지 않죠.
OpenAI(주로)가 AI로 트로피 사냥을 하려는 그 유명한 문제들이 유명한 이유는 에르되시 같은 인간 수학자가 그 문제를 풀어 가는 과정에서 새로운 수학이 발전할 만한 비옥한 땅이라고 알아보는 안목이 있었기 때문이에요.
AI가 창의성, 호기심, 지속적 학습 같은 걸 해낼 수 있게 되기 전까지는, 수학을 근본적으로 발전시키고 적용할 새 도구를 만드는 일에서 AI는 계속 인간에게 의존할 거예요. 인간이 그렇게 하려면 동료들이 내놓은 도전 과제에서 영감을 받는 게 도움이 되는데, AI가 이런 인간의 과제를 푸는 게 그토록 역효과를 내는 이유가 그겁니다. 제 꼬리를 먹는 뱀이죠.
어떻게 그렇게 확신하시죠? 인간 수학자가 쓸모와 통찰을 판단할 수 있다는 건 압니다. 하지만 AI가 그걸 더 잘할 수 있는지는 우리가 잘 모르잖아요. 그걸 평가하는 체계를 만들어 본 사람이 없는 걸로 알고 있어요.
기업 가치가 1조 달러 안팎인 회사가 낸 글은 vixra에 거의 없죠.
그 비유대로라면 진실은 아직 신발 끈을 매고 있는 중입니다.
모든 증명을 분석해서 모순이 있는지 없는지 찾는 데는 시간이 걸려요.
> 아주 간단한 사고 실험이지만, 누군가가 "이해했다"고 말하거나 동의한다는 사실은 그 주장의 타당성에 아무런 무게도 싣지 못한다는 결론을 내릴 수 있습니다.
글쎄요, 원래 항상 그렇지 않았나요? 주장하는 사람이 사칭범이든 아니든 상관없이, 직접 그 주제를 파고들어서 스스로 판단하거나, 전문가들 사이에 합의가 이루어질 때까지 기다리거나 둘 중 하나죠.
제 말은, 2026년인 지금은 인터넷이 보급돼 거짓말이 판치고, 게다가 AI가 등장해서 영상 증거 같은 진실의 닻까지 없애 버렸으니, 똑똑한 사람이라면 누구나 진실의 조작적 정의에 대해 한동안 곰곰이 생각해 봤을 거라고 믿어요. 그래서 출처가 사칭범이 아니라는 지식에 의존하지 않는 무언가를 이제는 갖고 있을 테고요.
네, 객관적으로 진실을 추구한다는 관점에서는 말씀에 동의해요. 어렵고, 현실적으로 불가능할 때도 많죠.
2년쯤 전, AI가 한창 유행하기 전에도 그랬어요. 논란, 과학 사기 조직, "논문 공장(paper mills)"을 검색해 보세요.
이제 그 박사 "사칭범"이 지난 몇 달 사이에 역사상 누구보다 눈에 띄는 수학적 진전을 이뤘다고 상상해 보세요.
그러면 그 논증의 결론이 좀 달라질 것 같은데요.
아니면 그 박사 사칭범이 Lean 구성 요소의 건전성(soundness) 버그를 발견해서 악용했을 수도 있죠.
그 사칭범이 만든 증명을 이해할 수 있는 사람이 없으니, 알 도리가 없어요.
Lean 증명 검사기는 독립적인 구현이 많이 있습니다.
https://arena.lean-lang.org/
같은 버그가 전부에 들어 있을 가능성은 극히 낮습니다.
정말 그런가요? 진짜 궁금해서 묻는 건데, arena에서 언급되는 것 중 제가 본 건 전부 Claude로 생성한 것이었고, 무작위로 몇 개 확인해 봤더니 전부 Claude가 커밋한 기록이 있더라고요.
LLM이 얼마나 만들었는지는 모르겠지만, 그래도 이걸 독립적인 구현이라고 부를 수 있나요?
네, 부를 수 있죠? Claude는 결정적인 부분이 거의 없어요. 충분히 복잡한 같은 문제를 주더라도 프롬프트만 조금 다르게 주면 완전히 다른 코드를 생성할 수 있습니다. 전부가 똑같은 버그를 하나 공유한다면 오히려 놀랄 일이죠.
복잡하지만 범위가 좁은 문제라면, 프롬프트가 무엇이든 Claude가 학습 데이터에 있는 같은 유형의 해법으로 수렴할 가능성이 있습니다. 그러면 같은 절차를 서로 다르게 구현한, 같은 코드의 여러 버전이 나오는데, 이게 '동작'은 하지만 미묘한 방식으로 틀렸을 수 있죠.
쉽게 저지를 만한 개념 혼동이라면 그렇게까지 놀랍지는 않을 것 같은데요.
AI가 버그를 찾았다면, 그걸 이용해 모든 걸 증명하면서 매주 PDF를 700개씩 쏟아냈을 것 같은데요. https://xkcd.com/704/
이건 충분히 복잡한 증명이라면 사람이 썼든 아니든 문자 그대로 어느 증명에나 해당하는 얘기입니다.
핵심 아이디어를 전달하는 데는 시간이 걸립니다. 다른 수학자들이 새로운 기법과 접근법, 혹은 기존 기법을 새롭게 조합한 방식을 따라잡는 데도 시간이 걸리고요.
이 분야의 실제 전문가들이 논증을 설명해 달라고 요청했고, 이제 이게 그럴듯하다고 믿는 단계에 와 있습니다. 이 글타래에 있는 다른 분은 Lean 증명을 만들었는데, 증명기의 버그를 악용해서 우리를 속이려 하는 건 아닐 겁니다.
요약하면, 진정하세요.
좀 더 현실적으로는, 그 사칭범이 결과물을 엄청나게 많이 만들어 냈고, 그중 맞는 것만 골라서 공개한 거겠죠(그리고 특히 흥미로운 오답 몇 개도 같이요).
네, 사회적 증거의 관점에서는 그렇죠. 객관적으로 진실을 추구하는 관점에서는 아니고요. 최고의 거짓말쟁이는 99%는 진실을 말하거든요.
@platypii와 저는 소수 위수 유한체 위의 DFT에 대해 같은 개선을 이룬 Lean 증명을 얻었습니다(합성곱 정리를 통해 다항식 곱셈도 따라 나옵니다). https://github.com/platypii/integer-mult-bounds-lean/blob/master/docs/dft/dft.pdf