no. 8 · Wednesday 4 November 2026
Low-rank matrices with three prescribed off-diagonal values over $\mathbb{F}_p$
Abstract
For every prime $p$ and every three-element set $L\subseteq\mathbb{F}_p$, we prove that, for every integer $n\geq1$, there exists a symmetric $n\times n$ matrix over $\mathbb{F}_p$ with zero diagonal, off-diagonal entries in $L$, and rank $O_{p,L}(n^{1/3})$. This answers a question of Bukh. When $0\notin L$, a standard polynomial argument shows that the exponent $1/3$ is optimal. The proof combines an incidence matrix factorization with a projective-plane construction controlling line-intersection numbers modulo $p$. A separate geometric construction in characteristic two yields better explicit constants in certain cases, and also gives integer lifts $L'$ of the prescribed sets $L$ and symmetric $L'$-matrices of rational rank $O_{p,L}(n^{1/3})$. When $0\notin L'$, this improves Bukh's general quadratic lower bound, giving matrices of order $Ω_{p,L}(r^3)$ and rational rank at most $r$.
- comments
- 14 pages. The second author has been added. Theorem 1.1 has been extended to cover all primes
- fields
- Number Theory, Combinatorics