254B, Notes 2: Cayley graphs and Kazhdan’s property (T)

6 December, 2011 in 254B - expansion in groups, math.CA, math.GR, math.RT, math.SP | Tags: Cayley graphs, lattices, Mautner phenomenon, property T, Schreier graphs, special linear group, spectral gap

In the previous set of notes we introduced the notion of expansion in arbitrary ${k}$ -regular graphs. For the rest of the course, we will now focus attention primarily to a special type of ${k}$ -regular graph, namely a Cayley graph.

Definition 1 (Cayley graph) Let ${G = (G,\cdot)}$ be a group, and let ${S}$ be a finite subset of ${G}$ . We assume that ${S}$ is symmetric (thus ${s^{-1} \in S}$ whenever ${s \in S}$ ) and does not contain the identity ${1}$ (this is to avoid loops). Then the (right-invariant) Cayley graph ${Cay(G,S)}$ is defined to be the graph with vertex set ${G}$ and edge set ${\{ \{sx,x\}: x \in G, s \in S \}}$ , thus each vertex ${x \in G}$ is connected to the ${|S|}$ elements ${sx}$ for ${s \in S}$ , and so ${Cay(G,S)}$ is a ${|S|}$ -regular graph.

Example 1 The graph in Exercise 3 of Notes 1 is the Cayley graph on ${{\bf Z}/N{\bf Z}}$ with generators ${S = \{-1,+1\}}$ .

Remark 1 We call the above Cayley graphs right-invariant because every right translation ${x\mapsto xg}$ on ${G}$ is a graph automorphism of ${Cay(G,S)}$ . This group of automorphisms acts transitively on the vertex set of the Cayley graph. One can thus view a Cayley graph as a homogeneous space of ${G}$ , as it “looks the same” from every vertex. One could of course also consider left-invariant Cayley graphs, in which ${x}$ is connected to ${xs}$ rather than ${sx}$ . However, the two such graphs are isomorphic using the inverse map ${x \mapsto x^{-1}}$ , so we may without loss of generality restrict our attention throughout to left Cayley graphs.

Remark 2 For minor technical reasons, it will be convenient later on to allow ${S}$ to contain the identity and to come with multiplicity (i.e. it will be a multiset rather than a set). If one does so, of course, the resulting Cayley graph will now contain some loops and multiple edges.

For the purposes of building expander families, we would of course want the underlying group ${G}$ to be finite. However, it will be convenient at various times to “lift” a finite Cayley graph up to an infinite one, and so we permit ${G}$ to be infinite in our definition of a Cayley graph.

We will also sometimes consider a generalisation of a Cayley graph, known as a Schreier graph:

Definition 2 (Schreier graph) Let ${G}$ be a finite group that acts (on the left) on a space ${X}$ , thus there is a map ${(g,x) \mapsto gx}$ from ${G \times X}$ to ${X}$ such that ${1x = x}$ and ${(gh)x = g(hx)}$ for all ${g,h \in G}$ and ${x \in X}$ . Let ${S}$ be a symmetric subset of ${G}$ which acts freely on ${X}$ in the sense that ${sx \neq x}$ for all ${s \in S}$ and ${x \in X}$ , and ${sx \neq s'x}$ for all distinct ${s,s' \in S}$ and ${x \in X}$ . Then the Schreier graph ${Sch(X,S)}$ is defined to be the graph with vertex set ${X}$ and edge set ${\{ \{sx,x\}: x \in X, s \in S \}}$ .

Example 2 Every Cayley graph ${Cay(G,S)}$ is also a Schreier graph ${Sch(G,S)}$ , using the obvious left-action of ${G}$ on itself. The ${k}$ -regular graphs formed from ${l}$ permutations ${\pi_1,\ldots,\pi_l \in S_n}$ that were studied in the previous set of notes is also a Schreier graph provided that ${\pi_i(v) \neq v, \pi_i^{-1}(v), \pi_j(v)}$ for all distinct ${1 \leq i,j \leq l}$ , with the underlying group being the permutation group ${S_n}$ (which acts on the vertex set ${X = \{1,\ldots,n\}}$ in the obvious manner), and ${S := \{\pi_1,\ldots,\pi_l,\pi_1^{-1},\ldots,\pi_l^{-1}\}}$ .

Exercise 1 If ${k}$ is an even integer, show that every ${k}$ -regular graph is a Schreier graph involving a set ${S}$ of generators of cardinality ${k/2}$ . (Hint: first show that every ${k}$ -regular graph can be decomposed into ${k/2}$ unions of cycles, each of which partition the vertex set, then use the previous example.

We return now to Cayley graphs. It is easy to characterise qualitative expansion properties of Cayley graphs:

Exercise 2 (Qualitative expansion) Let ${Cay(G,S)}$ be a finite Cayley graph.

(i) Show that ${Cay(G,S)}$ is a one-sided ${\epsilon}$ -expander for ${G}$ for some ${\epsilon>0}$ if and only if ${S}$ generates ${G}$ .

(ii) Show that ${Cay(G,S)}$ is a two-sided ${\epsilon}$ -expander for ${G}$ for some ${\epsilon>0}$ if and only if ${S}$ generates ${G}$ , and furthermore ${S}$ intersects each index ${2}$ subgroup of ${G}$ .

We will however be interested in more quantitative expansion properties, in which the expansion constant ${\epsilon}$ is independent of the size of the Cayley graph, so that one can construct non-trivial expander families ${Cay(G_n,S_n)}$ of Cayley graphs.

One can analyse the expansion of Cayley graphs in a number of ways. For instance, by taking the edge expansion viewpoint, one can study Cayley graphs combinatorially, using the product set operation

$\displaystyle A \cdot B := \{ab: a \in A, b \in B \}$

of subsets of ${G}$ .

Exercise 3 (Combinatorial description of expansion) Let ${Cay(G_n,S_n)}$ be a family of finite ${k}$ -regular Cayley graphs. Show that ${Cay(G_n,S_n)}$ is a one-sided expander family if and only if there is a constant ${c>0}$ independent of ${n}$ such that ${|E_n \cup E_n S_n| \geq (1+c) |E_n|}$ for all sufficiently large ${n}$ and all subsets ${E_n}$ of ${G_n}$ with ${|E_n| \leq |G_n|/2}$ .

One can also give a combinatorial description of two-sided expansion, but it is more complicated and we will not use it here.

Exercise 4 (Abelian groups do not expand) Let ${Cay(G_n,S_n)}$ be a family of finite ${k}$ -regular Cayley graphs, with the ${G_n}$ all abelian, and the ${S_n}$ generating ${G_n}$ . Show that ${Cay(G_n,S_n)}$ are a one-sided expander family if and only if the Cayley graphs have bounded cardinality (i.e. ${\sup_n |G_n| < \infty}$ ). (Hint: assume for contradiction that ${Cay(G_n,S_n)}$ is a one-sided expander family with ${|G_n| \rightarrow \infty}$ , and show by two different arguments that ${\sup_n |S_n^m|}$ grows at least exponentially in ${m}$ and also at most polynomially in ${m}$ , giving the desired contradiction.)

The left-invariant nature of Cayley graphs also suggests that such graphs can be profitably analysed using some sort of Fourier analysis; as the underlying symmetry group is not necessarily abelian, one should use the Fourier analysis of non-abelian groups, which is better known as (unitary) representation theory. The Fourier-analytic nature of Cayley graphs can be highlighted by recalling the operation of convolution of two functions ${f, g \in \ell^2(G)}$ , defined by the formula

$\displaystyle f * g(x) := \sum_{y \in G} f(y) g(y^{-1} x) = \sum_{y \in G} f(x y^{-1}) g(y).$

This convolution operation is bilinear and associative (at least when one imposes a suitable decay condition on the functions, such as compact support), but is not commutative unless ${G}$ is abelian. (If one is more algebraically minded, one can also identify ${\ell^2(G)}$ (when ${G}$ is finite, at least) with the group algebra ${{\bf C} G}$ , in which case convolution is simply the multiplication operation in this algebra.) The adjacency operator ${A}$ on a Cayley graph ${Cay(G,S)}$ can then be viewed as a convolution

$\displaystyle Af = |S| \mu * f,$

where ${\mu}$ is the probability density

$\displaystyle \mu := \frac{1}{|S|} \sum_{s \in S} \delta_s \ \ \ \ \ (1)$

where ${\delta_s}$ is the Kronecker delta function on ${s}$ . Using the spectral definition of expansion, we thus see that ${Cay(G,S)}$ is a one-sided expander if and only if

$\displaystyle \langle f, \mu*f \rangle \leq (1-\epsilon) \|f\|_{\ell^2(G)} \ \ \ \ \ (2)$

whenever ${f \in \ell^2(G)}$ is orthogonal to the constant function ${1}$ , and is a two-sided expander if

$\displaystyle \| \mu*f \|_{\ell^2(G)} \leq (1-\epsilon) \|f\|_{\ell^2(G)} \ \ \ \ \ (3)$

whenever ${f \in \ell^2(G)}$ is orthogonal to the constant function ${1}$ .

We remark that the above spectral definition of expansion can be easily extended to symmetric sets ${S}$ which contain the identity or have multiplicity (i.e. are multisets). (We retain symmetry, though, in order to keep the operation of convolution by ${\mu}$ self-adjoint.) In particular, one can say (with some slight abuse of notation) that a set of elements ${s_1,\ldots,s_l}$ of ${G}$ (possibly with repetition, and possibly with some elements equalling the identity) generates a one-sided or two-sided ${\epsilon}$ -expander if the associated symmetric probability density

$\displaystyle \mu := \frac{1}{2l} \sum_{i=1}^l \delta_{s_i} + \delta_{s_i^{-1}}$

obeys either (2) or (3).

We saw in the last set of notes that expansion can be characterised in terms of random walks. One can of course specialise this characterisation to the Cayley graph case:

Exercise 5 (Random walk description of expansion) Let ${Cay(G_n,S_n)}$ be a family of finite ${k}$ -regular Cayley graphs, and let ${\mu_n}$ be the associated probability density functions. Let ${A > 1/2}$ be a constant.

Show that the ${Cay(G_n,S_n)}$ are a two-sided expander family if and only if there exists a ${C>0}$ such that for all sufficiently large ${n}$ , one has ${\| \mu_n^{*m} - \frac{1}{|G_n|} \|_{\ell^2(G_n)} \leq \frac{1}{|G_n|^A}}$ for some ${m \leq C \log |G_n|}$ , where ${\mu_n^{*m} := \mu_n * \ldots * \mu_n}$ denotes the convolution of ${m}$ copies of ${\mu_n}$ .

Show that the ${Cay(G_n,S_n)}$ are a one-sided expander family if and only if there exists a ${C>0}$ such that for all sufficiently large ${n}$ , one has ${\| (\frac{1}{2} \delta_1 + \frac{1}{2} \mu_n)^{*m} - \frac{1}{|G_n|} \|_{\ell^2(G_n)} \leq \frac{1}{|G_n|^A}}$ for some ${m \leq C \log |G_n|}$ .

In this set of notes, we will connect expansion of Cayley graphs to an important property of certain infinite groups, known as Kazhdan’s property (T) (or property (T) for short). In 1973, Margulis exploited this property to create the first known explicit and deterministic examples of expanding Cayley graphs. As it turns out, property (T) is somewhat overpowered for this purpose; in particular, we now know that there are many families of Cayley graphs for which the associated infinite group does not obey property (T) (or weaker variants of this property, such as property ${\tau}$ ). In later notes we will therefore turn to other methods of creating Cayley graphs that do not rely on property (T). Nevertheless, property (T) is of substantial intrinsic interest, and also has many connections to other parts of mathematics than the theory of expander graphs, so it is worth spending some time to discuss it here.

The material here is based in part on this recent text on property (T) by Bekka, de la Harpe, and Valette (available online here).

— 1. Kazhdan’s property (T) —

Kazhdan’s property (T) is a representation-theoretic property of groups. Although we will primarily be interested in finite groups (such as ${SL_d({\bf Z}/p{\bf Z})}$ ), or at least discrete, finitely generated groups (such as ${SL_d({\bf Z})}$ ), it will be convenient to work in the more general category of locally compact groups which includes discrete finitely generated groups, but also Lie groups (such as ${SL_d({\bf R})}$ ) as examples. (Locally compact groups were studied extensively in last quarter’s course, but we will not need the theory of those groups from that course here.) For minor technical reasons we will restrict attention to locally compact groups ${G}$ that are Hausdorff, second countable, and compactly generated (so that there is a compact set ${S}$ that generates ${G}$ as a group, as is for instance the case for discrete finitely generated groups). We shall therefore abuse notation and abbreviate “locally compact second countable Hausdorff compactly generated group” as “locally compact group”. One can extend the study of property (T) to more general classes of groups than these, but this class will be sufficient for our applications while avoiding some technical subtleties that are not relevant for our purposes.

We will focus on a particular type of representation of locally compact groups, namely a unitary representation.

Definition 3 (Unitary representation) Let ${G}$ be a locally compact group. A unitary representation (or representation, for short) of ${G}$ is a (complex) separable Hilbert space ${H}$ (possibly infinite dimensional), together with a homomorphism ${\rho: G \rightarrow U(H)}$ from ${G}$ to the group ${U(H)}$ of unitary transformations on ${H}$ . Furthermore, we require ${\rho}$ to be continuous, where we give ${U(H)}$ the strong operator topology. We often abuse notation and refer to ${\rho}$ (rather than the pair ${(\rho,H)}$ ) as the representation of ${G}$ .

Two unitary representations ${\rho: G \rightarrow U(H)}$ , ${\rho': G \rightarrow U(H')}$ are isomorphic if there is a Hilbert space isomorphism ${\phi: H \rightarrow H'}$ such that ${\rho'(g) \circ \phi = \phi \circ \rho(g)}$ for all ${g \in G}$ . When one has such an isomorphism, we write ${\rho \equiv \rho'}$ .

Note that if ${G}$ is a discrete group, then the continuity hypothesis is automatic and can be omitted. One could easily turn the space of unitary representations of a fixed group ${G}$ into a category by defining the notion of a morphism between two unitary representations that generalises the notion of an isomorphism given above (basically by replacing “Hilbert space isomorphism” with “Hilbert space isometry”), but we will not need to do so here. One could also consider inseparable Hilbert space representations, but for minor technical reasons it will be convenient to restrict attention to the separable case. (Note that ${G}$ , being second countable, is separable, and so any orbit ${\{ gv: g \in G \}}$ of a vector ${v}$ in a Hilbert space is automatically contained in a separable subspace. As such, one can usually restrict without loss of generality to separable Hilbert spaces in applications.)

Example 3 (Trivial representation) Any locally compact group ${G}$ acts trivially on any Hilbert space ${H}$ by defining ${\rho(g)}$ to be the identity on ${H}$ for all ${g \in G}$ .

Example 4 (Regular representation) If ${G}$ is a discrete group, then we have the (left) regular representation ${\tau: G \rightarrow U(\ell^2(G))}$ of ${G}$ , in which the Hilbert space is ${\ell^2(G)}$ , and the action is given by the formula
$\displaystyle \tau(g) f(x) := f(g^{-1} x) = \delta_g * f(x)$

for ${g \in G}$ and ${x \in G}$ . (Note that the ${g^{-1}}$ here is needed to make ${\tau}$ a homomorphism.) This is easily verified to be a unitary representation. One can also consider the right-regular representation that takes ${f(x)}$ to ${f(xg)}$ , but this is easily seen to be isomorphic to the left-regular representation and will not be needed here.

More generally, if ${G}$ is a locally compact group equipped with a left-invariant Haar measure ${\mu}$ , one can define the (left) regular representation ${\tau}$ on ${L^2(G,d\mu)}$ by setting ${\tau(g) f(x) := f(g^{-1} x)}$ for all ${f \in L^2(G,d\mu)}$ . (Note that ${L^2(G,d\mu)}$ will be separable because we are assuming ${G}$ to be second countable.) For a review of the theory of Haar measure (and in particular, a proof that any locally compact group has a Haar measure, unique up to scalar multiplication), see this previous blog post of mine.

Example 5 (Quasiregular representation) If ${(X,\mu)}$ is a measure space that ${G}$ acts on in a transitive measure-preserving fashion, then we have the (left) quasiregular representation ${\tau_{X}: G \rightarrow U(L^2(X,\mu))}$ , in which the Hilbert spac is ${L^2(X,\mu)}$ , and the action is given by the formula
$\displaystyle \tau_{X}(g) f(x) := f(g^{-1} x)$

for ${g \in G}$ and ${x \in X}$ . Of course, the regular representation can be viewed as a special case of a quasiregular representation, as can the one-dimensional trivial representation.

Example 6 (Direct sum) If ${\rho_1: G \rightarrow U(H_1)}$ and ${\rho_2: G \rightarrow U(H_2)}$ are unitary representations of a locally compact group ${G}$ , then their direct sum ${\rho_1 \oplus \rho_2: G \rightarrow U(H_1 \oplus H_2)}$ is also a unitary representation, where ${H_1 \oplus H_2}$ is the Hilbert space of all formal sums ${v_1 \oplus v_2}$ with ${v_1 \in H_1}$ and ${v_2 \in H_2}$ with the inner product
$\displaystyle \langle v_1 \oplus v_2, w_1 \oplus w_2 \rangle_{H_1 \oplus H_2} := \langle v_1,w_1 \rangle_{H_1} + \langle v_2,w_2\rangle_{H_2}$

and the representation ${\rho_1 \oplus \rho_2}$ is given by the formula
$\displaystyle (\rho_1 \oplus \rho_2)(g) (v_1 \oplus v_2) := (\rho_1(g) v_1) \oplus (\rho_2(g) v_2).$

One can also form the direct sum of finitely many or even countably many unitary representations in a similar manner; we leave the details to the reader. (There is also a construction to combine uncountably many such representations, known as the direct integral, but we will not need it here.)

Example 7 (Subrepresentation) If ${\rho: G \rightarrow U(H)}$ is a unitary representation of a locally compact group ${G}$ , and ${H'}$ is a closed subspace of ${H}$ which is ${G}$ -invariant (thus ${\rho(g) H' \subset H'}$ for all ${g \in G}$ ), then we can form the restriction ${\rho\downharpoonright_{H'}: G \rightarrow U(H')}$ of ${\rho}$ to ${H'}$ , defined by setting ${\rho\downharpoonright_{H'}(g) v := \rho(g) v}$ for all ${g \in G}$ and ${v \in H'}$ . This is easily seen to also be a unitary representation, and is known as a subrepresentation of ${\rho}$ . By unitarity, we see that the orthogonal complement ${(H')^\perp}$ of ${H'}$ in ${H}$ is an invariant space, leading to the complementary subrepresentation ${\rho\downharpoonright_{(H')^\perp}}$ . One easily verifies the isomorphism
$\displaystyle \rho \equiv \rho\downharpoonright_{H'} \oplus \rho\downharpoonright_{(H')^\perp}.$

Example 8 (Invariant vectors) If ${\rho: G \rightarrow U(H)}$ is a unitary representation of a locally compact group ${G}$ , then the space ${H^G := \{ v \in H: \rho(g) v = v \hbox{ for all } g \in G \}}$ of ${G}$ -invariant vectors in ${H}$ is a closed invariant subspace of ${H}$ . By the preceding example, we thus have the decomposition
$\displaystyle \rho \equiv \rho\downharpoonright_{H^G} \oplus \rho\downharpoonright_{(H^G)^\perp}$

into a trivial representation ${\rho\downharpoonright_{H^G}}$ , and a representation ${\rho\downharpoonright_{(H^G)^\perp}}$ with no non-trivial invariant vectors. (Indeed, this is the only such decomposition up to isomorphism; we leave this as an exercise to the reader.) For instance, if ${G}$ is a finite group and we consider the regular representation ${\tau}$ (so ${H = \ell^2(G)}$ ), then ${H^G}$ is the one-dimensional space of constants ${{\bf C}}$ , while ${(H^G)^\perp}$ is the space ${\ell^2(G)_0}$ of functions of mean zero, so we have the decomposition
$\displaystyle \tau \equiv {\bf C} \oplus \tau\downharpoonright_{\ell^2(G)_0}.$

Note that if ${G}$ is an infinite discrete group, then there are already no non-trivial invariant vectors in ${\ell^2(G)}$ (why?), so the decomposition in this case is trivial:
$\displaystyle \tau \equiv 0 \oplus \tau\downharpoonright_{\ell^2(G)}.$

We now make a key definition of a Kazhdan constant, which is analogous to the expansion constant of a Cayley graph.

Definition 4 (Kazhdan constant) Let ${\rho: G \rightarrow U(H)}$ be a unitary representation of a locally compact group ${G}$ , and let ${S}$ be a compact subset of ${G}$ . The Kazhdan constant ${Kaz(G,S,\rho)}$ of ${S}$ and ${\rho}$ is then the supremum of all the constants ${\epsilon \geq 0}$ for which one has the bound
$\displaystyle \sup_{s \in S} \| \rho(s) v - v \|_H \geq \epsilon \|v\|_H$

for all ${v \in H}$ . Thus, for instance, ${Kaz(G,S,\rho)}$ vanishes whenever the representation ${\rho}$ contains non-trivial invariant vectors. The Kazhdan constant ${Kaz(G,S)}$ of ${S}$ is defined as
$\displaystyle Kaz(G,S) := \inf_\rho Kaz(G,S,\rho),$

where ${\rho}$ ranges over all unitary representations of ${G}$ with no non-trivial invariant vectors. A group ${G}$ is said to have Kazhdan property (T) if one has ${Kaz(G,S) > 0}$ for at least one compact set ${S}$ .

Thus, if ${G}$ has Kazhdan property (T), then one can find at least one compact set ${S}$ and some ${\epsilon>0}$ with the property that for every representation unitary ${\rho: G \rightarrow U(H)}$ with no non-trivial invariant vectors, and every ${v \in H}$ , one can find ${s \in S}$ such that ${\| \rho(s) v - v \|_H \geq \epsilon \|v\|_H}$ . Thus, we have a dichotomy: either a representation contains invariant vectors, or every vector in the representation is moved by a non-trivial amount by some “small” element of ${G}$ .

Example 9 Later on in these notes, we will show that ${SL_d({\bf Z})}$ and ${SL_d({\bf R})}$ have property (T) if and only if ${d \geq 3}$ . We will also see that a free non-abelian group ${F_k}$ on ${k}$ generators will never have property (T), and also no finitely generated infinite abelian group will have property (T).

Exercise 6 Show that every finite group ${G}$ has property (T). (Hint: first show that every vector ${v}$ in a unitary representation is contained in a subrepresentation of dimension at most ${|G|}$ , and that all the unitary maps ${\rho(g)}$ have order at most ${|G|}$ .) Later on, we shall establish the stronger statement that every compact group has property (T).

We record some basic properties of the Kazhdan constants:

Exercise 7 Let ${G}$ be a locally compact group, let ${\rho: G \rightarrow U(H)}$ be a representation, and let ${S, S'}$ be compact subsets of ${G}$ .

(i) If ${S \subset S'}$ , then ${Kaz(G,S,\rho) \leq Kaz(G,S',\rho)}$ and ${Kaz(G,S) \leq Kaz(G,S')}$ .

(ii) One has ${Kaz(G,S,\rho) = Kaz(G,S^{-1},\rho) = Kaz(G,S \cup S^{-1},\rho)}$ and ${Kaz(G,S) = Kaz(G,S^{-1}) = Kaz(G,S \cup S^{-1})}$ .

(iii) One has ${Kaz(G,S,\rho) = Kaz(G,S \cup \{1\},\rho)}$ and ${Kaz(G,S) = Kaz(G,S \cup \{1\})}$ .

(iv) One has ${Kaz(G,S^m,\rho) \leq m Kaz(G,S,\rho)}$ and ${Kaz(G,S^m) \leq m Kaz(G,S)}$ for all ${m \geq 1}$ .

(v) If ${S}$ generates ${G}$ as a group (thus every element of ${G}$ is a finite word in ${S}$ ), show that ${G}$ has Kazhdan property (T) if and only if ${Kaz(G,S) > 0}$ .

From the above exercise, we see that the precise choice of compact set ${S}$ needed to establish the Kazhdan property is not important, so long as that it generates the group (and by hypothesis, every locally compact group ${G}$ has at least one compact generating set ${S}$ .)

Remark 3 In our conventions, we are only considering locally compact groups that are compactly generated. However, in some applications it is important to note that the compact generation hypothesis is in fact automatic if one has Kazhdan’s property (T). Indeed, if ${Kaz(G,S) > 0}$ for some compact ${S}$ (which we may assume without loss of generality to be a neighbourhood of the identity), and ${G'}$ is the (necessarily open) subgroup of ${G}$ generated by ${S}$ , then the Dirac delta ${\delta_1}$ in the Hilbert space ${\ell^2(G/G')}$ is ${G'}$ -invariant and thus (by the hypothesis ${Kaz(G,S)>0}$ ) ${\ell^2(G/G')}$ has a ${G}$ -invariant vector, which forces ${G/G'}$ to be finite, and so ${G}$ is compactly generated.

Exercise 8 Let ${G}$ be a locally compact group, let ${S}$ be a compact subset of ${G}$ . Show that the following assertions are equivalent:

(i) ${Kaz(G,S)=0}$ .

(ii) There exists a unitary representation ${\rho: G \rightarrow U(H)}$ with no non-trivial invariant vectors such that ${Kaz(G,S,\rho)=0}$ .

(Hint: If ${Kaz(G,S)=0}$ , take a sequence of unitary representations of ${G}$ with no non-trivial invariant vectors but a sequence of increasingly ${S}$ -approximately-invariant vectors, and form their (infinite) direct sum.)

Exercise 9 Let ${G}$ be a locally compact group, let ${S}$ be a compact subset of ${G}$ , and let ${\epsilon>0}$ . Show that the following assertions are equivalent:

(i) ${Kaz(G,S) \geq \epsilon}$ .

(ii) For any unitary representation ${\rho: G \rightarrow U(H)}$ (possibly containing invariant vectors), and any ${v \in H}$ , one has
$\displaystyle \hbox{dist}(v, H^G) \leq \frac{1}{\epsilon} \sup_{s \in S} \| \rho(s) v - v \|_H.$

Exercise 10 Let ${G}$ be a locally compact group. Show that exactly one of the following is true:

(i) ${G}$ has property (T).

(ii) There exists a sequence ${\rho_n: G \rightarrow U(H_n)}$ of representations and a sequence of unit vectors ${v_n \in H_n}$ such that ${\| sv_n -v_n \|_{H_n} \rightarrow 0}$ for all ${s \in G}$ , but such that each of the ${H_n}$ contains no non-trivial invariant vectors.

Remark 4 Informally, the statement in (ii) of the preceding exercise shows that one can reach the trivial representation as a “limit” of a sequence of representations with no non-trivial invariant vectors. As such, property (T) can be viewed as the assertion that the trivial representation ${T}$ is isolated from the other representations in some sense, which is the origin for the term “property (T)”. This intuition can be formalised by introducing Fell’s topology on unitary representations; see the text of Bekka, de la Harpe, and Valette for details.

Now we show why Kazhdan constants are related to expansion in Cayley graphs.

Exercise 11 Let ${Cay(G,S)}$ be a finite ${k}$ -regular Cayley graph, and let ${\epsilon>0}$ . Let ${\rho = \tau\downharpoonright_{\ell^2(G)_0}}$ be the restriction of the regular representation of ${G}$ to the functions of mean zero.

(i) If ${Kaz(G,S,\rho) \geq \epsilon}$ , show that ${Cay(G,S)}$ is a one-sided ${c}$ -expander for some ${c = c(\epsilon,k) > 0}$ .

(ii) Conversely, if ${Cay(G,S)}$ is a one-sided ${\epsilon}$ -expander, show that ${Kaz(G,S,\rho) \geq c}$ for some ${c = c(\epsilon,k) > 0}$ .

(Hint: Use the triangle inequality and the cosine rule: if ${v, w}$ are unit vectors with ${\|v-w\|_H^2 = 2 - \langle v, w \rangle_H}$ .)

Thus, to show that a sequence ${Cay(G_n,S_n)}$ of ${k}$ -regular Cayley graphs form a one-sided expander family, it suffices to obtain a lower bound on the Kazhdan constants ${Kaz(G_n,S_n,\rho_n)}$ . There is a similar criterion for two-sided expansion:

Exercise 12 Let ${Cay(G,S)}$ be a finite ${k}$ -regular Cayley graph, and let ${\epsilon>0}$ . Let ${\rho = \tau\downharpoonright_{\ell^2(G)_0}}$ be the restriction of the regular representation of ${G}$ to the functions of mean zero.

(i) If ${Kaz(G,S^2,\rho) \geq \epsilon}$ , show that ${Cay(G,S)}$ is a two-sided ${c}$ -expander for some ${c = c(\epsilon,k) > 0}$ .

(ii) Conversely, if ${Cay(G,S)}$ is a two-sided ${\epsilon}$ -expander, show that ${Kaz(G,S^2,\rho) \geq c}$ for some ${c = c(\epsilon,k) > 0}$ .

One advantage of working with Kazhdan constants instead of expansion constants is that they behave well with respect to homomorphisms:

Exercise 13 Let ${G, G'}$ be locally compact groups, and suppose that there is a continuous surjective homomorphism ${\pi: G \rightarrow G'}$ from ${G}$ to ${G'}$ . Let ${S}$ be a compact subset of ${G}$ . Show that for any unitary representation ${\rho': G' \rightarrow U(H)}$ of ${G'}$ , one has ${Kaz(G',\pi(S),\rho') = Kaz(G,S,\rho' \circ \pi)}$ . Conclude that ${Kaz(G',\pi(S)) \geq Kaz(G,S)}$ . In particular, if ${G}$ has property (T), then ${G'}$ does also.

As a corollary of the above results, we can use Kazhdan’s property (T) to generate expander families:

Exercise 14 Let ${G}$ be a finitely generated discrete group, and let ${S}$ be a symmetric subset of ${G}$ that generates ${G}$ . Let ${N_n}$ be a sequence of finite index normal subgroups of ${G}$ , and let ${\pi_n: G \rightarrow G/N_n}$ be the quotient maps. Suppose that for all sufficiently large ${n}$ , ${\pi_n}$ is injective on ${S \cup \{1\}}$ . Show that if ${G}$ has property (T), then ${Cay(G/N_n, \pi_n(S))}$ for sufficiently large ${n}$ is an expander family.

It is thus of interest to find ways to demonstrate property (T), or in other words to create invariant vectors from almost invariant vectors. The next few exercises will develop some tools for this purpose.

Exercise 15 Let ${\rho: G \rightarrow U(H)}$ be a unitary representation of a locally compact group ${G}$ . Suppose that there is a closed convex set ${K}$ in ${H}$ that contains an orbit ${\{ gv_0: g \in G \}}$ of some element ${v_0}$ in ${K}$ . Show that ${K}$ contains an invariant vector. (Hint: Show that the set ${K' := \{ v \in H: gv \in K \hbox{ for all } g \in G \}}$ is closed, convex, and ${G}$ -invariant; now study an element of ${K'}$ of minimal norm.)

Exercise 16 Show that every compact group has property (T). (Hint: use Exercise 15.)

Exercise 17 (Direct products and property (T)) Let ${G, G'}$ be locally compact groups. Show that the product group ${G \times G'}$ (with the product topology, of course) has property (T) if and only if ${G}$ and ${G'}$ both separately have property (T). (Hint: one direction follows from Exercise 13. To obtain the other direction, start with an approximately invariant vector ${v}$ for ${G \times G'}$ and use Exercise 9 (and Exercise 7(v)) to show that the ${G \times G'}$ -orbit of ${v}$ stays close to ${v}$ , then use Exercise 15.)

Exercise 18 (Short exact sequences and property (T)) Let ${G}$ be a locally compact group, and let ${N}$ be a closed normal subgroup of ${G}$ ; then ${N}$ and ${G/N}$ are also locally compact. Show that if ${N}$ and ${G/N}$ have property (T), then ${G}$ also has property (T).

Exercise 19 Let ${G}$ be an infinite discrete finitely generated group, generated by a finite set ${S}$ . Show that the following assertions are equivalent:

(i) There exists a sequence ${F_n}$ of finite non-empty subsets in ${G}$ with the property that ${|sF_n \Delta F_n|/|F_n| \rightarrow 0}$ as ${n \rightarrow \infty}$ for each ${s \in S}$ . (Such a sequence of sets is known as a Folner sequence for ${G}$ .)

(ii) One has ${Kaz(G,S,\tau) = 0}$ , where ${\tau}$ is the regular representation of ${G}$ .

(Hint: you may wish to mimic the proof of the weak discrete Cheeger inequality.)

Infinite, finitely generated groups ${G}$ with property (i) or (ii) of the above exercise are known as amenable groups; amenability is an important property in ergodic theory, operator algebras, and many other areas of mathematics, but will not be discussed extensively in this course. The notion of amenability can also be extended to other locally compact groups, but we again will not discuss these matters here. From the above exercise, we see that an infinite amenable finitely generated group cannot have property (T). The next example shows, though, that it is also possible for non-amenable groups (such as the free group on two or more generators) to not have property (T).

Exercise 20

(i) Show that the integers ${{\bf Z}}$ do not have property (T).

(ii) Show that any infinite discrete abelian finitely generated group does not have property (T).

(iii) Show that any finitely generated group ${G}$ with infinite abelianisation ${G/[G,G]}$ does not have property (T).

(iv) Show that for any ${k \geq 1}$ , the free group on ${k}$ generators does not have property (T).

Exercise 21 (Property (T) and group cohomology) The purpose of this exercise is to link property (T) to some objects of interest in group cohomology, and in particular to demonstrate some “rigidity” properties of groups with property (T). (This exercise will not be needed in the rest of the course.) The results here originate from the work of Delorme and Guichardet; see Bekka, de la Harpe, and Valette or this paper of Shalom for a further discussion of the rigidity (and superrigidity) properties of groups with property (T).

Let ${\rho: G \rightarrow U(H)}$ be a unitary representation of a locally compact group ${G}$ . Define a ${\rho}$ -cocycle to be a continuous function ${c: G \rightarrow H}$ obeying the cocycle equation

$\displaystyle c(gh) = c(g) + \rho(g) c(h)$

for all ${g,h \in G}$ . (Equivalently, a ${\rho}$ -cocycle determines an affine isometric action ${v \mapsto \rho(g) v + c(g)}$ of ${G}$ on ${H}$ with ${\rho}$ as the unitary component of the action.) Define a ${\rho}$ -coboundary to be a function ${c: G \rightarrow H}$ of the form
$\displaystyle c(g) = v_0 - \rho(g) v_0$

for some fixed vector ${v_0 \in H}$ (or equivalently, an affine isometric action of ${G}$ on ${H}$ with a common fixed point ${v_0}$ ); observe that every ${\rho}$ -coboundary is automatically a ${\rho}$ -cocycle.

(i) Show that a ${\rho}$ -cocycle ${c: G \rightarrow H}$ is a ${\rho}$ -coboundary if and only if it is bounded. (Hint: if ${c}$ is a bounded ${\rho}$ -cocycle, then for any vector ${v}$ the orbit ${\{ \rho(g) v + c(g): g \in G \}}$ of ${v}$ lies in a ball. Exploit convexity to construct a shrinking sequence of such balls and use the completeness of ${H}$ pass to the limit.)

(ii) Show that if ${G}$ has property (T), then every ${\rho}$ -cocycle is a ${\rho}$ -coboundary. (Hint: the main difficulty is to lift the affine isometric action to a unitary action. One way to do this is to work in the Hilbert space ${\tilde H}$ that is the completion of the finitely supported measures on ${H}$ , using an inner product such as ${\langle \delta_v, \delta_w \rangle_{\tilde H} := e^{-\epsilon \|v-w\|^2}}$ for some sufficiently small ${\epsilon>0}$ (one needs to verify that this does indeed determine a positive definite inner product, which can be seen for instance by working in finite dimensions and using either Fourier transforms or gaussian identities). Note that the separability of ${H}$ will imply the separability of ${\tilde H}$ .)

(iii) Conversely, show that if for every unitary representation ${\rho}$ , every ${\rho}$ -cocycle is a ${\rho}$ -coboundary, then ${G}$ has property (T). (Hint: First show that (by taking a direct sum of counterexamples, as in Exercise 8) that if ${S}$ is a compact neighbourhood of the identity that generates ${G}$ , ${\rho: G \rightarrow U(H)}$ is any unitary representation, and ${c}$ is a ${\rho}$ -cocycle, then ${\sup_{g \in G} \|c(g)\|_H \leq C \sup_{s \in S} \|c(s)\|_H}$ , where ${C}$ depends on ${S}$ but is independent of ${\rho}$ or ${c}$ . Apply this fact to a coboundary generated by an approximate vector.)

— 2. Induced representations and property (T) —

Let ${\tilde G}$ be a locally compact group, and let ${G}$ be a subgroup of ${\tilde G}$ which is closed (and thus also locally compact). Clearly, every unitary representation ${\tilde \rho: \tilde G \rightarrow U(H)}$ of ${\tilde G}$ can be restricted to form a unitary representation ${Res^G_{\tilde G} \rho\: G \rightarrow U(H)}$ of ${G}$ . It is then natural to ask whether the converse is also true, that is to say whether any unitary representation ${\rho: G \rightarrow U(H)}$ of ${H}$ can be extended to a representation ${\tilde \rho: \tilde G \rightarrow U(H)}$ of ${\tilde G}$ on the same Hilbert space ${H}$ .

In general, the answer is no. For instance, if ${\tilde G}$ is the Heisenberg group ${\tilde G = \begin{pmatrix} 1 & {\bf Z} & {\bf Z} \\ 0 & 1 & {\bf Z} \\ 0 & 0 & 1 \end{pmatrix}}$ , and ${G = [\tilde G,\tilde G]}$ is the commutator group ${G = \begin{pmatrix} 1 & 0 & {\bf Z} \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}}$ , then any one-dimensional representation ${\tilde \rho: \tilde G \rightarrow U_1({\bf C})}$ must annihilate the commutator ${G}$ , but there are clearly non-trivial one-dimensional representations ${\rho: G \rightarrow U_1({\bf C})}$ of ${G}$ which thus cannot be extended to a representation of ${G}$ .

However, there is a fundamental construction that (under some mild hypotheses) takes a representation ${\rho: G \rightarrow U(H)}$ of ${G}$ and converts it to an induced representation ${\tilde \rho := Ind^{\tilde G}_G \rho: \tilde G \rightarrow U(\tilde H)}$ of ${\tilde G}$ , that acts on a somewhat larger Hilbert space ${\tilde H}$ than ${H}$ (in particular, the induced representation construction is not an inverse of the restricted representation construction). This construction will provide an important link between the representation theories of ${G}$ and ${\tilde G}$ , and in particular will connect property (T) for ${G}$ to property (T) for ${\tilde G}$ .

To motivate the induced representation construction, we work for simplicity in the case when ${G}$ and ${\tilde G}$ are discrete, consider the regular representations ${\tau: G \rightarrow U(H)}$ and ${\tilde \tau: \tilde G \rightarrow U(\tilde H)}$ of ${G}$ and ${\tilde G}$ respectively, where ${H := \ell^2(G)}$ and ${\tilde H := \ell^2(\tilde G)}$ . We wish to view the ${\tilde G}$ -representation ${\tilde \tau}$ as somehow being induced from the ${G}$ -representation ${\tau}$ :

$\displaystyle \tilde \tau = Ind_G^{\tilde G} \tau.$

To do this, we must somehow connect ${H}$ with ${\tilde H}$ , and ${\tau}$ with ${\tilde \tau}$ .

One natural way to proceed is to express ${\tilde G}$ as the union of cosets ${kG}$ of ${G}$ for ${k}$ in some set ${K}$ of coset representatives. We can then split ${\ell^2(\tilde G)}$ as a direct sum ${\ell^2(\tilde G) = \oplus_{k \in K} \ell^2(kG)}$ (at least in the model case when ${K}$ is finite), and each factor space ${\ell^2(kG)}$ can be viewed as a shift ${\ell^2(kG) = \tilde \rho(k) \ell^2(G)}$ of ${\ell^2(G)}$ . This does indeed give enough of a relationship between ${\tau}$ and ${\tilde \tau}$ to generalise to other representations, but it is a somewhat inelegant “coordinate-dependent” formalism because it initially depends on making a somewhat arbitrary choice of coset representatives ${K}$ (though one can show, at the end of the construction, that the choice of ${K}$ was ultimately irrelevant). Also, this method develops some technical complications when the quotient space ${\tilde G/G}$ is not discrete.

Because of this, we shall work instead with a more “coordinate-free” construction that does not require an explicit construction of coset representatives. Instead, we rely on the orthogonal projection ${\pi: \tilde H \rightarrow H}$ of the larger Hilbert space ${\tilde H = \ell^2(\tilde G)}$ to the smaller Hilbert space ${\ell^2(G)}$ , which in the case of the regular representation is just the restriction map, ${\pi(f) := f\downharpoonright_G}$ .

Observe that given any vector ${f \in \tilde H}$ and group element ${g \in \tilde G}$ , one can form the projection ${F(g) := \pi(\tilde \rho(g^{-1}) f)}$ in ${H}$ , which can be written explicitly as

$\displaystyle F(g)(x) = f(gx)$

for ${g \in \tilde G}$ and ${x \in \tilde G}$ . Thus ${F}$ is a function from ${\tilde G}$ to ${H}$ which obeys the symmetry

$\displaystyle F(gh) = \rho(h^{-1}) F(g) \ \ \ \ \ (4)$

for all ${g \in \tilde G}$ and ${h \in G}$ . Conversely, any function ${F: \tilde G \rightarrow H}$ obeying the symmetry (4) arises from an element ${f}$ of ${H'}$ in this manner. Thus, we may identify ${\tilde H}$ (as a vector space, at least), with the space of functions ${F: \tilde G \rightarrow H}$ obeying (4). Furthermore, the Hilbert space norm ${\|f\|_{\tilde H} = \|f\|_{\ell^2(\tilde G)}}$ of ${\tilde G}$ can be expressed in terms of ${F}$ via the identity

$\displaystyle \|f\|_{\tilde H} = (\sum_{g \in \tilde G/G} \|F(g)\|_H^2)^{1/2},$

where we use the fact (from (4)) that ${\|F(gh)\|_H = \|F(g)\|_H}$ for all ${h \in H}$ to view (by abuse of notation) ${\|F(\cdot)\|_H}$ as a function of ${\tilde G/G}$ rather than of ${\tilde G}$ . Similarly, given two vectors ${f, f' \in \tilde H}$ with associated functions ${F, F': \tilde G \rightarrow H}$ , the inner product ${\langle f, f' \rangle_{\tilde H}}$ can be recovered from ${F, F'}$ by the formula

$\displaystyle \langle f, f' \rangle_{\tilde H} = \sum_{g \in \tilde G/G} \langle F(g), F'(g) \rangle_H,$

where we adopt the same abuse of notation as before.

Motivated by this example, we now have the following construction (essentially due to Frobenius).

Definition 5 (Induced representation) Let ${\tilde G}$ be a locally compact group, and let ${G}$ be a subgroup of ${\tilde G}$ which is closed (and thus also locally compact). Suppose that there is a non-zero Radon measure ${\mu_{\tilde G/G}}$ on the quotient space ${\tilde G/G}$ which is invariant under the left-action of ${\tilde G}$ (i.e. it is a Haar measure of ${\tilde G/G}$ ). Let ${\rho: G \rightarrow U(H)}$ be a unitary representation of ${G}$ . Then we define the induced representation ${\tilde \rho = Ind_G^{\tilde G} \rho: \tilde G \rightarrow U(\tilde H)}$ as follows. We define ${\tilde H}$ to be the (pre-)Hilbert space of all functions ${F: \tilde G \rightarrow H}$ obeying (4) for all ${g \in \tilde G}$ and ${h \in G}$ , that are weakly measurable in the sense that ${\lambda(F)}$ is Borel measurable for all bounded linear functionals ${\lambda: H \rightarrow {\bf C}}$ , and such that the norm
$\displaystyle \|F\|_{\tilde H} := (\int_{g \in \tilde G/G} \|F(g)\|_H^2\ d\mu_{\tilde G/G}(g))^{1/2}$

is finite, where we abuse notation as before and view ${\|F(\cdot)\|_H}$ as a function of ${\tilde G/G}$ . (Note from the separability of ${H}$ that the function ${\|F(\cdot)\|_H}$ is measurable.) We also define the inner product on ${\tilde H}$ by
$\displaystyle \langle F, F' \rangle_{\tilde H} := \int_{g \in \tilde G/G} \langle F(g), F'(g) \rangle_H\ d\mu_{\tilde G/G}(g),$

and identify together elements of ${\tilde H}$ whose difference has norm zero, to obtain a genuine Hilbert space rather than a pre-Hilbert space. (We leave it to the reader to verify that this space is in fact complete; this is a “ ${G}$ -space” version of the standard argument establishing that ${L^2(X,\mu)}$ is complete for any measure space ${(X,\mu)}$ .) We then define the representation ${\tilde \rho}$ on ${\tilde H}$ by the formula
$\displaystyle \tilde \rho(g) F(x) := F(g^{-1} x)$

for all ${g, x \in \tilde G}$ ; one can verify that this is a well-defined unitary representation.

Remark 5 Given a Haar measure ${\mu_{\tilde G/G}}$ on ${\tilde G/G}$ and a Haar measure ${\mu_G}$ on ${G}$ , one can build a Haar measure ${\mu_{\tilde G}}$ on ${\tilde G}$ via the Riesz representation theorem and the integration formula
$\displaystyle \int_{\tilde G} f(x)\ d\mu_{\tilde G}(x) := \int_{\tilde G/G} (\int_{G} f(yz)\ d\mu_G(z)) d\mu_{\tilde G/G}(y)$

for ${f \in C_c(\tilde G)}$ , where we abuse notation by noting that the integrand is a ${G}$ -right-invariant function of ${y \in \tilde G}$ , and can thus be viewed as a function on the quotient space ${\tilde G/G}$ . As Haar measures on groups are determined up to constants (as shown for instance in this previous blog post), we conclude that Haar measures on quotient spaces ${\tilde G/G}$ , if they exist, are also determined up to constants. As such, the induced representation construction given above does not depend (up to isomorphism) on the choice of Haar measure on ${\tilde G/G}$ . However, it is possible to have quotient spaces for which no Haar measure is available; for instance the group of affine transformations ${x \mapsto ax+b}$ acts on ${{\bf R}}$ (which is then a quotient of the affine group by the stabiliser of a point), but without any invariant measure. It is possible to extend the induced representation construction to this setting also, but this is more technical; see this text of Folland for details.

Example 10 If ${G}$ is an open subgroup of ${\tilde G}$ , and ${\mu_{\tilde G/G}}$ is counting measure, then the induced representation of the trivial one-dimensional representation of ${G}$ is the quasiregular representation of ${\tilde G}$ on ${\tilde G/G}$ , and the induced representation of the regular representation of ${G}$ is the regular representation of ${\tilde G}$ .

Exercise 22 (Transitivity of induction) Let ${G_3 \leq G_2 \leq G_1}$ be locally compact groups, such that ${G_3}$ has finite index in ${G_2}$ , and ${G_2}$ has finite index in ${G_1}$ . Show that for any unitary representation ${\rho: G_3 \rightarrow U(H)}$ of ${G_3}$ , one has ${Ind_{G_2}^{G_3} Ind_{G_2}^{G_1} \rho \equiv Ind^{G_1}_{G_3} \rho}$ . (A similar statement is also true in the infinite index case, but is more technical to establish.)

As a first application of the induced representation construction (and the much simpler restricted representation construction), we show that one can pass from a group to a finite subgroup as far as property (T) is concerned.

Proposition 6 Let ${\tilde G}$ be a locally compact group, and let ${G}$ be a finite index closed subgroup of ${\tilde G}$ . Then ${\tilde G}$ has property (T) if and only if ${G}$ has property (T).

Proof: Suppose first that ${G}$ has property (T). Let ${S}$ be a compact generating subset of ${G}$ . As ${G}$ has finite index in ${\tilde G}$ , we may find a finite set ${K}$ in ${\tilde G}$ such that ${K G = \tilde G}$ . Let ${\rho: \tilde G \rightarrow U(H)}$ be a unitary representation, and suppose that ${H}$ has a unit vector ${v}$ such that ${\|sv-v\|_H \leq \epsilon}$ for all ${s \in S \cup K}$ , where ${\epsilon>0}$ is a small quantity (independent of ${\rho}$ ) to be determined later. We will show that ${v}$ lies within distance ${O(\epsilon)}$ from a ${\tilde G}$ -invariant vector (where the implied constant can depend on ${S,G,\tilde G}$ but not on ${\epsilon}$ ), which will give the claim for ${\epsilon}$ small enough.

By Exercise 7(v) applied to ${G}$ , ${Kaz(G,S) > 0}$ . By Exercise 9, we thus see that ${v}$ lies within ${O(\epsilon)}$ from a ${G}$ -invariant vector, so by the triangle inequality we may assume without loss of generality (and adjusting ${\epsilon}$ slightly) that ${v}$ is ${G}$ -invariant. If ${g \in G}$ is arbitrary, we may write ${g = k \gamma}$ for some ${k \in K}$ . Then ${\|gv-v\|_H = \|kv-v\|_H = O(\epsilon)}$ . Thus the ${\tilde G}$ -orbit of ${v}$ lies in a ball of radius ${O(\epsilon)}$ centred at ${v}$ , and so by Exercise 15 this ball contains an invariant vector as required.

Conversely, suppose that ${\tilde G}$ has property (T). Let ${S}$ be a compact generating subset of ${G}$ , which we may assume without loss of generality to be a neighbourhood of the identity. Let ${\rho: G \rightarrow U(H)}$ be a unitary representation, and let ${v_0}$ be a unit vector such that

$\displaystyle \|sv_0-v_0\|_H \leq \epsilon \ \ \ \ \ (5)$

for all ${s \in S}$ , where ${\epsilon>0}$ is a small quantity independent of ${\rho}$ to be chosen later. Our task is to show that ${v_0}$ lies within ${O(\epsilon)}$ of a ${G}$ -invariant vector. Now we form the induced representation ${\tilde \rho := Ind_{G}^{\tilde G} \rho: \tilde G \rightarrow U(\tilde H)}$ (using counting measure for ${\mu_{\tilde G/G}}$ ). By construction, ${\tilde H}$ is the space of all functions ${\tilde v: \tilde G \rightarrow H}$ such that ${\tilde v(x\gamma) := \rho(\gamma)^{-1} \tilde v(x)}$ for all ${\gamma \in G}$ and ${x \in \tilde G}$ . If we let ${K}$ be a finite set consisting of one representative of each left-coset of ${G}$ , it is easy to see that each element ${\tilde v: \tilde G \rightarrow H}$ of ${\tilde H}$ is determined by its restriction to ${K}$ , and conversely every function from ${\tilde v:K \rightarrow H}$ can be extended uniquely to an element of ${\tilde H}$ ; thus ${\tilde H}$ can be identified with the direct sum ${\oplus_{k \in K} H}$ of ${|K|}$ copies of ${H}$ . Also, ${\tilde H}$ contains ${H}$ as a ${G}$ -invariant subspace, by identifying each vector ${v \in H}$ with the function ${\tilde v}$ defined by setting ${\tilde v(\gamma) = \rho(\gamma)^{-1} v}$ for ${\gamma \in G}$ and ${\tilde v(x)=0}$ for ${x \not \in G}$ . The actions of ${\tilde \rho}$ and ${\rho}$ are then compatible in the sense that ${\tilde \rho(\gamma) v = \rho(\gamma) v}$ for all ${\gamma \in G}$ and ${v \in H}$ .

Now consider the vector

$\displaystyle \tilde v := \sum_{k \in K} \tilde \rho(k) v_0.$

We now study its invariance properties of this vector with respect to ${\tilde S := S \cup K}$ (which generates ${\tilde G}$ ). For any ${s \in \tilde S}$ and ${k \in K}$ , ${sk}$ lies in a compact subset of ${\tilde G}$ , and thus ${sk = k' s'}$ for some ${k' = k'(k,s)}$ in ${K}$ and ${s' = s'(k,s)}$ for some ${s'}$ in a compact subset of ${G}$ . Also, for fixed ${k}$ , the map ${k \mapsto k'(k,s)}$ is a permutation of ${K}$ . Since ${S}$ is a compact neighbourhood of the identity generating ${G}$ , we see from compactness that there is a finite ${m}$ such that ${s'(k,s) \in S^m}$ for all ${k,s}$ . In particular, from (5) and the triangle inequality we have

$\displaystyle \| \rho(s') v_0 - v_0 \|_H \leq m \epsilon.$

Since

$\displaystyle \tilde \rho(s) \tilde v - \tilde v = \sum_{k \in K} \tilde \rho(k'(k,s)) ( \rho(s'(k,s)) v_0 - v_0 )$

we conclude from the triangle inequality that

$\displaystyle \|\tilde \rho(s) \tilde v - \tilde v\|_H = O(\epsilon)$

where the implied constant can depend on ${m,S,K,G,\tilde G}$ but not on ${\rho}$ or ${\epsilon}$ . As ${\tilde G}$ has property (T), we conclude (for ${\epsilon}$ small enough) using Exercise 9 that ${\tilde v}$ lies within ${O(\epsilon)}$ of an ${\tilde G}$ -invariant vector ${w}$ . In particular, as ${\tilde G}$ -invariant vectors are also ${G}$ -invariant, ${w(1)}$ is a ${G}$ -invariant vector in ${H}$ which is within ${O(\epsilon)}$ of ${\tilde v(1)=v_0}$ , as desired. $\Box$

Actually, with a bit more effort, one can generalise the above proposition from the finite index case to the finite covolume case, as was first observed by Kazhdan. There is however a technical issue; once ${\tilde G/G}$ is not discrete, the original Hilbert space ${H}$ does not embed naturally into the induced Hilbert space ${\tilde H}$ (basically because ${G}$ now has measure zero in ${\tilde G}$ , so there is no obvious way to embed ${L^2(G)}$ into ${L^2(\tilde G)}$ ). This issue however can be dealt with by “convolving” with a suitable approximation to the identity ${f \in C_c(\tilde G)}$ , where ${C_c(\tilde G)}$ is the space of continuous functions ${f: \tilde G \rightarrow {\bf C}}$ with compact support. More precisely, we have the following definition:

Definition 7 Let ${\tilde G}$ be a locally compact group, and let ${G}$ be a subgroup of ${\tilde G}$ that is also a locally compact group. Let ${\mu_{\tilde G/G}}$ be a Haar measure on ${\tilde G/G}$ , and let ${\mu_G}$ be a Haar measure on ${G}$ . Let ${\rho: G \rightarrow U(H)}$ be a unitary representation, and let ${\tilde \rho: \tilde G \rightarrow U(\tilde H)}$ be the induced representation ${\tilde \rho = Ind_G^{\tilde G} \rho}$ . Let ${v \in H}$ , and let ${f \in C_c(\tilde G)}$ . Then we define the convolution ${C_f(v) \in \tilde H}$ of ${v}$ by ${f}$ to be the function ${C_f(v): \tilde G \rightarrow H}$ given by the formula
$\displaystyle C_f(v)(g) := \int_G f(gh) \rho(h) v d\mu_G(h).$

One easily verifies that ${C_f(v)}$ is well-defined and lies in ${\tilde H}$ .

Related to the convolution operation will be the projection ${\Pi_{\tilde G/G}(f) \in C_c(\tilde G/G)}$ of a function ${f \in C_c(\tilde G)}$ , defined by the formula

$\displaystyle \Pi_{\tilde G/G}(f)(g) = \int_G f(gh)\ d\mu_G(h),$

where the right-hand side is right ${G}$ -invariant in ${g}$ , and can thus be viewed as a function of ${\tilde G/G}$ rather than ${\tilde G}$ . We have the following key technical fact:

Lemma 8 (Surjectivity) The projection operator ${\Pi_{\tilde G/G}: C_c(\tilde G) \rightarrow C_c(\tilde G/G)}$ is surjective. Furthermore, given a non-negative function ${F}$ in ${C_c(\tilde G/G)}$ , we may find a non-negative function ${f'}$ in ${C_c(\tilde G)}$ with ${\Pi_{\tilde G/G}(f')= F}$ .

Proof: It suffices to prove the second claim. Let ${F: \tilde G/G \rightarrow {\bf R}^+}$ be a non-negative continuous function supported on some compact subset ${K}$ of ${\tilde G/G}$ . By compactness, one can find a compact subset ${\tilde K}$ of ${\tilde G}$ which covers ${K}$ in the sense that for every coset ${gG}$ in the preimage of ${K}$ , the set ${\tilde K \cap gG}$ is non-empty and open in ${gG}$ (or equivalently, ${g^{-1} \tilde K \cap G}$ is open in ${G}$ ). By Urysohn’s lemma, we may find a non-negative function ${f \in C_c(\tilde G)}$ which equals ${1}$ on ${\tilde K}$ , and then ${\Pi_{\tilde G/G}(f)}$ is nonzero on ${K}$ . Thus we may write ${F = \Pi_{\tilde G/G}(f) F'}$ for some ${F' \in C_c(\tilde G/G)}$ . If we let ${\pi: \tilde G \rightarrow \tilde G/G}$ be the projection map, then we easily verify that the function ${f' := f (F' \circ \pi)}$ lies in ${C_c(\tilde G)}$ and is non-negative with ${F = \Pi_{\tilde G/G}(f')}$ , and the claim follows. $\Box$

Now we generalise Proposition 6 to the finite covolume case:

Proposition 9 Let ${\tilde G}$ be a locally compact group, and let ${G}$ be a locally compact subgroup of ${\tilde G}$ . Suppose that ${G}$ has finite covolume in ${\tilde G}$ , which means that there exists a finite Haar measure ${\mu_{\tilde G/G}}$ on ${\tilde G/G}$ . Then ${\tilde G}$ has property (T) if and only if ${G}$ has property (T).

Proof: We may normalise the Radon measure ${\mu}$ to be a probability measure. Suppose first that ${G}$ has property (T). Let ${S}$ be a compact generating subset of ${G}$ , and let ${\epsilon}$ be chosen later. As ${\mu(\tilde G/G) = 1}$ and ${\tilde G}$ is compactly generated, we may use inner regularity and find a compact subset ${K}$ of ${\tilde G}$ such that ${\mu(\pi(K)) \geq 1-\epsilon}$ , where ${\pi: \tilde G \rightarrow \tilde G/G}$ is the projection map.

Now let ${\rho: \tilde G \rightarrow U(H)}$ be a unitary representation, and suppose that ${H}$ has a unit vector ${v}$ such that ${\|sv-v\|_H \leq \epsilon}$ for all ${s \in S \cup K}$ . As before, the goal is to show that ${v}$ lies within distance ${O(\epsilon)}$ from a ${\tilde G}$ -invariant vector, which will give the claim for ${\epsilon}$ small enough.

By Exercise 7(v) and Exercise 9 as in the previous argument, we may assume that ${v}$ is ${G}$ -invariant. The function ${g \mapsto \rho(g) v}$ then descends from a bounded ${H}$ -valued function on ${\tilde G}$ to a function on ${F: \tilde G/G \rightarrow H}$ . We may thus form the average

$\displaystyle \bar{v} := \int_{\tilde G/G} F(x)\ d\mu_{\tilde G/G}(x),$

where we can define the ${H}$ -valued integral in the weak sense, using bounded linear functionals ${\lambda: H \rightarrow {\bf C}}$ on ${H}$ and the Riesz representation theorem for Hilbert spaces, noting that ${F}$ is weakly integrable in the sense that ${\lambda(F)}$ is absolutely integrable for all bounded linear functionals ${\lambda}$ . By the left-invariance of ${\mu_{\tilde G/G}}$ we see that ${\bar{v}}$ is ${\tilde G}$ -invariant. Also, by construction, we have ${\|F(x)\|_H = O(1)}$ for all ${x \in \tilde G/G}$ , and ${\|F(x)-x\|_H = O(\epsilon)}$ for all ${x \in \pi(K)}$ , which has measure ${1-\epsilon}$ . As such we see that ${\|\bar{v}-v\|_H = O(\epsilon)}$ , and the claim follows.

Now suppose instead that ${\tilde G}$ has property (T). Let ${S}$ be a compact generating subset of ${G}$ , which we may assume without loss of generality to be a neighbourhood of the identity. Let ${\rho: G \rightarrow U(H)}$ be a unitary representation, and let ${v_0}$ be a unit vector obeying (5) for all ${s \in S}$ , and some small ${\epsilon>0}$ (depending only on ${S,G, \tilde G}$ and to be chosen later). We will suppose for contradiction that ${H}$ contains no non-trivial ${G}$ -invariant vectors.

As before, the first step is to build the induced representation ${\tilde \rho := Ind_G^{\tilde G} \rho: \tilde G \rightarrow U(\tilde H)}$ of ${\rho}$ , using the given Haar measure ${\mu_{\tilde G/G}}$ . Let ${\delta > 0}$ be a sufficiently small quantity (depending on ${S,G,\tilde G}$ , but not depending on ${\epsilon}$ ) to be chosen later. By inner regularity, we can find a compact subset ${K}$ of ${\tilde G/G}$ of measure ${\mu_{\tilde G/G}(K) \geq 1-\delta}$ . By Urysohn’s lemma followed by Lemma 8, we may find a function ${f \in C_c(G)}$ such that ${\Pi_{\tilde G/G}(f)}$ is bounded by ${1}$ and equals ${1}$ on ${K}$ ; in particular, it differs by ${1}$ only on a set of measure ${O(\delta)}$ . Now we consider the vector ${v \in \tilde H}$ defined by the formula

$\displaystyle v := C_f(v_0),$

thus

$\displaystyle v(g) = \int_G f(gh) \rho(h) v d\mu_G(h).$

By the triangle inequality one has

$\displaystyle \|v(g)\|_H \leq \int_G f(gh) d\mu_G(h) = \Pi_{\tilde G/G}(f) \leq 1 \ \ \ \ \ (6)$

for all ${g \in \tilde G}$ .

Let ${K'}$ be a compact subset of ${\tilde G}$ with ${\pi(K')}$ containing ${K}$ . For ${g \in K'}$ and ${h \in G}$ with ${gh}$ in the support of ${f}$ , we see from the approximate invariance of ${v_0}$ that

$\displaystyle \| \rho(h) v - v \|_H \ll_\delta \epsilon$

and thus

$\displaystyle \| v(g) - \Pi_{\tilde G/G} f(g) v \|_H \ll_\delta \epsilon.$

In particular, we see that ${\|v(g)\|_H}$ is equal to ${1 - O_\delta(\epsilon)}$ for all ${g \in K}$ (again abusing notation and descending from ${\tilde G}$ to ${\tilde G/G}$ ). From this and (6) we see that

$\displaystyle 1 \ll \|v\|_H \leq 1$

if ${\delta}$ is small enough (and ${\epsilon}$ sufficiently small depending on ${\delta}$ ).

Now we investigate the approximate invariance properties of ${v}$ . Let ${\tilde S}$ be a compact generating subset of ${\tilde G}$ (not depending on ${\delta}$ or ${\epsilon}$ ). For ${g \in K'}$ and ${s \in \tilde S}$ , the preceding argument gives

$\displaystyle \| v(g) - \Pi_{\tilde G/G} f(g) v \|_H \ll_\delta \epsilon$

and

$\displaystyle \| v(s^{-1} g) - \Pi_{\tilde G/G} f(s^{-1} g) v \|_H \ll_\delta \epsilon$

and thus (by choice of ${\Pi_{\tilde G/G} f}$ )

$\displaystyle \| v(g) - v(s^{-1} g) \|_H \ll_\delta \epsilon$

whenever ${g \in K \cap s K}$ (again abusing notation). This is a measure ${1-O(\delta)}$ subset of ${\tilde G/G}$ . From this and (6) we see that

$\displaystyle \| v - \tilde \rho(s) v \|_{\tilde H} \leq O_\delta(\epsilon) + O(\delta^{1/2}).$

Since ${\tilde G}$ has property (T), we conclude (if ${\delta}$ is small enough, and ${\epsilon}$ sufficiently small depending on ${\delta}$ ) that there exists a non-zero ${\tilde G}$ -invariant vector ${w \in \tilde H}$ . Thus, for all ${g \in \tilde G}$ , one has ${w(g x) = w(x)}$ for almost all ${x \in \tilde G}$ (using Haar measure on ${\tilde G}$ , of course). By the Fubini-Tonelli theorem, this implies that for almost all ${x}$ , one has ${w(g x) = w(x)}$ for almost all ${g \in \tilde G}$ . Fixing such a ${x}$ , we conclude in particular that ${w}$ is almost everywhere equal to a constant ${w_0 \in H}$ . By another application of Fubini-Tonelli, this implies the existence of a coset ${xG}$ on which ${w}$ is almost everywhere equal to ${w_0}$ (this time using the Haar measure coming from ${G}$ ). By (4), this makes ${w_0}$ ${G}$ -invariant, and thus zero by choice of ${H}$ . But this makes ${w}$ zero almost everywhere, contradicting the non-zero nature of ${w}$ . $\Box$

A discrete subgroup ${\Gamma}$ of a locally compact group ${G}$ with finite covolume is known as a lattice. Thus, for instance, ${{\bf Z}^d}$ is a lattice in ${{\bf R}^d}$ . Here is another important example of a lattice, involving the special linear groups ${SL_d}$ :

Proposition 10 For any ${d \geq 1}$ , ${SL_d({\bf Z})}$ is a lattice in ${SL_d({\bf R})}$ .

Proof: Clearly ${SL_d({\bf Z})}$ is discrete, so it suffices to show that there is a finite Haar measure on ${SL_d({\bf R})/SL_d({\bf Z})}$ . It will suffice to show that there is a subset ${E}$ of ${SL_d({\bf R})}$ of finite measure (with respect to a Haar measure on ${SL_d({\bf R})}$ , of course) whose projection onto ${SL_d({\bf R})/SL_d({\bf Z})}$ is surjective. Indeed, if this is the case, then one can construct a fundamental domain ${K}$ in ${E}$ by selecting, for each left coset ${g SL_d({\bf Z})}$ of ${SL_d({\bf Z})}$ , a single element of ${g SL_d({\bf Z}) \cap E}$ in some measurable fashion (noting that this set is discrete and so has finite intersection with every compact set, allowing one to locate minimal elements with respect to some measurable ordering on ${SL_d({\bf R})}$ ). As the translates of ${K}$ by the countable group ${SL_d({\bf Z})}$ cover ${SL_d({\bf R})}$ , ${K}$ must have positive measure; and one can then construct a Haar measure on ${SL_d({\bf R})/SL_d({\bf Z})}$ by pushing forward the Haar measure on ${K}$ .

One can interpret ${SL_d({\bf R})}$ as the space of all lattices in ${{\bf R}^d}$ generated by ${d}$ marked generators ${v_1,\ldots,v_d \in {\bf R}^d}$ which are unimodular in the sense that ${\det(v_1,\ldots,v_d)=1}$ . The quotient space ${SL_d({\bf R})/SL_d(Z)}$ can then be viewed as the space of all unimodular lattices without marked generators (since the action of ${SL_d({\bf Z})}$ simply serves to move one set of generators to another). Our task is thus to find a finite measure set of unimodular lattices with marked generators, which cover all unimodular lattices.

It will be slightly more convenient to work with ${GL_d({\bf R})}$ instead of ${SL_d({\bf R})}$ – i.e. the space of all lattices (not necessarily unimodular) with marked generators ${v_1, \ldots,v_d}$ . The reason for this is that there is a very simple Haar measure on ${GL_d({\bf R})}$ , namely the Lebesgue measure ${dv_1 \ldots dv_d}$ on the generators (or equivalently, the measure induced from the open embedding ${GL_d({\bf R}) \subset {\bf R}^{d^2}}$ ); this is easily verified to be a Haar measure. One can then use dilation to convert a Haar measure on ${GL_d({\bf R})}$ to one on ${SL_d({\bf R})}$ , for instance by declaring the ${SL_d({\bf R})}$ Haar measure of a set ${E \subset SL_d({\bf R})}$ to be the ${GL_d({\bf R})}$ Haar measure of the set ${\{ t A: t \in [1,2]; A \in E \}}$ . Our task is now to find a finite measure set of lattices with marked generators, which cover all lattices of covolume in the interval ${[1,2^d]}$ . Clearly one can replace ${[1,2^d]}$ here by any other compact interval in the positive real line.

This claim is trivial for ${d=1}$ , so suppose inductively that ${d>1}$ , and that the claim has already been proven for ${d-1}$ . From Minkowski’s theorem, every lattice ${\Gamma}$ of covolume in ${[1,2^d]}$ contains a non-zero vector ${v_d}$ of norm ${O(1)}$ , where we allow implied constants to depend on ${d}$ . We may assume this vector to be irreducible, so that ${\Gamma}$ is generated by ${v_d}$ and ${d-1}$ other generators ${v_1,\ldots,v_{d-1}}$ that are independent of ${v_d}$ . By subtracting or adding an integer multiple of ${v_d}$ to these other generators, we may assume that they take the form ${v_i = w_i + t_i n_d}$ for some ${w_i}$ orthogonal to ${v_i}$ and some ${t_i \in [0,|v_d|]}$ for each ${i=1,\ldots,d-1}$ , where ${n_d := v_d/|v_d|}$ is the direction vector of ${v_d}$ . Furthermore, ${w_1,\ldots,w_{d-1}}$ span a lattice in the ${d-1}$ -dimensional space ${n_d^\perp}$ of covolume comparable to ${1/|v_d|}$ .

For each fixed ${v_d}$ , the parameters ${t_1,\ldots,t_{d-1}}$ range over a cube of ${d-1}$ -dimensional Lebesgue measure ${|v_d|^{d-1}}$ . By induction hypothesis and a rescaling argument, the ${w_1,\ldots,w_{d-1}}$ can be made (after identifying ${n_d^\perp}$ arbitrarily with ${{\bf R}^{d-1}}$ ) to range over a set of ${GL_{d-1}({\bf R})}$ of Haar measure ${O( 1 / |v_d| )}$ . By the Fubini-Tonelli theorem (and the rotation-invariance of Lebesgue measure), we may thus cover all the lattices of covolume in ${[1,2^d]}$ in ${{\bf R}^d}$ by a subset of ${GL_d({\bf R})}$ of measure at most

$\displaystyle \int_{v_d \in {\bf R}^d: |v_d| = O(1)} |v_d|^{d-1} O( 1/|v_d| )\ dv_d$

which evaluates to ${O(1)}$ , and the claim follows. $\Box$

Combining this fact with Proposition 9, we obtain

Corollary 11 For any ${d \geq 1}$ , ${SL_d({\bf R})}$ has property (T) if and only if ${SL_d({\bf Z})}$ has property (T).

The usefulness of this corollary lies in the fact that there is a certain asymptotic conjugation argument of Mautner and Moore which is available for connected Lie groups such as ${SL_d({\bf R})}$ , but not for discrete groups such as ${SL_d({\bf Z})}$ , and allows one to boost the invariance properties of a vector; see Proposition 18 below.

We will now study the property (T) nature of the special linear group.

Remark 6 Another consequence of Proposition 9 (and Remark 3) is that if a locally compact group ${\tilde G}$ has property (T), then all lattices ${G}$ in ${\tilde G}$ are finitely generated; this was one of Kazhdan’s original applications of property (T). (Strictly speaking, one has to modify the proof of Proposition 9 to obtain this application, because one is not allowed to assume that ${G}$ is compactly generated any more; however, if one inspects the proof, one sees that the set ${S}$ in that proof does not need to generate all of ${G}$ , but merely needs to generate those ${h}$ for which ${gh}$ lies in the support of ${f}$ for some ${g \in K'}$ . As this is already a compact set, we can remove the hypothesis that ${G}$ is compactly generated.) It is surprisingly difficult to replicate this result for, say, ${SL_3({\bf R})}$ , without using property (T) (or something very close to it).

— 3. The special linear group and property (T) —

The purpose of this section is to prove the following theorem of Kazhdan:

Theorem 12 ${SL_d({\bf R})}$ has property (T) if and only if ${d \neq 2}$ .

Combining this theorem with Corollary 11 and Exercise 14, we obtain some explicit families of expanders:

Corollary 13 (Margulis’ expander construction) If ${d \geq 3}$ and ${S}$ is a symmetric set of generators of ${SL_d({\bf Z})}$ that does not contain the identity, then the Cayley graphs ${Cay( SL_d({\bf Z}/n{\bf Z}), \pi_n(S) )}$ form an expander family, where ${\pi_n: SL_d({\bf Z}) \rightarrow SL_d({\bf Z}/n{\bf Z})}$ is the obvious projection homomorphism.

We now prove this theorem. We first deal with the ${d=1,2}$ cases. The group ${SL_1({\bf R})}$ is trivial and thus has property (T). As for ${SL_2({\bf R})}$ , we may rule out property (T) by using the following basic fact:

Lemma 14 ${SL_2({\bf R})}$ contains a lattice isomorphic to the free group ${F_2}$ on two generators.

Indeed, from this lemma, Proposition 9, and Exercise 20, we conclude that ${SL_2({\bf R})}$ does not have property (T).

A proof of the above lemma is given in the exercise below.

Exercise 23 Let ${\Gamma}$ be the subgroup of ${SL_2({\bf Z})}$ (and hence of ${SL_2({\bf R})}$ ) generated by the elements ${a := \begin{pmatrix} 1 & 2 \\ 0 & 1\end{pmatrix}}$ and ${b := \begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix}}$ .

(i) If ${A := \{ (x,y) \in {\bf R}^2: |x| < |y| \}}$ and ${B := \{ (x,y) \in {\bf R}^2: |x| > |y| \}}$ , show that ${a^n A \subset B}$ and ${b^n B \subset A}$ for any non-zero integer ${n}$ , where ${SL_2({\bf R})}$ acts on ${{\bf R}^2}$ in the obvious manner.

(ii) Show that ${\Gamma}$ is a free group on two generators. (Hint: use (i) to show that any reduced word of ${a,b}$ that both begins and ends with ${a^{\pm 1}}$ , or begins and ends with ${b^{\pm 1}}$ , is not equal to the identity. This argument is a variant of the ping-pong lemma argument.)

(iii) Show that ${\Gamma}$ has finite index in ${SL_2({\bf Z})}$ . (Hint: Show that given an element of ${SL_2({\bf Z})}$ with columns ${v, w \in {\bf Z}^2}$ , one can multiply this element on the left by some word in ${a,b}$ to minimise the magnitude ${|v \cdot w|}$ of the dot product, until one reaches a point where ${|v \cdot w| \leq \|v\|^2, \|w\|^2}$ . Now use the Lagrange identity ${|v \cdot w|^2 + 1 = \|v\|^2 \|w\|^2}$ to conclude that ${v, w}$ have bounded size.)

(iv) Establish Lemma 14.

Now we turn to the higher-dimensional cases ${d \geq 3}$ . The idea is to first use Fourier analysis to understand the action of various simpler subgroups of ${SL_d({\bf R})}$ acting on a space ${H}$ with approximately invariant vectors, and obtain non-trivial vectors that are invariant with respect to those simpler subgroups. Then, we will use an asymptotic conjugation trick of Mautner to boost this invariance up to increasingly larger groups, until we obtain a non-trivial vector invariant under the whole group ${SL_d({\bf R})}$ . (As such, this section will presuppose some familiarity with Fourier analysis, as reviewed for instance in this blog post.)

We begin with a preliminary result, reminiscent of property (T) but in the category of probability measures.

Lemma 15 Let ${S}$ be a compact neighbourhood of the identity in ${SL_2({\bf R})}$ , and let ${\epsilon > 0}$ . Suppose that ${\mu}$ is a probability measure on ${{\bf R}^2}$ with the property that
$\displaystyle \| s_* \mu - \mu \|_{TV} \leq \epsilon$

for all ${s \in S}$ , where ${s}$ acts on ${{\bf R}^2}$ in the obvious manner, ${s_* \mu}$ is the pushforward of ${\mu}$ by ${s}$ , and ${\| \|_{TV}}$ denotes the total variation norm. Then ${\mu(\{0\}) = 1 - O(\epsilon)}$ , where the implied constant can depend on ${S}$ .

Proof: We modify the argument used to establish Exercise 23. (There are many other proofs available, but this one has the advantage of extending without difficulty to the integer setting of ${SL_2({\bf Z})}$ .) Let ${A, B, a, b}$ be as in that exercise. Then

$\displaystyle \| a_* \mu - \mu \|_{TV} = O(\epsilon)$

and thus

$\displaystyle \mu(B) \geq \mu( a A ) = \mu( A ) + O(\epsilon)$

and similarly

$\displaystyle \mu(A) \geq \mu( b B ) = \mu( B ) + O(\epsilon).$

Putting these estimates together, we conclude that

$\displaystyle \mu(B) = \mu(a A ) + O(\epsilon).$

Similarly one has

$\displaystyle \mu(B) = \mu(a^2 A) + O(\epsilon).$

Since

$\displaystyle B \backslash a^2 A \supset \{ (x,y) \in {\bf R}^2: |y| < |x| \leq 3|y| \},$

we conclude that the set ${\{ (x,y) \in {\bf R}^2: |y| < |x| \leq 3|y| \}}$ has measure ${O(\epsilon)}$ . Translating this set around by a finite number of explicit elements of ${SL_2({\bf R})}$ , we conclude that ${\mu( {\bf R}^2 \backslash \{0\} ) = O(\epsilon)}$ , and the claim follows. $\Box$

Now we use Fourier analysis to pass from probability measures back to Hilbert spaces. We will need a fundamental result from abstract harmonic analysis, namely Bochner’s theorem:

Proposition 16 (Bochner’s theorem for ${{\bf R}^d}$ ) Let ${f: {\bf R}^d \rightarrow {\bf C}}$ be a bounded continuous function which is positive semi-definite, in the sense that ${f(x)=\overline{f(-x)}}$ for all ${x \in {\bf R}^d}$ , and
$\displaystyle \int_{{\bf R}^d} \int_{{\bf R}^d} f(x-y)\ d\nu(x) d\overline{\nu}(y) \geq 0 \ \ \ \ \ (7)$

for all finite complex measures ${\nu}$ . Then there exists a non-negative finite measure ${\mu}$ on ${{\bf R}^d}$ such that ${f}$ is the inverse Fourier transform of ${\mu}$ , in the sense that
$\displaystyle f(x) = \int_{{\bf R}^d} e^{2\pi i x \cdot \xi}\ d\mu(\xi)$

for all ${x \in {\bf R}^d}$ .

Proof: Suppose first that ${f}$ was square-integrable. Then by Plancherel’s theorem, there is a square-integrable Fourier transform ${\hat f}$ for which one has

$\displaystyle f(x) = \int_{{\bf R}^d} e^{2\pi i x \cdot \xi} \hat f(\xi)\ d\xi$

in the sense of tempered distributions (or in an ${L^2}$ approximation sense). From (7) (applied to a smooth measure ${d\nu(x) = g(x)\ dx}$ ) and standard Fourier identities, one then has

$\displaystyle \int_{{\bf R}^d} \hat f(\xi) |\hat g(\xi)|^2\ d\xi \geq 0$

for any Schwartz function ${\hat g}$ . From this and the Lebesgue differentiation theorem we see that ${\hat f}$ is non-negative almost everywhere. By testing ${f}$ against an approximation ${R^d \phi(Rx)}$ to the identity, we also see from the continuity of ${f}$ that

$\displaystyle f(0) = \lim_{R \rightarrow \infty} \int_{{\bf R}^d} \hat f(\xi) \hat \phi(\xi/R)\ d\xi$

which (after choosing ${\phi}$ to have non-negative Fourier transform) we see that ${\hat f}$ is absolutely integrable. Setting ${d\mu(\xi) := \hat f(\xi)\ d\xi}$ , one obtains the claim.

Now we consider the general case. We consider a truncation ${f_R(x) := f(x) \psi(x/R)}$ of ${f}$ for some large ${R>0}$ , where ${\psi = \eta * \eta}$ and ${\eta}$ is a real even Schwartz function with unit ${L^2}$ norm. From the identity

$\displaystyle \int_{{\bf R}^d} \int_{{\bf R}^d} f_R(x-y)\ d\nu(x) d\overline{\nu}(y) = \int_{{\bf R}^d} |\hat \eta(\xi)|^2 \int_{{\bf R}^d} f_R(x-y)\ e^{2\pi i \xi \cdot x}d \nu(x) e^{-2\pi i \xi \cdot y} d\overline{\nu}(y)$

we see that ${f_R}$ is also positive semi-definite, and is thus the Fourier transform of a finite non-negative measure ${\mu_R}$ , with ${\mu_R({\bf R}^d) = f_R(0) = f(0)}$ . Since the ${f_R}$ converge in the sense of tempered distributions to ${f}$ , ${\mu_R}$ must converge in distribution to the distributional Fourier transform of ${f}$ . In particular, by the Riesz representation theorem, ${\hat f}$ must be another finite non-negative measure, and the claim follows. $\Box$

Remark 7 Bochner’s theorem can be extended to arbitrary locally compact abelian groups, and this fact can be used to build the foundation of Fourier analysis on such groups; see for instance this text of Rudin for details. (Note though that in order to do this without circularity, one needs a different proof than the one above, which presupposes Plancherel’s theorem, which in the case of general locally compact abelian groups is usually proven using Bochner’s theorem.) There are several substitutes for Fourier analysis that can serve this purpose, such as spectral theory or the Gelfand theory of ${C^*}$ algebras, but we will not discuss these topics here.

We can use Bochner’s theorem to analyse unitary representations ${\rho: {\bf R}^d \rightarrow U(H)}$ of Euclidean groups. (Actually, much the same analysis will apply to unitary representations of arbitrary locally compact abelian groups, but we will only need to work with ${{\bf R}^d}$ (and more specifically, ${{\bf R}^2}$ ) here.) Given a vector ${v}$ in the Hilbert space ${H}$ , we consider the associated autocorrelation function ${f_{v,v}: {\bf R}^d \rightarrow {\bf C}}$ defined by the formula

$\displaystyle f_{v,v}(x) := \langle \rho(x) v, v \rangle_H$

This is a continuous bounded function of ${{\bf R}^d}$ , and from the identity

$\displaystyle \int_{{\bf R}^d} \int_{{\bf R}^d} f_{v,v}(x-y)\ d\nu(x) d\overline{\nu}(y) = \| \int_{\bf R} \rho(x) v\ d\nu(x) \|_H^2$

we see that it is positive semi-definite. Thus, by Bochner’s theorem, there exists a non-negative finite measure ${\mu_{v,v}}$ whose inverse Fourier transform is ${f_{v,v}}$ , thus

$\displaystyle \langle \rho(x) v, v \rangle_H = \int_{{\bf R}^d} e^{2\pi i x \cdot \xi}\ d\mu_{v,v}(\xi). \ \ \ \ \ (8)$

In particular, ${\mu_{v,v}}$ has total mass ${\|v\|_H^2}$ . From a quantum mechanical viewpoint, one can view ${\mu_{v,v}}$ as the probability distribution of the momentum of ${v}$ (now viewed as a quantum state, and normalising ${v}$ to be a unit vector).

By depolarisation, we can then assign a complex finite measure ${\mu_{v,w}}$ to any pair of vectors ${v,w \in H}$ such that

$\displaystyle \langle \rho(x) v, w \rangle_H = \int_{{\bf R}^d} e^{2\pi i x \cdot \xi}\ d\mu_{v,w}(\xi).$

Indeed, one can explicitly define ${\mu_{v,w}}$ using the polarisation identity as

$\displaystyle \mu_{v,w} := \frac{1}{4}( \mu_{v+w,v+w} - \mu_{v-w,v-w} + i \mu_{v+iw,v+iw} - i \mu_{v-iw,v-iw} ).$

By the uniqueness of Fourier inversion, we see that ${\mu_{v,w}}$ is uniquely determined by ${v,w}$ , and is sesquilinear with respect to these inputs. By depolarising with the right normalisations, we see that this measure has total mass ${O(\|v\|_H \|w\|_H)}$ .

Exercise 24 (Functional calculus) Show that for any bounded Borel-measurable function ${m: {\bf R}^d \rightarrow {\bf C}}$ , there is a bounded operator ${m(\rho): H \rightarrow H}$ such that
$\displaystyle \langle m(\rho) v, w \rangle = \int_{{\bf R}^d} m(\xi) d\mu_{v,w}(\xi)$

for all unit vectors ${v, w}$ , with the operator norm of ${m(\rho)}$ bounded by the supremum norm of ${m}$ . Furthermore, show the map ${m \mapsto m(\rho)}$ is a *-homomorphism of *-algebras. In particular, for any Borel set ${E}$ , the operator ${\mu(E) := 1_E(\rho)}$ is an orthogonal projection on ${H}$ . Show that ${\mu}$ is a countably additive measure taking values as orthogonal projections on ${H}$ , with ${\mu({\bf R}^d)}$ equal to the identity operator on ${H}$ . Define a notion of integration with respect to such measures in such a way that one has the identities
$\displaystyle \rho(x) = \int_{{\bf R}^d} e^{2\pi i x \cdot \xi}\ d\mu(\xi)$

and
$\displaystyle m(\rho) = \int_{{\bf R}^d} m(\xi)\ d\mu(\xi)$

for all ${x \in {\bf R}^d}$ and bounded Borel-measurable ${m}$ . (This exercise is not explicitly used in the sequel, though the functional calculus perspective is definitely lurking beneath the surface in the arguments below. One can use the results of this exercise to establish Stone’s theorem on one-parameter groups, but we will not do so here.)

Now we can obtain a relative version of property (T), relating the Euclidean group ${{\bf R}^2}$ with the semi-direct product ${SL_2({\bf R}) \ltimes {\bf R}^2}$ , defined in the obvious manner.

Proposition 17 Let ${S}$ be a compact neighbourhood of the identity in ${SL_2({\bf R}) \ltimes {\bf R}^2}$ , and let ${\rho: SL_2({\bf R}) \ltimes {\bf R}^2 \rightarrow U(H)}$ be a unitary representation. If ${Kaz( SL_2({\bf R}) \ltimes {\bf R}^2, S, H )}$ is sufficiently small depending on ${S}$ , then ${H}$ contains a non-trivial ${{\bf R}^2}$ -invariant vector.

Remark 8 Another way of stating the conclusion of this proposition is that the pair ${(SL_2({\bf R}) \ltimes {\bf R}^2, {\bf R}^2)}$ of locally compact groups has relative property (T). See the text of Bekka, de la Harpe, and Valette for a more thorough discussion of this property.

Proof: Suppose that ${Kaz( SL_2({\bf R}) \ltimes {\bf R}^2, S, H ) < \epsilon}$ for some sufficiently small ${\epsilon>0}$ , then there is a unit vector ${v}$ in ${H}$ such that ${\|\rho(s)v-v\|_H \leq \epsilon}$ for all ${s \in S}$ . Now let ${g}$ be an element of ${SL_2({\bf R})}$ (which we can view as a subgroup of ${SL_2({\bf R}) \ltimes {\bf R}^2}$ , and similarly for ${{\bf R}^2}$ ). Observe that

$\displaystyle \langle \rho(x) \rho(g) v, \rho(g) v \rangle_H = \langle \rho(g(x)) v , v \rangle_H$

for all ${x \in {\bf R}^2}$ . Comparing this with the Fourier inversion formula (8) we see that

$\displaystyle \mu_{\rho(g)v,\rho(g)v} = (g^*)_* \mu_{v,v},$

where ${(g^*)_*}$ is the pushforward by the adjoint ${g^*}$ of ${g}$ . By the sesquilinearity and boundedness of ${\mu_{v,w}}$ , we thus see that

$\displaystyle \| (g^*)_* \mu_{v,v} - \mu_{v,v} \|_{TV} \ll \| \rho(g) v - v \|_H.$

By Lemma 15, we conclude that

$\displaystyle \mu_{v,v}(\{0\}) \geq 1 - O(\epsilon)$

which, by (8), implies that

$\displaystyle \langle \rho(x) v, v \rangle_H = 1 - O(\epsilon)$

for all ${x \in {\bf R}^2}$ . Using Exercise 15, we conclude that ${H}$ has a non-trivial ${{\bf R}^2}$ -invariant vector, as claimed. $\Box$

The above proposition gives a vector which is invariant with respect to the action of an abelian group, namely ${{\bf R}^2}$ . The next lemma, using an argument of Moore exploiting an asymptotic conjugation idea of Mautner, shows how to boost invariance from a small abelian group to a larger non-abelian group. We will only need this argument in the context of ${SL_2({\bf R})}$ , and using the three subgroups

$\displaystyle U^+ := \{ u_+(t) : t \in {\bf R} \}$

$\displaystyle D := \{ d(t): t \in {\bf R} \}$

$\displaystyle U^- := \{ u_-(t): t \in {\bf R} \}$

of ${SL_2({\bf R})}$ , where

$\displaystyle u_+(t) := \begin{pmatrix} 1 & t \\ 0 & 1 \end{pmatrix}$

$\displaystyle d(t) := \begin{pmatrix} e^t & 0 \\ 0 & e^{-t} \end{pmatrix}$

$\displaystyle u_-(t) := \begin{pmatrix} 1 & 0 \\ t & 1 \end{pmatrix}.$

Proposition 18 (Mautner phenomenon) Let ${\rho: SL_2({\bf R}) \rightarrow U(H)}$ be a unitary representation. Then any vector ${v}$ which is ${U^+}$ -invariant, is also ${SL_2({\bf R})}$ invariant.

Proof: The main idea (due to Moore) is to show that ${D}$ can be approximated by double cosets ${U^+ u_-(\epsilon) U^+}$ for ${\epsilon}$ arbitrarily small. More precisely, we will use the identity

$\displaystyle \begin{pmatrix} e^t & 0 \\ \epsilon & e^{-t} \end{pmatrix} = u_+(\frac{e^t-1}{\epsilon}) u_-(\epsilon) u_+( \frac{e^{-t}-1}{\epsilon} ) \in U^+ u_-(\epsilon) U^+$

for any ${t \in {\bf R}}$ and ${\epsilon > 0}$ . In particular, from the ${U^+}$ -invariance of ${v}$ , we have

$\displaystyle \langle \rho(\begin{pmatrix} e^t & 0 \\ \epsilon & e^{-t} \end{pmatrix}) v, v \rangle_H = \langle u_-(\epsilon) v, v \rangle_H.$

Sending ${\epsilon \rightarrow 0}$ we conclude that

$\displaystyle \langle d(t) v, v \rangle_H = \langle v, v \rangle_H;$

since ${d(t) v}$ has the same length as ${v}$ , we conclude that ${d(t) v = v}$ , thus ${v}$ is ${D}$ -invariant. Now we use a similar argument of Mautner to finish up. Starting with the identity

$\displaystyle d(t) u_-(s) d(-t) = u_-(e^{-t} s)$

for ${s,t \in {\bf R}}$ , we see from the ${D}$ -invariance of ${v}$ that

$\displaystyle \langle u_-(s) v, v \rangle = \langle u_-(e^{-t} s) v, v \rangle.$

Sending ${t \rightarrow \infty}$ and arguing as before we conclude that ${v}$ is also ${U^-}$ -invariant. Since ${U^+, D, U^-}$ generate ${SL_2({\bf R})}$ , the claim follows. $\Box$

Remark 9 As a corollary of the above proposition, we see that if a probability space ${(X,\mu)}$ with a measure-preserving action of ${SL_2({\bf R})}$ is ergodic with respect to the ${SL_2({\bf R})}$ action (in the sense that all ${SL_2({\bf R})}$ -invariant sets have either full measure or zero measure, or equivalently that ${L^2(X,\mu)_0}$ has no non-trivial ${SL_2({\bf R})}$ -invariant vectors), then it is necessarily ergodic with respect to the ${U^+}$ action as well. Thus, for instance, the action of ${U^+}$ on ${SL_2({\bf R})/SL_2({\bf Z})}$ (which is known as the horocycle flow) is ergodic. This is a special case of an ergodic theorem of Moore.

We can now establish that ${SL_3({\bf R})}$ has property (T) by navigating between various subgroups of that group. Indeed, let ${S}$ be a compact neighbourhood of the identity in ${SL_3({\bf R})}$ , and suppose that ${\rho: SL_3({\bf R}) \rightarrow U(H)}$ is a unitary representation with ${Kaz(SL_3({\bf R}),S,\rho)}$ sufficiently small. We need to show that ${H}$ contains an ${SL_3({\bf R})}$ -invariant vector. To do this, we first note that ${SL_3({\bf R})}$ contains a copy of the semi-direct product ${SL_2({\bf R}) \ltimes {\bf R}^2}$ , namely the space of all matrices in ${SL_3({\bf R})}$ of the form

$\displaystyle \begin{pmatrix} * & * & * \\ * & * & * \\ 0 & 0 & 1 \end{pmatrix}$

where the entries marked ${*}$ are unconstrained (beyond the ${SL_3}$ requirement that the entire matrix have determinant ${1}$ ). Applying Proposition 17, we conclude that ${H}$ contains a non-trivial vector ${v}$ which is invariant with respect to the matrices of the form

$\displaystyle \begin{pmatrix} 1 & 0 & * \\ 0 & 1 & * \\ 0 & 0 & 1 \end{pmatrix}. \ \ \ \ \ (9)$

Now we work with a copy of ${SL_2({\bf R})}$ in ${SL_3({\bf R})}$ , namely the matrices in ${SL_3({\bf R})}$ of the form

$\displaystyle \begin{pmatrix} * & 0 & * \\ 0 & 1 & 0 \\ * & 0 & * \end{pmatrix}. \ \ \ \ \ (10)$

The associated copy of ${U^+}$ here is a subgroup of the matrices of the form (9). Applying Proposition 18, we see that ${v}$ is invariant under the matrices in ${SL_3({\bf R})}$ of the form (9). A similar argument shows that ${v}$ is also invariant with respect to matrices in ${SL_3({\bf R})}$ of the form

$\displaystyle \begin{pmatrix} 1 & 0 & 0 \\ 0 & * & * \\ 0 & * & * \end{pmatrix}. \ \ \ \ \ (11)$

But it is easy to see (e.g. by working with the Lie algebras) that (10), (11) generate all of ${SL_3({\bf R})}$ , and the claim follows.

Exercise 25 Adapt the above argument to larger values of ${d}$ to finish the proof of Theorem 12. (Hint: one either has to extend Lemma 15 to higher dimensions, or else use a version of the Mautner argument to boost invariance with respect to, say, a copy of ${SL_3({\bf R})}$ , to invariance with respect to larger subgroups of ${SL_d({\bf R})}$ .)

— 4. A more elementary approach (optional) —

In Corollary 13 we constructed an explicit family of expander graphs, but the verification of the expander graph property was quite complicated, involving for instance the theory of induced representations, Bochner’s theorem, the Riesz representation theorem, and many other tools besides. It turns out that this is overkill; if all one wants to do is construct expanders (as opposed to establishing property (T) for various groups), one can skip much of the above theory and establish expansion by more elementary methods (one still needs some Fourier analysis, but now just for finite abelian groups). In this section we outline this approach, following the work of Gabber-Galil and Jimbo-Maruocka, as presented in the survey of Hoory, Linial, and Wigderson.

To avoid the need to exploit Mautner’s phenomenon, the example is based on the semi-direct product ${SL_2({\bf R}) \ltimes {\bf R}^2}$ (or more accurately, the lattice ${SL_2({\bf Z}) \ltimes {\bf Z}^2}$ ) rather than ${SL_d({\bf R})}$ or ${SL_d({\bf Z})}$ . More precisely, we show

Theorem 19 Let ${S}$ be a symmetric finite set generating ${SL_2({\bf Z}) \ltimes {\bf Z}^2}$ . Then the Schreier graphs ${Sch( ({\bf Z}/n{\bf Z})^2, \pi_n(S) )}$ form an one-sided expander family, where ${\pi_n: SL_2({\bf Z}) \ltimes {\bf Z}^2 \rightarrow SL_2({\bf Z}/n{\bf Z}) \ltimes ({\bf Z}/n{\bf Z})^2}$ is the obvious projection homomorphism. (Here, we allow the Schreier graphs to contain loops or repeated edges; one has to check that the theory of expander graphs used here extends to this setting, but this is routine and will be glossed over here.)

One can deduce this theorem from Proposition 17 and (a relative version of) Proposition 9. We will not do so here, but instead establish the theorem directly. We first need a discrete variant of Lemma 15:

Exercise 26 Let ${S}$ be a finite generating subset of ${SL_2({\bf Z})}$ , and let ${\epsilon > 0}$ . Suppose that ${\mu}$ is a probability measure on ${{\bf Z}^2}$ with the property that
$\displaystyle \| s_* \mu - \mu \|_{TV} \leq \epsilon$

for all ${s \in S}$ , where ${s}$ acts on ${{\bf Z}^2}$ in the obvious manner. Show that ${\mu(\{0\}) = 1 - O(\epsilon)}$ , where the implied constant can depend on ${S}$ .

Now we prove the theorem. Suppose for contradiction that the Schreier graphs do not form a one-sided expander family. Then we obtain a family of nearly invariant vectors:

Exercise 27 With the above assumption, show that after passing to a subsequence of ${n}$ ‘s, one can find a sequence ${f_n \in \ell^2( ({\bf Z}/n{\bf Z})^2 )}$ of mean zero functions of ${\ell^2}$ norm ${1}$ such that
$\displaystyle \sup_{s \in S} \| \rho_n(s) f_n - f_n \|_{\ell^2(({\bf Z}/n{\bf Z})^2)} = o(1),$

where ${\rho_n}$ is the quasiregular representation of ${SL_2({\bf Z}) \ltimes {\bf Z}^2}$ on ${({\bf Z}/n{\bf Z})^2}$ , and ${o(1)}$ denotes a quantity that goes to zero as ${n \rightarrow \infty}$ .

Let ${f_n}$ be as in the above exercise. If we let ${e_1, e_2}$ be the generators of the translation group ${{\bf Z}^2}$ , we see in particular that

$\displaystyle \| \rho_n(e_j) f_n - f_n \|_{\ell^2(({\bf Z}/n{\bf Z})^2)} = o(1)$

for ${j=1,2}$ . If we then introduce the finite Fourier transform

$\displaystyle \hat f_n(\xi_1,\xi_2) := \frac{1}{n} \sum_{x_1,x_2 \in {\bf Z}/n{\bf Z}} f_n(x_1,x_2) e^{-2\pi i (x_1 \xi_1 + x_2 \xi_2)/n},$

normalised to be an isometry on ${\ell^2(({\bf Z}/n{\bf Z})^2)}$ , we conclude from Plancherel’s theorem that

$\displaystyle \| (e^{-2\pi i \xi_j /n}-1) \hat f_n(\xi_1,\xi_2) \|_{\ell^2_{\xi_1,\xi_2}(({\bf Z}/n{\bf Z})^2)} = o(1).$

In particular, we can find a ball ${B_n}$ of radius ${o(n)}$ centred at the origin in ${({\bf Z}/n{\bf Z})^2}$ on which ${f_n}$ concentrates almost all of its ${\ell^2}$ mass:

$\displaystyle \| \hat f_n \|_{\ell^2( ({\bf Z}/n{\bf Z})^2 \backslash B_n )} = o(1).$

Let ${g_n \in \ell^2({\bf Z}^2)}$ be the restriction of ${\hat f_n}$ to ${B_n}$ , which one then identifies with a subset of ${{\bf Z}^2}$ . Then we have

$\displaystyle \|g_n\|_{\ell^2({\bf Z}^2)} = 1-o(1).$

If ${s}$ is any fixed element of ${SL_2({\bf Z})}$ , then we have

$\displaystyle \| \rho_n(s) f_n - f_n \|_{\ell^2(({\bf Z}/n{\bf Z})^2)} = o(1)$

and thus by Fourier duality

$\displaystyle \| \hat f_n \circ s^* - \hat f_n \|_{\ell^2(({\bf Z}/n{\bf Z})^2)} = o(1).$

Restricting to ${B_n}$ and then embedding into ${{\bf Z}^2}$ , we conclude that

$\displaystyle \| g_n \circ s^* - g_n \|_{\ell^2({\bf Z}^2)} = o(1).$

Applying Exercise 26, we conclude that

$\displaystyle g_n(0) = 1 - o(1).$

But as the ${f_n}$ have mean zero, we have ${g_n(0)=0}$ , giving the desired contradiction.

Remark 10 One advantage of this more elementary approach is that it is easier to obtain explicit bounds on the expansion constant of these graphs; see the paper of Jimbo-Marouka for details.

27 comments

Comments feed for this article

6 December, 2011 at 12:31 pm

Nick Cook

Not sure if it’s just me, but at the top of section 2 the Heisenberg group and commutator subgroup matrices are missing the field entries. [Corrected, thanks – T.]

7 December, 2011 at 8:40 am

Cristina

In Definition 2 (Schreier graph), last line, in the set of edges, x should be from X, not G. [Corrected, thanks – T.]

7 December, 2011 at 7:42 pm

Ryan O'Donnell

Marouka -> Maruoka [Corrected, thanks -T.]

8 December, 2011 at 3:30 pm

Harald

Dear Terry,

I must confess I am slightly confused by Exercise 21.

* In part (ii), shouldn’t the norm be e^{-epsilon |v-w|^2}, without the “1-” in front (and perhaps require v and w to be unit vectors)? Presumably you want the delta functions associated to v and w to have *large* inner product if v and w are close to each other.
* Also in part (ii): is it easy to see that the closure of the orbit (and not just the orbit itself) must live in something separable?

8 December, 2011 at 4:27 pm

Terence Tao

Oops, that was a mistake on my part (I was thinking of $\|\delta_v-\delta_w\|_{\tilde H}^2$ rather than $\langle \delta_v, \delta_w \rangle_{\tilde H}$ .)

The closure of a separable space is again separable, so I don’t see any difficulty to pass from the orbit to its closure (or more precisely, to the closure of its linear span). Actually, now that I look over the argument again, I see that as H was already separable, $\tilde H$ will be also, so this point is actually moot…

9 December, 2011 at 3:27 am

Harald

Yes, I was being silly on the second point. (Reason: I could not get out of my head the picture of a vector being pushed around a circle until the average of the delta functions of the images of the vector converged weakly to the circle’s measure. Presumably this doesn’t happen because of the funny norm.)

In Exercise 15, v\in G should be v\in H.

In the proof of Lemma 15, do you really need the ping-pong elements? Don’t you just need to bound mu on an angle at the origin – and can you cover that just by using a map a that shrinks one eigenvector and stretches the other one?

[Corrected, thanks. It is true that one can also use a single semisimple element instead of a pair of unipotent elements to demonstrate Lemma 15, but the argument given has the advantage of also working without any change over the integers. (Of course, there are also non-trivial semisimple elements in SL_2(Z), but the numerology becomes a bit uglier.) Also, I wanted to highlight the role of ping pong arguments, which tend to be a particularly flexible method (as one in principle has the entire free group to work with).) – T.]

10 December, 2011 at 4:24 am

Harald Helfgott

Where is exercise 24 being used? In the line before it – can you write down the depolarization in full? It’s not obvious to me how to distinguish the contribution of from that of .

[I’m guessing that the HTML parser ate your < and > signs; you have to use < and > instead. Anyways, I edited the text to include the explicit depolarisation identity. I wrote the notes in such a way that the functional calculus is not actually used to the arguments, although traditionally it is used for this purpose (i.e. one analyses the invariance properties of the projection-valued spectral measure $\mu$ , rather than its various components $\mu_{v,v}$ or $\mu_{v,w}$ ). That way the arguments become a little bit more elementary, though the simplification is admittedly minor. -T.]

14 December, 2011 at 3:03 pm

Sean Eberhard

I think your combinatorial description in Exercise 3 may be slightly off, for instance, if I take my family to consist of ${\bf Z}_{2n}$ by itself, $S = \{+1,-1\}$ , and $E$ to be the even elements.

14 December, 2011 at 3:26 pm

Terence Tao

I’m not sure I understand the counterexample. Here, there is no uniform positive constant c for which $|E_n S_n| \geq (1+c) |E_n|$ , and so this is not an expander family of graphs.

14 December, 2011 at 5:23 pm

Sean Eberhard

I mean I’m taking my family to consist of a single group, say ${\bf Z}_{2n}$ for any $n$ . For concreteness say ${\bf Z}_{2}$ . (If you insist on an infinite collection, take an infinite number of copies of this group.) Then the equation $|E_n S_n| \geq (1+c)|E_n|$ forces $c=0$.

14 December, 2011 at 5:52 pm

Terence Tao

Ah, I see the issue now. I’ve repaired the description.

16 December, 2011 at 10:14 am

254B, Notes 3: Quasirandom groups, expansion, and Selberg’s 3/16 theorem « What’s new

[…] the previous set of notes we saw how a representation-theoretic property of groups, namely Kazhdan’s property (T), […]

16 December, 2011 at 10:50 am

254B, Notes 3: Quasirandom groups, expansion, and Selberg’s 3/16 theorem | t1u

[…] the previous set of notes we saw how a representation-theoretic property of groups, namely Kazhdan’s property (T), could be […]

18 December, 2011 at 5:39 pm

254B, Notes 1: Basic theory of expander graphs « Another Word For It

[…] 254B, Notes 2: Cayley graphs and Kazhdan’s property (T) […]

20 December, 2011 at 12:41 pm

The spectral theorem and its converses for unbounded symmetric operators « What’s new

[…] for all . (Hint: use Bochner’s theorem, a proof of which (at least on , which is the case of interest here) can be found for instance in these notes.) […]

20 December, 2011 at 5:33 pm

Lior Silberman

After Cor. 13 you say “The group $\mathrm{SL}_1(\mathbb{R})$ is trivial and thus does not have property (T)” — but the trivial group trivially has property (T).

[Corrected, thanks – T.]

20 December, 2011 at 5:42 pm

Lior Silberman

Also, The second displayed equation in the proof of Prop 16 is missing half the equation (I think you mean to say that the given integral is non-negative?)

[Corrected, thanks – T.]

13 January, 2012 at 7:49 pm

254B, Notes 4: The Bourgain-Gamburd expansion machine « What’s new

[…] have now seen two ways to construct expander Cayley graphs . The first, discussed in Notes 2, is to use Cayley graphs that are projections of an infinite Cayley graph on a group with […]

13 February, 2012 at 4:51 pm

254B, Notes 6: Non-concentration in subgroups « What’s new

[…] (i) Show that generates a free subgroup of . (Hint: use a ping-pong argument, as in Exercise 23 of Notes 2.) […]

13 March, 2012 at 2:12 pm

Sean Eberhard

Dear Terry,

In Remark 6 you claim that Kazhdan’s theorem about finite generation of lattices is a consequence of Remark 3 and Proposition 9. This seems to me illegitimate, given that throughout this section we seem to be taking for granted compact generation. In particular, we prove Proposition 9 by starting with a compact generating set. Is there an easy way to fix this? – Best, Sean

13 March, 2012 at 3:34 pm

Terence Tao

Yes, this was a bit awkward; for my applications I only needed the compactly generated case and so assumed it throughout for simplicity, but for other applications (such as Kazhdan’s original application) it is important to not assume compact generation a priori. But for the specific task of proving Proposition 9, the compact generation of G is not actually needed; if one inspects the argument, one sees that the set S does not need to generate all of G, but merely to generate a certain compact subset of G, namely those h such that gh lies in the support of f for some g in K’. Indeed, one could basically just set S to be that set. I’ll adjust Remark 6 to reflect this.

19 March, 2012 at 3:22 am

Sean Eberhard

You’re right, that fixes it.

Still working my way through Proposition 9: Unless I’m not looking at it right, the end of the proof seems a little oversimplified. Namely, you claim that the $G$ -invariance of $w$ implies the $G$ -invariance of $w(g)$ (for almost all $g\in\widetilde{G}$ ). That this is not the case can be seen from the case of $\widetilde{G}/G$ finite: $G$ -invariance of $w$ only implies $G$ -invariance of $w(e)$ (unless $G$ is a normal subgroup).

Actually $\widetilde{G}$ -invariance of $w$ means that for all $g$ the equation $w(g^{-1} x) = w(x)$ holds for almost all $x$ . Now we must apply Fubini in order to change the order of quantification over $g$ and $x$ , to deduce that for almost all $x$ the equation $w(g^{-1} x) = w(x)$ holds for almost all $g$ , which then implies that $w$ is almost everywhere constant. At least, this seems to be the approach in the Bekka, de la Harpe, and Valette book, Theorem E.3.1.

[Corrected, thanks – T.]

2 May, 2012 at 8:34 am

Craig H

I have a question about Exercise 13. Why is it an inequality? When we look at the finite case, I’m pretty sure it’s an equality — I think it’s even an equality when the representation is finite-dimensional. I’m trying to figure out a context when it wouldn’t be just an equality, and I’m coming up blank. If you could help out, I’d appreciate it.

Also, in Exercise 21(i), can’t we just take the Haar integral of \rho(g)v + c(g)? By convexity, the result must lie in the ball (and hence be finite), and by the left-invariance of the Haar measure, it has the behavior that we’re looking for.

3 May, 2012 at 1:16 pm

Terence Tao

Yes, the first inequality in Exercise 13 is in fact an equality (and I have now adjusted the exercise accordingly), though the second inequality is not.

For Exercise 21(i), the averaging trick only works when G is compact, or at least amenable. Otherwise, the Haar measure is infinite and there is no obvious way to perform the averaging. (But this is certainly “morally” the right way to think about the problem.)

31 May, 2013 at 7:37 am

254B, Notes 2: Cayley graphs and Kazhdan’s property (T) | What’s new | Peter's ruminations

[…] https://terrytao.wordpress.com/2011/12/06/254b-notes-2-cayley-graphs-and-kazhdans-property-t/#more-55… […]

25 October, 2013 at 10:42 am

schreier graphs and the space of groups « citedcorpse

[…] a pair of exercises on Terry Tao’s blog that give another way to do this with finite graphs and the symmetric […]

18 November, 2013 at 11:41 pm

tt | Peter's ruminations

[…] https://terrytao.wordpress.com/2011/12/06/254b-notes-2-cayley-graphs-and-kazhdans-property-t/ […]

	john on Benford’s law, Zipf…
	john on Benford’s law, Zipf…
	Terence Tao on 254A, Notes 3: The operator no…
	elegantrium on 254A, Notes 3: The operator no…
	Bharath Ramsundar on 254A, Supplement 6: A cheap ve…
	Avi Levy on 254A, Supplement 6: A cheap ve…
	Terence Tao on 254A, Supplement 6: A cheap ve…
	254A, Supplement 6:… on 254A, Notes 6: Large values of…
	Anonymous on 254A, Supplement 6: A cheap ve…
	arch1 on 254A, Notes 4: Some sieve…
	Anonymous on 254A, Supplement 6: A cheap ve…
	254A, Supplement 6:… on 254A, Notes 7: Linnik’s…
	254A, Supplement 6:… on 254A, Supplement 4: Probabilis…
	254A, Supplement 6:… on 254A, Notes 1: Elementary mult…
	254A, Supplement 6:… on The Katai-Bourgain-Sarnak-Zieg…

254B, Notes 2: Cayley graphs and Kazhdan’s property (T)

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

Google+ feed

The Polymath Blog

Mathematics in Australia

27 comments

Leave a Reply Cancel reply

For commenters

Follow “What's new”

254B, Notes 2: Cayley graphs and Kazhdan’s property (T)

Share this:

Like this:

Related

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

Google+ feed

The Polymath Blog

Mathematics in Australia

27 comments

Leave a Reply Cancel reply

For commenters

Follow “What's new”