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

Definition 1 (Cayley graph)Let be a group, and let be a finite subset of . We assume that is symmetric (thus whenever ) and does not contain the identity (this is to avoid loops). Then the (right-invariant)Cayley graphis defined to be the graph with vertex set and edge set , thus each vertex is connected to the elements for , and so is a -regular graph.

Example 2The graph in Exercise 3 of Notes 1 is the Cayley graph on with generators .

Remark 3We call the above Cayley graphs right-invariant because every right translation on is a graph automorphism of . 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 , as it “looks the same” from every vertex. One could of course also considerleft-invariant Cayley graphs, in which is connected to rather than . However, the two such graphs are isomorphic using the inverse map , so we may without loss of generality restrict our attention throughout to left Cayley graphs.

Remark 4For minor technical reasons, it will be convenient later on to allow 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 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 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 5 (Schreier graph)Let be a finite group that acts (on the left) on a space , thus there is a map from to such that and for all and . Let be a symmetric subset of which acts freely on in the sense that for all and , and for all distinct and . Then theSchreier graphis defined to be the graph with vertex set and edge set .

Example 6Every Cayley graph is also a Schreier graph , using the obvious left-action of on itself. The -regular graphs formed from permutations that were studied in the previous set of notes is also a Schreier graph provided that for all distinct , with the underlying group being the permutation group (which acts on the vertex set in the obvious manner), and .

Exercise 7If is an even integer, show that every -regular graph is a Schreier graph involving a set of generators of cardinality . (Hint:first show that every -regular graph can be decomposed into 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 8 (Qualitative expansion)Let be a finite Cayley graph.

- (i) Show that is a one-sided -expander for for some if and only if generates .
- (ii) Show that is a two-sided -expander for for some if and only if generates , and furthermore intersects each index subgroup of .

We will however be interested in more quantitative expansion properties, in which the expansion constant is independent of the size of the Cayley graph, so that one can construct non-trivial expander families 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

of subsets of .

Exercise 9 (Combinatorial description of expansion)Let be a family of finite -regular Cayley graphs. Show that is a one-sided expander family if and only if there is a constant independent of such that for all sufficiently large and all subsets of with .

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

Exercise 10 (Abelian groups do not expand)Let be a family of finite -regular Cayley graphs, with the all abelian, and the generating . Show that are a one-sided expander family if and only if the Cayley graphs have bounded cardinality (i.e. ). (Hint:assume for contradiction that is a one-sided expander family with , and show by two different arguments that grows at least exponentially in and also at most polynomially in , 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 , defined by the formula

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 is abelian. (If one is more algebraically minded, one can also identify (when is finite, at least) with the group algebra , in which case convolution is simply the multiplication operation in this algebra.) The adjacency operator on a Cayley graph can then be viewed as a convolution

where is the probability density

where is the Kronecker delta function on . Using the spectral definition of expansion, we thus see that is a one-sided expander if and only if

whenever is orthogonal to the constant function , and is a two-sided expander if

whenever is orthogonal to the constant function .

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

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 11 (Random walk description of expansion)Let be a family of finite -regular Cayley graphs, and let be the associated probability density functions. Let be a constant.

- Show that the are a two-sided expander family if and only if there exists a such that for all sufficiently large , one has for some , where denotes the convolution of copies of .
- Show that the are a one-sided expander family if and only if there exists a such that for all sufficiently large , one has for some .

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 ). 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 ), or at least discrete, finitely generated groups (such as ), 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 ) 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 that are Hausdorff, second countable, and compactly generated (so that there is a compact set that generates 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 12 (Unitary representation)Let be a locally compact group. Aunitary representation(orrepresentation, for short) of is a (complex) separable Hilbert space (possibly infinite dimensional), together with a homomorphism from to the group of unitary transformations on . Furthermore, we require to be continuous, where we give the strong operator topology. We often abuse notation and refer to (rather than the pair ) as the representation of .Two unitary representations , are

isomorphicif there is a Hilbert space isomorphism such that for all . When one has such an isomorphism, we write .

Note that if 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 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 , being second countable, is separable, and so any orbit of a vector 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 13 (Trivial representation)Any locally compact group acts trivially on any Hilbert space by defining to be the identity on for all .

Example 14 (Regular representation)If is a discrete group, then we have the (left) regular representation of , in which the Hilbert space is , and the action is given by the formulafor and . (Note that the here is needed to make a homomorphism.) This is easily verified to be a unitary representation. One can also consider the right-regular representation that takes to , but this is easily seen to be isomorphic to the left-regular representation and will not be needed here.

More generally, if is a locally compact group equipped with a left-invariant Haar measure , one can define the (left) regular representation on by setting for all . (Note that will be separable because we are assuming 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 15 (Quasiregular representation)If is a measure space that acts on in a transitive measure-preserving fashion, then we have the (left) quasiregular representation , in which the Hilbert spac is , and the action is given by the formulafor and . Of course, the regular representation can be viewed as a special case of a quasiregular representation, as can the one-dimensional trivial representation.

Example 16 (Direct sum)If and are unitary representations of a locally compact group , then their direct sum is also a unitary representation, where is the Hilbert space of all formal sums with and with the inner productand the representation is given by the formula

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 17 (Subrepresentation)If is a unitary representation of a locally compact group , and is a closed subspace of which is -invariant (thus for all ), then we can form the restriction of to , defined by setting for all and . This is easily seen to also be a unitary representation, and is known as asubrepresentationof . By unitarity, we see that the orthogonal complement of in is an invariant space, leading to the complementary subrepresentation . One easily verifies the isomorphism

Example 18 (Invariant vectors)If is a unitary representation of a locally compact group , then the space of -invariant vectors in is a closed invariant subspace of . By the preceding example, we thus have the decompositioninto a trivial representation , and a representation 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 is a finite group and we consider the regular representation (so ), then is the one-dimensional space of constants , while is the space of functions of mean zero, so we have the decomposition

Note that if is an

infinitediscrete group, then there are already no non-trivial invariant vectors in (why?), so the decomposition in this case is trivial:

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

Definition 19 (Kazhdan constant)Let be a unitary representation of a locally compact group , and let be a compact subset of . TheKazhdan constantof and is then the supremum of all the constants for which one has the boundfor all . Thus, for instance, vanishes whenever the representation contains non-trivial invariant vectors. The Kazhdan constant of is defined as

where ranges over all unitary representations of with no non-trivial invariant vectors. A group is said to have

Kazhdan property (T)if one has for at least one compact set .

Thus, if has Kazhdan property (T), then one can find at least one compact set and some with the property that for every representation unitary with no non-trivial invariant vectors, and every , one can find such that . 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 .

Example 20Later on in these notes, we will show that and have property (T) if and only if . We will also see that a free non-abelian group on generators will never have property (T), and also no finitely generated infinite abelian group will have property (T).

Exercise 21Show that every finite group has property (T). (Hint:first show that every vector in a unitary representation is contained in a subrepresentation of dimension at most , and that all the unitary maps have order at most .) Later on, we shall establish the stronger statement that everycompactgroup has property (T).

We record some basic properties of the Kazhdan constants:

Exercise 22Let be a locally compact group, let be a representation, and let be compact subsets of .

- (i) If , then and .
- (ii) One has and .
- (iii) One has and .
- (iv) One has and for all .
- (v) If generates as a group (thus every element of is a finite word in ), show that has Kazhdan property (T) if and only if .

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

Remark 23In 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 for some compact (which we may assume without loss of generality to be a neighbourhood of the identity), and is the (necessarily open) subgroup of generated by , then the Dirac delta in the Hilbert space is -invariant and thus (by the hypothesis ) has a -invariant vector, which forces to be finite, and so is compactly generated.

Exercise 24Let be a locally compact group, let be a compact subset of . Show that the following assertions are equivalent:

- (i) .
- (ii) There exists a unitary representation with no non-trivial invariant vectors such that .
(

Hint:If , take a sequence of unitary representations of with no non-trivial invariant vectors but a sequence of increasingly -approximately-invariant vectors, and form their (infinite) direct sum.)

Exercise 25Let be a locally compact group, let be a compact subset of , and let . Show that the following assertions are equivalent:

- (i) .
- (ii) For any unitary representation (possibly containing invariant vectors), and any , one has

Exercise 26Let be a locally compact group. Show that exactly one of the following is true:

- (i) has property (T).
- (ii) There exists a sequence of representations and a sequence of unit vectors such that for all , but such that each of the contains no non-trivial invariant vectors.

Remark 27Informally, 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 is isolated from the other representations in some sense, which is the origin for the term “property (T)”. This intuition can be formalised by introducingFell’s topologyon 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 28Let be a finite -regular Cayley graph, and let . Let be the restriction of the regular representation of to the functions of mean zero.

- (i) If , show that is a one-sided -expander for some .
- (ii) Conversely, if is a one-sided -expander, show that for some .
(

Hint:Use the triangle inequality and the cosine rule: if are unit vectors with .)

Thus, to show that a sequence of -regular Cayley graphs form a one-sided expander family, it suffices to obtain a lower bound on the Kazhdan constants . There is a similar criterion for two-sided expansion:

Exercise 29Let be a finite -regular Cayley graph, and let . Let be the restriction of the regular representation of to the functions of mean zero.

- (i) If , show that is a two-sided -expander for some .
- (ii) Conversely, if is a two-sided -expander, show that for some .

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

Exercise 30Let be locally compact groups, and suppose that there is a continuous surjective homomorphism from to . Let be a compact subset of . Show that for any unitary representation of , one has . Conclude that . In particular, if has property (T), then does also.

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

Exercise 31Let be a finitely generated discrete group, and let be a symmetric subset of that generates . Let be a sequence of finite index normal subgroups of , and let be the quotient maps. Suppose that for all sufficiently large , is injective on . Show that if has property (T), then for sufficiently large 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 32Let be a unitary representation of a locally compact group . Suppose that there is a closed convex set in that contains an orbit of some element in . Show that contains an invariant vector. (Hint:Show that the set is closed, convex, and -invariant; now study an element of of minimal norm.)

Exercise 33Show that every compact group has property (T). (Hint:use Exercise 32.)

Exercise 34 (Direct products and property (T))Let be locally compact groups. Show that the product group (with the product topology, of course) has property (T) if and only if and both separately have property (T). (Hint:one direction follows from Exercise 30. To obtain the other direction, start with an approximately invariant vector for and use Exercise 25 (and Exercise 22(v)) to show that the -orbit of stays close to , then use Exercise 32.)

Exercise 35 (Short exact sequences and property (T))Let be a locally compact group, and let be a closed normal subgroup of ; then and are also locally compact. Show that if and have property (T), then also has property (T).

Exercise 36Let be an infinite discrete finitely generated group, generated by a finite set . Show that the following assertions are equivalent:

- (i) There exists a sequence of finite non-empty subsets in with the property that as for each . (Such a sequence of sets is known as a Folner sequence for .)
- (ii) One has , where is the regular representation of .
(

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

Infinite, finitely generated groups 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).

- (i) Show that the integers 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 with infinite abelianisation does not have property (T).
- (iv) Show that for any , the free group on generators does not have property (T).

Exercise 38 (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 be a unitary representation of a locally compact group . Define a

-cocycleto be a continuous function obeying thecocycle equationfor all . (Equivalently, a -cocycle determines an affine isometric action of on with as the unitary component of the action.) Define a

-coboundaryto be a function of the formfor some fixed vector (or equivalently, an affine isometric action of on with a common fixed point ); observe that every -coboundary is automatically a -cocycle.

- (i) Show that a -cocycle is a -coboundary if and only if it is bounded. (
Hint:if is a bounded -cocycle, then for any vector the orbit of lies in a ball. Exploit convexity to construct a shrinking sequence of such balls and use the completeness of pass to the limit.)- (ii) Show that if has property (T), then every -cocycle is a -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 that is the completion of the finitely supported measures on , using an inner product such as for some sufficiently small (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 will imply the separability of .)- (iii) Conversely, show that if for every unitary representation , every -cocycle is a -coboundary, then has property (T). (
Hint:First show that (by taking a direct sum of counterexamples, as in Exercise 24) that if is a compact neighbourhood of the identity that generates , is any unitary representation, and is a -cocycle, then , where depends on but is independent of or . Apply this fact to a coboundary generated by an approximate vector.)

** — 2. Induced representations and property (T) — **

Let be a locally compact group, and let be a subgroup of which is closed (and thus also locally compact). Clearly, every unitary representation of can be restricted to form a unitary representation of . It is then natural to ask whether the converse is also true, that is to say whether any unitary representation of can be extended to a representation of on the same Hilbert space .

In general, the answer is no. For instance, if is the Heisenberg group , and is the commutator group , then any one-dimensional representation must annihilate the commutator , but there are clearly non-trivial one-dimensional representations of which thus cannot be extended to a representation of .

However, there is a fundamental construction that (under some mild hypotheses) takes a representation of and converts it to an induced representation of , that acts on a somewhat larger Hilbert space than (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 and , and in particular will connect property (T) for to property (T) for .

To motivate the induced representation construction, we work for simplicity in the case when and are discrete, consider the regular representations and of and respectively, where and . We wish to view the -representation as somehow being induced from the -representation :

To do this, we must somehow connect with , and with .

One natural way to proceed is to express as the union of cosets of for in some set of coset representatives. We can then split as a direct sum (at least in the model case when is finite), and each factor space can be viewed as a shift of . This does indeed give enough of a relationship between and 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 (though one can show, at the end of the construction, that the choice of was ultimately irrelevant). Also, this method develops some technical complications when the quotient space 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 of the larger Hilbert space to the smaller Hilbert space , which in the case of the regular representation is just the restriction map, .

Observe that given any vector and group element , one can form the projection in , which can be written explicitly as

for and . Thus is a function from to which obeys the symmetry

for all and . Conversely, any function obeying the symmetry (4) arises from an element of in this manner. Thus, we may identify (as a vector space, at least), with the space of functions obeying (4). Furthermore, the Hilbert space norm of can be expressed in terms of via the identity

where we use the fact (from (4)) that for all to view (by abuse of notation) as a function of rather than of . Similarly, given two vectors with associated functions , the inner product can be recovered from by the formula

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 39 (Induced representation)Let be a locally compact group, and let be a subgroup of which is closed (and thus also locally compact). Suppose that there is a non-zero Radon measure on the quotient space which is invariant under the left-action of (i.e. it is a Haar measure of ). Let be a unitary representation of . Then we define theinduced representationas follows. We define to be the (pre-)Hilbert space of all functions obeying (4) for all and , that are weakly measurable in the sense that is Borel measurable for all bounded linear functionals , and such that the normis finite, where we abuse notation as before and view as a function of . (Note from the separability of that the function is measurable.) We also define the inner product on by

and identify together elements of 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 “-space” version of the standard argument establishing that is complete for any measure space .) We then define the representation on by the formula

for all ; one can verify that this is a well-defined unitary representation.

Remark 40Given a Haar measure on and a Haar measure on , one can build a Haar measure on via the Riesz representation theorem and the integration formulafor , where we abuse notation by noting that the integrand is a -right-invariant function of , and can thus be viewed as a function on the quotient space . 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 , 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 . However, it is possible to have quotient spaces for which no Haar measure is available; for instance the group of affine transformations acts on (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 41If is an open subgroup of , and is counting measure, then the induced representation of the trivial one-dimensional representation of is the quasiregular representation of on , and the induced representation of the regular representation of is the regular representation of .

Exercise 42 (Transitivity of induction)Let be locally compact groups, such that has finite index in , and has finite index in . Show that for any unitary representation of , one has . (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 43Let be a locally compact group, and let be a finite index closed subgroup of . Then has property (T) if and only if has property (T).

*Proof:* Suppose first that has property (T). Let be a compact generating subset of . As has finite index in , we may find a finite set in such that . Let be a unitary representation, and suppose that has a unit vector such that for all , where is a small quantity (independent of ) to be determined later. We will show that lies within distance from a -invariant vector (where the implied constant can depend on but not on ), which will give the claim for small enough.

By Exercise 22(v) applied to , . By Exercise 25, we thus see that lies within from a -invariant vector, so by the triangle inequality we may assume without loss of generality (and adjusting slightly) that is -invariant. If is arbitrary, we may write for some . Then . Thus the -orbit of lies in a ball of radius centred at , and so by Exercise 32 this ball contains an invariant vector as required.

Conversely, suppose that has property (T). Let be a compact generating subset of , which we may assume without loss of generality to be a neighbourhood of the identity. Let be a unitary representation, and let be a unit vector such that

for all , where is a small quantity independent of to be chosen later. Our task is to show that lies within of a -invariant vector. Now we form the induced representation (using counting measure for ). By construction, is the space of all functions such that for all and . If we let be a finite set consisting of one representative of each left-coset of , it is easy to see that each element of is determined by its restriction to , and conversely every function from can be extended uniquely to an element of ; thus can be identified with the direct sum of copies of . Also, contains as a -invariant subspace, by identifying each vector with the function defined by setting for and for . The actions of and are then compatible in the sense that for all and .

Now consider the vector

We now study its invariance properties of this vector with respect to (which generates ). For any and , lies in a compact subset of , and thus for some in and for some in a compact subset of . Also, for fixed , the map is a permutation of . Since is a compact neighbourhood of the identity generating , we see from compactness that there is a finite such that for all . In particular, from (5) and the triangle inequality we have

Since

we conclude from the triangle inequality that

where the implied constant can depend on but not on or . As has property (T), we conclude (for small enough) using Exercise 25 that lies within of an -invariant vector . In particular, as -invariant vectors are also -invariant, is a -invariant vector in which is within of , as desired.

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 is not discrete, the original Hilbert space does not embed naturally into the induced Hilbert space (basically because now has measure zero in , so there is no obvious way to embed into ). This issue however can be dealt with by “convolving” with a suitable approximation to the identity , where is the space of continuous functions with compact support. More precisely, we have the following definition:

Definition 44Let be a locally compact group, and let be a subgroup of that is also a locally compact group. Let be a Haar measure on , and let be a Haar measure on . Let be a unitary representation, and let be the induced representation . Let , and let . Then we define the convolution of by to be the function given by the formulaOne easily verifies that is well-defined and lies in .

Related to the convolution operation will be the projection of a function , defined by the formula

where the right-hand side is right -invariant in , and can thus be viewed as a function of rather than . We have the following key technical fact:

Lemma 45 (Surjectivity)The projection operator is surjective. Furthermore, given a non-negative function in , we may find a non-negative function in with .

*Proof:* It suffices to prove the second claim. Let be a non-negative continuous function supported on some compact subset of . By compactness, one can find a compact subset of which covers in the sense that for every coset in the preimage of , the set is non-empty and open in (or equivalently, is open in ). By Urysohn’s lemma, we may find a non-negative function which equals on , and then is nonzero on . Thus we may write for some . If we let be the projection map, then we easily verify that the function lies in and is non-negative with , and the claim follows.

Now we generalise Proposition 43 to the finite covolume case:

Proposition 46Let be a locally compact group, and let be a locally compact subgroup of . Suppose that hasfinite covolumein , which means that there exists afiniteHaar measure on . Then has property (T) if and only if has property (T).

*Proof:* We may normalise the Radon measure to be a probability measure. Suppose first that has property (T). Let be a compact generating subset of , and let be chosen later. As and is compactly generated, we may use inner regularity and find a compact subset of such that , where is the projection map.

Now let be a unitary representation, and suppose that has a unit vector such that for all . As before, the goal is to show that lies within distance from a -invariant vector, which will give the claim for small enough.

By Exercise 22(v) and Exercise 25 as in the previous argument, we may assume that is -invariant. The function then descends from a bounded -valued function on to a function on . We may thus form the average

where we can define the -valued integral in the weak sense, using bounded linear functionals on and the Riesz representation theorem for Hilbert spaces, noting that is weakly integrable in the sense that is absolutely integrable for all bounded linear functionals . By the left-invariance of we see that is -invariant. Also, by construction, we have for all , and for all , which has measure . As such we see that , and the claim follows.

Now suppose instead that has property (T). Let be a compact generating subset of , which we may assume without loss of generality to be a neighbourhood of the identity. Let be a unitary representation, and let be a unit vector obeying (5) for all , and some small (depending only on and to be chosen later). We will suppose for contradiction that contains no non-trivial -invariant vectors.

As before, the first step is to build the induced representation of , using the given Haar measure . Let be a sufficiently small quantity (depending on , but not depending on ) to be chosen later. By inner regularity, we can find a compact subset of of measure . By Urysohn’s lemma followed by Lemma 45, we may find a function such that is bounded by and equals on ; in particular, it differs by only on a set of measure . Now we consider the vector defined by the formula

thus

By the triangle inequality one has

Let be a compact subset of with containing . For and with in the support of , we see from the approximate invariance of that

and thus

In particular, we see that is equal to for all (again abusing notation and descending from to ). From this and (6) we see that

if is small enough (and sufficiently small depending on ).

Now we investigate the approximate invariance properties of . Let be a compact generating subset of (not depending on or ). For and , the preceding argument gives

and

and thus (by choice of )

whenever (again abusing notation). This is a measure subset of . From this and (6) we see that

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

A discrete subgroup of a locally compact group with finite covolume is known as a *lattice*. Thus, for instance, is a lattice in . Here is another important example of a lattice, involving the special linear groups :

Proposition 47For any , is a lattice in .

*Proof:* Clearly is discrete, so it suffices to show that there is a finite Haar measure on . It will suffice to show that there is a subset of of finite measure (with respect to a Haar measure on , of course) whose projection onto is surjective. Indeed, if this is the case, then one can construct a fundamental domain in by selecting, for each left coset of , a single element of 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 ). As the translates of by the countable group cover , must have positive measure; and one can then construct a Haar measure on by pushing forward the Haar measure on .

One can interpret as the space of all lattices in generated by marked generators which are *unimodular* in the sense that . The quotient space can then be viewed as the space of all unimodular lattices *without* marked generators (since the action of 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 instead of – i.e. the space of all lattices (not necessarily unimodular) with marked generators . The reason for this is that there is a very simple Haar measure on , namely the Lebesgue measure on the generators (or equivalently, the measure induced from the open embedding ), divided by the determinant magnitude ; this is easily verified to be a Haar measure. One can then use dilation to convert a Haar measure on to one on , for instance by declaring the Haar measure of a set to be the Haar measure of the set . Our task is now to find a finite measure set of lattices with marked generators, which cover all lattices of covolume in the interval . Clearly one can replace here by any other compact interval in the positive real line.

This claim is trivial for , so suppose inductively that , and that the claim has already been proven for . From Minkowski’s theorem, every lattice of covolume in contains a non-zero vector of norm , where we allow implied constants to depend on . We may assume this vector to be irreducible, so that is generated by and other generators that are independent of . By subtracting or adding an integer multiple of to these other generators, we may assume that they take the form for some orthogonal to and some for each , where is the direction vector of . Furthermore, span a lattice in the -dimensional space of covolume comparable to .

For each fixed , the parameters range over a cube of -dimensional Lebesgue measure . By induction hypothesis and a rescaling argument, the can be made (after identifying arbitrarily with ) to range over a set of of Haar measure . By the Fubini-Tonelli theorem (and the rotation-invariance of Lebesgue measure), we may thus cover all the lattices of covolume in in by a subset of of measure at most

which evaluates to , and the claim follows.

Combining this fact with Proposition 46, we obtain

Corollary 48For any , has property (T) if and only if 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 , but not for discrete groups such as , and allows one to boost the invariance properties of a vector; see Proposition 60 below.

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

Remark 49Another consequence of Proposition 46 (and Remark 23) is that if a locally compact group has property (T), then all lattices in are finitely generated; this was one of Kazhdan’s original applications of property (T). (Strictly speaking, one has to modify the proof of Proposition 46 to obtain this application, because one is not allowed to assume that is compactly generated any more; however, if one inspects the proof, one sees that the set in that proof does not need to generate all of , but merely needs to generate those for which lies in the support of for some . As this is already a compact set, we can remove the hypothesis that is compactly generated.) It is surprisingly difficult to replicate this result for, say, , 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:

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

Corollary 51 (Margulis’ expander construction)If and is a symmetric set of generators of that does not contain the identity, then the Cayley graphs form an expander family, where is the obvious projection homomorphism.

We now prove this theorem. We first deal with the cases. The group is trivial and thus has property (T). As for , we may rule out property (T) by using the following basic fact:

Lemma 52contains a lattice isomorphic to the free group on two generators.

Indeed, from this lemma, Proposition 46, and Exercise 37, we conclude that does not have property (T).

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

Exercise 53Let be the subgroup of (and hence of ) generated by the elements and .

- (i) If , show that and for any non-zero integer , where acts on in the obvious manner.
- (ii) Show that is a free group on two generators. (
Hint:use (i) to show that any reduced word of that both begins and ends with , or begins and ends with , is not equal to the identity. This argument is a variant of the ping-pong lemma argument.)- (iii) Show that has finite index in . (
Hint:Show that given an element of with columns , one can multiply this element on the left by some word in to minimise the magnitude of the dot product, until one reaches a point where . Now use the Lagrange identity to conclude that have bounded size.)- (iv) Establish Lemma 52.

Now we turn to the higher-dimensional cases . The idea is to first use Fourier analysis to understand the action of various simpler subgroups of acting on a space 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 . (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 54Let be a compact neighbourhood of the identity in , and let . Suppose that is a probability measure on with the property thatfor all , where acts on in the obvious manner, is the pushforward of by , and denotes the total variation norm. Then , where the implied constant can depend on .

*Proof:* We modify the argument used to establish Exercise 53. (There are many other proofs available, but this one has the advantage of extending without difficulty to the integer setting of .) Let be as in that exercise. Then

and thus

and similarly

Putting these estimates together, we conclude that

Similarly one has

Since

we conclude that the set has measure . Translating this set around by a finite number of explicit elements of , we conclude that , and the claim follows.

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 55 (Bochner’s theorem for )Let be a bounded continuous function which is positive semi-definite, in the sense that for all , andfor all finite complex measures . Then there exists a non-negative finite measure on such that is the inverse Fourier transform of , in the sense that

for all .

*Proof:* Suppose first that was square-integrable. Then by Plancherel’s theorem, there is a square-integrable Fourier transform for which one has

in the sense of tempered distributions (or in an approximation sense). From (7) (applied to a smooth measure ) and standard Fourier identities, one then has

for any Schwartz function . From this and the Lebesgue differentiation theorem we see that is non-negative almost everywhere. By testing against an approximation to the identity, we also see from the continuity of that

which (after choosing to have non-negative Fourier transform) we see that is absolutely integrable. Setting , one obtains the claim.

Now we consider the general case. We consider a truncation of for some large , where and is a real even Schwartz function with unit norm. From the identity

we see that is also positive semi-definite, and is thus the Fourier transform of a finite non-negative measure , with . Since the converge in the sense of tempered distributions to , must converge in distribution to the distributional Fourier transform of . In particular, by the Riesz representation theorem, must be another finite non-negative measure, and the claim follows.

Remark 56Bochner’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 algebras, but we will not discuss these topics here.

We can use Bochner’s theorem to analyse unitary representations 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 (and more specifically, ) here.) Given a vector in the Hilbert space , we consider the associated autocorrelation function defined by the formula

This is a continuous bounded function of , and from the identity

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

In particular, has total mass . From a quantum mechanical viewpoint, one can view as the probability distribution of the momentum of (now viewed as a quantum state, and normalising to be a unit vector).

By depolarisation, we can then assign a complex finite measure to any pair of vectors such that

Indeed, one can explicitly define using the polarisation identity as

By the uniqueness of Fourier inversion, we see that is uniquely determined by , and is sesquilinear with respect to these inputs. By depolarising with the right normalisations, we see that this measure has total mass .

Exercise 57 (Functional calculus)Show that for any bounded Borel-measurable function , there is a bounded operator such thatfor all unit vectors , with the operator norm of bounded by the supremum norm of . Furthermore, show the map is a *-homomorphism of *-algebras. In particular, for any Borel set , the operator is an orthogonal projection on . Show that is a countably additive measure taking values as orthogonal projections on , with equal to the identity operator on . Define a notion of integration with respect to such measures in such a way that one has the identities

and

for all and bounded Borel-measurable . (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 with the semi-direct product , defined in the obvious manner.

Proposition 58Let be a compact neighbourhood of the identity in , and let be a unitary representation. If is sufficiently small depending on , then contains a non-trivial -invariant vector.

Remark 59Another way of stating the conclusion of this proposition is that the pair 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 , then there is a unit vector in such that for all . Now let be an element of (which we can view as a subgroup of , and similarly for ). Observe that

for all . Comparing this with the Fourier inversion formula (8) we see that

where is the pushforward by the adjoint of . By the sesquilinearity and boundedness of , we thus see that

By Lemma 54, we conclude that

which, by (8), implies that

for all . Using Exercise 32, we conclude that has a non-trivial -invariant vector, as claimed.

The above proposition gives a vector which is invariant with respect to the action of an abelian group, namely . 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 , and using the three subgroups

of , where

Proposition 60 (Mautner phenomenon)Let be a unitary representation. Then any vector which is -invariant, is also invariant.

*Proof:* The main idea (due to Moore) is to show that can be approximated by double cosets for arbitrarily small. More precisely, we will use the identity

for any and . In particular, from the -invariance of , we have

Sending we conclude that

since has the same length as , we conclude that , thus is -invariant. Now we use a similar argument of Mautner to finish up. Starting with the identity

for , we see from the -invariance of that

Sending and arguing as before we conclude that is also -invariant. Since generate , the claim follows.

Remark 61As a corollary of the above proposition, we see that if a probability space with a measure-preserving action of is ergodic with respect to the action (in the sense that all -invariant sets have either full measure or zero measure, or equivalently that has no non-trivial -invariant vectors), then it is necessarily ergodic with respect to the action as well. Thus, for instance, the action of on (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 has property (T) by navigating between various subgroups of that group. Indeed, let be a compact neighbourhood of the identity in , and suppose that is a unitary representation with sufficiently small. We need to show that contains an -invariant vector. To do this, we first note that contains a copy of the semi-direct product , namely the space of all matrices in of the form

where the entries marked are unconstrained (beyond the requirement that the entire matrix have determinant ). Applying Proposition 58, we conclude that contains a non-trivial vector which is invariant with respect to the matrices of the form

Now we work with a copy of in , namely the matrices in of the form

The associated copy of here is a subgroup of the matrices of the form (9). Applying Proposition 60, we see that is invariant under the matrices in of the form (9). A similar argument shows that is also invariant with respect to matrices in of the form

But it is easy to see (e.g. by working with the Lie algebras) that (10), (11) generate all of , and the claim follows.

Exercise 62Adapt the above argument to larger values of to finish the proof of Theorem 50. (Hint:one either has to extend Lemma 54 to higher dimensions, or else use a version of the Mautner argument to boost invariance with respect to, say, a copy of , to invariance with respect to larger subgroups of .)

** — 4. A more elementary approach (optional) — **

In Corollary 51 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 (or more accurately, the lattice ) rather than or . More precisely, we show

Theorem 63Let be a symmetric finite set generating . Then the Schreier graphs form an one-sided expander family, where 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 58 and (a relative version of) Proposition 46. We will not do so here, but instead establish the theorem directly. We first need a discrete variant of Lemma 54:

Exercise 64Let be a finite generating subset of , and let . Suppose that is a probability measure on with the property thatfor all , where acts on in the obvious manner. Show that , where the implied constant can depend on .

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 65With the above assumption, show that after passing to a subsequence of ‘s, one can find a sequence of mean zero functions of norm such thatwhere is the quasiregular representation of on , and denotes a quantity that goes to zero as .

Let be as in the above exercise. If we let be the generators of the translation group , we see in particular that

for . If we then introduce the finite Fourier transform

normalised to be an isometry on , we conclude from Plancherel’s theorem that

In particular, we can find a ball of radius centred at the origin in on which concentrates almost all of its mass:

Let be the restriction of to , which one then identifies with a subset of . Then we have

If is any fixed element of , then we have

and thus by Fourier duality

Restricting to and then embedding into , we conclude that

Applying Exercise 64, we conclude that

But as the have mean zero, we have , giving the desired contradiction.

Remark 66One 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.

## 30 comments

Comments feed for this article

6 December, 2011 at 12:31 pm

Nick CookNot 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

CristinaIn 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'DonnellMarouka -> Maruoka

[Corrected, thanks -T.]8 December, 2011 at 3:30 pm

HaraldDear 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 TaoOops, that was a mistake on my part (I was thinking of rather than .)

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, will be also, so this point is actually moot…

9 December, 2011 at 3:27 am

HaraldYes, 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 HelfgottWhere 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 , rather than its various components or ). 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 EberhardI think your combinatorial description in Exercise 3 may be slightly off, for instance, if I take my family to consist of by itself, , and to be the even elements.

14 December, 2011 at 3:26 pm

Terence TaoI’m not sure I understand the counterexample. Here, there is no uniform positive constant c for which , and so this is not an expander family of graphs.

14 December, 2011 at 5:23 pm

Sean EberhardI mean I’m taking my family to consist of a single group, say for any . For concreteness say . (If you insist on an infinite collection, take an infinite number of copies of this group.) Then the equation forces $c=0$.

14 December, 2011 at 5:52 pm

Terence TaoAh, 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 SilbermanAfter Cor. 13 you say “The group 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 SilbermanAlso, 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 EberhardDear 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 TaoYes, 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 EberhardYou’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 -invariance of implies the -invariance of (for almost all ). That this is not the case can be seen from the case of finite: -invariance of only implies -invariance of (unless is a normal subgroup).

Actually -invariance of means that for all the equation holds for almost all . Now we must apply Fubini in order to change the order of quantification over and , to deduce that for almost all the equation holds for almost all , which then implies that 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 HI 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 TaoYes, 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/ […]

25 May, 2017 at 10:40 am

pietro gheriI have a question about the proof of proposition 17. In the bound for the total variation norm of should I use the bound on the total mass of this kind of measures? Is there a link between their total mass and their total variation norm?

Sorry to bother with such questions, I’m new to these topics.

Thanks in advance for your help!

[The phrase “total mass” before Exercise 24 has been corrected to “total variation”. -T.]14 March, 2019 at 2:41 am

Justin CI am confused by the claim made in the proof of Proposition 10 that the Lebesgue measure on is a Haar measure for this group.

It seems to me that the Lebesgue measure is invariant under addition, but not under the multiplication in the group. Don’t you need to divide the Lebesgue measure by the $d$-th power of the absolute value of the determinant to make it a Haar measure?

[Fair enough; I have corrected the text accordingly -T.]17 December, 2019 at 3:27 am

Mriganka Basu Roy ChowdhuryEquation should have instead of right?

[Corrected, thanks – T.]