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 2 The graph in Exercise 3 of Notes 1 is the Cayley graph on
with generators
.
Remark 3 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 4 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 groupto 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 the Schreier graph
is defined to be the graph with vertex set
and edge set
.
Example 6 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 7 If
is an even integer, show that every
-regular graph is a Schreier graph involving a set
of generators of cardinality
. (Hint: you may assume without proof Petersen’s 2-factor theorem, which asserts that every
-regular graph with
even can be decomposed into
edge-disjoint
-regular graphs. Now 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
obeys either (2) or (3).
We saw in the last set of notes that expansion can be characterised in terms of random walks. One can of course specialise this characterisation to the Cayley graph case:
Exercise 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. 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 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 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, ifis 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 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 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 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 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 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 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 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 19 (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 20 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 21 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:
Exercise 22 Let
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 23 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.
Exercise 24 Let
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 25 Let
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 26 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 27 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 28 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 29 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 30 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 31 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 32 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 33 Show 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 36 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 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).
Letbe 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 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 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 40 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 41 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 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 43 Let
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 44 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:
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 46 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 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
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
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 47 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
), 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 48 For 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 49 Another 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 52
contains 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 53 Let
be the subgroup of
(and hence of
) generated by the elements
and
.
- (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 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 54 Let
be a compact neighbourhood of the identity in
, and let
. Suppose that
is a probability measure on
with the property that
for 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
, and
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 56 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
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 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
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 58 Let
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 59 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 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 61 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 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 62 Adapt 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 63 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 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 64 Let
be a finite generating subset of
, and let
. Suppose that
is a probability measure on
with the property that
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 65 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 64, we conclude that
But as the have mean zero, we have
, giving the desired contradiction.
Remark 66 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.
30 comments
Comments feed for this article
6 December, 2011 at 12:31 pm
Nick Cook
Not sure if it’s just me, but at the top of section 2 the Heisenberg group and commutator subgroup matrices are missing the field entries. [Corrected, thanks – T.]
7 December, 2011 at 8:40 am
Cristina
In Definition 2 (Schreier graph), last line, in the set of edges, x should be from X, not G. [Corrected, thanks – T.]
7 December, 2011 at 7:42 pm
Ryan O'Donnell
Marouka -> Maruoka [Corrected, thanks -T.]
8 December, 2011 at 3:30 pm
Harald
Dear Terry,
I must confess I am slightly confused by Exercise 21.
* In part (ii), shouldn’t the norm be e^{-epsilon |v-w|^2}, without the “1-” in front (and perhaps require v and w to be unit vectors)? Presumably you want the delta functions associated to v and w to have *large* inner product if v and w are close to each other.
* Also in part (ii): is it easy to see that the closure of the orbit (and not just the orbit itself) must live in something separable?
8 December, 2011 at 4:27 pm
Terence Tao
Oops, that was a mistake on my part (I was thinking of
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
Harald
Yes, I was being silly on the second point. (Reason: I could not get out of my head the picture of a vector being pushed around a circle until the average of the delta functions of the images of the vector converged weakly to the circle’s measure. Presumably this doesn’t happen because of the funny norm.)
In Exercise 15, v\in G should be v\in H.
In the proof of Lemma 15, do you really need the ping-pong elements? Don’t you just need to bound mu on an angle at the origin – and can you cover that just by using a map a that shrinks one eigenvector and stretches the other one?
[Corrected, thanks. It is true that one can also use a single semisimple element instead of a pair of unipotent elements to demonstrate Lemma 15, but the argument given has the advantage of also working without any change over the integers. (Of course, there are also non-trivial semisimple elements in SL_2(Z), but the numerology becomes a bit uglier.) Also, I wanted to highlight the role of ping pong arguments, which tend to be a particularly flexible method (as one in principle has the entire free group to work with).) – T.]
10 December, 2011 at 4:24 am
Harald Helfgott
Where is exercise 24 being used? In the line before it – can you write down the depolarization in full? It’s not obvious to me how to distinguish the contribution of from that of .
[I’m guessing that the HTML parser ate your < and > signs; you have to use < and > instead. Anyways, I edited the text to include the explicit depolarisation identity. I wrote the notes in such a way that the functional calculus is not actually used to the arguments, although traditionally it is used for this purpose (i.e. one analyses the invariance properties of the projection-valued spectral measure
, 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 Eberhard
I 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 Tao
I’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 Eberhard
I 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 Tao
Ah, I see the issue now. I’ve repaired the description.
16 December, 2011 at 10:14 am
254B, Notes 3: Quasirandom groups, expansion, and Selberg’s 3/16 theorem « What’s new
[…] the previous set of notes we saw how a representation-theoretic property of groups, namely Kazhdan’s property (T), […]
16 December, 2011 at 10:50 am
254B, Notes 3: Quasirandom groups, expansion, and Selberg’s 3/16 theorem | t1u
[…] the previous set of notes we saw how a representation-theoretic property of groups, namely Kazhdan’s property (T), could be […]
18 December, 2011 at 5:39 pm
254B, Notes 1: Basic theory of expander graphs « Another Word For It
[…] 254B, Notes 2: Cayley graphs and Kazhdan’s property (T) […]
20 December, 2011 at 12:41 pm
The spectral theorem and its converses for unbounded symmetric operators « What’s new
[…] for all . (Hint: use Bochner’s theorem, a proof of which (at least on , which is the case of interest here) can be found for instance in these notes.) […]
20 December, 2011 at 5:33 pm
Lior Silberman
After Cor. 13 you say “The group
is trivial and thus does not have property (T)” — but the trivial group trivially has property (T).
[Corrected, thanks – T.]
20 December, 2011 at 5:42 pm
Lior Silberman
Also, The second displayed equation in the proof of Prop 16 is missing half the equation (I think you mean to say that the given integral is non-negative?)
[Corrected, thanks – T.]
13 January, 2012 at 7:49 pm
254B, Notes 4: The Bourgain-Gamburd expansion machine « What’s new
[…] have now seen two ways to construct expander Cayley graphs . The first, discussed in Notes 2, is to use Cayley graphs that are projections of an infinite Cayley graph on a group with […]
13 February, 2012 at 4:51 pm
254B, Notes 6: Non-concentration in subgroups « What’s new
[…] (i) Show that generates a free subgroup of . (Hint: use a ping-pong argument, as in Exercise 23 of Notes 2.) […]
13 March, 2012 at 2:12 pm
Sean Eberhard
Dear Terry,
In Remark 6 you claim that Kazhdan’s theorem about finite generation of lattices is a consequence of Remark 3 and Proposition 9. This seems to me illegitimate, given that throughout this section we seem to be taking for granted compact generation. In particular, we prove Proposition 9 by starting with a compact generating set. Is there an easy way to fix this? – Best, Sean
13 March, 2012 at 3:34 pm
Terence Tao
Yes, this was a bit awkward; for my applications I only needed the compactly generated case and so assumed it throughout for simplicity, but for other applications (such as Kazhdan’s original application) it is important to not assume compact generation a priori. But for the specific task of proving Proposition 9, the compact generation of G is not actually needed; if one inspects the argument, one sees that the set S does not need to generate all of G, but merely to generate a certain compact subset of G, namely those h such that gh lies in the support of f for some g in K’. Indeed, one could basically just set S to be that set. I’ll adjust Remark 6 to reflect this.
19 March, 2012 at 3:22 am
Sean Eberhard
You’re right, that fixes it.
Still working my way through Proposition 9: Unless I’m not looking at it right, the end of the proof seems a little oversimplified. Namely, you claim that the
-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 H
I have a question about Exercise 13. Why is it an inequality? When we look at the finite case, I’m pretty sure it’s an equality — I think it’s even an equality when the representation is finite-dimensional. I’m trying to figure out a context when it wouldn’t be just an equality, and I’m coming up blank. If you could help out, I’d appreciate it.
Also, in Exercise 21(i), can’t we just take the Haar integral of \rho(g)v + c(g)? By convexity, the result must lie in the ball (and hence be finite), and by the left-invariance of the Haar measure, it has the behavior that we’re looking for.
3 May, 2012 at 1:16 pm
Terence Tao
Yes, the first inequality in Exercise 13 is in fact an equality (and I have now adjusted the exercise accordingly), though the second inequality is not.
For Exercise 21(i), the averaging trick only works when G is compact, or at least amenable. Otherwise, the Haar measure is infinite and there is no obvious way to perform the averaging. (But this is certainly “morally” the right way to think about the problem.)
31 May, 2013 at 7:37 am
254B, Notes 2: Cayley graphs and Kazhdan’s property (T) | What’s new | Peter's ruminations
[…] https://terrytao.wordpress.com/2011/12/06/254b-notes-2-cayley-graphs-and-kazhdans-property-t/#more-55… […]
25 October, 2013 at 10:42 am
schreier graphs and the space of groups « citedcorpse
[…] a pair of exercises on Terry Tao’s blog that give another way to do this with finite graphs and the symmetric […]
18 November, 2013 at 11:41 pm
tt | Peter's ruminations
[…] https://terrytao.wordpress.com/2011/12/06/254b-notes-2-cayley-graphs-and-kazhdans-property-t/ […]
25 May, 2017 at 10:40 am
pietro gheri
I 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 C
I 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 Chowdhury
Equation
should have
instead of
right?
[Corrected, thanks – T.]