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.lalinea.tensor :as t]
   [scicloj.lalinea.elementwise :as el]
   [harmonica-book.book-helpers :refer [allclose?]]
   [fastmath.transform :as ft]
   [tech.v3.datatype.convolve :as dt-conv]
   [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)
4

Every element has an inverse.

(hm/inv G 15)
9

Characters: 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 #la/C [:float64 [24 24]
       [[1.000 + 0.000 i       1.000 + 0.000 i       1.000 + 0.000 i       1.000 + 0.000 i       1.000 + 0.000 i       1.000 + 0.000 i       1.000 + 0.000 i       1.000 + 0.000 i     1.000 + 0.000 i       1.000 + 0.000 i       1.000 + 0.000 i       1.000 + 0.000 i       1.000 + 0.000 i       1.000 + 0.000 i       1.000 + 0.000 i       1.000 + 0.000 i     1.000 + 0.000 i       1.000 + 0.000 i       1.000 + 0.000 i       1.000 + 0.000 i  ...]
        [1.000 + 0.000 i     0.9659 + 0.2588 i     0.8660 + 0.5000 i     0.7071 + 0.7071 i     0.5000 + 0.8660 i     0.2588 + 0.9659 i   6.123E-17 + 1.000 i    -0.2588 + 0.9659 i  -0.5000 + 0.8660 i    -0.7071 + 0.7071 i    -0.8660 + 0.5000 i    -0.9659 + 0.2588 i  -1.000 + 1.225E-16 i    -0.9659 - 0.2588 i    -0.8660 - 0.5000 i    -0.7071 - 0.7071 i  -0.5000 - 0.8660 i    -0.2588 - 0.9659 i  -1.837E-16 - 1.000 i     0.2588 - 0.9659 i  ...]
        [1.000 + 0.000 i     0.8660 + 0.5000 i     0.5000 + 0.8660 i   6.123E-17 + 1.000 i    -0.5000 + 0.8660 i    -0.8660 + 0.5000 i  -1.000 + 1.225E-16 i    -0.8660 - 0.5000 i  -0.5000 - 0.8660 i  -1.837E-16 - 1.000 i     0.5000 - 0.8660 i     0.8660 - 0.5000 i       1.000 + 0.000 i     0.8660 + 0.5000 i     0.5000 + 0.8660 i   6.123E-17 + 1.000 i  -0.5000 + 0.8660 i    -0.8660 + 0.5000 i  -1.000 + 1.225E-16 i    -0.8660 - 0.5000 i  ...]
        [1.000 + 0.000 i     0.7071 + 0.7071 i   6.123E-17 + 1.000 i    -0.7071 + 0.7071 i  -1.000 + 1.225E-16 i    -0.7071 - 0.7071 i  -1.837E-16 - 1.000 i     0.7071 - 0.7071 i     1.000 + 0.000 i     0.7071 + 0.7071 i   6.123E-17 + 1.000 i    -0.7071 + 0.7071 i  -1.000 + 1.225E-16 i    -0.7071 - 0.7071 i  -1.837E-16 - 1.000 i     0.7071 - 0.7071 i     1.000 + 0.000 i     0.7071 + 0.7071 i   6.123E-17 + 1.000 i    -0.7071 + 0.7071 i  ...]
        [1.000 + 0.000 i     0.5000 + 0.8660 i    -0.5000 + 0.8660 i  -1.000 + 1.225E-16 i    -0.5000 - 0.8660 i     0.5000 - 0.8660 i       1.000 + 0.000 i     0.5000 + 0.8660 i  -0.5000 + 0.8660 i  -1.000 + 1.225E-16 i    -0.5000 - 0.8660 i     0.5000 - 0.8660 i       1.000 + 0.000 i     0.5000 + 0.8660 i    -0.5000 + 0.8660 i  -1.000 + 1.225E-16 i  -0.5000 - 0.8660 i     0.5000 - 0.8660 i       1.000 + 0.000 i     0.5000 + 0.8660 i  ...]
        [1.000 + 0.000 i     0.2588 + 0.9659 i    -0.8660 + 0.5000 i    -0.7071 - 0.7071 i     0.5000 - 0.8660 i     0.9659 + 0.2588 i   6.123E-17 + 1.000 i    -0.9659 + 0.2588 i  -0.5000 - 0.8660 i     0.7071 - 0.7071 i     0.8660 + 0.5000 i    -0.2588 + 0.9659 i  -1.000 + 1.225E-16 i    -0.2588 - 0.9659 i     0.8660 - 0.5000 i     0.7071 + 0.7071 i  -0.5000 + 0.8660 i    -0.9659 - 0.2588 i  -1.837E-16 - 1.000 i     0.9659 - 0.2588 i  ...]
        [1.000 + 0.000 i   6.123E-17 + 1.000 i  -1.000 + 1.225E-16 i  -1.837E-16 - 1.000 i       1.000 + 0.000 i   6.123E-17 + 1.000 i  -1.000 + 1.225E-16 i  -1.837E-16 - 1.000 i     1.000 + 0.000 i   6.123E-17 + 1.000 i  -1.000 + 1.225E-16 i  -1.837E-16 - 1.000 i       1.000 + 0.000 i   6.123E-17 + 1.000 i  -1.000 + 1.225E-16 i  -1.837E-16 - 1.000 i     1.000 + 0.000 i   6.123E-17 + 1.000 i  -1.000 + 1.225E-16 i  -1.837E-16 - 1.000 i  ...]
        [1.000 + 0.000 i    -0.2588 + 0.9659 i    -0.8660 - 0.5000 i     0.7071 - 0.7071 i     0.5000 + 0.8660 i    -0.9659 + 0.2588 i  -1.837E-16 - 1.000 i     0.9659 + 0.2588 i  -0.5000 + 0.8660 i    -0.7071 - 0.7071 i     0.8660 - 0.5000 i     0.2588 + 0.9659 i  -1.000 + 1.225E-16 i     0.2588 - 0.9659 i     0.8660 + 0.5000 i    -0.7071 + 0.7071 i  -0.5000 - 0.8660 i     0.9659 - 0.2588 i   6.123E-17 + 1.000 i    -0.9659 - 0.2588 i  ...]
        [1.000 + 0.000 i    -0.5000 + 0.8660 i    -0.5000 - 0.8660 i       1.000 + 0.000 i    -0.5000 + 0.8660 i    -0.5000 - 0.8660 i       1.000 + 0.000 i    -0.5000 + 0.8660 i  -0.5000 - 0.8660 i       1.000 + 0.000 i    -0.5000 + 0.8660 i    -0.5000 - 0.8660 i       1.000 + 0.000 i    -0.5000 + 0.8660 i    -0.5000 - 0.8660 i       1.000 + 0.000 i  -0.5000 + 0.8660 i    -0.5000 - 0.8660 i       1.000 + 0.000 i    -0.5000 + 0.8660 i  ...]
        [1.000 + 0.000 i    -0.7071 + 0.7071 i  -1.837E-16 - 1.000 i     0.7071 + 0.7071 i  -1.000 + 1.225E-16 i     0.7071 - 0.7071 i   6.123E-17 + 1.000 i    -0.7071 - 0.7071 i     1.000 + 0.000 i    -0.7071 + 0.7071 i  -1.837E-16 - 1.000 i     0.7071 + 0.7071 i  -1.000 + 1.225E-16 i     0.7071 - 0.7071 i   6.123E-17 + 1.000 i    -0.7071 - 0.7071 i     1.000 + 0.000 i    -0.7071 + 0.7071 i  -1.837E-16 - 1.000 i     0.7071 + 0.7071 i  ...]
        [1.000 + 0.000 i    -0.8660 + 0.5000 i     0.5000 - 0.8660 i   6.123E-17 + 1.000 i    -0.5000 - 0.8660 i     0.8660 + 0.5000 i  -1.000 + 1.225E-16 i     0.8660 - 0.5000 i  -0.5000 + 0.8660 i  -1.837E-16 - 1.000 i     0.5000 + 0.8660 i    -0.8660 - 0.5000 i       1.000 + 0.000 i    -0.8660 + 0.5000 i     0.5000 - 0.8660 i   6.123E-17 + 1.000 i  -0.5000 - 0.8660 i     0.8660 + 0.5000 i  -1.000 + 1.225E-16 i     0.8660 - 0.5000 i  ...]
        [1.000 + 0.000 i    -0.9659 + 0.2588 i     0.8660 - 0.5000 i    -0.7071 + 0.7071 i     0.5000 - 0.8660 i    -0.2588 + 0.9659 i  -1.837E-16 - 1.000 i     0.2588 + 0.9659 i  -0.5000 - 0.8660 i     0.7071 + 0.7071 i    -0.8660 - 0.5000 i     0.9659 + 0.2588 i  -1.000 + 1.225E-16 i     0.9659 - 0.2588 i    -0.8660 + 0.5000 i     0.7071 - 0.7071 i  -0.5000 + 0.8660 i     0.2588 - 0.9659 i   6.123E-17 + 1.000 i    -0.2588 - 0.9659 i  ...]
        [1.000 + 0.000 i  -1.000 + 1.225E-16 i       1.000 + 0.000 i  -1.000 + 1.225E-16 i       1.000 + 0.000 i  -1.000 + 1.225E-16 i       1.000 + 0.000 i  -1.000 + 1.225E-16 i     1.000 + 0.000 i  -1.000 + 1.225E-16 i       1.000 + 0.000 i  -1.000 + 1.225E-16 i       1.000 + 0.000 i  -1.000 + 1.225E-16 i       1.000 + 0.000 i  -1.000 + 1.225E-16 i     1.000 + 0.000 i  -1.000 + 1.225E-16 i       1.000 + 0.000 i  -1.000 + 1.225E-16 i  ...]
        [1.000 + 0.000 i    -0.9659 - 0.2588 i     0.8660 + 0.5000 i    -0.7071 - 0.7071 i     0.5000 + 0.8660 i    -0.2588 - 0.9659 i   6.123E-17 + 1.000 i     0.2588 - 0.9659 i  -0.5000 + 0.8660 i     0.7071 - 0.7071 i    -0.8660 + 0.5000 i     0.9659 - 0.2588 i  -1.000 + 1.225E-16 i     0.9659 + 0.2588 i    -0.8660 - 0.5000 i     0.7071 + 0.7071 i  -0.5000 - 0.8660 i     0.2588 + 0.9659 i  -1.837E-16 - 1.000 i    -0.2588 + 0.9659 i  ...]
        [1.000 + 0.000 i    -0.8660 - 0.5000 i     0.5000 + 0.8660 i  -1.837E-16 - 1.000 i    -0.5000 + 0.8660 i     0.8660 - 0.5000 i  -1.000 + 1.225E-16 i     0.8660 + 0.5000 i  -0.5000 - 0.8660 i   6.123E-17 + 1.000 i     0.5000 - 0.8660 i    -0.8660 + 0.5000 i       1.000 + 0.000 i    -0.8660 - 0.5000 i     0.5000 + 0.8660 i  -1.837E-16 - 1.000 i  -0.5000 + 0.8660 i     0.8660 - 0.5000 i  -1.000 + 1.225E-16 i     0.8660 + 0.5000 i  ...]
        [1.000 + 0.000 i    -0.7071 - 0.7071 i   6.123E-17 + 1.000 i     0.7071 - 0.7071 i  -1.000 + 1.225E-16 i     0.7071 + 0.7071 i  -1.837E-16 - 1.000 i    -0.7071 + 0.7071 i     1.000 + 0.000 i    -0.7071 - 0.7071 i   6.123E-17 + 1.000 i     0.7071 - 0.7071 i  -1.000 + 1.225E-16 i     0.7071 + 0.7071 i  -1.837E-16 - 1.000 i    -0.7071 + 0.7071 i     1.000 + 0.000 i    -0.7071 - 0.7071 i   6.123E-17 + 1.000 i     0.7071 - 0.7071 i  ...]
        [1.000 + 0.000 i    -0.5000 - 0.8660 i    -0.5000 + 0.8660 i       1.000 + 0.000 i    -0.5000 - 0.8660 i    -0.5000 + 0.8660 i       1.000 + 0.000 i    -0.5000 - 0.8660 i  -0.5000 + 0.8660 i       1.000 + 0.000 i    -0.5000 - 0.8660 i    -0.5000 + 0.8660 i       1.000 + 0.000 i    -0.5000 - 0.8660 i    -0.5000 + 0.8660 i       1.000 + 0.000 i  -0.5000 - 0.8660 i    -0.5000 + 0.8660 i       1.000 + 0.000 i    -0.5000 - 0.8660 i  ...]
        [1.000 + 0.000 i    -0.2588 - 0.9659 i    -0.8660 + 0.5000 i     0.7071 + 0.7071 i     0.5000 - 0.8660 i    -0.9659 - 0.2588 i   6.123E-17 + 1.000 i     0.9659 - 0.2588 i  -0.5000 - 0.8660 i    -0.7071 + 0.7071 i     0.8660 + 0.5000 i     0.2588 - 0.9659 i  -1.000 + 1.225E-16 i     0.2588 + 0.9659 i     0.8660 - 0.5000 i    -0.7071 - 0.7071 i  -0.5000 + 0.8660 i     0.9659 + 0.2588 i  -1.837E-16 - 1.000 i    -0.9659 + 0.2588 i  ...]
        [1.000 + 0.000 i  -1.837E-16 - 1.000 i  -1.000 + 1.225E-16 i   6.123E-17 + 1.000 i       1.000 + 0.000 i  -1.837E-16 - 1.000 i  -1.000 + 1.225E-16 i   6.123E-17 + 1.000 i     1.000 + 0.000 i  -1.837E-16 - 1.000 i  -1.000 + 1.225E-16 i   6.123E-17 + 1.000 i       1.000 + 0.000 i  -1.837E-16 - 1.000 i  -1.000 + 1.225E-16 i   6.123E-17 + 1.000 i     1.000 + 0.000 i  -1.837E-16 - 1.000 i  -1.000 + 1.225E-16 i   6.123E-17 + 1.000 i  ...]
        [1.000 + 0.000 i     0.2588 - 0.9659 i    -0.8660 - 0.5000 i    -0.7071 + 0.7071 i     0.5000 + 0.8660 i     0.9659 - 0.2588 i  -1.837E-16 - 1.000 i    -0.9659 - 0.2588 i  -0.5000 + 0.8660 i     0.7071 + 0.7071 i     0.8660 - 0.5000 i    -0.2588 - 0.9659 i  -1.000 + 1.225E-16 i    -0.2588 + 0.9659 i     0.8660 + 0.5000 i     0.7071 - 0.7071 i  -0.5000 - 0.8660 i    -0.9659 + 0.2588 i   6.123E-17 + 1.000 i     0.9659 + 0.2588 i  ...]
        ...]]
}

All entries have magnitude 1 (they lie on the unit circle).

(allclose? (el/abs (:table ct)) 1.0)
true

The first row (\(k = 0\)) is the trivial character — all ones.

(allclose? (el/re ((:table ct) 0)) 1.0)
true

Let’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 (el/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 (t/complex-tensor-real temperatures))
signal
#la/C [:float64 [24] [2.000 + 0.000 i  3.000 + 0.000 i  7.000 + 0.000 i  12.00 + 0.000 i  17.00 + 0.000 i  22.00 + 0.000 i  25.00 + 0.000 i  24.00 + 0.000 i  19.00 + 0.000 i  13.00 + 0.000 i  7.000 + 0.000 i  3.000 + 0.000 i  3.000 + 0.000 i  4.000 + 0.000 i  8.000 + 0.000 i  13.00 + 0.000 i  18.00 + 0.000 i  23.00 + 0.000 i  26.00 + 0.000 i  25.00 + 0.000 i  ...]]
(def f-hat (hm/fourier-transform ct signal))
f-hat
#la/C [:float64 [24] [320.0 + 0.000 i  -1.000 + 7.596 i  -137.3 + 7.464 i  -1.000 + 2.414 i  6.000 - 6.928 i  -1.000 + 1.303 i  -2.000 + 2.000 i  -1.000 + 0.7673 i  2.000 - 3.109E-14 i  -1.000 + 0.4142 i  1.282 + 0.5359 i  -1.000 + 0.1317 i  0.000 - 1.959E-14 i  -1.000 - 0.1317 i  1.282 - 0.5359 i  -1.000 - 0.4142 i  2.000 - 4.219E-14 i  -1.000 - 0.7673 i  -2.000 - 2.000 i  -1.000 - 1.303 i  ...]]

The \(k = 0\) coefficient is the sum of all values (the DC component).

(el/re (f-hat 0))
320.0

Let’s see the magnitude spectrum — how strong each “frequency” is.

(-> (tc/dataset
     {:frequency (range 24)
      :magnitude (vec (el/abs 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 (ft/forward-1d (ft/transformer :real :fft) temperatures)
      fft-coefficients (let [data (vec fft-result)
                             n (/ (count data) 2)]
                         (t/complex-tensor
                          (mapv (fn [k] (data (* 2 k))) (range n))
                          (mapv (fn [k] (data (inc (* 2 k)))) (range n))))]
  (allclose? (t/select (el/abs f-hat) (range 12))
             (el/abs fft-coefficients)
             1e-8))
true

The 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]
    (t/compute-tensor
     [n n]
     (fn [j k]
       (el/abs (hm/character-inner-product (table j) (table k) sizes n)))
     :float64)))
orthogonality-matrix
#la/R [: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.070E-16     1.000 1.220E-16 2.780E-17 3.717E-17 9.483E-17 1.328E-17 3.243E-17 5.989E-17 7.562E-17 4.285E-17 6.596E-17 2.325E-17 6.228E-18 1.865E-17 3.959E-17 3.291E-17 6.534E-17 4.858E-17 5.345E-17 ...]
        [9.435E-17 1.220E-16     1.000 1.388E-17 1.043E-16 3.240E-17 5.875E-17 1.156E-17 2.785E-17 2.094E-17 6.939E-18 3.587E-17 4.138E-17 1.247E-16 2.544E-17 1.636E-17 5.556E-17 3.016E-17 1.007E-16 1.573E-17 ...]
        [8.605E-17 2.780E-17 1.388E-17     1.000 1.552E-17 3.988E-17 9.837E-17 4.171E-17 2.313E-18 8.109E-17 4.626E-18 7.976E-17 5.274E-17 3.631E-17 1.034E-17 2.313E-18 5.172E-18 3.362E-17 3.509E-17 7.875E-17 ...]
        [1.249E-16 3.717E-17 1.043E-16 1.552E-17     1.000 1.668E-17 8.459E-18 4.189E-17 1.668E-16 3.271E-18 4.908E-17 5.897E-18 1.309E-16 3.631E-17 1.042E-16 6.939E-18 4.626E-17 9.252E-18 9.273E-18 3.114E-17 ...]
        [1.114E-16 9.483E-17 3.240E-17 3.988E-17 1.668E-17     1.000 1.221E-17 7.174E-17 3.438E-17 4.920E-17 1.166E-16 2.316E-17 1.668E-17 6.412E-17 3.356E-17 2.845E-17 6.272E-17 6.465E-18 4.560E-17 1.156E-18 ...]
        [6.137E-17 1.328E-17 5.875E-17 9.837E-17 8.459E-18 1.221E-17     1.000 4.933E-17 6.799E-18 3.257E-17 6.042E-17 4.377E-17 5.258E-17 1.218E-17 1.026E-16 9.170E-17 9.789E-18 1.157E-17     0.000 5.294E-17 ...]
        [1.114E-16 3.243E-17 1.156E-17 4.171E-17 4.189E-17 7.174E-17 4.933E-17     1.000 7.174E-17 3.146E-17 4.128E-17 1.064E-16 1.388E-17 6.076E-17 1.193E-16 7.676E-17 3.844E-17 2.313E-18 1.345E-17 4.626E-18 ...]
        [1.334E-16 5.989E-17 2.785E-17 2.313E-18 1.668E-16 3.438E-17 6.799E-18 7.174E-17     1.000 3.271E-18 5.110E-17 3.265E-17 7.407E-33 6.024E-17 2.313E-17 8.340E-18 2.220E-16 3.500E-17 2.732E-18 5.556E-17 ...]
        [6.939E-17 7.562E-17 2.094E-17 8.109E-17 3.271E-18 4.920E-17 3.257E-17 3.146E-17 3.271E-18     1.000 3.271E-18 2.722E-17 5.415E-17 4.917E-17 3.271E-18 4.626E-18 9.252E-18 6.620E-17 9.621E-17 2.586E-17 ...]
        [8.937E-17 4.285E-17 6.939E-18 4.626E-18 4.908E-17 1.166E-16 6.042E-17 4.128E-17 5.110E-17 3.271E-18     1.000 1.573E-17 3.708E-17 4.189E-17 1.480E-16 1.179E-17 2.919E-17 1.196E-16 1.005E-16 3.125E-17 ...]
        [1.114E-16 6.596E-17 3.587E-17 7.976E-17 5.897E-18 2.316E-17 4.377E-17 1.064E-16 3.265E-17 2.722E-17 1.573E-17     1.000 2.359E-17 1.156E-18 3.823E-17 4.909E-17 6.272E-17 6.147E-17 1.605E-17 6.601E-17 ...]
        [6.123E-17 2.325E-17 4.138E-17 5.274E-17 1.309E-16 1.668E-17 5.258E-17 1.388E-17 7.407E-33 5.415E-17 3.708E-17 2.359E-17     1.000 1.976E-17 3.730E-17 5.110E-17 7.407E-33 1.850E-17 7.672E-17 2.069E-17 ...]
        [1.112E-16 6.228E-18 1.247E-16 3.631E-17 3.631E-17 6.412E-17 1.218E-17 6.076E-17 6.024E-17 4.917E-17 4.189E-17 1.156E-18 1.976E-17     1.000 1.207E-17 2.359E-17 3.372E-17 9.602E-17 5.496E-17 2.791E-17 ...]
        [9.355E-17 1.865E-17 2.544E-17 1.034E-17 1.042E-16 3.356E-17 1.026E-16 1.193E-16 2.313E-17 3.271E-18 1.480E-16 3.823E-17 3.730E-17 1.207E-17     1.000 7.314E-18 6.313E-17 3.631E-17 6.343E-17 1.311E-16 ...]
        [8.092E-17 3.959E-17 1.636E-17 2.313E-18 6.939E-18 2.845E-17 9.170E-17 7.676E-17 8.340E-18 4.626E-18 1.179E-17 4.909E-17 5.110E-17 2.359E-17 7.314E-18     1.000 8.340E-18 3.330E-17 2.746E-17 5.178E-17 ...]
        [1.334E-16 3.291E-17 5.556E-17 5.172E-18 4.626E-17 6.272E-17 9.789E-18 3.844E-17 2.220E-16 9.252E-18 2.919E-17 6.272E-17 7.407E-33 3.372E-17 6.313E-17 8.340E-18     1.000 6.255E-17 1.229E-17 4.279E-17 ...]
        [1.114E-16 6.534E-17 3.016E-17 3.362E-17 9.252E-18 6.465E-18 1.157E-17 2.313E-18 3.500E-17 6.620E-17 1.196E-16 6.147E-17 1.850E-17 9.602E-17 3.631E-17 3.330E-17 6.255E-17     1.000 4.692E-17 7.345E-17 ...]
        [4.075E-17 4.858E-17 1.007E-16 3.509E-17 9.273E-18 4.560E-17     0.000 1.345E-17 2.732E-18 9.621E-17 1.005E-16 1.605E-17 7.672E-17 5.496E-17 6.343E-17 2.746E-17 1.229E-17 4.692E-17     1.000 1.604E-17 ...]
        [1.110E-16 5.345E-17 1.573E-17 7.875E-17 3.114E-17 1.156E-18 5.294E-17 4.626E-18 5.556E-17 2.586E-17 3.125E-17 6.601E-17 2.069E-17 2.791E-17 1.311E-16 5.178E-17 4.279E-17 7.345E-17 1.604E-17     1.000 ...]
        ...]]

The matrix is the 24x24 identity (to numerical precision) — 1 on the diagonal, effectively 0 everywhere else.

(allclose? orthogonality-matrix
           (t/compute-tensor [24 24] (fn [j k] (if (= j k) 1.0 0.0)) :float64))
true

Perfect 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)]
  (el/reduce-max (el/abs (el/- reconstructed signal))))
2.904348053629478E-14

The 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 (t/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 (t/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 (el/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 (el/* f-fn-hat h-fn-hat)]
  (< (el/reduce-max (el/abs (el/- convolved-hat pointwise-product))) 1e-8))
true

Parseval’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 (el/abs signal)
      mag-f (el/abs f-hat)
      energy-time (el/sum (el/* mag-s mag-s))
      energy-freq (/ (el/sum (el/* mag-f mag-f))
                     (double (hm/order G)))]
  (< (Math/abs (- energy-time energy-freq)) 1e-8))
true

Connection 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)
47

To 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 (el/re (hm/convolve ct
                                     (t/complex-tensor-real f-real)
                                     (t/complex-tensor-real h-real)))]
  (allclose? cyclic-from-linear group-conv))
true

The 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:

The harmonica library builds all of these on the same protocol foundation demonstrated here.

source: notebooks/harmonica_book/dft_as_group_fourier.clj