PreprintCC BY 4.0arXiv
Optimality of finite field dimension expanders
Abstract
We show that random tuples of matrices over a finite field are uniform dimension expanders for every expansion coefficient below the optimal one, using elementary counting arguments. The same holds for the optimal coefficient along a set of dimensions of density 1. By contrast, along Fibonacci dimensions random pairs of matrices fail to be optimal dimension expanders with probability bounded away from zero.
Related
- Quantum expanders and dimension-free commutator bounds
- VC-dimension of distance graphs in finite field geometries
- On the Information Bottleneck for Ergodic Finite-State Markov Chains: Stationary Approximation and Asymptotic Optimality
- Finite-sample nonparametric mean tests: Leave-one-out duality and asymptotic optimality
- Probability-Maximizing Change Detection: Finite-Window Optimality
BibTeX
@misc{jezernik2026optimality,
title = {{Optimality of finite field dimension expanders}},
author = {Urban Jezernik and Markus Reineke},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32394},
eprint = {2610.32394},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32394},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimality of finite field dimension expanders
AU - Urban Jezernik
AU - Markus Reineke
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32394
UR - https://arxiv.org/abs/2610.32394
AB - We show that random tuples of matrices over a finite field are uniform dimension expanders for every expansion coefficient below the optimal one, using elementary counting arguments. The same holds for the optimal coefficient along a set of dimensions of density 1. By contrast, along Fibonacci dimensions random pairs of matrices fail to be optimal dimension expanders with probability bounded away from zero.
ER -