A set 5 in the vector space F_p~n is "good" if it satisfies the following (almost) equivalent conditions: 1. S is an expanding generating set of Abelian group F_p~n. 2. S are the rows of a generating matrix for a linear distance error-correcting code in F_p~n. 3. All (nontrivial) Fourier coefficients of S are bounded by some ε < 1 (i.e. the set S is ε-biased). A good set S must have at least cn vectors (with c > 1). We study conditions under which S is the orbit of only constant number of vectors, under the action of a finite group G on the coordinates. Such succinctly described sets yield very symmetric codes, and "amplifies" small constant-degree Cayley expanders to exponentially larger ones. For the regular action (the coordinates are named by the elements of the group G), we develop representation theoretic conditions on the group G which guarantee the existence (in fact, abundance) of such few expanding orbits. The condition is a (nearly tight) upper bound on the distribution of dimensions of the irreducible representations of G, and is the main technical contribution of this paper. We further show a class of groups for which this condition is implied by the expansion properties of the group G itself! Combining these, we can iterate the amplification process above, and give (near-constant degree) Cayley expanders which are built from Abelian components. For other natural actions, such as of the affine group on a finite field, we give the first explicit construction of such few expanding orbits. In particular, we can completely de-randomize the probabilistic construction of expanding generators in [2].
展开▼
