gpt 6 astra ultra attempt on CS-68

Unrestricted Linear-Circuit Lower Bound for the Discrete Fourier Transform

Definitions and mathematical statement

For $n\ge2$, let $\omega_n=e^{-2\pi i/n}$ and define the discrete Fourier transform by \[ y_j=\sum_{\ell=0}^{n-1}\omega_n^{j\ell}x_\ell, \qquad0\le j<n. \] A linear straight-line circuit starts with the input coordinates and allowed scalar constants. Each gate forms $\lambda f+\mu g$ from two previously available values, with arbitrary complex coefficients; its cost is one gate. Let $C_{\rm DFT}(n)$ be the minimum gate count for producing all outputs exactly. The conjecture is $C_{\rm DFT}(n)\ge c n\log n$ for an absolute $c>0$ and all sufficiently large $n$. There is no bound on coefficient magnitude or intermediate conditioning. Consequently, a lower bound proved only for bounded-coefficient or well-conditioned circuits is an approach to, not a solution of, the unrestricted question.

Formulation and concept references: [S1].

Short English statement

Must every exact linear circuit for the discrete Fourier transform use order $n\log n$ operations, even with arbitrary complex coefficients and ill-conditioned intermediate calculations?

Research attempt

Status: UNRESOLVED. Exact $O(n\log n)$ circuits are described, together with complete $\Omega(n\log n)$ proofs in two restricted models. The determinant proof requires bounded coefficients; the entropy proof requires unitary in-place gates. Explicit calculations show why neither restriction can be deleted for free. Only a linear lower bound is established here in the unrestricted model of the catalogue.

Source audit and affine constants.

The version of [S1] specified by the inherited bibliography was inspected on 27 September 2026. Its condition-number hypothesis is a property of intermediate transformations, and its lower bound depends on that parameter. It is not an unrestricted lower bound. The older determinant argument discussed there is also scale sensitive. The restricted arguments below are included with their hypotheses stated explicitly rather than treated as proofs of the selected conjecture.

If gates are allowed scalar constants as inputs, an intermediate value can be affine in the variables. Associate to it its vector of linear coefficients, obtained by taking derivatives with respect to the inputs. A constant has coefficient vector zero, and a gate $\lambda f+\mu g$ has vector $\lambda a+\mu b$. Since the required outputs are linear, all lower-bound arguments about these coefficient vectors remain valid even with affine intermediates.

1. Exact Fourier orthogonality.

Let $F_n=(\omega_n^{j\ell})_{0\le j,\ell<n}$. For two row indices $j,k$, \[ (F_nF_n^*)_{jk}=\sum_{\ell=0}^{n-1}\omega_n^{(j-k)\ell} =\begin{cases}n,&j=k,\\0,&j\ne k.\end{cases} \] The off-diagonal sum is a finite geometric series with ratio not equal to one. Thus \[ F_nF_n^*=nI,\qquad |\det F_n|=n^{n/2}. \] The normalized matrix $U_n=n^{-1/2}F_n$ is unitary and has determinant of absolute value one. Both matrices are invertible, but this rank fact alone says little about circuit size: the initial input coefficient vectors already span an $n$-dimensional space.

2. The radix-two upper bound in the selected gate model.

For $n=2m$, split the inputs into even and odd positions and compute their two length-$m$ transforms $E_j,O_j$. Then \[ y_j=E_j+\omega_n^jO_j,\qquad y_{j+m}=E_j-\omega_n^jO_j\quad(0\le j<m). \] Each displayed output is exactly one allowed gate; multiplication by the twiddle factor is included in that gate's coefficient. With $T(1)=0$ this gives \[ T(2m)\le2T(m)+2m, \] so $T(n)\le n\log_2n$ for powers of two. Reuse of $E_j,O_j$ is legal because the model permits previously computed values to feed multiple gates.

For arbitrary $n$, the chirp identity gives a reduction to convolution. Let $\zeta=e^{-\pi i/n}$, so $\omega_n=\zeta^2$. The identity \[ 2j\ell=j^2+\ell^2-(j-\ell)^2 \] rewrites the transform as \[ y_j=\zeta^{j^2}\sum_{\ell=0}^{n-1} (\zeta^{\ell^2}x_\ell)\zeta^{-(j-\ell)^2}. \] Embed this convolution in a cyclic one of power-of-two length $m\ge2n-1$, with $m<4n$. The kernel values for differences $-(n-1),\ldots,n-1$ occupy distinct residues modulo $m$, so the required output coordinates incur no aliasing. The kernel transform consists of fixed scalars and may be used as circuit coefficients. One forward transform of the variable input, pointwise scalar gates, and one inverse transform compute the convolution. Initial and final diagonal scalings take $O(n)$ further gates. Hence $C_{\rm DFT}(n)=O(n\log n)$ for every $n$.

This is an exact algebraic circuit statement with arbitrary fixed complex coefficients. It does not assume floating-point FFT accuracy or charge a transcendental constant oracle per input.

3. A determinant potential for bounded coefficients.

At any time collect all available linear coefficient vectors, including the original coordinate vectors. Let $D$ be the maximum absolute determinant of an $n$-by-$n$ matrix whose rows are chosen from this collection. Initially $D=1$. Adding a new vector $v=\lambda a+\mu b$ leaves old minors unchanged. A new minor using $v$ expands in that row as a sum of two old minors, with multipliers $\lambda,\mu$. Thus \[ D_{\rm new}\le\max(1,|\lambda|+|\mu|)D_{\rm old}. \] Repeated rows give a zero minor and cause no exception. If every coefficient has absolute value at most one, each gate increases $D$ by at most a factor two. Since the final collection contains all Fourier rows, \[ 2^s\ge n^{n/2},\qquad s\ge\tfrac12 n\log_2n. \] The argument accommodates arbitrary fan-out and stored intermediates; its essential extra assumption is the coefficient bound. With $|\lambda|,|\mu|\le B$ for a fixed $B\ge1$, it instead gives $s\ge n\log_2n/(2\log_2(2B))$.

If $B$ is unrestricted and can depend arbitrarily on the circuit, the last expression has no uniform $n\log n$ consequence. Indeed, one gate can create a coefficient vector of arbitrarily large norm and multiply a determinant by an arbitrarily large amount. A proof cannot retain the factor-two inequality after removing the hypothesis that made it true.

4. Normalization does not fix that defect.

The transforms $F_n$ and $U_n$ differ by a diagonal output scaling, which costs at most $n$ additional gates in either direction. Therefore their unrestricted circuit complexities differ by at most $n$. Nevertheless the determinant potential is $n^{n/2}$ for the former and one for the latter. This shows directly that the potential does not measure the desired unrestricted complexity in a scale-invariant manner.

One might try to normalize every intermediate coefficient vector, declaring large magnitudes harmless. But the gate coefficients needed to combine normalized vectors can then become large when those vectors almost cancel. For example the vectors associated with $Mx$ and $Mx+y$ become almost parallel after normalization when $M$ is large, while subtracting the original forms recovers $y$ exactly. Recovering that difference from the normalized forms requires large coefficients. Normalization is not a conversion to a bounded-coefficient circuit with a proved constant overhead.

5. A different lower bound for unitary in-place gates.

Now impose a different restriction: there are exactly $n$ registers, initially the inputs, and each step applies a two-by-two unitary transformation to two registers. Every intermediate matrix $U$ is unitary. Define \[ \Phi(U)=-\sum_{i,j}|U_{ij}|^2\log_2|U_{ij}|^2, \] with $0\log0=0$. Initially $\Phi(I)=0$. For the normalized Fourier matrix every squared entry equals $1/n$, so $\Phi(U_n)=n\log_2n$.

Consider a gate mixing rows $a,b$. For each column $j$, let $p_j=|U_{aj}|^2$, $q_j=|U_{bj}|^2$ and $t_j=p_j+q_j$. Unitarity of the gate preserves $t_j$. The contribution of these two entries to the potential is \[ -t_j\log_2t_j+t_j h_2(p_j/t_j), \] where the binary entropy $h_2$ lies between zero and one; the formula is interpreted as zero when $t_j=0$. Its increase is at most $t_j$. Summing over columns gives an increase of at most two because the two rows each have squared norm one. Therefore any such computation needs at least $n\log_2n/2$ unitary two-register gates.

This proof is insensitive to the determinant of the normalized target, but it uses preservation of both row norms and each two-entry column mass. An arbitrary gate in the catalogue does not have these properties. It can also create a new stored value instead of replacing two registers invertibly. Counting the restricted gates therefore cannot directly lower-bound every allowed unrestricted circuit.

6. What remains without either restriction.

Every Fourier output has a nonzero coefficient on every input. At $n\ge2$, none is an original coordinate or scalar constant, and the $n$ Fourier rows are distinct. Since a gate produces one value, at least $n$ gates are needed to make all outputs available. This is only a linear lower bound.

For a single output depending on all $n$ variables, its ancestor circuit also needs at least $n-1$ binary combination gates: a connected dependency graph with $n$ input leaves and $s$ internal binary gates has at most $2s$ incoming edges and at least $n+s-1$ edges, so $s\ge n-1$. One cannot multiply this bound by $n$, because the ancestor circuits for different outputs may share many intermediates, as the FFT itself does.

A successful unrestricted lower bound needs an invariant that tracks this shared computation while tolerating arbitrarily large coefficients, severe cancellation, extra stored values and nonunitary transformations. Neither of the two potentials above has all of those properties.

7. Exact algebra checks and the final gap.

The offline diagnostic verifies radix-two transform coefficients and Fourier orthogonality at powers of two through 16 using exact polynomial arithmetic modulo the corresponding cyclotomic polynomial $X^{n/2}+1$. It checks the chirp exponent identity and padding indices for small general lengths by exact integer congruences. No floating determinant is accepted as an exact proof of the matrix identity.

These checks support the upper-bound formulas and the algebra entering the potentials. The lower-bound arguments themselves are complete only in their declared restricted models. No new restriction has been derived for an optimal unrestricted circuit, and no potential with a uniformly bounded change under all its gates is provided. The catalogue's $\Omega(n\log n)$ lower bound remains unresolved here.

Sources

• S1 An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model, v5 header24July2014; internal31October2018. https://arxiv.org/pdf/1403.1307v5. Formulation source.