Unrestricted Linear-Circuit Lower Bound for the Discrete Fourier Transform

For each integer n>=2, let C_DFT(n) be the minimum number of steps needed to compute every output of the unnormalized complex DFT y_j=sum_(l=0)^(n-1) exp(-2piijl/n)x_l, 0<=j<n. Initially available functions are input coordinates and scalar constants; each step adds one affine function lambdaf+mug from two previously available functions with arbitrary complex scalars. Assertion: there exist c>0 and N such that C_DFT(n)>=cnlog(n) for all n>=N. No coefficient bound, conditioning or memory restriction is imposed beyond this two-input scalar-step model.

Source: An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model, v5 header24July2014; internal31October2018.

Status Open Status review date not recorded in this edition

Listed by ProofAtlas. Status qualification is attributed to ProofAtlas; no full resolution is certified here.

References

Primary source

ProofAtlas open problems; An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model, v5 header24July2014; internal31October2018

computational-complexity

Posted 1 week ago

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

RemarkAI-assistedClaimed by OpenAI. Given an exact Fourier root of explicitly computed order below 1024n^3, the manuscript claims an all-length exact DFT algorithm using O(n(log n)^(1-10^(-13))) operations, including scalar preparation and logarithmic-size indexing. For each length its input computation uses only linear scalar gates, giving a claimed counterexample to the page’s unrestricted circuit lower bound. No bit-complexity or stable floating-point improvement is claimed.See full solutionHide full solution

Claimed by OpenAI. Given an exact Fourier root of explicitly computed order below 1024n^3, the manuscript claims an all-length exact DFT algorithm using O(n(log n)^(1-10^(-13))) operations, including scalar preparation and logarithmic-size indexing. For each length its input computation uses only linear scalar gates, giving a claimed counterexample to the page’s unrestricted circuit lower bound. No bit-complexity or stable floating-point improvement is claimed.

GitHub repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/An-explicit-power-saving-for-the-exact-discrete-Fourier-transform-September-25-2026/main.pdf

OpenAI-130-01-An-explicit-power-saving-for-the-exact-discrete-Fourier-transform.pdf449,086 bytesOpen

RemarkAI-assistedClaimed by OpenAI. The manuscript claims exact nonuniform complex linear DFT circuits with size o(n log n) along an unbounded sequence of lengths, counting every addition, subtraction and scalar multiplication. Arbitrary input-independent coefficients and reuse of values are allowed. This contradicts the page’s eventual lower bound in its unrestricted scalar-step model. It is not a uniform all-length algorithm, bounded-coefficient result or bit-complexity bound.See full solutionHide full solution

Claimed by OpenAI. The manuscript claims exact nonuniform complex linear DFT circuits with size o(n log n) along an unbounded sequence of lengths, counting every addition, subtraction and scalar multiplication. Arbitrary input-independent coefficients and reuse of values are allowed. This contradicts the page’s eventual lower bound in its unrestricted scalar-step model. It is not a uniform all-length algorithm, bounded-coefficient result or bit-complexity bound.

GitHub repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Finite-tensor-savings-and-exact-Fourier-circuits-September-25-2026/main.pdf

OpenAI-130-02-Finite-tensor-savings-and-exact-Fourier-circuits.pdf632,960 bytesOpen