Dimension expanders (Q2474479): Difference between revisions

For any real \(\epsilon > 0\), an \(\epsilon\)-dimension expander is a pair \((V, \, \{T_i\}_{1 \leq i \leq k})\) consisting of a vector space \(V\) of finite dimension \(n\) over some field and a set of \(k\) linear transformations from \(V\) to \(V\) having the property that \[ \dim(W + \sum_{1\leq i\leq k} T_{i}(W)) \geq (1+\epsilon)\dim W \] for every subspace \(W\) of \(V\) with \(\dim W \leq {n \over 2}\). This notion generalizes the special case of an expander graph obtained as a Schreier graph for a finitely-generated permutation group, essentially replacing permutation representations by linear representations. The authors answer a question by \textit{A. Wigderson} [Lecture at IPAM, UCLA, February 2004] concerning \(\epsilon\)-dimension expanders of arbitrarily large dimension by proving that there exist \(k\) and \(\epsilon\) such that for every field \(F\) of characteristic zero and for every \(n\), explicit \(F\)-linear transformations \(T_i \! : F^n \to F^n\) can be found such that \((F^n, \, \{T_i\}_{1 \leq i \leq k})\) is an \(\epsilon\)-dimension expander. Their construction uses unitary group representations that are bounded away from the trivial representation in the sense of the Fell topology on the unitary dual of the group. Over finite fields (and more generally, fields of positive characteristic), the situation is more difficult, and left open, however, the authors report on some progress on this topic by \textit{Z. Dvir} and \textit{A. Shpilka} [Towards dimension expanders over finite fields, Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity (2008)]. They also describe connections between dimension expanders and their own work on algebras with property \(\tau\).