Dimension expanders

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Linear transformations, semilinear transformations (15A04) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25)

Abstract: We show that there exists

and

such that for every field

F

of characteristic zero and for every

, there exists explicitly given linear transformations

T_{1}, ..., T_{k} : F^{n} o F^{n}

satisfying the following: For every subspace

W

of

F^{n}

of dimension less or equal

f r a c n 2

,

d i m (W + s u m l_{i = 1}^{k} T_{i} W) g e (1 + e) d i m W

. This answers a question of Avi Wigderson [W]. The case of fields of positive characteristic (and in particular finite fields) is left open.

Review text

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\).

Recommendations

Cites work

Cited in

(20)

This page was built for publication: Dimension expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2474479)