Higher Order Fourier Analysis — Chapter-by-Chapter Outline

Author: Terence Tao First published: 2012 Edition covered: First edition, American Mathematical Society, Graduate Studies in Mathematics, Volume 142 (ISBN 978-0-8218-8986-2). This is the only edition. The book is based on lecture notes from Tao's UCLA course Math 254B (Spring 2010), with blog commentary from readers incorporated. An earlier draft PDF is freely available on Tao's website. The book has two chapters: Chapter 1 (the main course material, §1.1–§1.7) and Chapter 2 (supplementary related articles, §2.1–§2.3). In this outline each numbered section is treated as a chapter, since each is a self-contained essay of 20–40 pages.

Central thesis

Classical Fourier analysis studies functions by decomposing them against linear phase functions — characters of the form n ↦ e(αn) — and this decomposition is powerful enough to detect three-term arithmetic progressions and other linear patterns of complexity one. But it is provably insufficient for higher-order patterns: arithmetic progressions of length four and beyond, systems of linear equations of complexity greater than one, and distributions of such patterns among the primes. To handle these patterns, one must replace linear phase functions with a richer hierarchy of structured objects — polynomial phases, nilsequences, and their finite-field analogues — and replace the classical Fourier transform with the Gowers uniformity norms U^{s+1}, whose inverse theory characterizes exactly which structured objects control them.

The book develops this nascent theory systematically: it builds the equidistribution theory of polynomial sequences in tori and nilmanifolds (the "physical space" side), defines and proves the basic properties of Gowers norms (the "frequency space" side), establishes the inverse conjectures for those norms over finite fields and over the integers, and applies the resulting machinery to prove that the primes contain arithmetic progressions of every length, and more generally to count solutions to any system of linear equations of bounded complexity in the primes.

How far can Fourier analysis be generalized — replacing linear phases with polynomial and nilpotent ones — to control higher-order additive patterns, and what does this theory say about the distribution of such patterns in the primes?

Section 1.1 — Equidistribution of polynomial sequences in tori

Central question

When does a polynomial sequence P(n) — where P maps the integers to a torus T^d = (R/Z)^d — distribute itself uniformly (equidistribute) as n ranges over {1, …, N}, and how does one measure and quantify that equidistribution?

Main argument

The classical asymptotic theory: Weyl's theorem. The section begins with the asymptotic regime: a sequence x(1), x(2), … in a compact metric space X is asymptotically equidistributed with respect to a Borel probability measure µ if the empirical averages E{n∈[N]} f(x(n)) converge to ∫f dµ for every continuous f. The key tool is the Weyl equidistribution criterion: a sequence in T^d = (R/Z)^d is equidistributed with respect to Haar measure if and only if all non-trivial exponential sums E{n∈[N]} e(k · x(n)) → 0 as N → ∞ for every non-zero integer vector k. This criterion, together with the van der Corput differencing lemma (which reduces equidistribution of x(n) to that of the difference sequences x(n+h) − x(n)), gives Weyl's classical theorem: if P(n) = αd n^d + … + α1 n + α_0 is a polynomial with at least one irrational non-constant coefficient, then the sequence P(n) mod 1 is equidistributed in T.

The single-scale (quantitative) theory. For applications to the primes, one cannot merely send N → ∞; one needs quantitative control at a fixed but large scale N. A sequence x : {1, …, N} → T is ε-equidistributed if |E{n∈[N]} f(x(n)) − ∫f dµ| ≤ ε for all 1-Lipschitz functions f. A polynomial sequence P(n) is ε-equidistributed on [N] unless some coefficient αj (1 ≤ j ≤ d) is within O(N^{-j}) of a rational with small denominator — i.e., unless P is "rational to within the scale." This is the Weyl equidistribution criterion at single scale, and it gives a precise quantitative refinement of the classical theory.

Simultaneous equidistribution and Ratner theory. The equidistribution of polynomial sequences in higher-dimensional tori T^d is reduced to the one-dimensional case by the Weyl criterion, since a sequence is equidistributed in T^d if and only if each projected sequence k · x(n) (k ≠ 0) is equidistributed in T. The deeper context is that polynomial sequences on tori can be seen as special cases of polynomial orbits on nilmanifolds, and their equidistribution is a special case of Ratner's theorem on unipotent flows. This broader perspective, to be elaborated in §1.6, motivates the entire book.

The ultralimit regime. A third formulation sits between asymptotic and single-scale: the ultralimit regime, which uses ultrafilters and ultraproducts to collapse the δ and F parameters that clutter single-scale statements. This regime is formally equivalent to the single-scale theory but formally resembles the asymptotic theory — qualitative and clean — and is indispensable for some of the arguments in later sections. Section 2.1 provides the full foundations.

Key ideas

• A sequence in a compact space is equidistributed if and only if it time-averages every continuous function to its space integral.
• The Weyl equidistribution criterion reduces equidistribution to the vanishing of exponential sums E e(k · x(n)).
• The van der Corput lemma reduces the equidistribution of x(n) to that of x(n+h) − x(n) for each fixed h, enabling induction on the degree of a polynomial sequence.
• Weyl's theorem: P(n) is equidistributed on T unless all its non-constant coefficients are rational.
• The single-scale theory gives explicit bounds: P is ε-equidistributed on [N] unless a coefficient is highly rational relative to N.
• The three regimes — asymptotic, single-scale, and ultralimit — are inter-translatable, each offering different clarity–quantitativeness tradeoffs.
• The equidistribution theory of polynomial sequences is a gateway to the Ratner-theory classification of polynomial orbits on nilmanifolds.

Key takeaway

Polynomial sequences equidistribute unless they are "close to rational," and this precise quantitative version of equidistribution is the foundational input for all of higher-order Fourier analysis.

Section 1.2 — Roth's theorem

Central question

Can linear Fourier analysis prove that every dense subset of the integers contains infinitely many three-term arithmetic progressions, and what is the structure–randomness dichotomy that drives the proof?

Main argument

Roth's theorem. The section proves that if A ⊂ Z has positive upper density δ(A) = lim sup_{N→∞} |A ∩ [−N,N]| / (2N+1) > 0, then A contains infinitely many three-term arithmetic progressions a, a+r, a+2r (r > 0). This is the first non-trivial case of Szemerédi's theorem, which asserts the same for progressions of every length k.

The counting identity. The number of three-term progressions in A ∩ Z/N'Z can be expressed as the Fourier sum E{n,r ∈ Z/N'Z} 1A(n) 1A(n+r) 1A(n+2r) = Σα \hat{1}A(α) \hat{1}A(−2α) \hat{1}A(α). This identity shows that the count is determined by the Fourier coefficients of 1_A. If all non-zero Fourier coefficients are small (A is "Fourier-uniform"), then the count is approximately δ^3 N^2 — the random expectation — and A trivially contains many progressions.

The density increment argument. If A is not Fourier-uniform, then some Fourier coefficient at frequency α is large, meaning A correlates significantly with a linear character n ↦ e(αn). This correlation can be used to locate a long arithmetic subprogression P ⊂ [N] on which A has density at least δ + c(δ) — a density increment. Since density is bounded above by 1, this process terminates after finitely many iterations, producing a subprogression where A is dense enough to contain a progression by the base case. Roth's original 1956 proof followed this strategy.

The energy increment argument. An alternative proof decomposes 1_A into a structured component (capturing all significant Fourier correlations) and a pseudorandom residual. One maximizes the L^2 "energy" of the structured component via a greedy algorithm — the energy increment — which converges because energy is bounded. In the limit, the residual is genuinely Fourier-pseudorandom and the count can be evaluated by a direct Fourier calculation.

The key dichotomy: structure vs. randomness. Both proofs instantiate the same meta-principle: either the object is pseudorandom (and the count follows by direct calculation), or it correlates with a structured object, which forces a "gain" (density increment or energy increment) that can only happen finitely many times. This structure–randomness dichotomy is the engine that drives higher-order Fourier analysis and Szemerédi theory.

Key ideas

• Three-term progression counts are controlled by the L^4 Fourier norm: supα |hat{1}A(α)|.
• A set either has small Fourier coefficients everywhere (pseudorandom) or has a large Fourier coefficient at some frequency (structured).
• The density increment argument: large Fourier coefficient → density boost on a subprogression → finitely many steps → done.
• The energy increment argument: decompose into structured + pseudorandom pieces using greedy energy maximization.
• Both approaches extend to longer progressions (Szemerédi's theorem), but require a deeper inverse theory for the Gowers norms.
• The proofs already hint at why linear Fourier analysis is not enough for length-4 progressions: the relevant norm is not an L^4 Fourier norm but a U^3 Gowers norm.

Key takeaway

Roth's theorem is proved by a Fourier-analytic structure–randomness dichotomy, and understanding why this proof cannot directly extend to longer progressions motivates the entire theory of Gowers norms and their inverses.

Section 1.3 — Linear patterns

Central question

Which additive patterns in a finite abelian group are controlled by the Gowers uniformity norms, and what are the fundamental properties of those norms?

Main argument

Linear Fourier analysis fails for length-4 progressions. The section opens by demonstrating a fundamental obstruction. The count of four-term arithmetic progressions a, a+r, a+2r, a+3r in a subset A ⊂ Z/NZ is not controlled by the classical Fourier L^4 norm (i.e., by supα |hat{1}A(α)|). One can construct examples — using the equidistribution theory from §1.1 — where the Fourier transform of A looks flat (A is "Fourier-pseudorandom") and yet A has an atypical number of length-4 progressions because A correlates with a quadratic phase e(αn^2) rather than a linear one.

Parallelopipeds as universal patterns. A key structural insight is that one can largely reduce the study of arbitrary finite-complexity additive patterns to the study of a single family: the d-dimensional parallelopipeds {x + ω1 h1 + … + ωd hd : ωi ∈ {0,1}}. For d=1 these are pairs; for d=2 they are parallelograms {x, x+h1, x+h2, x+h1+h_2}; for d=3 they are full 8-point parallelopipeds. The Hilbert cube lemma (Exercise 1.3.2) shows that dense sets automatically contain high-dimensional parallelopipeds, making them much easier to find than arithmetic progressions.

Gowers uniformity norms. The correct measure for controlling parallelogram-type patterns is the Gowers U^d norm (also called the uniformity norm of order d), defined for functions f : G → C on a finite abelian group G by:

‖f‖{U^d(G)}^{2^d} := E{x,h1,…,hd ∈ G} ∏{ω ∈ {0,1}^d} C^{|ω|} f(x + ω1 h1 + … + ωd h_d)

where C^{|ω|} denotes complex conjugation when |ω| = ω1 + … + ωd is odd. These norms form an increasing sequence: ‖f‖{U^1} ≤ ‖f‖{U^2} ≤ ‖f‖{U^3} ≤ …, and they generalize the L^4 Fourier norm: ‖f‖{U^2} equals the L^4 norm of the Fourier transform of f.

Gowers–Cauchy–Schwarz and the counting lemma. The key utility of the Gowers norms is the Gowers–Cauchy–Schwarz inequality, which bounds multilinear averages over parallelopipeds in terms of Gowers norms of the inputs. This implies that whenever all Gowers norms of 1_A − δ are small (A is "Gowers-pseudorandom"), the counts of any bounded-complexity linear pattern in A approximate the expected random value δ^k. The challenge is to prove that a large Gowers norm forces correlation with a structured object — this is the inverse conjecture, treated in §§1.5–1.6.

Polynomial phases and discrete derivatives. The section introduces the operator ∂h f(x) := f(x+h) − f(x) (discrete derivative), and defines a function P : G → R/Z to be a polynomial of degree ≤ d if ∂{h1} ∂{h2} … ∂{h{d+1}} P(x) = 0 for all x and all hi. The U^{d+1} norm of e(P) equals 1 precisely when P is a polynomial of degree ≤ d, connecting the algebraic notion of polynomiality with the analytic notion of Gowers norm saturation.

Key ideas

• Classical Fourier (L^4) analysis controls three-term progressions but provably not four-term progressions.
• Any finite-complexity linear pattern is controlled by parallelopipeds, which in turn are controlled by Gowers norms.
• The Gowers U^d norm is the 2^d-th root of the average of f over all d-dimensional parallelopipeds, with alternating complex conjugations.
• ‖f‖{U^2(G)} = (Σξ |f̂(ξ)|^4)^{1/4}: the U^2 norm is the classical L^4 Fourier norm.
• A function saturates ‖f‖{U^{d+1}} = ‖f‖{L^∞} if and only if f = e(P) for a degree-d polynomial P.
• The Gowers–Cauchy–Schwarz inequality: multilinear parallelogram averages are bounded by Gowers norms of the inputs.
• Dense sets automatically contain all finite-dimensional parallelopipeds (Hilbert cube lemma); arithmetic progressions are harder.

Key takeaway

The Gowers uniformity norms are the right Fourier-analytic quantities for controlling higher-order additive patterns: they form a hierarchy beyond the classical Fourier L^4 norm, and their inverse theory — characterizing when a large Gowers norm is forced — is the central problem of higher-order Fourier analysis.

Section 1.4 — Equidistribution of polynomials over finite fields

Central question

How does the equidistribution theory of polynomial sequences work over vector spaces over finite fields, and how does the finite-field model illuminate and simplify the integer theory?

Main argument

The finite-field model. Vector spaces V = Fp^n over a prime field Fp serve as a dyadic model for the integers. They share additive structure with Z but differ in important ways: subspaces (the finite-field analogue of arithmetic progressions) are closed under addition, which simplifies many arguments. The trade-off is that finite fields have bounded torsion (every element satisfies p·x = 0) but lack bounded generation. Despite this, the finite-field setting illuminates the integer theory, and results proved first over F_p often suggest the right integer analogues.

Classical polynomials. A function P : Fp^n → Fp is a classical polynomial of degree ≤ d if it can be written as P(x1, …, xn) = Σ c{i1,…,in} x1^{i1}…xn^{in} with i1 + … + in ≤ d and each exponent in {0, …, p−1}. Equivalently, P is a polynomial of degree ≤ d if and only if ∂{h1}…∂{h{d+1}} P(x) = 0 for all x, hi — matching the Gowers-norm definition from §1.3. The space Poly{≤d}(V → Fp) has size at most p^{C(d+n, d)}.

Non-classical polynomials. When one works with phases e(P) : V → C (the Pontryagin dual), the relevant polynomials are not classical ones P : V → F_p but non-classical polynomials P : V → R/Z whose image may not lie in the p-th roots of unity. In high characteristic (p > d), every non-classical polynomial of degree ≤ d is equivalent modulo lower-order terms to a classical one, but in low characteristic (p ≤ d) there are genuinely new non-classical polynomials not captured by the classical theory — a phenomenon first identified by Lovett–Meshulam–Samorodnitsky and Green–Tao.

Degree-lowering under multiplication by p. A key algebraic lemma: if P ∈ Poly{≤d}(V → R/Z), then pP ∈ Poly{≤d−p+1}(V → R/Z). That is, multiplying by the characteristic p reduces the degree by p−1. This is characteristic of the finite-field setting and has no analogue over Z.

Equidistribution of polynomials over F_p. A polynomial phase e(P) : V → C is equidistributed (i.e., E_{x∈V} e(P(x)) = 0) if and only if P is not a polynomial of degree ≤ 0 (i.e., not constant). More generally, the rank of a polynomial (the minimal co-dimension of a subspace on which it reduces to lower degree) controls equidistribution: high-rank polynomials equidistribute very well, and degree-d polynomials of high rank are equidistributed on any affine subspace of large enough dimension. This is the finite-field analogue of Weyl's theorem.

Key ideas

• The finite-field vector space F_p^n is the standard dyadic model for the integers: it has bounded torsion but not bounded generation.
• Classical polynomials of degree ≤ d over F_p are exactly those functions whose (d+1)-st finite difference vanishes, matching the Gowers U^{d+1} saturation condition.
• In high characteristic (p > d) the non-classical and classical theories agree; in low characteristic they diverge.
• Multiplying a degree-d polynomial by p drops its degree by p−1, reflecting the bounded torsion of the field.
• The rank of a polynomial measures its "non-degeneracy" and controls how equidistributed it is.
• The finite-field equidistribution theory serves as a simplification and testing ground for the harder integer theory in §1.6.

Key takeaway

The finite-field setting offers a cleaner, more algebraic version of equidistribution theory that parallels the integer theory and serves as the key model for understanding the inverse conjecture; the main subtlety is the classical vs. non-classical distinction in low characteristic.

Section 1.5 — The inverse conjecture for the Gowers norm I. The finite field case

Central question

If a bounded function f : V → C on a finite-field vector space has large Gowers U^{d+1} norm, must f correlate with a polynomial phase e(φ) of degree ≤ d, and how is this proved?

Main argument

Three regimes of inverse theorems. The section distinguishes three versions of the inverse problem for U^{d+1}(V): the 100% problem (when ‖f‖{U^{d+1}} = ‖f‖{L^∞} = 1, must f be a polynomial phase?), the 99% problem (when ‖f‖{U^{d+1}} ≥ 1−ε, must f be close to a polynomial phase?), and the 1% problem (when ‖f‖{U^{d+1}} ≥ ε > 0, must f correlate with a polynomial phase?). The 100% case is easy: ‖e(P)‖_{U^{d+1}} = 1 if and only if P is degree ≤ d. The 99% case gives approximate structure near a polynomial. The 1% case is the hard, usable theorem.

The 99% inverse theorem (Proposition 1.5.1). If ‖f‖{L^∞} ≤ 1 and ‖f‖{U^{d+1}(V)} ≥ 1−ε, then there exists a degree-≤d polynomial φ ∈ Poly{≤d}(V → R/Z) such that ‖f − e(φ)‖{L^1(V)} = O{d,F}(ε^c) for some constant c > 0. The proof proceeds by induction on d using the structure of the polynomial group Poly{≤d}.

The 1% inverse theorem (Theorem 1.5.3). The main result: in characteristic p > d, if ‖f‖{L^∞} ≤ 1 and ‖f‖{U^{d+1}(V)} ≥ ε, then there exists φ ∈ Poly{≤d}(V → R/Z) such that |⟨f, e(φ)⟩{L^2}| ≫_{ε,d,F} 1. The proof is non-trivial and required several stages historically: the d=2 case is Green–Tao (2008), also independently Samorodnitsky (2007); the high-characteristic case for d > 2 used a Furstenberg correspondence + Host–Kra ergodic theory approach (Bergelson–Tao–Ziegler 2010); the low-characteristic case came later (Tao–Ziegler 2011).

Szemerédi's theorem for finite fields. As a corollary of the inverse theorem, one obtains an analogue of Szemerédi's theorem: if A ⊂ Fp^n satisfies |A| ≥ δ|Fp^n|, then for n large enough depending on p and δ, A contains an affine line {x, x+r, …, x+(p−1)r} for some x, r ∈ F_p^n, r ≠ 0. Both a density-increment proof and an energy-increment proof are given.

Classical vs. non-classical polynomials in low characteristic. A subtle issue: in characteristic 2 and for d ≥ 3, the 1% inverse theorem requires the full space of non-classical polynomials Poly{≤d}(V → R/Z), not merely the classical subspace Poly{≤d}(V → F2). There exist non-classical quadratic (over F2) phases that fail to correlate with any classical polynomial of the same degree. This is an obstruction unique to low characteristic.

Key ideas

• The U^{d+1} norm has a "100% inverse" (polynomial phases saturate it exactly), a "99% inverse" (near-saturation implies proximity to a polynomial), and a "1% inverse" (non-trivial Gowers norm implies non-trivial correlation with a polynomial).
• Converse to 1% inverse: correlation with a degree-d polynomial phase implies non-trivial U^{d+1} norm (easy direction).
• The hard "1% inverse theorem" was proved over many years: d=2 in 2007–08, general high-characteristic d in 2010, low-characteristic case in 2011.
• In high characteristic, classical and non-classical polynomials of degree ≤ d are interchangeable for the inverse theorem.
• In low characteristic (char = 2, d ≥ 3), non-classical polynomials genuinely escape classical polynomial approximation.
• Inverse theorems imply Szemerédi-type results by a density/energy increment argument over finite fields.

Key takeaway

The inverse conjecture for the Gowers norm over finite fields — a large U^{d+1} norm forces correlation with a degree-d polynomial phase — is the key structural theorem of the finite-field theory, and its proof reveals a rich interplay between algebraic degree, characteristic, and equidistribution.

Section 1.6 — The inverse conjecture for the Gowers norm II. The integer case

Central question

Over the integers (or cyclic groups Z/NZ), which structured objects replace polynomial phases as the "obstructions" to small Gowers norms for U^{s+1} with s ≥ 2, and how does one prove the inverse conjecture in this setting?

Main argument

Polynomial phases are insufficient for s ≥ 2. In the integer setting, an unexpected new phenomenon arises: for U^3(Z/NZ) and higher, classical polynomial phases e(αn^2 + βn + γ) are not sufficient to explain large Gowers norms. There exist functions f with large U^3 norm that correlate with bracket polynomial phases such as n ↦ e(⌊αn⌋βn) — functions of a polynomial type that are piecewise-polynomial rather than globally polynomial. This failure of classical polynomials forces the introduction of a broader class.

Three competing enlargements of the polynomial class. Tao discusses three closely related candidates: (1) local polynomials (polynomials on arithmetic progressions); (2) bracket polynomials (piecewise polynomial expressions involving integer-part functions); and (3) nilsequences — sequences of the form n ↦ F(g^n · x) where G is a nilpotent Lie group, Γ ⊂ G is a cocompact lattice, x ∈ G/Γ, and F : G/Γ → C is Lipschitz. The book focuses on nilsequences as the most structurally natural class.

Polynomial maps and nilmanifolds. A nilmanifold is a compact homogeneous space G/Γ where G is a connected, simply connected nilpotent Lie group and Γ is a cocompact discrete subgroup. A polynomial map g : Z → G generalizes the concept of a degree-d polynomial to group-valued maps: it satisfies ∂{h1}…∂{h{d+1}} g(n) = 1G for all hi. A nilsequence of degree ≤ d is a sequence a_n = F(g(n)Γ) for a polynomial map g : Z → G of degree ≤ d and a Lipschitz function F : G/Γ → C. For d=1 these reduce to linear characters; for d=2 they generalize quadratic phase functions.

Equidistribution on nilmanifolds. The section develops the equidistribution theory of polynomial orbits on nilmanifolds, generalizing §1.1's theory on tori (which are abelian nilmanifolds). The key theorem (due to Leibman, Green–Tao) states that a polynomial sequence g(n)Γ is equidistributed on G/Γ if and only if for every non-trivial character χ of G/Γ, the sequence χ(g(n)) is equidistributed on T — a nilmanifold analogue of the Weyl equidistribution criterion.

The inverse conjecture over Z/NZ (Green–Tao–Ziegler). The main result, proved in [GrTa2010, GrTaZi2010b], states: if f : Z/NZ → C with ‖f‖{L^∞} ≤ 1 and ‖f‖{U^{s+1}(Z/NZ)} ≥ ε, then f correlates with a degree-s nilsequence — specifically, |E{n∈Z/NZ} f(n) \overline{F(g(n)Γ)}| ≥ c(s, ε) > 0 for some degree-s polynomial map g and Lipschitz function F with ‖F‖{Lip} = O(1). Conversely, any nilsequence of degree s drives a large U^{s+1} norm.

Host-Kra groups and the algebraic framework. The section introduces the Host–Kra group HK^k(H, ≤ d), a subgroup of H^{2^k} encoding the combinatorial constraints that define polynomial maps, following work of Host–Kra (2005) and Leibman. These groups provide the algebraic framework for extending polynomial concepts from abelian to nilpotent settings, and Leibman's theorem that polynomial maps on nilpotent groups form a group (not merely a set) is a non-trivial fact relied upon throughout.

Key ideas

• Over Z/NZ with s ≥ 2, classical polynomial phases are not the correct obstruction class: bracket polynomials and nilsequences appear.
• Nilsequences are defined by polynomial orbits on nilmanifolds G/Γ (compact quotients of nilpotent Lie groups); they include all polynomial phases as a special abelian case.
• Equidistribution of polynomial orbits on nilmanifolds is governed by a Weyl-type criterion involving all characters of the nilmanifold.
• The Green–Tao–Ziegler inverse theorem: ‖f‖_{U^{s+1}(Z/NZ)} ≥ ε implies correlation with a degree-s nilsequence.
• Bracket polynomials like n ↦ e(⌊αn⌋βn) are "morally" nilsequences, arising from the 2-step Heisenberg nilmanifold.
• The Host–Kra groups provide the algebraic structure underlying polynomial maps in non-abelian settings.
• The inverse theorem over Z is the crucial input for counting patterns in the primes.

Key takeaway

The correct "higher-order Fourier analysis" over the integers requires replacing classical polynomial phases with nilsequences — sequences driven by polynomial orbits on nilmanifolds — and the Green–Tao–Ziegler inverse theorem confirms that these are exactly the obstructions to small Gowers norms.

Section 1.7 — Linear equations in primes

Central question

How does the machinery of higher-order Fourier analysis, combined with sieve theory, allow one to count solutions to systems of linear equations in the primes, and why are twin primes and even Goldbach beyond this method?

Main argument

The scope of the theory. The section applies the preceding theory to the primes P = {2, 3, 5, 7, …}. The most famous problems — twin primes (p2 − p1 = 2) and even Goldbach (p1 + p2 = N) — lie outside the scope of these methods because the relevant linear forms are commensurate (their linear span has dimension less than the number of variables), giving the system infinite Gowers complexity. But systems of bounded complexity — including arithmetic progressions p, p+r, …, p+(k−1)r and the odd Goldbach equation p1 + p2 + p_3 = N — are tractable.

Roth's theorem in the primes (Green 2005). The section develops the argument around a key motivating result: any subset A ⊂ P of positive relative density (lim sup |A ∩ [N]| / |P ∩ [N]| > 0) contains infinitely many three-term arithmetic progressions. The strategy is to transfer Roth's theorem from the integers to the primes. The main difficulty is that the primes have zero density in the integers (by the prime number theorem, |P ∩ [N]| ~ N / log N), so one cannot directly apply the integer theorem.

Three steps of the transference strategy. The proof is organized around three components:

(1) The general transference principle: any additive combinatorial result about dense subsets of the integers can be transferred to dense subsets of a pseudorandom measure — a positive measure ν on [N] that approximates the uniform measure in all Gowers norm senses (ν has small ‖ν − 1‖_{U^s} for all relevant s). This step uses no number theory and can be accomplished either by Fourier methods (for s ≤ 1) or by Hahn–Banach duality arguments.

(2) Sieve theory: the primes, or a suitable affine modification νP of the primes (the von Mangoldt function Λ, or a smoothed version thereof), constitute a pseudorandom measure. The key input is the Selberg sieve (or a variant used by Goldston–Yıldırım–Pintz), which shows that νP satisfies the required correlation conditions. The only fact about the Riemann zeta function truly needed is that it has a simple pole at s = 1 — no deep analytic continuation or zero-free region is required.

(3) Nilsequence correlations: to obtain asymptotics (not just existence) for patterns in the primes, one needs to show that the von Mangoldt function Λ has negligible correlation with all degree-s nilsequences for relevant s. This requires deeper analytic number theory: Vinogradov's method for estimating oscillatory sums over primes, and the Siegel–Walfisz theorem on primes in arithmetic progressions with good error terms.

The Green–Tao theorem. The full Green–Tao theorem (2008), proved with the same three-step strategy (transferring Szemerédi's theorem rather than Roth's theorem), establishes that the primes contain arithmetic progressions of every length k. The asymptotics for the number of k-term progressions in the primes up to N require the full inverse conjecture for Gowers norms (§1.6) and nilsequence correlation estimates.

The dense model theorem. A key technical tool in the transference step is the dense model theorem: any function f that is dense with respect to a pseudorandom measure ν can be modeled (up to Gowers-norm error) by a function g that is dense with respect to the uniform measure. This "porting" of density from a pseudorandom setting to the uniform setting is what allows Roth's and Szemerédi's theorems to be applied.

Key ideas

• The primes have zero density in Z, so one cannot directly apply Szemerédi's theorem; instead, one transfers the theorem via a pseudorandom measure framework.
• Twin primes and even Goldbach are excluded because their associated linear forms are commensurate (infinite Gowers complexity).
• The transference principle converts additive combinatorial results over dense subsets of Z to dense subsets of a pseudorandom measure — using no number theory.
• The Selberg sieve shows the primes satisfy the required pseudorandomness conditions, with only ζ(1) = ∞ needed from zeta function theory.
• Asymptotics (not just existence) require nilsequence correlation estimates for the von Mangoldt function, using Vinogradov's method and Siegel–Walfisz.
• The dense model theorem: a function dense relative to a pseudorandom measure can be approximated in Gowers-norm topology by a function dense relative to uniform measure.
• The Green–Tao theorem (primes contain k-term progressions for all k) is the motivating application of the entire book.

Key takeaway

The Green–Tao theorem that the primes contain arithmetic progressions of every length is proved by combining the inverse conjecture for Gowers norms with sieve theory and a transference principle, illustrating how higher-order Fourier analysis reaches all the way into the distribution of the prime numbers.

Section 2.1 — Ultralimit analysis and quantitative algebraic geometry

Central question

How does the ultrafilter formalism bridge the gap between qualitative (infinitary) and quantitative (finitary) mathematical arguments, and how can it be used to extract uniform quantitative bounds from classical algebraic geometry?

Main argument

The ultrafilter and ultralimit construction. An ultrafilter α∞ on N is a finitely additive {0,1}-valued measure on P(N) that is non-principal (no atom). Given an ultrafilter and a sequence of metric spaces Xn, the ultraproduct ∏{α∞} Xn is the space of equivalence classes of sequences (xn), where (xn) ~ (yn) if {n : xn = yn} ∈ α∞. For sequences of real numbers, the ultralimit lim{α∞} xn is the unique limit along α_∞, which always exists for bounded sequences. This formalizes a "generalized limit" that picks a consistent limiting value from any bounded sequence, regardless of whether ordinary limits exist.

Łoś's theorem and elementary limits. The foundational result is Łoś's theorem: the ultraproduct ∏{α∞} Xn satisfies any first-order sentence that is satisfied by Xn for α_∞-almost all n. This means the ultraproduct is an elementary limit — it inherits all first-order properties of the components. This is a manifestation of the compactness theorem in logic.

Relationship to nonstandard analysis. Ultralimit analysis is closely related to nonstandard analysis (Robinson's framework), with the same relationship as between measure theory and probability theory: both formalisms do the same mathematics, but emphasize different aspects. The text uses ultralimit language to emphasize that limit objects are ultralimits of standard objects.

Quantitative algebraic geometry via ultraproducts. The section's main application demonstrates ultralimit analysis by deriving quantitative versions of theorems in algebraic geometry from their classical qualitative versions. For example: the classical theorem that a variety of degree d in n variables over an algebraically closed field has at most polynomially many irreducible components (a qualitative bound) can be "lifted" via ultraproducts to give a quantitative bound that is uniform in the field and the ambient space — a bound depending only on d and n. The ultraproduct acts as a "complexity absorber," allowing one to reason qualitatively in the limit and then extract uniform quantitative bounds by compactness.

Applications to Gromov's theorem and Szemerédi. As further illustrations: Gromov's polynomial growth theorem (that finitely generated groups with polynomial volume growth are virtually nilpotent) has a quantitative version derivable via ultraproducts from the qualitative statement. Similarly, the deduction of Szemerédi's theorem from Furstenberg's multiple recurrence theorem can be re-derived via ultralimit analysis, clarifying the relationship between ergodic and combinatorial proofs.

Key ideas

• A non-principal ultrafilter on N assigns 0 or 1 to every subset, consistently with finite intersections, but to no finite set.
• Every bounded real sequence has a well-defined ultralimit; ultraproducts of metric spaces are complete metric spaces (for bounded distances).
• Łoś's theorem: ultraproducts inherit all first-order properties that hold for almost all components.
• Ultralimits produce the qualitative (infinitary) objects from which quantitative (finitary) bounds can be read off via compactness.
• The ultraproduct of a sequence of finite fields F_q (with q → ∞ along the ultrafilter) is a pseudo-finite field, an algebraically closed field with additional number-theoretic properties.
• Quantitative algebraic geometry: uniform degree bounds on varieties, Bézout's theorem with uniform constants, can be extracted from classical qualitative theorems.
• Ultralimit analysis is a flexible tool that reduces messy quantitative arguments to cleaner qualitative ones in the limit object.

Key takeaway

Ultrafilters and ultraproducts provide a systematic machine for converting qualitative ("soft") mathematical theorems into quantitative ("hard") theorems with uniform bounds, and this machine underlies much of the technical machinery needed in higher-order Fourier analysis.

Section 2.2 — Higher order Hilbert spaces

Central question

How can the axioms of inner product spaces and Hilbert spaces be generalized to a hierarchy of "higher-order" Hilbert spaces with 2^d-ary inner products, and what is the abstract framework that unifies the Gowers uniformity norms, Gowers box norms, and Gowers–Host–Kra seminorms?

Main argument

Classical Hilbert spaces: the order-1 case. A classical (order-1) Hilbert space is a complex vector space V with a sesquilinear inner product ⟨·,·⟩ : V × V → C satisfying conjugate symmetry, positive semi-definiteness, and (for Hilbert spaces) completeness. The Cauchy–Schwarz inequality |⟨v, w⟩| ≤ ‖v‖ ‖w‖ and the triangle inequality follow from these axioms.

The order-d inner product. The section proposes replacing the binary inner product with a 2^d-ary inner product — a multilinear map ⟨(fω){ω ∈ {0,1}^d}⟩ : V^{{0,1}^d} → C satisfying appropriate generalizations of conjugate symmetry, sesquilinearity in each slot, and positive semi-definiteness. The order-1 case (d=1) recovers the classical binary inner product. The order-2 case (d=2) gives a quartilinear form ⟨f{00}, f{01}, f{10}, f{11}⟩ analogous to ∫ f{00} f{01} f{10} f{11}.

The Cauchy–Schwarz–Gowers inequality. Analogously to the classical Cauchy–Schwarz inequality, these higher-order inner products satisfy a Cauchy–Schwarz–Gowers (CSG) inequality: the absolute value of the 2^d-ary inner product is bounded by the product (over all j ∈ {0,1}^d) of the 2^{d-1}-ary semi-norms of the corresponding lower-dimensional "slices." This inequality is proved by repeated application of the classical Cauchy–Schwarz inequality, inducting on d.

The resulting semi-norms. By setting all the f_ω equal and applying the CSG inequality, one obtains a semi-norm ‖f‖ := ⟨f, f, …, f⟩^{1/2^d}. For the concrete examples below, these semi-norms are exactly the Gowers norms.

Concrete instances.

• Gowers uniformity norms ‖f‖{U^d(G)}: the inner product is E{x, h1, …, hd ∈ G} ∏_{ω} C^{|ω|} f(x + ω · h), the average over d-dimensional parallelopipeds with alternating conjugations.
• Gowers box norms ‖f‖{□^d(X1 × … × X_d)}: used in the regularity theory of hypergraphs; the inner product averages f over d-dimensional "cubes" in a product space.
• Gowers–Host–Kra (GHK) seminorms ‖f‖_{U^d(X)} on an ergodic measure-preserving system (X, µ, T): defined via the Host–Kra structure theory using conditional expectations relative to characteristic factors.
• L^{2^d}(X): the Lebesgue spaces with exponent a power of two are the simplest non-trivial examples.

Abstract axiomatics. The section sets out a purely abstract axiomatization: a degree-d Hilbert space (or order-d Hilbert space) is a complex vector space equipped with a 2^d-ary form satisfying the analogues of conjugate symmetry, sesquilinearity, and positive semi-definiteness. All the above concrete examples satisfy this axiom system. The abstract framework is original to this section of the book — Tao notes it does not appear explicitly elsewhere in the literature — and provides a unified language for Gowers norms, box norms, and GHK seminorms.

Key ideas

• Classical Hilbert spaces are the order-1 case; the order-d generalization replaces the binary inner product with a 2^d-ary inner product.
• The Cauchy–Schwarz–Gowers inequality is the order-d analogue of Cauchy–Schwarz, proved by d-fold application of the classical inequality.
• The resulting semi-norms are: Gowers uniformity norms U^d(G), Gowers box norms □^d, Gowers–Host–Kra seminorms U^d(X), and L^{2^d} spaces.
• The abstract axiom system for degree-d Hilbert spaces is presented here for the first time; it unifies all the above examples.
• Higher-order Hilbert spaces arise wherever one needs to measure uniformity of functions with respect to parallelogram patterns.
• The tensor product structure (V ⊗ Ṽ where Ṽ is the complex conjugate of V) underlies the 2^d-ary inner product in the same way V ⊗ V̄ underlies the classical inner product.

Key takeaway

Higher-order Hilbert spaces are the natural abstract framework unifying Gowers norms, box norms, and ergodic seminorms: they arise from replacing the binary inner product with a 2^d-ary inner product that satisfies a generalized Cauchy–Schwarz inequality, and the resulting hierarchy of norms is exactly the right tool for measuring higher-order pseudorandomness.

Section 2.3 — The uncertainty principle

Central question

What is the abstract duality between internal (physical-space) and external (frequency-space) descriptions of mathematical objects, and how does this duality manifest in higher-order Fourier analysis and its connections to other fields?

Main argument

Duality as a recurring mathematical theme. The section opens with a survey of duality across mathematics, organized around the idea that any mathematical object X can be described either internally (by listing what X contains or what maps go into X) or externally (by listing how X interacts with its ambient context, or what maps go out of X). These two perspectives are typically "dual" in a precise sense:

• Vector space duality: vectors in V vs. linear functionals on V (Hahn–Banach).
• Subspace duality: a subspace W vs. its orthogonal complement W^⊥ (Hahn–Banach).
• Convex duality: extreme points of K vs. supporting half-spaces (Farkas's lemma).
• Ideal-variety duality: points in V(I) vs. polynomial generators of I (Nullstellensatz).
• Hilbert space duality: vectors in H vs. linear functionals via Riesz representation.
• Semantic-syntactic duality: models of a theory vs. axioms of that theory (Gödel completeness).
• Intrinsic-extrinsic duality: intrinsic geometry (curvature) vs. extrinsic embedding (Nash, theorema egregium).
• Group duality: presentations (generators and relations) vs. representations (Cayley's theorem).
• Pontryagin duality: elements of a locally compact abelian group G vs. characters in Ĝ.
• Pontryagin subgroup duality: subgroups of G vs. orthogonal complements in Ĝ (Poisson summation).
• Fourier duality: physical-space values f(x) vs. frequency-space values f̂(ξ).

The uncertainty principle as a constraint on simultaneous localization. The uncertainty principle in Fourier analysis states that a function cannot be simultaneously concentrated in both physical space and frequency space. In its most classical form (Heisenberg uncertainty principle), a function and its Fourier transform cannot both have small variance: Var(f) · Var(f̂) ≥ 1/(4π)^2. More generally, in the harmonic analysis of finite abelian groups, the support sizes satisfy |supp(f)| · |supp(f̂)| ≥ |G|.

The higher-order uncertainty principle. In higher-order Fourier analysis, the relevant duality is between Gowers norms (which measure pseudorandomness in physical space, i.e., lack of higher-order structure) and nilsequences (which describe structured functions in frequency space). The section formalizes this as an uncertainty principle for Gowers norms: a function cannot simultaneously have small Gowers U^{d+1} norm and be well-approximated by a degree-d nilsequence, because the two are dual descriptions of the same structure.

Applications of duality in the text. The section connects the duality theme to tools used throughout the book: the Hahn–Banach theorem in transference arguments (§1.7), the Nullstellensatz in quantitative algebraic geometry (§2.1), the Riesz representation theorem in the abstract Hilbert space theory (§2.2), and Pontryagin duality as the foundation of classical Fourier analysis generalized by the Gowers norm hierarchy.

Key ideas

• Duality is a universal mathematical organizing principle: every mathematical object has an internal (physical) and an external (frequency) description related by a fundamental theorem.
• The eleven instances of duality listed (vector spaces, subspaces, convex bodies, varieties, Hilbert spaces, semantic-syntactic, intrinsic-extrinsic, group, Pontryagin group, Pontryagin subgroup, Fourier) all share the same meta-structure.
• The classical uncertainty principle: a function and its Fourier transform cannot both be supported on small sets.
• The higher-order analogue: small Gowers U^{d+1} norm (pseudorandomness) and large correlation with a degree-d nilsequence (structure) are incompatible.
• The Hahn–Banach theorem — one of the fundamental duality tools — plays a key role in the transference arguments of §1.7.
• Pontryagin duality for abelian groups is the foundation of classical Fourier analysis; its "higher-order" analogue is the inverse conjecture for Gowers norms.

Key takeaway

The uncertainty principle in higher-order Fourier analysis is a manifestation of the universal duality between physical-space structure (Gowers norm conditions) and frequency-space structure (nilsequence correlations), and this duality is the conceptual backbone unifying the entire book.

The book's overall argument

1. Section 1.1 (Equidistribution of polynomial sequences in tori) — establishes the foundational equidistribution theory of polynomial sequences, in both asymptotic and single-scale regimes, introducing ultralimits as a third regime that bridges the two.
2. Section 1.2 (Roth's theorem) — applies classical linear Fourier analysis to prove a dense set contains three-term arithmetic progressions, introducing the structure–randomness dichotomy (density increment and energy increment arguments) that drives the entire book.
3. Section 1.3 (Linear patterns) — demonstrates that classical Fourier analysis fails for length-4 progressions, introduces Gowers uniformity norms as the correct replacement, and proves the Gowers–Cauchy–Schwarz inequality that makes them useful for pattern counting.
4. Section 1.4 (Equidistribution over finite fields) — develops the finite-field analogue of §1.1, introducing classical and non-classical polynomials and the rank notion that measures polynomial equidistribution; this serves as a simpler model for the integer inverse problem.
5. Section 1.5 (Inverse conjecture over finite fields) — proves that large U^{d+1} norm forces correlation with a polynomial phase in the finite-field setting (in three regimes: 100%, 99%, 1%), showing Szemerédi's theorem as a corollary and exposing the classical-vs-non-classical subtlety in low characteristic.
6. Section 1.6 (Inverse conjecture over the integers) — proves the analogous result for cyclic groups Z/NZ, establishing that the correct structured objects are nilsequences (polynomial orbits on nilmanifolds), not merely polynomial phases; this is the deepest result in the book (Green–Tao–Ziegler).
7. Section 1.7 (Linear equations in primes) — applies the entire preceding theory to the distribution of primes, combining the inverse conjecture (§1.6) with sieve theory and a transference principle to prove the Green–Tao theorem that primes contain arithmetic progressions of every length.
8. Section 2.1 (Ultralimit analysis and quantitative algebraic geometry) — provides the foundational formalism of ultralimits and ultraproducts used throughout Chapter 1, and illustrates its power in deriving quantitative algebraic geometry from qualitative theorems.
9. Section 2.2 (Higher order Hilbert spaces) — presents the abstract axiomatic framework unifying Gowers norms, box norms, and Gowers–Host–Kra seminorms as instances of a hierarchy of degree-d inner product spaces satisfying the Cauchy–Schwarz–Gowers inequality.
10. Section 2.3 (The uncertainty principle) — places the entire theory in the context of the universal duality between physical-space and frequency-space descriptions, identifying the inverse conjecture as the higher-order analogue of Pontryagin duality.

Common misunderstandings

Misunderstanding: Higher-order Fourier analysis just means using higher-frequency Fourier modes.

The book's title can suggest that the "higher order" refers to looking at higher harmonics e(2αn), e(3αn), etc. In fact it means replacing linear phase functions e(αn) altogether with genuinely nonlinear structured objects — quadratic phases e(αn^2), nilsequences driven by polynomial flows on nilmanifolds, and their finite-field analogues. The classical Fourier hierarchy (harmonics at integer multiples of a base frequency) is entirely separate from the Gowers norm hierarchy.

Misunderstanding: Gowers norms are just higher L^p norms.

The Gowers U^d norms are not L^p norms for higher p. They measure a qualitatively different type of regularity: specifically, how much the function "correlates with itself" over parallelogram patterns. The U^2 norm does equal the L^4 norm of the Fourier transform, but for d ≥ 2 the U^{d+1} norm measures correlations over d-dimensional parallelopipeds with no classical Fourier analogue.

Misunderstanding: The inverse conjecture is obvious because large Fourier transform implies correlation with a character.

For U^2, the inverse theorem is essentially the classical statement that large L^4 Fourier norm forces correlation with a linear character. But for U^3 and beyond, the analogous statement — that large Gowers norm forces correlation with a nilsequence — is highly non-trivial and took multiple teams of researchers (Green–Tao, Bergelson–Tao–Ziegler, Tao–Ziegler) over several years to prove. The difficulty is that nilsequences are genuinely more complex than polynomial phases.

Misunderstanding: The Green–Tao theorem that primes contain long arithmetic progressions uses only elementary methods.

The book clarifies that even the "soft" step of the proof — the transference principle — is not trivial, and the full Green–Tao theorem for progressions of length k ≥ 4 requires the full inverse conjecture for Gowers U^{k-1} norms (§1.6) plus nilsequence correlation estimates for the von Mangoldt function, which in turn require Vinogradov's exponential sum estimates and Siegel–Walfisz.

Misunderstanding: The finite-field and integer theories are essentially the same.

The finite-field theory (§§1.4–1.5) is simpler and serves as a model for the integer theory (§1.6), but there are genuine differences. Over F_p in low characteristic (p ≤ d), non-classical polynomials exist that have no good approximation by classical ones — this is an obstruction unique to finite fields. Conversely, nilsequences (the integer obstructions) are continuous-group objects with no direct finite-field analogue.

Misunderstanding: This book is complete and settled in its treatment of higher-order Fourier analysis.

The preface explicitly describes the theory as "still incomplete to some extent." The inverse conjecture for the integers was proved only shortly before publication, and several aspects of the finite-field theory (especially in low characteristic) remained active research areas. The book covers the foundational layer, not the frontier.

Central paradox / key insight

Classical Fourier analysis succeeds for length-3 arithmetic progressions because the count of such progressions is determined entirely by the Fourier transform — by how a set correlates with linear characters. This might suggest that for length-4 progressions, one simply needs to look at Fourier transforms at more frequencies. But this turns out to be false in a sharp, structural sense: one can construct sets that look completely "Fourier-random" (all Fourier coefficients are small) and yet have an anomalous number of length-4 progressions, because the set is not "Gowers-random" — it correlates with a quadratic phase function that the Fourier transform is blind to.

The key insight of the book is that there is an entire hierarchy of notions of pseudorandomness — Gowers uniformity at orders 2, 3, 4, … — each strictly finer than the previous, and each corresponding to a different class of structured objects (linear characters, polynomial phases, nilsequences) that can cause a failure of that level of pseudorandomness. Linear Fourier analysis is just the first level. Each level requires its own inverse theorem — a characterization of which structured object forces a large Gowers norm at that level — and the inverse conjecture (especially its proof over the integers by Green, Tao, and Ziegler) is the central achievement that makes the hierarchy usable.

A set can be random from the perspective of every Fourier frequency and yet be structured enough to contain far fewer (or far more) arithmetic progressions of length four than a truly random set — and the correct language to describe this phenomenon is not classical harmonic analysis but the theory of Gowers norms and nilsequences.

Important concepts

Equidistribution

A sequence x(1), x(2), … in a compact metric space X is equidistributed with respect to a Borel probability measure µ if for every continuous f : X → C, E{n∈[N]} f(x(n)) → ∫X f dµ as N → ∞. Quantitatively, the sequence is ε-equidistributed on [N] if |E_{n∈[N]} f(x(n)) − ∫f dµ| ≤ ε for all 1-Lipschitz f.

Gowers uniformity norm (U^d norm)

For a function f : G → C on a finite abelian group G and d ≥ 1, the Gowers U^d norm is defined by ‖f‖{U^d(G)}^{2^d} := E{x,h1,…,hd ∈ G} ∏{ω ∈ {0,1}^d} C^{|ω|} f(x + ω1 h1 + … + ωd hd), where C denotes complex conjugation. ‖f‖{U^2} equals the L^4 Fourier norm. ‖f‖{U^d} ≤ ‖f‖{U^{d+1}} for all d.

Polynomial map

A map P : H → G between additive groups (or nilpotent Lie groups) is a polynomial of degree ≤ d if all its (d+1)-fold discrete derivatives ∂{h1}…∂{h{d+1}} P(x) vanish identically. Over tori, this matches the algebraic notion of polynomials. Over nilpotent Lie groups, the definition uses the Host–Kra group framework.

Nilmanifold

A nilmanifold G/Γ is the quotient of a connected, simply connected nilpotent Lie group G by a cocompact lattice Γ. Tori T^d = R^d/Z^d are the simplest nilmanifolds (abelian case). The Heisenberg nilmanifold (from the 3-dimensional Heisenberg group) is the key example for quadratic Fourier analysis.

Nilsequence

A nilsequence of degree ≤ s is a sequence a_n = F(g(n)Γ) where G/Γ is a degree-s nilmanifold, g : Z → G is a polynomial map of degree ≤ s, and F : G/Γ → C is Lipschitz. Nilsequences of degree 1 are exactly the linear characters n ↦ e(αn); degree-2 nilsequences include the quadratic phases and bracket polynomials such as n ↦ e(⌊αn⌋βn).

Inverse conjecture for Gowers norms

The statement that ‖f‖{U^{s+1}(G)} ≥ ε (with ‖f‖{L^∞} ≤ 1) implies that f has non-trivial correlation with a degree-s structured object (polynomial phase over Fp; nilsequence over Z/NZ). This conjecture was proved over Fp by Green–Tao and Bergelson–Tao–Ziegler, and over Z/NZ by Green–Tao–Ziegler (2012). It is the central result of higher-order Fourier analysis.

Structure–randomness dichotomy

The meta-principle underlying most arguments in the book: any mathematical object is either pseudorandom (in which case it behaves like a random object and pattern counts follow from direct calculation) or it correlates with a structured object (a linear character, polynomial phase, or nilsequence), in which case one can pass to a sub-object with a higher density or more regular structure. Iterating this dichotomy finitely many times gives the theorem.

Pseudorandom measure

A non-negative function ν : Z/NZ → R is a pseudorandom measure if it approximates the uniform measure 1 in all Gowers U^s norms: ‖ν − 1‖_{U^s} = o(1). The key example is the von Mangoldt function Λ (smoothed by sieve weights), which is concentrated on the primes. The sieve theory step of the Green–Tao argument consists in verifying that Λ is pseudorandom.

Dense model theorem

A theorem asserting that any function f : Z/NZ → [0,1] that is dense with respect to a pseudorandom measure ν (i.e., E f(n)/ν(n) ≥ δ) can be approximated in Gowers-norm topology by a function g : Z/NZ → [0,1] that is dense with respect to the uniform measure (E g(n) ≥ δ'). This is the key tool in the transference step of the Green–Tao proof.

Ultralimit / ultraproduct

Given a non-principal ultrafilter α∞ on N, the ultralimit lim{α∞} xn of a bounded real sequence is its unique limit along α∞. The ultraproduct ∏{α∞} Xn is the space of equivalence classes of sequences (xn) ∈ ∏ Xn, where two sequences are equivalent if they agree on a set in α_∞. Łoś's theorem guarantees the ultraproduct inherits all first-order properties.

Van der Corput lemma

A technical lemma reducing the equidistribution of a sequence x(n) to the equidistribution of the "derivative sequences" x(n+h) − x(n) for h = 1, 2, … This is the key inductive tool for proving Weyl's theorem on polynomial equidistribution in §1.1.

Non-classical polynomial

A function P : V → R/Z from a vector space V over Fp to the unit circle that satisfies the degree-d differencing condition ∂{h1}…∂{h{d+1}} P = 0, but whose image is not contained in the p-th roots of unity (i.e., it does not factor through the map Fp → R/Z). Non-classical polynomials arise naturally in low characteristic and are needed for the inverse conjecture over F_p when char = 2 and d ≥ 3.

Rank (of a polynomial)

The rank of a polynomial P : V → R/Z over a finite field is the minimum co-dimension of an affine subspace W ⊂ V on which P is equivalent to a polynomial of strictly lower degree. High-rank polynomials equidistribute on large subspaces; low-rank polynomials have structured level sets.

Gowers–Cauchy–Schwarz inequality

The inequality ‖E{n ∈ G} f0(n) g1(n) … gk(n)‖ ≤ ‖f0‖{U^d} · C for a multilinear expression over a parallelogram pattern, analogous to the standard Cauchy–Schwarz inequality but for multi-linear averages over d-dimensional parallelopipeds. This is the main tool for deducing pattern counts from Gowers norms.

References and Web Links

Primary book and edition information

• Tao, Terence. Higher Order Fourier Analysis. American Mathematical Society, Graduate Studies in Mathematics, Volume 142, 2012. ISBN 978-0-8218-8986-2.
  • AMS bookstore page (GSM/142)
  • Tao's author page for this book
  • Draft PDF (free) on Tao's WordPress site

Background and overview

• Tao's blog category: 254B Higher Order Fourier Analysis (lecture notes)
• UCLA Math 254B course page (Spring 2010)
• Semantic Scholar entry for the book
• Survey: Higher-order Fourier Analysis and Applications (Hatami–Lovett–Szegedy)

Foundational papers the book builds on

• Gowers, W.T. "A new proof of Szemerédi's theorem." Geometric and Functional Analysis, 11 (2001), 465–588. (Introduces Gowers uniformity norms.)
• Host, B. and Kra, B. "Nonconventional ergodic averages and nilmanifolds." Annals of Mathematics, 161 (2005), 397–488. (Establishes the ergodic precursor to nilsequences.)
• Green, B. and Tao, T. "The primes contain arbitrarily long arithmetic progressions." Annals of Mathematics, 167 (2008), 481–547.
  • Green–Tao 2008 on arXiv
• Green, B., Tao, T., and Ziegler, T. "An inverse theorem for the Gowers U^{s+1}[N] norm." Annals of Mathematics, 176 (2012), 1231–1372.
  • Green–Tao–Ziegler inverse theorem on arXiv

Mini-course and secondary study resources

These are secondary summaries and should be used alongside, rather than instead of, the original book.

• Mini-course: Higher Order Fourier Analysis — Jakub Konieczny
• AMS end matter PDF (bibliography, index)