Near-Optimal Expanding Generating Sets for Solvable Permutation Groups

Let $G=<S>$ be a solvable permutation group of the symmetric group $S_n$ given as input by the generating set $S$. We give a deterministic polynomial-time algorithm that computes an \emph{expanding generating set} of size $\tilde{O}(n^2)$ for $G$. More precisely, the algorithm computes a subset $T\subset G$ of size $\tilde{O}(n^2)(1\mathrm{/}\lambda {)}^{O(1)}$ such that the undirected Cayley graph $Cay(G,T)$ is a $\lambda$-spectral expander (the $\tilde{O}$ notation suppresses ${\log }^{O(1)}n$ factors). As a byproduct of our proof, we get a new explicit construction of $\epsilon$-bias spaces of size $\tilde{O}(n\text{poly}(\log d))(\frac{1}{\epsilon }{)}^{O(1)}$ for the groups ${\mathbb{Z}}_d^n$. The earlier known size bound was $O((d+n\mathrm{/}{\epsilon }^2){)}^{11\mathrm{/}2}$ given by \cite{AMN98}.