DIMENSION EXPANDERS

ALEXANDER LUBOTZKY AND EFIM ZELMANOV

In memory of Walter Feit

Abstract. We show that there exists k ∈ ℕ and 0 < ϵ ∈ ℝ such that for every field F of characteristic zero and for every n ∈ ℕ, there exists explicitly given linear transformations T_{1}, …, T_{k} : F^{n} → F^{n} satisfying the following:

For every subspace W of F^{n} of dimension less or equal \frac{n}{2},

dim(W + ∑_{i=1}^{k} T_{i}W) ≥ (1+ϵ) dim W. This answers a question of Avi

Wigderson [W]. The case of fields of positive characteristic (and in particular finite fields) is left open.

1. Introduction

A finite k-regular graph X = (V, E) with n vertices is called ϵexpander (for 0 < ϵ ∈ ℝ) if for every subset of vertices W ⊂ V with |W | ≤ \frac{|V |}{2}, |N(W)| ≥ (1+ϵ)|W | where N(W) = \{y ∈ V | distance(y, W) ≤ 1}.

Most k-regular graphs X (when k is even then all graphs) are obtained as Schrier graphs of groups (see e.g. [Lu2, (5.4)]) so there is a finite group G and a symmetric set S of generators of it of size k acting on V such that the graph structure of X is obtained by connecting x ∈ V to sx, s ∈ S. An expander graph can be thought of as a permutational representation of a group G, with a set of generators S = {s_{1}, …, s_{k}}, acting on a set V and satisfying for every subset W

of size at most \frac{|V |}{2}, |W ∪ ⋃_{i=1}^{k} s_{i}W | ≥ (1 + ϵ)|W |.

Motivated by some considerations from theoretical computer science, a notion of dimension expanders was suggested by [BISW] where linear represenations replace permutational representation.

Definition 1.1. Let F be a field, k ∈ ℕ, ϵ > 0, V a vector space of dimension n over F and T_{1}, …, T_{k} F -linear transformations from V to V. We say that the pair (V, {T_{i}}_{i=1}^{k}) is an ϵ-dimension expander if for

every subspace W of dimension less or equal \frac{n}{2}, dim(W + ∑_{i=1}^{k} T_{i}W) ≥

(1 + ϵ) dim W.

This research was supported by grants from the NSF and the BSF (US-Israel Binational Science Foundation).

It is not difficult to prove that whenever there is a meaningful measure/probability on F (and hence also on M_{n}(F) and GL_{n}(F)) a random choice of T_{1}, …, T_{k} will give ϵ-dimension expanders for suitable k and ϵ (see [Lu1, Proposition 1.2.1, p. 5] for an analogue result for graphs).

In [W], Wigderson posed the problem of finding, for a fixed field F and for some fixed k and ϵ, ϵ-dimension expanders of arbitrarily large dimension. He suggested there that the set of linear transformations defined by any irreducible representation evaluated at expanding generators of the underlying finite group, gives rise to a dimension expander over the complex numbers and possibly over finite fields as well.

Our main result is:

Theorem 1.2. There exist k ∈ ℕ and 0 < ϵ ∈ ℝ such that for every field F of characteristic zero and for every n, there are explicitly given T_{i} : F^{n} → F^{n}, i = i, …, k such that (F^{n}, {T_{i}}_{i=1}^{k}) is an ϵ-dimension expander.

In fact we confirmed Wigderson’s suggestion over the complex numbers but we also show that over finite fields the situation is more delicate. To put it on a wider perspective let us recall that the standard method to get explicit constructions of expander graphs is by showing that the induced unitary representation of the group G on the space ℓ_{0}^{2}(V) is “bounded away from the trivial representation” in the sense of the Fell topology of the unitary dual of G (see [Lu1, §3]). Here ℓ_{0}^{2}(V) is the space of all functions from the set of vertices V to ℂ. We will show in §2, that the complex vector space V = ℂ^{n} becomes a dimension expander with respect to a set of generators S of G, when G acting unitarily and irreducibly on V, if the adjoint (unitary) representation of G on Sℓ_{n}(ℂ) = {A ∈ M_{n}(ℂ)|traceA = 0} is bounded away from the trivial representation. This crucial observation enables us to use the known results and methods developed to construct expander Cayley graphs, to construct also dimension expanders over ℂ. The extensions to an arbitrary characteristic zero field F is then standard (see §3 below).

The use of unitarity is very unfortunate and is the main obstacle for extending our results to positive characteristic. In fact, Example 4.IV below implies that there are expander groups whose linear representations over finite fields are not dimension expanders. We still should mention that the finite examples one may deduce from Example 4.IV are of groups whose order is divisible by p and the represenations are over 𝔽_{p}. It may still be that in the “non-modular” case, i.e., the order of the group is prime to the characteristic, Wigderson suggestion holds even over finite fields.

As of now, the only results over finite fields we are aware of are of Dvir and Shpilka [DS] who constructed explicit dimension expanders (of constant expansion) over GF (2) in dimension n with O(log n) transformations. They can also expand the dimension by a smaller factor 1 + O(1/ log n) explicitly using a constant number of transformations.

Finally, let us relate the results of this note to our work on “algebras with property τ” [LuZa]: Recall that a group Γ generated by a finite set S is said to have property τ if there exists ϵ > 0 such that whenever Γ acts transitively on a finite set V the resulting graph (when x ∈ V is connected to sx, s ∈ S) is an ϵ-expander. The notion of dimension expanders calls for defining an F -algebra A with a finite set of generators S to have property τ if there exists ϵ > 0 such that for every irreducible representation ρ on a finite dimensional F -dimension V, the pair (V, ρ(S)) is ϵ-dimension expander. We should note however that we do not know in general that for a group Γ with property τ (or even T) the group algebra ℂ[Γ] has τ (and it looks unlikely - see examples 4.V and 4.VI). We know this only with respect to representations of ℂ[Γ] which are unitary on Γ. So we do not know whether ℂ[SL_{3}(ℤ)] has τ. We do know, though, that ℂ[SL_{3}(𝔽_{p}[t])] has τ. But to see the delicacy of the issue we show that 𝔽_{p}[SL_{3}(𝔽_{p}[t])] does not have τ, while we do not know the answer for 𝔽_{ℓ}[SL_{3}(𝔽_{p}[t])] for a prime ℓ different than p. We elaborate on this in §4, leaving the full treatment to

[LuZa] where connections with the Golod-Shafarevich theory and some questions originated in 3-manifold theory are studied.

We take the opportunity to thank A. Jaikin-Zapirain and A. Wigderson for useful suggestions.

2. The adjoint representation

Let Γ be a group generated by a finite set S and (H, ρ : Γ → U(H)) a unitary representation of Γ. The Kazhdan constant K = K_{Γ}^{S}((H, ρ)) is defined as:

inf_{0≠v∈H} max_{s∈S} \{\frac{∥ρ(s)v − v∥}{∥v∥}\}

Recall that the group Γ is said to have property T if K_{Γ}^{S} = inf_{(H,ρ)∈R_{0}(Γ)} K_{Γ}^{S}((H, ρ)) >

0 when R_{0}(Γ) is the family of all unitary representations of Γ which have no non-trivial Γ-fixed vector. In this case, K_{Γ}^{S} is called the Kazhdan constant of Γ with respect to S. Similarly Γ is said to have property τ if K_{Γ}^{S}(τ) = inf_{(H,ρ)∈R_{0}^{f} (Γ)} K_{Γ}^{S}(H, ρ) > 0 when R_{0}^{f}(Γ) is the subset

of R_{0}(Γ) of all representations for which ρ(Γ) is finite. The number K_{Γ}^{S}(τ) is the τ-constant of Γ.

If H is a finite dimensional space, say H = ℂ^{n} and ρ a unitary representation ρ : Γ → U(H) = U_{n}(ℂ), then it induces a representation adjρ on Hom(H, H) ≃ M_{n}(ℂ) defined by adjρ(γ)(T) = ρ(γ)T ρ(γ)^{−1} for γ ∈ Γ and T ∈ M_{n}(ℂ). The subspace Sℓ_{n}(ℂ) of all the linear transformations (or matrices) of trace 0 is invariant under adjρ. If ρ is irreducible then by Schur’s Lemma, Sℓ_{n}(ℂ) does not have any nontrivial adjρ(Γ)-fixed vector.

The space Hom(H, H) is also a Hilbert space when one defines for T_{1}, T_{2} ∈ Hom(H, H), ⟨T_{1}, T_{2}⟩ = trT_{1}T_{2}^{∗}, and adjρ is a unitary representation on it and on its invariant subspace Sℓ_{n}(ℂ).

Proposition 2.1. If ρ : Γ → U_{n}(ℂ) is an irreducible unitary representation, then V = ℂ^{n} is an ϵ-dimension expander for ρ(S) where ϵ = \frac{κ^{2}}{12}, κ = K_{Γ}^{S}(Sℓ_{n}(ℂ), adjρ).

Proof. Let W ≤ V be a subspace of dimension m ≤ \frac{n}{2}. Let P be the linear projection from V to W. As P^{∗} = P, we have that ⟨P, P ⟩ = tr(P^{2}) = tr(P) = m. The right hand equality is seen simply by considering a basis which is a union of a basis of W and of W^{⊥}. Consider Q = P − \frac{m}{n}I where I is the identity operator. Then

trQ = trP − tr(\frac{m}{n}I) = 0, so Q ∈ Sℓ_{n}(ℂ).

The norm of Q is:

∥Q∥^{2} = tr((P − \frac{m}{n}I)(P − \frac{m}{n}I)^{∗}) =

=tr(P^{2} − 2\frac{m}{n}P + \frac{m^{2}}{n^{2}} I) = m − 2\frac{m^{2}}{n} + \frac{m^{2}}{n^{2}} n = m − \frac{m^{2}}{n} .

It follows now that there exists s ∈ S such that ∥ρ(s)(Q) − Q∥^{2} ≥ κ^{2}∥Q∥^{2}. Notice that ρ(s)(Q) = ρ(s)Qρ(s)^{−1} = ρ(s)P ρ(s)^{−1} − \frac{m}{n}I = P′ − \frac{trP′}{n} I where P′ = ρ(s)P ρ(s)^{−1} is the projection of V onto the subspace W′ = ρ(s)(W), so trP′ = m as well.

Lemma 2.2. If W, W′ are two subspaces of V of dimension m and P, P′ the projections to W and W′, respectively, then Re < P, P′ >≥ 4m − 3dim(W + W′).

Proof. Denote U_{0} = W ∩ W′, U_{1} = U_{0}^{⊥} ∩ W, and U_{2} = U_{0}^{⊥} ∩ W′ and d_{i} = dimU_{i}. Then V = U_{0} ⊕ U_{1} ⊕ U_{2} ⊕ (W + W′)^{⊥}.

Let us choose an orthonormal basis for V compose of {α_{1}, …, α_{d_{0}}} an orthonormal basis for U_{0}, {β_{1}, …, β_{d_{1}+d_{2}}} an orthonormal basis for U_{1}⊕U_{2} and {γ_{1}, …, γ_{r}}, r = dimV −(d_{0}+d_{1}+d_{2}), an orthonormal basis for (W +W′)^{⊥}. The operator P P′ is the identity on U_{0} and zero on (W + W′)^{⊥}. It is a linear transformation of norm ≤ 1, so | < P P′β_{i}, β_{i} > | ≤ 1 and hence:

(∗)  −1 ≤ Re < P P′β, β_{i} >≤ 1.

The trace of P P′ on U_{0} is dimU_{0} and it is 0 on (W +W′)^{⊥}. Together with (*) we get:

Re tr(P P′) ≥ dimU_{0} − dimU_{1} − dimU_{2} =

= dim(W ∩ W′) − (dimV − dim(W ∩ W′) − dim(W + W′)^{⊥}) =

= 2dim(W ∩ W′) − dim(W + W′) =
= 4m − 3dim(W + W′)

The last equality follows from the fact that dim(W ∩ W′) = dimW + dimW′ − dim(W + W′) =

= 2m − dim(W + W′).
□

So altogether,

κ^{2}(m − \frac{m^{2}}{n}) ≤ ∥ρ(s)(Q) − Q∥^{2} = ∥ρ(s)P ρ(s^{−1}) − P ∥^{2} = ∥P′ − P ∥^{2}

= ⟨P′ − P, P′ − P ⟩ = ⟨P′, P′⟩ + ⟨P, P ⟩ − ⟨P, P′⟩ − ⟨P′, P ⟩

= 2m − 2Re < P, P′ >

≤ 2m − 2(4m − 3dim(W + W′)) = 6dim(W + W′) − 6m, .

and therefore

m(1 + \frac{κ^{2}}{6} (1 − \frac{m}{n})) ≤ dim(W + W′).

As 1 − \frac{m}{n} ≥ \frac{1}{2}, we get that dimW (1 + \frac{κ^{2}}{12}) ≤ dim(W + W′) and Proposition 2.1 is now proved. □

Remark/Question 2.5 For graph expanders or equivalently, as in the introduction, for permutational representation of Γ on a set V, V is an expander iff the representation of Γ on ℓ_{0}^{2}(V) is bounded away from the trivial representation (cf. [Lu1, 4.3]). Do we have such a converse for Proposition 2.1? I.e., if a ℂ-vector space V = ℂ^{n} is a dimension expander with respect to a unitary representation ρ of Γ, does it imply that the representation adjρ on Sℓ_{n}(ℂ) is bounded away from the trivial representation?

3. Examples and a proof of Theorem 1.2

There are many known examples of groups with property T or τ. They can now, in light of Proposition 2.1, be used to give a proof for Theorem 1.2, i.e. to give explicit sets of linear transformations of ℂ^{n} which solve Wigderson’s Problem.

Let us take some of the examples which are the simplest to present: 3.I Fix 3 ≤ d ∈ ℕ and let Γ = SL_{d}(ℤ) with a fixed set of generators, e.g. S = {A, B} when A is the transformation sending e_{1} to e_{1} + e_{2} and fixing e_{2}, …, e_{d} and B will send e_{i} → e_{i+1} for i = 1, …, d − 1 and e_{d} to (−1)^{d−1}e_{1}. (Here {e_{1}, …, e_{d}} is the standard basis for ℤ^{d}).

As Γ has Property T, whenever we take a finite dimensional irreducible unitary representation ρ of Γ on V = ℂ^{n}, ρ(A) and ρ(B) make V a dimension expander. Remark/Question 3.1 Is this true also for the non-unitary representations of Γ? Note that, say SL_{3}(ℤ), has infinitely many irreducible rational representations (i.e. rational representations of SL_{3}(ℂ) restricted to the Zariski dense subgroup SL_{3}(ℂ)). These representations are classified by the highest weights of Sℓ_{3}(ℂ). Are they dimension expanders with respect to ρ(A) and ρ(B)?

3.II Fix 3 ≤ d ∈ ℕ and a prime p and let Γ = SL_{d}(𝔽_{p}[t]). This Γ has (T) and all its representations over ℂ factor through finite quotients ([Ma, Theorem 3, p.3]) which implies that they can be unitarized. Thus unlike in example 3.I, we can deduce that all the irreducible complex representations of Γ give rise to dimension expanders.

3.III Let Γ = SL_{2}(ℤ) and for a prime p, denote Γ(p) = Ker(SL_{2}(ℤ) →

SL_{2}(ℤ/pℤ)). Let A = (\begin{matrix}1 & 1 \\ 0 & 1 \end{matrix}) and B = (\begin{matrix}0 & 1 \\ −1 & 0 \end{matrix}) form a set of gener-

ators S for Γ. The group Γ has property τ with respect to the family {Γ(p)} – see [Lu1, 4].

This means that there exists κ > 0 such that for all unitary representations (V, ρ) of Γ which factor through Γ/Γ(p) = SL_{2}(p) for some p and do not have a fixed point, K_{Γ}^{S}(V, ρ) > κ. The group SL_{2}(p) acts

on the 𝔽_{p}-projective line ℙ^{1} = \{0, …, p−1, ∞\} via (\begin{matrix}a & b \\ c & d \end{matrix}) (z) = \frac{az+b}{cz+d}.

This is a double transitive permutational representations (and indeed give rise to expander graphs – see [Lu1, Theorem 4.4.2]). Moreover, it induces an irreducible linear representation ρ on ℓ_{0}^{2}(P^{1}) ≅ ℂ^{p}. The adjoint representation of Γ on Sℓ_{p}(ℂ) also factors through SL_{2}(p) and is therefore bounded away from the trivial representation. Hence ℂ^{p} are dimension expanders with respect to the explicitly given transformations ρ(A) and ρ(B).

3.IV Recently Kassabov ([K2]) showed that the Cayley graphs of the symmetric groups Σ_{n} are expanders with respect to an explicitly given set S_{n} of generators with |S_{n}| ≤ k for some k (k ≤ 30 in his work). This means that there exists κ > 0 such that K_{Σ_{n}}^{S_{n}}(V, ρ) > κ for every n and every representation (V, ρ) ∈ R_{0}(Σ_{n}). This can be applied in particular to adjρ_{n} when ρ_{n} is the linear representation of Σ_{n} on ℂ^{n−1} ≅ ℓ_{0}^{2}({1, …, n}) induced from the natural permutational representation of Σ_{n} on the set {1, …, n}. We get this way that ℂ^{n−1} are dimension expanders for every n with respect to k explicit linear transformations.

Examples 3.III and 3.IV are especially useful for us as the representations ρ which appear in these examples are all defined over ℚ. This enables us now to prove Theorem 1.2 over every field of characteristic zero. Indeed, if F is such a field then F contains ℚ and so the examples 3.III and 3.IV give finite representations ρ into GL_{n}(F) for various values of n. Now if |F | ≤ ℵ, then F can be embedded into ℂ and so GL_{n}(F) ⊂ GL_{n}(ℂ) and as ρ are finite, they can be unitarized over ℂ. Now, as ℂ^{n} = ℂ ⊗_{F} F^{n}, every F -subspace W of F^{n} spans a

ℂ-subspace \overline{W} of ℂ^{n} of the same dimension. It is easy to see that for ρ(s) ∈ GL_{n}(F), dim_{F} (ρ(s)W + W) = dim_{ℂ}(ρ(s)\overline{W} + \overline{W}) hence F^{n} are also dimension expanders.

This actually covers also the general case: if F has large cardinality and W ≤ F^{n} is a counter example, then the entries of a basis of W generate a finitely generated field F_{1} and the counterexample can already be found in F_{1}^{m}. This is impossible by the previous paragraph - so Theorem 1.2 is now proved for every field F or characteristic zero.

The above discussion may give the impression that the only way to make ℂ^{n} into dimension expander may be via unitary and even finite representation. This is not the case. Let us consider more examples: 3.V Fix 5 ≤ d ∈ ℕ and p a prime. Let f be the quadratic form x_{1}^{2} + ⋯ + x_{d−2}^{2} − \sqrt{p} x_{d−1}^{2} − \sqrt{p} x_{d}^{2} and let Γ be the group SO(O, f) of all the d × d matrices over O of determinant 1 preserving f, where O is the ring of integers of the field E = ℚ(\sqrt{p}). The group Γ is a Zariski dense subgroup of the E-algrebraic group H = SO(f).

Let G = Res_{E/Q}(H) be the restriction of scalors from E to ℚ of H. Then Γ sits diagonally as a lattice the real points of G which is isomorphic to SO(ℝ, f) × SO(ℝ, f^{ι}) = SO(d − 2, 2) × SO(d) (([Ma, Theorem 3.2.4])) and it therefore has property T. Here, ι is the unique non-trivial element of the Galois group Gal(E/ℚ).

Every irreducible E-rational represenation of H define two real representations of Γ-one for each of the two embeddings of E into ℝ. For an element g of Γ if one represenation sends it to a matrix A, the second sends it to A^{ι} - i.e., applying ι to all the entries of A. It follows, that if one representation define ϵ-dimension expander so is the other. Now, one of these two representation factors through SO(d) and hence it is always unitary. As Γ has T, it follows that it defines a dimension expander. The other one is never unitary as its real Zariski closer is SO(d − 2, 2). Still, we deduce that it is a dimension expander. By taking infinitely many such E-rational represenation one sees that neither finiteness nor unitarity are necessary for dimension expanders.

It is our lack of other methods which forces us to use unitarity (even in a non-unitary example). It will be extremely interesting and important to develop methods to build dimension expanders not via unitarity. This is exactly the obstacle that should be overcome in order to answer Wigderson’s problem for fields of positive characteristic.

4. Algebras with property τ

In this section we briefly comment on the connection between dimension expanders and algebras with property τ. A more systematic study of these algebras will be given in [LuZa].

Motivated by the definition of groups with τ and by some problems on Golod-Shafarevich groups and 3-manifold groups, we would like to have a notion of algebras with property τ. There are several reasonable options. The most natural one is probably:

Definition 4.1. Let F be a field and A an F -algebra generated by a finite set S. A is said to have property τ if there exists an ϵ > 0 such that for every (F −)finite dimensional simple A-module V and for every subspace W of V of dimension most \frac{1}{2} dim V, dim(W + ∑_{s∈S} sW) ≥

(1 + ϵ) dim W. Namely, V is an ϵ-dimension expander with respect to S.

It is not difficult to see that if A has τ with respect to S, it has it with respect to any other finite set of generators, possibly with a different ϵ.

Examples:

4.I. Let A be the free algebra over F on one generator x, i.e. A = F [x]. Assume F has field extensions of infinitely many different degrees, i.e., {F_{i}}_{i∈ℕ} are finite field extensions with n_{i} = [F_{i} : F] ≥ i. So, F_{i} = F [x]/(f_{i}(x)), when f_{i}(x) is an irreducible polynomial of degree n_{i}, is an irreducible A module in a clear way. Let W be the span of x + (f_{i}(x)), …, x^{[ \frac{n_{i}}{2} ]−1} + (f_{i}(x)) in F_{i}. Then dim(W + xW) ≤ (1 + \frac{2}{n_{i}} ) dim W and hence A does not have property τ.

4.II. On the other hand if F is algebraically closed, then every finite dimensional simple module of F [x] is one dimensional and hence F [x] has τ in a vacuous way. (This is perhaps a hint that Definition 4.1 is maybe not the most appropriate one). But see also Example 4.VI below for comparison.

4.III If F as in 4.I and d ∈ ℕ a fixed integer, then by a similar argument M_{d}(F [x]) does not have property τ.

4.IV Let p be a fixed prime, 3 ≤ d ∈ ℕ a fixed integer and Γ = SL_{d}(𝔽_{p}[x]). It follows from Example 3.II that the group algebra ℂ[Γ] has property τ (and, in fact, it follows that F [Γ] has τ for every characteristic zero field.) On the other hand the algebra 𝔽_{p}[SL_{d}(𝔽_{p}[x])] is mapped epimorphically onto M_{d}(𝔽_{p}[x]) via the natural embedding SL_{d}(𝔽_{p}[x]) ⊆ M_{d}(𝔽_{p}[x]). The latter does not have τ by 4.III. Hence 𝔽_{p}[SL_{d}(𝔽_{p}[x])] does not have τ. We do not know if for a prime ℓ ≠ p, 𝔽_{ℓ}[SL_{d}(𝔽_{p}[x])] has τ or not.

4.V It was shown recently by Kassabov and Nikolov [KN] that for d ≥ 3, the group Γ = SL_{d}(ℤ[x]) has property τ. Since SL_{d}(ℤ[x]) is mapped onto SL_{d}(𝔽_{p}[x]) for every x, it follows that for every p, 𝔽_{p}[Γ] does not have τ. We do not know if ℂ[SL_{d}(ℤ[x])] has τ. If it has, the same would apply for ℂ[SL_{d}(ℤ)] which would resolve Question 3.1.

4.VI Let R = ℤ⟨x, y⟩ be the free non-commutative ring on x any y. Fix 3 ≤ d ∈ ℤ and let Γ = EL_{d}(R) - the group generated by the elementary unipotent matrices I + rE_{ij} inside M_{d}(R), when r ∈ R and 1 ≤ i ≠ j ≤ d. It was conjectured by Kassabov [K1] that Γ has τ and some partial results in this direction are proved there . We claim that for every field F, F [Γ] - the group algebra of Γ over F, does not have property τ. To see this, let us observe first that F ⟨x, y⟩ = F ⊗_{ℤ}ℤ⟨x, y⟩ does not have τ. Indeed, the latter would have implied that there exists ϵ > 0 such that for any n ∈ ℕ and any two generators a and b of M_{n}(F) and any subspace W of F^{n} with dim W ≤ \frac{n}{2}, we have dim(W + aW + bW) ≥ (1 + ϵ) dim W, which is clearly not the case. A general (easy) argument shows that if an F -algebra A does not have τ then M_{d}(A) does not have it either (see [LuZa] for this and more). Thus M_{d}(F ⟨x, y⟩) does not have τ. The algebra F [Γ] is mapped onto M_{d}(F ⟨x, y⟩) and so the same applies to it.

It is interesting to compare the last example with the results of Elek ([E1], [E2]). He defined a notion of “amenable algebra” and proved that a group Γ is amenable if and only if its group algebra ℂ[Γ] is amenable.

The above examples illustrate the delicacy of finding algebras with property τ over finite fields or similarly dimension expanders. The lack of unitarity is the main obstacle and the main problem we leave open is to find a method replacing it for fields of positive characteristic in general and finite fields in particular.

References

[BISW] B. Barak, R. Impagliazzo, A. Shpilka and A. Wigderson, Private communication.

[DS] Z. Dvir, A. Shpilka, In prepartion.

[E1] G. Elek, The amenability of affine algebras. J. Algebra 264(2003), 469–478.

[E2] G. Elek, The amenability and non-amenability of skew fields. arXiv:math.RA/0311375

[K1] M. Kassabov, Universal lattices and unbounded rank expanders, preprint February 2005. arXiv:math.GR/0502237

[K2] M. Kassabov, Symmetric groups and expanders (announcement), Electronic Research Announcements of AMS (to appear). arXiv:math.GR/0503204

[KN] M. Kassabov, N. Nikolov, Universal lattices and property τ. Preprint, February 2005. arXiv:math.GR/0502112

[Lu1] A. Lubotzky, Discrete groups, expanding graphs and invariant measures. Progress in Mathematics, 125. Birkhuser Verlag, Basel, 1994. xii+195 pp

[Lu2] A. Lubotzky, Cayley graphs: eigenvalues, expanders and random walks. Surveys in combinatorics, 1995 (Stirling), 155–189, London Math. Soc. Lecture Note Ser., 218, Cambridge Univ. Press, Cambridge, 1995.

[LuZa] A. Lubotzky, E. Zelmanov, On algebras with property τ. In preparation.

[Ma] G. Margulis, Discrete subgroups of semisimple Lie groups. Ergebnisse der Mathematik und ihrer Grenzgebiete (3) 17. Springer-Verlag, Berlin, 1991. x+388 pp.

[W] A. Wigderson, A lecture at IPAM, UCLA, February 2004.

Institute of Mathematics, Hebrew University, Jerusalem 91904 IS-RAEL

  E-mail address: alexlub@math.huji.ac.il

Department of Mathematics, University of California at San-Diego (UCSD), La Jolla, CA 92093-0112 USA

  E-mail address: ezelmano@math.ucsd.edu