Lossless dimension expanders via linearized polynomials and subspace designs (Q2236661)

A collection of \(d\) linear maps \(\Gamma_1,\ldots,\Gamma_d\) on an \(n\)-dimensional vector space \(F^n\) over a (finite) field \(F\), is called an \((\eta,\beta)\)-dimension expander of degree \(d\), if for every subspace \(U\) of dimension at most \(\eta n\), the dimension of \(\sum_{j=1}^d\Gamma_j(U)\) is at least \(\beta\dim(U)\). Though a random collection of \(d=O(1)\) linear maps on a vector space over a finite field offers excellent (lossless) expansion properties \(\beta \approx d\) for \(\eta\ge \Omega(1/d)\), it is not trivial to give explicit constructions even for modest expansion factor \(\beta = 1+\varepsilon\). For large finite fields \(|F|\ge \Omega(n)\), the author's constructions achieve lossless expansion \(\beta\ge (1-\varepsilon)d\) and \(\eta\ge (1-\varepsilon)/d\). Moreover they also obtain degree-proportional expansion for smaller field sizes. As the authors indicate, prior to this work, no explicit constructions of degree-proportional dimension expanders were known.