Finite simple groups as expanders
See allHide authors and affiliations

Edited by Robion C. Kirby, University of California, Berkeley, and approved February 21, 2006 (received for review November 30, 2005)
Abstract
We prove that there exist k ∈ ℕ and 0 < ε ∈ ℝ such that every nonabelian finite simple group G, which is not a Suzuki group, has a set of k generators for which the Cayley graph Cay(G; S) is an εexpander.
Let X be a finite graph and 0 < ε ∈ ℝ. Then X is called an εexpander if for every subset A of the vertices of X with A ≤ (1/2)X we have ∂A ≥ εA, where ∂A denotes the boundary of A, i.e., the vertices of distance 1 from A.
Expander graphs play an important role in computer science and combinatorics, and many efforts has been dedicated to their constructions (cf. ref. 1, the references therein, and ref. 2). Many of these constructions are of Cayley graphs, and in particular various infinite families of finite simple groups have been shown to be expanding families.
A finite group G is called an εexpander with respect to a generating subset S if the Cayley graph Cay(G; S) is an εexpander. We will say that an infinite family 𝔊 of groups is a family of expanders if there exists k ∈ ℕ and 0 < ε ∈ ℝ such that every group G ∈ 𝔊 has a subset S of k generators with respect to (w.r.t.) which G is an εexpander. In this situation we also say that the groups G ∈ 𝔊 are expanders “uniformly.” Until recently all known such families consisting of simple groups were of bounded Lie rank (cf. refs. 1 and 3), a fact that has raised speculation that this is the only possibility (see refs. 4 and 5).
It is easy to see that the diameter of each graph X_{i} from an expander family {X_{i} } is most c logX_{i}  (where c is a constant). In ref. 6 it was shown that every nonabelian finite simple group has a set S of seven generators for which the Cayley graph Cay(G; S) has a diameter bounded by C log(G) for an absolute constant C. It was conjectured there that one can even make all finite simple groups expanders uniformly, although, as observed by Y. Luz (see ref. 4), the generators used in ref. 6 do not give rise to expanders.
The main goal of this note is to announce a proof of almost the whole of this conjecture.
Theorem 1.
There exist k ∈ ℕ and 0 < ε ∈ ℝ such that every nonabelian finite simple group G, which is not a Suzuki group, has a set S of k generators for which Cay(G; S) is an εexpander.
In fact careful estimates using variations of some of the arguments below yield k < 1,000 and ε > 10^{−10} .
We believe that the above theorem holds also for the Suzuki groups, but our (diverse) methods do not apply to them. What makes them exceptional is the fact that they do not contain copies of SL_{2}(𝔽_{p}) or PSL_{2}(𝔽_{p}) like all the other finite simple groups (see below for more details).
The proof of Theorem 1 is the accumulation of the works (refs. 7–10 and A.L., unpublished results) in the following chronological order.
In ref. 7 it was proved, extending the work of Shalom (3), that for m ≥ 3 and k ≥ 0 the group SL_{m}(ℤ[x _{1}, …, x _{k}]) has property (τ), i.e., its finite quotients are expanders. It was then further shown in ref. 8 that if R = ℤ〈x _{1}, …, x_{k} 〉 is a free noncommutative ring, then suitable finite quotients of EL_{m}(R) are also expanders uniformly, provided m ≥ 3 [where EL_{m}(R) denotes the subgroup of the multiplicative group of Mat_{m}(R) generated by the elementary matrices]. This includes, in particular, the groups EL_{3}(Mat_{n}(𝔽_{q})) ≃ SL_{3n}(𝔽_{q}), and thus SL_{3n}(𝔽_{q}) are uniformly expanders for all n and for all prime powers q. For every d ≥ 3, the group SL_{d}(𝔽_{q}) is a bounded product of copies of SL_{3n}(𝔽_{q}) for n = ⌊d/3⌋, which implies (using Lemma 1 below) that the groups {SL_{d}(𝔽_{q})  d ≥ 3, q prime power} form a family of expanders.
It was then shown in ref. 10 that every finite simple classical group of Lie type is a bounded product of copies of SL_{d}(𝔽_{q}) and its central quotients. This fact can be combined with the previous results to yield that all classical groups of Lie type of sufficiently high rank are expanders uniformly.
The alternating groups Alt(n) [or equivalently the symmetric groups Sym(n)] for n ≥ 5 are also expanders in a uniform way. This result is proved in ref. 9. The argument here is more involved because Alt(n) contains copies of SL_{d}(𝔽_{q}), but it is not boundedly generated by such groups. The proof instead goes by decomposing the regular representation of Alt(n) into two components. On the first component Alt(n) acts as if it is boundedly generated by some copies of powers of SL_{d}(𝔽_{q}). On the second component one applies the eigenvalue estimates of ref. 11. The idea of this decomposition comes from work of Roichman (12).
On the other hand, it is shown by A.L. (unpublished results) that the family SL_{2}(𝔽_{q}), q a prime power, is also a family of expanders. This result is proved by a combination of Selberg’s Theorem (cf. ref. 1 and Section 4) with the explicit construction of Ramanujan graphs as given in ref. 13. In fact, a similar method (using the theory of Ramanujan complexes cf. ref. 14 and their explicit construction in ref. 13) also gives that the groups SL_{d}(𝔽_{q}) for all d ≥ 2 and all prime powers q are expanders uniformly.
The case of SL_{2}(𝔽_{q}) is the crucial new case of A.L. (unpublished results). It is further shown there, using some model theoretic results of Hrushovski and Pillay (15), that for a fixed r, all finite simple groups of Lie type and of rank at most r, with the exception of the Suzuki groups, are bounded products of copies of SL_{2}(𝔽_{q})’s. One therefore deduces that the groups of Lie type and rank ≤ r are expanders uniformly. This case exactly complements the results of refs. 8 and 10 and all together gives that all finite simple groups of Lie type, with the possible exception of the Suzuki groups, are expanders uniformly.
By the classification of the finite simple groups (CFSG), every (nonabelian) finite simple group is either alternating or of Lie type or one of finitely many sporadic groups. Thus, Theorem 1 follows from the works described above.
The layout of the current note does not reflect the chronological story. We recall and make in Section 1 some observations regarding the representation theoretic reformulation of the problem. In Section 2 we describe the proof for SL_{2}, while Sections 3 and 4 give two proofs for the case of SL_{d}, (d ≥ 3): first, via Ramanujan complexes and second, via EL_{3}(ℤ〈x _{1}, …, x _{k}〉). In Section 5 we use the results for SL_{d}(𝔽_{q}) to construct expanding generating sets in all simple groups of Lie type (with the exception of the Suzuki groups). In Section 6 we describe the proof for Alt(n), which is a case of great special interest.
1. A Representation Theoretic Interpretation
As is well known (cf. ref. 1, Chap. 4), the expanding property of Cay(G; S) is equivalent to representation theoretic properties. We need some notation.
The normalized adjacency matrix of a kregular graph X is defined to be Δ = 1/k·A where A is the adjacency matrix of X. Then all the eigenvalues of Δ are in [−1, 1]. The second largest eigenvalue is denoted λ(X).
Let I(α, G, S) denote the following statement:
For every unitary representation (V, ϕ) of G, every 0 ≠ v ∈ V and every 0 < δ ∈ ℝ, if ϕ(s)v − v < δ for each s ∈ S, then ϕ(g)v − v < αδ for each g ∈ G (i.e., a vector v which is “Salmost invariant” is also “Galmost invariant”).
Proposition 1 below can be deduced from the proofs of propositions 4.2.4 and 4.2.5 and theorem 4.3.2 of ref. 1, noting that the “nonnormalized spectral gap” λ_{1}(X) there is equal to k(1 − λ(X)) under our definition.
Proposition 1.
The following hold:


For each α > 0 there is ε > 0 such that a Cayley graph X = Cay(G; S) is an εexpander if I(α, G, S) holds.

For each δ > 0 there is α > 0 such that if X = Cay(G, S) is a Cayley graph and λ(X) < 1 − δ then I(α, G; S) holds.


Moreover, if k = S is bounded then the implications in (i) can be reversed.
We shall repeatedly use the following easy lemma.
Lemma 1 (9).
Let G be a finite group generated by a collection of subgroups {H_{i}} and let ε _{1}, δ > 0. Assume that each subgroup H_{i} is generated by a subset S_{i} such that ∪_{i} S_{i} ≤ k and that each graph Cay(H_{i}; S_{i}) is an ε _{1} expander. Moreover, assume that the graph Y = Cay(G; ∪_{i}H_{i}) satisfies λ(Y) < 1 − δ.
Then there exists ε > 0 depending on ε _{1}, δ and k such that the Cayley graph Cay(G; ∪_{i}S_{i}) is an εexpander.
For the proof take any unitary representation (V, ϕ) of G with a ∪_{i} S_{i} almost invariant vector v. Restricting the representation to each H_{i} we see that v is H_{i} almost invariant. The last assumption of Lemma 1 implies that v is then Galmost invariant and by Proposition 1, Cay(G; ∪_{i} S_{i} ) is an expander.
This lemma implies for example that if G is a bounded product of a bounded number of subgroups H _{1}, H _{2}, …, H _{ℓ} and each H _{i} is an ε_{0}expander (w.r.t. some set of generators S_{i} ), then G is an εexpander w.r.t. their union S = ∪S_{i} .
2. The SL_{2}(𝔽 _{pk} ) Case
In this section we will show, following A.L. (unpublished results), that PSL_{2}(q) can be made into expanders uniformly for every prime power q = p^{α} . It is known that:
Fact 1:
The family of groups SL_{2}(𝔽_{p}), p prime, w.r.t. the generators form a family of expanders. For a proof, based on Selberg’s theorem λ_{1} ≥ 3/16, see ref. 1, Section 4.
Fact 2:
For a fixed prime p, the groups SL_{2}(𝔽_{pk}), k ∈ ℕ, have a subset S_{p}
of p + 1 generators for which the Cayley graphs X = Cay(SL
_{2}(p
^{k}); S_{p}
) are Ramanujan graphs, i.e., λ(X) ≤ (2
The result of Fact 2 was first proved by Morgenstern (16), and it relies on Drinfeld’s solution to the characteristic p Ramanujan conjecture for GL_{2}. However, for our purpose we need the explicit construction of Ramanujan graphs (as special cases of Ramanujan complexes) as given in ref. 13. In the construction there, a symmetric set of p + 1 generators S′_{p} for SL_{2}(𝔽_{pk}) is given as the p + 1 conjugates of a fixed element C by a fixed nonsplit torus H of SL_{2}(𝔽_{p}), i.e., S′_{p} = {h ^{−1} C ^{±1} h  h ∈ H}. Now therefore these graphs are εexpanders by Proposition 1, for some ε > 0 independent of k and p. However, the generating sets S′_{p} are not bounded.
At the same time Cay(SL _{2}(p); {A, B}) are expanders uniformly by Fact 1. All together, these facts imply that Cay(SL_{2}(𝔽_{pk }); {A, B, C}) are expanders by Lemma 1: Indeed, if (V, ϕ) is a representation of G = SL_{2}(𝔽_{pk }) and v ∈ V is Salmost invariant for the set S = {A, B, C}, then v is SL_{2}(𝔽_{p})almost invariant and hence is also S′_{p} almost invariant, because S′_{p} ⊂ SL_{2}(𝔽_{p})·C·SL_{2}(𝔽_{p}), and hence v is Galmost invariant.
This argument shows that SL_{2}(𝔽_{pk }) are uniformly expanders with three generators.
3. SL_{d} (𝔽_{pk }) via Ramanujan Complexes
One can generalize the proof for SL_{2} described in Section 2 to SL_{d} for every d. We sketch the proof below (details available from A.L. upon request).
Let F = 𝔽_{q} be the field of order q = p^{k} , for some prime p. Let E = 𝔽_{qd} be the unique field extension of degree d. The natural map E* → GL_{d}(𝔽_{q}) given by letting E* act on E by multiplication, induces an isomorphism of where H is a nonsplit maximal torus of order (q^{d} − 1)/(q − 1). In ref. 13 it was shown that there exists an ε > 0 such that for a suitable choice of D ∈ SL_{d}(𝔽_{q}), the Cayley graphs Cay(SL_{d}(𝔽_{q}); S′) are εexpanders when S′ = {h ^{−1} Dh  h ∈ H}. What is really proved there is that the adjacency operator of this Cayley graph is the sum of the first and the last of the d − 1 Hecke operators on the Cayley complex SL_{d}(𝔽_{q}), which is a Ramanujan complex, see ref. 14. The eigenvalue bound on these Hecke operators implies that and in particular these are εexpanders by Proposition 1.
We mention that the proof here (when d ≥ 3) does not need the full power of the Ramanujan bound. A weaker bound which is sufficient for our purposes, can be deduced from the infinite dimensional representation theory of the group SL_{d}(𝔽_{q}((t))).
Assume now that d is even, d = 2m. Then the map E* GL_{d}(𝔽_{q}) described above factors through which shows that H ≤ SL_{d}(𝔽_{q}) is contained in a copy of SL_{2}(𝔽_{qm }).
Take now the expanding generating set {A, B, C} of SL_{2}(𝔽_{qm }) from Section 2 with D to obtain a generating set S of four elements for SL_{d}(𝔽_{q}).
We claim that SL_{d}(𝔽_{q}) are a family of expanders w.r.t. these four generators. By Lemma 1 again, an S = {A, B, C, D}almost invariant vector is SL_{2}(𝔽_{qm })almost invariant, and then it is H·D·Halmost invariant hence also S′almost invariant and thus G = SL_{d}(𝔽_{q})almost invariant as required.
This argument covers the case of even d. For odd d, the group SL_{d}(𝔽_{q}) is a product of four copies of SL_{d−1}(𝔽_{q}), and we can apply Lemma 1.
4. SL_{d}(𝔽_{pk }) for (d ≥ 3) via EL_{3} (R)
A different proof for the case of SL_{d} has been given in ref. 8 [prior to the proof of A.L. (unpublished results), which is described in Section 3]. This proof builds on the work of Shalom (3), where he gave a new proof of Kazhdan’s result (17) that SL_{3}(ℤ) has property (T). Shalom’s proof has two ingredients.
Part 1:
The group Λ = SL_{2}(ℤ) × ℤ^{2} has a relative Kazhdan property (T) relative to ℤ^{2}, i.e., if (V, ϕ) is a unitary representation space of Λ with an almost invariant vector w.r.t. the set of four natural generators, then this vector is ℤ^{2}almost invariant.
Part 2:
The group Λ is isomorphic to a maximal parabolic subgroup of SL_{3}(ℤ). Conjugating with the Weyl group gives rise to six obvious embeddings of Λ in SL_{3}(ℤ). The images of ℤ^{2} in these embeddings (which include all root subgroups) boundedly generate SL_{3}(ℤ) by a result of Carter and Keller (18).
Parts 1 and 2 together imply that if V is a unitary representation of Γ = SL_{3}(ℤ) and v ∈ V is an almost invariant vector (w.r.t. some generating set) it will be Γalmost invariant, and therefore the group Γ has property (T).
A similar argument to Part 1 works also for Λ = SL_{2}(R _{0}) × R _{0} ^{2}, when R _{0} is the polynomial ring in k variables over ℤ. However, it is not known if the bounded generation of Part 2 holds in this case, which would imply that SL_{3}(R _{0}) has property (T). Still, by analyzing the congruence kernel of SL_{3}(R _{0}), it is deduced in ref. 7 that Γ = SL_{3}(R _{0}) has property (τ), i.e., all of its finite factors are expanders (w.r.t. a fixed set of generators of Γ).
A step further is taken in ref. 8: it is shown there that Part 1 holds even if one takes the noncommutative free ring R = ℤ〈x _{1}, …, x_{k} 〉, i.e., Λ = EL_{2}(R) × R ^{2} has property (T) relative to R ^{2}.
It will be quite surprising if the analogue of the Carter and Keller result holds for Γ = EL_{3} (R), i.e., if Γ is boundedly generated by its root subgroups. However, this fact holds for many quotients R̄ of R: If R̄ = Mat_{n}(𝔽_{q}) or R̄ = Mat_{n}(𝔽_{q})^{s} for s ≤ q ^{n2}, then R̄ is an image of ℤ〈x _{1}, x _{2}, x _{3}〉 and EL_{3} (R̄) is boundedly generated by its elementary matrices in a way that is independent of n, q, and s. This result implies that the groups EL_{3}(Mat_{n}(𝔽_{q})) = SL_{3n}(𝔽_{q}) and EL_{3}(Mat_{n}(𝔽_{q})^{s}) = SL_{3n}(𝔽_{q})^{s} are a family of expanders.
For a general d ≥ 3, one notes again that SL_{d}(𝔽_{q}) is a bounded product of a bounded number of copies of SL_{3n}(𝔽_{q}) for n = ⌊d/3⌋. We can therefore deduce by Lemma 1 that SL_{d}(𝔽_{q}) form a family of expanders for all d ≥ 3 and every prime power q.
One of the advantages of this construction is that it also produces expanders in very large powers of the group SL_{d}(𝔽_{q}), which are essential for constructing expanding generating sets in the alternating groups (see Section 6).
5. Simple Groups of Lie Type
The following two theorems show how to reduce the case of finite simple groups of Lie type (minus the Suzuki groups) to the case of SL_{d}(𝔽_{q}) described in Sections 2–4.
Theorem 2 (10).
There exists a constant C such that every finite simple group G of classical type is a product of at most C subgroups of G which are quotients of SL_{d}(𝔽_{q}) (for some d ≥ 2 and q).
Theorem 3 (A.L., unpublished results).
Given r ∈ ℕ, there exists a constant C(r) with the following property: Suppose G is a finite simple group of Lie type of Lie rank at most r, which is not a Suzuki group. Then G is a product of at most C(r) subgroups each of which is a quotient of SL_{2}(𝔽_{q}) for a suitably chosen field 𝔽_{q} .
As explained in Lemma 1, once a group G is a product of boundedly many groups that are εexpanders, its Cayley graph is an ε′expander. So Theorem 1 is now proved for all groups of Lie type except for the Suzuki groups. The reason for the Suzuki groups to be excluded is the fact that they do not contain copies of SL_{d}(𝔽_{q}) or PSL_{d}(𝔽_{q}) for any d ≥ 2 and prime power q. In fact, the order of a Suzuki group is not divisible by 3, whereas SL_{d}(𝔽_{q}) is.
The proof of Theorem 2 is based on the fact that an arbitrary connected Dynkin diagram of high rank becomes one of type A_{d} after a vertex is deleted. In this way we can find a quasisimple quotient G _{1} of SL_{d+1}(𝔽_{q}) inside G (in fact it is a Levi factor of a suitable parabolic subgroup).
If U (resp. U _{1}) is a maximal unipotent subgroup of G (resp G _{1}) then ref. 10 proves that U is a product of at most 14 conjugates of U _{1} (using that the positive root system of G parameterizing U is “close” to the root system A_{d} of U_{1} ). A theorem of Liebeck and Pyber in ref. 19 now gives that G is a product of at most 13 conjugates of U and hence a product of at most 13 × 14 = 182 conjugates of G _{1}.
A very detailed and laborious analysis of this kind will also lead to a similar proof of Theorem 3 with explicit bounds for C(r), but this is not the way this theorem is proved by A.L. (unpublished results).
Instead, the author there appeals to a model theoretic method developed by Hrushovski and Pillay (15). There, it is shown that “definable” subgroups of GL _{n}(F) over pseudoalgebraically closed field F are very much like Zariski closed subgroups over algebraically closed field. In particular, if a definable subgroup H is generated by finitely many definable subgroups L _{1}, …, L _{c}, then it is a bounded product of them. Now, it follows from the Lang–Weil Theorem that ultraproducts of finite fields are pseudoalgebraically closed (see ref. 20). As elementary statements are true in an ultraproduct if they are true in almost all factors, one can get “bounded results” over finite fields. This scheme is applied to show that all the finite simple groups (except the Suzuki groups) contain “definable” subgroups isomorphic to SL_{2}(𝔽_{q}) or PSL_{2}(𝔽_{q}) and hence are generated by them in a bounded way (when the rank is bounded).
6. The Alternating Groups
Last but not least is the case of the alternating groups Alt(n). For its special importance, we restate it as follows.
Theorem 4 (9).
There exist l ∈ ℕ and 0 < ε ∈ ℝ such that for every n ∈ ℕ the alternating group Alt(n) has an explicit set of generators S_{n} of size at most l such that Cay(Alt(n); S_{n} ) is an εexpander. The same holds also for the symmetric groups Sym(n).
The main idea of the proof in ref. 9 is as follows. Assume first that n = d ^{6} and d = 2^{3k} − 1 for some k. Based on ideas and results from ref. 8 (see Section 4) it is shown first that the Cayley graphs of the groups Δ_{k} = SL_{3k}(𝔽_{2})^{d5} w.r.t. some generating set F_{k} of size at most 20 are ε_{0}expanders for all k and d = 2^{3k} − 1 (for some fixed ε_{0} > 0).
Now, thinking of the set {1, …, n} as the points in a sixdimensional cube of size d, and remembering that SL_{3k}(𝔽_{2}) acts transitively on a set of size d (via its defining linear action on 𝔽_{2} ^{3k}), we can construct six different embeddings π_{i} of Δ_{k} into Alt(n), where the image under π_{i} of each copy of SL_{3k}(𝔽_{2}) in Δ_{k} acts on the points on a line parallel to the ith coordinate axis in the cube. Denote S_{n} = ∪_{i}π_{i}(F_{k} ) and E = ∪_{i}π_{i}(Δ_{k}). We will show that the Cayley graphs of Alt(n) with respect to S_{n} form a family of expanders. Using that F_{k} is an expanding generating set in Δ_{k} by Lemma 1 it suffices to show that the existence of an Ealmost invariant vector v in any unitary representation V of Alt(n) implies the existence of an Alt(n)almost invariant vector.
We decompose V as a sum of two representations V _{1} ⊕ V _{2}, where V _{1} is the sum of all irreducible representations of Alt(n) in V corresponding to partitions λ ⊢ n, where the first row λ_{1} is not too big (less than n − d ^{5/4}) and V _{2} contains all others. A similar decomposition is used by Roichman in ref. 12 to show that the Cayley graphs of Alt(n) with respect to conjugacy classes have some expanding properties. We will use two different arguments to show that the projection v _{1} of v in V _{1} is small and that projection v _{2} in V _{2} is close to an invariant vector.
Argument 1:
Using the definition of the set E, it is shown that a bounded power of E acts transitively on “nearly all” ordered ℓtuples of points in the cube for some ℓ of size approximately d ^{5}/(3 log d). Also a bounded power of E contains a permutation that acts as ℓcycle. Thus, the vector v, and therefore v_{1} , is almost invariant by nearly all elements in the conjugacy class C_{ℓ} of ℓcycles in Alt(n). Here nearly all means a subset of proportion tending to 1, as k and n tend to infinity. This fact implies that v _{1} is almost invariant under the action of the operator The operator L acts as a multiplication by χ_{λ}(C _{ℓ})/χ_{λ}(id) on the irreducible representation V_{λ} corresponding to the partition λ, where χ_{λ} is the character of V_{λ} . At this point one can appeal to the results of Roichman (11), who studied normalized character values of the symmetric groups. Roichman’s results give that χ_{λ}(C _{ℓ})/χ_{λ}(id) ≪ 1, for any λ ⊢ n, provided that the first row λ_{1} is small. Therefore, ‖Lv _{1}‖ ≪ ‖v _{1}‖, which together with the almost invariance of v _{1} under L, implies that the vector v _{1} is short.
Argument 2:
Using that all irreducible representations in V _{2} corresponds to partitions with λ_{1} ≥ n − d ^{5/4}, one can view the linear span W of the orbit of v _{2} in V _{2} as part of the induced representation to Alt(n) of the trivial representation of Alt(n − d ^{5/4}). This induced representation has a basis 𝔅, whose elements corresponds to the ordered d ^{5/4}tuples of points in the cube. The size of the basis 𝔅 is significantly smaller that the size of E, and it can be shown that the random walk on 𝔅 defined by E mixes in just several steps. This fact, together with the almost invariance of v _{2} under E, implies that v _{2} is close to an invariant vector.
This argument finishes the sketch of the proof for the case Alt(n) for n = (2^{3k} − 1)^{6} for some k. The case of general n follows from the observation that Alt(n) can be written as a product of a bounded number of copies of Alt(n_{k} ) for n_{k} = (2^{3k} − 1)^{6} embedded in Alt(n). By adding any odd permutation to S_{n} , we see that the symmetric groups Sym(n) also form a family of expanders.
Acknowledgments
A.L. was supported by the National Science Foundation and the Binational Science Foundation (U.S. and Israel). This work was done while visiting the Institute for Advanced Study at Princeton University, supported by the Ambrose Monell Foundation and the Ellentuck Fund.
Footnotes
 ^{¶}To whom correspondence should be addressed. Email: nikolay.nikolov{at}new.ox.ac.uk

Author contributions: M.K., A.L., and N.N. performed research; and A.L. wrote the paper.

Conflict of interest statement: No conflicts declared.

This paper was submitted directly (Track II) to the PNAS office.
 Abbreviations:
 w.r.t.,
 with respect to.
Abbreviation:
 © 2006 by The National Academy of Sciences of the USA
References

↵
 Lubotzky A.
 ↵

↵
 Shalom Y.

↵
 Lubotzky A. ,
 Weiss B.

↵
 Lafferty J. D. ,
 Rockmore D.
 ↵

↵
 Kassabov M. ,
 Nikolov N.

↵
 Kassabov M.

↵
 Kassabov M.

↵
 Nikolov N.
 ↵

↵
 Roichman Y.
 ↵

↵
 Lubotzky A. ,
 Samuels B. ,
 Vishne U.

↵
 Hrushovski E. ,
 Pillay A.
 ↵

↵
 Kaz̆dan D. A.
 ↵
 ↵

↵
 Fried M. D. ,
 Jarden M.