Expanding generating sets for solvable permutation groups

Let G = S be a solvable permutation group given as input by the generating set S, that is, G is a solvable subgroup of the symmetric group Sn. We give a deterministic polynomial-time algorithm that computes an expanding generating set T of size O(n2(1/λ)c) for G such that the undirected Cayley graph Cayu(G, T) is a λ-spectral expander and the constant c is at most 8 (the O notation suppresses logO(1) n and logO(1)(1/λ) factors). As a byproduct of our proof, we get a new explicit construction of ε-bias spaces of size O(n(log d)O(1)(1/ε)c) for the groups Znd and c ≤ 8. The earlier known size bound was O((d + n/ε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 ≤ Sn given by a generating set, in deterministic polynomial time we can compute an expanding generating set T of size (n/λ)O(1) such that Cayu(G, T) is a λ-spectral expander where the O(1) notation involves a large constant.