Expanding Generating Sets for Solvable Permutation Groups

Let $G =\langle S\rangle$ be a solvable permutation group given as input by the generating set $S$, that is, $G$ is a solvable subgroup of the symmetric group $S_n$. We give a deterministic polynomial-time algorithm that computes an expanding generating set $T$ of size $\tilde{O}(n^2(1/\lambda)^{c})$ for $G$ such that the undirected Cayley graph ${\rm Cay}_u(G,T)$ is a $\lambda$-spectral expander and the constant $c$ is at most $8$ (the $\tilde{O}$ notation suppresses $\log ^{O(1)}n$ and $\log ^{O(1)}(1/\lambda)$ factors). As a byproduct of our proof, we get a new explicit construction of $\varepsilon$-bias spaces of size $\tilde{O}(n (\log d)^{O(1)}(1/\varepsilon)^{c})$ for the groups $\mathbb{Z}_d^n$ and $c\leq 8$. The earlier known size bound was $O((d + n/\varepsilon^2)^{11/2})$ given by [ Y. Azar, R. Motwani, and J. Naor , Combinatorica, 18 (1998), pp. 151--171]. We also note that for any permutation group $G\le S_n$ given by a generating set, in deterministic polynomial time we can compute an expanding generating set $T$ of size $\left({n}/{\lambda}\right)^{O(1)}$ such that ${\rm Cay}_u(G,T)$ is a $\lambda$-spectral expander where the $O(1)$ notation involves a large constant.