Documentary state: DRAFT_UNACCEPTED. This draft has NOT been editorially admitted. Mathematical claims require independent checking.
OAI-26 family 130: exact discrete Fourier transforms below n log n
Editorial status: DRAFT_UNACCEPTED. NO_CERTIFICATION. This account documents a pinned publisher claim; it does not independently verify an algorithm or arithmetic complexity bound.
The question in plain language
The discrete Fourier transform (DFT) reorganizes a sequence of numbers into its frequency components. The standard fast Fourier transform evaluates a length \(n\) DFT in order \(n\log n\) arithmetic operations. Family 130 claims a deterministic exact-arithmetic algorithm that saves a small but genuine power of the logarithm.
The issue is not numerical approximation: the asserted construction computes the transform exactly in a specific algebraic computation model.
A small example
For an input vector \((x_0,\ldots,x_{n-1})\) and a primitive root of unity of order \(n\) \(\omega\), its DFT has entries
Direct evaluation takes order \(n^2\) arithmetic operations. An FFT reuses intermediate expressions to reach approximately \(n\log n\). The source claims an asymptotic improvement, not merely a faster constant factor for selected lengths.
What is known
The protected Family 130 catalogue identifies two manuscripts, An explicit power saving for the exact discrete Fourier transform and Finite tensor savings and exact Fourier circuits.
The pinned publisher overview claims that for every input length \(n\), a deterministic algorithm computes the exact length \(n\) DFT using
operations. The stated computation model permits exact complex arithmetic, unrestricted coefficients, and a supplied root of unity. The overview explicitly counts scalar preparation and logarithmic-word indexing.
Because the exponent saving is extremely small, it would not necessarily yield a practical speedup at ordinary input lengths. Its mathematical significance, if established, is crossing the asymptotic \(n\log n\) benchmark within the stated model.
The result must not automatically be translated into a Turing-machine bit-complexity improvement: exact complex numbers and unrestricted coefficients can conceal representation costs absent a specified bit model.
GCL verification state
Source lock: openai/math@1581d4cbdd69a0faf34b2089614fe2a814316a6a. The two PDFs and the publisher's claimed \(\delta\) value and model assumptions are pinned by the catalogue and overview.
This documentary pass has not checked the tensor decomposition, circuit construction, handling of arbitrary lengths, exact arithmetic accounting or the derivation of the stated power saving. No Family 130-specific critical proof audit, independently reproduced algorithm, Comparator determination, or MATHCERT certificate is asserted.
What remains
Read both pinned manuscripts and reconstruct the finite tensor saving, including the base tensor, rank or arithmetic complexity estimate, recursive use and treatment of nonconforming lengths. Verify that the asymptotic bound holds for every \(n\), rather than only powers of selected integers or a subsequence.
Check the precise operation model: permitted complex constants, root-of-unity supply, scalar preparation, indexing costs, uniform algorithm generation and whether the computed output is exact. Audit all constants and the derivation of \(\delta=10^{-13}\), separating asymptotic complexity from implementation practicality.
Complete mathematical Markdown and MkDocs regression, source-critical editorial review, and protected merge/readback. Editorial admission alone would not certify the claimed DFT algorithm.
Sources and claim boundaries
- Pinned explicit DFT power-saving manuscript.
- Pinned tensor savings and Fourier circuits manuscript.
- Pinned OAI-26 overview, Family 130.
- GCL editorial assignment.
Boundary: NO_CERTIFICATION. The exact Fourier-transform complexity claims remain publisher-reported pending independent verification.
Indexed primary manuscript paths:
- An explicit power saving for the exact discrete Fourier transform —
preprints/An-explicit-power-saving-for-the-exact-discrete-Fourier-transform-September-25-2026/main.pdf - Finite tensor savings and exact Fourier circuits —
preprints/Finite-tensor-savings-and-exact-Fourier-circuits-September-25-2026/main.pdf