4 The DFT as Fourier Transform on a Group
The Discrete Fourier Transform (DFT) is one of the most important algorithms in computing. It decomposes a signal into “frequencies” — but what are these frequencies, really?
The answer comes from group theory: the DFT is the Fourier transform on the cyclic group \(\mathbb{Z}/n\mathbb{Z}\). The “frequencies” are the irreducible representations (characters) of this group. The DFT matrix is the character table.
This notebook makes the connection explicit, step by step.
(ns harmonica-book.dft-as-group-fourier
(:require
[scicloj.harmonica :as hm]
[scicloj.harmonica.linalg.complex :as cx]
[harmonica-book.book-helpers :refer [allclose?]]
[fastmath.transform :as t]
[tech.v3.datatype :as dtype]
[tech.v3.datatype.functional :as dfn]
[tech.v3.datatype.convolve :as dt-conv]
[tech.v3.tensor :as tensor]
[tablecloth.api :as tc]
[scicloj.tableplot.v1.plotly :as plotly]
[scicloj.kindly.v4.kind :as kind]))A signal is a function on a group
Suppose we record monthly average temperatures (°C) over two years (we saw this data briefly in the Quickstart — here we develop the theory in full):
(def temperatures
[2 3 7 12 17 22 25 24 19 13 7 3
3 4 8 13 18 23 26 25 20 14 8 4])(-> (tc/dataset {:month (range 24) :temp temperatures})
(plotly/base {:=x :month :=y :temp
:=title "Monthly temperatures — two years of data"
:=x-title "month" :=y-title "°C"})
(plotly/layer-line)
(plotly/layer-point {:=mark-size 5})
plotly/plot)These 24 numbers implicitly define a periodic pattern — after month 23, the cycle repeats. The clear seasonal pattern (cold winters, warm summers) repeats twice.
Mathematically, the indices \(0, \ldots, 23\) form the cyclic group \(\mathbb{Z}/24\mathbb{Z}\): integers with addition mod 24. A signal of length 24 is a function on this group. The “mod” in modular arithmetic captures the periodicity: position 24 wraps around to position 0, just as January follows December.
(def G (hm/cyclic-group 24))(hm/elements G)(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23)The group operation is addition mod 24.
(hm/op G 15 9)0(hm/op G 18 10)4Every element has an inverse.
(hm/inv G 15)9Characters: rotations at different speeds
A character of \(\mathbb{Z}/n\mathbb{Z}\) is a homomorphism from the group to the complex numbers of magnitude 1 — that is, a mapping that preserves the group operation and lands on the unit circle.
For \(\mathbb{Z}/n\mathbb{Z}\), the characters are:
\[\chi_k(g) = \omega^{kg}\]
where \(\omega = e^{2\pi i/n}\) is the primitive \(n\)-th root of unity and \(k = 0, 1, \ldots, n-1\).
Each character \(\chi_k\) is a “rotation at speed \(k\)” — it goes around the unit circle \(k\) times as \(g\) goes from 0 to \(n-1\). This is exactly the “rotations at different speeds” intuition from signal processing.
The character table is the DFT matrix
The character table collects all characters into a matrix. Row \(k\) gives the values of character \(\chi_k\) at each group element.
Why are characters the “right” basis? Consider the shift operator \(T_1 f(g) = f(g - 1)\), which translates a signal by one step. A character \(\chi_k\) is an eigenvector of every shift: \(T_a \chi_k(g) = \chi_k(g - a) = \omega^{-ka} \chi_k(g)\). The eigenvalue \(\omega^{-ka}\) depends on the shift amount but not on \(g\) — this is what makes characters “pure frequencies.” Decomposing into characters diagonalizes all shifts simultaneously.
(def ct (hm/character-table G))ct{:group {:n 24},
:classes
[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23],
:class-sizes [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1],
:irrep-labels
[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23],
:table #ComplexTensor [24 24]
[[1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, ... (24 total)]
[1.0, 0.9659258262890683+0.25881904510252074i, 0.8660254037844387+0.49999999999999994i, 0.7071067811865476+0.7071067811865475i, 0.5000000000000001+0.8660254037844386i, 0.25881904510252096+0.9659258262890682i, 6.123233995736766E-17+1.0i, -0.25881904510252063+0.9659258262890683i, -0.4999999999999998+0.8660254037844387i, -0.7071067811865475+0.7071067811865476i, -0.8660254037844385+0.5000000000000003i, -0.9659258262890682+0.258819045102521i, -1.0+1.2246467991473532E-16i, -0.9659258262890684-0.25881904510252035i, -0.8660254037844388-0.4999999999999997i, -0.7071067811865479-0.7071067811865471i, -0.5000000000000004-0.8660254037844384i, -0.2588190451025215-0.9659258262890681i, -1.8369701987210297E-16-1.0i, 0.2588190451025203-0.9659258262890684i, ... (24 total)]
[1.0, 0.8660254037844387+0.49999999999999994i, 0.5000000000000001+0.8660254037844386i, 6.123233995736766E-17+1.0i, -0.4999999999999998+0.8660254037844387i, -0.8660254037844385+0.5000000000000003i, -1.0+1.2246467991473532E-16i, -0.8660254037844388-0.4999999999999997i, -0.5000000000000004-0.8660254037844384i, -1.8369701987210297E-16-1.0i, 0.49999999999999933-0.866025403784439i, 0.8660254037844384-0.5000000000000004i, 1.0, 0.8660254037844387+0.49999999999999994i, 0.5000000000000001+0.8660254037844386i, 6.123233995736766E-17+1.0i, -0.4999999999999998+0.8660254037844387i, -0.8660254037844385+0.5000000000000003i, -1.0+1.2246467991473532E-16i, -0.8660254037844388-0.4999999999999997i, ... (24 total)]
[1.0, 0.7071067811865476+0.7071067811865475i, 6.123233995736766E-17+1.0i, -0.7071067811865475+0.7071067811865476i, -1.0+1.2246467991473532E-16i, -0.7071067811865479-0.7071067811865471i, -1.8369701987210297E-16-1.0i, 0.7071067811865474-0.7071067811865477i, 1.0, 0.7071067811865476+0.7071067811865475i, 6.123233995736766E-17+1.0i, -0.7071067811865475+0.7071067811865476i, -1.0+1.2246467991473532E-16i, -0.7071067811865479-0.7071067811865471i, -1.8369701987210297E-16-1.0i, 0.7071067811865474-0.7071067811865477i, 1.0, 0.7071067811865476+0.7071067811865475i, 6.123233995736766E-17+1.0i, -0.7071067811865475+0.7071067811865476i, ... (24 total)]
[1.0, 0.5000000000000001+0.8660254037844386i, -0.4999999999999998+0.8660254037844387i, -1.0+1.2246467991473532E-16i, -0.5000000000000004-0.8660254037844384i, 0.49999999999999933-0.866025403784439i, 1.0, 0.5000000000000001+0.8660254037844386i, -0.4999999999999998+0.8660254037844387i, -1.0+1.2246467991473532E-16i, -0.5000000000000004-0.8660254037844384i, 0.49999999999999933-0.866025403784439i, 1.0, 0.5000000000000001+0.8660254037844386i, -0.4999999999999998+0.8660254037844387i, -1.0+1.2246467991473532E-16i, -0.5000000000000004-0.8660254037844384i, 0.49999999999999933-0.866025403784439i, 1.0, 0.5000000000000001+0.8660254037844386i, ... (24 total)]
[1.0, 0.25881904510252096+0.9659258262890682i, -0.8660254037844385+0.5000000000000003i, -0.7071067811865479-0.7071067811865471i, 0.49999999999999933-0.866025403784439i, 0.9659258262890683+0.25881904510252074i, 6.123233995736766E-17+1.0i, -0.9659258262890682+0.258819045102521i, -0.5000000000000004-0.8660254037844384i, 0.7071067811865474-0.7071067811865477i, 0.8660254037844387+0.49999999999999994i, -0.25881904510252063+0.9659258262890683i, -1.0+1.2246467991473532E-16i, -0.2588190451025215-0.9659258262890681i, 0.8660254037844384-0.5000000000000004i, 0.7071067811865476+0.7071067811865475i, -0.4999999999999998+0.8660254037844387i, -0.9659258262890684-0.25881904510252035i, -1.8369701987210297E-16-1.0i, 0.9659258262890681-0.25881904510252157i, ... (24 total)]
[1.0, 6.123233995736766E-17+1.0i, -1.0+1.2246467991473532E-16i, -1.8369701987210297E-16-1.0i, 1.0, 6.123233995736766E-17+1.0i, -1.0+1.2246467991473532E-16i, -1.8369701987210297E-16-1.0i, 1.0, 6.123233995736766E-17+1.0i, -1.0+1.2246467991473532E-16i, -1.8369701987210297E-16-1.0i, 1.0, 6.123233995736766E-17+1.0i, -1.0+1.2246467991473532E-16i, -1.8369701987210297E-16-1.0i, 1.0, 6.123233995736766E-17+1.0i, -1.0+1.2246467991473532E-16i, -1.8369701987210297E-16-1.0i, ... (24 total)]
[1.0, -0.25881904510252063+0.9659258262890683i, -0.8660254037844388-0.4999999999999997i, 0.7071067811865474-0.7071067811865477i, 0.5000000000000001+0.8660254037844386i, -0.9659258262890682+0.258819045102521i, -1.8369701987210297E-16-1.0i, 0.9659258262890683+0.25881904510252074i, -0.4999999999999998+0.8660254037844387i, -0.7071067811865479-0.7071067811865471i, 0.8660254037844384-0.5000000000000004i, 0.25881904510252096+0.9659258262890682i, -1.0+1.2246467991473532E-16i, 0.2588190451025203-0.9659258262890684i, 0.8660254037844387+0.49999999999999994i, -0.7071067811865475+0.7071067811865476i, -0.5000000000000004-0.8660254037844384i, 0.9659258262890681-0.25881904510252157i, 6.123233995736766E-17+1.0i, -0.9659258262890684-0.25881904510252035i, ... (24 total)]
[1.0, -0.4999999999999998+0.8660254037844387i, -0.5000000000000004-0.8660254037844384i, 1.0, -0.4999999999999998+0.8660254037844387i, -0.5000000000000004-0.8660254037844384i, 1.0, -0.4999999999999998+0.8660254037844387i, -0.5000000000000004-0.8660254037844384i, 1.0, -0.4999999999999998+0.8660254037844387i, -0.5000000000000004-0.8660254037844384i, 1.0, -0.4999999999999998+0.8660254037844387i, -0.5000000000000004-0.8660254037844384i, 1.0, -0.4999999999999998+0.8660254037844387i, -0.5000000000000004-0.8660254037844384i, 1.0, -0.4999999999999998+0.8660254037844387i, ... (24 total)]
[1.0, -0.7071067811865475+0.7071067811865476i, -1.8369701987210297E-16-1.0i, 0.7071067811865476+0.7071067811865475i, -1.0+1.2246467991473532E-16i, 0.7071067811865474-0.7071067811865477i, 6.123233995736766E-17+1.0i, -0.7071067811865479-0.7071067811865471i, 1.0, -0.7071067811865475+0.7071067811865476i, -1.8369701987210297E-16-1.0i, 0.7071067811865476+0.7071067811865475i, -1.0+1.2246467991473532E-16i, 0.7071067811865474-0.7071067811865477i, 6.123233995736766E-17+1.0i, -0.7071067811865479-0.7071067811865471i, 1.0, -0.7071067811865475+0.7071067811865476i, -1.8369701987210297E-16-1.0i, 0.7071067811865476+0.7071067811865475i, ... (24 total)]
[1.0, -0.8660254037844385+0.5000000000000003i, 0.49999999999999933-0.866025403784439i, 6.123233995736766E-17+1.0i, -0.5000000000000004-0.8660254037844384i, 0.8660254037844387+0.49999999999999994i, -1.0+1.2246467991473532E-16i, 0.8660254037844384-0.5000000000000004i, -0.4999999999999998+0.8660254037844387i, -1.8369701987210297E-16-1.0i, 0.5000000000000001+0.8660254037844386i, -0.8660254037844388-0.4999999999999997i, 1.0, -0.8660254037844385+0.5000000000000003i, 0.49999999999999933-0.866025403784439i, 6.123233995736766E-17+1.0i, -0.5000000000000004-0.8660254037844384i, 0.8660254037844387+0.49999999999999994i, -1.0+1.2246467991473532E-16i, 0.8660254037844384-0.5000000000000004i, ... (24 total)]
[1.0, -0.9659258262890682+0.258819045102521i, 0.8660254037844384-0.5000000000000004i, -0.7071067811865475+0.7071067811865476i, 0.49999999999999933-0.866025403784439i, -0.25881904510252063+0.9659258262890683i, -1.8369701987210297E-16-1.0i, 0.25881904510252096+0.9659258262890682i, -0.5000000000000004-0.8660254037844384i, 0.7071067811865476+0.7071067811865475i, -0.8660254037844388-0.4999999999999997i, 0.9659258262890683+0.25881904510252074i, -1.0+1.2246467991473532E-16i, 0.9659258262890681-0.25881904510252157i, -0.8660254037844385+0.5000000000000003i, 0.7071067811865474-0.7071067811865477i, -0.4999999999999998+0.8660254037844387i, 0.2588190451025203-0.9659258262890684i, 6.123233995736766E-17+1.0i, -0.2588190451025215-0.9659258262890681i, ... (24 total)]
[1.0, -1.0+1.2246467991473532E-16i, 1.0, -1.0+1.2246467991473532E-16i, 1.0, -1.0+1.2246467991473532E-16i, 1.0, -1.0+1.2246467991473532E-16i, 1.0, -1.0+1.2246467991473532E-16i, 1.0, -1.0+1.2246467991473532E-16i, 1.0, -1.0+1.2246467991473532E-16i, 1.0, -1.0+1.2246467991473532E-16i, 1.0, -1.0+1.2246467991473532E-16i, 1.0, -1.0+1.2246467991473532E-16i, ... (24 total)]
[1.0, -0.9659258262890684-0.25881904510252035i, 0.8660254037844387+0.49999999999999994i, -0.7071067811865479-0.7071067811865471i, 0.5000000000000001+0.8660254037844386i, -0.2588190451025215-0.9659258262890681i, 6.123233995736766E-17+1.0i, 0.2588190451025203-0.9659258262890684i, -0.4999999999999998+0.8660254037844387i, 0.7071067811865474-0.7071067811865477i, -0.8660254037844385+0.5000000000000003i, 0.9659258262890681-0.25881904510252157i, -1.0+1.2246467991473532E-16i, 0.9659258262890683+0.25881904510252074i, -0.8660254037844388-0.4999999999999997i, 0.7071067811865476+0.7071067811865475i, -0.5000000000000004-0.8660254037844384i, 0.25881904510252096+0.9659258262890682i, -1.8369701987210297E-16-1.0i, -0.25881904510252063+0.9659258262890683i, ... (24 total)]
[1.0, -0.8660254037844388-0.4999999999999997i, 0.5000000000000001+0.8660254037844386i, -1.8369701987210297E-16-1.0i, -0.4999999999999998+0.8660254037844387i, 0.8660254037844384-0.5000000000000004i, -1.0+1.2246467991473532E-16i, 0.8660254037844387+0.49999999999999994i, -0.5000000000000004-0.8660254037844384i, 6.123233995736766E-17+1.0i, 0.49999999999999933-0.866025403784439i, -0.8660254037844385+0.5000000000000003i, 1.0, -0.8660254037844388-0.4999999999999997i, 0.5000000000000001+0.8660254037844386i, -1.8369701987210297E-16-1.0i, -0.4999999999999998+0.8660254037844387i, 0.8660254037844384-0.5000000000000004i, -1.0+1.2246467991473532E-16i, 0.8660254037844387+0.49999999999999994i, ... (24 total)]
[1.0, -0.7071067811865479-0.7071067811865471i, 6.123233995736766E-17+1.0i, 0.7071067811865474-0.7071067811865477i, -1.0+1.2246467991473532E-16i, 0.7071067811865476+0.7071067811865475i, -1.8369701987210297E-16-1.0i, -0.7071067811865475+0.7071067811865476i, 1.0, -0.7071067811865479-0.7071067811865471i, 6.123233995736766E-17+1.0i, 0.7071067811865474-0.7071067811865477i, -1.0+1.2246467991473532E-16i, 0.7071067811865476+0.7071067811865475i, -1.8369701987210297E-16-1.0i, -0.7071067811865475+0.7071067811865476i, 1.0, -0.7071067811865479-0.7071067811865471i, 6.123233995736766E-17+1.0i, 0.7071067811865474-0.7071067811865477i, ... (24 total)]
[1.0, -0.5000000000000004-0.8660254037844384i, -0.4999999999999998+0.8660254037844387i, 1.0, -0.5000000000000004-0.8660254037844384i, -0.4999999999999998+0.8660254037844387i, 1.0, -0.5000000000000004-0.8660254037844384i, -0.4999999999999998+0.8660254037844387i, 1.0, -0.5000000000000004-0.8660254037844384i, -0.4999999999999998+0.8660254037844387i, 1.0, -0.5000000000000004-0.8660254037844384i, -0.4999999999999998+0.8660254037844387i, 1.0, -0.5000000000000004-0.8660254037844384i, -0.4999999999999998+0.8660254037844387i, 1.0, -0.5000000000000004-0.8660254037844384i, ... (24 total)]
[1.0, -0.2588190451025215-0.9659258262890681i, -0.8660254037844385+0.5000000000000003i, 0.7071067811865476+0.7071067811865475i, 0.49999999999999933-0.866025403784439i, -0.9659258262890684-0.25881904510252035i, 6.123233995736766E-17+1.0i, 0.9659258262890681-0.25881904510252157i, -0.5000000000000004-0.8660254037844384i, -0.7071067811865475+0.7071067811865476i, 0.8660254037844387+0.49999999999999994i, 0.2588190451025203-0.9659258262890684i, -1.0+1.2246467991473532E-16i, 0.25881904510252096+0.9659258262890682i, 0.8660254037844384-0.5000000000000004i, -0.7071067811865479-0.7071067811865471i, -0.4999999999999998+0.8660254037844387i, 0.9659258262890683+0.25881904510252074i, -1.8369701987210297E-16-1.0i, -0.9659258262890682+0.258819045102521i, ... (24 total)]
[1.0, -1.8369701987210297E-16-1.0i, -1.0+1.2246467991473532E-16i, 6.123233995736766E-17+1.0i, 1.0, -1.8369701987210297E-16-1.0i, -1.0+1.2246467991473532E-16i, 6.123233995736766E-17+1.0i, 1.0, -1.8369701987210297E-16-1.0i, -1.0+1.2246467991473532E-16i, 6.123233995736766E-17+1.0i, 1.0, -1.8369701987210297E-16-1.0i, -1.0+1.2246467991473532E-16i, 6.123233995736766E-17+1.0i, 1.0, -1.8369701987210297E-16-1.0i, -1.0+1.2246467991473532E-16i, 6.123233995736766E-17+1.0i, ... (24 total)]
[1.0, 0.2588190451025203-0.9659258262890684i, -0.8660254037844388-0.4999999999999997i, -0.7071067811865475+0.7071067811865476i, 0.5000000000000001+0.8660254037844386i, 0.9659258262890681-0.25881904510252157i, -1.8369701987210297E-16-1.0i, -0.9659258262890684-0.25881904510252035i, -0.4999999999999998+0.8660254037844387i, 0.7071067811865476+0.7071067811865475i, 0.8660254037844384-0.5000000000000004i, -0.2588190451025215-0.9659258262890681i, -1.0+1.2246467991473532E-16i, -0.25881904510252063+0.9659258262890683i, 0.8660254037844387+0.49999999999999994i, 0.7071067811865474-0.7071067811865477i, -0.5000000000000004-0.8660254037844384i, -0.9659258262890682+0.258819045102521i, 6.123233995736766E-17+1.0i, 0.9659258262890683+0.25881904510252074i, ... (24 total)]
... (24 rows total)]}All entries have magnitude 1 (they lie on the unit circle).
(allclose? (cx/cabs (:table ct)) 1.0)trueThe first row (\(k = 0\)) is the trivial character — all ones.
(allclose? (cx/re ((:table ct) 0)) 1.0)trueLet’s visualize a few characters as rotations. Character \(\chi_k\) completes \(k\) full rotations over the 24 group elements.
(-> (tc/dataset
(let [table (:table ct)]
(for [k [0 1 2 3]
g (range 24)]
{:month g
:real-part (cx/re ((table k) g))
:character (str "chi_" k)})))
(plotly/base {:=x :month
:=y :real-part
:=color :character
:=x-title "Group element g (month)"
:=y-title "Re(chi_k(g))"
:=title "Characters of Z/24Z — real parts (cosine components)"})
(plotly/layer-line)
(plotly/layer-point {:=mark-size 6})
plotly/plot)Each character oscillates at a different rate — exactly the cosine waves at different frequencies that the DFT decomposes a signal into. Character \(\chi_2\) completes two full cycles in 24 months — the annual frequency.
Fourier transform on the group
The Fourier transform of a function \(f\) on a finite group is:
\[\hat{f}(k) = \sum_{g \in G} f(g) \cdot \overline{\chi_k(g)}\]
This is an inner product: “how much does \(f\) align with character \(\chi_k\)?” For \(\mathbb{Z}/n\mathbb{Z}\), this is exactly the DFT formula.
(def signal (cx/complex-tensor-real temperatures))signal#ComplexTensor [24]
[2.0, 3.0, 7.0, 12.0, 17.0, 22.0, 25.0, 24.0, 19.0, 13.0, 7.0, 3.0, 3.0, 4.0, 8.0, 13.0, 18.0, 23.0, 26.0, 25.0, ... (24 total)](def f-hat (hm/fourier-transform ct signal))f-hat#ComplexTensor [24]
[320.0, -1.0000000000000484+7.5957541127251424i, -137.2820323027551+7.464101615137718i, -1.0000000000000213+2.414213562373079i, 5.999999999999962-6.928203230275513i, -1.000000000000032+1.3032253728412102i, -2.000000000000009+1.9999999999999902i, -1.0000000000000342+0.7673269879789584i, 1.9999999999999751-3.108624468950438E-14i, -1.0000000000000244+0.41421356237308116i, 1.2820323027550629+0.5358983848622507i, -1.000000000000047+0.1316524975873985i, -1.9594348786357652E-14i, -1.0000000000000444-0.13165249758739717i, 1.2820323027550633-0.5358983848622372i, -1.0000000000000246-0.41421356237311135i, 1.999999999999976-4.218847493575595E-14i, -1.000000000000035-0.7673269879789588i, -2.0000000000000075-2.0000000000000098i, -1.0000000000000284-1.3032253728412089i, ... (24 total)]The \(k = 0\) coefficient is the sum of all values (the DC component).
(cx/re (f-hat 0))320.0Let’s see the magnitude spectrum — how strong each “frequency” is.
(-> (tc/dataset
{:frequency (range 24)
:magnitude (vec (cx/cabs f-hat))})
(plotly/base {:=x :frequency
:=y :magnitude
:=x-title "Frequency k (character index)"
:=y-title "|f-hat(k)|"
:=title "Fourier spectrum of monthly temperatures on Z/24Z"})
(plotly/layer-line)
(plotly/layer-point {:=mark-size 6})
plotly/plot)The dominant oscillating component is \(k = 2\) — two complete cycles over the 24-month window, i.e. the annual cycle (period = 12 months).
You’ll also notice a matching peak at \(k = 22\). This is not a separate physical phenomenon — for real-valued signals, the DFT spectrum is always symmetric: the component at \(k\) and the component at \(n - k\) are complex conjugates of each other (\(n = 24\) here, so \(k = 2\) and \(k = 22 = 24 - 2\) carry the same information).
Beyond the annual cycle, a few smaller components are visible above the noise floor: \(k = 4\) and \(k = 20\) (the semi-annual harmonic, period = 6 months) and \(k = 1\) and \(k = 23\) (a slow drift over the 2-year window). Each pair is again a component and its conjugate mirror.
Comparison with the standard FFT
Let’s verify that our group-theoretic Fourier transform gives the same result as the standard FFT from fastmath.
The fastmath FFT returns interleaved [re_0, im_0, re_1, im_1, ...] for the first \(N/2\) coefficients (exploiting Hermitian symmetry). We extract them and compare magnitudes with our full result.
(let [fft-result (t/forward-1d (t/transformer :real :fft) temperatures)
fft-coefficients (let [data (vec fft-result)
n (/ (count data) 2)]
(cx/complex-tensor
(mapv (fn [k] (data (* 2 k))) (range n))
(mapv (fn [k] (data (inc (* 2 k)))) (range n))))]
(allclose? (dtype/sub-buffer (cx/cabs f-hat) 0 12)
(cx/cabs fft-coefficients)
1e-8))trueThe magnitudes match. The group-theoretic Fourier transform and the standard DFT compute exactly the same thing — because they are the same thing.
Character orthogonality
The characters of a finite group satisfy beautiful orthogonality relations. These are not just mathematical curiosities — they are what make the Fourier transform invertible.
Row orthogonality: different characters are orthogonal.
\[\frac{1}{|G|} \sum_{g \in G} \chi_j(g) \overline{\chi_k(g)} = \delta_{jk}\]
(def orthogonality-matrix
(let [table (:table ct)
sizes (:class-sizes ct)
n 24]
(tensor/compute-tensor
[n n]
(fn [j k]
(cx/cabs (hm/character-inner-product (table j) (table k) sizes n)))
:float64)))orthogonality-matrix#tech.v3.tensor<float64>[24 24]
[[ 1.000 1.070E-16 9.435E-17 8.605E-17 1.249E-16 1.114E-16 6.137E-17 1.114E-16 1.334E-16 6.939E-17 8.937E-17 1.114E-16 6.123E-17 1.112E-16 9.355E-17 8.092E-17 1.334E-16 1.114E-16 4.075E-17 1.110E-16 1.295E-16 7.657E-17 9.392E-17 1.110E-16]
[1.070E-16 1.000 1.206E-16 4.163E-17 4.189E-17 9.483E-17 1.463E-17 3.146E-17 5.628E-17 7.140E-17 2.776E-17 7.864E-17 1.407E-17 4.626E-18 1.156E-17 2.814E-17 3.523E-17 7.170E-17 4.626E-17 5.320E-17 4.626E-18 5.395E-17 3.815E-17 4.626E-17]
[9.435E-17 1.206E-16 1.000 1.963E-17 1.110E-16 3.701E-17 7.459E-17 1.034E-17 3.336E-17 6.939E-18 1.619E-17 3.730E-17 3.730E-17 1.208E-16 9.252E-18 1.552E-17 5.551E-17 2.776E-17 8.530E-17 1.034E-17 2.785E-17 1.034E-17 1.272E-16 4.138E-17]
[8.605E-17 4.163E-17 1.963E-17 1.000 1.463E-17 3.271E-17 9.537E-17 5.796E-17 1.407E-17 5.801E-17 2.313E-17 6.877E-17 5.274E-17 2.861E-17 9.252E-18 0.000 1.246E-17 3.730E-17 3.103E-17 7.046E-17 1.668E-17 5.551E-17 2.313E-18 5.594E-17]
[1.249E-16 4.189E-17 1.110E-16 1.463E-17 1.000 4.626E-18 2.313E-18 2.776E-17 1.538E-16 1.034E-17 3.336E-17 0.000 1.156E-16 3.730E-17 1.068E-16 9.537E-18 5.160E-17 6.542E-18 1.246E-17 2.776E-17 1.110E-16 5.172E-18 2.962E-17 1.156E-17]
[1.114E-16 9.483E-17 3.701E-17 3.271E-17 4.626E-18 1.000 1.034E-17 6.939E-17 2.962E-17 5.796E-17 1.181E-16 4.039E-17 1.668E-17 7.170E-17 3.271E-17 5.110E-17 5.670E-17 4.626E-18 4.626E-17 5.089E-17 4.163E-17 7.046E-17 1.308E-17 4.649E-17]
[6.137E-17 1.463E-17 7.459E-17 9.537E-17 2.313E-18 1.034E-17 1.000 4.170E-17 4.626E-18 2.814E-17 7.459E-17 5.089E-17 6.021E-17 1.463E-17 8.530E-17 9.310E-17 1.684E-17 1.907E-17 0.000 4.632E-17 2.313E-18 3.523E-17 8.530E-17 4.491E-17]
[1.114E-16 3.146E-17 1.034E-17 5.796E-17 2.776E-17 6.939E-17 4.170E-17 1.000 5.670E-17 3.271E-17 3.730E-17 9.714E-17 1.463E-17 5.782E-17 1.250E-16 7.459E-17 3.730E-17 5.089E-17 1.407E-17 4.626E-18 0.000 4.718E-17 2.814E-17 6.939E-17]
[1.334E-16 5.628E-17 3.336E-17 1.407E-17 1.538E-16 2.962E-17 4.626E-18 5.670E-17 1.000 1.907E-17 5.556E-17 4.364E-17 1.850E-17 5.947E-17 2.785E-17 1.850E-17 2.220E-16 3.730E-17 2.617E-17 6.124E-17 5.160E-17 1.481E-17 5.594E-17 3.730E-17]
[6.939E-17 7.140E-17 6.939E-18 5.801E-17 1.034E-17 5.796E-17 2.814E-17 3.271E-17 1.907E-17 1.000 6.542E-18 3.312E-17 6.206E-17 5.395E-17 1.976E-17 5.551E-17 1.552E-17 7.046E-17 8.898E-17 4.265E-17 9.537E-18 0.000 1.806E-17 3.271E-17]
[8.937E-17 2.776E-17 1.619E-17 2.313E-17 3.336E-17 1.181E-16 7.459E-17 3.730E-17 5.556E-17 6.542E-18 1.000 2.313E-17 2.785E-17 3.701E-17 1.110E-16 1.156E-17 3.730E-17 1.227E-16 8.442E-17 3.730E-17 1.114E-16 6.939E-18 9.252E-18 1.481E-17]
[1.114E-16 7.864E-17 3.730E-17 6.877E-17 0.000 4.039E-17 5.089E-17 9.714E-17 4.364E-17 3.312E-17 2.313E-17 1.000 1.463E-17 5.570E-17 2.776E-17 5.004E-17 5.851E-17 4.304E-17 1.668E-17 6.939E-17 3.238E-17 2.926E-17 1.205E-16 4.626E-18]
[6.123E-17 1.407E-17 3.730E-17 5.274E-17 1.156E-16 1.668E-17 6.021E-17 1.463E-17 1.850E-17 6.206E-17 2.785E-17 1.463E-17 1.000 1.865E-17 3.701E-17 5.089E-17 1.850E-17 1.850E-17 7.705E-17 1.850E-17 1.156E-16 5.722E-17 3.238E-17 1.552E-17]
[1.112E-16 4.626E-18 1.208E-16 2.861E-17 3.730E-17 7.170E-17 1.463E-17 5.782E-17 5.947E-17 5.395E-17 3.701E-17 5.570E-17 1.865E-17 1.000 2.313E-17 4.718E-17 3.730E-17 8.558E-17 4.626E-17 4.039E-17 4.626E-18 7.046E-17 3.815E-17 7.401E-17]
[9.355E-17 1.156E-17 9.252E-18 9.252E-18 1.068E-16 3.271E-17 8.530E-17 1.250E-16 2.785E-17 1.976E-17 1.110E-16 2.776E-17 3.701E-17 2.313E-17 1.000 8.340E-18 6.943E-17 3.271E-17 7.918E-17 1.342E-16 2.962E-17 1.668E-17 4.626E-18 3.271E-17]
[8.092E-17 2.814E-17 1.552E-17 0.000 9.537E-18 5.110E-17 9.310E-17 7.459E-17 1.850E-17 5.551E-17 1.156E-17 5.004E-17 5.089E-17 4.718E-17 8.340E-18 1.000 1.463E-17 3.368E-17 3.925E-17 5.796E-17 6.939E-18 5.570E-17 1.034E-17 6.877E-17]
[1.334E-16 3.523E-17 5.551E-17 1.246E-17 5.160E-17 5.670E-17 1.684E-17 3.730E-17 2.220E-16 1.552E-17 3.730E-17 5.851E-17 1.850E-17 3.730E-17 6.943E-17 1.463E-17 1.000 6.124E-17 1.481E-17 4.138E-17 1.492E-16 6.542E-18 3.103E-17 5.851E-17]
[1.114E-16 7.170E-17 2.776E-17 3.730E-17 6.542E-18 4.626E-18 1.907E-17 5.089E-17 3.730E-17 7.046E-17 1.227E-16 4.304E-17 1.850E-17 8.558E-17 3.271E-17 3.368E-17 6.124E-17 1.000 5.089E-17 7.401E-17 2.926E-17 5.395E-17 1.308E-17 2.384E-17]
[4.075E-17 4.626E-17 8.530E-17 3.103E-17 1.246E-17 4.626E-17 0.000 1.407E-17 2.617E-17 8.898E-17 8.442E-17 1.668E-17 7.705E-17 4.626E-17 7.918E-17 3.925E-17 1.481E-17 5.089E-17 1.000 1.552E-17 4.626E-18 1.016E-16 7.918E-17 1.246E-17]
[1.110E-16 5.320E-17 1.034E-17 7.046E-17 2.776E-17 5.089E-17 4.632E-17 4.626E-18 6.124E-17 4.265E-17 3.730E-17 6.939E-17 1.850E-17 4.039E-17 1.342E-16 5.796E-17 4.138E-17 7.401E-17 1.552E-17 1.000 0.000 3.368E-17 2.814E-17 9.252E-17]
[1.295E-16 4.626E-18 2.785E-17 1.668E-17 1.110E-16 4.163E-17 2.313E-18 0.000 5.160E-17 9.537E-18 1.114E-16 3.238E-17 1.156E-16 4.626E-18 2.962E-17 6.939E-18 1.492E-16 2.926E-17 4.626E-18 0.000 1.000 1.668E-17 1.119E-16 3.238E-17]
[7.657E-17 5.395E-17 1.034E-17 5.551E-17 5.172E-18 7.046E-17 3.523E-17 4.718E-17 1.481E-17 0.000 6.939E-18 2.926E-17 5.722E-17 7.046E-17 1.668E-17 5.570E-17 6.542E-18 5.395E-17 1.016E-16 3.368E-17 1.668E-17 1.000 1.034E-17 3.730E-17]
[9.392E-17 3.815E-17 1.272E-16 2.313E-18 2.962E-17 1.308E-17 8.530E-17 2.814E-17 5.594E-17 1.806E-17 9.252E-18 1.205E-16 3.238E-17 3.815E-17 4.626E-18 1.034E-17 3.103E-17 1.308E-17 7.918E-17 2.814E-17 1.119E-16 1.034E-17 1.000 1.206E-16]
[1.110E-16 4.626E-17 4.138E-17 5.594E-17 1.156E-17 4.649E-17 4.491E-17 6.939E-17 3.730E-17 3.271E-17 1.481E-17 4.626E-18 1.552E-17 7.401E-17 3.271E-17 6.877E-17 5.851E-17 2.384E-17 1.246E-17 9.252E-17 3.238E-17 3.730E-17 1.206E-16 1.000]]The matrix is the 24x24 identity (to numerical precision) — 1 on the diagonal, effectively 0 everywhere else.
(allclose? orthogonality-matrix
(tensor/compute-tensor [24 24] (fn [j k] (if (= j k) 1.0 0.0)) :float64))truePerfect reconstruction
The inverse Fourier transform recovers the original signal exactly.
\[f(g) = \frac{1}{|G|} \sum_{k} \hat{f}(k) \cdot \chi_k(g)\]
(let [reconstructed (hm/inverse-fourier-transform ct f-hat)]
(dfn/reduce-max (cx/cabs (cx/csub reconstructed signal))))2.904348053629478E-14The convolution theorem
On any finite group, convolution in the group domain corresponds to pointwise multiplication in the Fourier domain.
\[(f * h)(g) = \sum_{x \in G} f(x) \cdot h(x^{-1}g)\]
In the Fourier domain:
\[\widehat{f * h}(k) = \hat{f}(k) \cdot \hat{h}(k)\]
For \(\mathbb{Z}/n\mathbb{Z}\), this is the familiar cyclic convolution theorem. It is the reason fast convolution is possible: instead of \(O(n^2)\) direct summation, we can compute forward FFT, pointwise multiply, and inverse FFT in \(O(n \log n)\).
(def f-fn (cx/complex-tensor-real
[1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3]))(def h-fn (cx/complex-tensor-real
[0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]))Convolve via the library (which uses the Fourier domain internally).
(def convolved (hm/convolve ct f-fn h-fn))(mapv #(Math/round %) (vec (cx/re convolved)))[3 4 3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]Verify: the Fourier transform of the convolution equals the pointwise product of the individual transforms.
(let [f-fn-hat (hm/fourier-transform ct f-fn)
h-fn-hat (hm/fourier-transform ct h-fn)
convolved-hat (hm/fourier-transform ct convolved)
pointwise-product (cx/cmul f-fn-hat h-fn-hat)]
(< (dfn/reduce-max (cx/cabs (cx/csub convolved-hat pointwise-product))) 1e-8))trueParseval’s theorem (energy conservation)
The total “energy” of a signal is preserved under the Fourier transform. This guarantees that the transform is an isometry — no information is lost or amplified when changing between the time and frequency domains.
\[\sum_{g} |f(g)|^2 = \frac{1}{|G|} \sum_{k} |\hat{f}(k)|^2\]
(let [mag-s (cx/cabs signal)
mag-f (cx/cabs f-hat)
energy-time (dfn/sum (dfn/* mag-s mag-s))
energy-freq (/ (dfn/sum (dfn/* mag-f mag-f))
(double (hm/order G)))]
(< (Math/abs (- energy-time energy-freq)) 1e-8))trueConnection to dtype-next convolution
The dtype-next library provides convolve1d for efficient real-valued linear convolution. For signals on cyclic groups, cyclic convolution can be obtained from a full linear convolution by folding the overflow back around.
(def f-real
[1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3])(def h-real
[0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0])Full linear convolution has length \(2n - 1\).
(def linear-conv
(vec (dt-conv/convolve1d f-real h-real {:mode :full :edge-mode :zero})))(count linear-conv)47To get cyclic convolution, fold the tail back onto the first \(n\) elements.
(def cyclic-from-linear
(let [n 24]
(mapv (fn [i]
(+ (linear-conv i)
(if (< (+ i n) (count linear-conv))
(linear-conv (+ i n))
0.0)))
(range n))))cyclic-from-linear[3.0
4.0
3.0
2.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0]This matches our group-theoretic convolution exactly.
(let [group-conv (cx/re (hm/convolve ct
(cx/complex-tensor-real f-real)
(cx/complex-tensor-real h-real)))]
(allclose? cyclic-from-linear group-conv))trueThe connection: harmonica’s convolve computes cyclic convolution via the group Fourier transform (pointwise multiply in the frequency domain), which is equivalent to folding a linear convolution. For real-valued signals, dtype-next’s convolve1d provides the fast underlying linear convolution; harmonica adds the group-theoretic structure.
What comes next
The cyclic group is the simplest case. The same framework — groups, characters, Fourier transform — extends to every finite group:
Product groups \(G_1 \times G_2\) — componentwise operations, giving the 2D DFT as a special case. See the next chapter. Random Walks and Convolution explores what happens when you convolve a step distribution repeatedly.
Dihedral groups \(D_n\) — symmetries of regular polygons, used for rosette patterns, Burnside counting, and musical pitch classes.
Symmetric groups \(S_n\) — where characters are indexed by partitions and the Fourier transform produces matrix-valued coefficients. See Symmetric Groups, Character Theory, and Random Transpositions.
The harmonica library builds all of these on the same protocol foundation demonstrated here.