Skip to content
FR · Français
Get started

Language: English · Français

Exact discrete Fourier transform below n log n: the exponent saving δ

0.0012331685≤ value ≤no upper bound trackedlower boundupper bound
10−9​10−6​0.00125 Sept2 Oct9 Octupdated on Oct 12, 2026Lower bound 1e-13, Sep 25, 2026, OpenAI, published, off the scale, below the plateau of the other records1e-13Lower bound 5.5e-10, Oct 8, 2026, shea256, mergedLower bound 7.3e-5, Oct 8, 2026, shea256, mergedLower bound 0.00067, Oct 9, 2026, shea256, mergedLower bound 0.000754736, Oct 10, 2026, shea256, mergedLower bound 0.0012331685, Oct 12, 2026, shea256, merged0.0012331685lower10−9​10−7​10−5​0.00125 Sept30 Sept5 Oct10 Octupdated on Oct 12, 2026Lower bound 1e-13, Sep 25, 2026, OpenAI, published, off the scale, below the plateau of the other records1e-13Lower bound 5.5e-10, Oct 8, 2026, shea256, mergedLower bound 7.3e-5, Oct 8, 2026, shea256, mergedLower bound 0.00067, Oct 9, 2026, shea256, mergedLower bound 0.000754736, Oct 10, 2026, shea256, mergedLower bound 0.0012331685, Oct 12, 2026, shea256, merged0.0012331685lower bound
Off the scale, shown at the bottom edge of the chart: 1e-13 (Sep 25, 2026, OpenAI).Only one side is tracked: there is no space between two bounds to colour.Hover over the points or move through them with the keyboard; a click opens the PR, the commit or the source page.Tap a point to read its source; tap it again to open the PR or the page.
  1. lower bound 0.00067by shea256github.com
  2. lower bound ≈ 0.00075474by shea256github.com
  3. lower bound ≈ 0.0012332by shea256PR #4
  4. Last checked
Lower bound · merged · Oct 12, 2026
Exact value : 0.0012331685
Improve exact DFT saving to 0.0012331685 with a verified Lean proof · PR #4
by shea256
FollowReport

Cite this frontier

DiscoverIA. Exact discrete Fourier transform below n log n: the exponent saving δ [Frontier, checked on Oct 12, 2026]. DiscoverIA registry. https://discoveria.ai/en/frontieres/fourier-dft-exact/

Only the lower bound is tracked. The lower bound has moved 5 times since 2026, most recently on Oct 12, 2026.

δ such that the exact discrete Fourier transform of every length n is computed in O(n (log n)^(1−δ)) operations in the model of OpenAI's family 130 (exact complex arithmetic, unrestricted coefficients, supplied root of unity, unit-cost logarithmic-word indexing); a construction gives a lower bound on the best δ.

These are asymptotic exponent savings, not running times: the repository claims no practical FFT speedup. Verification status varies by point: 5.5e-10, 7.3e-5 and 6.7e-4 are written transfers with exact finite checks and no formal proof; 7.54736e-4 reuses Sussman's Lean framework; the repository's current value (1.2331685e-3, PR #4) has a Lean proof accepted by the comparator according to the repository, without independent human mathematical review. The stated saving is chosen below the tensor witness to absorb the overhead of the Fourier reduction; the integer-multiplication parameter κ is a different quantity.

Linked announcement in the registry

Every step, as a table : Lower bound (6 points)

Best δ established by a construction (OpenAI preprint, then the value the repository maintainer selects).

Points : Lower bound
DateExact valueNatureAuthorsSource
Oct 12, 20260.0012331685 Current recordmergedshea256PR #4
Oct 10, 20260.000754736 Current recordmergedshea256github.com
Oct 9, 20260.00067 Current recordmergedshea256github.com
Oct 8, 20267.3e-5 Current recordmergedshea256github.com
Oct 8, 20265.5e-10 Current recordmergedshea256github.com
Sep 25, 20261e-13 Current recordpublishedOpenAIgithub.com
Other tracked problems (8)

Report an error or suggest a source

How DiscoverIA uses your address and how to exercise your rights: privacy policy.

Bot check not configured.