\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \newcommand{\C}{{\mathbb C}} \newcommand{\E}{{\mathbb E}} \newcommand{\R}{{\mathbb R}} \newcommand{\N}{{\mathbb N}} \newcommand{\Q}{{\mathbb Q}} \newcommand{\Z}{{\mathbb Z}} \newcommand{\circulant}{{\rm circ}} \newcommand{\Sz}{S_{01}} \newcommand{\Spm}{S_{\pm1}} \newcommand{\HBE}{\mathrm{H_{BE}}} \newcommand{\GF}{\mathrm{GF}} \newcommand{\x}{{\varepsilon}} \newcommand{\raisedot}{\raisebox{2pt}{$.$}} \newcommand{\raisecomma}{\raisebox{2pt}{$,$}} \newcommand{\nsp}{\hspace{0em}} \def\modd#1 #2{#1\ \mbox{\rm (mod}\ #2\mbox{\rm )}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Computation of Maximal Determinants of \\ \vskip .1in Binary Circulant Matrices } \vskip 1cm \large Richard P. Brent\\ Mathematical Sciences Institute\\ Australian National University\\ Canberra, ACT 2601 \\ Australia\\ \href{mailto:circulants@rpbrent.com}{\tt circulants@rpbrent.com} \\ \ \\ Adam B.\ Yedidia\\ Electrical Engineering and Computer Science\\ Massachusetts Institute of Technology\\ Cambridge, MA 02139 \\ USA\\ \href{mailto:adamyedidia@gmail.com}{\tt adamyedidia@gmail.com} \end{center} \renewcommand{\thetable}{\arabic{table}} \begin{abstract} We describe algorithms for computing maximal determinants of binary circulant matrices of small orders. Here ``binary matrix'' means a matrix whose elements are drawn from $\{0,1\}$ or $\{-1,1\}$. We describe efficient parallel algorithms for the search, using Duval's algorithm for generation of necklaces and the well-known representation of the determinant of a circulant in terms of roots of unity. Tables of maximal determinants are given for orders $\le 52$. Our computations extend earlier results and disprove two plausible conjectures. \end{abstract} \section{Introduction} \label{sec:intro} A \emph{circulant} matrix $A = (a_{j,k})$ of order $n$ is an $n \times n$ matrix whose elements $a_{j,k}$ depend only on $(k-j) \bmod n$. Thus, an $n \times n$ circulant is a matrix of the form $A = (a_{(k-j) \bmod n})_{\,0 \le j, k < n}$. Circulants arise in various applications in signal processing and combinatorics, and have a close connection with Fourier transforms. The set of all circulants of order $n$ (with elements in some fixed ring $R$) form a commutative algebra, since the sum and product of two circulants is a circulant, and it is easy to see that multiplication of circulants is commutative. We write $\circulant(a_0,a_1,\ldots,a_{n-1})$ for the circulant $(a_{(k-j) \bmod n})_{\,0\le j,k 1$. Thus, for a given (one-sided) tolerance $\varepsilon > 0$, we should take \begin{equation} \label{eq:Tchoice} T \approx \frac{2P\ln P}{\varepsilon^2}\,\raisedot \end{equation} With this choice \footnote{In fact, our program used simply $T = 4000P$, equivalent to taking $\varepsilon = \sqrt{\ln(P)/2000}$ in~\eqref{eq:Tchoice}. We had $P \le 416$, so $\varepsilon \le \sqrt{\ln(416)/2000} < 0.06$.} of $T$ we can expect that, on average, the slowest processor will take only about $1+\varepsilon$ times as long as the average processor.\footnote{This ignores any random variations in speed due to other users in a shared multi-processor computer system. In practice such variations may be larger than the variations caused by random sampling.} We now describe how to randomly and uniformly sample the set of all necklaces of length $n$. Generate a random binary string of length $n$, and test (using Booth's algorithm) if it corresponds to a necklace. If so, accept the string. Otherwise, reject the string and try again.\footnote{It is not sufficient to rotate the string until we obtain a necklace. This would not give each necklace an equal probability of selection. Consider, for example, the case $n=2$, where the three necklaces $00$, $01$, and $11$ would be selected with probabilities $1/4$, $1/2$, and $1/4$ respectively. } This process is repeated until we have the desired number $T$ of necklaces (not necessarily distinct). Clearly each necklace is equally likely to appear in the final list. Since the probability of a random binary string of length $n$ being a necklace is $K/2^n$, the expected number of random binary strings that are needed is $T/(K/2^n) = nT\,(1+O(2^{-n/2}))$. The algorithm that we have described is an example of Von Neumann's \emph{rejection method}~\cite{von-Neumann-work}. Other examples may be found in Devroye's book~\cite{Devroye86}. For $n \ge 2$ we can speed up the generation of random necklaces, if we exclude the special cases $0\ldots 0$ and $1\ldots 1$, and take advantage of the fact that all other necklaces have the form $0x\ldots y1$, where $x,\ldots,y \in\{0,1\}$. \section{Computational results} Our computations extend some entries in the OEIS~\cite{OEIS}. Tables \ref{tab:a}--\ref{tab:b} give computational results for the maximal determinants $D_{01}(n)$ of $\{0,1\}$-circulants of orders $n \le 52$. The third column of each table gives the ratio $D_{01}(n)/U_{01}(n)$, where $D_{01}(n)$ is the maximum of $|\det(B)|$ for $\{0,1\}$-circulants $B$ of order $n$, and $U_{01}(n)$ is an upper bound on $D_{01}(n)$. Similarly, Tables \ref{tab:c}--\ref{tab:d} give computational results for the maximal determinants $D_{\pm1}(n)$ of $\{\pm1\}$-circulants of orders $n \le 52$. Here the third column is the ratio $D_{\pm1}(n)/U_{\pm1}(n)$, where $U_{\pm1}(n)$ is an upper bound on $D_{\pm1}(n)$. In Tables \ref{tab:c}--\ref{tab:d} we scale the determinants of $\{\pm1\}$-circulants by dividing by the known factor $2^{n-1}$. In the last column of Table~\ref{tab:c}, ``$-$'' and ``$+$'' are used as abbreviations for $-1$ and $+1$ respectively. The bounds $U_{01}(n)$ and $U_{\pm1}(n)$ are defined as follows. Let \begin{equation} \HBE(n) := \begin{cases} n^{n/2}, &\text{if } n \equiv \modd 0 4;\\ 2(n-1)\,(n-2)^{(n-2)/2}, &\text {if } n \equiv \modd 2 4;\\ (2n-1)^{1/2}\,(n-1)^{(n-1)/2}, &\text{otherwise.} \end{cases} \label{eq:HBE} \end{equation} Then $\HBE(n)$ is an upper bound on $|\det A|$ for $\{\pm1\}$-matrices $A$ of order~$n$. The case $n \equiv \modd 0 4$ is due to Hadamard~\cite{Hadamard93}; the case $n \equiv \modd 2 4$ is due to Ehlich~\cite{Ehlich64a} and Wojtas~\cite{Wojtas64}; and the remaining case ($n$ odd) is due to Barba~\cite{Barba33}, Ehlich~\cite{Ehlich64a}, and Wojtas~\cite{Wojtas64}. We do not use Ehlich's slightly sharper, but more complicated, bound that applies when $n \equiv \modd 3 4$. For this bound, see Ehlich~\cite{Ehlich64b} or Orrick~\cite{Orrick-www}. In view of the discussion in \S\ref{sec:intro}, we take \begin{equation} \label{eq:pmbound} U_{\pm1}(n) := 2^{n-1}\lfloor{\HBE(n)/2^{n-1}}\rfloor \end{equation} and \begin{equation} \label{eq:01bound} U_{01}(n) := \lfloor\HBE(n+1)/2^n \rfloor. \end{equation} It is an open question whether $D_{\pm1}(n)$ attains the bound $U_{\pm1}(n)$ for any $n > 13$. (If we restrict attention to the cases $n \equiv \modd 0 4$, this is the \emph{circulant Hadamard} problem.) On the other hand, $D_{01}(p) = U_{01}(p)$ for all primes $p \equiv \modd 3 4$. This follows from the first \emph{Paley construction}~\cite{Paley33}, which constructs a Hadamard matrix of order $p+1$ with a circulant submatrix of order $p$. Inspection of Tables \ref{tab:a}--\ref{tab:b} reveals that $D_{01}(n) = U_{01}(n)$ in some other cases, specifically $n \in \{1, 2, 4, 15, 35\}$. Table \ref{tab:b} extends the list of $D_{01}(n)$ values given for $n \le 37$ in OEIS \seqnum{A086432} and the associated b-file. Table \ref{tab:d} extends the list of $D_{\pm1}(n)/2^{n-1}$ values given for $n \le 28$ in OEIS \seqnum{A215897}. This implies a corresponding extension for OEIS \seqnum{A215723}, which lists the unscaled values $D_{\pm1}(n)$. As an indication of the time required to compute the tables, we note that the computation of $D_{01}(52)$ using our parallel program (implemented in C using GMP~\cite{GMP}) took $11$ processor-years using 128 Intel Xeon3 (2.2GHz) and 224 Xeon4 (2.6GHz) processors. The computation time for order $n$ was roughly proportional to $2^n$. For verification, all the values given in the tables for orders $n < 50$ were computed at least twice, using different programs and/or different prime moduli~$p$. No discrepancies were found. In Sections \ref{sec:conjA}--\ref{sec:conjB2} we discuss some plausible conjectures that motivated our computations. \section{Conjecture A} \label{sec:conjA} {From} the third column of Table~\ref{tab:a}, the determinant of a $\{0,1\}$-circulant can attain the upper bound $U_{01}(n)$ in the cases \hbox{$n \in \{1,2,3,4,7,11,15,19,23\}$}. The Paley construction explains this for $n = 3, 7, 11, 19, 23$, and larger cases where $n$ is a prime and $n \equiv \modd 3 4$. However, it does not explain the case $n=15=3 \times 5$. Also, the upper bound is not attained for $n = 27 = 3^3$. Thus, a plausible conjecture is that the upper bound can be attained whenever $n \equiv \modd 3 4$ is the product of at most two distinct primes. Support is provided by the computation for $n = 35 = 5 \times 7$, since $D_{01}(35) = U_{01}(35)$. Our computation for $n=39$ disproves this conjecture, since $39 = 3 \times 13$ is a product of two distinct primes, but $D_{01}(39) < U_{01}(39)$. Another counter-example is $n=51 = 3 \times 17$. We find that $D_{01}(51) < U_{01}(51)/2$. After our computations were completed, we found an explanation for the cases $n=15$ and $n=35$. In each case $n$ has the form $p(p+2)$, where $p$ and $p+2$ are both prime. Such $n$ are covered by case (2) of the following theorem, which we quote (with a change in notation) from Kotsireas {et al.\ }\cite{KKS06}. Note that a ``circulant core'' of order $n$ refers to a $\{0,1\}$-circulant matrix of order $n$ which can be used to construct a Hadamard matrix of order $n+1$ using the correspondence between $\{0,1\}$-matrices and $\{\pm1\}$-matrices described in~\S1. \begin{samepage} \begin{theorem}[Hadamard circulant core construction] \label{thm:circulant_core} A Hadamard matrix of order $n+1$ with circulant core of order $n$ exists if \begin{itemize} \item[(1)] $n \equiv \modd 3 4$ is a prime; \item[(2)] $n = p(p+2)$, where $p$ and $p+2$ are prime; \item[(3)] $n = 2^k-1$, where $k$ is a positive integer; or \item[(4)] $n = 4k^2 + 27$, where $k$ is a positive integer and $n$ is a prime. \end{itemize} \end{theorem} \end{samepage} \begin{proof} Case (1) is due to Paley~\cite{Paley33}; case (2) is due to Stanton and Sprott~\cite{Stanton58} and also Whiteman~\cite{Whiteman62}; case (3) is due to Singer~\cite{Singer38}; and case (4) is due to Hall~\cite[Theorem 2.2]{Hall56}. \end{proof} Hall~\cite[p.~$980$]{Hall56} remarks that case~(4) is subsumed by case~(1), since $4k^2+27 \equiv \modd 3 4$, but we mention case~(4) since Hall's construction is different from that of Paley. We do not know if the list given by Theorem~\ref{thm:circulant_core} is exhaustive. The computational results given in Tables~\ref{tab:a}--\ref{tab:b} show that, for $1 \le n \le 52$, only those $n$ given by Theorem~\ref{thm:circulant_core} can provide a Hadamard matrix of order $n+1$ with a circulant core. Also, a circulant $\{0,1\}$-matrix of order $n \le 52$ can achieve the upper bound \eqref{eq:01bound} if and only if $n \le 4$ or $n$ satisfies condition (1), (2) or (3) of Theorem~\ref{thm:circulant_core}. \section[Conjecture B, case 1] {Conjecture B, case $[0,1]$} \label{sec:conjB1} When considering maximal determinants of matrices with real elements in the interval $[0,1]$, we can see that the maximum occurs at extreme points of the polytope.\footnote{This is already implicit in Hadamard~\cite{Hadamard93}.} To prove this, we need only note that the determinant $\det A$ of a square matrix $A= (a_{j,k})$ is a linear function of each variable $a_{j,k}$ considered separately. Thus, if a local maximum of $\det A$ occurs for some $a_{j,k} \in (0,1)$, we can replace $a_{j,k}$ by (at least one of) $0$ or $1$ without decreasing $\det A$. This argument does not apply if $A$ is restricted to be a circulant of order $n > 1$, because then the free parameters are just the elements $a_0,\ldots,a_{n-1}$ of the first row of $A$, and $\det A$ is \emph{not} a linear function of each $a_j$ considered separately. For example, if $n=2$ we have $\det A = a_0^2 - a_1^2$. Nevertheless, inspection of small cases suggests the conjecture that the maximum of $|\det A|$ occurs at extreme points of the $n$-dimensional polytope. We were unable to prove the conjecture, so wrote a program to check it numerically, and found that, in general, the conjecture is false. The idea is as follows. Consider all possible circulants $A$ of order $n$ with entries in $\{0,1\}$. If $\det A = \pm D_{01}(n)$, check if a small perturbation of $a_0$ towards the interior of the polytope would increase $|\det A|$. Although such behaviour is rare, it does occur.\footnote{For reasons of efficiency, our program takes as input a list (generated during the computation of Tables \ref{tab:a}--\ref{tab:b}) of necklaces that define circulants $A$ with maximal $|\det A|$, then considers all possible rotations of these circulants.} The smallest examples occur for $n=9$. Consider $A = \circulant(a_0,\ldots, a_8)$ with $(a_0,\ldots,a_8) = (0,0,0,1,1,1,1,0,1)$. We have $\det A = 95 = D_{01}(9)$, but $\partial \det A/\partial a_0 = 9$. If $a_0 = \x$ for some small $\x$, then $|\det A(\x)| = 95 + 9\x + O(\x^2)$, so $|\det A(\x)| > 95$ for sufficiently small $\x > 0$. In fact, $|\det A(0.241)| > 96.757$. For $n=10$, an example is $A = \circulant(0, 0, 1, 0, 0, 1, 1, 1, 1, 0)$, $\det A = 275$. Replacing $a_0$ by $\x = 0.112$, we obtain $\det A(\x) > 279.4$. We found examples of such behaviour for $n=9, 10$, and no other $n$ up to the limit of Table~\ref{tab:b}. However, there is a different class of examples that occur when $n = 4k+1 > 5$ is a prime, e.g.,~$n = 13, 17, 29, 37, 41$, etc. For this class we make a small modification to the \emph{Uniformly Redundant Arrays} (URAs) of \cite{Busboom97,Fenimore78}, which are equivalent to Abelian difference sets~\cite{Hall56}.\footnote{Our construction is also close to the ``modified'' URAs (MURAs) of \cite{Gottesman89}.} Define \[ A_n(x) := \circulant\left(x, \textstyle\frac{1+\chi(1)}{2},\frac{1+\chi(2)}{2},\ldots, \frac{1+\chi(n-1)}{2}\right), \] where $\chi$ is a quadratic character, defined by the Legendre symbol \[ \chi(j) = \left(\frac{j}{n}\right) := \begin{cases} +1, &\text{if $j$ is a quadratic residue modulo $n$, $j \not\equiv \modd 0 n$};\\ -1, &\text{if $j$ is a quadratic non-residue modulo $n$};\\ \phantom{+}0, &\text{if $j \equiv \modd 0 n$}. \end{cases} \] Then $A_n(0)$ corresponds to a $1$-D URA, but $\det A_n(0)$ is not generally maximal in the class of circulant determinants. However, $\det A_n(\frac12)$ may be larger than the corresponding entry in Tables~\ref{tab:a}--\ref{tab:b}. It may be shown\footnote{The proof uses the identity $A_n(0)^2 + A_n(0) = k(I+J)$.} that, for $n = 4k+1$ an odd prime, \begin{equation} \det A_n(x) = (x+2k)(x^2-x-k)^{2k}. \label{eq:detAx} \end{equation} In particular, $\det A_n(0) = 2 k^{2k+1}$, $\det A_n(1) = (2k+1)k^{2k}$, and \[ \det A_n({\textstyle\frac12}) = 2^{-n}\,n^{(n+1)/2}. \] It may be verified numerically that $\det A_n(\frac12)$ exceeds the maximal determinant given in Tables~\ref{tab:a}--\ref{tab:b} for $n = 13, 17, 29, 37,$ and $41$. The next possibility, $n=53$, is beyond the range of Table~\ref{tab:b}. We observe that the maximum of $\det A_n(x)$ for $x\in [0,1]$ is not at $x=\frac12$. One can show, by logarithmic differentiation of~\eqref{eq:detAx}, that a local maximum occurs at \[ x = x_k := \frac{\sqrt{1+4k^2}+1-2k}{2} = \frac12 + \frac{1}{8k} + O(k^{-3}), \] and \[ \max_{0\le x \le 1}\det A_n(x) = \det A_n(x_k) = \det A_n({\textstyle\frac12})\left(1+\frac{1}{8kn} + O(k^{-4})\right). \] For example, if $k=3, n=13$, we have $x_3 = (\sqrt{37}-5)/2 \approx 0.5414$, and $ U_{01}(13) = 9477 > \det A_{13}(x_3) \approx 7684.16 > \det A_{13}({\textstyle\frac12}) \approx 7659.73 > D_{01}(13) = 6561 > \det A_{13}(1) = 5103 > \det A_{13}(0) = 4374. $ \section[Conjecture B, case 2] {Conjecture B, case $[-1,1]$} \label{sec:conjB2} Replacing $[0,1]$ by $[-1,1]$, we find analogous behaviour to that described in~\S\ref{sec:conjB1}, for $n = 2, 9, 10, 11, 18$, $22$, and no other $n$ up to the limit of Table~\ref{tab:d}. The case $n=2$ is trivial because, for circulants of order~$2$ over $\Spm$, we necessarily have $\det A = 0$ at the extreme points $(a_0,a_1) = (\pm1, \pm1)$. The other cases are non-trivial. For example, if $n=9$, consider \[A(\x) := \circulant(1-\x,1,-1,1,-1,-1,1,1,1).\] We find that \[\det A(\x) = 6912 + 4608\x + O(\x^2),\] so sufficiently small $\x > 0$ gives $\det A(\x) > 6912 = D_{\pm1}(9)$. Indeed, we can take $\x=1$, as $\det A(1) = 8582 > 6912$. If $n=10$, we find that \[\det\circulant(1-\x, -1, 1, 1, -1, -1, -1, -1, -1, -1) = -(22528 + 2560\x + O(\x^2)),\] and \[\det\circulant(-1+\x, -1, -1, 1, -1, 1, 1, -1, -1, -1) = 22528 + 7680\x + O(\x^2),\] so in both cases a sufficiently small $\x>0$ disproves the conjecture. A different type of exceptional case is illustrated by \[ A(x) := \circulant(x, -1, 1, -1, 1, 1, -1, -1, -1, -1), \] where we find that $\det A(x)$ is an even polynomial in $x$, and \[-\det A(0) = 33489 > -\det A(\pm1) = 22528 = D_{\pm1}(10).\] Similarly, for order $22$, consider \[ A(x) := \circulant(x,\! -1,\! 1,\! 1,\! -1,\! -1,\! -1,\! -1,\! -1,\! -1,\! -1,\! 1,\! 1,\! -1,\! 1,\! -1,\! 1,\! -1,\! 1,\! 1,\! -1,\! -1). \] Then \[ -\det A(0) = 216409254831025 > -\det A(\pm1) = 215055782117376. \] Since $215055782117376 = D_{\pm1}(22) = 2^{21}\times 102546588$ (see Table~\ref{tab:c}), we have $|\det A(0)| > D_{\pm1}(22)$. Our search was not exhaustive, so there may be other $n$ within the range of Tables~\ref{tab:c}--\ref{tab:d} for which the maximum determinant does not occur at an extreme point of $[-1,1]^n$. \section{Remarks on periodic autocorrelations} It is hard to discern a pattern in the lex-least words given in Tables~\ref{tab:a}--\ref{tab:d}. It seems more fruitful to consider the \emph{periodic autocorrelations} of the first rows of the corresponding circulants. Equivalently, we can consider the first rows of the \emph{Gram matrices} $G = A^TA$, where $A$ is the relevant circulant. In the case of $(0,1)$-circulants, it can be useful to map $(0,1) \mapsto (-1,1)$, and consider the first row of $G' = (2A-J)^T (2A-J)$. Provided $n > 4$, the upper bound is achieved in Tables \ref{tab:a}--\ref{tab:b} if and only if the first row of $G'$ is $(n,-1,-1,\ldots,-1)$. See, for example, MacWilliams and Sloane~\cite{MacWilliams76}. In some cases the maximal determinants given in Tables~\ref{tab:a}--\ref{tab:d} have only small prime factors. For example, the entry for $n=52$ in Table~\ref{tab:d} factors as \hbox{$2^{49}\times 3^{24}\times 5^4$}, and this can be explained if we observe that the first row of $G$ is $(52, 0, 0, 0, 4, \ldots, 0, 0, 0, 4, 0, 0, 0)$. Thus, we can write $G = 52I + 4E^4 + 4E^8 + \cdots + 4E^{48}$, where $E$ is the ``circular shift'' matrix. Similarly, the entry for $n=48$ in Table~\ref{tab:d} is $2^{49}\times 3^6\times 5^{12}$, and here $G = 48I + 4E^{12} + 8E^{24} + 4E^{36}$. \section{Acknowledgements} We thank J\"org Arndt for correcting our terminology, Alex Arkhipov for his helpful comments about Hadamard matrices with circulant cores and related group theory, and the authors of Magma~\cite{Magma1} and GMP~\cite{GMP} for their invaluable software. An anonymous referee helped us to clarify several points in \S\ref{sec:Lyndon} and \S\ref{sec:parallel}. Computing resources were provided by the Australian National University and the University of Newcastle (Australia). The first author was supported in part by Australian Research Council grant DP140101417. \section{Appendix: tables of maximal determinants} \begin{table}[H] \vspace*{-0pt} \begin{center} \begin{tabular}{c|c|c|cc} order & maximal & ratio & lex-least & lex-least \\ $n$ & $|$determinant$|$ & $D_{01}(n)/$ & word & word \\ & $D_{01}(n)$ & $U_{01}(n)$ & (decimal) & (over $\{0,1\}$) \\ \hline $1$ & $1$ & $1.0000$ & $1$ & \nsp{\tt 1} \\ $2$ & $1$ & $1.0000$ & $1$ & \nsp{\tt 01} \\ $3$ & $2$ & $1.0000$ & $3$ & \nsp{\tt 011} \\ $4$ & $3$ & $1.0000$ & $7$ & \nsp{\tt 0111} \\ $5$ & $4$ & $0.8000$ & $15$ & \nsp{\tt 01111} \\ $6$ & $9$ & $0.7500$ & $11$ & \nsp{\tt 001011} \\ $7$ & $32$ & $1.0000$ & $23$ & \nsp{\tt 0010111} \\ $8$ & $45$ & $0.6923$ & $47$ & \nsp{\tt 00101111} \\ $9$ & $95$ & $0.6597$ & $47$ & \nsp{\tt 000101111} \\ $10$ & $275$ & $0.6152$ & $55$ & \nsp{\tt 0000110111} \\ $11$ & $1458$ & $1.0000$ & $183$ & \nsp{\tt 00010110111} \\ $12$ & $2240$ & $0.6145$ & $439$ & \nsp{\tt 000110110111} \\ $13$ & $6561$ & $0.6923$ & $1527$ & \nsp{\tt 0010111110111} \\ $14$ & $19952$ & $0.5759$ & $751$ & \nsp{\tt 00001011101111} \\ $15$ & $131072$ & $1.0000$ & $2479$ & \nsp{\tt 000100110101111} \\ $16$ & $214245$ & $0.5691$ & $2935$ & \nsp{\tt 0000101101110111} \\ $17$ & $755829$ & $0.6784$ & $2935$ & \nsp{\tt 00000101101110111} \\ $18$ & $2994003$ & $0.6505$ & $9903$ & \nsp{\tt 000010011010101111} \\ $19$ & $19531250$ & $1.0000$ & $22427$ & \nsp{\tt 0000101011110011011} \\ $20$ & $37579575$ & $0.6010$ & $28023$ & \nsp{\tt 00000110110101110111} \\ $21$ & $134534444$ & $0.6560$ & $45999$ & \nsp{\tt 000001011001110101111} \\ $22$ & $577397064$ & $0.6178$ & $117623$ & \nsp{\tt 0000011100101101110111} \\ $23$ & $4353564672$ & $1.0000$ & $340831$ & \nsp{\tt 00001010011001101011111} \\ $24$ & $10757577600$ & $0.7060$ & $843119$ & \nsp{\tt 000011001101110101101111} \\ $25$ & $31495183733$ & $0.5787$ & $638287$ & \nsp{\tt 0000010011011110101001111} \\ \hline \end{tabular} \end{center} \caption{Maximal determinants of $\{0,1\}$-circulants of order $n \le 25$.} \vspace*{-20pt} \label{tab:a} \end{table} \begin{table}[H] \begin{center} \begin{tabular}{c|c|c|c} order & maximal & ratio to & lex-least word \\ $n$ & $|$determinant$|$ & upper bound & (decimal) \\ \hline $26$ & $154611524732$ & $0.5744$ & $957175$ \\ $27$ & $738139162166$ & $0.5442$ & $1796839$ \\ $28$ & $3124126889325$ & $0.6101$ & $5469423$ \\ $29$ & $11937232425585$ & $0.6069$ & $6774063$ \\ $30$ & $65455857159975$ & $0.6271$ & $37463883$ \\ $31$ & $562949953421312$ & $1.0000$ & $77446231$ \\ $32$ & $1395230053365015$ & $0.6148$ & $47828907$ \\ $33$ & $5687258414265018$ & $0.6123$ & $196303815$ \\ $34$ & $30551195956571643$ & $0.5827$ & $95151003$ \\ $35$ & $300189270593998242$ & $1.0000$ & $1324935477$ \\ $36$ & $809028975189744400$ & $0.6309$ & $1822895095$ \\ $37$ & $3198686446402685263$ & $0.5760$ & $430812063$ \\ $38$ & $19288701806345611347$ & $0.5825$ & $2846677239$ \\ $39$ & $103227456252120723684$ & $0.5161$ & $10313700815$ \\ $40$ & $529663503370085366373$ & $0.5885$ & $6269629671$ \\ $41$ & $2311393009109010944326$ & $0.5638$ & $26764629467$ \\ $42$ & $15469925980869995489631$ & $0.6023$ & $22992859983$ \\ $43$ & $162805498773679522226642$ & $1.0000$ & $92035379515$ \\ $44$ & $402826140168935435652453$ & $0.5245$ & $162368181483$ \\ $45$ & $2268175963362305735661143$ & $0.6192$ & $226394696439$ \\ $46$ & $12738408112895861486972391$ & $0.5307$ & $631304341299$ \\ $47$ & $158993694406781688266883072$ & $1.0000$ & $4626135339999$ \\ $48$ & $483776963047101724429782080$ & $0.6179$ & $924925407055$ \\ $49$ & $2226275734022433928055705600$ & $0.5715$ & $1588449170843$ \\ $50$ & $15940963431893953997118039375$ & $0.5992$ & $5455102172067$ \\ $51$ & $86343902346653136953496818019$ & $0.4706$ & $12463552538547$ \\ $52$ & $471252255596620483490068604560$ & $0.5013$ & $23418838481755$ \\ \hline \end{tabular} \end{center} \caption{Maximal determinants of $\{0,1\}$-circulants, $25 < n \le 52$.} \vspace*{-10pt} \label{tab:b} \end{table} \begin{table}[H] \begin{center} \begin{tabular}{c|c|c|cc} order & maximal & ratio & lex-least & lex-least \\ $n$ & scaled $|$det$|$ & $D_{\pm}(n)/$ & word & word \\ & $D_{\pm1}(n)/2^{n-1}$ & $U_{\pm}(n)$ & (decimal) & (over $\{\pm1\}$) \\ \hline 1 & 1 & 1.0000 & 0 & \nsp{\tt -} \\ 2 & 0 & 0.0000 & 0 & \nsp{\tt --} \\ 3 & 1 & 1.0000 & 1 & \nsp{\tt --+} \\ 4 & 2 & 1.0000 & 1 & \nsp{\tt ---+} \\ 5 & 3 & 1.0000 & 1 & \nsp{\tt ----+} \\ 6 & 4 & 0.8000 & 1 & \nsp{\tt -----+} \\ 7 & 8 & 0.6667 & 11 & \nsp{\tt ---+-++} \\ 8 & 18 & 0.5625 & 11 & \nsp{\tt ----+-++} \\ 9 & 27 & 0.4154 & 11 & \nsp{\tt -----+-++} \\ 10 & 44 & 0.3056 & 11 & \nsp{\tt ------+-++} \\ 11 & 267 & 0.5973 & 39 & \nsp{\tt -----+--+++} \\ 12 & 1024 & 0.7023 & 83 & \nsp{\tt -----+-+--++} \\ 13 & 3645 & 1.0000 & 83 & \nsp{\tt ------+-+--++} \\ 14 & 6144 & 0.6483 & 83 & \nsp{\tt -------+-+--++} \\ 15 & 23859 & 0.6886 & 359 & \nsp{\tt ------+-++--+++} \\ 16 & 50176 & 0.3828 & 691 & \nsp{\tt ------+-+-++--++} \\ 17 & 187377 & 0.4977 & 1643 & \nsp{\tt ------++--++-+-++} \\ 18 & 531468 & 0.4770 & 2215 & \nsp{\tt ------+---+-+--+++} \\ 19 & 3302697 & 0.7176 & 9895 & \nsp{\tt -----+--++-+-+--+++} \\ 20 & 10616832 & 0.5436 & 6483 & \nsp{\tt -------++--+-+-+--++} \\ 21 & 39337984 & 0.6291 & 67863 & \nsp{\tt ----+----+--+---+-+++} \\ 22 & 102546588 & 0.5000 & 21095 & \nsp{\tt -------+-+--+--++--+++} \\ 23 & 568833245 & 0.6087 & 72519 & \nsp{\tt ------+---++-++-+---+++}\\ 24 & 3073593600 & 0.7060 & 144791 & \nsp{\tt ------+---++-+-++--+-+++} \\ 25 & 8721488875 & 0.5724 & 108199 & \nsp{\tt --------++-+--++-+-+--+++}\\ \hline \end{tabular} \end{center} \caption{Maximal scaled determinants of $\{\pm1\}$-circulants of order $n \le 25$.} \vspace*{-10pt} \label{tab:c} \end{table} \begin{table}[H] \begin{center} \begin{tabular}{c|c|c|c} order & maximal scaled $|$det$|$ & ratio to & lex-least word\\ $n$ & $D_{\pm1}(n)/2^{n-1}$ & upper bound & (decimal)\\ \hline 26 & 32998447572 & 0.6064 & 355463 \\ 27 & 164855413835 & 0.6125 & 604381 \\ 28 & 572108938470 & 0.4218 & 1289739 \\ 29 & 2490252810073 & 0.4863 & 1611219 \\ 30 & 10831449635712 & 0.5507 & 1680711 \\ 31 & 68045615234375 & 0.6520 & 6870231 \\ 32 & 282773291271138 & 0.5023 & 12817083 \\ 33 & 1592413932070703 & 0.7017 & 18635419 \\ 34 & 5234078743146888 & 0.5635 & 55100887 \\ 35 & 33374247484277975 & 0.6366 & 149009085 \\ 36 & 198124573871046186 & 0.6600 & 160340631 \\ 37 & 787413957917252603 & 0.6140 & 415804239 \\ 38 & 3195257068570067448 & 0.5754 & 829121815 \\ 39 & 22999238901574021485 & 0.6946 & 4737823097 \\ 40 & 117140061677844350646 & 0.5857 & 1446278811 \\ 41 & 536469708946538168543 & 0.5961 & 3001209959 \\ 42 & 2417648227367853639168 & 0.5897 & 19153917469 \\ 43 & 14611334654738350617599 & 0.5689 & 52222437727 \\ 44 & 65738632907943707712320 & 0.4038 & 20159598251 \\ 45 & 438910341492340511320163 & 0.5715 & 166482220965 \\ 46 & 2010768410464246499566152 & 0.5489 & 90422521191 \\ 47 & 12779930756727248097293989 & 0.5324 & 115099593371 \\ 48 & 100192997081088000000000000 & 0.6302 & 242235026743 \\ 49 & 408375323859124630659059549 & 0.5216 & 1416138805685 \\ 50 & 2152519997519833685106486024 & 0.5526 & 2380679727935 \\ 51 & 14098690136202107270366810369 & 0.5300 & 2716242515341 \\ 52 & 99371059004238555166801920000 & 0.5416 & 1758408815375 \\ \hline \end{tabular} \end{center} \caption{Maximal scaled determinants of $\{\pm1\}$-circulants, $25 < n \le 52$.} \vspace*{-10pt} \label{tab:d} \end{table} \begin{thebibliography}{99} \bibitem{Ables68} J. G. Ables, Fourier transform photography: a new method for X-ray astronomy, \emph{Proc.\ Astron.\ Soc.\ Austral.} \textbf{1} (1968), 172--173. \bibitem{Asif15} M. S. Asif, A. Ayremlou, A. Sankaranarayanan, A. Veeraraghavan, and R. Baraniuk, Flatcam: Thin, bare-sensor cameras using coded aperture and computation, \emph{IEEE Trans.\ Comput.\ Imaging}, to appear. Preprint, 2015, available at \url{http://arxiv.org/abs/1509.00116}. \bibitem{Barba33} G. Barba, Intorno al teorema di Hadamard sui determinanti a valore massimo, \emph{Giorn. Mat. Battaglini} {\bf{71}} (1933), 70--86. \bibitem{Berstel94} J. Berstel and M. Pocchiola, Average cost of Duval's algorithm for generating Lyndon words, \emph{Theoret.\ Comput.\ Sci.\ }\textbf{132} (1994), 415--425. \bibitem{Booth80} K. S. Booth, Lexicographically least circular substrings, \emph{Inform.\ Process.\ Lett.\ }\textbf{10} (1980), 240--242. \bibitem{Magma1} W. Bosma, J. Cannon, and C. Playoust, The Magma algebra system. I. The user language, \emph{J. Symbolic Comput.} \textbf{24} (1997), 235--265. \bibitem{Briggs18} K. Briggs and F. Ying, How to estimate quantiles easily and reliably, \emph{Math.\ Today (Southend-on-Sea)} \textbf{54}, 1 (Feb.\ 2018), 26--29. \bibitem{Busboom97} A. Busboom, H. Elders-Boll, and H. D. Schotten, Uniformly redundant arrays, \emph{Experimental Astronomy} \textbf{8} (1998), 97--123. \bibitem{Cameron06} P. J. Cameron, Hadamard Matrices, in \emph{Encyclopaedia of Design Theory}, Queen Mary, University of London, 2006. \\ Available at \url{http://www.maths.qmul.ac.uk/~lsoicher/designtheory.org/ library/encyc/topics/}. \bibitem{Devroye86} L. Devroye, \emph{Non-Uniform Random Variate Generation}, Springer-Verlag, New York, 1986, {\S}II.3. Available from \url{http://luc.devroye.org/rnbookindex.html}. \bibitem{Dicke68} R. H. Dicke, Scatter-hole cameras for X-rays and gamma rays, \emph{Astrophys.\ J.} \textbf{153} (1968), L101--L106. \bibitem{Duval88} J.-P. Duval, G\'en\'eration d'une section des classes de conjugaison et arbre des mots de Lyndon de longueur born\'ee, \emph{Theoret.\ Comput.\ Sci.\ } \textbf{60} (1988), 255--383. \bibitem{Ehlich64a} H. Ehlich, Determinantenabsch\"atzungen f\"ur bin\"are Matrizen, \emph{Math.\ Z.\ }\textbf{83} (1964), 123--132. \bibitem{Ehlich64b} H. Ehlich, Determinantenabsch\"atzungen f\"ur bin\"are Matrizen mit $n \equiv \modd 3 4$, {\em Math.\ Z.\ }\textbf{84} (1964), 438--447. \bibitem{Fenimore78} E. E. Fenimore and T. M. Cannon, Coded aperture imaging with uniformly redundant arrays, \emph{Applied Optics} \textbf{17} (1978), 337--347. \bibitem{Fletcher01} R.J. Fletcher, M. Gysin, and J. Seberry, Application of the discrete Fourier transform to the search for generalised Legendre pairs and Hadamard matrices, \emph{Australas.\ J.\ Combin.\ }\textbf{23} (2001), 75--86. \bibitem{Ghosh13} S. Ghosh and R. Pasupathy, Low-storage online estimators for quantiles and densities, \emph{Proc.\ 2013 Winter Simulation Conference}, IEEE, New York, 2013, 778--789. \bibitem{Gottesman89} S. R. Gottesman and E. E. Fenimore, New family of binary arrays for coded aperture imaging, \emph{Applied Optics\ }\textbf{28} (1989), 4344--4352. \bibitem{GMP} T. Granlund, \emph{The GNU MP Bignum Library}, \url{http://gmplib.org/}, 2016. \bibitem{Hadamard93} J. Hadamard, R\'esolution d'une question relative aux d\'eterminants, \emph{Bull.\ des Sci.\ Math.} \textbf{17} (1893), 240--246. Reprinted in \emph{Oeuvres de Jacques Hadamard}, Tome 1, CNRS, Paris, 1968, 239--245. \bibitem{Hall56} M. Hall, Jr., A survey of difference sets, \emph{Proc.\ Amer.\ Math.\ Soc.} \textbf{7} (1956), 975--986. \bibitem{KMP-algorithm} D. E. Knuth, J. H. Morris, and V. Pratt, Fast pattern matching in strings, \emph{SIAM J.\ Comput.\ }\textbf{6} (1977), 323--350. \bibitem{Kociumaka14} T. Kociumaka, J. Radoszewski, and W. Rytter, Computing $k$-th Lyndon word and decoding lexicographically minimal de Bruijn sequence, \emph{CPM 2014, Lect.\ Notes in Comp.\ Sci.,} Vol.\ {8486}, Springer, 2014, pp.\ 202--211. \bibitem{KKS06} I. S. Kotsireas, C. Koukouvinos, and J. Seberry, Hadamard ideals and Hadamard matrices with circulant core, \emph{J.\ Combin.\ Math.\ Combin.\ Comput.} \textbf{57} (May 2006), 47--63. \bibitem{Levin07} A. Levin, R. Fergus, F. Durand, and W. Freeman, Image and depth from a conventional camera with a coded aperture, \emph{ACM Trans.\ Graph.\ }\textbf{26.3} (2007), 70. \bibitem{Lyndon54} R. C. Lyndon, On Burnside's problem, \emph{Trans.\ Amer.\ Math.\ Soc.} \textbf{77} (1954), 202--215. \bibitem{MacWilliams76} F. J. MacWilliams and N. J. A. Sloane, Pseudo-random sequences and arrays, \emph{Proc.\ IEEE} \textbf{64} (1976), 1715--1729. \bibitem{Neubauer97} M. G. Neubauer and A. J. Radcliffe, The maximum determinant of $\{\pm1\}$-matrices, \emph{Linear Algebra Appl.} \textbf{257} (1997), 289--306. \bibitem{von-Neumann-work} J. von Neumann, Various techniques used in connection with random digits, in {\em Monte Carlo Method}, Appl.\ Math.\ Series {\bf{12}}, US Nat.\ Bureau of Standards, 1951, 36--38 (summary written by G.~E.~Forsythe); reprinted in {\em John von Neumann Collected Works}, Vol.~5, Pergamon Press, New York, 1963, pp.\ 768--770. \bibitem{OEIS} OEIS Foundation Inc., \emph{The On-Line Encyclopedia of Integer Sequences}, \url{http://oeis.org}, 2018. \bibitem{Orrick-www} W. Orrick, The Hadamard maximal determinant problem, preprint. Available at \url{http://www.indiana.edu/~maxdet/}, 2018. \bibitem{Paley33} R. E. A. C. Paley, On orthogonal matrices, \emph{J.~Mathematics and Physics} \textbf{12} (1933), 311--320. \bibitem{Shiloach81} Y. Shiloach, Fast canonization of circular strings, \emph{J.\ Algorithms} \textbf{2} (1981), 107--121. \bibitem{Shirshov53} A. I. Shirshov, Subalgebras of free Lie algebras, \emph{Mat.\ Sbornik N.S.} \textbf{33} (1953), 441--452. \bibitem{Singer38} J. Singer, A theorem in finite projective geometry and some applications to number theory, \emph{Trans.\ Amer.\ Math.\ Soc.} \textbf{43} (1938), 377--385. \bibitem{Smyth08} C. Smyth, The Mahler measure of algebraic numbers: a survey, in \emph{Number Theory and Polynomials}, J.~McKee and C.~Smyth (eds.), Cambridge Univ.\ Press, New York, 2008, 322--349. \bibitem{Stanton58} R. G. Stanton and D. A. Sprott, A family of difference sets, \emph{Can.\ J.\ Math.} \textbf{10} (1958), 73--77. \bibitem{Sylvester67} J. J. Sylvester, Thoughts on inverse orthogonal matrices, simultaneous sign-successions, and tessellated pavements in two or more colours, with applications to Newton's rule, ornamental tile-work, and the theory of numbers, \emph{London Edinburgh and Dublin Philos.\ Mag.\ and J.\ Sci.} \textbf{34} (1867), 461--475. \bibitem{Whiteman62} A. L. Whiteman, A family of difference sets, \emph{Illinois J.\ Math.} \textbf{6} (1962), 107--121. \bibitem{Williamson44} J. Williamson, Hadamard's determinant theorem and the sum of four squares, \emph{Duke Math.\ J.} \textbf{11} (1944), 65--81. \bibitem{Wojtas64} M. Wojtas, On Hadamard's inequality for the determinants of order non-divisible by $4$, \emph{Colloq. Math.} \textbf{12} (1964), 73--83. \bibitem{Yedidia17} A. Yedidia, C. Thrampoulidis, and G. Wornell, Analysis and optimization of aperture design in computational imaging, preprint, 2017. Available at \url{http://arxiv.org/abs/1712.04541}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 05A19, 65T50. \noindent \emph{Keywords: } binary matrix, Booth's algorithm, circulant, circulant core, computational imaging, convolutional Gaussian channel, difference set, discrete Mahler measure, Duval's algorithm, Hadamard bound, Hadamard matrix, Lyndon word, maximal determinant, modular computation, MURA, necklace, parallel algorithm, parallel computation, quantile estimation, URA. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000031}, \seqnum{A086432}, \seqnum{A215723}, \seqnum{A215897}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received April 25 2018; revised version received June 6 2018. Published in {\it Journal of Integer Sequences}, June 10 2018. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}