Probabilistic lower bounds on maximal determinants of binary matrices

Publication date 17 November 2017

Abstract: Let

m a t h c a l D (n)

be the maximal determinant for

n i m e s n

p m 1

-matrices, and

m a t h c a l R (n) = m a t h c a l D (n) / n^{n / 2}

be the ratio of

m a t h c a l D (n)

to the Hadamard upper bound. Using the probabilistic method, we prove new lower bounds on

m a t h c a l D (n)

and

m a t h c a l R (n)

in terms of

d = n - h

, where

h

is the order of a Hadamard matrix and

h

is maximal subject to

h l e n

. For example,

m a t h c a l R (n) > (p i e / 2)^{- d / 2}

if

1 l e d l e 3

, and

m a t h c a l R (n) > (p i e / 2)^{- d / 2} (1 - d^{2} (p i / (2 h))^{1 / 2})

if

d > 3

. By a recent result of Livinskyi,

d^{2} / h^{1 / 2} o 0

as

n o i n f t y

, so the second bound is close to

(p i e / 2)^{- d / 2}

for large

n

. Previous lower bounds tended to zero as

n o i n f t y

with

d

fixed, except in the cases

d i n 0, 1

. For

d g e 2

, our bounds are better for all sufficiently large

n

. If the Hadamard conjecture is true, then

d l e 3

, so the first bound above shows that

m a t h c a l R (n)

is bounded below by a positive constant

(p i e / 2)^{- 3 / 2} > 0.1133

.

Recommendations

Cited in

(9)

This page was built for publication: Probabilistic lower bounds on maximal determinants of binary matrices