Exact Fourier transforms below n log n

Source and verification

This article explains family 130 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Fourier matrices and arithmetic cost

For $n\ge 1$, write ${\zeta }_n=e^{2\pi i/n}$ and define the unnormalized discrete Fourier transform by

$$(F_{n}x{)}_j=\sum _{k=0}^{n-1}{\zeta }_n^{jk}{x}_k,0\le j<n.$$

Direct evaluation uses quadratic arithmetic work. The usual FFT shares intermediate sums to achieve $O(n\log n)$ operations. The two manuscripts in this family investigate savings in that asymptotic scale under exact complex arithmetic. Neither addresses floating-point error or the bit cost of representing complex numbers. (OpenAI, 2026) (OpenAI, 2026b)

For example,

$$F_2\left(\genfrac{}{}{0ex}{}{x_0}{x_1}\right)=\left(\genfrac{}{}{0ex}{}{x_0+x_1}{x_0-x_1}\right).$$

A scalar linear circuit uses additions, subtractions, and multiplication by constants independent of $x$. Each costs one gate; a general combination $\alpha u+\beta v$ can cost three. Copying the name of an available value does not mean that all arithmetic with it is free.

The manuscripts distinguish two resource models:

Result	Constants and organization	Length guarantee
Finite tensor savings	Circuit and arbitrary complex coefficients chosen separately for each length; preparation uncharged	An unbounded sequence
Explicit power saving	One deterministic algorithm; scalar preparation, schedules, and logarithmic-word address operations charged; one specified root supplied	Every positive length

The complex registers have unbounded exact precision in both models. The logarithmic word size in the second row applies to integer addresses, not complex values. Restrictions on coefficient magnitude, conditioning, or allowable gates can change the lower-bound question substantially.

🏷️ The two source statements

Let $L(n)$ be the minimum gate count of an exact scalar linear circuit computing $F_n$. The finite-savings paper states

$$\underset{n\to \infty }{\mathrm{liminf}}\frac{L(n)}{n{\log }_{2}n}=0.$$

Equivalently, for every $c>0$ and every cutoff $N_0$, some $n\ge N_0$ admits fewer than $cn{\log }_{2}n$ gates. This quantified statement supplies neither an all-length bound nor an efficient procedure for preparing its circuit constants. (OpenAI, 2026b)

The explicit companion defines

$$\begin{array}{c}m=10^6,W_{\ast }=2^{71},\\ \Delta =6871402692000000,\\ \lambda =m-\Delta /W_{\ast },\\ \theta ={\log }_m\lambda <1.\end{array}$$

All-length exact arithmetic bound, as stated in the manuscript

One deterministic algorithm computes $F_{n}x$ for every $n\ge 1$ in

$$O\left(n(\log n{)}^{\theta }(\log \log n{)}^{4-\theta }\right)$$

operations as $n\to \infty$, including scalar preparation, schedule construction, and index work. It requires one specified root ${\zeta }_{D_{\ast }}$, where $D_{\ast }$ is explicitly computable and $D_{\ast }<1024n^3$. In this model the bound is eventually

$$O\left(n(\log n{)}^{1-10^{-13}}\right).$$

A finite initial range is handled directly. (OpenAI, 2026a)

The exact constants define the exponent; its decimal value is about $0.9999999999997894$. The improvement is extremely small, and the construction has enormous fixed constants. The theorem gives no useful practical crossover estimate. Supplying a root is an explicit resource: rational field operations alone cannot manufacture roots of arbitrarily large order from rational constants.

🏷️ From one finite saving to tensor powers

For a $q\times q$ matrix $A$, its tensor power $A^{\otimes b}$ acts on arrays indexed by $b$ coordinates, each taking $q$ values. Applying $A$ separately along every axis uses

$$b{q}^{b-1}$$

calls to $A$: there are $q^{b-1}$ fibers per axis. A finite win is an exact implementation with strictly fewer such calls, allowing permutations and invertible diagonal maps between calls. The matrix must be nonmonomial, meaning that it does more than permute and rescale individual coordinates. This temporary call-count convention does not make diagonal operations free in the final scalar circuit.

The existence paper proves that at least one such finite win exists, then amplifies it to an exponent saving in tensor order. It does not assert a finite win for every nonmonomial matrix. Its proof assumes that none exists and derives a consistent system of prices for matrix calls. Simultaneous savings for finitely many matrix types could be packed into one block-diagonal instance, contradicting that assumption; separation and compactness produce the prices.

The difficult price laws concern elimination of internal coordinates, feedback, and changes of input-output bases. They are proved for exact finite matrices without assuming continuity of price. Two descriptions of a constructed reflection eventually give

$$\begin{array}{rl}dw-O(w)& \le p(R),\\ p(R)& \le \frac{3}{4}dw+O(w),\end{array}$$

with absolute constants and arbitrarily large $d$. The contradiction establishes existence of a finite win. The price is an auxiliary consequence of the no-win assumption, not an independently established circuit-size lower bound. These structural arguments remain source interfaces here. (OpenAI, 2026b)

The explicit companion starts from a specified finite network for

$$C=\frac{1}{2}\left(\begin{array}{cc}1+i& 1-i\\ 1-i& 1+i\end{array}\right).$$

It transforms $W_{\ast }$ arbitrary arrays simultaneously. If $T(k)$ is the cost on arrays of length $2^k$, normalizing by their total size gives

$$\begin{array}{c}t(k)=\frac{T(k)}{W_{\ast }{2}^k},\\ t(k)\le A+\lambda t(\lfloor k/m\rfloor ).\end{array}$$

After $r=O({\log }_m(k+1))$ recursion levels,

$$\begin{array}{rl}t(k)& \le A\sum _{j<r}{\lambda }^j+B{\lambda }^r\\ & =O((k+1{)}^{\theta }).\end{array}$$

Thus the tensor cost is $O(2^k(k+1{)}^{\theta })$. The strict finite saving makes $\lambda <m$, which is exactly what makes $\theta <1$.

The role of all $W_{\ast }$ arrays matters: each recursive batch contains arbitrary data, including values in coordinates used temporarily by another part of the network. The finite identity must transform every role correctly. Padding the number of roles to a power of two makes the recursive batches exact and avoids accumulating partially filled batches. (OpenAI, 2026a)

🏷️ Borrowing coordinates without increasing width

To transfer tensor savings to Fourier matrices, both papers need a factorization of $F_r$ on exactly $r$ coordinates into $O(1+{\log }^{4}r)$ layers. Each layer is a permutation and scaling, or acts independently on disjoint pairs of coordinates. Newton interpolation supplies diagonal and triangular Toeplitz factors; convolution implements the structured triangular operations.

Ordinary convolution programs introduce workspace. Repeatedly enlarging each small factor would destroy the intended tensor dimensions. The useful replacement is a linear replay identity that permits workspace to start with arbitrary values.

Suppose a linear computation of $Mx$ uses scratch coordinates $z$. Simulating its gates by adding values into those coordinates has the form

$$z⟼Uz+Tx,$$

where $U$ is unit lower triangular. If the output read is $F{z}_{\mathrm{current}}+Dx$, correctness with zero scratch says $FT+D=M$.

Run the computation, add its output into a separate target $y$, and reverse the scratch updates. This restores $z$ but adds $Mx+FUz$ to $y$. Now repeat the same scratch program with all direct input contributions omitted, subtract its output $FUz$, and reverse again. The net map is

$$(x,y,z)⟼(x,y+Mx,z).$$

The cancellation holds even when the initial scratch values depend on other data. Bounded fan-out permits the coordinate updates to be arranged into a controlled number of disjoint-pair layers. Choosing chunk sizes to fit these actual programs inside the available coordinates supplies the exact-width factorization. This is more than a formal matrix identity: the width and preparation costs must survive compilation. (OpenAI, 2026a) (OpenAI, 2026b)

🏷️ Synchronization and arbitrary transform lengths

For pairwise coprime factors, suitable permutations turn a Fourier transform into a tensor product of smaller Fourier transforms. Synchronize the small exact-width layer programs across these factors. A simultaneous pair layer splits the full coordinate set into sectors carrying tensor powers of the fixed kernel. The sector sizes sum to the full array size, so the tensor saving controls their combined arithmetic cost.

Indexing must also be charged. Scanning every tensor coordinate separately at every array entry would reintroduce a factor proportional to the number of axes. The manuscript constructs a traversal with linear total array work, using precomputed local digit tables and accumulated addresses. (OpenAI, 2026a)

Take the largest initial product $R_{\ell }$ of odd primes with $R_{\ell }\le 2n$, and let $L=2^e{R}_{\ell }$ be the first such multiple reaching $2n$. Then

$$\begin{array}{c}2n\le L<4n,\\ \ell =\Theta \left(\frac{\log n}{\log \log n}\right).\end{array}$$

The prime factors and the remaining power of two have polylogarithmic size. The synchronized part costs $O(L{\ell }^{\theta }(\log \ell {)}^4)$; a conventional FFT handles the small power-of-two axis.

To obtain $F_n$ from the convenient length $L$, put $\eta ={\zeta }_{2n}$ and use the exact identity

$${\zeta }_n^{jk}={\eta }^{j^2}{\eta }^{-(k-j{)}^2}{\eta }^{k^2}.$$

Multiply $x_j$ by ${\eta }^{j^2}$, convolve with the fixed sequence ${\eta }^{-u^2}$ for $-(n-1)\le u\le n-1$, and multiply output $k$ by ${\eta }^{k^2}$. Padding to $L\ge 2n$ makes the relevant residues distinct. Two forward transforms and one inverse compute the convolution; transforming the fixed kernel is charged as scalar preparation. Since that operand is fixed, all operations on variable input remain linear.

One master root suffices:

$$D_{\ast }=(2n)L{2}^{\lceil {\log }_2(16L)\rceil }<1024n^3.$$

Every root used in the construction is extracted as an integer power of the supplied specified root. Finally,

$$\begin{array}{c}{\ell }^{\theta }(\log \ell {)}^4\\ =\Theta \left((\log n{)}^{\theta }(\log \log n{)}^{4-\theta }\right),\end{array}$$

which explains the theorem’s logarithmic factors. The manuscript bounds $\theta <1-2\cdot 10^{-13}$; the remaining fixed power of $\log \log n$ is eventually absorbed by $(\log n{)}^{10^{-13}}$.

🏷️ Convolution and related complexity models

For two variable length-$n$ vectors, pad to $2n-1$, Fourier-transform both, multiply the transformed entries, and invert. This computes linear convolution with the same asymptotic bound, now allowing products of two input-dependent values. It is a bilinear arithmetic algorithm, whereas the transform itself is input-linear. No integer bit-complexity or finite-field conclusion follows solely from this reduction. (OpenAI, 2026a)

Integer multiplication treats tape movement and precision, which are separate obligations beyond exact complex arithmetic. Matrix multiplication exponents likewise illustrates why a finite tensor construction requires careful accounting before yielding a uniform asymptotic algorithm.

🏷️ Key steps and proof outlines

Exact cancellation permits arbitrary borrowed storage

The local compiler must implement a small Fourier transform inside an array already containing useful data. It cannot silently assume unused coordinates are zero. The explicit paper’s “Replay with arbitrary borrowed coordinates” lemma explains how to use such storage and restore it exactly.

Suppose a linear circuit computes $Mx$, using $g$ intermediate gates of fan-in at most two, with each output a single source or gate read (or zero). Let $y$ be the output coordinates and $z\in {\mathbb{C}}^g$ borrowed coordinates. Count output uses in the fan-out bound. Replace each gate assignment by addition into its borrowed coordinate. A forward sweep then has the form $z\mapsto Uz+Tx$, where $U$ is unit lower triangular. If the output reads are $Fz+Dx$, correctness on zero borrowed data says $FT+D=M$.

Run that sweep, add its output into $y$, and undo the sweep. The borrowed vector is restored, but the target has received $Mx+FUz$. Now repeat the sweep with direct inputs from $x$ suppressed, subtract the output $FUz$, and undo again. The combined map is exactly

$$(x,y,z)⟼(x,y+Mx,z).$$

This identity holds for arbitrary, even correlated, initial contents of $z$. For depth $H$ and bounded fan-out $\delta$, edge coloring groups each depth level’s shears into $O(\delta +1)$ layers of disjoint coordinate pairs. Four sweeps and two readouts use at most $8g+2a$ shears for $a$ outputs and depth $O((\delta +1)(H+1))$. This local restoration identity is what makes a width-preserving compiler possible. (OpenAI, 2026a)

Synchronization converts axis layers into tensor powers

After compilation, each axis has a word alternating monomial operations and layers of disjoint copies of the fixed two-coordinate map $C$. Pad these words to common slot types. The identity

$$\left(\underset{j}{⨂}{A}_j\right)\left(\underset{j}{⨂}{B}_j\right)=\underset{j}{⨂}(A_j{B}_j)$$

justifies synchronizing corresponding slots across axes. Another axis may change data while a local word is in progress; restoration is required of the completed local linear map, not of every intervening global slot.

In a pair slot, each axis is partitioned into pairs and singletons. A sector chooses one block from each axis. If it chooses $k$ pairs, its width is $2^k$ and its transform is exactly $C^{\otimes k}$. For two axes partitioned as pair plus singleton, the four sector widths are $4,2,2,1$: the corresponding operations are $C\otimes C$, $C$, $C$, and the identity. This is a concrete reason that improvements for tensor powers can act on a whole mixed-radix Fourier array.

If there are $\ell$ axes and total width $R$, the sector widths sum to $R$. The bound $O(2^k(k+1{)}^{\theta })$ for a width-$2^k$ sector therefore sums to $O(R(\ell +1{)}^{\theta })$ for a slot. This estimate uses all sectors, including singleton sectors; dropping their movement cost would conceal overhead precisely where the saving is smallest.

Index generation must also be linear

Recomputing all $\ell$ digits at every array position would cost $R\ell$ and erase the improvement. The source instead traverses mixed-radix prefixes recursively. For radices $r_j\ge 2$,

$$\sum _{j=0}^{\ell }\prod _{i=1}^j{r}_i<2R.$$

It maintains the original address, packed-sector start, within-sector offset, and prefix width, updating each with a constant number of operations when extending a prefix. A depth-first stack avoids copying the prefix. The same traversal also accumulates tensor-monomial scalars, so those products are charged. Thus packing, unpacking, and discovering sectors cost $O(R)$, as established in “Synchronizing tensor factors in linear array work.”

From a finite saving to an asymptotic exponent

The fixed tensor construction reduces the normalized recurrence to $t(k)\le A+\lambda t(\lfloor k/m\rfloor )$, with $m=10^6$ and $\lambda =m-\Delta /W_{\ast }$ as defined above. At recursion depth $j$ the accumulated normalized recurrence weight is at most ${\lambda }^j$; stopping when $m^j$ reaches $k$ gives $t(k)=O(k^{{\log }_m\lambda })$. The strict inequality $\lambda <m$ supplies $\theta <1$, even though its numerical gap from one is very small.

The local compiler contributes logarithmic overhead; smooth-length padding, exact chirp convolution, and the common root-of-unity preparation transfer the tensor result to every input length. These are necessary interfaces because a fast transform on a sparse set of lengths would establish only a subsequence result. The existence companion’s finite-savings argument has that different conclusion and does not itself supply this explicit uniform compilation or all-length estimate. Both papers work in their stated exact arithmetic model; this proof outline makes no floating-point stability claim. (OpenAI, 2026b; OpenAI, 2026a)

🏷️ Manuscripts and verification scope

• An explicit power saving for the exact discrete Fourier transform — pinned manuscript and companion source.
• Finite tensor savings and exact Fourier circuits — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. Its selected comparator concerns the subsequential nonuniform circuit theorem, not the explicit all-length algorithm with charged preparation. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. An explicit power saving for the exact discrete Fourier transform.

🐻  OpenAI 2026b. Finite tensor savings and exact Fourier circuits.