Lower bounds on maximal determinants via the probabilistic method

The Hadamard maximal determinant problem is to find the maximal determinant D(n) of a square {±1}-matrix of given order n. Hadamard proved the upper bound D(n) ≤ nn/2. This talk is concerned with lower bounds on R(n) := D(n)/nn/2. Define d := n− h, where h is the maximal order of a Hadamard matrix no larger than n. Using the probabilistic method, we can show that R(n) ≥ κd > 0, where κd depends only on d . Previous lower bounds depend on both d and n. Our bounds are improvements for d > 1 and all sufficiently large n. This talk will outline the main results and methods used to obtain them. For technical details, see the preprint at http://arxiv.org/abs/1211.3248. Richard Brent Abstract Introduction – the Hadamard bound and conjecture I D(n) := denote the maximum determinant attainable by an n × n {±1}-matrix. I Hadamard proved the upper bound D(n) ≤ nn/2. I A Hadamard matrix is an n × n ±1 matrix A with det(A) = ±nn/2. I If a Hadamard matrix of order n exists, then n = 1, 2, or a multiple of 4. We’ll ignore the cases n ∈ {1,2}. I The Hadamard conjecture is that Hadamard matrices exist for every positive multiple of 4. I This talk is about lower bounds on D(n). Richard Brent Introduction