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 graph is 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 1 The graph in Exercise 3 of Notes 1 is the Cayley graph on with generators .
Remark 1 We 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 consider left-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 2 For 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 2 (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 the Schreier graph is defined to be the graph with vertex set and edge set .
Example 2 Every 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 1 If 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 2 (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 3 (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 4 (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
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 5 (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 3 (Unitary representation) Let be a locally compact group. A unitary representation (or representation, 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 isomorphic if 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 3 (Trivial representation) Any locally compact group acts trivially on any Hilbert space by defining to be the identity on for all .
Example 4 (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 formula
for 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 5 (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 formula
for 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 6 (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 product
and 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 7 (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 a subrepresentation of . 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 8 (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 decomposition
into 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 infinite discrete 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 4 (Kazhdan constant) Let be a unitary representation of a locally compact group , and let be a compact subset of . The Kazhdan constant of and is then the supremum of all the constants for which one has the bound
for 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 9 Later 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 6 Show 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 every compact group has property (T).
We record some basic properties of the Kazhdan constants:
- (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 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 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.
- (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.)
- (i) .
- (ii) For any unitary representation (possibly containing invariant vectors), and any , one has
Exercise 10 Let 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 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 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 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 12 Let 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 13 Let 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 14 Let 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 15 Let 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 16 Show that every compact group has property (T). (Hint: use Exercise 15.)
Exercise 17 (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 13. To obtain the other direction, start with an approximately invariant vector for and use Exercise 9 (and Exercise 7(v)) to show that the -orbit of stays close to , then use Exercise 15.)
Exercise 18 (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 19 Let 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 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 be a unitary representation of a locally compact group . Define a -cocycle to be a continuous function obeying the cocycle equation
for all . (Equivalently, a -cocycle determines an affine isometric action of on with as the unitary component of the action.) Define a -coboundary to be a function of the form
for 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 8) 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 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 5 (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 the induced representation as 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 norm
is 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 5 Given a Haar measure on and a Haar measure on , one can build a Haar measure on via the Riesz representation theorem and the integration formula
for , 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 10 If 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 22 (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.
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 7(v) applied to , . By Exercise 9, 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 15 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
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 9 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 7 Let 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 formula
One 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:
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 6 to the finite covolume case:
Proposition 9 Let be a locally compact group, and let be a locally compact subgroup of . Suppose that has finite covolume in , which means that there exists a finite Haar 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 7(v) and Exercise 9 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 8, 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
for all .
Let be a compact subset of with containing . For and with in the support of , we see from the approximate invariance of that
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 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 10 For 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 ); 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 9, we obtain
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 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 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 9 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:
Corollary 13 (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:
A proof of the above lemma is given in the exercise below.
- (i) If and , 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 14.
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.
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 .) Let be as in that exercise. Then
Putting these estimates together, we conclude that
Similarly one has
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:
for 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 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 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
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 24 (Functional calculus) Show that for any bounded Borel-measurable function , there is a bounded operator such that
for 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
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.
Remark 8 Another 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 for some sufficiently small , 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 15, we conclude that
which, by (8), implies that
for all . Using Exercise 15, 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
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 9 As 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 17, we conclude that contains a non-trivial vector which is invariant with respect to the matrices of the form
The associated copy of here is a subgroup of the matrices of the form (9). Applying Proposition 18, 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
Exercise 25 Adapt the above argument to larger values of 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 , to invariance with respect to larger subgroups of .)
— 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 (or more accurately, the lattice ) rather than or . More precisely, we show
Theorem 19 Let 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 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:
for 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 27 With the above assumption, show that after passing to a subsequence of ‘s, one can find a sequence of mean zero functions of norm such that
where 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 26, we conclude that
But as the have mean zero, we have , 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.