caa a22 4500 445358564 CHVBK 20180317142908.0 cr unu---uuuuu 170323e20110501xx s 000 0 eng 10.1007/s00493-011-2540-8 doi (NATIONALLICENCE)springer-10.1007/s00493-011-2540-8 Towards dimension expanders over finite fields [Elektronische Daten] [Zeev Dvir, Amir Shpilka] In this paper we study the problem of explicitly constructing a dimension expander raised by [3]: 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 $\mathbb{F}^n $ to itself {A i } i∈I such that for every linear subspace V ⊂ $\mathbb{F}^n $ of dimension dim(V)<n/2 we have $\dim \left( {\sum\limits_{i \in I} {A_i (V)} } \right) \geqslant (1 + \alpha ) \cdot \dim (V),$ where α>0 is some constant. In other words, the dimension of the subspace spanned by {A i (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. 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/logn). 2. 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). János Bolyai Mathematical Society and Springer Verlag, 2011 Dvir Zeev Dept. of Mathematics Dept. of Computer Science, Princeton University, Princeton, NJ, USA aut Shpilka Amir Faculty of Computer Science, Technion - Israel Institute of Technology, Haifa, Israel aut Combinatorica Springer-Verlag 31/3(2011-05-01), 305-320 0209-9683 31:3<305 2011 31 493 https://doi.org/10.1007/s00493-011-2540-8 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00493-011-2540-8 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Dvir Zeev Dept. of Mathematics Dept. of Computer Science, Princeton University, Princeton, NJ, USA aut NATIONALLICENCE 700 1- Shpilka Amir Faculty of Computer Science, Technion - Israel Institute of Technology, Haifa, Israel aut NATIONALLICENCE 773 0- Combinatorica Springer-Verlag 31/3(2011-05-01), 305-320 0209-9683 31:3<305 2011 31 493 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer