{"id":"openai-math/Finite-tensor-savings-and-exact-Fourier-circuits","pdf":"https://github.com/openai/math/blob/main/preprints/Finite-tensor-savings-and-exact-Fourier-circuits-September-25-2026/main.pdf","url":"https://github.com/openai/math/tree/main/preprints/Finite-tensor-savings-and-exact-Fourier-circuits-September-25-2026","tags":["linear-algebra","circuit-complexity","fourier-transform"],"score":0,"title":"Finite tensor savings and exact Fourier circuits","domain":"Theoretical computer science","family":"130","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We construct exact nonuniform Fourier circuits of size $`o(n\\log n)`$ along an unbounded sequence of lengths, counting every addition, subtraction, and scalar multiplication. This refutes the $`\\Omega(n\\log n)`$ lower bound in the unrestricted complex linear-circuit model. The construction uses a finite tensor saving: a tensor power of some invertible nonmonomial complex matrix can be computed with fewer matrix calls than the standard tensor-axis algorithm on the same coordinates, when invertible monomial maps are allowed freely between calls.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{},"formalized":true,"family_title":"Exact Fourier transforms below $`n\\log n`$"}