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

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 group to be finite. However, it will be convenient at various times to “lift” a finite Cayley graph up to an infinite one, and so we permit to be infinite in our definition of a Cayley graph.

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

Definition 5 (Schreier graph) Let be a finite group that acts (on the left) on a space , thus there is a map from to such that and for all and . Let be a symmetric subset of which acts freely on in the sense that for all and , and for all distinct and . Then 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).

(Emmanuel Kowalski) The large sieve inequalities

[This post is authored by Emmanuel Kowalski.]

This post may be seen as complementary to the post “The parity problem in sieve theory“. In addition to a survey of another important sieve technique, it might be interesting as a discussion of some of the foundational issues which were discussed in the comments to that post.

Many readers will certainly have heard already of one form or another of the “large sieve inequality”. The name itself is misleading however, and what is meant by this may be something having very little, if anything, to do with sieves. What I will discuss are genuine sieve situations.

The framework I will describe is explained in the preprint arXiv:math.NT/0610021, and in a forthcoming Cambridge Tract. I started looking at this first to have a common setting for the usual large sieve and a “sieve for Frobenius” I had devised earlier to study some arithmetic properties of families of zeta functions over finite fields. Another version of such a sieve was described by Zywina (“The large sieve and Galois representations”, preprint), and his approach was quite helpful in suggesting more general settings than I had considered at first. The latest generalizations more or less took life naturally when looking at new applications, such as discrete groups.

Unfortunately (maybe), there will be quite a bit of notation involved; hopefully, the illustrations related to the classical case of sieving integers to obtain the primes (or other subsets of integers with special multiplicative features) will clarify the general case, and the “new” examples will motivate readers to find yet more interesting applications of sieves.