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\ge 1$, 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^{\prime }$ of the prescribed sets $L$ and symmetric $L^{\prime }$-matrices of rational rank $O_{p,L}(n^{1/3})$. When $0\notin L^{\prime }$, this improves Bukh's general quadratic lower bound, giving matrices of order ${\Omega }_{p,L}(r^3)$ and rational rank at most $r$.

arXiv comment14 pages. The second author has been added. Theorem 1.1 has been extended to cover all primes