LECTURE NOTES 9 FOR 247B

TERENCE TAO

1. Fourier analysis on finite abelian groups

We have been using Fourier analysis on the Euclidean group R^{d} (and to a lesser extent, on the toral group T^{d}) for some time now. It turns out that Fourier analysis can in fact be formalised on any locally compact Hausdorff abelian group. We will come to this generalisation later in this set of notes, but to keep things simple for now we will work with the special setting of finite abelian groups, in which qualitative issues such as integrability, measurability, continuity, etc. are irrelevant, and one can do things like induct on dimension without having to invoke things like Zorn’s lemma.

Our viewpoint shall be representation-theoretic. Other approaches to the subject include the Gelfand-theoretic approach (viewing the convolution algebra as a B^{∗}- algebra), spectral-theoretic (focusing on trying to diagonalise various translationinvariant operators), or algebraic (using explicit classifications of the group and its characters). Each of these approaches is worthwhile (and they are of course closely related to each other), but we select the representation-theoretic approach as it extends relatively easily to the non-abelian case, whereas the other approaches have more difficulty.

In contrast to previous notes, the material here will be largely algebraic in nature; what analysis there is here is largely of a qualitative nature (e.g. dealing with issues of continuity, integrability, etc.) rather than quantitative (estimates, etc.).

We now turn to the details. Fix a finite additive group (G, +), where we use the addition symbol for the group operation to emphasise the abelian nature of the group; in particular we use 0 for the group identity and −x for the group inverse of x. It will not be terribly relevant for this finitary analysis, but we give G the discrete topology and the discrete σ-algebra. Let #G denote the cardinality of G. We define the normalised Haar measure dx on this group to be the normalised counting measure

∫_{G} f(x) dx := \frac{1}{#G} ∑_{x∈G} f(x).

The normalising factor \frac{1}{#G} will almost never be seen again, being concealed within the measure dx at all times.

We have the (finite-dimensional) Hilbert space L^{2}(G) of functions f : G → C, with inner product

⟨f, g⟩_{L^{2}(G)} := ∫_{G} f(x)\overline{g(x)} dx.

Note that as G is finite, all norms are equivalent, thus for instance L^{2}(G) = L^{1}(G) = L^{∞}(G). Every group element y ∈ G gives rise to a translation operator Trans_{y} : L^{2}(G) → L^{2}(G), defined by

Trans_{y}f(x) := f(x − y);

observe each such operator is a unitary operator on L^{2}(G), and furthermore the map y ↦ Trans_{y} is a homomorphism:

Trans_{y}Trans_{z} = Trans_{y+z}.  (1)

In other words, the map y ↦ Trans_{y} is a unitary representation of the group G acting on the Hilbert space L^{2}(G); this particular representation is known as the regular representation. One consequence of (1) is that all the translations commute with each other.

Given two functions f, g ∈ L^{2}(G), we can form their convolution f ∗ g ∈ L^{2}(G) by the formula

f ∗ g(x) := ∫_{G} f(y)g(x − y) dy.

One easily verifies that convolution is bilinear, associative, and commutative (the latter of course relies on the abelian nature of G). There is also an identity element δ ∈ L^{2}(G), defined by δ(x) := (#G)1_{{0}}, thus f ∗ δ = δ ∗ f = 1.

Given any g ∈ L^{2}(G), we can define the associated convolution operator T_{g} : L^{2}(G) → L^{2}(G) by T_{g}f := g ∗ f. Equivalently, we have

T_{g} = ∫_{G} g(y)Trans_{y} dy,

thus convolution operators are nothing more than linear combinations of translation operators. The convolution operators commute with each other, and are translation-invariant; conversely, it is not hard to show that every translationinvariant operator is a convolution operator. (One can view the map g ↦ T_{g} as a representation of the convolution algebra L^{2}(G) acting on itself.)

Define a translation-invariant subspace V of L^{2}(G) to be any subspace of V which is invariant under all of the translations Trans_{y}, thus Trans_{y}V = V for all y; one can also think of such a space as a component of the regular representation of G. Equivalently, V is preserved by all of the operators T_{g}. Besides the trivial examples of {0} and L^{2}(G), two other simple examples of such spaces are the space {c : c ∈ G} of constant functions, and the space {f ∈ L^{2}(G) : ∫_{G} f = 0} of meanzero functions. Another important pair of examples: given any convolution operator T_{g}, the kernel {f ∈ L^{2}(G) : T_{g}f = 0} and the range {T_{g}f : f ∈ L^{2}(G)} are also translation-invariant (this is basically because convolution operators commute with translations). The vector sum or intersection of two translation-invariant spaces is translation-invariant; since all the translation operators are unitary, we also see that the orthogonal complement of a translation-invariant space is translation-invariant.

Example 1.1. In the case of the cyclic group G = Z/NZ, given any ξ ∈ Z/NZ we can form the one-dimensional translation-invariant space V_{ξ} generated by the character e_{ξ} : x ↦ e^{2πixξ/N}. If we secretly allow ourselves the use of the finite Fourier transform, it is not hard to see that a space is translation-invariant iff it is the direct sum of some of these V_{ξ}, or equivalently if it is of the form {f ∈ L^{2}(G) : f̂|_{E} = 0} for some fixed set of frequencies E ⊂ Z/NZ. Readers familiar with the finite Fourier transform may find it instructive to keep this example in mind for the rest of this section.

Since T_{g}δ = g for all g ∈ L^{2}(G), we see that any translation-invariant space which contains the convolution identity δ, must be all of L^{2}(G). Equivalently, a translation-invariant space is proper if and only if it avoids δ.

From these facts it is clear that (a) every proper translation-invariant subspace is contained in a maximal translation-invariant subspace; and (b) every translationinvariant subspace can be expressed (possibly non-uniquely) as the direct sum of irreducible translation-invariant subspaces, i.e. non-zero subspaces which cannot be nontrivially split as the sum of two smaller translation-invariant subspaces. It is not hard to show that a translation-invariant subspace is irreducible iff its orthogonal complement is maximal.

Remark 1.2. The orthogonal projection to a translation-invariant space is a translationinvariant operator, and thus given by convolution with some function μ, in particular μ∗μ = μ. Such functions are known as idempotent measures and were influential in the classical development of harmonic analysis. We have however structured our presentation here so that these measures are not needed.

We now come to the first really non-trivial result about these spaces. There are two equivalent forms of this result. The first is phrased in terms of maximal translationinvariant subspaces:

Proposition 1.3 (Gelfand-Mazur theorem, special case). All maximal translationinvariant subspaces are hyperplanes (i.e. their codimension is one).

Proof Suppose for contradiction that we have a maximal translation-invariant subspace V of codimension two or greater. Observe that V is an ideal of the Banach algebra L^{2}(G), and hence the quotient L^{2}(G)/V is also a Banach algebra, with dimension at least two. In particular, it contains an element g which is not a multiple of the identity. From Liouville’s theorem we know that (g − z)^{−1} cannot exist for every complex z, thus there is a z ∈ C for which g−z is non-invertible. Thus the kernel of g − z is a proper non-zero ideal in L^{2}(G)/V, which induces a proper translation-invariant subspace of L^{2}(G) which strictly contains V, contradicting maximality.

The second is phrased in terms of the orthogonal complement, irreducible translationinvariant subspaces:

Proposition 1.4. All irreducible translation-invariant subspaces have dimension one.

Proof Let V be an irreducible translation-invariant subspace, and suppose for contradiction that V had dimension at least two. Then V will contain a non-zero function f which vanishes at at least one point. Then there exists y ∈ G such that Trans_{y}f is not a constant multiple of f (simply choose y so that Trans_{y} shifts a zero of f to a non-zero of f). In particular, Trans_{y} is not a constant multiple of the identity on V. On the other hand, it is a unitary transformation on V. Thus by the spectral theorem, it has an eigenvalue, and hence a non-trivial eigenspace W in V. Since all the translations commute with each other, we see that W is also translation-invariant, as is the orthogonal complement of W in V. But this contradicts the irreducibility of V.

Of course, the above two propositions are equivalent to each other; interestingly, they both secretly use complex analysis in the proof (the latter via the spectral theorem for unitary operators). In the special case of finite abelian groups, another way to establish these propositions is to use the classification of finite abelian groups and then explicitly construct a Fourier transform with which to analyse these translation-invariant spaces. This is the most direct proof, but relies heavily on the classification, which is not easily available for more general abelian groups.

Now let V be an irreducible translation-invariant subspace, thus one-dimensional. This means that each of the translation operators Trans_{y} acts by multiplication by a complex constant χ_{V} (y) on V; since Trans_{y} is unitary, we must have |χ_{V} (y)| = 1. Also, from (1) we see that χ_{V} is a homomorphism: χ_{V} (y + z) = χ_{V} (y)χ_{V} (z). In other words, χ_{V} : G → S^{1} is a multiplicative character of G; conversely, given any multiplicative character χ : G → S^{1}, the one-dimensional space generated by χ is clearly an irreducible translation-invariant space. Thus the irreducible translationinvariant spaces are in one-to-one correspondence with multiplicative characters. Introducing the exponential function e : R/Z → S^{1} by e(x) := e^{2πix}, we can write any multiplicative character χ as χ = e(ξ), where ξ : G → R/Z is an additive character, i.e. an additive homomorphism from G to R/Z. Thus the irreducible translation-invariant spaces are also in one-to-one correspondence with additive characters.

Remark 1.5. As a corollary, one also concludes that every maximal translationinvariant subspace is the orthogonal complement of a multiplicative character χ.

Define the Pontryagin dual Ĝ of G to be the space of all additive characters of G; this is clearly an additive group. Given x ∈ G and ξ ∈ Ĝ, we shall also write ξ · x for ξ(x) ∈ R/Z. We refer to elements ξ of Ĝ as frequencies. Given a frequency ξ, the associated irreducible translation-invariant space V_{ξ} is described as the linear span of the multiplicative character e_{ξ} : x ↦ e(ξ · x).

Lemma 1.6 (Orthogonality). If ξ, η are two distinct frequencies, then the associated translation-invariant subspaces V_{ξ} and V_{η} are orthogonal to each other.

Proof It suffices to show that e_{ξ} and e_{η} are orthogonal, or in other words that the expression

I := ∫_{G} e(ξ · x)e(−η · x) dx

is zero. Shifting x by y we see that

I = e(ξ · y)e(−η · y)I

for all y ∈ G. But since ξ, η are distinct, then there exists y such that ξ · y ≠ η · y, and so I = 0 as claimed.

Splitting the regular representation into irreducible (and now also orthogonal) components, we conclude

Corollary 1.7 (Peter-Weyl theorem, finite abelian case). L^{2}(G) = ⨁_{ξ∈Ĝ} V_{ξ}. In particular (by dimension count) #G = #Ĝ. Equivalently, the space {e_{ξ} : ξ ∈ Ĝ} of multiplicative characters is an orthonormal basis for L^{2}(G).

Observe that if f ∈ L^{2}(G) and ξ ∈ Ĝ, the orthogonal projection of f to V_{ξ} is given by f̂(ξ)e_{ξ}, where f̂(ξ) = ⟨f, e_{ξ}⟩_{L^{2}(G)} = ∫_{G} f(x)e(−ξ · x) dx. We thus conclude

Corollary 1.8 (Fourier inversion formula). For any f ∈ L^{2}(G), we have f = ∑_{ξ∈Ĝ} f̂(ξ)e_{ξ}.

Other quick consequences are the Plancherel identity

∥f∥_{L^{2}(G)} = ∥f̂∥_{l^{2}(Ĝ)}

and more generally Parseval identity

⟨f, g⟩_{L^{2}(G)} = ⟨f̂, ĝ⟩_{l^{2}(Ĝ)}.

It is also easy to check the convolution identity

{ \atop f ∗ g} = f̂ĝ

and dually that

f̂g = f̂∗ ĝ

where the ∗ on the right now refers to discrete convolution (using counting measure on Ĝ rather than normalised counting measure on G).

Observe that every x ∈ G can be viewed as a character x ↦ ξ · x on Ĝ, thus providing a canonical map from G to ˆ Ĝ. This map is injective. To see this, suppose that x was in the kernel of this map, then ξ · x = 0 for all ξ ∈ Ĝ, or equivalently Trans_{x} fixes each of the characters e_{ξ}. By the Fourier inversion formula this implies that Trans_{x} fixes all functions, which is observe. From the Peter-Weyl theorem we also know that G and ˆ Ĝ have the same cardinality. Thus the map is bijective. In other words, the Pontryagin dual of Ĝ is canonically identifiable with G itself.

Example 1.9. When G = Z/NZ, each ξ ∈ Z/NZ generates a character, defined by ξ · x := ξx/N. These are N distinct characters, and so by the Peter-Weyl theorem there are no further characters. Thus the abstract Fourier transform given here corresponds to the usual finite Fourier transform on Z/NZ.

We have the usual duality relationship between translation and modulation: for every f ∈ L^{2}(G) and y ∈ G, ξ ∈ Ĝ we have

{ \atop Trans_{y}f} = Mod_{−y}f̂; { \atop Mod_{ξ}f} = Trans_{ξ}f̂

where Mod_{−y}F (ξ) := e(−ξ · y)F (ξ) and Mod_{ξ}f(x) := e(ξ · x)f(x).

2. Locally compact abelian groups

Many (though not all) of the theory developed above continues to apply in the more general category of locally compact abelian (LCA) groups - topological groups which are both abelian and locally compact. (A topological group is a group with a topology under which the group operations are continuous. To avoid minor technicalities, we also assume that the topology is Hausdorff.) We will omit some details, and refer the reader to Rudin’s “ Fourier analysis on groups” for a full treatment.

Fix a LCA group G. The first task is to determine the analogue of the measure dx used earlier. This is Haar measure - a non-negative translation-invariant Radon measure which is not identically zero. The fact that such a measure exists at all is non-trivial - akin to the construction of Lebesgue measure, which is Haar measure for R^{d}. Roughly speaking, the way the measure is constructed is to use covering by translates of a small neighbourhood of the origin to create some sort of outer measure, and then send that neighbourhood to zero (normalising the measure so that some fixed compact set has measure 1, say). We will not give the details here, as it is a little tricky. However, it is relatively easy to show that Haar measure is unique up to constants. For if dx and d̃x are two Haar measures, then for any f, g ∈ C_{c}(G) one easily verifies using Fubini’s theorem that

∫_{G} ∫_{G} g(y)f(x + y) d̃xdy = (∫_{G} f(x) d̃x)(∫_{G} g(y)dy) = (∫_{G} f(x) dx)(∫_{G} g(−y) d̃y)

and so by choosing g so that the two g-integrals are non-zero, we see that dx and d̃x differ by a constant multiple. From this we also conclude that Haar measure is always reflection-symmetric, since the reflection of Haar measure is also translationinvariant and assigns the same weight to symmetric sets as the original measure.

We can now define convolution operators as before, but on L^{1}(G) rather than L^{2}(G). This turns L^{1}(G) into a B^{∗}-algebra (a Banach algebra with a conjugation, namely f̃(x) := \overline{f(−x)}). The analogue of “maximal translation-invariant subspace” is now “maximal convolution ideal” of L^{1}(G). The Gelfand-Mazur theorem argument works in this setting and shows that such maximal convolution ideals have codimension one, and are therefore identifiable with non-trivial B^{∗}-algebra homomorphisms λ from L^{1}(G) to C. By the duality of L^{1}(G) and L^{∞}(G), such homomorphisms take the form λ : f ↦ ∫_{G} f(x)\overline{χ(x)} dx for some χ ∈ L^{∞}(G). Using the homomorphism property and approximations to the identity we can show that

λ ∘ Trans_{y} = \overline{χ(y)}λ;

since translations are continuous in L^{1}(G) we conclude that χ is continuous. Also, the identity also reveals that χ is multiplicative: χ(x + y) = χ(x)χ(y). Since χ is also in L^{∞}(G) and non-trivial, we conclude that |χ| = 1. Thus χ is a continuous multiplicative map from G to S^{1}, otherwise known as a multiplicative character. Again, we can write χ(x) = e(ξ · x), where ξ : G → R/Z is a continuous homomorphism from G to R/Z, otherwise known as a additive character or frequency.

Let Ĝ be the collection of additive characters; this is an abelian group. We can define the Fourier transform f̂: Ĝ → C for any f ∈ L^{1}(G) by

f̂(ξ) := ∫_{G} f(x)e(−ξ · x) dx.

Thus each frequency ξ generates a linear functional on L^{1}(G), i.e. we have an embedding of Ĝ in L^{1}(G)^{∗}. We give Ĝ the topology induced by the weak-* topology on L^{1}(G); this is easily verified to make Ĝ a locally compact abelian group. By the preceding discussion, f̂ is essentially the Gelfand transform of f in the B^{∗}-algebra L^{1}(G).

We let A(Ĝ) := {f̂ : f ∈ L^{1}(G)} (this is known as the Wiener algebra of Ĝ.) One easily verifies that { \atop f ∗ g} = f̂ĝ, and so A(Ĝ) becomes a B^{∗}-algebra with pointwise product (rather than convolution) as the multiplication operation. It is also translation-invariant. There is an analogue of the Riemann-Lebesgue lemma, which asserts that A(Ĝ) ⊂ C_{0}(Ĝ), where C_{0}(Ĝ) is the space of continuous functions which go to zero at infinity. As A(Ĝ) is also closed under conjugation and separates points, the Stone-Weierstrass theorem then shows that A(Ĝ) is in fact dense in C_{0}(Ĝ) in the uniform topology. This makes A(Ĝ) a useful class of “test functions” to verify a variety of Fourier-analytic identities.

Now we move towards the all-important Fourier inversion formula. Let M(Ĝ) be the space of finite Radon measures on Ĝ. Given such a measure ν, one can define its inverse Fourier transform F^{∗}ν ∈ C(G) by

F^{∗}ν(x) := ∫Ĝ e(ξ · x) dν(ξ).

We let B(G) denote the space of all such inverse Fourier transforms. One easily verifies that this is a translation-invariant sub-algebra of C(G). From Fubini’s theorem we have the duality relationship

∫_{G} f\overline{F^{∗}ν(x)} dx = ∫Ĝ f̂(ξ)\overline{dν(ξ)}

for all f ∈ L^{1}(G) and ν ∈ M(Ĝ).

So far we have not shown that Ĝ is large in any sense. One convenient way to obtain this largeness is to show that B(G) is large. A key tool for achieving this is

Theorem 2.1 (Bochner’s theorem). Let f ∈ C(G) be positive semi-definite, in the sense that we have ⟨f ∗ μ, μ⟩ ≥ 0 for any finitely supported complex measure μ. Then f ∈ B(G), and furthermore we have f = F^{∗}ν for a non-negative measure ν.

We remark that the converse is easily established: if ν is a non-negative finite Radon measure on Ĝ, then F^{∗}f is positive semi-definite.

Proof Let f be positive semi-definite. It is easy to see that f(x) = \overline{f(−x)} and |f(x)| ≤ f(0) for all x; we can then normalise f(0) = 1.

It is not hard to use the hypothesis and limiting arguments to show that ⟨f∗g, g⟩ ≥ 0 for all simple functions g of finite measure support, and thence also for all g ∈ L^{1}(G). This implies that the inner product ⟨g, h⟩_{f} := ⟨f ∗ g, h⟩ is positive semi-definite, and thus by the Cauchy-Schwarz inequality

|⟨g, h⟩_{f}| ≤ |⟨g, g⟩_{f}|^{1/2}|⟨h, h⟩_{f}|^{1/2}.

Letting h be an approximation to the identity, and taking limits, using the fact that f is continuous and equals 1 near the origin, one soon concludes that

|f ∗ g(0)| ≤ |f ∗ g ∗ g̃(0)|^{1/2}

where g̃(x) := \overline{g(−x)}. We can iterate this repeatedly and obtain

|f ∗ g(0)| ≤ |(T_{g}T_{g}^{∗})^{2^{n}}f(0)|^{1/2^{n+1}}
≤ ∥(T_{g}T_{g}^{∗})^{2^{n}}∥_{L^{∞}(G)→L^{∞}(G)}^{1/2^{n+1}},
= ∥(T_{g}T_{g}^{∗})^{2^{n}}∥_{L^{1}(G)→L^{1}(G)}^{1/2^{n+1}},

where T_{g} is the operation of convolution by g. Taking limits as n → ∞ we can thus bound |f ∗ g(0)| by the spectral radius ρ(T_{g}). But Gelfand theory tells us that

ρ(T_{g}) ≤ ∥ĝ∥_{L^{∞}(Ĝ)}.

(Quick sketch of proof: observe that g−z is invertible (hence holomorphic) in L^{1}(G) if |z| > ∥ĝ∥_{L^{∞}(Ĝ)} (otherwise the range of g − z is a proper ideal, hence contained in a maximal ideal, contradiction) and Cauchy’s integral formula outside of a circle then quickly shows that

∥(ff^{∗})^{n}∥_{L^{1}(G)}/∥ĝ∥_{L^{∞}(Ĝ)}^{2n} → 0 as n → ∞

and the claim follows. The reverse inequality is also true.)

To summarise so far, we have shown that

|f ∗ g(0)| ≤ ∥ĝ∥_{L^{∞}(Ĝ)}

for all g ∈ L^{1}(G). Thus the map ĝ ↦ f ∗ g(0) is a bounded linear functional with norm at most 1 on A(Ĝ), and hence extends by density to C(Ĝ). Applying the Riesz representation theorem, we obtain a finite Radon measure ν on Ĝ with total mass one

f ∗ g(0) = ∫Ĝ ĝ dν

for all g ∈ L^{1}(G). The right-hand side is also equal to ⟨g, F^{∗}\overline{ν}⟩, and so by duality we see that f is (up to some harmless conjugations) the inverse Fourier transform of a measure of total mass 1. Since f(0) = 1, we also see that this measure has to be non-negative as required.

One easily verifies that for any f ∈ L^{2}(G), the function f ∗ f̃ is positive definite, indeed ⟨f ∗ f̃∗ μ, μ⟩ = ∥f ∗ μ∥_{L^{2}(G)}^{2} ≥ 0. By Bochner’s theorem we conclude that f ∗ f̃ ∈ B(G). From Young’s inequality we thus also see that if f ∈ L^{1}(G) ∩ L^{2}(G) then f ∗ f̃ ∈ L^{1}(G) ∩ B(G). From this and translation invariance, we obtain a large class of functions in L^{1}(G) ∩ B(G). The significance of this is that we can establish a preliminary inversion formula in this class:

Proposition 2.2 (Preliminary inversion theorem). There exists a Haar measure dξ on Γ̂ such that whenever f ∈ L^{1}(G) ∩ B(G), then f̂ ∈ L^{1}(Ĝ) and

f(x) = ∫Ĝ f̂(ξ)e(ξ · x) dξ.

Proof Since f ∈ B(G), there exists ν_{f} ∈ M(Ĝ) such that f = F^{∗}ν_{f}. Observe that if f, g ∈ L^{1}(G) ∩ B(G) and h ∈ L^{1}(G), then

∫Ĝ f̂ĥ dν_{g} = ∫Ĝ { \atop f ∗ h} dν_{g} = f ∗ h ∗ Fν_{g}(0) = f ∗ g ∗ h(0).

By symmetry of convolution we thus have

∫Ĝ f̂ĥ dν_{g} = ∫Ĝ ĝĥ dν_{f}

for all ĥ ∈ A(Ĝ). Since A(Ĝ) is dense in C(Ĝ), we conclude from the Riesz representation theorem that

f̂dν_{g} = ĝdν_{f}.

To put this another way, the quantity dν_{f}/f̂ is independent of f on any region on which the quotient is well-defined (i.e. f̂ is non-zero). Given any ξ ∈ Ĝ, one can engineer an f in L^{1}(G) ∩ B(G) whose Fourier transform does not vanish near ξ by taking an expression of the form f = h ∗ h̃ for some approximation to the identity h, by the previous discussion; we can then glue all the dν_{f}/f̂ measures together to create a Radon measure dξ such that dν_{f} = f̂ dξ for all f ∈ L^{1}(G) ∩ B(G). By translating ν_{f} (which modulates f, which translates f̂) we see that dξ is translationinvariant and is thus a Haar measure. Since f = F^{∗}ν_{f}, the claim now follows.

One consequence of the inversion theorem is that

f(0) = ∫Ĝ f̂(ξ) dξ

whenever f ∈ L^{1}(G) ∩ B(G), which implies also that

f ∗ g(0) = ∫Ĝ f̂(ξ)ĝ(ξ) dξ

for f, g ∈ L^{1}(G) ∩ B(G). This easily implies the Plancherel and Parseval identities in this class. Using approximations to the identity, one can show that L^{1}(G)∩B(G) is dense in L^{2}(G), and so we obtain Plancherel’s theorem, namely that there is a unique unitary extension of the Fourier transform to L^{2}(G).

Given that Haar measure is defined up to a multiplicative constant, the only remaining question is to determine what this constant is. But by testing against a single explicit non-trivial function, one can recover this constant. Some standard examples:

Example 2.3. Let G = Z. Then it is easy to see that the only additive characters x ↦ ξ · x from Z to R/Z can be parameterised by a frequency ξ ∈ R/Z, given by the formula ξ · x = xξ. Thus Ĝ ≡ R/Z. Testing against f(x) := 1_{x=0} (so f̂(ξ) = 1 we see that the Fourier measure dξ on Ĝ is just Lebesgue measure.

Example 2.4. Let G = Z/NZ. Then the additive characters x ↦ ξ ·x from Z/NZ to R/Z lift to one from Z to R/Z so are parameterised by ξ ∈ R/Z as before, but also we must have Nξ = 0 in order to be able to descend back to Z/NZ. Thus Ĝ is equivalent to the N^{th} roots of R/Z, which can also be identified with Z/NZ (if we change the pairing (x, ξ) ↦ ξ · x to ξ · x = ξx/N). Thus Ĝ ≡ Z/NZ. Testing against f(x) := 1_{x=0} (so f̂(ξ) = 1 we see that the Fourier measure dξ on Ĝ is just counting measure.

Example 2.5. Let G = R. Then it is easy to see that the only additive characters x ↦ ξ · x from R to R/Z can be parameterised by a frequency ξ ∈ R, and given by the formula ξ · x = ξx mod 1; this can be seen by first using the continuity to observe that for x close enough to zero, ξ · x lies in (say) a 0.1 neighbourhood of the origin in R/Z, and then one can easily show using the homomorphism property and continuity that ξ · x is linear near the origin, then one can extend to all of R using the homomorphism property again. Thus Ĝ ≡ R. Testing against the function f(x) := e^{−πx^{2}} (say) one sees that the required Fourier measure dξ on Ĝ is just Lebesgue measure.

Example 2.6. Let G = R/Z. The additive characters x ↦ ξ · x from R/Z to R/Z descend from characters from R to R/Z, but in order for the descent to work properly the frequency ξ must be an integer. Thus Ĝ = Z. Testing against f(x) := 1 (so f̂(ξ) = 1_{ξ=0}) we see that dξ is just counting measure.

Observe that each x ∈ G induces an additive character on Ĝ by the map x : ξ ↦ ξ·x. This allows one to canonically embed G in ˆ Ĝ; this map is easily seen to be an injective homomorphism and homeomorphism. We have two Plancherel theorems on Ĝ, one with frequencies in ˆ Ĝ and one with frequencies in G. The only way these can be compatible is if G has full measure in ˆ Ĝ and the Fourier measure of ˆ Ĝ is dx. In fact one can show that G is equal to all of ˆ Ĝ, by observing that (by the full measure property) G is dense, while also being locally compact. This equivalence

G ≡ ˆ Ĝ is sometimes referred to as Pontryagin duality.

3. The Walsh ring

For most applications in real-variable harmonic analysis, the general theory of Fourier analysis on LCA groups can be specialised to the classical cases of the real line, torus, integers, cyclic groups, and products thereof. There are however a number of other interesting groups (or rings) on which this theory is useful. One is Fourier analysis on the ring A_{Q} of adeles, which is of significant importance in algebraic number theory but which will not be discussed here. Another is to multiplicative abelian groups such as R^{+} (which leads to the Mellin transform) or (Z/NZ)^{∗} (which leads to the theory of characters in number theory). The other is the Walsh ring or Cantor-Walsh ring^{1} W_{p}, which is a dyadic variant of the real number ring R and which serves as a useful model for harmonic analysis on the real line (among other things, it manages to avoid the perennial presence of Schwartz tails which plague the analysis on R.

To define the Walsh ring, we need an prime p; in many applications we set p = 2 (giving the dyadic Walsh ring) or p = 3 (giving the ternary Walsh ring). We let F_{p} be the field of p elements (identified with Z/pZ and with {0, …, p−1} in the usual manner), and let F_{p}(t) be the ring of Laurent polynomials in one indeterminate t, thus a typical non-zero element of F_{p}(t) is of the form

x = ∑_{n=A}^{B} a_{n}t^{n}

for some finite integers A ≤ B and coefficients a_{n} ∈ F_{p} with a_{B} ≠ 0. We can also represent this element more suggestively in “base p notation” as

x = a_{B}a_{B−1} … a_{0}.a_{−1} … a_{A}.

Indeed, if we identify an element ∑_{n=A}^{B} a_{n}t^{n} of F_{p}(t) with the base p terminating decimal ∑_{n=A}^{B} a_{n}p^{−n} (recall that we identify F_{p} with {0, …, p − 1}), we obtain a ring which resembles the ring of base p terminating decimals in the reals, but where addition and multiplication are performed without the “carry” operation (or in more modern jargon, the cocycle is trivial).

Just as the reals R are the metric completion of the rationals Q, the Walsh ring W_{p} are the metric completion of the Laurent ring F_{p}(t), using the metric d(x, y) := ∥x − y∥_{p} := p^{−B}, where B is the degree of x − y (i.e. the largest power of t which appears; we use the convention that the degree of 0 is −∞). One easily observes that the ring operations are locally uniformly continuous on F_{p}(t) and thus extend in a unique continuous manner to W_{p}. The completion can also be identified with the one-sided infinite series

x = ∑_{n=−∞}^{B} a_{n}t^{n}

over F_{p}; one can also almost identify this ring with the half-line R^{+} by identifying x with ∑_{n=−∞}^{B} a_{n}p^{−n}, but of course the infamous 0.999 … = 1 problem shows that there is a problem with doing so at every element of F_{p}(t). Strictly speaking, one thus has to adjoin an additional element infinitesimally to the left of every non-zero terminating base p decimal in R^{+} before one has a fully accurate representation of the Walsh ring W_{p}, but we will gloss over this annoying technicality; in particular, we shall abuse notation and describe elements of W_{p} using the formula ∑_{n=−∞}^{B} a_{n}p^{−n} rather than the more accurate ∑_{n=−∞}^{B} a_{n}t^{n}. (An alternate approach is to identify x with ∑_{n=−∞}^{B} a_{n}q^{−n} for some q > p, which identifies W_{p} bijectively with a Cantor set, but then the analogy between W_{p} and R^{+} is diminished.) We can pull back Lebesgue measure on R^{+} to create a measure dx on W_{p}, which is easily seen to be a Haar measure.

1This notation is not standard.

The metric d extends of course to the completion W_{p}; it is somewhat related to the usual Euclidean metric on R^{+} by observing that d(x, y) ≥ \frac{1}{2}|x − y|, but it is possible for d(x, y) to much larger than |x − y| (this occurs for instance if x and y are close to but on opposite sides of a terminating decimal). The metric d is in fact better than a metric, it is an ultrametric (or non-archimedean metric), thus

d(x, y) ≤ max(d(x, z), d(z, y)).

This implies that the metric balls are nested. Indeed, the metric balls here are nothing more than the p-dyadic intervals [\frac{j}{p^{n}} , \frac{j+1}{p^{n}}) for n ∈ Z, j ≥ 0 (note that we include the element \frac{j}{p^{n}} + ∑_{m=−∞}^{n−1} \frac{p−1}{p^{n}}, which is infinitesimally to the left of \frac{j+1}{p^{n}}, in this ball).

The space W_{p} is homeomorphic to an unbounded Cantor set, as the identification x ↔ ∑_{n=−∞}^{B} a_{n}q^{−n} shows; in particular, W_{p} is locally compact as well as abelian. Now let’s compute the Pontryagin dual of W_{p}. Let ξ : x ↦ ξ · x be an additive character. Observe that for each integer n, ξ · p^{n} must be a p^{th} root of unity in R/Z, since adding p^{n} to itself p times in W_{p} gives zero (note this is not the same as p × p^{n} in W_{p}!). Thus we can write ξ · p^{n} = a_{−n−1}/p for some a_{−n−1} ∈ F_{p}. By continuity, we see that ξ · p^{n} → 0 as n → +∞, and hence a_{n} = 0 for all sufficiently large n, say n > N. If we then write

ξ̃:= ∑_{n=−∞}^{N} a_{n}p^{−n} ∈ W_{p}

and define the dot product

( ∑_{n=−∞}^{N} a_{n}p^{−n}, ∑_{m=−∞}^{M} b_{m}p^{−m}) := ∑_{n=−M}^{N} a_{n}b_{−1−m}/p ∈ R/Z

then we see that

ξ · x = ξ̃· x

for all x ∈ F_{p}(t), and hence by continuity for all x ∈ W_{p} also. Thus Ŵ_{p} is identifiable with W_{p}, using the dot product · : W_{p} × W_{p} → R/Z described above.

If one lets f := 1_{[0,1)} in W_{p}, one easily checks that f̂ = f, which by Plancherel’s theorem tells us that the Fourier measure dξ is the same as the original measure dx. Note that in sharp contrast to the Fourier theory on R, in W_{p} it is perfectly possible to have a function of compact support whose Fourier transform is also of compact support. This leads to a very pleasant harmonic analysis in W_{p}, which can be regarded as a simplified model of harmonic analysis in R: many of the foundational theorems of the subject are somewhat simpler in this setting while still capturing the main essence of the real-variable theory (a good example arises by comparing the ordinary Hardy-Littlewood maximal function with its Walsh variant, namely the dyadic (or p-adic) maximal function). We will however not pursue this theme in detail here.

4. Exercises

• Q1. (Poisson summation formula for finite abelian groups) Let G be a finite abelian group, and let H be a subgroup of G. Define the orthogonal complement H^{⊥} ⊂ Ĝ of H as H^{⊥} := {ξ ∈ Ĝ : ξ·x = 0 for all x ∈ H}. Show that H^{⊥} is a subgroup of Ĝ, and that Ĝ/H^{⊥} is canonically identifiable with Ĥ. In particular we see that

#G = (#H)(#H^{⊥}).

Show that

ˆ1_{H}(ξ) = \frac{#H}{#G} 1_{H^{⊥}}(ξ)

and conclude the Poisson summation formula

\frac{1}{#H} ∑_{x∈H} f(x) = ∑_{ξ∈H^{⊥}} f̂(ξ)

for all f ∈ L^{2}(G). More generally, show that

\frac{#G}{#H} f̂1_{H}(ξ) = ∑_{η∈H^{⊥}} f̂(ξ + η)

and

\frac{#G}{#H} { \atop f ∗ 1_{H}}(ξ) = 1_{H^{⊥}}(ξ)f̂(ξ)

for all f ∈ L^{2}(G) and ξ ∈ Ĝ (thus “the Fourier transform of restriction is projection”, and vice versa).

• Q2. (Uncertainty principle for finite abelian groups) Let G be a finite abelian group. Show that for any non-zero f ∈ L^{2}(G) we have

#(supp(f))#(supp(f̂)) ≥ #G.

(Hint: use the Plancherel and Hölder inequalities, together with the trivial bound ∥f̂∥_{l^{∞}(Ĝ)} ≤ ∥f∥_{L^{1}(G)}.

• Q3. (Entropy uncertainty principle for finite abelian groups) Let G be a finite abelian group. Establish the Hausdorff-Young inequality

∥f̂∥_{l^{p′} (Ĝ)} ≤ ∥f∥_{L^{p}(G)}

for all 1 ≤ p ≤ 2 and f ∈ L^{p}(G); differentiate this at p = 2 to conclude the entropy uncertainty principle

∫_{x∈G} |f(x)|^{2} log \frac{1}{|f(x)|^{2}} + ∑_{ξ∈Ĝ} |f̂(ξ)|^{2} log \frac{1}{|f̂(ξ)|^{2}} ≥ 0

for all f ∈ L^{2}(G) with ∥f∥_{L^{2}(G)} = 1, using the convention 0 log \frac{1}{0} = 0. Using Jensen’s inequality, give a second proof of the uncertainty principle from Q2.

• Q4. (Adjoints in finite abelian groups) Let G be a finite abelian group, and let ϕ : G → G be an automorphism. Define the adjoint operator ϕ^{∗} : Ĝ → Ĝ by

ϕ^{∗}(ξ) · x := ξ · ϕ(x).

Show that ϕ^{∗} is also an automorphism, and that for any f ∈ L^{2}(G) we have

{ \atop f ∘ ϕ} = f̂∘ (ϕ^{∗})^{−1}.

• Q5. Show that the Pontryagin dual of a compact abelian group is a discrete abelian group, and vice versa.

• Q6. Let W_{p} be a Walsh group. Define the operators Dil_{p^{n}}^{q} for 1 ≤ q ≤ ∞ and n ∈ Z and f ∈ L^{q}(W_{p}) by

Dil_{p^{n}}^{q}f(x) := p^{n/q}f(p^{−n}x).

(Note that Walsh multiplication of x by p^{−n} corresponds with classical multiplication.) Show that Dil_{p^{n}}^{q} is an isometry on L^{q}(W_{p}), and that

{ \atop Dil_{p^{n}}^{q}f} = Dil_{p^{−n}}^{q′} f̂.

• Q7 (Walsh uncertainty principle). Let W_{p} be a Walsh group, f ∈ L^{2}(W_{p}), and n ∈ Z. Show that f̂ is supported in the interval [0, p^{n}) if and only if f is constant on every ball of radius p^{−n}. We remark that the Walsh-Fourier projection to the interval [0, p^{n}) is highly analogous to the Littlewood-Paley projection ψ_{≤n}, and enjoys essentially the same theory (in fact, the Walsh theory is cleaner and simpler, and is also closely related to martingale theory).

• Q8 (Tiles). Define a tile to be a set of the form P = I × w ⊂ W_{p} × W_{p}, where I, w are balls with |I||w| = 1. Show that the space V_{P} := {f ∈ L^{2}(I) : f̂ ∈ L^{2}(w)} is one-dimensional, and that V_{P} and V_{Q} are orthogonal whenever P, Q are disjoint tiles. If a set Ω ⊂ W_{p} × W_{p} can be partitioned Ω = P_{1} ∪ … ∪ P_{n} into finitely many disjoint tiles, show that the vector space V_{Ω} := V_{P_{1}} + … + V_{P_{n}} is independent of the choice of partition.

Department of Mathematics, UCLA, Los Angeles CA 90095-1555

E-mail address: tao@math.ucla.edu