Probabilistic lower bounds on maximal determinants of binary matrices

Abstract

et D(n) be the maximal determinant for n × n {±1}-matrices, and R(n) = D(n)/nn/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 R(n) in terms of d = n − h, where h is the order of a Hadamard matrix and h is maximal subject to h ≤ n. For example, (Formula Presented) By a recent result of Livinskyi, d2/h1/2 → 0 as n → ∞, so the second bound is close to (πe/2)−d/2 for large n. Previous lower bounds tended to zero as n→∞with d fixed, except in the cases d ∈ {0, 1}. For d ≥ 2, our bounds are better for all sufficiently large n. If the Hadamard conjecture is true, then d ≤ 3, so the first bound above shows that R(n) is bounded below by a positive constant (πe/2)−3/2 > 0.1133 Show more