The Euclidean distortion of the lamplighter group

Tim Austin^{∗} UCLA

  timaustin@math.ucla.edu

Assaf Naor^{†} Courant Institute

                             naor@cims.nyu.edu

Alain Valette Université de Neuchâtel

                                                  alain.valette@unine.ch

Abstract

We show that the cyclic lamplighter group C_{2} ≀C_{n} embeds into Hilbert space with distortion O ( \sqrt{logn}). This matches the lower bound proved by Lee, Naor and Peres in [14], answering a question posed in that paper. Thus the Euclidean distortion of C_{2} ≀C_{n} is Θ ( \sqrt{logn}). Our embedding is constructed explicitly in terms of the irreducible representations of the group. Since the optimal Euclidean embedding of a finite group can always be chosen to be equivariant, as shown by Aharoni, Maurey and Mityagin [1] and by Gromov (see [9]), such representation-theoretic considerations suggest a general tool for obtaining upper and lower bounds on Euclidean embeddings of finite groups.

1 Introduction

Given a bi-Lipschitz map f : X ↪ Y from one metric space (X, ρ_{X}) into another (Y, ρ_{Y}), the distortion of f is defined to be the product of the greatest expansion under f and that under its inverse:

dist(f) sup_{\begin{matrix}x,z∈X \\ x z \end{matrix}} \frac{ρ_{Y}(f (x), f (z))}{ρ_{X}(x, z)} · sup_{\begin{matrix}x,z∈X \\ x z \end{matrix}} \frac{ρ_{X}(x, z)}{ρ_{Y}(f (x), f (z))} .

We now define the overall distortion of X into Y to be the infimal distortion over all bi-Lipschitz f : X ↪ Y (and take this to be +∞ if no such maps exist), and write it c_{Y}(X). There are various contexts in which either a particular domain space or a particular target space is of interest; for example, the distortions of many different spaces into the Banach spaces Y = L_{p} have been studied extensively (see [16] for a partial survey of this area). In this case we write c_{p}(X) in place of c_{L_{p}}(X). In this paper we will be concerned with the case p = 2, and will refer to the distortion c_{2}(X) as the Euclidean distortion of X. We will usually denote Hilbert space by H, and will assume throughout that it is complex.

We will study the Euclidean distortion of a particular parameterized family of groups: the cyclic lamplighter groups. These are defined to be the wreath products of the order-two cyclic group C_{2} = {0, 1} by the cyclic groups C_{n} = {0, 1, …, n − 1}. In general, the wreath product L ≀H of some finite group L by some other finite group H is the semidirect product L^{H} H, where H acts on L^{H} by left multiplication of the coordinates. Concretely, L ≀H is the set L^{H} × H equipped with the multiplication

((x_{h})_{h∈H}, g)· ((y_{h})_{h∈H}, k) ((x_{h} · y_{gh})_{h∈H}, gk).

∗This work was conducted while T. Austin was visiting the Courant Institute of Mathematical Sciences, New York University.

†Research supported by NSF grants CCF-0635078 and DMS-0528387.

Thus, our object of study will be G C_{2} ≀C_{n}. Notice that in this case the discrete cube C_{2}^{C_{n}} appearing in the definition of G can be interpreted as the family PC_{n} of subsets of C_{n} by identifying x = (x_{k})_{k∈C_{n}} with {j ∈ C_{n} : x_{j} = 1}, so that the group operation within this cube is now the symmetric difference. Henceforth we will abuse notation and treat a point x ∈ C_{2}^{C_{n}} as a subset. This G is a finite solvable group, and can be generated by the two elements ({0}, 0) and (∅, 1); these then give rise to a left-invariant word metric ρ on the group.

In [14] it was shown by the method of Markov convexity that (with this metric understood) c_{2}(G) \sqrt{logn}. As noted in [14], an alternative proof of this lower bound follows from exhibiting a constant distortion embedding of a complete binary tree of depth Θ(n) into G (see [15]), and then applying Bourgain’s lower bound for the Euclidean distortion of trees [7]. Somewhat surprisingly, this embedded tree is an asymptotically worst-case obstruction to embedding the entire lamplighter group G into Hilbert space. Our main result is that the above lower bound is tight up to universal constants, answering a question posed in [14]:

Theorem 1.1. For each n there is a bi-Lipschitz map f : G ↪ H for which

ρ((x, j), (y, k)) ∥f (x, j) − f (y, k)∥ \sqrt{logn}· ρ((x, j), (y, k))

for all (x, j), (y, k) ∈ G.

We will construct an embedding of G of essentially least possible distortion of a very special type: we will first specify an action β of G on a Hilbert space H by unitary operators (i.e. a unitary representation), and then obtain the embedding into H itself by carefully choosing a suitable point v ∈ H and then mapping (x, j) ∈ G to the image of v under β(x, j). Hilbert space embeddings of groups constructed in this way are referred to as equivariant.

Note that if G is locally compact and Abelian, then any map f : G ↪ H can be analyzed via its vectorspace valued Fourier transform. The Euclidean embeddings of various Abelian groups and some associated discrete spaces have been successfully studied in this way: consider, for example, the analyses of flat Riemannian tori and of quotients of the Hamming cube under group actions in [11]. However, upon moving to non-Abelian groups a general framework for either proving good lower bounds on their Euclidean distortion or for isolating their low-distortion Euclidean embeddings is yet to emerge; in addition to our use of an analysis of irreducible representations to find such an embedding for the group of interest here, we discuss in Section 3 a result, due to Aharoni, Maurey and Mityagin [1] in the case of Abelian groups and to Gromov (see [9]) in the case of general amenable groups, according to which equivariant embeddings must always appear among those with minimal distortion. We finish with some applications of this basic fact and some open problems.

Remark on notation In addition to the Landau notation (o, O, Ω and Θ), in this paper we will use ≈ and , to denote, respectively, equality or the corresponding inequality up to some universal positive multiplicative constant. We will also write [f (x)|x ∈ X] for the average of some function f : X → over a finite set X.

2 The embedding

We will specify our embedding through an indexed family of irreducible representations of the lamplighter group, together with a vector in each of them. The direct sum of these representations gives a single (fairly high-dimensional) representation of the lamplighter group, together with the desired low-distortion equivariant embedding into Hilbert space through the image of the direct sum of these vectors.

2.1 The lamplighter group and its representations

It seems helpful to recall the following heuristic description of the lamplighter group with the aforementioned generators, if only for the exposition of some of our later proofs. Consider a collection of n lamps indexed by C_{n} (that is, say, positioned equidistantly around a circular street), together with a lighter, who walks along the street and either lights or douses lamps or leaves them unchanged.

We now interpret a pair (x, j) in G as an operation on the whole system of lamps and lighter: the lamps at those positions indexed by the set x ⊆ C_{n} will be changed (lighted if dark or vice-versa), and the lighter will move to a position j steps further round the circle C_{n}. (Note that alternatively we could think of (x, j) as describing the state of the system with the lamps at positions in x illuminated and the lighter at position j, but this intuition is a little less appropriate for understanding the group law; of course, this ‘state’ description of (x, j) simply arises by applying the ‘operation’ (x, j) to the state with all lamps doused and the lighter initially at 0.)

Given this description, we can think of the generator ({0}, 0) as the act of changing the lamp at the current location of the lamplighter, and similarly (∅, 1) as the act of the lamplighter moving one position to the next lamp around the circle. Let us write d_{C_{n}} for the obvious nearest-neighbour-graph metric on the cyclic group C_{n}.

We shall use the following simple approximation for the word metric ρ on G.

Lemma 2.1. The metric ρ satisfies

ρ((x, j), (y, ℓ)) ≈ d_{C_{n}}(j, k) + max_{k∈x△y}(d_{C_{n}}(0, k) + 1)

(where we interpret the maximum as 0 if x = y).

Proof Since ρ is an invariant metric it suffices to show that for all (x, j) ∈ G

ρ((x, j), (∅, 0)) ≈ d_{C_{n}}(0, j) + max_{k∈x}(d_{C_{n}}(0, k) + 1).

The ρ-distance of (x, j) from (∅, 0) is the length of the shortest word in ({0}, 0) and (∅, 1) and their inverses that evaluates to (x, j). Certainly, such a word must contain at least d_{C_{n}}(0, j) copies of either (∅, 1) or its inverse. Similarly, for any k ∈ x, any word evaluating to (x, j) must contain at least d_{C_{n}}(0, k) copies of the same generator, (∅, 1), or its inverse, since the lamplighter has to travel to position k ∈ C_{n} in order to change the lamp at position k. In the latter case the word must also contain at least one copy of ({0}, 0) for the act of changing that lamp. This proves that

ρ((x, j), (∅, 0)) ≥ d_{C_{n}}(0, j) + max_{k∈x}(d_{C_{n}}(0, k) + 1).

On the other hand, this reasoning shows at once that ρ((x, j), (x, 0))actually equals d_{C_{n}}(0, j) for any x ∈ C_{2}^{C_{n}} (since no lamps need be lit or doused for this journey of the lamplighter). In addition, for any x ∈ C_{2}^{C_{n}}, the lamplighter can change all the lamps of x by first traveling to the furthest point of x from 0 on one side of C_{n}, lighting the necessary lamps along the way, and then returning to the origin and repeating this exercise on the other side. This clearly takes at most 6 max_{k∈x}(d_{C_{n}}(0, k) + 1) steps, and therefore

ρ((x, j), (∅, 0)) ≤ ρ((x, j), (x, 0))+ ρ((x, 0), (∅, 0)) d_{C_{n}}(0, j) + max_{k∈x}(d_{C_{n}}(0, k) + 1),

as required.

Next we recall some of the unitary representations of G. Our list consists of all the irreducible representations when n is prime (these are found by the standard method of inducing representations; see [10]). For composite n some of these representations break up further. However, we will only use members of this list whole, and so will not trouble ourselves with the more complicated decompositions for composite n. The representations of interest fall naturally into two families:

• Some factor through the natural quotient mapping C_{2} ≀C_{n} C_{n} with kernel the normal subgroup C_{2}^{C_{n}} × {0}, and these are then given just by the (one-dimensional) irreducible representations of C_{n}: for each u ∈ {0, 1, …, n − 1} we obtain the character

χ_{u}(x, j) e^{2πiuj/n}Id_{},

where of course χ_{0} is just the trivial representation π_{triv}.

• The remainder of our list corresponds to direct sums of non-trivial one-dimensional irreducible representations of the cube tied together by a permutation action of the lamplighter-motion group C_{n}. Let α : C_{n} → C_{n} denote the cyclic left shift α(j) j − 1, and define for each A ⊆ C_{n} the Walsh function W_{A} : C_{2}^{C_{n}} → {−1, 1} by W_{A}(x) = (−1)^{|A∩x|}. For A {∅, C_{n}} we define the representation π_{A}: C_{2} ≀C_{n} ^{C_{n}} by

(π_{A}(∅, 1)v)_{k}  v_{k+1},
(π_{A}(x, 0)v)_{k}  W_{A}(α^{k}(x))v_{k} = (−1)^{|A∩α^{k}(x)|}v_{k}.

For A = C_{n} this is replaced by its more degenerate relative, the one-dimensional representation

π_{C_{n}}(x, j) (−1)^{|x|}Id_{}= W_{C_{n}}(α^{j}(x))Id_{}.

Note that there is a natural extension of the definition of π_{A} to the case A = ∅:

(π_{∅}(∅, 1)v)_{k} v_{k+1}  and  π_{∅}(x, 0) Id_{^{Cn}};  (1)

this is given simply by composing the quotient C_{2} ≀C_{n} C_{n} with the regular representation C_{n} ^{C_{n}}, and as such it is isomorphic to the direct sum of all the one-dimensional representations χ_{u} in the first part of our list.

Before introducing our specific embedding, let us motivate the construction by considering some generalities of the task of constructing a low distortion equivariant embedding from these ingredients. Suppose we have constructed an equivariant embedding f of G, expressed as

f (x, j) = β(x, j)v

for some unitary representation β : G H that decomposes as

β(x, j) = ( ⨁_{u∈C_{n}} ⨁_{r=1}^{a_{u}} χ_{u}(x, j))⊕ ( ⨁_{∅ A⊆C_{n}} ⨁_{s=1}^{b_{A}} π_{A}(x, j)),

where a_{u}, b_{A} ∈ ∪ {0} are multiplicities, and some vector

v = ( ⨁_{u∈C_{n}} ⨁_{r=1}^{a_{u}} v^{u,r})⊕ ( ⨁_{∅ A⊆C_{n}} ⨁_{s=1}^{b_{A}} v^{A,s}) ∈ H

with v^{u,r} (respectively v^{A,s}) lying in the r^{th} (respectively s^{th}) subspace corresponding to a subrepresentation χ_{u} (respectively π_{A}).

We can calculate a counterpart to Lemma 2.1 for use in our subsequent analysis:

∥f (x, j) − f (∅, 0)∥^{2} = ∑_{u∈C_{n}} ∑_{r=1}^{a_{u}} |e^{2πiju/n} − 1|^{2} |v^{u,r}|^{2} + ∑_{\begin{matrix}A⊆C_{n} \\ A ∅ \end{matrix}} ∑_{s=1}^{b_{A}} ∑_{k∈C_{n}} |W_{A}(α^{k}(x)) · v_{k+j}^{A,s} − v_{k}^{A,s}|^{2} .  (2)

Suppose now that we know for f the bounds

ρ((x, j), (y, k)) ≤ ∥f (x, j) − f (y, k)∥ ≤ Dρ((x, j), (y, k))

(that is, dist(f) ≤ D and f has been multiplied by a scalar if necessary so that it is non-contractive). Then one natural approach to proving lower bounds for D is to consider the averages of the squared distances ρ((x, j), (y, k))^{2} and ∥f (x, j) − f (y, k)∥^{2} for (x, j), (y, k) in some subsets of G for which the forms of the latter averages simplify in terms of our orthogonal decomposition for f. A lower bound for D can be obtained by comparing different such averages, as can some information on which equivariant embeddings might be close to attaining distortion D. Given the invariant nature of our functions of interest, we can simplify our task further by setting (y, k) = (∅, 0) and averaging only over (x, j).

For the sake of simplicity, we will consider this heuristic for f in which the one-dimensional representations χ_{u} appear only through the direct sum π_{∅} = ⨁ _{u∈C_{n}}χ_{u}, as described in (1), and in which all the multiplicities b_{A} are 1 (noting that if the vector v^{A} is 0 then the representation π_{A} effectively does not appear).

Suppose, then, that H is some subset of G. Then

[ρ((x, j), (∅, 0))^{2} |(x, j) ∈ H] ≤ [∥f (x, j) − f (∅, 0)∥^{2} |(x, j) ∈ H]
= ∑_{A⊆C_{n}} [∥π_{A}(x, j)v^{A}− v^{A}∥^{2} |(x, j) ∈ H]
= 2 ∑_{A⊆C_{n}} ∥v^{A}∥^{2} − 2 ∑_{A⊆C_{n}}ℜ ⟨ [π_{A}(x, j) |(x, j) ∈ H] v^{A}, v^{A}⟩.  (3)

This will be most helpful to us if we can arrange that for each A ⊆ C_{n} the expectation [π_{A}(x, j) |(x, j) ∈ H] takes a simple form on the copy of ^{C_{n}} corresponding to π_{A}. This happens, for example, if H is a subcube of the canonical subgroup C_{2}^{C_{n}} × {0} of G. (In fact, this can be fitted into a more general discussion of averages over subgroups, but we postpone this to Subsection 3.1.) If H = {(x, 0) : x ⊆ B} for some B ⊆ C_{n} then a straightforward calculation reduces (3) to

[ρ((x, 0), (∅, 0))^{2} |x ⊆ B]≤ 2 ∑_{A⊆C_{n}} ∑_{\begin{matrix}k∈C_{n} \\ B∩α^{−k}(A) ∅ \end{matrix}} |v_{k}^{A}|^{2} .

On the other hand, we can apply the upper bound on ∥f (x, j) − f (∅, 0)∥^{2} with (x, j) one of the generators to see that

D^{2} = D^{2}ρ((\{0\}, 0), (∅, 0))^{2} ≥ ∥f (\{0\}, 0) − f (∅, 0)∥^{2} = 2 ∑_{\begin{matrix}A⊆C_{n} \\ 0∈A \end{matrix}} ∥v^{A}∥^{2}

and

D^{2} = D^{2}ρ((∅, 1), (∅, 0))^{2} ≥ ∥f (∅, 1) − f (∅, 0)∥^{2} = 2 ∑_{A⊆C_{n}} ∑_{k∈C_{n}} |v_{k+1}^{A} − v_{k}^{A}|^{2} .

Finally, by actually estimating the expectation [ρ((x, 0), (∅, 0))^{2} |x ⊆ B]using Lemma 2.1, we can now use the above two inequalities to give a lower bound for D by comparing

∑_{A⊆C_{n}} ∑_{\begin{matrix}k∈C_{n} \\ B∩α^{−k}(A) ∅ \end{matrix}} |v_{k}^{A}|^{2}  (4)

against

∑_{\begin{matrix}A⊆C_{n} \\ 0∈A \end{matrix}} ∥v^{A}∥^{2} and ∑_{A⊆C_{n}} ∑_{k∈C_{n}} |v_{k+1}^{A} − v_{k}^{A}|^{2}  (5)

for different possible choices of v^{A}.

Such a comparison might rely on the Poincaré inequality for the discrete circle C_{n}, applied to the functions v_{•}^{A}. However, a careful examination now shows that playing with different choices of B ⊆ C_{n} does not give a non-trivial (that is to say, growing in n) lower bound for D, even though we know from the Markov convexity calculation that D \sqrt{logn}.

This very failure does, however, suggest that relatively low-distortion embeddings might be found by looking for those v^{A} that are close to saturating the Poincaré inequality for C_{n}. For each A ⊆ C_{n} this inequality bounds the overall average squared difference

\frac{1}{n^{2}} ∑_{j,k∈C_{n}} |v_{j}^{A}− v_{k}^{A}|^{2} ,

by a multiple of the local average

\frac{1}{n} ∑_{k∈C_{n}} |v_{k+1}^{A} − v_{k}^{A}|^{2} .

In general, the latter must be multiplied by n^{2} to bound the former, but this inequality is close to tight only if the function v_{•}^{A} varies relatively slowly around the circle (that is, if its Fourier transform is concentrated at low frequencies). One finds that this near-saturation is necessary in order to obtain a small distortion estimate from (4) and (5) when B = C_{n}. On the other hand, for more general B the resulting estimate can be kept small only if we know that a positive proportion of the mass ∑ _{A⊆C_{n}} ∥v^{A}∥^{2} is contributed by sets that intersect B; and this, in turn, requires that the distribution of the squared norms ∥v^{A}∥^{2} be approximately invariant under rotations of the sets A and be spread roughly uniformly over sets A of a broad range of different sizes.

We have suppressed the calculations behind this discussion, as we are presently trying only to be motivational. One is led naturally to consider sets A ⊆ C_{n} that can be quite large, but are not evenly distributed around C_{n}, so that there is some large arc of C_{n} away from A into which we can concentrate most of the ℓ^{2}(C_{n})-norm of a slowly-varying function v_{•}^{A}. In the next subsection we will construct an embedding from this intuition, using all subsets A that lie within some arc I of the circle C_{n} of length ⌊n/3⌋. Of course, we must concede a distortion of least Ω( \sqrt{logn}) somewhere, and it turns that this is manifested for the best possible choice of v^{A} in a slight shortfall from saturation of the Poincaré inequality.

2.2 The embedding itself

The irreducible representations and corresponding vectors that we will use will be indexed by pairs (I, A) for I an arc (i.e. a connected subset) of C_{n} of length ⌊n/3⌋ and A ⊆ I. Let us write I for the family of such arcs, of which there are n, and PI for the collection of subsets of a given arc I. For each pair (I, A), the corresponding irreducible representation will simply be that indexed by A in the list of the previous subsection, retaining the convention that for A = ∅ we identify π_{∅} with the regular-quotient representation C_{2} ≀C_{n} C_{n} ^{C_{n}}, which is isomorphic to the direct sum ⨁ _{u∈C_{n}}χ_{u}.

We still need to specify the associated vector v^{A,I}. We will take this to depend only on I, defining (v_{k}^{I})_{k∈C_{n}} by

v_{k}^{I} \{ \begin{matrix}η & k ∈ I \\ δ \sqrt{d_{C_{n}}(k, I)} & k I. \end{matrix}

This definition depends on the choice of the two parameters δ, η. The analysis that follows below can be performed by first allowing these to be free and then optimizing them; we obtain

η \frac{1}{n2^{n/6}} and δ \frac{1}{\sqrt{n}2^{n/6}}.

Another optimization is also implicit in our definition of v_{k}^{I}: a priori, we could have taken v_{k}^{I} to be of the form δ · d_{C_{n}}(k, I)^{α} for k I and then optimized also over α > 0. This optimization does naturally lead to the exponent α = \frac{1}{2}: it turns out that all other values of α give distortion following a positive power law in n.

Note that this function v_{•}^{I} has the qualitative properties suggested by our heuristic argument of the previous subsection: it witnesses the small constant 1/n^{2} to within a factor of logn for the Poincaré inequality on the circle C_{n}, and has only a very small part of its ℓ^{2}(C_{n})-norm inside the arc I ⊇ A. We have restricted ourselves to those sets A that can be contained in some arc I of the circle precisely so that in each summand with representation π_{A} the associated vector v^{A,I} can be chosen to take small values on A but still be close to optimal for the Poincaré inequality.

Assembling the above, our overall embedding of C_{2} ≀C_{n} is given by

f (x, j) = ⨁_{I∈I} ⨁_{A∈PI}π_{A}(x, j)v^{I} = ⨁_{I∈I} ⨁_{A∈PI}(W_{A}(α^{k}(x)) · v_{k+j}^{I})_{k∈C_{n}}.

We can now specialize the identity (2) to this data (adjusting to our convention for π_{∅}) and so compute:

∥f (x, j) − f (∅, 0)∥^{2} = ∑_{I∈I} ∑_{A∈PI} ∑_{k∈C_{n}} |W_{A}(α^{k}(x))v_{k+j}^{I} − v_{k}^{I}|^{2}

≈ ∑_{I∈I} ∑_{A∈PI}( ∑_{k∈C_{n}} |v_{k+j}^{I} − v_{k}^{I}|^{2} + ∑_{k∈C_{n}}1_{{W_{A}(α^{k}(x))=−1}}|v_{k}^{I}|^{2} ), (6)

where in the second step we have used the additional fact that our vectors (v_{k}^{I})_{k∈C_{n}} have non-negative real entries, so that

|W_{A}(α^{k}(x))v_{k+j}^{I} − v_{k}^{I}|^{2} = \{ \begin{matrix}|v_{k+j}^{I} − v_{k}^{I}|^{2} & if W_{A}(α^{k}(x)) = 1 \\ |v_{k+j}^{I} + v_{k}^{I}|^{2} & if W_{A}(α^{k}(x)) = −1 \end{matrix} ≈ |v_{k+j}^{I} − v_{k}^{I}|^{2} + 1_{\{W_{A}(α^{k}(x))=−1\}}|v_{k}^{I}|^{2} ,

where we also used the elementary fact that \frac{(a+b)^{2}}{(a−b)^{2}+b^{2}} ∈ [\frac{1}{5}, 2]for every a, b > 0.

Proof of Theorem 1.1 We prove the upper and lower bounds on ∥f (x, j) − f (y, k)∥^{2} separately. Note that since both this embedded distance and the original metric ρ are G-invariant it suffices to consider the case (y, k) = (∅, 0).

Step 1: upper bound We wish to show that

∥f (x, j) − f (∅, 0)∥ \sqrt{logn}· ρ((x, j), (∅, 0))

for all (x, j) ∈ G. Since ρ is a word metric it suffices to check this for (x, j) equal to each of the two generators.

Suppose first that (x, j) = ({0}, 0). Then our formula (6) gives

∥f ({0}, 0) − f (∅, 0)∥^{2} ≈ ∑_{I∈I} ∑_{A∈PI} ∑_{k∈C_{n}}1_{{W_{A}(α^{k}({0}))=−1}}|v_{k}^{I}|^{2} = ∑_{I∈I} ∑_{A∈PI} ∑_{k∈A} |v_{k}^{I}|^{2} = η^{2}n ∑_{A∈PI}|A| ≈ η^{2}n^{2}2^{n/3} = 1,

owing to our choice of η.

Similarly, setting (x, j) = (∅, 1), we obtain

∥f (∅, 1) − f (∅, 0)∥^{2} ≈ ∑_{I∈I} ∑_{A∈PI}( ∑_{k∈C_{n}} |v_{k+1}^{I} − v_{k}^{I}|^{2} + ∑_{k∈C_{n}}1_{{W_{A}(∅)=−1}}|v_{k}^{I}|^{2} ) = ∑_{I∈I} ∑_{A∈PI} ∑_{k∈C_{n}} |v_{k+1}^{I} − v_{k}^{I}|^{2} .

From our choice of v^{I} we deduce that

|v_{k+1}^{I} − v_{k}^{I}|≈ \{ \begin{matrix}0 & if k, k + 1 ∈ I \\ |δ − η| ≈ |δ| & if |I ∩ \{k, k + 1\}| = 1 \\ δ_{\frac{1}{\sqrt{d_{Cn}(k,I)}}} & if k, k + 1 ∈ C_{n} \ I, \end{matrix}

and so the above sum can be bounded by

∥f (∅, 1) − f (∅, 0)∥^{2}  2δ^{2} ∑_{I∈I} ∑_{A∈PI} ∑_{k=1}^{⌊n/3⌋}( \frac{1}{\sqrt{k}})^{2} = 2δ^{2} ∑_{I∈I} ∑_{A∈PI} ∑_{k=1}^{⌊n/3⌋}\frac{1}{k} ≈ 2δ^{2}n2^{n/3}logn ≈ logn,

owing to our choice of δ.

Taking square roots and comparing these two estimates with the approximation given by Lemma 2.1 completes the check of both generators, and so also the proof of the upper bound; note that these two checks already dictate our choice of η and δ up to O( \sqrt{logn}) and Ω(1/ \sqrt{logn}) respectively.

Step 2: lower bound We will obtain the lower bound

∥f (x, j) − f (∅, 0)∥ ρ((x, j), (∅, 0))

by breaking the sum

∑_{I∈I} ∑_{A∈PI}( ∑_{k∈C_{n}} |v_{k+j}^{I} − v_{k}^{I}|^{2} + ∑_{k∈C_{n}}1_{{W_{A}(α^{k}(x))=−1}}|v_{k}^{I}|^{2} )

into the two obvious subsums and estimating these separately.

Step 2.1: first sum We will use a rather crude estimate obtained by considering various ranges of possible values of d_{C_{n}}(0, j) and for each of them summing over only a certain range of k; this will be enough to obtain the lower bound we seek.

Observe from the definition of v_{k}^{I} that if d_{C_{n}}(0, j) ≤ d_{C_{n}}(k, I) ≤ n/3 − d_{C_{n}}(0, j) then

|v_{k+j}^{I} − v_{k}^{I}| δ \frac{d_{C_{n}}(0, j)}{\sqrt{d_{C_{n}}(k, I)}}.

Suppose first that d_{C_{n}}(0, j) ≤ n/100; then taking only those k in the above range gives the lower bound

∑_{I∈I} ∑_{A∈PI} ∑_{k∈C_{n}} |v_{k+j}^{I} − v_{k}^{I}|^{2} δ^{2} ∑_{I∈I} ∑_{A∈PI} ( ∑_{k: d_{Cn}(0,j)≤d_{Cn}(k,I)≤n/3−d_{Cn}(0,j)} ( \frac{d_{C_{n}}(0, j)}{\sqrt{d_{C_{n}}(k, I)}})^{2})

≥ δ^{2}d_{C_{n}}(0, j)^{2} (n2^{⌊n/3⌋−1}) ∑_{k=⌈n/100⌉}^{⌊n/3−n/100⌋}\frac{1}{k} ≈ (δ^{2}n2^{n/3})d_{C_{n}}(0, j)^{2} ≈ d_{C_{n}}(0, j)^{2},

recalling our choice of δ.

On the other hand, if d_{C_{n}}(0, j) > n/100, then for those two arcs J_{1} and J_{2} of points k ∈ C_{n} satisfying 0 < d_{C_{n}}(k, I) < n/1000, at least one of them, say J_{1}, is such that d_{C_{n}}(k + j, I) ≥ 10d_{C_{n}}(k, I) for all k ∈ J_{1}. These k ∈ J_{1} therefore satisfy also

|v_{k+j}^{I} − v_{k}^{I}| \sqrt{n/1000}.

Therefore, taking instead the sum over J_{1} in the above estimate, we have

∑_{I∈I} ∑_{A∈PI} ∑_{k∈C_{n}} |v_{k+j}^{I} − v_{k}^{I}|^{2} δ^{2} ∑_{I∈I} ∑_{A∈PI} ∑_{k∈J_{1}}( \sqrt{n/1000})^{2} (δ^{2}n2^{n/3})(n/1000)^{2} d_{C_{n}}(0, j)^{2}.

In either case, we obtain

∑_{I∈I} ∑_{A∈PI} ∑_{k∈C_{n}} |v_{k+j}^{I} − v_{k}^{I}|^{2} d_{C_{n}}(0, j)^{2}.

Step 2.2: second sum We now require a lower bound on

∑_{I∈I} ∑_{A∈PI} ∑_{k∈C_{n}}1_{{|A∩α^{k}(x)| odd}}|v_{k}^{I}|^{2} = ∑_{I∈I} ∑_{k∈C_{n}} |v_{k}^{I}|^{2} ( ∑_{A∈PI}1_{{|A∩α^{k}(x)| odd}}).

Note that for any non-empty subset B of C_{n} and for each I ∈ I, if we choose a subset A of I uniformly at random then the probability that the intersection size |A ∩ B| is odd is 1/2 if I ∩ B ∅ and 0 if I ∩ B = ∅. Indeed, choosing a subset A of I uniformly at random and then considering A ∩ B simply generates a subset of I ∩ B uniformly at random; but precisely half of these are odd unless I ∩ B = ∅, in which case they are all even. Applying this reasoning with B = α^{k}(x), we conclude that

∑_{A∈PI}1_{\{|A∩α^{k}(x)| odd\}}= \frac{1}{2}|PI|1_{\{I∩α^{k}(x) ∅\}} = 2^{⌊n/3⌋−1}1_{\{I∩α^{k}(x) ∅\}},

and so our sum of interest simplifies to

2^{⌊n/3⌋−1}∑_{I∈I} ∑_{k∈C_{n}}1_{{I∩α^{k}(x) ∅}} |v_{k}^{I}|^{2} .

Suppose that ℓ ∈ x is a point of x at a maximal distance from 0 in C_{n}. Then, in particular, I∩α^{k}(x) ⊇ I∩{ℓ+k} is nonempty for all k ∈ α^{−ℓ}(I), and so

2^{⌊n/3⌋−1}∑_{I∈I} ∑_{k∈C_{n}}1_{{I∩α^{k}(x) ∅}} |v_{k}^{I}|^{2} ≥ 2^{⌊n/3⌋−1}∑_{I∈I} ∑_{k∈α^{−ℓ}(I)} |v_{k}^{I}|^{2} .

Therefore it will suffice to give a suitably strong lower bound for ∑ _{k∈α^{−ℓ}(I)} |v_{k}^{I}|^{2}. Moreover we see from the rotational symmetry in our definition of v^{I} that this quantity is the same for all I ∈ I. We may therefore assume that in the natural labeling of C_{n} as {1, 2, …, n} the arc I appears as an initial segment, and appealing to symmetry further, we may replace ℓ by −ℓ and assume that ℓ ∈ {1, 2, …, ⌊n/2⌋}. Given this, the terms appearing in the desired sum are:

• terms equal to η corresponding to k ∈ I ∩ α^{ℓ}(I), and hence to k ∈ {ℓ + 1, …, ⌊n/3⌋};

• the remaining terms δ, δ \sqrt{2}, δ \sqrt{3}, …, δ \sqrt{ℓ}.

Squaring these and summing them therefore yields

(⌊n/3⌋ − ℓ)η^{2} + δ^{2} ∑_{t=1}^{ℓ} t ≈ (n/3 − ℓ)η^{2} + δ^{2}ℓ^{2},

and so overall

∑_{I∈I} ∑_{A∈PI} ∑_{k∈C_{n}}1_{{|A∩α^{k}(x)| odd}}|v_{k}^{I}|^{2} n2^{n/3}((n/3 − ℓ)η^{2} + δ^{2}ℓ^{2}) 1 + ℓ^{2},

recalling again our choices of δ and η.

Completion of step 2 Given the above estimates for the first and second sum of our expression we deduce the lower bound

∥f (x, j) − f (∅, 0)∥^{2} d_{C_{n}}(0, j)^{2} + 1 + ℓ^{2}.

Recalling the choice of ℓ, taking square roots and comparing this with the expression of Lemma 2.1 completes the proof.

3 Discussion and further questions

This section is composed of two parts.

In Subsection 3.1 we present the known result that equivariant Euclidean embeddings of finite groups with invariant metrics always appear among the embeddings of minimal distortion. This justifies a reduction to the consideration of equivariant embeddings of which we then give two applications.

In Subsection 3.2 we discuss some further questions.

3.1 Equivariant embeddings suffice

Unlike the special embedding of the lamplighter group constructed in Subsection 2.2, a generic Hilbert space embedding is certainly not equivariant. However, it turns out that searching in this smaller class was, in a sense, guaranteed to work: for an invariant metric on a finite group the restricted family of equivariant embeddings must contain embeddings of distortion at least as low as any other. This is the conclusion of Lemma 3.1 below. For the same reason it suffices to consider equivariant embeddings when proving Euclidean distortion lower bounds for invariant metrics on finite groups. The formulation we give of Lemma 3.1 below is a simplified version for the case of finite groups which we will use to investigate quantitative distortion bounds. In the case of infinite Abelian groups this lemma was used by Aharoni, Maurey and Mityagin [1] in their work on uniform embeddings of Banach spaces into Hilbert space (see also chapter 8 in the book [6]). The lemma was discovered independently by Gromov (unpublished) in the case of arbitrary amenable groups, and was used by de Cornulier, Tessera and Valette [9] (in terms of Hilbert space valued cocycles) to prove qualitative non-embeddability results for certain such groups. Note that an analogous lemma holds for uniform embeddings into Hilbert space, but for the sake of simplicity we present only the bi-Lipschitz case.

Lemma 3.1. If a finite group G with a left-invariant metric ρ has a Euclidean embedding f such that

\frac{1}{B}∥f (x) − f (y)∥ ≤ ρ(x, y) ≤ A∥f (x) − f (y)∥  (7)

for all x, y ∈ G, then there is an equivariant embedding g into a Hilbert space H, say g = β(·)v for v ∈ H and β : G H a unitary representation, which satisfies the same inequalities as in (7).

Proof Define a positive semidefinite scalar product on ^{G} by K(δ_{x}, δ_{y}) \frac{1}{|G|}∑ _{z∈G}⟨f (zx), f (zy)⟩. The required embedding g : G → ^{G} is simply given by g(x) δ_{x}. Let β denote the left-regular representation of G on ^{G}. Then g(x) = β(x)δ_{e}, where e is the identity element of G. Now we compute that

\frac{∥g(x) − g(y)∥_{K}^{2}}{ρ(x, y)^{2}} = \frac{1}{|G|}∑_{z∈G}(\frac{∥f (zx)∥^{2} + ∥f (zy)∥^{2} − 2⟨f (zx), f (zy)⟩}{ρ(x, y)^{2}}) = \frac{1}{|G|}∑_{z∈G} \frac{∥f (zx) − f (zy)∥^{2}}{ρ(zx, zy)^{2}}.  (8)

By (7) each of the summands in (8) lies between 1/B^{2} and A^{2}, and hence so does the whole expression, as required. It remains to note that ∥g(x)∥ is independent of x ∈ G, so that β is a unitary representation with respect to the scalar product K.

Given this, we can now prove for arbitrary finite groups a formalized version of the heuristic lower-bound analysis that was presented in Subsection 2.1 to motivate the construction of our embedding:

Lemma 3.2. Let G be a finite group generated by S ⊆ G and let ρ be the corresponding word metric. Let γ_{1} H_{1}, …, γ_{t} H_{t} be the nontrivial irreducible representations of G. Then there exist integers a_{1}, …, a_{t} ≥ 0 satisfying ∑ _{j=1}^{t} a_{j} dim(H_{j}) ≤ |G| and sets of vectors {v^{j,r}}_{r=1}^{a_{j}} ⊆ H_{j} for which

c_{2}(G) ≥ \sqrt{\frac{∑ _{x∈G}ρ(x, e)^{2}}{2|G|} · \frac{∑ _{s∈S} ∑ _{j=1}^{t} ∑ _{r=1}^{a_{j}} ∥γ_{j}(s)v^{j,r} − v^{j,r} ∥^{2}}{|S| ∑ _{j=1}^{t} ∑ _{r=1}^{a_{j}} ∥v^{j,r} ∥^{2}}}.

Proof Assume that there exists a Euclidean embedding f satisfying (7), and let g be the equivariant embedding from Lemma 3.1. Note that its dimension is at most |G|. We can write β = ⨁ _{j=1}^{t} γ_{j}^{⊕a_{j}} , where a_{j} ∈ ∪ {0} are multiplicities. Correspondingly we decompose the vector v from Lemma 3.1 as v = ⨁ _{j=1}^{t} ⨁ _{r=1}^{a_{j}} v^{j,r}. Then

∑_{x∈G}ρ(x, e)^{2} ≤ A^{2} ∑_{x∈G}∥g(x) − g(e)∥^{2}

= A^{2} ∑_{x∈G} ∑_{j=1}^{t} ∑_{r=1}^{a_{j}} ∥γ_{j}(x)v^{j,r} − v^{j,r} ∥^{2}

= A^{2} ∑_{x∈G} ∑_{j=1}^{t} ∑_{r=1}^{a_{j}} (2 ∥v^{j,r} ∥^{2} − 2ℜ ⟨γ_{j}(x)v^{j,r}, v^{j,r}⟩)

= 2A^{2}|G| ∑_{j=1}^{t} ∑_{r=1}^{a_{j}} ∥v^{j,r} ∥^{2} − 2A^{2} ∑_{j=1}^{t} ∑_{r=1}^{a_{j}} ℜ ⟨( ∑_{x∈G}γ_{j}(x))v^{j,r}, v^{j,r}⟩

= 2A^{2}|G| ∑_{j=1}^{t} ∑_{r=1}^{a_{j}} ∥v^{j,r} ∥^{2} ,  (9)

since ∑ _{x∈G}γ_{j}(x) = 0, by the irreducibility of γ_{j} (see [10]). On the other hand

|S| = ∑_{s∈S} ρ(s, e)^{2} ≥ \frac{1}{B^{2}} ∑_{s∈S} ∥g(s) − g(e)∥^{2} = \frac{1}{B^{2}} ∑_{s∈S} ∑_{j=1}^{t} ∑_{r=1}^{a_{j}} ∥γ_{j}(s)v^{j,r} − v^{j,r} ∥^{2} .

It follows that

AB ≥ \sqrt{\frac{∑ _{x∈G}ρ(x, e)^{2}}{2|G|} · \frac{∑ _{s∈S} ∑ _{j=1}^{t} ∑ _{r=1}^{a_{j}} ∥γ_{j}(s)v^{j,r} − v^{j,r} ∥^{2}}{|S| ∑ _{j=1}^{t} ∑ _{r=1}^{a_{j}} ∥v^{j,r} ∥^{2}}}.

Infimizing over AB yields the required result.

Remark We can obtain a larger family of lower bounds for c_{2}(G) by modifying the first part of the proof of Lemma 3.2 to the case of a sum over a subgroup H of G. However, this can lead to a more complicated expression owing to the decomposition of the representations γ_{j} into smaller irreducible representations of H. Let π_{1} K_{1}, …, π_{m} K_{m}be the irreducible representations of H, where π_{1} is the trivial representation Id_{K_{1}}. Upon writing γ_{j} as ⨁ _{ℓ=1}^{m} π_{ℓ}^{⊕b_{j,ℓ}} and correspondingly v^{j,r} as ⨁ _{ℓ=1}^{m} ⨁ _{u=1}^{b_{j,ℓ}} v_{ℓ,u}^{j,r}, the sum ∑ _{x∈H} γ_{j}(x)

equals (|H|Id_{K_{1}}^{⊕b_{j,1}} )⊕ 0. This leads to a modification of (9), and thence to another lower bound on the Euclidean distortion via the same argument.

In the case of the lamplighter group, this further decomposition remains manageable, and it was by trying to approach equality in the resulting lower bounds that we were led to the embedding of Subsection 2.2.

Remark As indicated in Subsection 2.1, the lamplighter group G = C_{2} ≀C_{n} has the curious property that it does not embed into Hilbert space with distortion bounded independent of n, but this nonembeddabability is not detectable (in the sense of Lemma 3.2 and the remark that follows it) by comparing the averages of the squared group distances ρ(x, y)^{2} and of the squared embedded distances ∥f (x) − f (y)∥^{2} across subgroups of G (the natural averages to take) against the averages across local movements using the two generators. We find instead that for any given subgroup of G, G itself has embeddings into Hilbert space that look good on average across that subgroup, and ‘push’ the bad distortion (which we know must be at least Ω( \sqrt{logn}) somewhere) into some set of pairs of point in the group that this average does not see. We should stress that different subgroups may require slightly different embeddings: the Ω( \sqrt{logn}) distortion of our actual construction of Subsection 2.2, for example, can be detected by looking at averages across suitably-chosen subgroups of G, while other embeddings, poorer overall, cannot be detected by those subgroups. The point is that no small collection of different subgroups reliably finds the distortion. This conclusion follows from considering a number of variants of the embedding of Subsection 2.2; however, the necessary calculations seem more lengthy than revealing and we will not discuss them in detail here. Furthermore, one can also compute easily given the methods of [17] that G, like Hilbert space, does have Markov type 2 (another averaging-based invariant for metric spaces introduced by Ball in [5]) with constant independent of n, so that this also does not give an observable obstruction to Hilbert space embeddings.

It results that both the minimal Euclidean distortion of G and also embeddings witnessing that distortion are hard to find using standard averaging-based machinery. Some quite delicate averaging-based obstruction, such as the Markov convexity actually used to study this group in [14], is really necessary. Furthermore, while that application of Markov convexity in [14] does amount to the identification of a large embedded tree in G, it is not at all clear a priori that the minimal-distortion embeddings of this embedded tree already tell us just how bad the Euclidean distortion of the whole group must be, or how to attain that distortion. It is somewhat surprising that this invariant happens to give the correct growth rate of the Euclidean distortion, and it might be interesting to ask whether Markov convexity — based, in this case, on the presence of large embedded trees inside G — can be replaced by some averaging argument using a different kind of substructure of G to give the same lower bound.

We will finish our discussion of the consequences of Lemma 3.1 with a more concrete application. Recall that a metric space (X, ρ) is of negative type if the space X with the square root metric \sqrt{ρ} embeds isometrically into Hilbert space. The Goemans-Linial conjecture asserted that any such metric also embeds with bounded distortion into L_{1}. This is now known to be false in general: see Khot and Vishnoi [12]. Their construction did not give an invariant group metric; however, more recently Lee and Naor [13] have shown that a particular invariant metric on the Heisenberg group is also a counterexample to the Goemans-Linial conjecture, using a result of Cheeger and Kleiner [8]. On the other hand, the following proposition shows that such counterexamples cannot arise from Abelian groups subject to a restriction on the exponent of the group (and we suspect that this restriction can be removed).

Proposition 3.3. Let (G, ρ) be a finite Abelian group equipped with an invariant metric. Suppose that 2 ≤ m ∈ satisfies mx = 0 for all x ∈ G. Let D = c_{2} (G, \sqrt{ρ}). Then

c_{1}(G, ρ) D^{4} logm

and for all 1 < p < 2

c_{p} (G, ρ^{1/p}) \frac{D^{4/p}}{p − 1} .

Proof Let Γ = Ĝ denote the dual of G. By Lemma 3.1 (G, \sqrt{ρ}) admits a distortion-D embedding into Hilbert space which is equivariant, and so which breaks into a direct sum of characters and associated vectors. By rescaling it follows that there are {a_{χ}}_{χ∈Γ} ⊆ _{+} such that for all x ∈ G,

∑_{χ∈Γ} a_{χ} |1 − χ(x)|^{2} ≤ ρ(x, 0) ≤ D^{2} ∑_{χ∈Γ} a_{χ} |1 − χ(x)|^{2} .  (10)

For every x ∈ G and k ≥ 0 denote

A_{k}(x) {χ ∈ Γ : 2^{−k} < |χ(x) − 1| ≤ 2^{−k+1}} .

We also define A_{∞} (x) {χ ∈ Γ : χ(x) = 1}. Then Γ = A_{∞} (x) ∪ ⋃ _{k=0}^{∞} A_{k}(x) and this union is disjoint. Moreover, 1 = χ(0) = χ(mx) = χ(x)^{m}, so that χ(x) is an m^{th} root of unity. Therefore if χ(x) 1 then |χ(x) − 1| ≥ |e^{2πi/m}− 1| ≥ \frac{1}{m}. It follows that for finite k > log_{2} m + 1 the set A_{k}(x) is empty.

It follows routinely from the definition of A_{k}(x) that, firstly,

∑_{χ∈A_{k}(x)}a_{χ} |1 − χ(x)|^{2} ≥ 2^{−k} ∑_{χ∈A_{k}(x)}a_{χ} |1 − χ(x)| ,  (11)

and, secondly, that for every χ ∈ A_{k}(x)

|1 − χ(x)^{2^{k−1}} | 2^{k}|1 − χ(x)|.  (12)

Moreover, by the invariance of ρ and the triangle inequality, we know that for every k ≥ 1,

2^{k−1}ρ(x, 0) ≥ ρ (2^{k−1}x, 0).  (13)

Therefore, for every k ≥ 1 we have

2^{k−1} ∑_{χ∈Γ} a_{χ}|1 − χ(x)|^{2} ≥^{(10)} \frac{2^{k−1}}{D^{2}}ρ(x, 0) ≥^{(13)} \frac{1}{D^{2}}ρ (2^{k−1}x, 0) ≥^{(10)} \frac{1}{D^{2}} ∑_{χ∈Γ} a_{χ} |1 − χ(2^{k−1}x)|^{2}

≥ \frac{1}{D^{2}} ∑_{χ∈A_{k}(x)}a_{χ} |1 − χ(x)^{2^{k−1}} |^{2} ^{(12)} \frac{2^{2k}}{D^{2}} ∑_{χ∈A_{k}(x)}a_{χ} |1 − χ(x)|^{2} ^{(11)} \frac{2^{k}}{D^{2}} ∑_{χ∈A_{k}(x)}a_{χ} |1 − χ(x)| . (14)

Thus (for k ≥ 1 by (14), and trivially for k = 0)

∑_{χ∈A_{k}(x)}a_{χ} |1 − χ(x)| D^{2} ∑_{χ∈Γ} a_{χ}|1 − χ(x)|^{2},  (15)

and so, combining the above,

\frac{ρ(x, 0)}{D^{2}} ≤^{(10)} ∑_{χ∈Γ} a_{χ}|1 − χ(x)|^{2} ≤ 2 ∑_{χ∈Γ} a_{χ}|1 − χ(x)| = 2 ∑_{k≤log_{2}(2m)} ∑_{χ∈A_{k}(x)}a_{χ}|1 − χ(x)|

^{(15)} D^{2} logm ∑_{χ∈Γ} a_{χ}|1 − χ(x)|^{2} ≤^{(10)} D^{2} logm · ρ(x, 0). (16)

Let μ be the measure on Γ given by μ({χ}) = a_{χ} and consider the embedding f : G → L_{1}(Γ, μ) defined by f (x)(χ) χ(x). Inequality (16) says precisely that dist(f) D^{4} logm. This completes the proof of the first assertion of the proposition.

The proof of the second assertion is similar. Analogously to (11),

∑_{χ∈A_{k}(x)}a_{χ} |1 − χ(x)|^{2} ≥ 2^{−k(2−p)} ∑_{χ∈A_{k}(x)}a_{χ} |1 − χ(x)|^{p} .

Arguing as for (14)

∑_{χ∈A_{k}(x)}a_{χ} |1 − χ(x)|^{p} D^{2}2^{−(p−1)k} ∑_{χ∈Γ} a_{χ}|1 − χ(x)|^{2}.

Hence

\frac{ρ(x, 0)}{D^{2}} ≤ ∑_{χ∈Γ} a_{χ}|1 − χ(x)|^{2} ≤ 2^{2−p} ∑_{χ∈Γ} a_{χ}|1 − χ(x)|^{p} = 2^{2−p} ∑_{k=0}^{∞} ∑_{χ∈A_{k}(x)}a_{χ}|1 − χ(x)|^{p}

D^{2} ∑_{k=0}^{∞} 2^{−(p−1)k} ∑_{χ∈Γ} a_{χ}|1 − χ(x)|^{2} ≤ \frac{D^{2}}{1 − 2^{−(p−1)}} · ρ(x, 0) \frac{D^{2}}{p − 1} · ρ(x, 0), (17)

and we may now take the same f as above to give the required embedding into L_{p}(Γ, μ).

Remark Proposition 3.3 implies, in particular, that any invariant metric ρ on the discrete cube {0, 1}^{d} for which c_{2} (\{0, 1\}^{d}, \sqrt{ρ})= D has also c_{1} (\{0, 1\}^{d}, ρ) D^{4}. It seems likely that the fourth power is far from optimal. More interestingly, for general finite Abelian groups we see no compelling reason to believe that the factor of logm in Proposition 3.3 is necessary. If it can be removed, this would imply that no invariant metric on a finite Abelian group can serve as a counterexample to the Goemans-Linial conjecture. (Note that when G is the cyclic group C_{m} the factor logm can already be improved to \sqrt{logm}· loglogm by the general result of [4].)

3.2 Further questions

We speculate that the methods suggested by Lemma 3.1 can be used to give a fuller analysis of minimal distortion Euclidean embeddings for various groups and homogeneous spaces. For example, our experience with the lamplighter group suggests that the methods of this paper may bear on other wreath products L ≀H; however, we should observe at once that the behaviour of these can depend radically on the choice of generators, even among those obtained by choosing generators for the acting group H and then including a suitable additional member of L^{H}:

Proposition 3.4. Let S be a uniformly random subset of C_{n} of cardinality |S| ≥ 100 logn, conditioned on the event that it generates C_{n} (which occurs asymptotically almost surely). Consider the wreath product C_{2} ≀C_{n} equipped with the word metric ρ corresponding to the generating set ({∅} × S)∪ {({0}, 0)}. Then

c_{2} (C_{2} ≀C_{n}, ρ) \sqrt{n}

asymptotically almost surely.

Proof Let G be the Cayley graph of C_{n} with the generating set S. Then by [2] the metric ρ on C_{2}≀C_{n} is the shortest path metric on the zig-zag product of the Hamming cube C_{2}^{C_{n}} (with the standard graph structure) and the graph G, which we denote by Z (we refer to [2, 18] for the definition and properties of the zig-zag product). Let λ_{1} be the normalized second eigenvalue of C_{2}^{C_{n}} and let λ_{2} be the normalized second eigenvalue of G. Then it is well known that λ_{1} = 1 − \frac{2}{n}, and the Alon-Roichman theorem [3] states that λ_{2} is bounded away from 1 asymptotically almost surely. By Theorem 4.3 in [18], the normalized second eigenvalue of Z, which we denote by λ, is at most

\frac{1}{2} (1 − λ_{2}^{2}) λ_{1} + \frac{1}{2} \sqrt{(1 − λ_{2}^{2})^{2} λ_{1}^{2} + 4λ_{2}^{2}} ≤ 1 − \frac{Ω(1)}{n} ,

where the last estimate holds asymptotically almost surely. It follows from a standard argument that for every f : C_{2} ≀C_{n} → H,

\frac{1}{|C_{2} ≀C_{n}|^{2}} ∑_{x,y∈C_{2}≀C_{n}}∥f (x) − f (y)∥^{2} ≤ \frac{2}{1 − λ} · \frac{1}{|E(Z)|} ∑_{xy∈E(Z)} ∥f (x) − f (y)∥^{2}.

Hence, if f satisfies ρ(x, y) ≤ ∥f (x) − f (y)∥ ≤ Dρ(x, y) for every x, y ∈ C_{2} ≀C_{n}, then also

\frac{1}{|C_{2} ≀C_{n}|^{2}} ∑_{x,y∈C_{2}≀C_{n}}ρ(x, y)^{2} \frac{nD^{2}}{|E(Z)|} ∑_{xy∈E(H)}ρ(x, y)^{2} ≤ nD^{2}.

Now observe that two randomly chosen points of the lamplighter group differ in their first coordinate in a set of size Ω(n) with probability bounded away from 0. Therefore a positive proportion of the terms in the left-hand side above are at least Ω(n^{2}), since if two states x and y of the lamplighter group differ so much, the lamplighter must change Ω(n) lamps to pass between them, irrespective of the choice of generators in the “movement group” C_{n}. It follows that D \sqrt{n}, as required.

It seems natural that the lower bound of Ω( \sqrt{n}) obtained above is tight, but we have not investigated this.

In spite of the possibility of a purely spectral argument as in Proposition 3.4, we hope that a consideration of equivariant embeddings and their decompositions into irreducible representations may shed some light on other families of wreath products, or other semidirect products.

Finally, we should note that our construction of Subsection 2.2 clearly rests crucially on special properties of Hilbert space embeddings, and so the following question remains essentially untouched:

Question 3.5. Does the infimal distortion c_{1}(C_{2} ≀C_{n}) of the lamplighter group with the metric ρ into the Banach space L_{1} tend to infinity with n?

References

[1] I. Aharoni, B. Maurey, and B. S. Mityagin. Uniform embeddings of metric spaces and of Banach spaces into Hilbert spaces. Israel J. Math., 52(3):251–265, 1985.

[2] N. Alon, A. Lubotzky, and A. Wigderson. Semi-direct product in groups and zig-zag product in graphs: connections and applications (extended abstract). In 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), pages 630–637. IEEE Computer Soc., Los Alamitos, CA, 2001.

[3] N. Alon and Y. Roichman. Random Cayley graphs and expanders. Random Structures Algorithms, 5(2):271–284, 1994.

[4] S. Arora, J. R. Lee, and A. Naor. Euclidean distortion and the Sparsest Cut. To appear in J. Amer. Math. Soc.

[5] K. Ball. Markov chains, Riesz transforms and Lipschitz maps. Geom. Funct. Anal., 2(2):137–172, 1992.

[6] Y. Benyamini and J. Lindenstrauss. Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2000.

[7] J. Bourgain. The metrical interpretation of superreflexivity in Banach spaces. Israel J. Math., 56(2):222–230, 1986.

[8] J. Cheeger and B. Kleiner. Differentiating maps into L^{1} and the geometry of BV functions. Preprint, 2006.

[9] Y. de Cornulier, R. Tessera, and A. Valette. Isometric group actions on Hilbert spaces: growth of cocycles. To appear in Geom. Funct. Anal.

[10] W. Fulton and J. Harris. Representation theory, volume 129 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1991. A first course, Readings in Mathematics.

[11] S. Khot and A. Naor. Nonembeddability theorems via Fourier analysis. Math. Ann., 334(4):821–852, 2006.

[12] S. Khot and N. K. Vishnoi. Integrality gap for cut problems and embeddability of negative type metrics into l1. In 46th Annual Symposium on Foundations of Computer Science, pages 53–62, New York, 2005. ACM.

[13] J. R. Lee and A. Naor. L_{p} metrics on the Heisenberg group and the Goemans-Linial conjecture. In 47th Annual Symposium on Foundations of Computer Science, pages 99–108, New York, 2006. ACM.

[14] J. R. Lee, A. Naor, and Y. Peres. Trees and Markov convexity. To appear in Geom. Funct. Anal.

[15] R. Lyons, R. Pemantle, and Y. Peres. Random walks on the lamplighter group. Ann. Probab., 24(4):1993–2006, 1996.

[16] J. Matoušek. Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002.

[17] A. Naor, Y. Peres, O. Schramm, and S. Sheffield. Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces. Duke Math. J., 134(1):165–197, 2006.

[18] O. Reingold, S. Vadhan, and A. Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders. Ann. of Math. (2), 155(1):157–187, 2002.