Towards dimension expanders over finite fields

Zeev Dvir, Amir Shpilka

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

In this paper we study the problem of explicitly constructing a dimension expander raised by [3]: Let Fn be the n dimensional linear space over the field F. Find a small (ideally constant) set of linear transformations from Fn to itself {Ai}i∈I such that for every linear subspace V ⊂ Fn of dimension dim(V), < n/2 we have, where α>0 is some constant. In other words, the dimension of the subspace spanned by {Ai(V)}i∈I should be at least (1+α)·dim(V). For fields of characteristic zero Lubotzky and Zelmanov [10] 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. 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/logn). We give a set of O<(logn) matrices with expanding factor of (1+α), for some constant α>0. Our constructions are algebraic in nature and rely on expanding Cayley graphs for the group ℤ=ℤn and small-diameter Cayley graphs for the group SL2(p).

Original languageEnglish (US)
Pages (from-to)305-320
Number of pages16
JournalCombinatorica
Volume31
Issue number3
DOIs
StatePublished - May 1 2011

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Towards dimension expanders over finite fields'. Together they form a unique fingerprint.

  • Cite this