정확한 이산 푸리에 변환의 개선된 지수 경계

고속 푸리에 변환(FFT)은 1965년부터 길이 n인 이산 푸리에 변환(DFT)을 O(n log n) 연산으로 계산해 왔다. 2026년 9월 공개된 OpenAI 수학 문제 #130(정확한 이산 푸리에 변환의 명시적 거듭제곱 절감)은 정확한 변환이 log n의 작은 거듭제곱만큼 이 경계를 개선할 수 있음을 보였으며, 발표된 지수 절감치는 1e-13이었다. 이 저장소는 더 큰 절감치를 제안하는 연구 초안을 담고 있다.

#130의 정확한 복소수 연산, 지정된 근, 로그 워드 주소 모델을 전제로 초안이 제안하는 모든 길이에 대한 경계는 다음과 같다.

$$T(n) = O\left( n (\log n)^{1-\delta} \right), \qquad \delta = 7.3 \times 10^{-5}$$

여기서 T(n)은 길이 n 입력의 정확한 DFT를 계산하는 비용이다.

이 결과는 작성된 논증과 유한 검산으로 뒷받침된다. 다만 독립적인 수학적 검토와 전체 과정의 형식 검증은 아직 이뤄지지 않았다. 외부 Lean 소스는 수치 인증서와 정수 곱셈 매개변수의 조립을 검사하지만, 푸리에 정리 자체를 형식화하지는 않는다. 별도로 검토할 수 있는 이전 결과도 대안으로 보존돼 있다.

이 결과는 더 빠른 FFT를 뜻하지 않는다. 점근적 지수 경계에 관한 결과다. 인자 (log n)^delta가 2에 도달하려면 log n이 약 2^13,700이어야 하며, 이는 존재할 수 있는 어떤 입력보다도 훨씬 크다. 실용적인 FFT 속도 향상, 유한 정밀도 안정성, 계수가 제한된 경우의 정리, 새로운 정수 곱셈 경계는 주장하지 않는다.

기여 내역

  • 네트워크: Douglas Colkitt, icekylinx, eumemic, Aurel Prosz / Paureel의 작업을 바탕으로 한 Swapnil Jain의 6차 복소 네트워크다. 네트워크 개선의 공로는 인용된 기여자들에게 있다. 소스는 f2176bc에 고정돼 있다.
  • 이 초안: 해당 네트워크를 푸리에 논문의 균일 배열 모델로 옮기고 추가 유한 검산을 제안한다.
  • AI 지원: 초안은 GPT-6 Pro와 GPT-6-Astra Max의 도움으로 작성됐다. 전체 기록은 원고와 외부 NOTICE에 있다.

정량 비교

  • OpenAI #130 명시적 구성: 임계 절감치는 약 2.10644e-13, 발표된 순수 거듭제곱 푸리에 절감치는 1e-13이다.
  • 이전 축소 중심 대안: 임계 절감치는 약 5.22970e-10, 제시된 절감치는 5.2e-10이다.
  • 나머지 묶음을 적용한 이전 축소 중심 구성: 임계 절감치는 약 5.30776e-10, 제시된 절감치는 5.3e-10이다.
  • 이전 공유 합 구성: 임계 절감치는 약 5.51273e-10, 제시된 절감치는 5.5e-10이다.
  • 기여자를 명시한 6차 복소 네트워크: 엄격한 증인값은 a=7.3852222e-5이며, 제안된 전이를 사용한 절감치는 delta=7.3e-5다.

이 값들은 점근적 지수 매개변수이지 측정된 실행 시간 단축이 아니다. 이전 구성의 절감치는 가져온 네트워크의 절감치에 더해지지 않는다.

새 텐서 값은 임계 근이 아니라 인증된 엄격한 증인값이다. 이 값은 추가로 (log log n)^(4-theta) 인자가 붙는 경계를 제공하며, 여기서 theta=1-a다. delta<a를 선택하면 이 인자를 흡수할 수 있다. 인증서는 엄격한 모멘트 부등식과 양의 간격 a-delta=8.52222e-7을 모두 확인한다.

구성

문제 #109와 #130의 공통 요소는 다음 텐서 거듭제곱에 대한 유한 네트워크다.

$$C = \\frac{1}{2} \\begin{pmatrix} 1+i & 1-i \\\\ 1-i & 1+i \\end{pmatrix}$$

이는 정수 곱셈 하위 절차가 아니다. 새 구성은 같은 텐서 변환을 임의 입력에 적용하면서 각 나머지 블록을 하나의 재귀 호출로 묶는다. 개선에는 세 가지 요소가 쓰인다.

  • 전체 나머지 묶기: 쌍 제외 생성기가 서로소 여부 계산을 공유한다.
  • 2단계 위상: 두 단계에서 m=h^2=576을 사용한다.
  • 중심 복사 일정: 유지된 중심이 임시 복사본을 통해 읽기 결과를 제공하며, 복사본에 적용되는 변환 비용도 명시적으로 계산한다.

원고는 2단계 끝점 보정, 선형 시간 배열 배치, 불완전한 묶음이 있는 가변 폭 점화식, #130의 기존 컴파일러와 모든 길이 축소를 통한 전이를 설명한다. 정수 연산에 특화된 정밀도, 테이프 배치, 가우시안 재표본화 개선은 이 전이의 전제가 아니다.

검증

표준 라이브러리만 사용하는 Python 3.10 이상에서 다음을 실행한다.

`python3 verification/run_checks.py

`

검사는 로컬 계수 항목 4,096,576개를 모두 다시 만들고, 두 방향의 이진 레이블과 실제 보조 프레임 경로를 확인하며, 전체 하위 문제 폭 히스토그램을 재구성한다. 정확한 유리수 로그 경계로 모멘트도 인증한다. 스칼라 항등식과 끝점 항등식도 시험하고, 복사 누락·끝점 누락·과도한 절감치를 설정한 대조 사례를 거부한다. 이전 검사 묶음도 계속 실행되며 기존 기준 인증서와 일치한다.

이 검사는 유한한 근거일 뿐, 독립적인 심사 보고서나 규모가 매우 큰 전체 DFT 알고리즘의 실행이 아니다.

Pandoc과 pdfLaTeX가 필요하며 python3 scripts/build_manuscript.py로 PDF와 LaTeX를 다시 만들 수 있다.

집중 검토가 필요한 부분

  • 복사본을 이용한 읽기 일정
  • 2단계 데이터 프레임 인터페이스와 끝점 보정
  • 전체 나머지의 선형 시간 배치
  • 점화식의 나머지 비용

이전 감사 기록은 보관된 3단계 결과에 적용된다. 새 정리를 감사한 기록은 아니다.

파일

출처

공유 네트워크는 OpenAI의 #109 원고에서 비롯됐다. 이번 전이는 별도의 #130 명시적 푸리에 원고를 사용하며, 특히 명제 4.2와 5.4절을 활용한다.

새 유한 구성은 Douglas Colkitt의 틀과 여러 선행 기여를 바탕으로 한 Swapnil Jain의 6차 복소 네트워크다. 선행 기여에는 icekylinx의 전체 나머지 묶기와 중심 복사, eumemic의 전체 복소 묶기, Aurel Prosz / Paureel의 2단계 위상과 끝점 보정이 포함된다. 전체 기여 내역과 라이선스는 원고와 외부 NOTICE에 보존돼 있다.