Low-rank matrices with three prescribed off-diagonal values over
In the authors' words
Let be a prime such that is a primitive root modulo . We prove that, for every three-element set and every integer , there exists a symmetric matrix over with zero diagonal, off-diagonal entries in , and rank . This answers a question of Bukh for all such primes and, in particular, settles the case singled out on his problem list. When , a standard polynomial argument shows that the exponent is optimal. The proof combines a geometric construction in characteristic two with an incidence matrix factorization over . The same construction yields integer lifts of the prescribed sets and symmetric -matrices of rational rank . When , this improves Bukh's general quadratic lower bound, giving matrices of order and rational rank at most .
Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 10 pages