You are currently browsing the tag archive for the ‘Cayley graphs’ tag.

This is a sequel to my previous blog post “Cayley graphs and the geometry of groups“. In that post, the concept of a Cayley graph of a group {G} was used to place some geometry on that group {G}. In this post, we explore a variant of that theme, in which (fragments of) a Cayley graph on {G} is used to describe the basic algebraic structure of {G}, and in particular on elementary word identities in {G}. Readers who are familiar with either category theory or group homology/cohomology will recognise these concepts lurking not far beneath the surface; we wil remark briefly on these connections later in this post. However, no knowledge of categories or cohomology is needed for the main discussion, which is primarily focused on elementary group theory.

Throughout this post, we fix a single group {G = (G,\cdot)}, which is allowed to be non-abelian and/or infinite. All our graphs will be directed, with loops and multiple edges permitted.

In the previous post, we drew the entire Cayley graph of a group {G}. Here, we will be working much more locally, and will only draw the portions of the Cayley graph that are relevant to the discussion. In this graph, the vertices are elements {x} of the group {G}, and one draws a directed edge from {x} to {xg} labeled (or “coloured”) by the group element {g} for any {x, g \in G}; the graph consisting of all such vertices and edges will be denoted {Cay(G,G)}. Thus, a typical edge in {Cay(G,G)} looks like this:

Figure 1.

One usually does not work with the complete Cayley graph {Cay(G,G)}. It is customary to instead work with smaller Cayley graphs {Cay(G,S)}, in which the edge colours {g} are restricted to a smaller subset of {G}, such as a set of generators for {G}. As we will be working locally, we will in fact work with even smaller fragments of {Cay(G,G)} at a time; in particular, we only use a handful of colours (no more than nine, in fact, for any given diagram), and we will not require these colours to generate the entire group (we do not care if the Cayley graph is connected or not, as this is a global property rather than a local one).

Cayley graphs are left-invariant: for any {a \in G}, the left translation map {x \mapsto ax} is a graph isomorphism. To emphasise this left invariance, we will usually omit the vertex labels, and leave only the coloured directed edge, like so:

Figure 2.

This is analogous to how, in undergraduate mathematics and physics, vectors in Euclidean space are often depicted as arrows of a given magnitude and direction, with the initial and final points of this arrow being of secondary importance only. (Indeed, this depiction of vectors in a vector space can be viewed as an abelian special case of the more general depiction of group elements used in this post.)

Let us define a diagram to be a finite directed graph {H = (V,E)}, with edges coloured by elements of {G}, which has at least one graph homomorphism into the complete Cayley graph {Cay(G,G)} of {G}; thus there exists a map {\phi: V \rightarrow G} (not necessarily injective) with the property that {\phi(w) = \phi(v) g} whenever {(v,w)} is a directed edge in {H} coloured by a group element {g \in G}. Informally, a diagram is a finite subgraph of a Cayley graph with the vertex labels omitted, and with distinct vertices permitted to represent the same group element. Thus, for instance, the single directed edge displayed in Figure 2 is a very simple example of a diagram. An even simpler example of a diagram would be a depiction of the identity element:


Figure 3.

We will however omit the identity loops in our diagrams in order to reduce clutter.

We make the obvious remark that any directed edge in a diagram can be coloured by at most one group element {g}, since {y=xg, y=xh} implies {g=h}. This simple observation provides a way to prove group theoretic identities using diagrams: to show that two group elements {g, h} are equal, it suffices to show that they connect together (with the same orientation) the same pair of vertices in a diagram.

Remark 1 One can also interpret these diagrams as commutative diagrams in a category in which all the objects are copies of {G}, and the morphisms are right-translation maps. However, we will deviate somewhat from the category theoretic way of thinking here by focusing on the geometric arrangement and shape of these diagrams, rather than on their abstract combinatorial description. In particular, we view the arrows more as distorted analogues of vector arrows, than as the abstract arrows appearing in category theory.

Just as vector addition can be expressed via concatenation of arrows, group multiplication can be described by concatenation of directed edges. Indeed, for any {x,g,h \in G}, the vertices {x, xg, xgh} can be connected by the following triangular diagram:

Figure 4.

In a similar spirit, inversion is described by the following diagram:

Figure 5.

We make the pedantic remark though that we do not consider a {g^{-1}} edge to be the reversal of the {g} edge, but rather as a distinct edge that just happens to have the same initial and final endpoints as the reversal of the {g} edge. (This will be of minor importance later, when we start integrating “{1}-forms” on such edges.)

A fundamental operation for us will be that of gluing two diagrams together.

Lemma 1 ((Labeled) gluing) Let {D_1 = (V_1,E_1), D_2 = (V_2,E_2)} be two diagrams of a given group {G}. Suppose that the intersection {D_1 \cap D_2 := (V_1 \cap V_2, E_1 \cap E_2)} of the two diagrams connects all of {V_1 \cap V_2} (i.e. any two elements of {V_1 \cap V_2} are joined by a path in {D_1 \cap D_2}). Then the union {D_1 \cup D_2 := (V_1 \cup V_2, E_1 \cup E_2)} is also a diagram of {G}.

Proof: By hypothesis, we have graph homomorphisms {\phi_1: D_1 \rightarrow Cay(G,G)}, {\phi_2: D_2 \rightarrow Cay(G,G)}. If they agree on {D_1 \cap D_2} then one simply glues together the two homomorphisms to create a new graph homomorphism {\phi: D_1 \cup D_2 \rightarrow Cay(G,G)}. If they do not agree, one can apply a left translation to either {\phi_1} or {\phi_2} to make the two diagrams agree on at least one vertex of {D_1 \cap D_2}; then by the connected nature of {D_1 \cap D_2} we see that they now must agree on all vertices of {D_1 \cap D_2}, and then we can form the glued graph homomorphism as before. \Box

The above lemma required one to specify the label the vertices of {D_1,D_2} (in order to form the intersection {D_1 \cap D_2} and union {D_1 \cup D_2}). However, if one is presented with two diagrams {D_1, D_2} with unlabeled vertices, one can identify some partial set of vertices of {D_1} with a partial set of vertices of {D_2} of matching cardinality. Provided that the subdiagram common to {D_1} and {D_2} after this identification connects all of the common vertices together, we may use the above lemma to create a glued diagram {D}.

For instance, if a diagram {D} contains two of the three edges in the triangular diagram in Figure 4, one can “fill in” the triangle by gluing in the third edge:

Figure 6.

One can use glued diagrams to demonstrate various basic group-theoretic identities. For instance, by gluing together two copies of the triangular diagram in Figure 4 to create the glued diagram

Figure 7.

and then filling in two more triangles, we obtain a tetrahedral diagram that demonstrates the associative law {(gh)k = g(hk)}:

Figure 8.

Similarly, by gluing together two copies of Figure 4 with three copies of Figure 5 in an appropriate order, we can demonstrate the Abel identity {(gh)^{-1} = h^{-1} g^{-1}}:

Figure 9.

In addition to gluing, we will also use the trivial operation of erasing: if {D} is a diagram for a group {G}, then any subgraph of {D} (formed by removing vertices and/or edges) is also a diagram of {G}. This operation is not strictly necessary for our applications, but serves to reduce clutter in the pictures.

If two group elements {g, h} commute, then we obtain a parallelogram as a diagram, exactly as in the vector space case:

Figure 10.

In general, of course, two arbitrary group elements {g,h} will fail to commute, and so this parallelogram is no longer available. However, various substitutes for this diagram exist. For instance, if we introduce the conjugate {g^h := h^{-1} g h} of one group element {g} by another, then we have the following slightly distorted parallelogram:

Figure 11.

By appropriate gluing and filling, this can be used to demonstrate the homomorphism properties of a conjugation map {g \mapsto g^h}:

Figure 12.

Figure 13.

Another way to replace the parallelogram in Figure 10 is to introduce the commutator {[g,h] := g^{-1}h^{-1}gh} of two elements, in which case we can perturb the parallelogram into a pentagon:

Figure 14.

We will tend to depict commutator edges as being somewhat shorter than the edges generating that commutator, reflecting a “perturbative” or “nilpotent” philosophy. (Of course, to fully reflect a nilpotent perspective, one should orient commutator edges in a different dimension from their generating edges, but of course the diagrams drawn here do not have enough dimensions to display this perspective easily.) We will also be adopting a “Lie” perspective of interpreting groups as behaving like perturbations of vector spaces, in particular by trying to draw all edges of the same colour as being approximately (though not perfectly) parallel to each other (and with approximately the same length).

Gluing the above pentagon with the conjugation parallelogram and erasing some edges, we discover a “commutator-conjugate” triangle, describing the basic identity {g^h = g [g,h]}:

Figure 15.

Other gluings can also give the basic relations between commutators and conjugates. For instance, by gluing the pentagon in Figure 14 with its reflection, we see that {[g,h] = [h,g]^{-1}}. The following diagram, obtained by gluing together copies of Figures 11 and 15, demonstrates that {[h,g^{-1}] = [g,h]^{g^{-1}}},

Figure 16.

while this figure demonstrates that {[g,hk] = [g,k] [g,h]^k}:

Figure 17.

Now we turn to a more sophisticated identity, the Hall-Witt identity

\displaystyle [[g,h],k^g] [[k,g],h^k] [[h,k],g^h] = 1,

which is the fully noncommutative version of the more well-known Jacobi identity for Lie algebras.

The full diagram for the Hall-Witt identity resembles a slightly truncated parallelopiped. Drawing this truncated paralleopiped in full would result in a rather complicated looking diagram, so I will instead display three components of this diagram separately, and leave it to the reader to mentally glue these three components back to form the full parallelopiped. The first component of the diagram is formed by gluing together three pentagons from Figure 14, and looks like this:

Figure 18.

This should be thought of as the “back” of the truncated parallelopiped needed to establish the Hall-Witt identity.

While it is not needed for proving the Hall-Witt identity, we also observe for future reference that we may also glue in some distorted parallelograms and obtain a slightly more complicated diagram:

Figure 19.

To form the second component, let us now erase all interior components of Figure 18 or Figure 19:

Figure 20.

Then we fill in three distorted parallelograms:

Figure 21.

This is the second component, and is the “front” of the truncated praallelopiped, minus the portions exposed by the truncation.

Finally, we turn to the third component. We begin by erasing the outer edges from the second component in Figure 21:

Figure 22.

We glue in three copies of the commutator-conjugate triangle from Figure 15:

Figure 23.

But now we observe that we can fill in three pentagons, and obtain a small triangle with edges {[[g,h],k^g] [[k,g],h^k] [[h,k],g^h]}:

Figure 24.

Erasing everything except this triangle gives the Hall-Witt identity. Alternatively, one can glue together Figures 18, 21, and 24 to obtain a truncated parallelopiped which one can view as a geometric representation of the proof of the Hall-Witt identity.

Among other things, I found these diagrams to be useful to visualise group cohomology; I give a simple example of this below, developing an analogue of the Hall-Witt identity for {2}-cocycles.

Read the rest of this entry »

In this final set of course notes, we discuss how (a generalisation of) the expansion results obtained in the preceding notes can be used for some nnumber-theoretic applications, and in particular to locate almost primes inside orbits of thin groups, following the work of Bourgain, Gamburd, and Sarnak. We will not attempt here to obtain the sharpest or most general results in this direction, but instead focus on the simplest instances of these results which are still illustrative of the ideas involved.

One of the basic general problems in analytic number theory is to locate tuples of primes of a certain form; for instance, the famous (and still unsolved) twin prime conjecture asserts that there are infinitely many pairs {(n_1,n_2)} in the line {\{ (n_1,n_2) \in {\bf Z}^2: n_2-n_1=2\}} in which both entries are prime. In a similar spirit, one of the Landau conjectures (also still unsolved) asserts that there are infinitely many primes in the set {\{ n^2+1: n \in {\bf Z} \}}. The Mersenne prime conjecture (also unsolved) asserts that there are infinitely many primes in the set {\{ 2^n - 1: n \in {\bf Z} \}}, and so forth.

More generally, given some explicit subset {V} in {{\bf R}^d} (or {{\bf C}^d}, if one wishes), such as an algebraic variety, one can ask the question of whether there are infinitely many integer lattice points {(n_1,\ldots,n_d)} in {V \cap {\bf Z}^d} in which all the coefficients {n_1,\ldots,n_d} are simultaneously prime; let us refer to such points as prime points.

At this level of generality, this problem is impossibly difficult. Indeed, even the much simpler problem of deciding whether the set {V \cap {\bf Z}^d} is non-empty (let alone containing prime points) when {V} is a hypersurface {\{ x \in {\bf R}^d: P(x) = 0 \}} cut out by a polynomial {P} is essentially Hilbert’s tenth problem, which is known to be undecidable in general by Matiyasevich’s theorem. So one needs to restrict attention to a more special class of sets {V}, in which the question of finding integer points is not so difficult. One model case is to consider orbits {V = \Gamma b}, where {b \in {\bf Z}^d} is a fixed lattice vector and {\Gamma} is some discrete group that acts on {{\bf Z}^d} somehow (e.g. {\Gamma} might be embedded as a subgroup of the special linear group {SL_d({\bf Z})}, or on the affine group {SL_d({\bf Z}) \ltimes {\bf Z}^d}). In such a situation it is then quite easy to show that {V = V \cap {\bf Z}^d} is large; for instance, {V} will be infinite precisely when the stabiliser of {b} in {\Gamma} has infinite index in {\Gamma}.

Even in this simpler setting, the question of determining whether an orbit {V = \Gamma b} contains infinitely prime points is still extremely difficult; indeed the three examples given above of the twin prime conjecture, Landau conjecture, and Mersenne prime conjecture are essentially of this form (possibly after some slight modification of the underlying ring {{\bf Z}}, see this paper of Bourgain-Gamburd-Sarnak for details), and are all unsolved (and generally considered well out of reach of current technology). Indeed, the list of non-trivial orbits {V = \Gamma b} which are known to contain infinitely many prime points is quite slim; Euclid’s theorem on the infinitude of primes handles the case {V = {\bf Z}}, Dirichlet’s theorem handles infinite arithmetic progressions {V = a{\bf Z} + r}, and a somewhat complicated result of Green, Tao, and Ziegler handles “non-degenerate” affine lattices in {{\bf Z}^d} of rank two or more (such as the lattice of length {d} arithmetic progressions), but there are few other positive results known that are not based on the above cases (though we will note the remarkable theorem of Friedlander and Iwaniec that there are infinitely many primes of the form {a^2+b^4}, and the related result of Heath-Brown that there are infinitely many primes of the form {a^3+2b^3}, as being in a kindred spirit to the above results, though they are not explicitly associated to an orbit of a reasonable action as far as I know).

On the other hand, much more is known if one is willing to replace the primes by the larger set of almost primes – integers with a small number of prime factors (counting multiplicity). Specifically, for any {r \geq 1}, let us call an {r}-almost prime an integer which is the product of at most {r} primes, and possibly by the unit {-1} as well. Many of the above sorts of questions which are open for primes, are known for {r}-almost primes for {r} sufficiently large. For instance, with regards to the twin prime conjecture, it is a result of Chen that there are infinitely many pairs {p,p+2} where {p} is a prime and {p+2} is a {2}-almost prime; in a similar vein, it is a result of Iwaniec that there are infinitely many {2}-almost primes of the form {n^2+1}. On the other hand, it is still open for any fixed {r} whether there are infinitely many Mersenne numbers {2^n-1} which are {r}-almost primes. (For the superficially similar situation with the numbers {2^n+1}, it is in fact believed (but again unproven) that there are only finitely many {r}-almost primes for any fixed {r} (the Fermat prime conjecture).)

The main tool that allows one to count almost primes in orbits is sieve theory. The reason for this lies in the simple observation that in order to ensure that an integer {n} of magnitude at most {x} is an {r}-almost prime, it suffices to guarantee that {n} is not divisible by any prime less than {x^{1/(r+1)}}. Thus, to create {r}-almost primes, one can start with the integers up to some large threshold {x} and remove (or “sieve out”) all the integers that are multiples of any prime {p} less than {x^{1/(r+1)}}. The difficulty is then to ensure that a sufficiently non-trivial quantity of integers remain after this process, for the purposes of finding points in the given set {V}.

The most basic sieve of this form is the sieve of Eratosthenes, which when combined with the inclusion-exclusion principle gives the Legendre sieve (or exact sieve), which gives an exact formula for quantities such as the number {\pi(x,z)} of natural numbers less than or equal to {x} that are not divisible by any prime less than or equal to a given threshold {z}. Unfortunately, when one tries to evaluate this formula, one encounters error terms which grow exponentially in {z}, rendering this sieve useful only for very small thresholds {z} (of logarithmic size in {x}). To improve the sieve level up to a small power of {x} such as {x^{1/(r+1)}}, one has to replace the exact sieve by upper bound sieves and lower bound sieves which only seek to obtain upper or lower bounds on quantities such as {\pi(x,z)}, but contain a polynomial number of terms rather than an exponential number. There are a variety of such sieves, with the two most common such sieves being combinatorial sieves (such as the beta sieve), based on various combinatorial truncations of the inclusion-exclusion formula, and the Selberg upper bound sieve, based on upper bounds that are the square of a divisor sum. (There is also the large sieve, which is somewhat different in nature and based on {L^2} almost orthogonality considerations, rather than on any actual sieving, to obtain upper bounds.) We will primarily work with a specific sieve in this notes, namely the beta sieve, and we will not attempt to optimise all the parameters of this sieve (which ultimately means that the almost primality parameter {r} in our results will be somewhat large). For a more detailed study of sieve theory, see the classic text of Halberstam and Richert, or the more recent texts of Iwaniec-Kowalski or of Friedlander-Iwaniec.

Very roughly speaking, the end result of sieve theory is that excepting some degenerate and “exponentially thin” settings (such as those associated with the Mersenne primes), all the orbits which are expected to have a large number of primes, can be proven to at least have a large number of {r}-almost primes for some finite {r}. (Unfortunately, there is a major obstruction, known as the parity problem, which prevents sieve theory from lowering {r} all the way to {1}; see this blog post for more discussion.) One formulation of this principle was established by Bourgain, Gamburd, and Sarnak:

Theorem 1 (Bourgain-Gamburd-Sarnak) Let {\Gamma} be a subgroup of {SL_2({\bf Z})} which is not virtually solvable. Let {f: {\bf Z}^4 \rightarrow {\bf Z}} be a polynomial with integer coefficients obeying the following primitivity condition: for any positive integer {q}, there exists {A \in \Gamma \subset {\bf Z}^4} such that {f(A)} is coprime to {q}. Then there exists an {r \geq 1} such that there are infinitely many {A \in \Gamma} with {f(A)} non-zero and {r}-almost prime.

This is not the strongest version of the Bourgain-Gamburd-Sarnak theorem, but it captures the general flavour of their results. Note that the theorem immediately implies an analogous result for orbits {\Gamma b \subset {\bf Z}^2}, in which {f} is now a polynomial from {{\bf Z}^2} to {{\bf Z}}, and one uses {f(Ab)} instead of {f(A)}. It is in fact conjectured that one can set {r=1} here, but this is well beyond current technology. For the purpose of reaching {r=1}, it is very natural to impose the primitivity condition, but as long as one is content with larger values of {r}, it is possible to relax the primitivity condition somewhat; see the paper of Bourgain, Gamburd, and Sarnak for more discussion.

By specialising to the polynomial {f: \begin{pmatrix} a & b \\ c & d \end{pmatrix} \rightarrow abcd}, we conclude as a corollary that as long as {\Gamma} is primitive in the sense that it contains matrices with all coefficients coprime to {q} for any given {q}, then {\Gamma} contains infinitely many matrices whose elements are all {r}-almost primes for some {r} depending only on {\Gamma}. For further applications of these sorts of results, for instance to Appolonian packings, see the paper of Bourgain, Gamburd, and Sarnak.

It turns out that to prove Theorem 1, the Cayley expansion results in {SL_2(F_p)} from the previous set of notes are not quite enough; one needs a more general Cayley expansion result in {SL_2({\bf Z}/q{\bf Z})} where {q} is square-free but not necessarily prime. The proof of this expansion result uses the same basic methods as in the {SL_2(F_p)} case, but is significantly more complicated technically, and we will only discuss it briefly here. As such, we do not give a complete proof of Theorem 1, but hopefully the portion of the argument presented here is still sufficient to give an impression of the ideas involved.

Read the rest of this entry »

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

of subsets of {G}.

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

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

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

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

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

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

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

where {\mu} is the probability density

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

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

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

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

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

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

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

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

obeys either (2) or (3).

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

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

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

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

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

Read the rest of this entry »

In most undergraduate courses, groups are first introduced as a primarily algebraic concept – a set equipped with a number of algebraic operations (group multiplication, multiplicative inverse, and multiplicative identity) and obeying a number of rules of algebra (most notably the associative law). It is only somewhat later that one learns that groups are not solely an algebraic object, but can also be equipped with the structure of a manifold (giving rise to Lie groups) or a topological space (giving rise to topological groups). (See also this post for a number of other ways to think about groups.)

Another important way to enrich the structure of a group {G} is to give it some geometry. A fundamental way to provide such a geometric structure is to specify a list of generators {S} of the group {G}. Let us call such a pair {(G,S)} a generated group; in many important cases the set of generators {S} is finite, leading to a finitely generated group. A generated group {(G,S)} gives rise to the word metric {d: G \times G \rightarrow {\bf N}} on {G}, defined to be the maximal metric for which {d(x,sx) \leq 1} for all {x \in G} and {s \in S} (or more explicitly, {d(x,y)} is the least {m} for which {y = s_1^{\epsilon_1} \ldots s_m^{\epsilon_m} x} for some {s_1,\ldots,s_m \in S} and {\epsilon_1,\ldots,\epsilon_m \in \{-1,+1\}}). This metric then generates the balls {B_S(R) := \{ x \in G: d(x,\hbox{id}) \leq R \}}. In the finitely generated case, the {B_S(R)} are finite sets, and the rate at which the cardinality of these sets grow in {R} is an important topic in the field of geometric group theory. The idea of studying a finitely generated group via the geometry of its metric goes back at least to the work of Dehn.

One way to visualise the geometry of a generated group is to look at the (labeled) Cayley colour graph of the generated group {(G,S)}. This is a directed coloured graph, with edges coloured by the elements of {S}, and vertices labeled by elements of {G}, with a directed edge of colour {s} from {x} to {sx} for each {x \in G} and {s \in S}. The word metric then corresponds to the graph metric of the Cayley graph.

For instance, the Cayley graph of the cyclic group {{\bf Z}/6{\bf Z}} with a single generator {S = \{1\}} (which we draw in green) is given as

while the Cayley graph of the same group but with the generators {S = \{2,3\}} (which we draw in blue and red respectively) is given as

We can thus see that the same group can have somewhat different geometry if one changes the set of generators. For instance, in a large cyclic group {{\bf Z}/N{\bf Z}}, with a single generator {S = \{1\}} the Cayley graph “looks one-dimensional”, and balls {B_S(R)} grow linearly in {R} until they saturate the entire group, whereas with two generators {S = \{s_1,s_2\}} chosen at random, the Cayley graph “looks two-dimensional”, and the balls {B_S(R)} typically grow quadratically until they saturate the entire group.

Cayley graphs have three distinguishing properties:

  • (Regularity) For each colour {s \in S}, every vertex {x} has a single {s}-edge leading out of {x}, and a single {s}-edge leading into {x}.
  • (Connectedness) The graph is connected.
  • (Homogeneity) For every pair of vertices {x, y}, there is a unique coloured graph isomorphism that maps {x} to {y}.

It is easy to verify that a directed coloured graph is a Cayley graph (up to relabeling) if and only if it obeys the above three properties. Indeed, given a graph {(V,E)} with the above properties, one sets {G} to equal the (coloured) automorphism group of the graph {(V,E)}; arbitrarily designating one of the vertices of {V} to be the identity element {\hbox{id}}, we can then identify all the other vertices in {V} with a group element. One then identifies each colour {s \in S} with the vertex that one reaches from {\hbox{id}} by an {s}-coloured edge. Conversely, every Cayley graph of a generated group {(G,S)} is clearly regular, is connected because {S} generates {G}, and has isomorphisms given by right multiplication {x \mapsto xg} for all {g\in G}. (The regularity and connectedness properties already ensure the uniqueness component of the homogeneity property.)

From the above equivalence, we see that we do not really need the vertex labels on the Cayley graph in order to describe a generated group, and so we will now drop these labels and work solely with unlabeled Cayley graphs, in which the vertex set is not already identified with the group. As we saw above, one just needs to designate a marked vertex of the graph as the “identity” or “origin” in order to turn an unlabeled Cayley graph into a labeled Cayley graph; but from homogeneity we see that all vertices of an unlabeled Cayley graph “look the same” and there is no canonical preference for choosing one vertex as the identity over another. I prefer here to keep the graphs unlabeled to emphasise the homogeneous nature of the graph.

It is instructive to revisit the basic concepts of group theory using the language of (unlabeled) Cayley graphs, and to see how geometric many of these concepts are. In order to facilitate the drawing of pictures, I work here only with small finite groups (or Cayley graphs), but the discussion certainly is applicable to large or infinite groups (or Cayley graphs) also.

For instance, in this setting, the concept of abelianness is analogous to that of a flat (zero-curvature) geometry: given any two colours {s_1, s_2}, a directed path with colours {s_1, s_2, s_1^{-1}, s_2^{-1}} (adopting the obvious convention that the reversal of an {s}-coloured directed edge is considered an {s^{-1}}-coloured directed edge) returns to where it started. (Note that a generated group {(G,S)} is abelian if and only if the generators in {S} pairwise commute with each other.) Thus, for instance, the two depictions of {{\bf Z}/6{\bf Z}} above are abelian, whereas the group {S_3}, which is also the dihedral group of the triangle and thus admits the Cayley graph

is not abelian.

A subgroup {(G',S')} of a generated group {(G,S)} can be easily described in Cayley graph language if the generators {S'} of {G'} happen to be a subset of the generators {S} of {G}. In that case, if one begins with the Cayley graph of {(G,S)} and erases all colours except for those colours in {S'}, then the graph foliates into connected components, each of which is isomorphic to the Cayley graph of {(G',S')}. For instance, in the above Cayley graph depiction of {S_3}, erasing the blue colour leads to three copies of the red Cayley graph (which has {{\bf Z}/2{\bf Z}} as its structure group), while erasing the red colour leads to two copies of the blue Cayley graph (which as {A_3 \equiv {\bf Z}/3{\bf Z}} as its structure group). If {S'} is not contained in {S}, then one has to first “change basis” and add or remove some coloured edges to the original Cayley graph before one can obtain this formulation (thus for instance {S_3} contains two more subgroups of order two that are not immediately apparent with this choice of generators). Nevertheless the geometric intuition that subgroups are analogous to foliations is still quite a good one.

We saw that a subgroup {(G',S')} of a generated group {(G,S)} with {S' \subset S} foliates the larger Cayley graph into {S'}-connected components, each of which is a copy of the smaller Cayley graph. The remaining colours in {S} then join those {S'}-components to each other. In some cases, each colour {s \in S\backslash S'} will connect a {S'}-component to exactly one other {S'}-component; this is the case for instance when one splits {S_3} into two blue components. In other cases, a colour {s} can connect a {S'}-component to multiple {S'}-components; this is the case for instance when one splits {S_3} into three red components. The former case occurs precisely when the subgroup {G'} is normal. (Note that a subgroup {G'} of a generated group {(G,S)} is normal if and only if left-multiplication by a generator of {S} maps right-cosets of {G'} to right-cosets of {G'}.) We can then quotient out the {(G',S')} Cayley graph from {(G,S)}, leading to a quotient Cayley graph {(G/G', S \backslash S')} whose vertices are the {S'}-connected components of {(G,S)}, and the edges are projected from {(G,S)} in the obvious manner. We can then view the original graph {(G,S)} as a bundle of {(G',S')}-graphs over a base {(G/G',S\backslash S')}-graph (or equivalently, an extension of the base graph {(G/G',S\backslash S')} by the fibre graph {(G',S')}); for instance {S_3} can be viewed as a bundle of the blue graph {A_3} over the red graph {{\bf Z}/2{\bf Z}}, but not conversely. We thus see that the geometric analogue of the concept of a normal subgroup is that of a bundle. The generators in {S \backslash S'} can be viewed as describing a connection on that bundle.

Note, though, that the structure group of this connection is not simply {G'}, unless {G'} is a central subgroup; instead, it is the larger group {G' \rtimes \hbox{Aut}(G')}, the semi-direct product of {G'} with its automorphism group. This is because a non-central subgroup {G'} can be “twisted around” by operations such as conjugation {g' \mapsto sg's^{-1}} by a generator {s \in S}. So central subgroups are analogous to the geometric notion of a principal bundle. For instance, here is the Heisenberg group

\displaystyle  \begin{pmatrix} 1 & {\bf F}_2 & {\bf F}_2 \\ 0 & 1 & {\bf F}_2 \\ 0 & 0 & 1 \end{pmatrix}

over the field {{\bf F}_2} of two elements, which one can view as a central extension of {{\bf F}_2^2} (the blue and green edges, after quotienting) by {{\bf F}_2} (the red edges):

Note how close this group is to being abelian; more generally, one can think of nilpotent groups as being a slight perturbation of abelian groups.

In the case of {S_3} (viewed as a bundle of the blue graph {A_3} over the red graph {{\bf Z}/2{\bf Z}}), the base graph {{\bf Z}/2{\bf Z}} is in fact embedded (three times) into the large graph {S_3}. More generally, the base graph {(G/G', S \backslash S')} can be lifted back into the extension {(G,S)} if and only if the short exact sequence {0 \rightarrow G' \rightarrow G \rightarrow G/G' \rightarrow 0} splits, in which case {G} becomes a semidirect product {G \equiv G' \rtimes H} of {G'} and a lifted copy {H} of {G/G'}. Not all bundles can be split in this fashion. For instance, consider the group {{\bf Z}/9{\bf Z}}, with the blue generator {1} and the red generator {3}:

This is a {{\bf Z}/3{\bf Z}}-bundle over {{\bf Z}/3{\bf Z}} that does not split; the blue Cayley graph of {{\bf Z}/3{\bf Z}} is not visible in the {{\bf Z}/9{\bf Z}} graph directly, but only after one quotients out the red fibre subgraph. The notion of a splitting in group theory is analogous to the geometric notion of a global gauge. The existence of such a splitting or gauge, and the relationship between two such splittings or gauges, are controlled by the group cohomology of the sequence {0 \rightarrow G' \rightarrow G \rightarrow G/G' \rightarrow 0}.

Even when one has a splitting, the bundle need not be completely trivial, because the bundle is not principal, and the connection can still twist the fibres around. For instance, {S_3} when viewed as a bundle over {{\bf Z}/2{\bf Z}} with fibres {A_3} splits, but observe that if one uses the red generator of this splitting to move from one copy of the blue {A_3} graph to the other, that the orientation of the graph changes. The bundle is trivialisable if and only if {G'} is a direct summand of {G}, i.e. {G} splits as a direct product {G = G' \times H} of a lifted copy {H} of {G/G'}. Thus we see that the geometric analogue of a direct summand is that of a trivialisable bundle (and that trivial bundles are then the analogue of direct products). Note that there can be more than one way to trivialise a bundle. For instance, with the Klein four-group {{\bf Z}/2{\bf Z} \times {\bf Z}/2{\bf Z}},

the red fibre {{\bf Z}/2{\bf Z}} is a direct summand, but one can use either the blue lift of {{\bf Z}/2{\bf Z}} or the green lift of {{\bf Z}/2{\bf Z}} as the complementary factor.

Emmanuel Breuillard, Ben Green, and I have just uploaded to the arXiv our paper “Approximate subgroups of linear groups“, submitted to GAFA. This paper contains (the first part) of the results announced previously by us; the second part of these results, concerning expander groups, will appear subsequently. The release of this paper has been coordinated with the release of a parallel paper by Pyber and Szabo (previously announced within an hour(!) of our own announcement).

Our main result describes (with polynomial accuracy) the “sufficiently Zariski dense” approximate subgroups of simple algebraic groups {{\bf G}(k)}, or more precisely absolutely almost simple algebraic groups over {k}, such as {SL_d(k)}. More precisely, define a {K}-approximate subgroup of a genuine group {G} to be a finite symmetric neighbourhood of the identity {A} (thus {1 \in A} and {A^{-1}=A}) such that the product set {A \cdot A} can be covered by {K} left-translates (and equivalently, {K} right-translates) of {A}.

Let {k} be a field, and let {\overline{k}} be its algebraic closure. For us, an absolutely almost simple algebraic group over {k} is a linear algebraic group {{\bf G}(k)} defined over {k} (i.e. an algebraic subvariety of {GL_n(k)} for some {n} with group operations given by regular maps) which is connected (i.e. irreducible), and such that the completion {{\bf G}(\overline{k})} has no proper normal subgroups of positive dimension (i.e. the only normal subgroups are either finite, or are all of {{\bf G}(\overline{k})}. To avoid degeneracies we also require {{\bf G}} to be non-abelian (i.e. not one-dimensional). These groups can be classified in terms of their associated finite-dimensional simple complex Lie algebra, which of course is determined by its Dynkin diagram, together with a choice of weight lattice (and there are only finitely many such choices once the Lie algebra is fixed). However, the exact classification of these groups is not directly used in our work.

Our first main theorem classifies the approximate subgroups {A} of such a group {{\bf G}(k)} in the model case when {A} generates the entire group {{\bf G}(k)}, and {k} is finite; they are either very small or very large.

Theorem 1 (Approximate groups that generate) Let {{\bf G}(k)} be an absolutely almost simple algebraic group over {k}. If {k} is finite and {A} is a {K}-approximate subgroup of {{\bf G}(k)} that generates {{\bf G}(k)}, then either {|A| \leq K^{O(1)}} or {|A| \geq K^{-O(1)} |{\bf G}(k)|}, where the implied constants depend only on {{\bf G}}.

The hypothesis that {A} generates {{\bf G}(k)} cannot be removed completely, since if {A} was a proper subgroup of {{\bf G}(k)} of size intermediate between that of the trivial group and of {{\bf G}(k)}, then the conclusion would fail (with {K=O(1)}). However, one can relax the hypothesis of generation to that of being sufficiently Zariski-dense in {{\bf G}(k)}. More precisely, we have

Theorem 2 (Zariski-dense approximate groups) Let {{\bf G}(k)} be an absolutely almost simple algebraic group over {k}. If {A} is a {K}-approximate group) is not contained in any proper algebraic subgroup of {k} of complexity at most {M} (where {M} is sufficiently large depending on {{\bf G}}), then either {|A| \leq K^{O(1)}} or {|A| \geq K^{-O(1)} |\langle A \rangle|}, where the implied constants depend only on {{\bf G}} and {\langle A \rangle} is the group generated by {A}.

Here, we say that an algebraic variety has complexity at most {M} if it can be cut out of an ambient affine or projective space of dimension at most {M} by using at most {M} polynomials, each of degree at most {M}. (Note that this is not an intrinsic notion of complexity, but will depend on how one embeds the algebraic variety into an ambient space; but we are assuming that our algebraic group {{\bf G}(k)} is a linear group and thus comes with such an embedding.)

In the case when {k = {\bf C}}, the second option of this theorem cannot occur since {{\bf G}({\bf C})} is infinite, leading to a satisfactory classification of the Zariski-dense approximate subgroups of almost simple connected algebraic groups over {{\bf C}}. On the other hand, every approximate subgroup of {GL_n({\bf C})} is Zariski-dense in some algebraic subgroup, which can be then split as an extension of a semisimple algebraic quotient group by a solvable algebraic group (the radical of the Zariski closure). Pursuing this idea (and glossing over some annoying technical issues relating to connectedness), together with the Freiman theory for solvable groups over {{\bf C}} due to Breuillard and Green, we obtain our third theorem:

Theorem 3 (Freiman’s theorem in {GL_n({\bf C})}) Let {A} be a {K}-approximate subgroup of {GL_n({\bf C})}. Then there exists a nilpotent {K}-approximate subgroup {B} of size at most {K^{O(1)}|A|}, such that {A} is covered by {K^{O(1)}} translates of {B}.

This can be compared with Gromov’s celebrated theorem that any finitely generated group of polynomial growth is virtually nilpotent. Indeed, the above theorem easily implies Gromov’s theorem in the case of finitely generated subgroups of {GL_n({\bf C})}.

By fairly standard arguments, the above classification theorems for approximate groups can be used to give bounds on the expansion and diameter of Cayley graphs, for instance one can establish a conjecture of Babai and Seress that connected Cayley graphs on absolutely almost simple groups over a finite field have polylogarithmic diameter at most. Applications to expanders include the result on Suzuki groups mentioned in a previous post; further applications will appear in a forthcoming paper.

Apart from the general structural theory of algebraic groups, and some quantitative analogues of the basic theory of algebraic geometry (which we chose to obtain via ultrafilters, as discussed in this post), we rely on two basic tools. Firstly, we use a version of the pivot argument developed first by Konyagin and Bourgain-Glibichuk-Konyagin in the setting of sum-product estimates, and generalised to more non-commutative settings by Helfgott; this is discussed in this previous post. Secondly, we adapt an argument of Larsen and Pink (which we learned from a paper of Hrushovski) to obtain a sharp bound on the extent to which a sufficiently Zariski-dense approximate groups can concentrate in a (bounded complexity) subvariety; this is discussed at the end of this blog post.

This week there is a conference here at IPAM on expanders in pure and applied mathematics. I was an invited speaker, but I don’t actually work in expanders per se (though I am certainly interested in them). So I spoke instead about the recent simplified proof by Kleiner of the celebrated theorem of Gromov on groups of polynomial growth. (This proof does not directly mention expanders, but the argument nevertheless hinges on the absence of expansion in the Cayley graph of a group of polynomial growth, which is exhibited through the smoothness properties of harmonic functions on such graphs.)

Read the rest of this entry »

Archives

RSS Google+ feed

  • An error has occurred; the feed is probably down. Try again later.
Follow

Get every new post delivered to your Inbox.

Join 3,875 other followers