ECCC-Report TR07-122https://eccc.weizmann.ac.il/report/2007/122Comments and Revisions published for TR07-122en-usFri, 07 Dec 2007 11:34:50 +0200
Paper TR07-122
| Towards Dimension Expanders Over Finite Fields |
Zeev Dvir,
Amir Shpilka
https://eccc.weizmann.ac.il/report/2007/122In this paper we study the problem of explicitly constructing a
{\em dimension expander} raised by \cite{BISW}: Let $\mathbb{F}^n$
be the $n$ dimensional linear space over the field $\mathbb{F}$.
Find a small (ideally constant) set of linear transformations from
$\F^n$ to itself $\{A_i\}_{i \in I}$ such that for every linear
subspace $V \subset \F^n$ of dimension $\dim(V) < n/2$ we have
$$\dim\left(\sum_{i \in I} A_i(V) \right) \geq (1+\alpha) \cdot
\dim(V),$$ where $\alpha >0$ is some constant. In other words, the
dimension of the subspace spanned by $\{ A_i(V) \}_{i\in I}$
should be at least $(1+\alpha) \cdot \dim(V)$. For fields of
characteristic zero Lubotzky and Zelmanov \cite{LubotzkyZelmanov}
completely solved the problem by exhibiting a set of matrices, of
size independent of $n$, having the dimension expansion property.
In this paper we consider the finite field version of the problem
and obtain the following results:
1) We give a constant number of matrices that expand the dimension of every
subspace of dimension $d < n/2$ by a factor of $(1 + 1/\log n)$.
2) We give a set of $O(\log n)$ matrices with expanding factor
of $(1+\alpha)$, for some constant $\alpha>0$.
Our constructions are algebraic in nature and rely on expanding
Cayley graphs for the group $\mathbb{Z}/\mathbb{Z}n$ and
small-diameter Cayley graphs for the group $\mathrm{SL}_2(p)$.
Fri, 07 Dec 2007 11:34:50 +0200https://eccc.weizmann.ac.il/report/2007/122