Probabilistic lower bounds on maximal determinants of binary matrices

Richard P. Brent, Judy-anne H. Osborn, Warren D. Smith

Published 2015-01-26Version 1

Let $D(n)$ be the maximal determinant for $n \times n$ $\{\pm 1\}$-matrices, and ${\mathcal R}(n) = D(n)/n^{n/2}$ be the ratio of $D(n)$ to the Hadamard upper bound. Using the probabilistic method, we prove new lower bounds on $D(n)$ and ${\mathcal R}(n)$ in terms of the distance $d$ to the nearest (smaller) Hadamard matrix, defined by $d = n-h$, where $h$ is the order of a Hadamard matrix and $h$ is maximal subject to $h \le n$. The lower bounds on ${\mathcal R}(n)$ are \[ {\mathcal R}(n) > \left(\frac{2}{\pi e}\right)^{d/2} \;\text{ if }\; 1 \le d \le 3,\;\text{ and} \] \[{\mathcal R}(n) > \left(\frac{2}{\pi e}\right)^{d/2} \left(1 - d^2\left(\frac{\pi}{2h}\right)^{1/2}\right) \;\text{ if }\; d > 3. \] Since $d^2/h^{1/2} \to 0$ as $n \to \infty$, the latter 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 ${\mathcal R}(n)$ is bounded below by a positive constant $(\pi e/2)^{-3/2} > 0.1133$.