Given an integer $n$, I want to prove the existence of an $n\times n$ binary matrix (with 0,1 entries), whose determinant is a prime number. What is a lower bound on the largest determinant that I can get?
Here is some useful information I found:
- This OEIS sequence provides an upper bound of the determinant of a binary $n\times n$ matrix. The upper bound is exponential in $n$.
- This OEIS sequence provides the smallest positive integer that is not the determinant of a binary $n\times n$ matrix. This provides a lower bound for non-prime determinants. But, the sequence only lists special cases - not a general lower bound as a function of $n$.
- This paper (in Theorem 6) proves that, for any $d\leq \lfloor \frac{n}{2} \rfloor^2 - 1$, there is a binary matrix with determinant $d$. This is a lower bound on the determinant, but it is very loose (relative to the exponential upper bound). The Bertrand–Chebyshev theorem implies, if I understand correctly, that for any $k$, there is a prime number between $k/2$ and $k$; substituting $k=\lfloor\frac{n}{2} \rfloor^2 - 1$ yields a lower bound of $\approx n^2/4$ (the factor 2 can be substantially improved, e.g. to $1.2$ for any $n\geq 25$; this yields a lower bound of $\approx n^2/2.4$).
Can these results be improved? Is it possible to get a lower bound for the prime determinant of a binary matrix, which is exponential in $n$, or at least polynomial with degree higher than $2$?
