Expanders from symmetric codes

摘要

(MATH) A set S in the vector space FF_pⁿ is "good" if it satisfies the following (almost) equivalent conditions:

• S is an expanding generating set of Abelian group FF_pⁿ.
• S are the rows of a generating matrix for a linear distance error-correcting code in FF_pⁿ.
• 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 [19, 2].For the regular action (the coordinates arenamed 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 derandomize the probabilistic construction of expanding generators in [2].