Probabilistic lower bounds on maximal determinants of binary matrices

Abstract

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$.

17 pages, 2 tables, 24 references. Shorter version of arXiv:1402.6817v4. Typos corrected in v2 and v3, new Lemma 7 in v4, updated references in v5, added Remark 2.8 and a reference in v6, updated references in v7

References in corpus (1)

• Bounds on determinants of perturbed diagonal matrices

Cited by in corpus (1)

• Asymptotic approximation of central binomial coefficients with rigorous error bounds