OpenAI가 주장하는 더 빠른 푸리에 변환의 수학 살펴보기

Ben Recht의 arg min 글 "Faster Fourier Transforms"(2026-10-12) 본문을 옮겼어요. 원문의 수식 이미지는 텍스트로 옮기지 못해 말로 풀었어요.

The OpenAI algorithm for the FFT is less a breakthrough and more a malicious exploit.

FFT 복습

고속 푸리에 변환(FFT)은 디지털 신호 처리의 가장 중요한 혁신 중 하나예요. 길이 n 신호의 주파수 성분을 구하려면 단순 계산으로 n²번 연산이 필요하지만, 1965년 Cooley와 Tukey가 고안한 재귀 절차(위키백과는 1805년 가우스에게 공을 돌려요)는 입력을 섞어 길이 n/2 변환 두 개로 나누고 다시 합치는 과정을 log₂n번 반복해 5n log₂n 미만의 연산으로 끝내요. n이 1,000이면 약 20배, 100만이면 1만 배 빨라져요.

n번은 적어도 필요하니, FFT는 그 한계보다 5log₂n배 느려요. n이 1조면 200배죠. 이 앞자리 계수를 줄일 수 있느냐가 오래된 질문이에요.

OpenAI의 주장과 읽는 방식

지난주 OpenAI가 수학계에 쏟아낸 대량 논문 중 'main.pdf'라는 파일이 log(n) 항이 표준 FFT보다 아주 조금 작은 FFT를 주장해요. Recht는 "OpenAI에서도 아무도 안 읽은 논문을 내가 왜 읽나"라며, 다른 수학자들처럼 챗봇에게 다시 넣어 핵심을 뽑아냈다고 비꼬아요.

문제 1: 은하(galactic) 알고리즘

big-O 표기는 큰 n에서 상수배를 무시해요. 실용적으로 빠른 FFT라면 적당한 n에서 50n보다 적은 연산이 필요한데, O(n)은 10^80·n일 수도 있어요. Lipton과 Regan은 이렇게 상상할 수 없을 만큼 큰 숨은 상수를 가진 알고리즘을 '은하 알고리즘'이라 불러요.

OpenAI FFT는 확실히 은하급이에요. N=10^12일 때 추정 상수 C가 10^100이라, n=10^100에서도 기존 FFT가 10^99배 빨라요. 점근적으로는 더 빠르지만 불가능하게 큰 n에서만 그래요.

문제 2: 실제 컴퓨터와 무관한 계산 모델

"The model uses exact complex arithmetic."

이 알고리즘은 복소수를 임의 정밀도로 저장하고 곱할 수 있다고 가정하고, 크기가 n에 대해 초다항식으로 커지는 복소수를 한 번의 연산으로 곱한다고 쳐요. 비트로 저장하면 메모리가 사실상 입력 길이에 지수적이에요. 그런 컴퓨터는 없어요. 정리가 '참'이라도 우리가 풀려던 문제가 아니에요.

이건 놀랍지 않대요. 1973년 Morgenstern은 계수 크기가 유한하면 ½n log n보다 빠를 수 없음을 증명했고, 40년 뒤 Ailon은 심각한 수치 불안정 없이는 n log n보다 빠를 수 없음을 보였어요. 그런데도 사람들은 그 모델이 너무 제한적이라고 했죠.

이론 컴퓨터 과학의 문화

Recht는 이 결과를 수학적 돌파라기보다 컴퓨터 과학자들이 설계 명세를 제대로 형식화하지 못해 생긴 기묘함으로 봐요. 불가능한 문제에 봇을 풀었더니 불법 해킹을 하고 있는 것과 비슷하다고요. O(n^2.25) 행렬 곱셈 결과도 상수를 추정조차 할 수 없다고 지적해요.

그래도 더 잘 쓰였다면 STOC·FOCS에 실렸을 테고 행렬 곱셈 논문은 상도 받았을 거래요. 이론 CS가 알고리즘을 실제로 돌리지 않아도 되는 문화이기 때문이에요.

AI is really good at automating our worst tendencies.

AI는 아무도 좋아하지 않지만 개인이 벗어나기 어려운 관행을 증폭하고, 이제 쓸모없는 이론 논문도 쓸 수 있대요. 다만 이 터무니없는 증명 더미를 보며 다 함께 다른 길을 생각해 볼 수도 있다고 맺어요.