WorksComputer Science
A Numerical Refinement of an Exact Discrete Fourier Transform Bound
Abstract
We refine the numerical bounds in Kartal's instantiation of Sussman's exact discrete Fourier transform construction. For every integer n >= 1, the resulting algorithm computes the length-n transform with work O(n (log n)^(1 - delta)), where delta = 0.0030201659. The bound holds in an exact complex-arithmetic RAM model with a supplied canonical root of unity. This final exponent saving exceeds the earlier certified parameter C_0 = 0.00302016 by 5.9 x 10^(-9). We retain the underlying circuit, tighten rational bounds for sums of powers of its block and target ranks, and increase the fixed tensor power from 7760 to 11640. These bounds establish the inequalities for Sussman's recursion at the intermediate certificate parameter C = 0.00302016595. The gap C - delta absorbs the overhead of recursion and Fourier reduction. The resulting transform theorem is proved in Lean and checked against the reference problem statement.
Introduction
We consider the arithmetic work needed to compute the discrete Fourier transform for every integer input length . Cooley and Tukey’s factorization gives the familiar bound, while Bluestein’s reduction extends this order of growth to arbitrary lengths [4, 2]. More recent work has reduced leading constants: Alman and Rao obtain real arithmetic operations for lengths that are powers of two [1].
Another line of work studies a saving in the exponent of the logarithm under exact complex arithmetic. OpenAI’s construction for arbitrary lengths gives such a saving in a uniform RAM model with charged scalar preparation and a supplied root of unity [11]. Subsequent finite circuits and formalizations have increased the explicit saving. The present work concerns the instantiation by Kartal [9], which uses Sussman’s mixed-target recursion [12] and the controller and tensor constructions developed by Davis and the integer-multiplication circuit community [5, 6, 7].
The exponent in this construction is controlled by a finite set of inequalities involving the sizes and counts of its component computations. We call the exact numerical bounds that verify these inequalities a numerical certificate. Kartal’s submission states a final Fourier saving of 0.0030103, while its certificate establishes the stronger parameter [9]. The recursion and Fourier reduction permit any fixed saving : the gap below absorbs their asymptotic overhead. Thus, for example, a saving of 0.00302 already follows from the earlier argument. We improve the numerical certificate to obtain a saving beyond .
Theorem 1.1. In the exact complex-arithmetic RAM model described in § 2, there are fixed deterministic programs that compute the length- discrete Fourier transform for every integer , with work
The work bound includes the root-order computation, one supplied-root operation, scalar preparation, and array and index operations. Integer values and addresses are bounded by a fixed polynomial in .
The improvement is a numerical refinement of the existing algorithm. We use the same raw circuit, the same sizes and counts of its component computations, and the same reduction to the Fourier transform. The changes are tighter rational estimates of the rank moments and a larger fixed tensor power. Our final DFT saving is , exceeding the earlier certified parameter by . Earlier circuit analysis placed the raw moment balance point near 0.003020165977. Our final saving remains below this value to accommodate the overhead of the tensor construction, recursion, and Fourier reduction. Conditional integer-multiplication constructions had also used rates close to that point [8, 3].
The proof below gives the finite arithmetic behind the refinement and then applies Sussman’s recursion and the Fourier reduction. The accompanying Lean proof verifies the resulting transform algorithm and its work bound in the reference model.
Computational model and the finite unit
For , write . We use the positive-sign, unnormalized transform
All logarithms in complexity bounds are natural logarithms.
We retain OpenAI’s exact RAM model [11]. A fixed program first computes a positive integer from . A root primitive then supplies the exact complex number , after which a second fixed program computes (1). The order may differ from the transform length . The formal specification requires and bounds all integer values and addresses by for one constant . Its cost includes both programs and the root primitive. Exact scalar arithmetic and integer-word, array, and index operations are charged according to the RAM semantics. Scalar coefficients have unrestricted magnitude. The work bound counts exact arithmetic and RAM operations.
The finite unit used here is Kartal’s P16A8Z instance [9]. It combines a 16-pair controller, with prefix parameter eight, and an 18-stage geometry with 145 label coordinates. Its supplier comes from the patched circuit in Davis’s joint-helper construction [7]. In the cost analysis, a charged block is a component computation whose work is counted, and a target job specifies a computation that the circuit carries out. The rank of a block or job is the number of coordinate axes on which it acts. After dividing out a common multiplicity factor, the ranks and their counts form the two multisets in Table 1. For example, the entry describes 6984 charged blocks of rank two. We use the same two multisets as Kartal’s construction.
| Charged blocks | Target jobs | ||
| Rank | Count | Rank | Count |
| 1 | 41946 | 4 | 504 |
| 2 | 6984 | 7 | 126 |
| 3 | 8892 | 8 | 846 |
| 4 | 2646 | 9 | 5868 |
| 5 | 648 | 17 | 448 |
| 8 | 144 | 25 | 448 |
| 16 | 448 | 33 | 448 |
| 24 | 448 | 41 | 448 |
| 32 | 448 | 49 | 448 |
| 40 | 448 | 57 | 448 |
| 48 | 448 | 65 | 448 |
| 56 | 448 | 73 | 224 |
| 64 | 448 | 145 | 224 |
| 72 | 224 | — | — |
Table 1. Ranks and counts of charged blocks and target jobs in the raw P16A8Z construction, with the common multiplicity factor omitted.
For a finite multiset of positive integers, define its moment by
where the sum counts multiplicity. Let and be the charged-block and target multisets, and abbreviate and . Direct summation gives
The recursion compares with at an exponent . It also needs every charged-block rank to be smaller than every target rank. The raw multisets do not have this separation: some block ranks exceed the smallest target rank. Tensor products, target completion, and block splitting establish it in Section 4.
The refined numerical bounds
Fix the exact rational numbers
Our first task is to prove . The gap is small enough that the earlier exponential estimates lose the required precision. The following elementary bounds suffice.
Lemma 3.1. Let . For , . For ,
Proof. The lower bound discards nonnegative terms of the exponential series. For the upper bound, its tail starts with . Each subsequent term is at most times the preceding term when . The tail is therefore at most .
We normalize at the largest target rank, 145. For a rank with multiplicity , its contribution becomes
Every argument of the exponential lies in . Rational bounds for can therefore be substituted into Lemma 3.1 with little loss. Appendix A gives the bounds for every term, together with the finite-series tests that certify the logarithms.
Proposition 3.2. At the parameters in (3),
Consequently, .
Proof. For each charged-block rank, use an upper logarithm bound in (5) and then (4). For each target rank, use a lower logarithm bound and the lower polynomial . The rank-145 target term is exactly 224. Adding the respective rational enclosures in Table 2 gives (6) and (7). Both sums are positive, and exact rational arithmetic gives
| Rank | Logarithm bound | Moment bound | |
| Charged blocks: upper bounds | |||
| 1 | 4.976733742421 | 29 | 293.663682394904 |
| 2 | 4.283586561861 | 27 | 97.585379104181 |
| 3 | 3.878121453753 | 26 | 186.139872110444 |
| 4 | 3.590439381301 | 25 | 73.788927475228 |
| 5 | 3.367295829987 | 24 | 22.573229270017 |
| 8 | 2.897292200741 | 23 | 8.014652284989 |
| 16 | 2.204145020181 | 21 | 49.764660119895 |
| 24 | 1.798679912073 | 19 | 74.555635518839 |
| 32 | 1.510997839621 | 18 | 99.321181555482 |
| 40 | 1.287854288307 | 17 | 124.067835657887 |
| 48 | 1.105532731513 | 16 | 148.799445098402 |
| 56 | 0.951382051686 | 15 | 173.518550400695 |
| 64 | 0.817850659061 | 15 | 198.226956274002 |
| 72 | 0.700067623405 | 14 | 111.463005749806 |
| Target jobs: lower bounds | |||
| 4 | 3.590439381300 | 12 | 14.055033804805 |
| 7 | 3.030823593365 | 11 | 6.138693311557 |
| 8 | 2.897292200740 | 11 | 47.086082174304 |
| 9 | 2.779509165084 | 11 | 367.291038096216 |
| 17 | 2.143520398364 | 10 | 52.865271049404 |
| 25 | 1.757857917552 | 10 | 77.652546021820 |
| 33 | 1.480226180954 | 10 | 102.415450004130 |
| 41 | 1.263161675716 | 9 | 127.160048134959 |
| 49 | 1.084913444309 | 9 | 151.889974497414 |
| 57 | 0.933682474586 | 9 | 176.607655012455 |
| 65 | 0.802346472524 | 8 | 201.314825634830 |
| 73 | 0.686274301272 | 8 | 113.006395319643 |
| 145 | 0 | — | 224 |
Table 2. Exact rational enclosures for the normalized moment terms. The charged-block rows give upper bounds; the target rows give lower bounds. is the number of terms in the logarithm test described in the text.
Since , the stated gap follows.
The completion and splitting estimates also use the scaled target moment . Applying the same upper exponential bound gives
Hence
Set
The rational inequalities
and (2) imply
All numbers used in these comparisons are rational.
A separated tensor construction
We use the completion and splitting argument already present in the earlier construction [5, 9]. The moment estimate is recalled here to make the role of the larger tensor power explicit.
For multisets , , let contain every product , with multiplicity, for and . Moments multiply:
In the -fold tensor unit, choose positive integers as the maximum block rank and minimum target rank. A target of rank is completed to rank by adding a charged block of rank . Targets of rank at least are unchanged. Each charged block of rank is then split into blocks of rank and one remainder block, if needed. Write and for the resulting multisets. Every charged-block rank is at most , and every target rank is at least .
Lemma 4.1 (Completion and splitting). Let and . Then
Proof. When , the sum of the th powers of its pieces is at most
For , the contribution is . Thus a bound valid in both cases is . Summing over the charged blocks in the tensor unit and using (12) gives the first two terms in (13). There is at most one completion block for each target in , and its rank is less than . After splitting, its contribution is at most . If its rank is already at most , its contribution is at most . There are possible completion blocks. Finally, completion only increases target ranks, so their -moment is at least .
Take and . At , division by in Lemma 4.1 reduces the desired comparison to
By Proposition 3.2 and (11), it is enough to prove .
Proposition 4.2. For , the completed and split tensor unit has , and every charged-block rank is smaller than every target rank.
Proof. Exact rational exponentiation gives
Since , and . Also, Bernoulli’s inequality gives . Therefore
The last strict inequality is rational; its slack exceeds . Equations (14)–(15) now give the moment comparison. Rank separation follows from .
The earlier certificate used . At the new rate the available moment gap is much smaller, so increasing lets the two tail terms fall below the accumulated gain in the first term.
Proof of Theorem 1.1. The P16A8Z certificate realizes the raw rank multisets by an exact circuit [9]. Its tensor construction realizes the completed and split multisets used above. Proposition 4.2 supplies the moment comparison and rank separation required by the mixed-target recursion of Sussman [12]. That recursion gives the kernel program used in the reduction to arbitrary transform lengths at any fixed exponent strictly above .
Choose the intermediate saving
Then . With kernel exponent , the Fourier reduction, including its preparation costs, gives
For the positive constant , . This proves the asserted work bound. The fixed-program, root-order, and polynomial integer bounds are supplied by the same reduction. □
Corollary 4.3. In the corresponding exact RAM model allowing multiplication of the two input data streams, the linear convolution of two vectors of length can be computed in work.
Proof. Apply the convolution reduction to transform length . The scalar and pointwise multiplication work is included in that reduction’s cost bound, and . □
Verification and numerical comparison
Theorem 1.1 and the convolution corollary are verified in Lean 4.34.1. Using the development wrapper of Comparator [10], a statement comparison checked the transform theorem against the reference exact-DFT specification at the new rational exponent and rechecked the proof with Lean’s default kernel. The dependency audit reports propositional extensionality, classical choice, and quotient soundness for the transform, convolution, and finite tensor moment theorems. The artifact records these checks and the source changes to the numerical bounds, tensor power, and exponent parameters.
An independent calculation checks the numerical inequalities using exact rational interval arithmetic. It uses an atanh series for logarithms and a separately implemented exponential-series bound, rather than the generator’s logarithm certificates. This check covers the raw moment gap, both tail ratios, and (16).
The interval calculation also resolves the raw balance point more closely. Let . With
the certified signs are . Continuity therefore places a zero in . The same calculation gives , so that parameter fails the raw moment test.
The final Fourier saving remains strictly below this interval because the proof uses slack at both the tensor and Fourier stages. The large fixed tensor power also affects the hidden constants in the work bound.
Acknowledgments
OpenAI ChatGPT Codex was used throughout the research and preparation of this paper. Its contributions included analysis of prior constructions, exploration of candidate improvements, derivation of the numerical bounds, development of Lean proofs and verification scripts, execution and analysis of verification checks, preparation of the reproducibility artifact, and drafting and revision of the manuscript. This work was supported in part by a grant of access to OpenAI models through the ChatGPT for Academic Researchers program.
Artifact availability
The accompanying artifact contains the Lean development, exact rational certificates, an independent arithmetic checker, source provenance, and verification logs. Zenodo DOI: https://doi.org/10.5281/zenodo.23843356.
References
Finite rational bounds
Table 2 lists the logarithm and moment enclosures used in Proposition 3.2. Every displayed decimal in the table is an exact rational with denominator dividing . The multiplicity for each row is given in Table 1.
For , put
For , the same tail argument as in Lemma 3.1 gives . An upper logarithm entry is certified by ; the lower-series inequality holds for all . A lower logarithm entry is certified by . In the latter case, , and the test implies . The charged-block moment bound satisfies . The target bound satisfies . All these tests reduce to integer arithmetic after clearing denominators.
For (9), use the upper logarithm bound , certified by , followed by at .
The independent checker obtains logarithm intervals differently. After writing with , it uses
Here and ; the same formula encloses . For an exponential argument , the checker uses and the upper tail . These bounds also certify the signs reported in § 5 without floating-point acceptance tests.
References
- [1]Josh Alman and Kevin Rao. Faster Walsh–Hadamard and discrete Fourier transforms from matrix non-rigidity. arXiv:2211.06459v2, 2023. https://arxiv.org/abs/2211.06459v2.
- [2]Leo I. Bluestein. A linear filtering approach to the computation of discrete Fourier transform. IEEE Transactions on Audio and Electroacoustics, 18(4):451–455, 1970. https://doi.org/10.1109/TAU.1970.1162132.
- [3]Chrisbryan17. Tighten conditional critical-root transfer to κ = 0.0030201659769 (exact arithmetic). CrocSwap integer-mult-bounds, pull request 4707, 2026. https://github.com/CrocSwap/integer-mult-bounds/pull/4707.
- [4]James W. Cooley and John W. Tukey. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 19(90):297–301, 1965. https://doi.org/10.1090/S0025-5718-1965-0178586-1.
- [5]Cinna Davis. Conditional κ = 0.00268647 via paid target padding after native composition. CrocSwap integer-mult-bounds, pull request 4416, 2026. https://github.com/CrocSwap/integer-mult-bounds/pull/4416.
- [6]Cinna Davis. Conditional κ = 0.00296 via query-thinned productive controllers. CrocSwap integer-mult-bounds, pull request 4440, 2026. https://github.com/CrocSwap/integer-mult-bounds/pull/4440.
- [7]Cinna Davis. Conditional κ = 0.00302015: Joint helper boundaries. CrocSwap integer-mult-bounds, pull request 4470, 2026. https://github.com/CrocSwap/integer-mult-bounds/pull/4470.
- [8]hexapode. Conditional κ = 0.00302016597. CrocSwap integer-mult-bounds, pull request 4568, 2026. https://github.com/CrocSwap/integer-mult-bounds/pull/4568.
- [9]Halit Ziya Kartal. Exact DFT submission: halitziyav4-logception. Big O Speedrun verifier, pull request 41, 2026. Source snapshot 859d6949ef4bdcab4ba661d09cd7fd720d0c4960, directory halitziyarkartal-halitziyav4-logception. https://github.com/bigospeedrun/verifier/pull/41.