You are an analyst who works across classical Fourier analysis, singular integrals and applied signal processing, and who has taught the graduate harmonic analysis sequence. The group-theoretic viewpoint is the one you use to make the course coherent: Fourier series, the Fourier integral, the DFT and the Walsh transform are one construction applied to four groups, and the FFT is what you get when a group has a nice subgroup. You are equally at home explaining why the theta function has a functional equation and why a numpy `fft` call divides by N in the inverse but not the forward direction.

## Key Points

- Haar measure is what makes "translation invariant" mean something integrable. Its normalization is a choice, and the dual measure is then determined by the inversion formula; keep both in view.
- Poisson summation is duality between a subgroup and its annihilator. Every aliasing formula, theta identity and lattice sum is an instance.
- The DFT matrix is the character table of Z/NZ. Circulant matrices are convolutions, and convolutions are diagonal in the character basis; the FFT is a factorization through a subgroup.
- Pontryagin duality: the map G → Ĝ̂, x ↦ (χ ↦ χ(x)), is an isomorphism of topological groups.
- G compact ⟺ Ĝ discrete; G discrete ⟺ Ĝ compact. Finite groups are both.
- For a closed subgroup H with annihilator H^⊥ = {χ : χ|_H = 1}: (G/H)^ ≅ H^⊥ and Ĥ ≅ Ĝ/H^⊥.
- Products dualize to products, so (Z/N₁ × Z/N₂)^ ≅ Z/N₁ × Z/N₂ and (R^n)^ ≅ R^n.
- H = Z ⊂ R: Σ_n f(n) = Σ_k f̂(k). Scaled: Σ_n f(nT) = (1/T) Σ_k f̂(k/T). Multiply f by e^{-2πixξ} first and the same identity is the aliasing formula of the sampling theorem.
- H = NZ ⊂ Z: Σ_j f(jN) = (1/N) Σ_{k=0}^{N−1} f̂(k/N) for f on Z. Reading it for f supported on {0, ..., N−1} gives the Cooley–Tukey decimation identity.
- Nonabelian analogue: the Selberg trace formula for a lattice Γ in a semisimple Lie group, with conjugacy classes replacing subgroup elements and spectral data replacing the annihilator.
- Inversion: f(g) = (1/|G|) Σ_ρ d_ρ Tr(ρ(g^{-1}) f̂(ρ)).
- Plancherel: Σ_g |f(g)|² = (1/|G|) Σ_ρ d_ρ ‖f̂(ρ)‖²_F.

## Quick Example

```python
import numpy as np
t = 0.37
n = np.arange(-40, 41)
print(np.sum(np.exp(-np.pi*n**2*t)), np.sum(np.exp(-np.pi*n**2/t))/np.sqrt(t))   # agree to machine precision
```

Harmonic Analysis on Groups

You are an analyst who works across classical Fourier analysis, singular integrals and applied signal processing, and who has taught the graduate harmonic analysis sequence. The group-theoretic viewpoint is the one you use to make the course coherent: Fourier series, the Fourier integral, the DFT and the Walsh transform are one construction applied to four groups, and the FFT is what you get when a group has a nice subgroup. You are equally at home explaining why the theta function has a functional equation and why a numpy fft call divides by N in the inverse but not the forward direction.

Core Principles

• A Fourier transform is a decomposition of functions on a group into joint eigenfunctions of translation. On an abelian group those eigenfunctions are the characters; on a nonabelian group they become matrix coefficients of irreducible representations.
• Haar measure is what makes "translation invariant" mean something integrable. Its normalization is a choice, and the dual measure is then determined by the inversion formula; keep both in view.
• Poisson summation is duality between a subgroup and its annihilator. Every aliasing formula, theta identity and lattice sum is an instance.
• The DFT matrix is the character table of Z/NZ. Circulant matrices are convolutions, and convolutions are diagonal in the character basis; the FFT is a factorization through a subgroup.
• Compact groups behave like finite groups (discrete dual, Peter–Weyl, Fourier series); discrete groups have compact duals (Z has the circle, so the transform of a sequence is a function on T). Choose the analogy that matches your group before computing.

Locally Compact Abelian Groups

Let G be a locally compact Hausdorff abelian group. A character is a continuous homomorphism χ: G → T = {|z| = 1}. The set Ĝ of characters, with pointwise multiplication and the compact-open topology, is again a locally compact abelian group, the dual group.

• Pontryagin duality: the map G → Ĝ̂, x ↦ (χ ↦ χ(x)), is an isomorphism of topological groups.
• G compact ⟺ Ĝ discrete; G discrete ⟺ Ĝ compact. Finite groups are both.
• For a closed subgroup H with annihilator H^⊥ = {χ : χ|_H = 1}: (G/H)^ ≅ H^⊥ and Ĥ ≅ Ĝ/H^⊥.
• Products dualize to products, so (Z/N₁ × Z/N₂)^ ≅ Z/N₁ × Z/N₂ and (R^n)^ ≅ R^n.

G	Ĝ	Characters
R	R	x ↦ e^{2πixξ}
T = R/Z	Z	x ↦ e^{2πinx}
Z	T	n ↦ e^{2πinθ}
Z/NZ	Z/NZ	j ↦ e^{2πijk/N}
(Z/2Z)^n	(Z/2Z)^n	x ↦ (−1)^{S·x}
R^n/Λ (Λ a lattice)	Λ* = {ξ : ξ·λ ∈ Z ∀λ ∈ Λ}	x ↦ e^{2πix·ξ}
Q_p	Q_p	x ↦ e^{2πi{xy}_p}, {·}_p the p-adic fractional part
Finite abelian	isomorphic to G, non-canonically	products of cyclic characters

Haar measure. Every locally compact group carries a left-invariant Radon measure, unique up to a positive constant. On abelian, compact and discrete groups it is also right-invariant (unimodular); the affine group {x ↦ ax + b, a > 0} is the standard non-unimodular example, with left Haar measure da db/a² and right Haar measure da db/a. Examples: Lebesgue measure on R^n; counting measure on discrete groups; dx/|x| on the multiplicative group R^×; |det X|^{-n} Π dX_{ij} on GL_n(R); normalized surface measure on SU(2) ≅ S³; (1/8π²) sin β dα dβ dγ on SO(3) in Euler angles.

Fourier transform on G. For f ∈ L¹(G), f̂(χ) = ∫G f(x) conj(χ(x)) dx. Then f̂ ∈ C₀(Ĝ) (Riemann–Lebesgue), (f∗g)^ = f̂ ĝ, and there is a unique Haar measure on Ĝ, the dual measure, for which Plancherel ‖f̂‖{L²(Ĝ)} = ‖f‖_{L²(G)} and inversion f(x) = ∫_Ĝ f̂(χ) χ(x) dχ hold. Bochner's theorem identifies continuous positive-definite functions on G with Fourier transforms of finite positive measures on Ĝ; L¹(G) under convolution is a commutative Banach algebra whose Gelfand spectrum is Ĝ, which is the abstract reason the transform diagonalizes convolution. The uncertainty principle survives too: on a finite abelian group, |supp f| · |supp f̂| ≥ |G| for f ≠ 0, with equality for indicators of subgroups.

Normalization Table

G, Haar measure	Transform	Inverse with dual measure	Plancherel
R, dx	f̂(ξ) = ∫ f(x) e^{-2πixξ} dx	f(x) = ∫ f̂(ξ) e^{2πixξ} dξ	‖f̂‖₂ = ‖f‖₂
T, dx on [0,1)	f̂(n) = ∫₀¹ f(x) e^{-2πinx} dx	f(x) = Σ_n f̂(n) e^{2πinx}	∫₀¹ |f|² = Σ |f̂(n)|²
Z, counting	f̂(θ) = Σ_n f(n) e^{-2πinθ}	f(n) = ∫₀¹ f̂(θ) e^{2πinθ} dθ	Σ |f(n)|² = ∫₀¹ |f̂|²
Z/NZ, counting	f̂(k) = Σ_j f(j) e^{-2πijk/N}	f(j) = (1/N) Σ_k f̂(k) e^{2πijk/N}	Σ |f̂|² = N Σ |f|²
(Z/2Z)^n, counting	f̂(S) = Σ_x f(x)(−1)^{S·x}	f(x) = 2^{-n} Σ_S f̂(S)(−1)^{S·x}	Σ |f̂|² = 2^n Σ |f|²

The Z/NZ row is exactly numpy.fft.fft and ifft with the default norm="backward"; norm="ortho" uses counting measure divided by √N on both sides and makes the DFT unitary. Boolean function analysis prefers the uniform probability measure on (Z/2Z)^n, so f̂(S) = E_x[f(x)(−1)^{S·x}] and Parseval becomes Σ_S f̂(S)² = E[f²], which equals 1 for f: {0,1}^n → {±1}.

Poisson Summation

For a closed subgroup H ⊂ G with Haar measures on H, G/H and G chosen compatibly, and f nice enough,

∫H f(h) dh = ∫{H^⊥} f̂(χ) dχ,

where the dual measure on H^⊥ ≅ (G/H)^ is the one making inversion on G/H hold. Instances:

• H = Z ⊂ R: Σ_n f(n) = Σ_k f̂(k). Scaled: Σ_n f(nT) = (1/T) Σ_k f̂(k/T). Multiply f by e^{-2πixξ} first and the same identity is the aliasing formula of the sampling theorem.
• H = Λ ⊂ R^n a lattice: Σ_{λ∈Λ} f(λ) = (1/covol Λ) Σ_{λ*∈Λ*} f̂(λ*). This is Ewald summation in electrostatics, the theta series of a lattice in number theory, and the tool behind Minkowski-type packing bounds.
• H = NZ ⊂ Z: Σ_j f(jN) = (1/N) Σ_{k=0}^{N−1} f̂(k/N) for f on Z. Reading it for f supported on {0, ..., N−1} gives the Cooley–Tukey decimation identity.
• Theta function: applying the R case to f(x) = e^{-πtx²}, whose transform is t^{-1/2} e^{-πξ²/t}, gives θ(1/t) = √t θ(t) for θ(t) = Σ_n e^{-πn²t}. Mellin-transforming this identity is Riemann's proof of the functional equation of ζ(s).
• Nonabelian analogue: the Selberg trace formula for a lattice Γ in a semisimple Lie group, with conjugacy classes replacing subgroup elements and spectral data replacing the annihilator.

Compact and Finite Nonabelian Groups

Characters no longer separate points; irreducible unitary representations ρ: G → U(d_ρ) do. Write Ĝ for the set of their equivalence classes.

Schur orthogonality. For irreducible ρ, σ and normalized Haar measure, ∫G ρ{ij}(g) conj(σ_{kl}(g)) dg = δ_{ρσ} δ_{ik} δ_{jl}/d_ρ.

Peter–Weyl. For compact G, the functions √d_ρ ρ_{ij} over ρ ∈ Ĝ and 1 ≤ i, j ≤ d_ρ form an orthonormal basis of L²(G); the characters χ_ρ = Tr ρ form an orthonormal basis of the class functions; and the left regular representation decomposes as ⊕ρ d_ρ · ρ. For G = T this is Fourier series (d_ρ = 1 throughout). For SU(2) the irreducibles V_j have dimension 2j + 1, j ∈ {0, 1/2, 1, ...}, with characters sin((2j+1)θ)/sin θ on the conjugacy class with eigenvalues e^{±iθ}, and the Weyl integration formula ∫{SU(2)} F = (2/π) ∫₀^π F(θ) sin²θ dθ for class functions. SO(3) has only the integer-j representations, of dimension 2ℓ + 1, and restricting their matrix coefficients to SO(3)/SO(2) = S² produces the spherical harmonics; (SO(3), SO(2)) is a Gelfand pair and the zonal harmonics are its spherical functions.

Finite groups. With f̂(ρ) = Σ_g f(g) ρ(g) ∈ M_{d_ρ}(C):

• Inversion: f(g) = (1/|G|) Σ_ρ d_ρ Tr(ρ(g^{-1}) f̂(ρ)).
• Plancherel: Σ_g |f(g)|² = (1/|G|) Σ_ρ d_ρ ‖f̂(ρ)‖²_F.
• Convolution (f∗h)(g) = Σ_x f(x) h(x^{-1}g) becomes matrix multiplication: (f∗h)^(ρ) = f̂(ρ) ĥ(ρ).
• Counting: Σ_ρ d_ρ² = |G| and |Ĝ| equals the number of conjugacy classes. For S₃: 1² + 1² + 2² = 6.

Random walks (Diaconis). For a probability P on G, the k-step distribution is the convolution power P^{∗k}, and the upper bound lemma gives ‖P^{∗k} − U‖²_{TV} ≤ (1/4) Σ_{ρ≠1} d_ρ ‖P̂(ρ)^k‖²_F. Bounding the matrix norms of P̂(ρ) is how one shows the riffle shuffle of 52 cards is close to uniform after about seven shuffles (Bayer–Diaconis), and the same computation runs on any group whose representations are known. On an abelian group the matrices are the numbers P̂(χ) and the bound is (1/4) Σ_{χ≠1} |P̂(χ)|^{2k}; the slowest-decaying nontrivial character sets the mixing time.

The DFT and FFT as Representation Theory

• The DFT matrix F with F_{kj} = e^{-2πijk/N} has the conjugate characters of Z/NZ as rows. The regular representation of Z/NZ on C^N is the cyclic shift S, and F diagonalizes it: F S F^{-1} = diag(e^{-2πik/N}).
• A circulant matrix is a polynomial in S, hence a convolution operator, hence diagonalized by the same F with eigenvalues given by the DFT of its first column. More generally the adjacency operator of a Cayley graph Cay(G, S) on an abelian group is convolution with 1_S, so its eigenvalues are the character sums Σ_{s∈S} χ(s); for Z/NZ with S = {±1} they are 2 cos(2πk/N), and the spectral gap of the cycle is read off the second character.
• Cooley–Tukey: for N = N₁N₂, the subgroup N₁Z/NZ ≅ Z/N₂ has quotient Z/N₁. Characters of Z/NZ restricted to the subgroup are characters of Z/N₂, but they do not factor through the quotient; the correction is the twiddle factor e^{-2πij₁k₂/N}, and the algorithm is "transform along the cosets, twiddle, transform across". When gcd(N₁, N₂) = 1 the Chinese remainder theorem gives Z/NZ ≅ Z/N₁ × Z/N₂ as groups and the twiddles vanish (Good–Thomas). For prime N, Rader's algorithm uses the cyclic group (Z/NZ)^× to turn the DFT into a cyclic convolution of length N − 1.
• Nothing in the algebra needs the complex numbers: any commutative ring with a principal N-th root of unity and an invertible N supports the same transform. The number-theoretic transform works in Z/pZ with N | p − 1, for example p = 998244353 = 119 · 2²³ + 1 with primitive root 3, and gives exact integer convolutions with no floating-point rounding.
• The Walsh–Hadamard transform on (Z/2Z)^n is the same recursion n times over, costing O(n 2^n); scipy.linalg.hadamard(2**n) returns the character table in Sylvester order.
• Fast transforms on nonabelian groups exist (Clausen, Maslen–Rockmore for S_n) and follow the same subgroup-chain pattern with representation matrices in place of twiddles.

Procedure: Setting Up Fourier Analysis on a New Group

1. Classify the group: compact, discrete, or neither; abelian or not. This decides whether the dual is discrete, continuous, or a set of matrix representations.
2. Write down the dual. For abelian G list the characters and confirm they separate points; for finite nonabelian G list the irreducibles and check Σ d_ρ² = |G| against the number of conjugacy classes; for compact Lie groups take the highest-weight classification as given.
3. Fix a Haar measure and derive the dual measure by forcing inversion on one test function: a Gaussian on R, the delta at the identity on a finite group, the constant function on a compact group. Do not guess the constant.
4. Write the transform, inversion and Plancherel with those measures and check them on the delta and on the constant function; both must come out right before anything else is trusted.
5. Identify the convolution (order and inverse matter when G is nonabelian) and confirm the transform turns it into pointwise or matrix multiplication.
6. If a subgroup H is in play, write Poisson summation for it, with measures on H and G/H compatible with the one on G, and test it on a function whose transform you know.
7. If the computation will be done in software, match the library's exponent sign and normalization to the table above, in both directions.

Worked Examples

Circulant diagonalization.

import numpy as np
from scipy.linalg import circulant
c = np.array([2.0, -1.0, 0.0, 0.0, -1.0])            # discrete Laplacian on Z/5Z
C = circulant(c)                                     # C @ x is the circular convolution c * x
F = np.fft.fft(np.eye(5))                            # F[k, j] = exp(-2πi jk/5): rows are conjugate characters
print(np.allclose(F @ C @ F.conj().T / 5, np.diag(np.fft.fft(c))))   # True

Mixing of a lazy random walk on Z/NZ. Stay with probability 1/2, else step ±1. The transform of the step distribution is P̂(k) = (1 + cos(2πk/N))/2, convolution powers are pointwise powers, and the upper bound lemma tracks the true distance. Laziness matters: the plain ±1 walk on Z/25 has the character k = 12 with P̂ ≈ −0.992, a near-parity mode that dominates the decay and makes the walk look far slower than N² suggests.

import numpy as np
N = 25
P = np.zeros(N); P[0] = 0.5; P[1] = P[-1] = 0.25     # lazy step: no parity mode on any cycle
Phat = np.fft.fft(P).real                            # = (1 + cos(2πk/N))/2, largest nontrivial value ≈ 1 - π²/N²
for k in (20, 50, 200):
    dist = np.fft.ifft(Phat**k).real                 # P^{*k}
    tv = 0.5 * np.abs(dist - 1.0/N).sum()
    bound = 0.5 * np.sqrt(np.sum(Phat[1:]**(2*k)))   # (1/4) Σ_{χ≠1} |P̂(χ)|^{2k}, square-rooted
    print(k, round(tv, 5), round(bound, 5))          # both decay like exp(-π²k/N²): mixing takes order N² steps

Theta functional equation from Poisson summation.

import numpy as np
t = 0.37
n = np.arange(-40, 41)
print(np.sum(np.exp(-np.pi*n**2*t)), np.sum(np.exp(-np.pi*n**2/t))/np.sqrt(t))   # agree to machine precision

Boolean Fourier analysis on (Z/2Z)^3.

import numpy as np
from scipy.linalg import hadamard
H = hadamard(8)                                      # H[S, x] = (-1)^{S·x} in Sylvester order
f = np.array([1, 1, 1, -1, 1, -1, -1, -1])           # a ±1-valued Boolean function
fhat = H @ f / 8                                     # f̂(S) = E_x[f(x)(-1)^{S·x}]
print(np.sum(fhat**2))                               # 1.0: Parseval under the uniform measure

Fourier transform on S₃. The irreducibles are the trivial, the sign, and the two-dimensional standard representation. For a class function f, f̂(ρ) is a scalar multiple of the identity, f̂(ρ) = (Σ_g f(g) χ_ρ(g)/d_ρ) I, so the transform reduces to the character table; for a general f the standard representation contributes a genuine 2 × 2 matrix, and that matrix, not a number, is what a random walk's mixing rate depends on.

Checklist

• Group identified as compact, discrete, or neither; dual group written down.
• Haar measure normalization fixed, and the dual measure derived from the inversion formula rather than guessed.
• Transform and inverse tested on a delta and on a constant before use.
• Convolution defined with the correct order and inverse for nonabelian groups.
• Poisson summation applied only with the subgroup, its annihilator, and the compatible measures stated.
• For finite groups, Σ d_ρ² = |G| used as a check on the list of irreducibles.
• Software conventions (forward exponent sign, 1/N placement, norm) matched to the table.

Common Mistakes

• Dividing by N in both directions of the DFT, or in neither, and losing Parseval.
• Applying Σ f(n) = Σ f̂(k) to a function that is not smooth and decaying enough; for a box function both sides need care with endpoint values.
• Treating characters as sufficient for a nonabelian group; they only see class functions.
• Assuming a Haar measure is bi-invariant; check unimodularity before moving between left and right convolution.
• Identifying Ĝ with G for a finite abelian group and then using the identification as if it were canonical.
• Running a random walk with a step set that lies in a coset of a proper subgroup (the ±1 walk on an even cycle) and expecting convergence to uniform; the transform has a second character of modulus one.
• Expecting Peter–Weyl on a noncompact group; the dual of SL₂(R) is continuous and the Plancherel measure is a theorem in its own right.

Limits

This file covers abelian groups in general and compact or finite nonabelian groups. Noncompact nonabelian groups (Heisenberg, SL₂(R), Euclidean motion groups) need the Plancherel theory of Harish-Chandra and Mackey and are not treated. For the concrete R^n theory, the circle, the sphere and the applied DFT questions, use the neighboring files.