%% ToC v002/a005.tex \documentclass{toc} \newtheorem{observation}[theorem]{Observation} \newcommand{\obsref}[1]{\hyperref[#1]{Observation~\ref*{#1}}} \newcommand{\ignore}[1]{} \def\eps {\varepsilon} \newcommand {\lfrac}[1] {\lfloor {#1} \rfloor} \newcommand{\wreath}[2] {{#1} \wr {#2}} \newcommand{\cay}{\mbox{C}} \newcommand{\sch}{\mbox{Sch}} \newcommand{\p}{\perp} \newcommand{\prl}{{||}} \DeclareMathOperator* {\Expectation }{ \mathbb{E} } \newcommand{\E} { \Expectation \displaylimits } \newcommand{\onesvec}[1] { \bar{1} } \newcommand{\graph}[1] {\mathcal{#1}} \newcommand{\set}[1] {{#1}} \newcommand{\elm}[1] {{#1}} \newcommand{\com}[1] { {{#1}^{*}} } \def\valpha {\underline{\alpha}} \def\vx {\underline{x}} \def\vg {\underline{g}} \def\vtg {\tilde{\underline{g}}} \def\th{\tilde{h}} \def\tg {\tilde{g}} \def\vy {\underline{y}} \def\subgroup {<} \newcommand {\symm}[2] {\mbox{Sym}({#1},{#2})} \newcommand{\zigzag}{\mathbin{\raisebox{.2ex}{ \hspace{-.4em}$\bigcirc$\hspace{-.75em}{\rm z}\hspace{.15em}}}} \tocdetails{% volume=2, number=5, year=2006, firstpage=91, received={August 4, 2005}, published={April 25, 2006} } \bibliographystyle{tocplain} \runningauthor{E.~Rozenman, A.~Shalev, and A.~Wigderson} \runningtitle{Iterative Construction of Cayley Expander Graphs} \copyrightauthor{Eyal Rozenman and Aner Shalev and Avi Wigderson} \begin{document} \begin{frontmatter}%[classification=text] \title{Iterative Construction of Cayley Expander Graphs} \author[eyal]{ Eyal Rozenman\thanks{The Hebrew university, Jerusalem. E-mail: {\tt eyalroz@cs.huji.ac.il}. Part of this research was performed while visiting the Institute for Advanced Study, Princeton, NJ.}} \author[aner]{ Aner Shalev\thanks{The Hebrew university, Jerusalem. E-mail: {\tt shalev@math.huji.ac.il}. Partially supported by BSF grant 2000-53 and a grant from the Israel Science Foundation.}} \author[avi]{ Avi Wigderson\thanks{Institute for Advanced Study, Princeton. E-mail: {\tt avi@ias.edu}. Partially supported by NSF grant CCR-0324906.}} \begin{abstract} We construct a sequence of groups $G_n$, and explicit sets of generators $Y_n \subset G_n$, such that all generating sets have bounded size, and the associated Cayley graphs are all expanders. The group $G_1$ is the alternating group $A_d$, the set of even permutations on the elements $\{1,2,\ldots,d\}$. The group $G_n$ is the group of all even symmetries of the rooted $d$-regular tree of depth $n$. Our results hold for any large enough $d$. We also describe a finitely generated infinite group $G_\infty$ with generating set $Y_\infty$, given with a mapping $f_n$ from $G_{\infty}$ to $G_n$ for every $n$, which sends $Y_\infty$ to $Y_n$. In particular, under the assumption described above, $G_{\infty}$ has property $(\tau)$ with respect to the family of subgroups $\ker(f_n)$. The proof is elementary, using only simple combinatorics and linear algebra. The recursive structure of the groups $G_n$ (iterated wreath products of the alternating group $A_d$) allows for an inductive proof of expansion, using the group theoretic analogue (of Alon et al., 2001) of the zig-zag graph product (Reingold et al., 2002). The basis of the inductive proof is a recent result by Kassabov (2005) on expanding generating sets for the group $A_d$. Essential use is made of the fact that our groups have the {\em commutator property:} every element is a commutator. We prove that direct products of such groups are expanding even with highly correlated tuples of generators. Equivalently, highly dependent random walks on several copies of these groups converge to stationarity on all of them essentially as quickly as independent random walks. Moreover, our explicit construction of the generating sets $Y_n$ above uses an efficient algorithm for solving certain equations over these groups, which relies on the work of Nikolov (2003) on the commutator width of perfect groups. %\ignore{ %Without using any assumptions on $S_d$ we construct a sequence of %expanding Schreier graphs on the groups $G_n$, which results in a %sequence of expanders where each graph in the sequence is a lift of %the previous graph. \endabstract %} \end{abstract} \tocams{05C25, 37A30} \tocacm{G.2.2, G.3} \tockeywords{Cayley graphs, Expanders, Expander graphs, Wreath products} \tocpdftitle{Iterative construction of Cayley Expander graphs} \tocpdfauthor{Eyal Rozenman and Aner Shalev and Avi Wigderson} \end{frontmatter} %\pagebreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} \label{intro:sec} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Expander graphs} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Expanders are graphs which are sparse but nevertheless highly connected. Expanders graphs have been used to solve many fundamental problems in computer science, in topics including network design (e.g. \cite{Pippenger87,PippengerYa82,AjtaiKoSz83}), complexity theory (\cite{Valiant77,Sipser88,Urquhart87}), derandomization (\cite{NaorNa93,ImpagliazzoNiWi94,ImpagliazzoWi97}), coding theory (\cite{SipserSp96,Spielman96}), and cryptography (\cite{GoldreichImLeVeZu90}). Expander graphs have also found some applications in various areas of pure mathematics, such as topology, measure theory, game theory and group theory (e.g. ~\cite{KaltonRo83,Lubotzky94,Gromov00,LubotzkyPa01}). Standard probabilistic arguments (\cite{Pinsker73}) show that almost every constant-degree ($\geq 3$) graph is an expander. However, most applications demand explicit constructions. Here we take the most stringent definition of explicitness of an infinite family of graphs, requiring that a deterministic polynomial time algorithm can compute the neighbors of any given vertex, from the vertex name and the index of the graph in the family. This challenge of explicit construction led to an exciting and extensive body of research. Most of this work was guided by the algebraic characterization of expanders, developed in \cite{Tanner84,AlonMi85,Alon86}. They showed the intimate relation of (appropriate quantitative versions of) the combinatorial (isoperimetric) notion of expansion above, to the spectral gap in the adjacency matrix (or, almost equivalently, the Laplacian) of the graph. This relationship is tight enough for almost all applications (but there are some exceptions, e.g. see~\cite{WigdersonZu99,CapalboReVaWi02}). Using this connection, an infinite family of regular graphs is defined to be an expander family if for all of them the second largest eigenvalue of the normalized adjacency (i.e. random walk) matrix is bounded above by the same constant that is smaller than $1$. %% It would be convenient to fix this constant, say to 1/10, which allows %% to talk about a fixed graph being expanding. This choice is immaterial %% for an infinite family, as one can get any constant from another by %% taking a fixed power of the graph. This algebraic definition of expanders by eigenvalues naturally led researchers to consider algebraic constructions where this eigenvalue can be estimated. The celebrated sequence of papers \cite{Margulis73, GabberGa81, AlonMi85, AlonGaMi87, JimboMa87, LubotzkyPhSa88, Margulis88,Morgenstern94} provided such highly explicit families of constant-degree expanders. All of these constructions are based on groups, and their analysis often appeals to deep results in mathematics. The algebraic mould was broken recently by \cite{ReingoldVaWi02}, where a simple, combinatorial construction of constant-degree expander graphs was presented. The construction is iterative, generating the next graph in the family from two previous ones via a novel graph product, the {\em zig-zag} product. This product was proved (using simple linear algebra) to simultaneously keep the degree small, and retain expansion. Thus the iteration process need only be provided with an initial, fixed size expander ``seed'' graph, from which all others are generated. The required parameters of the seed graph are easily shown to hold for a random graph (which suffices for explicitness - it is of constant size), but it is also easy to construct one explicitly. Our main result in this paper is a similar iterative construction of expanding {\em Cayley} graphs (which we turn to define next) from one initial ``seed'' Cayley graph. In our case, the seed Cayley graph is based on the group $A_d$, the group of even permutations on the set $\{1,2,\ldots,d\}$. In a recent breakthrough, Kassabov~\cite{Kassabov05} explicitly constructed a bounded-size, expanding generating set for $A_d$, which yields the seed expander Cayley graph we need. Our construction may be seen as another step in exploring this fundamental notion of expansion, and its relations to yet unexplored mathematical structures. It also further explores the power of the zig-zag product in constructing even stronger expanders. It was already shown \cite{CapalboReVaWi02} that it can yield expansion beyond the eigenvalue bound, and is shown here to yield Cayley expanders. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Expanding Cayley graphs} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% For a finite group $H$ and a (symmetric) set of elements $T$ in it, the Cayley graph $C(H;T)$ has the elements of $H$ as vertices, and edges connect a pair of vertices $g,h$ if their ``ratio'' $gh^{-1}$ is in $T$. We remark that while most applications do not require the expanders to be ``Cayley'', the recent paper \cite{Ben-SassonSuVaWi03} seems to essentially require Cayley expanders to achieve nearly linear-sized locally testable codes (LTCs) and probabilistically checkable proof (PCPs). Many of the algebraic expander constructions mentioned above are Cayley graphs. In all of these, the groups in question are linear matrix groups over finite fields, and their expansion follows from celebrated results in mathematics, including Kazhdan's work on Property $T$ \cite{Kazhdan67}, Selberg's 3/16 theorem \cite{Selberg65}, and the resolution of the Ramanujan conjecture of Eichler, Deligne and Igusa (starting in \cite{Eichler54}). It should be noted that for some of the other algebraic constructions elementary proof of expansion exist, using only a discrete Fourier transform \cite{JimboMa87}. For other natural families of groups the question was considered both by mathematicians and computer scientists. For example, for Abelian groups it is easy to see that any set of expanding generators has to be at least logarithmic in the size of the group. Thus they cannot provide expanding Cayley graphs of constant degree (a more general result appears in \cite{Klawe84}). Lubotzky and Weiss generalized this negative result for all solvable groups of bounded derived length \cite{LubotzkyWe93}. Understanding which natural families of groups can be made expanding (with a fixed size generating set) is a basic question, and little progress was made over the foundational results above in the last 15 years. However, in the last year several breakthroughs were made by Kassabov and Nikolov~\cite{Kassabov05,Kassabov_lattices05,NikolovKa05}. These results suggest that all the simple groups may have fixed size expanding generating sets. Of particular interest to our work is the family of symmetric groups (of all permutations). Much work has been devoted to analyzing the expansion of this group under a variety of generating sets in the context of card shuffling (e.g. see \cite{DiaconisSh94,LovaszWi98}). However, in all these papers the generating sets are huge, and did not provide a clue to the status of this problem. In a recent breakthrough, Kassabov~\cite{Kassabov05} showed that the symmetric groups indeed have explicit, fixed-size expanding generators, independent on the group size. %% \ignore{ %% The best upper bound known, which applies to {\em every} %% finite group, is logarithmic in the group size \cite{AlonRo94}. For %% the symmetric group on $d$ letters $S_d$ this bound gives $O(d\log d)$ %% expanding generators. We conjecture that $d^{1/30}$ generators %% suffice, and this conjecture will provide the seed Cayley graph to our %% iterative construction. %% } The possibility that the zig-zag product and iterative construction may be used for Cayley expanders was first revealed in \cite{AlonLuWi01}. They discovered that the well-known {\em semi-direct} product on groups may be viewed (roughly speaking) as a special case of the zig-zag product of graphs. More precisely, the zig-zag product of two Cayley graphs, with certain important restrictions on the structure of their generating sets, is a Cayley graph of the semi-direct product of the associated groups. Thus one can generate larger Cayley expanders of small degree from smaller ones. This observation was used to show that expansion is {\em not} a group property -- in some groups certain constant size sets will expand, while others will not. This Cayley graph version of the zig-zag theorem raises the hope that, given a ``seed'' expander Cayley graph, one can obtain a sequence of expander Cayley graphs via an iterative process using the zig-zag theorem. However, unlike the case of unstructured graphs, the restrictions on generators alluded to above for applying the zig-zag product on Cayley graphs, make iterations a highly nontrivial (and illuminating) task. In \cite{MeshulamWi02} such a construction was given, which falls short of the task at hand on two counts. First, the generating sets (and hence the degrees) of the groups in the family are not of constant size, but rather grow slowly (roughly like $\log^*$ of the group size). Second, these generating sets are shown to exist via a probabilistic argument, hence the resulting family is not explicit. Still, this construction makes no assumptions, as the seed Cayley expander for the iteration is easily seen to exist. In this paper we fix both problems. We give a sequence of groups $G_n$, and explicit generating sets $Y_n$ for each $G_n$, such that the Cayley graphs $C(G_n,Y_n)$ are expanding. Moreover, $Y_n$ as bounded size, independent of $n$. Actually, we will later on see that the generators $Y_n$ are consistent with each other: In the natural projection of $G_{n+1}$ to $G_n$ the set $Y_{n+1}$ projects to the set $Y_n$. The technique developed yields some results which do not require a seed Cayley graph at all. We show how to obtain an explicit sequence of expanding {\em Schreier graphs}. (The novelty is in the explicitness, since by~\cite{Gross77} every regular graph with even degree is a Schreier graph). We then use the Schreier graph sequence to construct a sequence of expanders $\graph{X}_n$ in which each graph $\graph{X}_{n+1}$ is a lift of $\graph{X}_n$, by noticing that in our Schreier graph sequence each graph is actually a lift of its predecessor (lifts are defined in \secref{sec:lift_expanders}). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Our construction}\label{intro:our_construction} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Our groups are completely different from most groups previously used in this area. Indeed, they are very natural combinatorial objects. Let $T(d,n)$ denote the $d$-regular tree of depth $n$. The group of symmetries of this tree allows permuting the children of every internal node arbitrarily. Thus every element of this group may be described by a mapping of the internal nodes to the symmetric group $S_d$, describing how to permute the children of every such node. Group product of two such elements is simply performing the first set of permutations at every node, and then the next set. Our groups $G_n$ are subgroups of all symmetries, allowing only {\em even} permutations at every internal node of $T(d,n)$. This natural restriction avoids a huge Abelian quotient that would have rendered expansion impossible, as the group would not even be generated by a constant number of generators. Our method of proof (sketched below) is elementary, using only linear algebra. All other known proofs use representation theory of the groups involved, and in most cases much deeper results as well. There is a very natural inductive definition of the groups $G_n$. $G_1$ is the alternating group $A_d$ of all even permutations on $d$ elements (and is essentially the ``seed group'' of our construction). $G_{n+1}$ can be obtained from $d$ copies of $G_n$, and one copy of $A_d$ acting on them simply by permuting the copies. Formally, this is called a wreath product, denoted $G_{n+1} = G_n \wr A_d$, and is a special case of a semidirect product, giving equivalently $G_{n+1} = (G_n)^d \rtimes A_d$. Our assumption gives a small expanding set of generators for $A_d$, and by induction we have such a set for $G_n$. How does induction proceed? Naturally, we would like to use the zig-zag theorem for the semi-direct product \cite{AlonLuWi01,ReingoldVaWi02}. The technical requirement alluded to above is simply that we find an expanding generating set for $(G_n)^d$, which need not be small, but must be an orbit under the action of $A_d$, given a (small) expanding generating set $Y_n$ for $G_n$. A natural candidate for such an orbit is all (even) permutations of the {\em balanced $d$-vector}, one which has every one of the elements of $Y_n$ occurring the same number of times (if $|Y_n|$ divides $d$). It is the largest possible orbit, and the projection of a random element of the orbit to any small subset of the coordinates is (almost) a random independent element of $Y_n$ in each coordinate. We now turn to study the second eigenvalue of the Cayley graph of $(G_n)^d$ under these generators. The associated linear operator acts on the space of real functions on $(G_n)^d$. Luckily, this space of functions is simple to describe - it is the $d$-fold tensor product of the same space for $G_n$. What is not so lucky is the dependence between the coordinates of a balanced vector. Indeed, had $G_n$ been Abelian, this orbit would not even be generating (i.e. the graph would not be connected). Here our special group structure is important. A key fact (proved by Nikolov \cite{Nikolov03}) is that every element in $G_n$ is a commutator. Construct a new generating set $\tilde Y_n$ by adding to $Y_n$, for each of its elements, the constituents of its representation as a commutator. We use Nikolov's proof to actually give a polynomial time algorithm for finding this representation. Now take the orbit of all balanced vectors over $\tilde Y_n$ to be the generating set for $(G_n)^d$. How can this revision take care of the dependencies? A simpler setting, to which we reduce our analysis, is the following Cayley graph. The group is simply $(G_n)^2$, namely only two copies of $G_n$. The generators are all pairs $(g,g^{-1})$ for all $g\in \tilde Y_n$. Thus, there is {\em complete} correlation between the two coordinates. The key point is that, using the special structure of $\tilde Y_n$, with positive probability a short word in one of the two components will vanish, while in the second it will give an original generator of $Y_n$, thereby decoupling the dependence of the two components. So, quite surprisingly, this Cayley graph on two copies is expanding despite the complete correlation (it is a nontrivial exercise to even establish connectivity of this graph -- note that it would {\em not} be connected had $G_n$ been Abelian, or if we took instead the pairs $(g,g)$ for any group $G_n$). This construction (which we feel is of independent interest) is quite special and mysterious, and naturally the description above hides many essential details. Still, it is the heart of the matter. For $m \geq n$ there is a natural \ignore{ embedding map $G_n \to G_m$. Given a symmetry of the tree with depth $n$, send it to the symmetry of the depth $m$ tree, which acts on the first $n$ levels. } restriction map $G_m \to G_n$ - given a symmetry of the tree with depth $m$ consider its action on the subtree with depth $n$ with the same root. As we shall see, the generating set $Y_m$ is mapped to $Y_n$ under this restriction. This gives rise to an infinite ``limit group'' $G_{\infty}$ given with a generating set $Y_\infty$ and restriction maps $f_n: G_\infty \to G_n$, where $f_n(Y_\infty)=Y_n$. In particular, under the assumption on $A_d$, the group $G_{\infty}$ has property $(\tau)$ with respect to the family of subgroups $\ker(f_n)$ (Lubotzky's property $(\tau)$, a ``baby'' version of Kazhdan's property (T), is defined in \secref{sec:compatible_generators}). \ignore{ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{On our assumption} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% How realistic is our conjecture that the alternating group\footnote{Everything in this discussion holds equivalently for the symmetric group $S_d$ up to constants.} $A_d$ (with $d$ large enough) has $d^{1/30}$ expanding generators? As mentioned, the best known upper bound is $O(d \log d)$, which is logarithmic in the group size -- a result that holds for {\em every} group. What makes $A_d$ special, and indeed leads people to speculate that it even has a constant number of expanding generators independent of $d$, are the following two results that seem to be in the ``right direction''. The first is a theorem of Dixon \cite{Dixon69}, that with probability $1-o(1)$, two random permutations generate $A_d$. The second is a result of Babai et al. \cite{BabaiHatyeiKaLuSe90} that $A_d$ has seven generators which yield a Cayley graph of logarithmic diameter. Incidentally, both results hold for every non-Abelian finite simple group~\cite{LiebeckSha95}. In another related work, Lubotzky and Pak~\cite{LubotzkyPa01} show that if the automorphism group of the free group $F_k$ on $k$ generators has Kazhdan property $(T)$ then for infinitely many $d$, the group $A_d$ has an expanding generating set of size $O(k^2)$, independent of $d$. } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Organization of this paper} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In \secref{PRELIM} we define expander graphs and Cayley graphs, and present some useful results. In \secref{OVERVIEW_OF_CONST} we define the sequence of groups we use. In \secref{pf_of_main_thm} we describe the expanding generating sets, and prove the main \thmref{MAIN_THM} - that they are indeed expanding - by induction. The proof is based on a main lemma (\thmref{BALANCED_EXPANSION_THM}). The lemma gives an expanding generating set for the group $G^d$ given an expanding generating set for $G$ (under certain conditions on $G$). Finally, in \secref{pf_of_NikThm} we present an algorithmic version of Nikolov's theorem, that every element in our family of groups has a commutator representation that can be found efficiently. We then turn to some corollaries of the main theorem. In \secref{sec:schreier_expanders} we explicitly construct a sequence of expanding Schreier graphs, free from the seed graph on the alternating group. In \secref{sec:consistent_generators} we give generators for a subgroup of the symmetry group of the {\em infinite} rooted $d$-regular tree. These generators, when restricted to the {\em finite} rooted $d$-regular tree with depth $n$, generate an expander Cayley graph on the (alternating) group of symmetries of this finite tree. As a corollary we deduce that this infinite group has Lubotzky's Property ($\tau$) with respect to a natural infinite family of normal subgroups. Then in \secref{sec:lift_expanders} we combine the previous two results to obtain a sequence of expanding graphs each of which is a lift of the previous one. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Preliminaries}\label{PRELIM} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Graphs, eigenvalues and adjacency matrices}\label{sec:graphs} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% All graphs discussed in this paper are undirected, regular graphs. We allow multiple edges and self loops, so graphs are best understood as symmetric nonnegative integer matrices with a fixed row-sum, called the {\em degree}. For a graph $\graph{X}$, we let $V(\graph{X})$ denote its set of vertices and $E(\graph{X})$ its (multiset of) edges. Let $\graph{X}$ be a $k$-regular graph, and $M=M_{\graph{X}}$ its normalized adjacency matrix (divide the adjacency matrix by the degree $k$ to make it stochastic). We denote by $\lambda(\graph{X})$ the second largest (in absolute value) eigenvalue of $M$. The {\em spectral gap} of the graph is $1-\lambda(\graph{X})$. Let $W$ be the vector space of real functions on the set $V(\graph{X})$, with its standard $L_2$ inner product. $M_{\graph{X}}$ defines a linear operator on $W$: For $f \in W$, the value of the function $M_{\graph{X}}(f) \in W$ on a vertex $x$ is the average value of $f$ on all the neighbors of $x$ (counted with multiplicities). %Each function is naturally a vector in $\mathb{R}^{|\graph{X}|}$ %and identify the %characteristic function of a vertex $v_i$ are a basis. Let $W_{\prl}$ be the one-dimensional subspace consisting of the constant functions, and let $W_{\p}$ be the orthogonal complement. Since the constant functions are eigenvectors of $M$ corresponding to the (largest) eigenvalue 1, then \[ \lambda(\graph{X}) = \max_{w \in W_{\p}} {\|Mw\|/\|w\|} \] where $\|w\|$ is the $L_2$ norm of $w$. \begin{definition} An infinite family of graphs $\graph{X}_n$ is called an {\bf expander family} if $\lambda(\graph{X}_n) \leq \mu$ for some $\mu < 1$ independent of $n$. The family is said to be (strongly) {\bf explicitly described}, if there is a polynomial time algorithm which, on input $n$ and the name of a vertex $v$ in $G_n$ (in binary), outputs the neighbors of $v$ in $G_n$. \end{definition} We will use the following two simple results, which describe how taking the tensor power of a graph, and taking the power of a graph, affect the 2nd eigenvalue $\lambda$: \begin{claim}\label{indep_power_claim} Let $\graph{X}=(V,E)$ be a graph, and let $M_{\graph{X}}$ be the normalized adjacency matrix. Let $M_{\graph{Y}} = (M_{\graph{X}})^{\otimes d}$, and define $\graph{Y}$ to be the graph (on the vertex set $V^d$) with normalized adjacency matrix $M_{\graph{Y}}$. Then $\lambda(\graph{Y})=\lambda(\graph{X})$. \end{claim} \begin{observation}\label{power_eig_obs} Let $\graph{X}=(V,E)$ be a graph, $M_{\graph{X}}$ the normalized adjacency matrix and $M_{\graph{Y}} = (M_{\graph{X}})^k$. Let $\graph{Y}$ be the graph (on vertex set $V$) with normalized adjacency matrix $M_{\graph{Y}}$. Then $\lambda(\graph{Y}) = \lambda(\graph{X})^k$. \end{observation} %We omit the easy proof. We will use the following convexity result later: If the spectral gap $(1-\lambda(\graph{Y}))$ of a graph $\graph{Y}$ is not too small, and $\graph{Y}$ is a large subgraph of $\graph{X}$ (on the same vertex set) then the spectral gap of $\graph{X}$ is also not too small. \begin{claim} \label{mixture_claim} Let $\graph{Y}=(V,E_1) \subset \graph{X}=(V,E_2)$ (i.e. $E_1 \subset E_2$) be $s$- and $t$-regular graphs respectively on the same vertex set $V$. Then \[ 1-\lambda(\graph{X}) \geq \frac{s}{t}(1-\lambda(\graph{Y}))\enspace. \] \end{claim} We will later need the following result on vectors \begin{claim}\label{vector_claim} If for some vectors $w_0,w_1,\ldots,w_L$, all with norm $1$, \[ (1/L)\cdot \| \sum_{i=1}^{L} {w_i} \| \leq 1-\eps \] then \[ (1/L) \cdot \sum_{i=1}^{L} \|w_0+w_i\|/2 \leq 1-\eps/4\enspace. \] \end{claim} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Groups and the wreath product}\label{semi-direct} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsubsection{Cayley graphs}\label{cayley_graphs} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let $G$ be a finite group. We will represent groups multiplicatively, and 1 will denote the identity element of the group. Let $Y$ be a multi-subset of $G$. We will always use {\em symmetric} sets $Y$, namely the number of occurrences of $x$ and $x^{-1}$ in $Y$ is the same for every $x\in G$. $|Y|$ will denote the size of the multiset (counting multiplicities). The {\em Cayley graph} $\cay(G,Y)$ has vertex set $G$, and for every vertex $g\in G$ and $x\in Y$ there is an edge $(g,gx)$. The graph $\cay(G,Y)$ is undirected (as $Y$ is symmetric) and is $|Y|$-regular. For $x \in G$ let $P_x$ be the permutation matrix corresponding to $g \to gx$ in $G$. The normalized adjacency matrix of $\cay(G,Y)$ is $\sum_{x \in Y}{P_x}/|Y|$. We will also use the notation $\E_{x \in Y}{[P_x]}$ to denote this average of operators. Let $W=W(G)$ be the vector space of functions $G \to \mathbb{R}$ as in the previous section. We will be interested in the expansion properties of Cayley graphs on the group $G^d$, the Cartesian product of $d$ copies of $G$. Note that $W(G^d)= W^{\otimes d}$. \begin{observation} Let $W_\prl$ be the space of constant functions on the vertices of $G$, and let $W_\p$ be its orthogonal complement. Let $\bar{b} = (b_1,\ldots,b_d)$ be a length-$d$ vector in the alphabet $\{\prl,\p\}$, and let $W_{\bar{b}}$ be the vector space $\otimes_{i=1}^d W_{b_i}$. Consider the space $W^{\otimes d}$, the $d$-th tensor power of $W$. The space $W^{\otimes d}$ inherits an inner product structure from $W$, where the inner product of two pure tensors is the product of the inner products of the components of the tensors. The orthogonal decomposition $W = W_{\prl} + W_{\p}$ induces an orthogonal decomposition % \[W^{\otimes d}=\sum_{\bar{b}\in \{\prl,\p\}^d}{W_{\bar{b}}}\] % to $2^d$ subspaces by the distributive law for tensor products. For any $x \in G^d$ the operator $P_x$ preserves the decomposition. \end{observation} \begin{corollary} For any Cayley graph $C(G^d,\bar{Y})$, the normalized adjacency operator $\E_{x \in \bar{Y}}{[P_x]}$ preserves the given decomposition of $W^{\otimes d}$, so \[ \lambda(G^d,\bar{Y}) = \max_{\bar{b} \neq \prl^d} \max_{w \in W_{\bar{b}}} { \| \E_{x \in \bar{Y}}{[P_x(w)]}\|}/\|w\|\enspace. \] % That is, it suffices to bound $\| \E_{x \in \bar{Y}}{[P_x(w)]}\|$ from above, for vectors $w$ that are purely in one of these $2^d-1$ subspaces. \end{corollary} % The following two observations describe cases where we can ignore part of the coordinates of $x \in G^d$ when trying to estimate $\| \E_{x \in \bar{Y}} [P_x(w)]\| $. \begin{observation}\label{independence_obs} Let $\bar{b}=b_1,\ldots,b_d$ where $b_i = \perp$ for $i \leq r$ and $b_i = \prl$ otherwise. For $w \in W_{\bar{b}} = W_{\perp}^{\otimes r} \otimes W_{\prl}^{\otimes(d-r)}$, the value of $P_x(w)$ does not depend on $x_{r+1},\ldots,x_d$. \end{observation} \begin{proof} $w$ is a real function on $G^d$. The statement that $w \in W_{\bar{b}}$ and $b_i = \prl$ means that $w$ does not depend on the $i$-th coordinate of its input. \end{proof} \begin{observation}\label{norm_independence_obs} Let $\bar{X} \subset G^d$ be a set of group elements whose last $d-r$ coordinates constitute some fixed vector $\bar{x} \in G^{d-r}$. Then for every $w \in W^{\otimes d}$ the value of \[ \| \E_{x \in \bar{X}} [P_x(w)] \| \] does not depend on $\bar{x}$. \end{observation} %\proof %The operator $P_x$ can be written as %\[ %P_{x_1,\ldots,x_r,\bar{1}} \circ P{ % \obsref{power_eig_obs} from \secref{sec:graphs} translates nicely to the Cayley graph world \begin{observation}\label{cayley_power_obs} Let $G$ be a group, $Y \subset G$. Define $Z$ to be the set of all words of length $k$ in $Y$. Then $\lambda(G,Z) = \lambda(G,Y)^k$. \end{observation} We end with an observation which simplifies the proof of explicitness for families of Cayley graphs. \begin{observation} \label{explicit_cayley_obs} A family of Cayley graphs $C(G_n,Y_n)$ is explicit if there are polynomial time algorithms in $\log |G_n|$ for \begin{itemize} \item performing group multiplication in $G_n$, \item computing inverses in $G_n$, and \item computing the set $Y_n$. \end{itemize} \end{observation} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsubsection{Wreath products and the zig-zag product}\label{sec:wreath} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let $A$ and $B$ be finite groups. Assume that $B \subset S_d$, that is, it acts by permutations on the set $[d] = \{1,\ldots,d\}$. Define the {\em wreath product} \footnote{More precisely, this is referred to as the {\em permutational} wreath product in the literature.} $\wreath{A}{B}$ of $A$ and $B$ to be the group whose elements are vectors $(a_1,\ldots,a_d,\sigma)$, where $a_i \in A$ for all $i$, and $\sigma \in B$. The group multiplication rule is \[ (a_1,\ldots,a_d,\sigma) \cdot (\tilde{a}_1,\ldots,\tilde{a}_d,\tau) = (a_{\tau(1)}\tilde{a}_1,\ldots,a_{\tau(d)}\tilde{a}_d , \sigma \tau)\enspace. \] % One can check that this defines a group structure on $\wreath{A}{B}$. The wreath product is a special case of a more general construction - it is the {\em semi-direct product} of $A^d$ and $B$, where $A^d$ is the Cartesian product of $d$ copies of $A$. The groups $A^d,B$ are naturally embedded in $\wreath{A}{B}$, and we will sometimes refer to elements of $A^d$ and $B$ as elements of $\wreath{A}{B}$. Let $\alpha \subset A^d,\beta \subset B$ be sets of generators. Suppose $\alpha$ has a special structure: it is a {\em single $B$-orbit}. This means that for some arbitrary $\bar{a} \in \alpha$, the set $\alpha$ consists of all vectors obtained from $\bar a$ by permuting its coordinates by a permutation in $B$. We now define a set $\gamma$ in $ \wreath{A}{B}$ by $\gamma = \{ x \bar{a} y \mid x,y \in \beta\}$. One can check that $\gamma$ generates $\wreath{A}{B}$. The following theorem from \cite{AlonLuWi01}, following the zig-zag theorem of \cite{ReingoldVaWi02}, shows that if $\alpha,\beta$ are sufficiently good expanding generators then so is $\gamma$. \begin{theorem}\label{zigzag_semidirect_thm}{\em \cite{AlonLuWi01}} If $\alpha$ is a single $B$-orbit then $ \lambda(\wreath{A}{B},\gamma) \leq \lambda(A^d,\alpha) + \lambda(B,\beta) $. \end{theorem} Note that $|\gamma| = |\beta|^2$ depends only on the size of $\beta$, while $\alpha$ could be large (it could be as large as $|B|$). Also, it is easy to compute $\gamma$ given $\alpha$ and $\beta$, as multiplications in $\wreath{A}{B}$ can be computed efficiently. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsubsection{The commutator property}\label{commutator_property:sec} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let $A$ be a group. For $g,h \in A$ define the {\em commutator} $[g,h]$ to be $g h g^{-1} h^{-1}$. $A$ has the {\em commutator property} if for every element $a \in A$ there is a solution in the variables $x,y$ to the equation $a = [x,y]$. (Note that this is a stronger property than just the commutator subgroup $[A, A]$ being equal to $A$.) % Nikolov \cite{Nikolov03} proves \begin{theorem}\label{NIK_THM} {\em \cite{Nikolov03}} Let $A$ be a group, and $B \subset S_d$ a group of permutations. If $A,B$ have the commutator property then so does $\wreath{A}{B}$. \end{theorem} We shall need an algorithmic version of this theorem. For a group $A$, a {\em commutator representation algorithm} gives, for an input $a \in A$, some pair $x,y \in A$ such that $a = [x,y]$. \begin{theorem}\label{ALGO_NIK_THM} Let $A,B$ be as in \thmref{NIK_THM}. Suppose we are given commutator representation algorithms for the groups $A,B$. Then we obtain such an algorithm for $\wreath{A}{B}$. This algorithm calls the algorithm on $B$ one time, and the algorithm on $A$ at most $d$ times, and uses at most $O(d)$ extra multiplication operations on $A,B$. (The description of the algorithm appears in the proof of the theorem.) \end{theorem} % We prove the theorem in \secref{pf_of_NikThm}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Overview of the construction} \label{OVERVIEW_OF_CONST} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In \secref{groups_def} we will define our sequence of groups $G_n$. In \secref{pf_of_main_thm} we will show how to find generating subsets $Y_n \subset G_n$ that give $\lambda(G_n,Y_n) < 1/1000$ with bounded size $|Y_1|^4$. This will be based on the assumption that there exists a small enough subset $Y_1$ of the alternating group $A_d$ such that $\lambda(A_d,Y_1) < 1/1000$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{The family of groups}\label{groups_def} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % $A_d$, the alternating group, is the base group for our inductive %construction. \begin{definition} The groups in our construction are defined by $G_1=A_d$ and, inductively, $G_{n+1}=\wreath{G_n}{A_d}$. \end{definition} Another way to view the group $G_n$ is as a subgroup of the full group of symmetries of the $d$-regular, depth $n$ tree (by $d$-regularity here we mean that each inner vertex has $d$ descendants). Each element in the group of symmetries is uniquely defined by writing a permutation on each internal node of the tree, indicating how the children of this vertex are permuted. In the subgroup $G_n$ all these permutations should be {\em even}. The representation of an element of $G_n$ as a list of even permutations is polynomial in $\log{|G_n|}$. Multiplying two elements and inverting an element can be done in time which is polynomial in the size of this representation The following important corollary of \thmref{ALGO_NIK_THM} shows that for our groups $G_n$ there is an efficient commutator representation algorithm. % \begin{lemma}\label{lemma:Nikolov_for_G_n} If $d \geq 5$ then the groups $G_n$ have the commutator property of \secref{commutator_property:sec}. Moreover, $G_n$ has a commutator representation algorithm that runs in time polynomial in $\log{|G_n|}$. \end{lemma} \begin{proof} $G_1 = A_d$, and by \cite{Ore51} it has the commutator property. By induction, using \thmref{NIK_THM}, every $G_n$ has the commutator property. The existence of an efficient commutator representation algorithm follows from \thmref{ALGO_NIK_THM}. Full details are given in \secref{pf_of_NikThm}. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Main theorem} \label{pf_of_main_thm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem}\label{MAIN_THM} Suppose that for some $d$ there exists a set of generators $Y_1 \subset A_d$ such that $\lambda(A_d,Y_1) < 1/1000$ and $|Y_1| \leq d^{1/28}/10^{40}$. Then there exist sets $Y_n \subset G_n$ such that $\lambda(G_n,Y_n) < 1/1000$ and $|Y_n| \leq d^{1/7}/10^{40}$. Furthermore, $Y_n$ can be computed in time polynomial in $\log{|G_n|}$. \end{theorem} The graphs $C(G_n,Y_n)$ are the required sequence of Cayley graphs. The sets $Y_n$ can be computed efficiently, and we saw in \secref{groups_def} that group operations in $G_n$ can also be computed efficiently, so by \obsref{explicit_cayley_obs} this is an explicit family of Cayley graphs. The assumption of the theorem is true for very large $d$: \begin{theorem}[\cite{Kassabov05}] For every integer $d \geq 0$ there exists a subset $U_d$ of the symmetric group $S_d$ such that $|U_d| \leq 10^{10^7}$ and $\lambda(S_d,U_d) \leq 1/1000$. \end{theorem} \begin{corollary} If $d \geq 10^{10^9}$ Then the conditions of \thmref{MAIN_THM} hold. \end{corollary} \ignore{ Note that to satisfy the assumption of the theorem one only needs to exhibit an expanding generating set for $A_d$ for a {\em fixed}, large enough $d$, which is (theoretically) a problem solvable on a computer. Unfortunately, ``large enough'' here is too large to be feasible - according to the current bounds $d$ has to be larger that $10^{28 \cdot 40}$, since $1 \leq |Y_1| \leq d^{1/28}/10^{40}$. Computations on $A_d$ for such $d$ are far from being doable. We believe that the constants can be improved, but we do not see how to reach feasible values of $d$ even when optimizing the constants. } We will construct the expanding generators $Y_n \subset G_n$ inductively. The basis of the induction is the assumption in the theorem about $G_1 = A_d$. Let $G = G_n$. We are given $Y \subset G$ such that $\lambda(G,Y) < 1/1000$ and $|Y| \leq d^{1/7}/10^{40}$. We want to find a set $Y' \subset \wreath{G}{A_d}$ such that $\lambda(\wreath{G}{A_d},Y') < 1/1000$ and $|Y'| \leq d^{1/7}/10^{40}$. We will use \thmref{zigzag_semidirect_thm}. The theorem requires an expanding generating set for $A_d$ (which we already have), and an expanding generating set $T \subset G^d$ which is a single $A_d$-orbit. Given any element of such $T$, \thmref{zigzag_semidirect_thm} produces (explicitly) an expanding generating set for $\wreath{G}{A_d} = G_{n+1}$. Can we find an expanding, single-orbit, generating set for $G^d$? Here is a simple attempt that fails. Take $T=Y^d$. The set $Y^d$ is expanding, as $\lambda(G^d,Y^d) = \lambda(G,Y)$ by \clmref{indep_power_claim}. Unfortunately, $Y^d$ contains exponentially many $A_d$-orbits. Another natural set to consider in $G^d$ is the set of {\em balanced vectors}: % \begin{definition}\label{def:balanced_vectors} Let $G$ be a group, and $Y \subset G$. For $d > |Y|$, define $Y^{(d)}$ to be the vectors in $Y^d$ in which every $u \in Y$ appears exactly $\lfrac{d/|Y|}$ times, and the rest of the elements are $1 \in G$. We call these vectors {\bf balanced vectors}. Every two elements in the set $Y^{(d)}$ are equal up to a permutation of the coordinates. Since $d>|Y|$ we may assume that the permutation is even. In other words, the set $Y^{(d)}$ is a single $A_d$-orbit. \end{definition} % The set $Y^{(d)}$ looks promising, but is it expanding? Not always. If $G$ is Abelian, $Y^{(d)}$ does not even {\em generate} $G^d$, since every element in ${Y}^{(d)}$ has product of coordinates equal to $1$ ($Y$ is symmetric, and every element of $Y$ appears the same number of times in $Y^{(d)}$). The groups $G_n$ are far from being Abelian. Indeed, every element of $G_n$ has a representation as a commutator. It turns out that this property, along with the existence of a small generating set $Y$ for $G$ (assumed by induction) enables us to find a good generating set for $G^d$. We will enlarge $Y$ somewhat to a set $X \supset Y$, and see that $X^{(d)}$ is expanding for $G^d$. \begin{definition} \label{def:com_y} Let $G$ be a group, and let $Y \subset G$. Suppose every element $y \in Y$ can be written as a commutator in $G$, namely $y=a_y b_y a_y^{-1} b_y^{-1}$ for some $a_y,b_y \in G$. Define \[ \com{Y} = \bigcup_{y \in Y} \{a_y, b_y, a_y^{-1}, b_y^{-1}, a_y^{-1}b_y^{-1}, b_y a_y\} \cup \{1\}\enspace. \] $\com{Y}$ is symmetric, and $|\com{Y}| \leq 7|Y|$. \end{definition} \begin{theorem}\label{BALANCED_EXPANSION_THM} Let $G$ be a group. Suppose that every element of $Y$ is a commutator in $G$. Let $c,k \in \mathbb{N}$ be constants (to be chosen later). Define $c \cdot Y \subset G$ to be the multi-subset where every element of $Y$ appears $c$ times. Define $X = (c \cdot Y) \cup \com{Y}$, and $\lambda = \lambda(G,Y)$. If $d \geq k^2 \cdot |X|^7$ then \[ \lambda(G^d,X^{(d)}) < 0.01+\max{\left\{ (\lambda+7/c) , e^{-k c (1-\lambda) /10^6} \right\} } \] where $X^{(d)}$ is the set of balanced vectors. \end{theorem} The proof is given in \secref{pf_of_balanced_expansion_thm}. To get a feeling for the constants, note that the larger $k$ and $c$ are, the better inequality we get in the theorem. $k$ is large when $X$ is small. $c$ is large when $X$ is much larger that $Y$, so $k$ gets smaller when $c$ gets larger. Nevertheless, it is not difficult to make both of them large enough for our purposes. \thmref{BALANCED_EXPANSION_THM} is the required result for the inductive step - it remains to show that we can choose $c,k$ properly such that $\lambda(G^d,X^{(d)})$ is small enough for \thmref{zigzag_semidirect_thm}. %%\begin{proof}[] We proceed with the inductive step. We are given a set $Y_n \subset G_n$ of size at most $|Y_1|^4$ such that $\lambda(G_n,Y_n) < 1/1000$. Apply \thmref{BALANCED_EXPANSION_THM} (with $c=10^3,k=10^5$). Then the conditions of \thmref{BALANCED_EXPANSION_THM} hold, and we obtain a set $X^{(d)} \subset G^d$ such that $\lambda(G,X^{(d)}) < 1/50$ (just substitute our $k,c$ in the theorem to see this). Apply \thmref{zigzag_semidirect_thm} to obtain a subset $P \subset G_{n+1}$ of size $|Y_1|^2$, and $\lambda(G_{n+1},P) < 1/1000+1/50$. Define $Y_{n+1}$ to be the set of all words of length 2 in $P$. This is a set of size $|Y_1|^4$ and (by \obsref{cayley_power_obs}) $\lambda(G_{n+1},Y_{n+1}) < (1/1000+1/50)^2 < 1/1000$. This completes the inductive step. % %\end{proof} \qed %If $G=G_n$ then every element of $G$ is a commutator by %\thmref{NikThm}. Following the discussion of \secref{} we %defined $Y_n \subset G_n$ such that $|Y_n| = |Y_1|^4$. %\thmref{balanced_expansion_thm} gives us the required tool to %define our generating sets: %The assumption that every element of $Y$ is a commutator in $G$ is %satisfied for $G_n$ by \thmref{NikThm}. %% \begin{claim} %% Define $C=10^4$ and $X = C Y_i \cup \com{Y_i}$ then with the %% assumptions of \thmref{MainThm} %% \[ %% \lambda(G_i^n,X^{(n)}) \leq 1/50 %% \] %% \end{claim} %% \proof The $K$ of theorem \ref{balanced_expansion_thm} will satisfy %% (using $Y_i \leq 10^{-40} n^{1/7}$) %% \[ %% K \geq \sqrt{\frac{n}{|X|^7}} %% \geq \sqrt{\frac{n}{10 C^7 |Y_i|^7} } %% \geq \sqrt{\frac{n}{10 \cdot 10^{28} \cdot 10^{-40} \cdot n}} %% \geq 10^{5} %% \] %% We can now calculate that $\lambda(G_i^n,X^{(n)})<1/50$ by checking %% the two upper bounds in \thmref{balanced_expansion_thm}. The %% first bound is %% \[ %% 10(\lambda+6/C) = 10(10^{-3}+6\cdot 10^{-4}) < 1/50 %% \] %% And the second is %% \[ %% \exp(-\frac{KC(1-\lambda)}{10^5}) %% \leq %% \exp(-\frac{10^{5} \cdot 10^4}{2 \cdot 10^6}) %% \leq 1/50 %% \] %% \endproof %% Apply this theorem to $\cay(G_i^n,X^{(n)})$ and $\cay(A_n,Y_1)$ to obtain a set %% $D \subset G_{i+1}$ such that $\lambda(G_{i+1},D) < 1/50 + 1/1000$. %% Note that $|D| = 2|Y_1|^2$, and set $Y_{i+1} = D^{*2}$. %% So %% \begin{itemize} %% \item $\lambda(G_{i+1},Y_{i+1}) < (1/50+1/1000)^2 < 1/1000$ %% \item $|Y_{i+1}| = |D|^2 = 4|Y_1|^4 \leq n^{1/7}/10^{40}$ %% \end{itemize} %% % %% Which proves \thmref{MainThm}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Proof of \thmref{BALANCED_EXPANSION_THM}} \label{pf_of_balanced_expansion_thm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The theorem appears in \secref{pf_of_main_thm}. Let $G,Y,X,\lambda$ be as defined in \thmref{BALANCED_EXPANSION_THM}. We will use the notation $W=W(G)$ and $W(G^d),W_{\bar{b}}$ defined in \secref{cayley_graphs}. We need to prove that for every $w \in W(G^d)_{\p}$ such that $\|w\|=1$, at least one of the following upper bounds holds: % \begin{eqnarray} & & \| \E_{x \in X^{(d)}}{[P_x (w)]} \| \label{main_eq1} \leq 0.01 + \lambda+\frac{7}{c}\enspace,\; \text{or} %\\ %& & %\mbox{or} \\ & & \| \E_{x \in X^{(d)}}{[P_x (w)]} \| \label{main_eq2} \leq 0.01 + e^{-kc (1-\lambda) /10^6}\enspace. \end{eqnarray} We saw in \secref{cayley_graphs} that it is enough to prove this for $w \in W_{\bar{b}}$ when $\bar{b} \neq \{\prl\}^d$. Since $X^{(d)}$ is invariant under permutation of the coordinates it is enough to prove the inequality for every $w \in W_{\p}^{\otimes r} \otimes W_{\prl}^{\otimes (d-r)}$ where $1 \leq r \leq d$ (this is $W_{\bar{b}}$ for $b_i = \p$ for $1 \leq i \leq r$ and $b_i = \prl$ for $r < i \leq d$). We split the proof to small and large $r$ cases. For small $r$ we will prove inequality~(\ref{main_eq1}), and for large $r$ we will prove inequality~(\ref{main_eq2}). {\bf Small $r$ case}: When $r \leq 0.1 \sqrt{d/|X|}$, the first $r$ coordinates of a random element in $X^{(d)}$ are very closely a random element in $X^r$. By \obsref{independence_obs} $P_x(w)$ only depends on the first $r$ coordinates of $x$, so it is enough to bound $\| \E_{x \in X^r}{[P_x (w)]}\|$ for $w \in W_{\p}^{\otimes r}$. By \clmref{indep_power_claim} $\| \E_{x \in X^r}{[P_x (w)]} \| \leq \lambda(G,X)^r$. The worst case is when $r=1$. As $Y \subset X$ we can use \clmref{mixture_claim} to give an upper bound to $\lambda(G,X)$, and we obtain inequality~(\ref{main_eq1}). This part is relatively easy, and we will not give a more detailed proof. Notice however that the argument for small $r$ works for {\em any} group $G$, not only for our special sequence of groups, and from the generating set $X$ we only used the $Y$ part - not the $\com{Y}$ part. {\bf Large $r$ case}: When $r$ is large the result is no longer true for any group (for any Abelian group there exists an $f \in W^{\otimes d}$ such that $P_y(f) = f$ for all $y \in Y^{(d)}$). We will need the $\com{Y}$ part of the generating set $X$ (recall that it is only defined when every element of $G$ is a commutator). We will start with the analysis of a different graph - the Cayley graph $C(G \times G,\{(y, y^{-1}) | y \in \com{Y}\})$. We give a lower bound of $(1-\lambda(G,Y))/21|\com{Y}|^2$ on the spectral gap of this graph in \secref{gg_expansion}. Afterward, in \secref{reduction_to_GG}, we will give an upper bound on $\| \E_{x \in X^{(d)}}{[P_x(w)]}\|$ using the spectral gap of this graph on $G \times G$. This part is again true for every group $G$, not only our groups. Notice that the spectral gap bound we get in the $G \times G$ case is rather weak - much smaller than the spectral gap of the original graph $C(G,Y)$. When $r$ is large enough we are able to apply the $G \times G$ result many times in parallel, amplifying the weaker upper bound in $G \times G$. We will obtain the upper bound~(\ref{main_eq2}). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Expansion of $G \times G$ with correlated generators} \label{gg_expansion} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{definition} Let $G$ be a group, and let $Y \subset G$ be a subset of $G$. Define \[ \widetilde{Y} = \{(y,y^{-1})\mid y \in Y\}\enspace. \] \end{definition} \begin{theorem} \label{gg_thm} Suppose $\lambda(G,Y) < 1-\eps$ for some $\eps$, and that every element of $Y$ is a commutator in $G$. Then \[ \lambda(G \times G,\widetilde{\com{Y}}) \leq 1-\frac{\eps}{21 |\com{Y}|^2} \enspace. \] \end{theorem} We find \thmref{gg_thm} quite surprising. In the set $\widetilde{Y}$ there is {\em complete correlation} between the two coordinates, and it would seem that this correlation would prevent the graph from being an expander. For example, if $G$ is Abelian and $Y$ generates $G$ then $\widetilde{Y}$ does not even generate $G \times G$, but only the subgroup $\{(g,g^{-1}) \mid g \in G\}$. Also, for any group $G$ the set $\{(y,y) \mid y \in Y\}$ only generates the subgroup $\{(g, g)\mid g \in G\}$. In both cases the correlation in the generating set prevents the graph from being an expander. We manage to decouple this correlation in the case of the special generating set $\com{Y}$, whose existence relies on the commutator property of $G$. The key observation is that we can represent the element $(y,1)$ for any $y \in Y$ as a word of length $3$ in $\widetilde{\com{Y}}$. We prove this in the following observation. \begin{observation}\label{decoupling_obs} Let $Z$ be the set of words of length $3$ in the set $\widetilde{\com{Y}}$. Then \[ C(G \times G, \{(Y,1) \cup (1,Y)\}) \subset C(G \times G,Z)\enspace. \] \end{observation} \begin{proof} Recall that for every $y \in Y$ the set $\com{Y}$ contains the elements $a_y,b_y, a_y^{-1}b_y^{-1}$ where $y = a_y b_y a_y^{-1} b_y^{-1}$. Observe that \[ (a_y,a_y^{-1}) \cdot (b_y,b_y^{-1}) \cdot ((a_y^{-1} b_y^{-1}),(a_y^{-1} b_y^{-1})^{-1}) = (y,1)\enspace. \] This gives the required representation of $(y,1)$. We can obtain $(1,y)$ similarly. \end{proof} It is easy to see that if $C(G,Y)$ has spectral gap $\eps$ then the graph $C(G \times G,\{ (Y,1) \cup (1,Y)\})$ has spectral gap $\eps/2$. We now have the decoupling we were looking for - the correlated generating set $Z$ contains the uncorrelated one $(Y,1) \cup (1,Y)$. More precisely, apply \clmref{mixture_claim} to observation \ref{decoupling_obs}, and deduce that \begin{observation} $C(G \times G, Z)$ has spectral gap at least $\eps/7|\com{Y}|^2$. \end{observation} % Recall that $Z$ consists of all words of length $3$ in the $\widetilde{\com{Y}}.$ By \obsref{cayley_power_obs}, the spectral gap of $C( G \times G,\widetilde{\com{Y}})$ is at most 3 times smaller than the spectral gap of $C(G \times G,Z)$, and the theorem is proved. \endproof %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Reduction to $G \times G$}\label{reduction_to_GG} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% We bound the average $\| \E_{x \in X^{(d)}}{[P_x (w)]} \|$ from above in terms of $\lambda(G \times G,\widetilde{\com{Y}})$ from \secref{gg_expansion}. For $x \in X^d$ write $x = (x_1,x_2,\bar{x})$ where $x_1,x_2 \in G$ and $\bar{x} \in G^{d-2}$. By the triangle inequality, %% ToC edit: incomplete sentence \begin{claim} \label{pairs_claim} For every $w \in W^{\otimes d}$ \[ \| \E_{x \in X^{(d)}} {[P_x (w)] } \| \leq \E_{x \in X^{(d)}} { \|(P_{x_1,x_2,\bar{x}}+P_{x_2,x_1,\bar{x}})(w)/2\|} \enspace. \] \end{claim} % By \obsref{norm_independence_obs} the value of $\|(P_{x_1,x_2,\bar{x}}+P_{x_2,x_1,\bar{x}})(w)/2\|$ only depends on the first two coordinates of $x$. We therefore group together all the $x$ with equal $x_1,x_2$, replacing $\bar{x}$ by $\onesvec{d-2}$, a $(d-2)$-length vector of $1$'s, and it is enough to bound $ \E_{x \in X^{(d)}}{ \|(P_{x_1,x_2,\onesvec{d-2}}+P_{x_2,x_1,\onesvec{d-2}})(w)/2\|} $. The number of times each pair $x_1,x_2$ appears in the average above is proportional to the number of extensions of $x_1,x_2$ to a vector $(x_1,x_2,\bar{x}) \in X^{(d)}$. As $d$ is much larger than $2$, the number of such extensions is nearly equal for every pair $x_1,x_2$, and we obtain the following: %% ToC edit: ``we get'' --> ``we obtain the following'' \begin{claim}\label{reduction_from_2_coords} If $d \geq 100|X|$ then for every $w \in W^{\otimes d}$ \[ \E_{x \in X^{(d)}} { \|(P_{x_1,x_2,\bar{x}}+P_{x_2,x_1,\bar{x}})(w)/2\|} \leq \E_{y \in X^2} {\|(P_{y_1,y_2,\onesvec{d-2}}+P_{y_2,y_1,\onesvec{d-2}}) (w) / 2\|}+0.01 \|w\|\enspace. \] \end{claim} The $0.01$ above pays for the fact that the number of extensions is only nearly equal. The following lemma bounds the RHS of \clmref{reduction_from_2_coords}. \begin{lemma}\label{reduction_part_lemma} If $\lambda(G,Y) < 1-\eps$ and $r \geq 2$ then for every $w \in W_{\p}^{ \otimes r} \otimes W^{\otimes (d-r)}$ \[ \E_{y \in X^2} {\|(P_{y_1,y_2,\onesvec{d-2}}+P_{y_2,y_1,\onesvec{d-2}}) (w) / 2\|} \leq (1-\frac{c\eps}{2 \cdot 10^4 |X|^3})\|w\| \overset{\text{{\small \em def}}}{=} \Delta \| w \|\enspace. \] %where $y_1,y_2$ are in coordinates $k,k+1$ for some $1 \leq k \leq r-1$. \end{lemma} We prove the lemma in \secref{pf_of_reduction_part_lemma}. Combining \clmref{reduction_from_2_coords} and \lemref{reduction_part_lemma} we obtain \[ \left\| \E_{x\in X^{(d)}} {[P_x (w)] } \right\| \leq (\Delta+0.01) \|w\| \] but $\Delta$ is too close to $1$. The problem originates from \clmref{pairs_claim}, where we partitioned the set $ X^{(d)}$ into pairs based on the value of the first $2$ coordinates. This partition turns out to be too coarse. We will use a finer partition of $X^{(d)}$ by looking at the first $t$ pairs of coordinates, for some properly chosen $t \leq r$. This will amplify the bound to $\Delta^t$. We now define this finer partition precisely. Let $H_t < S_d$ be the subgroup (of size $2^{t}$) generated by the transpositions $(2k-1,2k)$ for $1 \leq k \leq t$, and group together the elements $\{\sigma(x) \mid \sigma \in H_t\}$. When $t=1$ we get the grouping into pairs discussed above. The argument leading to \clmref{reduction_from_2_coords} shows the following: %% ToC edit: authors note new phrasing above. \begin{claim} \label{reduction_to_gg_1_claim} If $2t \leq 0.1\sqrt{d/|X|}$ then for every $w \in W^{\otimes d}$ \[ \left\| \E_{x \in X^{(d)}}{[P_x(w)]}\right\| \leq \E_{y \in X^{2t}} {\left\| \E_{\sigma \in H_t} \left[{ P_{\sigma(y,\onesvec{d-2t})}(w) } \right] \right\|} + 0.01\enspace. \] \end{claim} The case $t=1$ is \clmref{reduction_from_2_coords}. However, the weak upper bound $\Delta$ we had for $t=1$ amplifies to $\Delta^t$. \begin{claim}\label{amplification_claim} Suppose that for every $w \in W_{\p}^{\otimes 2}\otimes W^{\otimes d-2}$ \[ \E_{y \in X^2} \left\| \frac{1}{2} (P_{y_1,y_2,\onesvec{d-2}}+P_{y_2,y_1,\onesvec{d-2}}) (w)\right\| \leq \Delta \|w\|\enspace. \] Then for every $w \in W_{\p}^{\otimes 2t}\otimes W^{\otimes d-2t}$ \[ \E_{y \in X^{2t}} \left\| { \E_{\sigma \in H_t}\left[{P_{\sigma(y,\onesvec{d-2t})}(w)}\right] } \right\| \leq \Delta^t \|w\|\enspace. \] The notation $\onesvec{}$ denotes a vector of length $d-2$ in the first inequality, and a vector of length $d-2t$ in the second one. \end{claim} \proof The proof is by induction on $t$. The case $t=1$ is the assumption of the claim. For general $t$ \begin{align*} \E_{y \in X^{2t}} \left\| { \E_{\sigma \in H_t}\left[ {P_{\sigma(y,\onesvec{d-2t})}(w) } \right] } \right\| &= \E_{\substack{z \in X^2\\ y \in X^{2(t-1)}}} \left\| { \E_{\sigma \in H_{t-1}}{P_{\sigma(1,1,y,\onesvec{d-2t})}} \left[ {P_{z_1,z_2,\onesvec{d-2}}+P_{z_2,z_1,\onesvec{d-2}} (w) } \right] } \right\| \\ & \leq \Delta^{t-1} \E_{z \in X^2} \left\| (P_{z_1,z_2,\onesvec{d-2}}+P_{z_2,z_1,\onesvec{d-2}}) (w) \right\| \leq \Delta^t \|w \|\enspace. \end{align*} Note that in the second line above $\sigma \in H_{t-1}$ acts on the vector $y$ - not on the first $2t-2$ coordinates. The first inequality follows from the induction hypothesis for $H_{t-1}$. The second inequality follows from the induction hypothesis for $H_1$. \endproof We can now complete the proof using $\lambda(G,Y) < 1-\eps$. Pick an integer $t$ satisfying \[ 0.05\sqrt{d/|X|} \leq2t \leq 0.1\sqrt{d/|X|} \leq r\enspace. \] Then by the claims in this section, for $w \in W_{\p}^{\otimes r}\otimes W^{\otimes d-r}$ of norm 1, % \[ \left\| \E_{x \in X^{(d)}} {[P_x (w)] } \right\| \leq 0.01 + \bigl(1-\frac{c\eps}{2 \cdot 10^4 |X|^3}\bigr)^t \leq 0.01 + \exp{\big(\frac{-c t \eps}{2 \cdot 10^4 |X|^3} \big) } \leq 0.01 + \exp{\big( \frac{-k c \eps}{ 10^6 } \big) }\enspace. \] %In the second inequality we used $|\com{Y}| < 10|X|/c$ We plugged in $2t \geq 0.05 \sqrt{d/|X|} \geq 0.05 k |X|^3$. This concludes the proof of \thmref{BALANCED_EXPANSION_THM} for large $r$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsubsection {Proof of \lemref{reduction_part_lemma} } \label{pf_of_reduction_part_lemma} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let $\tau$ be the spectral gap of $C(G \times G,\{(y,y^{-1}) \mid y \in \com{Y}\})$. From \thmref{gg_thm} we have for every $u \in W_{\p} \otimes W$ % \begin{equation}\label{gg_ineq} \left\| \E_{y \in \com{Y}} \left[ {P_{y, y^{-1}} (u) } \right]\right\| \leq (1-\tau)\|u\|\enspace. \end{equation} % In \lemref{reduction_part_lemma} we want to bound \begin{equation}\label{lemma_expression} \E_{y \in X^2} \|(P_{y_1,y_2,\onesvec{d-2}}+P_{y_2,y_1,\onesvec{d-2}}) (w) / 2\| \end{equation} from above, for every $w \in W_{\p}^{\otimes r}\otimes W^{\otimes(d-r)}$. %% ToC edit: authors note new sentence structure above. We will start with the case $d=2$. We will bound (\ref{lemma_expression}) in terms of the LHS of (\ref{gg_ineq}). In order to do that, we will have to deal with the fact that the norm in (\ref{gg_ineq}) appears outside the expectation, while in (\ref{lemma_expression}) it appears inside the expectation (see \clmref{norm_inside_claim}). Also, the average in (\ref{lemma_expression}) is over $y \in X^2$, while in (\ref{gg_ineq}) the average is over $y \in \com{Y}$ (see \clmref{reduction_part_2_claim}). After completing the proof in the case $d=2$, we turn to prove the lemma for general $d$ (\clmref{general_d_claim}). %For $d=2$ there are two obstacles to %overcome. The first is moving from $y,y^{-1}$ to $y_1,y_2 \begin{claim}\label{norm_inside_claim} For every $u \in W_{\p} \otimes W$ \[ \E_{y \in \com{Y}} \left\| \frac{1}{2}(P_{y,1}+P_{1,y}) (u) \right\| \leq (1-\tau/4)\|u\|\enspace. \] \end{claim} \begin{proof} From \clmref{vector_claim} and \eqref{gg_ineq} \[ \E_{y \in \com{Y}} { \left\| \frac{1}{2} (P_{y, y^{-1}}+I) (u)\right\| } \leq (1-\tau/4)\|u\|\enspace. \] Applying the unitary operator $P_{1,y}$ to each element above proves the claim. \end{proof} % % \begin{claim}\label{reduction_part_2_claim} For every $u \in W_{\p} \otimes W$ \[ \E_{y \in X^2} { \left\| \frac{1}{2} (P_{y_1,y_2}+P_{y_2,y_1}) (u)\right\| } \leq (1-\frac{\tau}{8c|X|}) \|u\|\enspace. \] \end{claim} %Consider $\E_{y \in X^2}{ \| \frac{1}{2} (P_{y_1,y_2}+P_{y_2,y_1}) (u)\|}$. \begin{proof} %% ToC edit: added "Proof" here--is this OK? Let $p$ be the probability that for a random $y \in X^2$ we have $y_1 \in \com{Y}$ and $y_2 = 1$. Then $p \geq (1/2c) \cdot 1/|X|$ (as $X = c \cdot Y \cup \com{Y}$ and $\com{Y}$ is larger than $Y$). Using a convexity argument similar to \clmref{mixture_claim} we see that \begin{align*} \E_{y \in X^2} { \left\| \frac{1}{2} (P_{y_1,y_2}+P_{y_2,y_1}) (u)\right\| } &\leq p \cdot \E_{y \in \com{Y}} \left\| \frac{1}{2} (P_{y,1}+P_{1,y}) (u) \right\| + (1-p) \cdot \|u\| \\ %% ToC edit: AUTHORS CHECK PREVIOUS LINE--norm marker added. &\leq p \cdot (1-\tau/4)\|u\| + (1-p) \|u\| \leq (1 - p \tau)\|u\| \leq (1 - \frac{\tau}{8c|X|})\|u\| \end{align*} which proves \clmref{reduction_part_2_claim}. \end{proof} We have shown that for every $u \in W_{\p} \otimes W$ $$ \E_{y \in X^2}{ \left\| \frac{1}{2} (P_{y_1,y_2}+P_{y_2,y_1}) (u)\right\|} \leq \bigl(1-\frac{\tau}{8c|X|}\bigr)\|u\| \leq \bigl(1-\frac{\eps}{21 \cdot 8 |\com{Y}|^2 \cdot |X|}\bigr)\|u\| \leq \bigl(1-\frac{c\eps}{2 \cdot 10^4 |X|^3}\bigr)\|u\|\enspace. $$ The last step follows from $|\com{Y}| \leq 10|X|/c$ (which is true since $X = c Y \cup \com{Y}$ and $|\com{Y}| \leq 10 |Y|$). We have almost completed proving the lemma. We have the right upper bound, but for $u \in W^{\otimes 2}$ instead of in $W^{\otimes d}$. \begin{claim} \label{general_d_claim} If there exists $\lambda > 0$ such that for every $u \in W_{\p}^{\otimes 2}$ \[ \E_{y \in X^2} \left\|[\frac{1}{2}(P_{y_1,y_2} +P_{y_2,y_1})(u)]\right\| \leq \lambda \|u\| \] then for every $w \in W_{\p}^{\otimes 2} \otimes W^{\otimes (d-2)}$ \[ \E_{y \in X^2} \left\|[\frac{1}{2}(P_{y_1,y_2,\onesvec{d-2}} +P_{y_2,y_1,\onesvec{d-2}})(w)]\right\| \leq \lambda \|w\|\enspace. \] \end{claim} \begin{proof} Write $w \in W_{\p}^{\otimes r} \otimes W^{\otimes (d-r)}$ as $w=\sum{u_i \otimes v_i}$ where $u_i \in W_{\p}^{ \otimes 2}$ and $v_i \in W^{\otimes(d-2)}$, such that the $v_i$ are orthogonal and $\|v_i\|=1$. We have \[ \E_y \left\|[\frac{1}{2}(P_{y_1,y_2,\onesvec{d-2}} +P_{y_2,y_1,\onesvec{d-2}})(w)]\right\|^2 = \E_y \sum_i \left\|[\frac{1}{2}(P_{y_1,y_2} +P_{y_2,y_1})(u_i)]\right\|^2 \leq \lambda^2 \|w\|^2 \] and the result follows since $\E(X)^2 \leq \E(X^2)$ for any random variable $X$. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Proof of \thmref{ALGO_NIK_THM}}\label{pf_of_NikThm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The theorem appears in \secref{commutator_property:sec}. \begin{remark} This section contains equations in groups. Constants in the equations will be written in Greek letters. Variables will be written in small Latin letters. Vectors of length $d$ are underlined. \end{remark} Let $C = A \wr B$, where $A$ is any group and $B \subset S_d$. Given an element $\gamma \in C$ we look for a ``commutator representation algorithm'' that solves the equation $\gamma = [c_1,c_2] := c_1 c_2 {c_1}^{-1}{c_2}^{-1}$. By assumption we have such an algorithm for $A$ and $B$. The proof below extends Nikolov's proof in~\cite{Nikolov03}. Any element $\gamma \in \wreath{A}{B}$ has a unique representation $c = \beta \cdot \valpha$ with $\beta \in B$, $\valpha \in A^d$, so it is enough to solve, for every pair $(\beta \in B,\valpha \in A^d)$, the equation $\beta \valpha = [b_1 \vx,b_2 \vy]$. %in the four variables $b_1,b_2 \in B$, $\vx,\vy \in A^d$. Now \[ [b_1 \vx,b_2 \vy] = [b_1,b_2] \cdot \vx^{b_2 b_1^{-1} b_2^{-1}} \vy^{b_1^{-1} b_2^{-1}} \vx^{-b_1^{-1} b_2^{-1}} \vy^{-b_2^{-1}} \] where $\vx^b = b^{-1} \vx b$. In our case $\vx^b$ is simply a permutation of the coordinates of $\vx$ by $b \in B \subset S_d$. We obtain a pair of equations: \begin{align*} \beta &= [b_1,b_2],\;\text{and} \\ \valpha &= \vx^{b_2 b_1^{-1} b_2^{-1}} \vy^{b_1^{-1} b_2^{-1}} \vx^{-b_1^{-1} b_2^{-1}} \vy^{-b_2^{-1}}\enspace. \end{align*} By assumption there is an algorithm that solves $\beta=[b_1,b_2]$. %in the variables $b_1,b_2$. Fix some solution $b_1=\beta_1,b_2=\beta_2$. It remains to solve \[ \valpha = \vx^{\beta_2 \beta_1^{-1} \beta_2^{-1}} \vy^{\beta_1^{-1} \beta_2^{-1}} \vx^{-\beta_1^{-1} \beta_2^{-1}} \vy^{-\beta_2^{-1}}\enspace. \] %where $\vx,\vy \in A^d$ are variables and $\valpha \in A^d$ , %$b_1,b_2$ are fixed coefficients. Since $\vx^\beta$ is a permutation (depending on $\beta$) of the coordinates of $\vx$, the following lemma solves a more general system of equations. % \begin{lemma} For any four permutations $\sigma_1,\sigma_2,\sigma_3,\sigma_4 \in S_d$ and for any $\valpha = \alpha_1,\ldots,\alpha_d \in A^d$, the following system of $d$ equations, one for each $1 \leq i \leq d$: \[ \alpha_i = x_{\sigma_1(i)} y_{\sigma_2(i)} x_{\sigma_3(i)}^{-1} y_{\sigma_4(i)}^{-1} \] %in the $2d$ variables $x_i,y_i$. has a solution algorithm that calls the commutator representation algorithm on $A$ at most $d$ times, and does at most $O(d)$ operations in the group $A$. \end{lemma} The rest of this section is devoted to the proof of this lemma. %We have a set of $d$ equations in the $2d$ variables $x_1,\ldots,x_d$ and %$y_1,\ldots,y_d \in A$ with constants $\alpha_1,\ldots,\alpha_d$. \begin{definition} We shall refer to the $\alpha_i$ as {\bf constants} and to the $x_i,y_i,x_i^{-1},y_i^{-1}$ as {\bf literals}. \end{definition} There are $d$ constants and $4d$ literals in our system. An important fact is that each literal appears {\em exactly once} in the system. Let us solve first in the case that all four $\sigma_i$ are the identity permutation. The system in this case is: \begin{eqnarray*} & & \alpha_1 = [x_1,y_1] \\ & & \alpha_2 = [x_2,y_2] \\ & & \cdots \\ & & \alpha_d = [x_d,y_d] \end{eqnarray*} In this case the equations are independent (no variable appears in more than one equation). Each equation asks for a commutator representation for $\alpha_i \in A$. We solve the system of equations by calling the commutator representation algorithm for $A$ for each equation separately. The solution for general $\sigma_i$ is by reduction to a system similar to the one we obtained for the $\sigma_i=1$ case. As long as there are variables that appear in more than one equation, we will remove equations by ``Gaussian elimination,'' until we obtain a system of independent equations. We will then translate each equation to a commutator representation equation like the ones above. As mentioned, each literal appears exactly once in the system. If $x_i,x_i^{-1}$ do not both appear in the same equation, then we can eliminate $x_i,x_i^{-1}$ from the system by substitution (paying $O(1)$ multiplications in $A$). This reduces the number of equations in the system by $1$. Repeat the substitution operation until it is no longer possible. Notice that the property that each literal appears exactly once is preserved along the way. \begin{claim} The substitution process ends with $L \leq d$ equations \[ \delta_l = W_l \quad \forall l \in \{1,\ldots,L\} \] where $W_l$ is some word in literals and constants. The equations are now independent - every literal appears in the same equation as its inverse, or they both do not appear in the system. \qed \end{claim} We will now reduce this system to $L$ commutator representation problems in the group $A$. The following lemma finds a ``hidden commutator'' in each of the words $W_l$: \begin{lemma} \cite{Nikolov03} In every $W_l$ there exist $g,h \in \{1,2,\ldots,d\}$ depending on $l$, such that \[ W_l = Z_1 x_g Z_2 y_h Z_3 x_g^{-1} Z_4 y_h^{-1} Z_5 \] where the $Z_i$ are words in literals and constants from the word $W_l$ (they do not contain $x_g^{\pm 1},x_h^{\pm 1}$ since each literal appears at most once in the system of equations). \end{lemma} The proof is in \cite{Nikolov03}. Given that such a hidden commutator exists, it is easy to find one in time polynomial in $d$ by looking at all the literals appearing in $W_l$ (there are at most $2d$ of those). Substitute every variable appearing in the $Z_i$ by $1$. This does not affect any other equation - the equations are independent at this point. We obtain a new equation \[ \delta_l = \zeta_1 x_g \zeta_2 y_h \zeta_3 x_g^{-1} \zeta_4 y_h^{-1} \zeta_5\enspace. \] This is now an equation in two variables $x_g,x_h$ - all the other words are constants. This is almost a ``commutator representation'' equation. Indeed, if the five $\zeta_i$ are all equal $1$, we obtain the equation \[ \delta_l = [x_g,y_h] \] which is solved by calling the commutator algorithm on $A$. For general $\zeta_i$ we transform the ``hidden'' commutator to a ``real'' commutator by changing variables. Define $\tilde{x}_g = \zeta_3 x_g \zeta_4$ and $\zeta_h = y_h \zeta_2^{-1}\zeta_3^{-1}$. Observe that \[ \delta_l = \zeta_1 \zeta_4 [\tilde{x}_g, \tilde{y}_h] \zeta_3 \zeta_2 \zeta_5\enspace. \] Rewrite this equation as \[ (\zeta_1 \zeta_4)^{-1} \delta_l (\zeta_3 \zeta_2 \zeta_5)^{-1} = [\tilde{x}_g, \tilde{y}_h]\enspace. \] The LHS is some constant element in $A$, and the equation requests a representation of this element as a commutator. We can find a solution by calling the commutator representation algorithm on $A$. The solution is in the variables $\tilde{x}_g, \tilde{y}_h$, but this is easily translated to a solution in our original variables $x_g,y_h$. How many operations did we use? We called the commutator representation algorithm in $A$ at most $d$ times (one call for each final equation $v_l=W_l$). We called the commutator representation algorithm on $B$ one time. We used $O(1)$ multiplications in $B$, and $O(d)$ multiplications in $A$ (there were $O(1)$ per either removing an equation or solving a final equation). We can now deduce \lemref{lemma:Nikolov_for_G_n}. Define $m(n)$ to be the cost (in bit operations) of multiplication in $G_n$, and define $c(n)$ to be the cost of computing the commutator representation of an element in $G_n$. As $m(n+1) < (d+1)m(n)$ and $m(1)=O(d^2)$ we deduce that $m(n)<(d+1)^{n+2} \cdot O(1)$. From the discussion above we see that $c(n+1) < (d+1)c(n) + m(n) \cdot O(d) < (d+1)c(n) + d^{n+3}\cdot O(1)$. This implies that $c(n) < d^{4n} \cdot O(1)$ for large enough $d$. Finally, as $\log{|G_n}| > d^n$, \lemref{lemma:Nikolov_for_G_n} follows. \endproof %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Expanding Schreier graphs} \label{sec:schreier_expanders} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% For a finite group $H$, a subgroup $H' < H$, and a (symmetric) set of elements $U$ in it, the {\em Schreier graph} $\sch(H,H',U)$ has vertex set $H/H'$ , and edges $(g H', ug H')$ for every $u \in U$, resulting in a $|U|$-regular graph. If $H' = \{1\}$ then $\sch(H,\{1\},U)$ is simply the Cayley graph $\cay(H,U)$. In this section we prove an analogue of \thmref{MAIN_THM} for Schreier graphs. In \thmref{MAIN_THM} we constructed a sequence of expanding Cayley graphs assuming the existence of a good ``seed'' Cayley graph. Here we do the same for Schreier graphs. The difference here is that the ``seed'' Schreier graph is known to exist by elementary arguments, and we do not rely on the strong theorem of~\cite{Kassabov05}. By~\cite{Gross77}, {\em every} $2d$-regular graph is a Schreier graph, so a sequence of expanding Schreier graphs is implicit in any sequence of (even degree regular) expander graphs. However, it is generally hard to compute a Schreier graph representation of a given $d$-regular graph. In this section we explicitly provide the Schreier graph representation of our graphs. There is another way to describe Schreier graphs. Let $H$ be a group acting transitively on a set $\set{E}$. Define a graph $\sch(H,\set{E},U)$ whose vertices are $\set{E}$, and whose edges are $(\elm{e},u \elm{e})$ for all $u \in U$ and $\elm{e} \in \set{E}$. Pick a vertex $\elm{e}_0 \in \set{E}$, and define $H' = \{h \in H \mid h \elm{e}_0 = \elm{e}_0)$, the stabilizer of $\elm{e}_0$. The graph we defined on $\set{E}$ is isomorphic to $\sch(H, H',U)$ by taking $h \elm{e}_0$ to $h H'$. The following definition gives an example of groups acting on sets. This example will be the basis of a construction of expander Schreier graphs. To fix notation, we redefine our basic objects: \begin{definition}\label{def:tree_sym} Let $T_{n,d}$ be the rooted $d$-regular tree with depth $n$, let $\symm{n}{d}$ be its group of symmetries, and let $\set{E}_n$ be the set of leaves of $T_{n,d}$, on which $\symm{n}{d}$ acts naturally. \end{definition} % Expansion of a Cayley graph implies the expansion of all its Schreier graphs: \begin{claim}\label{claim:Cayley_exp_Sch_exp} Let $H$ be a group , let $H' < H$ be a subgroup and let $U \subset G$ be a subset. Then $\lambda(\sch(H,H',U)) \leq \lambda(\cay(H,U))$. \end{claim} \proof Let $v : H/H' \to \mathbb{C}$ be an eigenvector of the Schreier graph. Define $\hat{v} : H \to \mathbb{C}$ by $\hat{v}(h) = v(hH')$. Then $\hat{v}$ is an eigenvector of $\cay(H,U)$ with the same eigenvalue as $v$. % \qed \\ % In \thmref{MAIN_THM} we constructed a sequence of Cayley graphs $\cay(G_n,Y_n)$ where $G_n$ is a subgroup of $\symm{n}{d}$, and showed that it is an expander family under some assumption on the symmetric group $A_d$, which is true for very large $d$. In light of \clmref{claim:Cayley_exp_Sch_exp}, the family $\sch(G_n,\set{E}_n,Y_n)$ is also a sequence of expander graphs, under the same assumption. Below we construct expanding generating sets for $G_n$, which are both simpler than $Y_n$ and do not require any assumptions (and work for much smaller $d$). Reminder: for two groups $G,K$, such that $K