Harmonic Analysis is Langlands — The Fast Fourier Transform as the Computational Langlands Correspondence for GL(1)

In the paper's words

We identify the Fast Fourier Transform (FFT) as the computational Langlands correspondence for the general linear group GL(1). Harmonic analysis on the finite cyclic group Z/nZ decomposes functions into irreducible characters -- the FFT -- and this structure generalises directly to harmonic analysis on G(Q)\G(A) for a reductive group G -- the Langlands program. The operation is the same: decompose a function on a group into spectral components indexed by irreducible representations.

The abstract, verbatim, and its opening sentence is the claim. Every line below is quoted from the text.

Numbers it reports

1. Gauss was performing harmonic analysis on a cyclic group, decomposing a discrete signal into its frequency components, predating Cooley--Tukey by 160 years.

   from 2.2 Gauss's 1805 Asteroid Interpolation

2. It took 160 years for Cooley and Tukey to rediscover the algorithm, and another 60 years for the Langlands program to reveal what that algorithm was really computing: the spectral decomposition of the automorphic spectrum of $\mathrm{GL}(1)$.

   from 7.3 Gauss's Adelic Instinct

How it is done

1. The Fast Fourier Transform -- published by Cooley and Tukey in 1965, traced by them to unpublished work of Gauss in 1805 -- is widely regarded as the most important numerical algorithm of the twentieth century (1).

   from 1. Introduction

2. Gauss's method was adelicity avant la lettre : discrete samples at finitely many observation times ($p$-adic-like finite completions) reconstructing a continuous orbital trajectory (Archimedean place).

   from 2.2 Gauss's 1805 Asteroid Interpolation

3. For $\mathrm{GL}(1)$, automorphic representations are one-dimensional and the multiplicity-one theorem holds trivially.

   from 4.2 Why This is Hard

4. The adelic FFT algorithm (detailed in the companion specification [ALP §5.2]) is: Local FFT at each finite place $p$: Compute $\hat{f}_p$ on $\mathbb{Z}/p^{k_p}\mathbb{Z}$ in $O(p^{k_p} \log p^{k_p})$ operations.

   from 4.3 The Adelic FFT for $\mathrm{GL}(1)$

What would falsify it

1. Archimedean readout: The physical measurement occurs at the Archimedean place, producing $\hat{f}_\infty$ as the observable output.

   from 6.2 The Adelic FFT Processor

Where the claim stops

1. For $\mathrm{GL}(n)$ with $n \geq 2$, it is an open problem: the Computational Langlands Problem .

   from 1. Introduction

2. Computing the spectral decomposition requires solving this global constraint -- a problem whose complexity for non-abelian $G$ is not known to be in P.

   from 4.2 Why This is Hard

3. The passive geometric error correction provided by the ultrametric ($p$-adic) distance -- under which small errors cannot accumulate (the non-Archimedean property $\|x + y\|_p \leq \max(\|x\|_p, \|y\|_p)$) -- protects quantum information during computation.

   from 6.1 Bruhat--Tits Qudits

Where to read

1. 1. Introduction329 words · 1 min
2. 2. Harmonic Analysis on Abelian Groups: The FFT273 words · 1 min
3. 3. Harmonic Analysis on Non-Abelian Groups: The Langlands Program416 words · 2 min
4. 4. The Computational Langlands Problem458 words · 2 min
5. 5. The Bruhat--Tits Tree as the Natural Dyadic Decomposition494 words · 2 min
6. 6. Ultrametric Quantum Computation as the Computational Substrate473 words · 2 min
7. 7. Discussion391 words · 2 min
8. Declarations147 words · 1 min