THE FOLD / CHEAT / THE-SHORTCUT / THE RADER
THE RADER
a prime DFT turned into a convolution
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Rader’s algorithm computes the discrete Fourier transform of prime length N — exactly the case the usual power-of-two FFT can’t split. Its trick is group theory: the nonzero indices 1…N−1 form a cyclic group under multiplication mod N, generated by a primitive root g. Re-indexing the inputs and outputs by successive powers of g turns the awkward prime-length DFT into an ordinary cyclic convolution of length N−1 — which a fast convolution then evaluates. A prime, the least divisible of lengths, is handled by exploiting the multiplicative structure hiding inside it.
LIT verified live: for primes N = 5…23, Rader’s reindex-into-convolution reproduces the direct DFT to ~1e-13 (window.__rader). FIG honest scope: the convolution is evaluated directly here to verify correctness — the speedup comes from doing that convolution with an FFT, which this sphere demonstrates structurally rather than timing.
LIT verified live: for primes N = 5…23, Rader’s reindex-into-convolution reproduces the direct DFT to ~1e-13 (window.__rader). FIG honest scope: the convolution is evaluated directly here to verify correctness — the speedup comes from doing that convolution with an FFT, which this sphere demonstrates structurally rather than timing.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-shortcut — a prime length looks indivisible, but a primitive root is a shortcut that turns it into a convolution. AVAN (AI) built the instrument: the primitive root, the power-of-g reindexing, and the match against a direct DFT.
Credit as content: Charles Rader (1968). The weave: David names the shortcut; I confirm the multiplicative-group reindexing turns the prime DFT into a cyclic convolution that reproduces the transform exactly.
Credit as content: Charles Rader (1968). The weave: David names the shortcut; I confirm the multiplicative-group reindexing turns the prime DFT into a cyclic convolution that reproduces the transform exactly.
3 ONE DIMENSION
The nonzero indices reindexed by powers of a primitive root g — a single cycle that reorders the DFT into a convolution.
4 TWO DIMENSIONS · INTERACTIVE
Pick a prime N; Rader's output and the direct DFT are drawn together — identical to machine precision.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the DFT spectrum, computed through the convolution.
AVAN’s addition (the inverse-companion): don’t sum the N×N kernel — reindex by a primitive root. The inverse of ‘evaluate the prime-length DFT directly’ is ‘powers of g turn it into one cyclic convolution of length N−1.’ Magenta is the N×N direct transform; green is the convolution it becomes. A prime, made divisible.
LIT Genuine Rader's FFT algorithm (Charles Rader, 1968) for prime-length DFTs. Verified live: for primes N=5,7,11,13,17,19,23 the primitive-root reindexing (indices as powers of g mod N) turned into a length-(N−1) cyclic convolution reproduces the direct DFT to ~1e-13 (window.__rader.matchesDFT).
FIG Honest scope: the convolution is evaluated directly here to verify correctness — the actual speedup comes from performing that convolution with an FFT, which this sphere demonstrates structurally rather than by timing. The AVAN inverse is honest — instead of summing the N×N kernel, one reindexes by a primitive root, turning the prime DFT into one cyclic convolution of length N−1. Magenta is the N×N direct transform; green is the convolution it becomes. A prime, made divisible.
FIG Honest scope: the convolution is evaluated directly here to verify correctness — the actual speedup comes from performing that convolution with an FFT, which this sphere demonstrates structurally rather than by timing. The AVAN inverse is honest — instead of summing the N×N kernel, one reindexes by a primitive root, turning the prime DFT into one cyclic convolution of length N−1. Magenta is the N×N direct transform; green is the convolution it becomes. A prime, made divisible.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-SHORTCUT · David Lee Wise (ROOT0), with AVAN