Probabilistic lower bounds on maximal determinants of binary matrices

Let ${mathcal D}(n)$ be the maximal determinant for $n times n$ ${pm 1}$-matrices, and $mathcal R(n) = {mathcal D}(n)/n^{n/2}$ be the ratio of ${mathcal D}(n)$ to the Hadamard upper bound. Using the probabilistic method, we prove new lower bounds on ${mathcal D}(n)$ and $mathcal R(n)$ in terms of $d = n-h$, where $h$ is the order of a Hadamard matrix and $h$ is maximal subject to $h le n$. For example, $mathcal R(n) > (pi e/2)^{-d/2}$ if $1 le d le 3$, and $mathcal R(n) > (pi e/2)^{-d/2}(1 - d^2(pi/(2h))^{1/2})$ if $d > 3$. By a recent result of Livinskyi, $d^2/h^{1/2} to 0$ as $n to infty$, so the second bound is close to $(pi e/2)^{-d/2}$ for large $n$. Previous lower bounds tended to zero as $n to infty$ with $d$ fixed, except in the cases $d in {0,1}$. For $d ge 2$, our bounds are better for all sufficiently large $n$. If the Hadamard conjecture is true, then $d le 3$, so the first bound above shows that $mathcal R(n)$ is bounded below by a positive constant $(pi e/2)^{-3/2} > 0.1133$.