% rpb249_ejc, paper on lower bound for maxdet function D(n), % from H_minors_v09/10.tex, modified to use EJC style as in ejc-sample.tex % RPB and J-a, 20130414 % \documentclass[12pt]{article} \usepackage{e-jc} \specs{P15}{20(2)}{2013} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{graphicx} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \newcommand{\comment}[1]{} \newcommand{\raisecomma}{\raisebox{2pt}{$,$}} \newcommand{\raisedot}{\raisebox{2pt}{$.$}} \newcommand{\Dbar}{{\mathcal R}} \newcommand{\Tabcompare}{{Table~1}} % Hardcode table number as automatic % numbering does not seem to work \newcommand{\C}{{\mathbb C}} \newcommand{\R}{{\mathbb R}} \newcommand{\N}{{\mathbb N}} \newcommand{\Q}{{\mathbb Q}} \newcommand{\Z}{{\mathbb Z}} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \begin{document} \bibliographystyle{plain} \title{~\\[-40pt] General lower bounds on maximal determinants\\ of binary matrices} \author{Richard P. Brent\\ \small Australian National University\\[-0.8ex] \small Canberra, ACT 0200, Australia\\[-0.8ex] \small\tt maxdet@rpbrent.com\\ \and Judy-anne H. Osborn\\ \small The University of Newcastle\\[-0.8ex] \small Callaghan, NSW 2308, Australia\\[-0.8ex] \small\tt Judy-anne.Osborn@newcastle.edu.au } % It is a cludge to use \date for the dedication, but how else to do it? \date{\small In memory of Warwick Richard de Launey 1958--2010\\[1.4ex] \dateline{Aug 9, 2012}{Apr 14, 2013}{Apr 24, 2013}\\ \small Mathematics Subject Classifications: 05B20, 15A15, 15B34, 62K05} \maketitle \begin{abstract} We prove general lower bounds on the maximal determinant of \hbox{$n \times n$} $\{+1,-1\}$-matrices, both with and without the assumption of the Hadamard conjecture. Our bounds improve on earlier results of de Launey and Levin (2010) and, for certain congruence classes of $n \bmod 4$, the results of Koukouvinos, Mitrouli and Seberry (2000). In an Appendix we give a new proof, using Jacobi's determinant identity, of a result of Sz\"oll\H{o}si (2010) on minors of Hadamard matrices. \bigskip\noindent \textbf{Keywords:} $\{\pm 1\}$-matrices; lower bounds; maximal determinant; D-optimal designs; Hadamard matrices \end{abstract} \section{Introduction} \label{sec:intro} For $n \ge 1$, let $D(n)$ denote the maximum determinant attainable by an $n \times n$ $\{+1,-1\}$-matrix (abbreviated ``$\{\pm1\}$-matrix'' from now on). There are several well-known {upper} bounds on $D(n)$, such as Hadamard's original bound~\cite{Hadamard} $D(n) \le n^{n/2}$, which applies for all positive integers $n$, and bounds due to Ehlich~\cite{Ehlich64a,Ehlich64b}, Barba~\cite{Barba33}, and Wojtas~\cite{Wojtas64}, which are stronger but apply only to certain congruence classes of $n \bmod 4$. In this paper we give new lower bounds on $D(n)$, improving in certain cases on earlier results of Cohn~\cite{Cohn63}, Clements and Lindstr\"om~\cite{CL65}, Koukouvinos, Mitrouli and Seberry~\cite{KMS00}, and de Launey and Levin~\cite{LL}. Since $D(n)$ is a rapidly increasing function of $n$, it is convenient to normalize by the Hadamard bound. Thus, we define $\Dbar(n) := D(n)/n^{n/2}$ and express our bounds in terms of $\Dbar(n)$. Hadamard's inequality becomes $\Dbar(n) \le 1$. We consider square $\{\pm1\}$-matrices. The \emph{order} is the number of rows (or columns) of such a matrix. A $\{\pm1\}$-matrix $H$ with $|\det H| = n^{n/2}$ is called a \emph{Hadamard matrix}. A Hadamard matrix has order $1$, $2$, or a multiple of $4$; the \emph{Hadamard conjecture} is that every positive multiple of~$4$ is the order of a Hadamard matrix. It is known from~\cite{KT} that every positive multiple of $4$ up to and including $664$ is the % added in v3, RPB 20120818 order of a Hadamard matrix. Our technique for obtaining lower bounds on $D(n)$ is to consider a Hada\-mard matrix $H$ of order % say $h$ as close as possible to $n$. If $h > n$ we consider minors of order $n$ in $H$, much as was done by de Launey and Levin~\cite{LL}, although the details differ as we use a theorem of Sz\"oll\H{o}si~\cite{Szollosi10} instead of the probabilistic approach of~\cite{LL}. If $h < n$ we construct a matrix of order $n$ with large determinant having $H$ as a submatrix. By combining both ideas, we improve on the bounds that are attainable using either idea separately. The distance $\delta(n) = |h-n|$ of $n$ from the (closest) order $h$ of a Hadamard matrix can be bounded by the \emph{prime gap} function $\lambda(x)$ which bounds the maximum distance between successive primes $p_i, p_{i+1}$ with $p_i \le x$. Thus, we can use bounds on $\lambda(x)$, such as the theorem of Baker, Harman and Pintz~\cite{BHP}, to obtain unconditional lower bounds on $D(n)$. Unfortunately, the known bounds on $\lambda(x)$ are much weaker than what is conjectured to be true. We give unconditional lower bounds on $D(n)$ and $\Dbar(n)$ in \S\ref{sec:bounds}. Theorem~\ref{thm:unconditional1} implies that $\Dbar(n) \ge n^{-\delta(n)/2}$. In \S\ref{sec:H_bounds} we give stronger lower bounds on the assumption of the Hadamard conjecture. Theorem~\ref{thm:conditional1} improves (for large~$n$) on the bounds of Koukouvinos, Mitrouli and Seberry~\cite{KMS00} in the cases $n \bmod 4 \in \{1,2\}$. Assuming the Hadamard conjecture, the relative gap between the (Hadamard) upper bound and the lower bound is of order at most $n^{1/2}$. More precisely, our Corollary~\ref{cor:improved} gives $\Dbar(n) \ge (3n)^{-1/2}$. This improves on the lower bound of de Launey and Levin~\cite{LL}, who obtained $\Dbar(n) \ge cn^{-3/2}$ for some constant~$c>0$. A comparison of our bounds with earlier results is given in \S\ref{sec:comparison} (see also Remark~\ref{remark:LL} in \S\ref{sec:bounds}). Our lower bound results are weaker than what is conjectured to be true. Numerical evidence for $n \le 120$ supports a conjecture of Rokicki \emph{et al}~\cite{Orrick-prog} that $\Dbar(n) \ge 1/2$. In~\S\ref{sec:H_bounds} we come close to this conjecture (on the assumption of the Hadamard conjecture) for five of the eight congruence classes of $n \bmod 8$. \subsection*{Notation} The positive integers are denoted by $\Z^{+}$, and the reals by $\R$. The notations $f \ll g$ and $g \gg f$ mean the same as $f = O(g)$. For $n\in\Z^{+}$, ${\cal H}_n$ denotes the set of Hadamard matrices of order $n$, and ${\cal H} := \{n\in\Z^{+}\;|\; {\cal H}_n \ne \emptyset\}$. The elements of $\cal H$ in increasing order form the sequence $(n_i)_{i \ge 1}$ of all possible orders of Hadamard matrices ($n_1 = 1$, $n_2 = 2$, $n_3=4$, $n_4 = 8$, $n_5 = 12, \ldots$). The distance of $n$ from a Hadamard order is \begin{equation} \label{def:delta} \delta(n) := \min_{h \in \cal H} |n-h|. \end{equation} \pagebreak[3] The primes are denoted by $(p_i)_{i \ge 1}$ with $p_1 = 2, p_2 = 3$, etc. The \emph{prime gap} function $\lambda:\R \to \Z$ is \[\lambda(x) := \max\;\{p_{i+1}-p_i\;|\; p_i \le x\} \cup \{0\}.\] By analogy, we define the \emph{Hadamard gap} function $\gamma:\R\to\Z$ to be \[\gamma(x) := \max\;\{n_{i+1}-n_i\;|\; n_i \le x\} \cup \{0\}.\] Finally, $\beta_n$ denotes the well-known mapping from $\{\pm1\}$-matrices of order $n > 1$ to $\{0,1\}$-matrices of order $n-1$, such that \[|\det(A)| = 2^{n-1}|\det\beta_n(A)|.\] \section{Unconditional lower bounds on {\it D}({\it n})} % avoid hyperref warning by not using $D(n)$ \label{sec:bounds} The connection between the prime gap function $\lambda$ and the Hadamard gap function $\gamma$ is given by the following lemma. \begin{lemma} \label{lemma:gamma_ineq} For $n \ge 8$, we have $\gamma(n) \le 2\lambda(n/2-1)$. \end{lemma} \begin{proof} If $p$ is an odd prime, then $n = 2(p+1) \in \cal H$. This follows from the second Paley construction~\cite{Paley33} if $p \equiv 1 \pmod 4$, or from the first Paley construction followed by the Sylvester construction if $p \equiv 3 \pmod 4$. Thus, if $p_i$, $p_{i+1}$ are consecutive odd primes, then $n_j = 2(p_i + 1) \in \cal H$, $n_k = 2(p_{i+1} + 1) \in \cal H$, and $k > j$. The result now follows from the definitions of the two gap functions. \end{proof} \begin{remark} {De Launey and Gordon~\cite{LG} have shown that the sequence of Hadamard orders $(n_i)$ is asymptotically denser than the sequence of primes. Even if we consider only the Paley and Sylvester constructions and Kronecker products arising from them~\cite{Agaian}, we can frequently find Hadamard matrices whose orders lie in the interior of the interval $(2(p_i+1),2(p_{i+1}+1))$ defined by a large prime gap. } \end{remark} \begin{corollary} \label{cor:delta_ineq} For $n \ge 8$, we have $\delta(n) \le \lambda(n/2-1)$. \end{corollary} \begin{proof} By the definition of $\delta(n)$ we have $\delta(n) \le \gamma(n)/2$, so the result follows from Lemma~\ref{lemma:gamma_ineq}. \end{proof} Lemma~\ref{lemma:ineq1} gives an inequality that is often useful. \begin{lemma} \label{lemma:ineq1} If $\alpha \in \R$, $n \in \Z$, and $n > |\alpha| > 0$, then \[\frac{(n-\alpha)^{n-\alpha}}{n^n} > \left(\frac{1}{ne}\right)^\alpha\,\raisedot\] \end{lemma} \begin{proof} Taking logarithms, and writing $x = \alpha/n$, the inequality reduces to \[(1-x)\ln(1-x) + x > 0,\] or equivalently (since $0 < |x| < 1$) \[\frac{x^2}{1\cdot 2} + \frac{x^3}{2\cdot 3} + \frac{x^4}{3\cdot 4} + \cdots > 0.\] This is clear if $x>0$, and also if $x < 0$ because then the terms alternate in sign and decrease in magnitude. \end{proof} Recently Sz\"oll\H{o}si~\cite[Proposition 5.5]{Szollosi10} established an elegant correspondence between the minors of order $n$ and of order $h-n$ of a Hadamard matrix of order $h$. His result applies to complex Hadamard matrices, of which $\{\pm1\}$-Hadamard matrices are a special case. More precisely, if $d+n = h$, $0 < d < h$, then for each minor of order $d$ and value $\Delta$ there corresponds a minor of order $n$ and value $\pm h^{h/2 - d}\Delta$. Previously, only a few special cases (for small~$d$ or $n$, see for example~\cite{DP88,KMS01,SXKM03,Sharpe07}) were known. We note that Sz\"oll\H{o}si's crucial Lemma~5.7 follows easily from Jacobi's determinant identity~\cite{BS83,Gantmacher,Jacobi}, although Sz\"oll\H{o}si gives a different proof.\footnote{In the Appendix we give a proof of Sz\"oll\H{o}si's Lemma~5.7 using Jacobi's identity.} \begin{lemma} \label{lemma:minor} Suppose $0 < n < h$ and $h \in \cal H$. Then $D(n) \ge 2^{d-1}h^{h/2 - d}$, where $d = h-n$. \end{lemma} \begin{proof} Let $H \in {\cal H}_h$ be a Hadamard matrix of order~$h$, and let $M$ be any $n\times n$ submatrix of $H$ (so $M$ does not necessarily have contiguous rows or columns in $H$). Let $M'$ be the $d\times d$ submatrix consisting of the intersection of the complementary set of rows and columns of $H$. Some such $M'$ must be nonsingular, else we could prove, using Laplace's expansion of the determinant and induction on $n$, that $\det(H)=0$, contradicting the assumption that $H$ is a Hadamard matrix. Thus, without loss of generality, $\det(M') \ne 0$. Since $M'$ is a $\{\pm1\}$-matrix, we must have $|\det(M')| \ge 2^{d-1}$. By~Sz\"oll\H{o}si's theorem, $|\det(M)| = h^{h/2-d}|\det(M')| \ge 2^{d-1}h^{h/2-d}$. \end{proof} \begin{remark} {We could improve Lemma~\ref{lemma:minor} for large $d$ by using the fact that, from a result of de Launey and Levin~\cite[proof of Prop.~5.1]{LL}, there exists $M'$ with $|\det(M')| \ge (d!)^{1/2}$, which is asymptotically larger than the bound $|\det(M')| \ge 2^{d-1}$ that we used in our proof. However, in our application of the lemma, $h \gg d$, so it is the power of $h$ in the bound that is significant. } \end{remark} \begin{lemma} \label{lemma:major} Suppose $0 < h < n$ and $h \in \cal H$. Then $D(n) \ge 2^{n-h}h^{h/2}$. \end{lemma} \begin{proof} The case $h=1$ is trivial, so suppose that $h > 1$. Let $H \in {\cal H}_h$ be a Hadamard matrix of order~$h$, so $H$ has determinant $\pm h^{h/2}$ and the corresponding $\{0,1\}$-matrix $\beta_h(H)$ has determinant $\pm 2^{1-h}h^{h/2}$. We can construct a $\{0,1\}$-matrix $A$ of order $n-1$ and the same determinant as $\beta_h(H)$ by adding a border of $n-h$ rows and columns (all zero except for the diagonal entries). Now construct a $\{\pm1\}$-matrix $B \in \beta_n^{(-1)}(A)$ by applying the standard mapping from $\{0,1\}$-matrices to $\{\pm1\}$-matrices. We have $|\det(B)| = 2^{n-1}|\det(A)| = 2^{n-h}h^{h/2}$. \end{proof} \begin{lemma} \label{lemma:n_delta_bound} Let $n \in \Z^{+}$ and $\delta = \delta(n)$ be defined by \eqref{def:delta}. Then $n \ge 3\delta$. \end{lemma} \begin{proof} The interval $[2n/3,4n/3)$ contains a unique power of two, say $h$. By the Sylvester construction, $h \in {\cal H}$. However, $|n-h| \le n/3$, so $\delta \le n/3$. \end{proof} \begin{theorem} \label{thm:unconditional1} If $n\in\Z^{+}$ and $\delta = \min_{h\in\cal H}|n-h|$, then \begin{equation} \label{eq:uncondbd} \Dbar(n) \ge \left(\frac{4}{ne}\right)^{\delta/2}. \end{equation} \end{theorem} \begin{proof} By the definition of $\delta$, there exists a Hadamard matrix $H$ of order $h = n \pm \delta$. If $\delta = 0$ the result is trivial, so suppose $\delta \ge 1$. We consider two cases. First suppose that $h = n + \delta$. Applying Lemma~\ref{lemma:minor}, we have \[D(n) \ge 2^{\delta-1}h^{h/2 - \delta} \ge h^{h/2 - \delta}.\] Now, applying Lemma~\ref{lemma:ineq1} with $\alpha = -\delta$ gives \[\Dbar(n) \ge \frac{h^{h/2-\delta}}{n^{n/2}} = \frac{(n+\delta)^{(n+\delta)/2}}{n^{n/2}}(n+\delta)^{-\delta} \ge \left(\frac{ne}{(n+\delta)^2}\right)^{\delta/2}. \] By Lemma~\ref{lemma:n_delta_bound} we have $\delta/n \le 1/3 < (e/2 - 1)$, from which it is easy to verify that $ne/(n+\delta)^2 > 4/(ne)$. The inequality \eqref{eq:uncondbd} follows. Now suppose that $h = n - \delta$. From Lemma~\ref{lemma:major} we have $D(n) \ge 2^\delta h^{h/2}$. Using Lemma~\ref{lemma:ineq1} with $\alpha = \delta$, we have \[\Dbar(n) > 2^{\delta}\left(\frac{1}{ne}\right)^{\delta/2} = \left(\frac{4}{ne}\right)^{\delta/2}.\] Thus, in all cases we have established the desired lower bound on $\Dbar(n)$. \end{proof} \begin{remark} \label{remark:LL} { Consider $n>4$ in the interval $(n_i, n_{i+1})$ between two consecutive Hadamard orders, and write $\Delta := (n_{i+1}-n_i)/2 \ge 2$. De Launey and Levin~\cite[Theorem 3]{LL} % also Proposition 5.1 take $d = n_{i+1}-n \le 2\Delta-1$ and give (in our notation) the bound $\Dbar(n) \ge n^{-d/2}$. In contrast, our bound is $\Dbar(n) \ge n^{-\delta/2}$, where $\delta \le \Delta$. Note that $\max(d)+1 = 2\max(\delta) = 2\Delta$. In the worst case, the bound of de Launey and Levin is $n^{-(2\Delta-1)/2}$, whereas the worst case for our bound is $n^{-\Delta/2}$. Thus, we almost halve the exponent of $n$ in the worst-case bound. The reason for the difference is that de Launey and Levin always take a Hadamard matrix with order $h = n_{i+1} > n$, whereas we take $h = n_i < n$ and use Lemma~\ref{lemma:major} if that gives a sharper bound. } \end{remark} \begin{corollary} \label{cor:uncond} For $n\in\Z$, $n \ge 4$, % Omitted in earlier versions but should exclude $n=3$ \[\Dbar(n) \ge \left(\frac{4}{ne}\right)^{\lambda(n/2)/2},\] where $\lambda(n)$ is the prime gap function defined above. \end{corollary} \begin{proof} For $n \ge 8$ this follows from Theorem~\ref{thm:unconditional1}, using Corollary~\ref{cor:delta_ineq}. It is easy to check that the inequality holds for $4 \le n < 8$ by using the known values of $D(n)$ listed in~\cite{Orrick-www}. % Also OK for $n = 1, 2$, but fails for $n=3$ \end{proof} \begin{remark} \label{remark:Hoheisel} { In the literature there are many inequalities for $\lambda(n)$, see for example Hoheisel~\cite{Hoheisel} or Huxley~\cite{Huxley}. The best result so far seems to be that of Baker, Harman and Pintz~\cite{BHP}, who proved that $\lambda(n) \le n^{21/40}$ for $n \ge n_0$, where $n_0$ is a sufficiently large (effectively computable) constant. Assuming the Riemann hypothesis, Cram\'er~\cite{Cramer} proved that $\lambda(n) = O(n^{1/2}\log n)$. ``Cram\'er's conjecture'' implies that $\lambda(n) = O((\log n)^2)$, and numerical computations~\cite{Nicely-gaps,Shanks64,Silva} provide some evidence for this conjecture. For a discussion of other relevant results on prime gaps, see~\cite[\S1]{LL}. } \end{remark} \pagebreak[3] \begin{corollary} \label{cor:asymptotics} If $n\in N$, then \[0 \le {n\ln n} - 2\ln D(n) = O(n^{21/40}\ln n) \;\text{\rm\ as }\; n \to \infty.\] \end{corollary} \begin{proof} The result follows from Corollary~\ref{cor:uncond} and the theorem of Baker, Harman and Pintz~\cite{BHP}. \end{proof} \section{Conditional lower bounds on {\it D}({\it n})} % avoid hyperref warning by not using $D(n)$ \label{sec:H_bounds} In this section we assume the Hadamard conjecture and give lower bounds on $D(n)$ that are sharper than the unconditional bounds of~\S\ref{sec:bounds}. The idea of the proof of Theorem~\ref{thm:conditional1} is similar to that of Theorem~\ref{thm:unconditional1}~-- we use a Hadamard matrix of slightly smaller or larger order to bound $D(n)$ when $n \not\equiv 0 \pmod 4$. In each case, we choose whichever construction gives the sharper bound. First we make a definition and state two well-known lemmas. \begin{definition} Let $A$ be a $\{\pm1\}$-matrix. The \emph{excess} of $A$ is $\sigma(A) := \sum_{i,j}a_{i,j}$. If $n \in {\cal H}$, then % $w(n) := \max_{H \in {\cal H}_n} w(H)$ and $\sigma(n) := \max_{H \in {\cal H}_n} \sigma(H)$. \end{definition} The following lemma is a corollary of \cite[Theorem~1]{EM}, and gives a small improvement on Best's lower bound~\cite[Theorem~3]{Best} $\sigma(h) \ge 2^{-1/2}h^{3/2}$. \begin{lemma} \label{lemma:sigma_lower} If $4 \le h \in {\cal H}$, then \begin{equation*} %\label{eq:SW1} \sigma(h) \ge (2/\pi)^{1/2}h^{3/2}. \end{equation*} \end{lemma} The following lemma is ``well-known''~-- it follows from~\cite[Theorem~2]{SW} and is also mentioned in later works such as~\cite[pg.~166]{FK}. \begin{lemma} \label{lemma:sigma_upper} If $h \in {\cal H}$, then \begin{equation*} %\label{eq:D_lower} D(h+1) \ge h^{h/2}\left(1 + \frac{\sigma(h)}{h}\right). \end{equation*} \end{lemma} \begin{theorem} \label{thm:conditional1} Assume the Hadamard conjecture. For $n \in \Z^{+}$, we have \begin{equation} \label{eq:three_cases} \Dbar(n) \ge \begin{cases} \left(\frac{2}{\pi e}\right)^{1/2} & \text{\rm if $n \equiv 1 \pmod 4$,}\\ \left(\frac{8}{\pi e^2 n}\right)^{1/2} & \text{\rm if $n \equiv 2 \pmod 4$,}\\ (n+1)^{(n-1)/2}/n^{n/2} \;\,\sim \left(\frac{e}{n}\right)^{1/2} & \text{\rm if $n \equiv 3 \pmod 4$.} \end{cases} \end{equation} \end{theorem} \begin{proof} Since $\Dbar(1) = \Dbar(2) = 1$, the result holds for $n \in \{1,2\}$, so we assume that $n \ge 3$. Suppose that $4 \le h \equiv 0 \pmod 4$. We are assuming the Hadamard conjecture, so $h \in {\cal H}$. Thus, combining the inequalities of Lemma~\ref{lemma:sigma_lower} and Lemma~\ref{lemma:sigma_upper}, we have \begin{equation} \label{eq:Dh1} D(h+1) \ge h^{h/2}(1 + (2h/\pi)^{1/2})\,. \end{equation} Let $A$ be a $\{\pm1\}$-matrix of order $h+1$ with determinant at least the right side of~\eqref{eq:Dh1}. By the argument used in the proof of Lemma~\ref{lemma:major}, we can construct a $\{\pm1\}$-matrix of order $h+2$ with determinant at least $2h^{h/2}(1 + (2h/\pi)^{1/2})$ by adjoining a row and column to $A$. % (it does not matter that $A$ is not a Hadamard matrix). Thus \begin{equation} \label{eq:Dh2} D(h+2) \ge 2h^{h/2}(1 + (2h/\pi)^{1/2})\,. \end{equation} To prove the first inequality in~\eqref{eq:three_cases}, put $h = n-1$ in~\eqref{eq:Dh1} and use Lemma~\ref{lemma:ineq1} with $\alpha = 1$. Thus, for $1 < n \equiv 1 \pmod 4$, \[\Dbar(n) \ge \left(\frac{2}{\pi e}\right)^{1/2}\left( \left(1-\frac{1}{n}\right)^{1/2}\!\! +\, \left(\frac{\pi}{2n}\right)^{1/2}\right) > \left(\frac{2}{\pi e}\right)^{1/2}\!.\] To prove the second inequality in~\eqref{eq:three_cases}, put $h = n-2$ in~\eqref{eq:Dh2} and use Lemma~\ref{lemma:ineq1} with $\alpha = 2$. Thus, for $2 < n \equiv 2 \pmod 4$, \[\Dbar(n) \ge \left(\frac{8}{\pi e^2 n}\right)^{1/2}\left( \left(1 - \frac{2}{n}\right)^{1/2} \!\!+\, \left(\frac{\pi}{2n}\right)^{1/2}\right) > \left(\frac{8}{\pi e^2 n}\right)^{1/2}\!. \] Finally, if $n\equiv 3 \pmod 4$, then a Hadamard matrix of order $n+1$ exists. From Lemma~\ref{lemma:minor} with $h = n+1$ we have $D(n) \ge (n+1)^{(n-1)/2}$. % (This improves on \cite{KMS00,LL}.) \end{proof} \begin{corollary} \label{cor:improved} Assume the Hadamard conjecture. If $n \ge 1$ then \[\Dbar(n) \ge 1/\sqrt{3n}\,.\] \end{corollary} \begin{proof} For $n>2$ this follows from Theorem~\ref{thm:conditional1}, since $\pi e^2 < 24$ (in fact we could replace the constant $3$ in the statement of the Corollary by $\pi e^2/8 \approx 2.9017$). The result is also true if $n \in \{1,2\}$, as then $\Dbar(n) = 1$. \end{proof} \begin{remark} { Inequality~\eqref{eq:Dh1} is within a factor $\sqrt{\pi}$ of Barba's upper bound \hbox{$(2h+1)^{1/2}h^{h/2}$}. } \end{remark} \begin{remark} { If $n \equiv 2 \pmod 8$, we get a lower bound $\Dbar(n) \ge 2/(\pi e)$ by using the Sylvester construction on a matrix of order $n/2 \equiv 1 \pmod 4$. Thus, the remaining cases in which there is a ratio of order $n^{1/2}$ between the upper and lower bounds are $(n \bmod 8) \in \{3,6,7\}$. } \end{remark} \section{Comparison with earlier results} \label{sec:comparison} Since different authors use different notations, it is not always easy to compare their lower bounds. To assist the reader in this, we briefly compare our results with the earlier lower-bound results of Cohn~\cite{Cohn63}, Clements and Lindstr\"om~\cite{CL65}, Koukouvinos, Mitrouli and Seberry~\cite{KMS00}, and de Launey and Levin~\cite{LL}. Cohn~\cite[Theorem 13]{Cohn63} shows that, for any given positive $\varepsilon$ and all sufficiently large $n$, $D(n) \ge n^{(1/2-\varepsilon)n}$. %Taking logarithms, This inequality is equivalent to \[n\ln n - 2\ln D(n) \le 2\varepsilon n\ln n\,.\] Thus, we can express Cohn's result as $\ln D(n) \sim \frac12 n\ln n$, or equivalently \[n\ln n - 2\ln D(n) = o(n\ln n) \;\text{ as }\; n \to \infty\,.\] Clements and Lindstr\"om~\cite[Corollary to Theorem 2]{CL65} improved Cohn's result by showing that the $o(n\ln n)$ term could be replaced by $O(n)$. More precisely, they obtained the bound \[n\ln n - 2\ln D(n) \le n\ln(4/3)\,.\] Our Corollary~\ref{cor:asymptotics} improves (at least asymptotically) on the results of Cohn, Clements and Lindstr\"om by showing that \[n\ln n - 2\ln D(n) = O(n^{21/40}\ln n) \;\text{ as }\; n \to \infty\,.\] The exponent $21/40$ here arises from a bound~\cite{BHP} on prime gaps. Koukouvinos, Mitrouli and Seberry~\cite[Theorem~2]{KMS00} assume that $4t = v+1$ is the order of a Hadamard matrix, and consider orders $v$, $v-1$ and $v-2$ separately. They obtain lower bounds of $(4t)^{2t-1}$, $2(4t)^{2t-2}$, and $4(4t)^{2t-3}$ respectively in these cases. On the assumption that both $4t-4$ and $4t$ are orders of Hadamard matrices, the comparison with our Theorem~\ref{thm:conditional1} is summarized in {\Tabcompare}. The asymptotics all follow from the fact that $\lim_{n\to\infty}(1+c/n)^n = \exp(c)$. For example, the case $n \equiv 1 \bmod 4$ corresponds to taking minors of order $n = v-2 = 4t-3$, and the lower bound of Koukouvinos \emph{et al} is \[4(4t)^{2t-3} = 4(n+3)^{(n-3)/2} \sim 4e^{3/2}n^{(n-3)/2} \;\text{ as }\; n \to \infty\,.\] From {\Tabcompare} we see that the bounds are the same in the case $n \equiv 3 \bmod 4$, but our bounds are sharper (for sufficiently large $n$) in the other two cases. More precisely, our Theorem~\ref{thm:conditional1} gives sharper bounds than Theorem~2 of~\cite{KMS00} if $n \ge 9$ in the case $n \equiv 1 \bmod 4$, and if $n \ge 82$ in the case $n \equiv 2 \bmod 4$. \begin{table}[h] % Table \Tabcompare\ hardcoded \begin{center} % as automatic numbering doesn't work \begin{tabular}{|c|c|c|c|} \hline $n$ & $n \bmod 4$ & Koukouvinos \emph{et al}~\cite{KMS00} & Our Theorem~\ref{thm:conditional1} \\ \hline & & & \\[-8pt] $v-2$ & $1$ & $4(e/n)^{3/2} \approx 17.93/n^{3/2}$ & $(2/(\pi e))^{1/2} \approx 0.4839$ \\ & & & \\[-8pt] $v-1$ & $2$ & $\;\;2e/n \approx 5.437/n$ & $(8/(\pi e^2 n))^{1/2} \approx 0.5871/n^{1/2}$\\ & & & \\[-8pt] $v$ & $3$ & $(e/n)^{1/2} \approx 1.649/n^{1/2}$ & $(e/n)^{1/2} \approx 1.649/n^{1/2}$\\ \hline \end{tabular} \caption{Asymptotics of some lower bounds on $\Dbar(n)$} \end{center} \end{table} We give two examples. First consider $n = 13 \equiv 1 \bmod 4$. Theorem~2 of \cite{KMS00} (with $t=4$, $v=15$, $n=v-2$) gives $D(13) \ge 4(4t)^{2t-3} = 4194304$, so $\Dbar(13) \ge 0.2410$. Our Theorem~\ref{thm:conditional1} gives the sharper bound $\Dbar(13) \ge 0.4839$. The maximal determinant is known from~\cite{Raghavarao} to be $D(13) = 14929920$, so $\Dbar(13) \approx 0.8579$. As a second example, consider $n = 94 \equiv 2 \bmod 4$. Theorem~2 of \cite{KMS00} (with $t=24$, $v=95$, $n=v-1$) gives a lower bound $D(94) \ge 2\cdot 96^{46}$, so $\Dbar(94) \ge 0.0560$, whereas our Theorem~\ref{thm:conditional1} gives $\Dbar(94) \ge 0.0605$. This bound can be improved by a construction due to Rokicki, see \cite{Orrick-www}, but the exact value of $\Dbar(94)$ is unknown. Our Theorem~\ref{thm:unconditional1} is more general than Theorem~2 of Koukouvinos \emph{et~al}, as Theorem~\ref{thm:unconditional1} covers the cases $n\le v-3$ which occur if the Hadamard conjecture is false and a Hadamard matrix of order $4t-4$ does not exist. If $n = v$ or $v-1$ then Theorem~\ref{thm:unconditional1} gives bounds of the same order of magnitude as those of Koukouvinos \emph{et~al} (of order $n^{-1/2}$ and $n^{-1}$ respectively), which is to be expected as in the first half of the proof of Theorem~\ref{thm:unconditional1} (and Lemma~\ref{lemma:minor}) we use a similar argument involving minors of a Hadamard matrix of order $v+1$. Our bounds are slightly weaker as the constant $4/e$ in the inequality~\eqref{eq:uncondbd} is not optimal in all cases. As explained in Remark~\ref{remark:LL} of \S\ref{sec:bounds}, our Theorem~\ref{thm:unconditional1} improves on Theorem~3 of de Launey and Levin~\cite{LL} by almost halving the worst-case exponent of~$n$. \section{Conclusion and remarks} Recall that $\delta(n) = |h-n|$ is the distance from a given order $n$ to the closest order $h$ of a Hadamard matrix. We have shown that $\Dbar(n) \ge n^{-\delta(n)/2}$ (see Theorem~\ref{thm:unconditional1}). On the assumption of the Hadamard conjecture, % which implies that $\delta(n) \le 2$, this can be improved to $\Dbar(n) \ge (3n)^{-1/2}$ (see Corollary~\ref{cor:improved}). In view of the numerical result $\Dbar(n) \ge 1/2$ that holds for $n \le 120$ (see~\cite{Orrick-www}), our bounds seem far from the best possible. The best prospect of improving them may be to apply the probabilistic method, as was done in the case $n = h+1$ by Brown and Spencer~\cite{BS71} and (independently) by Best~\cite{Best}. For preliminary results in this direction, see the work in progress at~\cite{rpb253}. \subsection*{Acknowledgements} We thank Will Orrick for his assistance in locating some of the references, and Warren Smith for pointing out the connection between Jacobi's identity and Sz\"oll\H{o}si's theorem. We also thank the referee, whose comments helped significantly to clarify the exposition. \pagebreak[4] \section{Appendix: Proof of Sz\"oll\H{o}si's Lemma 5.7} Here we give a short proof of Lemma 5.7 of Sz\"oll\H{o}si~\cite{Szollosi10}, using Jacobi's determinant identity~\cite{BS83,Gantmacher,Jacobi}. \begin{lemma}[Sz\"oll\H{o}si] \label{lemma:Sz} Given any unitary matrix \[U = \left[\begin{matrix} A & B\\ C & D\\ \end{matrix}\right] \] with blocks $A$, $B$, $C$, $D$, where $A$ and $D$ are square matrices not necessarily of the same size, then we have $|\det(A)| = |\det(D)|$. \end{lemma} \begin{proof} %[Proof via Jacobi's identity] Since $U$ is unitary, we have \[ U^{-1} = U^{*} = \left[\begin{matrix} A^{*} & C^{*}\\ B^{*} & D^{*}\\ \end{matrix}\right]\,, \] where ``$*$'' denotes the complex conjugate transpose. Thus, from Jacobi's identity, \[\det(A) = \det(U)\det(D^{*})\,.\] Taking absolute values and using $|\det(U)| = 1$, we obtain \[|\det(A)| = |\det(D^{*})| = |\det(D)|\,.\] \end{proof} \begin{remark} \label{remark:Sz} { If $H$ is a Hadamard matrix of order $h$, we can apply Lemma~\ref{lemma:Sz} to $U := h^{-1/2}H$ which is a unitary matrix. Thus, if $H$ is written in block form as \[H = \left[\begin{matrix} A & B\\ C & D\\ \end{matrix}\right]\,, \] where $A$ is $n\times n$ and $D$ is $d\times d$, we have \[|\det(h^{-1/2}A)| = |\det(h^{-1/2}D)|\,.\] Equivalently, since $h=n+d$, \[|\det(A)| = % h^{(n-d)/2}|\det(D)| = h^{h/2-d}|\det(D)|\,,\] which is the result that we use in \S\ref{sec:bounds}. } \end{remark} \pagebreak[4] \begin{thebibliography}{99} \bibitem{Agaian} S.~S.~Agaian. \newblock{\em Hadamard Matrices and their Applications}. \newblock Lecture Notes in Mathematics, Vol.\ {1168}. Springer-Verlag, Berlin, 1985. \bibitem{BHP} R.~C.~Baker, G.~Harman, and J.~Pintz. \newblock The difference between consecutive primes, II. \newblock {\em Proc.\ London Math.\ Soc.\ $(3)$}, {83}:532--562, 2001. \bibitem{Barba33} G.~Barba. \newblock Intorno al teorema di Hadamard sui determinanti a valore massimo. \newblock {\em Giorn.\ Mat.\ Battaglini}, {71}:70--86, 1933. \bibitem{Best} M.~R.~Best. The excess of a Hadamard matrix. \newblock {\em Indag.\ Math., }{39}:357--361, 1977. \bibitem{rpb253} R.~P.~Brent, J.~H.~Osborn, and W.~D.~Smith. \newblock Lower bounds on maximal determinants of $\pm 1$ matrices via the probabilistic method. \newblock \arxiv{1211.3248v2}, 2012. \bibitem{BS71} T.~A.~Brown and J.~H.~Spencer. % Thomas A. Brown, Joel H. Spencer \newblock Minimization of $\pm 1$ matrices under line shifts. \newblock {\em Colloq.\ Math.}, {23}:165--171, 1971. \bibitem{BS83} R.~A.~Brualdi and H.~Schneider. \newblock Determinantal identities: Gauss, Schur, Cauchy, Sylvester, Kronecker, Jacobi, Binet, Laplace, Muir, and Cayley. \newblock {\em Linear Algebra Appl., }{52/53}:769--791, 1983. \bibitem{CL65} G.~F.~Clements and B.~Lindstr\"om. \newblock A sequence of $(\pm 1)$-determinants with large values. \newblock {\em Proc.\ Amer.\ Math.\ Soc., }{16}:548--550, 1965. \bibitem{Cohn63} J.~H.~E.~Cohn. \newblock On the value of determinants. \newblock {\em Proc.\ Amer.\ Math.\ Soc., }{14}:581--588, 1963. \bibitem{Cramer} H.~Cram\'er. \newblock On the order of magnitude of the difference between consecutive prime numbers. \newblock {\em Acta Arithmetica}, {2}:23--46, 1936. \bibitem{DP88} J.~Day and B.~Peterson. \newblock Growth in Gaussian elimination. \newblock {\em Amer.\ Math.\ Monthly}, {95}:489--513, 1988. \bibitem{Ehlich64a} H.~Ehlich. \newblock Determinantenabsch\"atzungen f\"ur bin\"are Matrizen. \newblock {\em Math.\ Zeitschr., }{83}:123--132, 1964. \bibitem{Ehlich64b} H.~Ehlich. \newblock Determinantenabsch\"atzungen f\"ur bin\"are Matrizen mit $n \equiv 3 \bmod 4$. \newblock {\em Math.\ Zeitschr., }{84}:438--447, 1964. \bibitem{EM} H.~Enomoto and M.~Miyamoto. \newblock On maximal weights of Hadamard matrices. \newblock {\em J.\ Combin.\ Theory Ser. A}, {29}:94--100, 1980. \bibitem{FK} N.~Farmakis and S.~Kounias. \newblock The excess of Hadamard matrices and optimal designs. \newblock {\em Discrete Math.}, {67}:165--176, 1987. \bibitem{Gantmacher} \newblock F.~R.~Gantmacher. \newblock {\em The Theory of Matrices}, Vol.~1. Chelsea, New York, 1960. \bibitem{Hadamard} J.~Hadamard. \newblock R\'esolution d'une question relative aux d\'eterminants. \newblock {\em Bull.\ Sci.\ Math.\ S\'er.\ $2$, }{17}:240--246, 1893. Also {\em Oeuvres de Jacques Hadamard}, Tome~1, 239--245. CNRS, Paris, 1968. \bibitem{Hoheisel} G.~Hoheisel. \newblock Primzahlprobleme in der Analysis. \newblock {\em Sitz.\ Preuss.\ Akad.\ Wiss., }{2}:1--13, 1930. \bibitem{Huxley} M.~N.~Huxley. \newblock On the difference between consecutive primes. \newblock {\em Inventiones Math.}, {15}:164--170, 1972. \bibitem{Jacobi} C.~G.~J.~Jacobi. \newblock De formatione et proprietatibus determinantium. \newblock {\em J.\ reine angew.\ Math.,} %\newblock {\em Crelle's J.,} {22}:285--318, 1841. Also \newblock {\em C.\ G.\ J.\ Jacobi's Gesammelte Werke}, Bd.~3, 355--392. Georg Reimer, Berlin, 1884. % also Chelsea, New York, 1969. \bibitem{KT} H.~Kharaghani and B.~Tayfeh-Rezaie. \newblock {A Hadamard matrix of order $428$}. \newblock {\em J.\ Combinatorial Designs}, {13}:435--440, 2005. \bibitem{KMS00} C.~Koukouvinos, M.~Mitrouli, and J.~Seberry. \newblock Bounds on the maximum determinant for $(1,-1)$ matrices. \newblock {\em Bull.\ Inst.\ Combin.\ Appl.}, {29}:39--48, 2000. \bibitem{KMS01} C.~Koukouvinos, M.~Mitrouli, and J.~Seberry. \newblock An algorithm to find formul\ae\ and values of minors for Hadamard matrices. \newblock {\em Linear Algebra Appl.}, {330}:129--147, 2001. \bibitem{LG} W.~de Launey and D.~M.~Gordon. \newblock On the density of the set of known Hadamard orders. \newblock {\em Cryptogr.\ Commun.,} {2}:233--246, 2010; \arxiv{1004.4872v1}, 2010. \bibitem{LL} W.~de Launey and D.~A.~Levin. \newblock $(1,-1)$-matrices with near-extremal properties. \newblock {\em SIAM J.\ Discrete Math.}, {23}:1422--1440, 2009. \bibitem{Nicely-gaps} T.~Nicely. \newblock {New maximal prime gaps}. \newblock {\em Math.\ Comp.}, {68}:1311--1315, 1999. \bibitem{Orrick-www} W.~P.~Orrick and B.~Solomon. \newblock {\em The Hadamard maximal determinant problem}. \newblock \url{http://www.indiana.edu/~maxdet/}, Oct.\ 7, 2012. \bibitem{Paley33} R.~E.~A.~C.~Paley. \newblock On orthogonal matrices. \newblock {\em J.\ of Mathematics and Physics}, % Published by/for MIT. Not J. Math. Phys. which started in 1960. % See also American Philosophical Society {12}:311--320, 1933. \bibitem{Orrick-prog} T.~Rokicki, I.~Kazmenko, J-C.~Meyrignac, W.~P.~Orrick, V.~Trofimov, and J.~Wroblewski. \newblock {\em Large determinant binary matrices: results from Lars Backstrom's programming contest}, July 31, 2010, 18 pp. \newblock Unpublished report (courtesy of W.~P.~Orrick). \bibitem{Raghavarao} D.~Raghavarao. \newblock Some optimum weighing designs. \newblock {\em Ann.\ Math.\ Statist., }{30}:295--303, 1959. \bibitem{SW} K.~W.~Schmidt and E.~T.~H.~Wang. \newblock The weights of Hadamard matrices. \newblock {\em J. Combin.\ Theory Ser.\ A}, {23}:257--263, 1977. \bibitem{SXKM03} J.~Seberry, T.~Xia, C.~Koukouvinos, and M.~Mitrouli. \newblock The maximal determinant and subdeterminants of $\pm 1$ matrices. \newblock {\em Linear Algebra Appl.}, {373}:297--310, 2003. \bibitem{Shanks64} D.~Shanks. \newblock On maximal gaps between successive primes. \newblock {\em Math.\ Comp.}, {18}:646--651, 1964. \bibitem{Sharpe07} F.~R.~Sharpe. \newblock The maximum value of a determinant. \newblock {\em Bull.\ AMS}, {14}:121--123, 1907. \bibitem{Silva} T.~O.~e~Silva. \newblock {\em Gaps between consecutive primes}. \url{http://www.ieeta.pt/~tos/gaps.html}, Nov.\ 22, 2012. \bibitem{Szollosi10} F.~Sz\"oll\H{o}si. \newblock Exotic complex Hadamard matrices and their equivalence. \newblock {\em Cryptogr.\ Commun.,} {2}:187--198, 2010; \arxiv{1001.3062v2}, 2010. \bibitem{Wojtas64} M.~Wojtas. On Hadamard's inequality for the determinants of order non-divisible by~$4$. \newblock {\em Colloq. Math., }{12}:73--83, 1964. \end{thebibliography} \end{document}