<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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 &lt; 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&lt;n}$ whose 
first row is $(a_0,a_1,\ldots,a_{n-1})$.

By a \emph{binary} matrix we mean a matrix whose elements are in one of the
sets $\Sz := \{0,1\}$ or $\Spm := \{-1,1\}$. It will be clear from
the context which of these two cases is being considered.
A \emph{binary circulant} is a circulant matrix whose
elements are in $\Sz$ or $\Spm$.

There is a natural 
correspondence between the integers
\hbox{$\{0,1,\ldots 2^n-1\}$} and the binary circulant matrices of order
$n$.  If $N\in \{0,1,\ldots,2^n-1\}$ has the representation
\[N = \sum_{j=0}^{n-1} 2^{n-1-j\,}b_j,\]
so may be written in binary as $b_0 \ldots b_{n-1}$,
we associate $N$ with
$\circulant(a_0,\ldots,a_{n-1})$,
where $a_j = b_j$ in the case of $\Sz$, and $a_j = 2b_j-1$ in
the case of $\Spm$.

The \emph{maximal determinant problem} is concerned with the maximal value
of $|\det A|$ for an $n\times n$ binary matrix $A$. 
The \emph{Hadamard bound}~\cite{Hadamard93} states that, in the case of
binary matrices $A$ over $\{\pm1\}$, we have 
\begin{equation}
|\det A| \le n^{n/2}.					\label{eq:Hadamard1}
\end{equation}
Moreover, Hadamard's inequality is sharp for infinitely many $n$, for
example, powers of two 
(Sylvester~\cite{Sylvester67}), 
or $n$ of the form
$q+1$ where $q \equiv \modd 3 4$ and $q$ is a prime power
(Paley~\cite{Paley33}).

There is a well-known 
connection between the determinants of
$\{0,1\}$-matrices of order $n$ and
$\{\pm1\}$-matrices of order $n+1$.
This implies that an $(n+1)\times (n+1)$ $ \{\pm1\}$-matrix 
always has determinant divisible
by $ 2^{n}$.
See 
Neubauer and Radcliffe
\cite{Neubauer97} 
for details.
We give an example with $n=3$, starting with an $n\times n$ binary
matrix $B$ and ending with an $(n+1)\times(n+1)$ $\{\pm1\}$-matrix $A$,
with $\det A = 2^n\det B$.
\[
B = 
\left(\begin{tabular}{ccc}
$1$&amp;$0$&amp;$1$\\
$1$&amp;$1$&amp;$0$\\
$0$&amp;$1$&amp;$1$
\end{tabular}\right)
\begin{tabular}{c}
\begin{tiny}{ double}\end{tiny}\\[-5pt]
$\longrightarrow$
\end{tabular}
\left(\begin{tabular}{rrr}
$2$&amp;$0$&amp;$2$\\
$2$&amp;$2$&amp;$0$\\
$0$&amp;$2$&amp;$2$
\end{tabular}\right)
\]

\[
\begin{tabular}{c}
\begin{tiny}{ border}\end{tiny}\\[-5pt]
$\longrightarrow$
\end{tabular}
\left(\begin{tabular}{rrrr}
1&amp;1&amp;1&amp;1\\
$0$&amp;$2$&amp;$0$&amp;$2$\\
$0$&amp;$2$&amp;$2$&amp;$0$\\
$0$&amp;$0$&amp;$2$&amp;$2$
\end{tabular}\right)
\begin{tabular}{c}
\begin{tiny}{ subtract}\end{tiny}\\[-5pt]
$\longrightarrow$\\[-7pt]
\begin{tiny}{ first row}\end{tiny}
\end{tabular}
\left(\begin{tabular}{rrrr}
$1$&amp;$1$&amp;$1$&amp;$1$\\
$-1$&amp;$1$&amp;$-1$&amp;$1$\\
$-1$&amp;$1$&amp;$1$&amp;$-1$\\
$-1$&amp;$-1$&amp;$1$&amp;$1$
\end{tabular}\right) = A.
\]
The doubling step is the
only step where the determinant changes, and there it is multiplied
by $2^n$.

Thus, Hadamard's bound~\eqref{eq:Hadamard1} gives the bound
\begin{equation}
|\det B| = 2^{-n}|\det A| \le 2^{-n}(n+1)^{(n+1)/2},	\label{eq:Hadamard2}
\end{equation}
which applies for all $\{0,1\}$-matrices $B$ of order $n$.
We shall refer to both \eqref{eq:Hadamard1} and \eqref{eq:Hadamard2} as
\emph{Hadamard's inequality}, since it will be clear from the context
which inequality is intended.\footnote{In fact, Hadamard 
in~\cite{Hadamard93} proved a more
general inequality than~\eqref{eq:Hadamard1}, and as far as we are aware he
never stated~\eqref{eq:Hadamard2} explicitly.
A simple proof of~\eqref{eq:Hadamard1} is given by Cameron~\cite{Cameron06}.
}

The mapping from $\{0,1\}$-matrices to $\{\pm1\}$-matrices  
is reversible if we are allowed to
normalize the first row and column of the $\{\pm1\}$-matrix by changing 
the signs of rows/columns as necessary. 

The transformation illustrated above (or its reverse) 
does \emph{not} preserve any
circulant structure. 

\emph{Hadamard matrices} are square matrices with entries in $\Spm$ and
mutually orthogonal rows. The order of a Hadamard matrix is $1$, $2$, or
a multiple of $4$.  It is not known whether a Hadamard matrix of order
$4k$ exists for every positive integer $k$~--- this is the 
\emph{Hadamard conjecture}.

Various constructions for Hadamard matrices use circulant matrices. For
example, the first Paley construction (Paley~\cite{Paley33}) 
uses a circulant matrix
of order~$p$, where $p$ is a prime, $p \equiv \modd 3 4$, to
construct a Hadamard matrix of order \hbox{$p+1$}.
(The Paley construction also works for prime powers, e.g.,~$27 = 3^3$,
but does not involve circulants in such cases.)
Fletcher, Gysin and
Seberry~\cite{Fletcher01} use two circulants and a border of width
two to construct Hadamard matrices.  The Williamson
construction (Williamson~\cite{Williamson44})
requires four matrices $A, \ldots, D$ which
satisfy certain conditions, and for computational reasons these matrices
are usually taken to be circulants.

Circulant matrices also play an important role in noisy convolutional
Gaussian channels. Given a channel in which the output vector is given by
the convolution of the input vector with a chosen mask vector, in the
presence of additive Gaussian noise, the choice of mask that maximizes the
mutual information of the channel in high-SNR regimes is the first row of a
$\{0,1\}$-circulant
with near-flat Fourier spectrum,
and this circulant is often one with maximal or close to maximal 
determinant. This has important applications in X-ray and gamma ray
astronomy, optics, and computational
imaging~\cite{Ables68,Asif15,Dicke68,Fenimore78,Levin07,Yedidia17}.


It is well-known that the (unnormalized) eigenvectors of
$\circulant(a_0,\ldots,a_{n-1})$ are given by
$v_j = (1,\omega^j,\omega^{2j},\ldots,\omega^{(n-1)j})^T$,
$0 \le j &lt; n$,
where $\omega$ is a primitive $n$-th root of unity. For example,
in $\C$ we can take $\omega := \exp(2\pi i/n)$.
It follows that the eigenvalues are
\begin{equation}
\lambda_j = a_0 + a_1\omega^j + \cdots + a_{n-1}\omega^{(n-1)j},
	\; 0 \le j &lt; n,				\label{eq:lambda}
\end{equation}
and the determinant is
\begin{equation}
\prod_{j=0}^{n-1}\lambda_j = \prod_{j=0}^{n-1} f(\omega^j),
						\label{eq:det_product}
\end{equation}
where
\[f(z) := \sum_{k=0}^{n-1} a_k z^k.\]
The polynomial $f(z)$ is called the \emph{associated polynomial} of
the circulant.
Also, $f(z)$ is called a \emph{Littlewood polynomial} if the
coefficients $a_k \in \{\pm1\}$, and a 
\emph{Newman polynomial} if the $a_k \in \{0,1\}$ and $a_0 = 1$.

If $A = \circulant(a_0,\ldots,a_{n-1})$ is nonsingular, then
\eqref{eq:det_product} gives
\[
\frac{\log|\det A|}{n} = \frac{1}{n}\sum_{j=0}^{n-1}
	\log|f(e^{2\pi ij/n})|\,.
\]
This may be regarded as a discrete analogue of the
\emph{Mahler measure}~\cite{Smyth08}
\[
m(f) := \int_0^1 \log|f(e^{2\pi it})|\,{\rm d}t\,. 
\]
Using~\eqref{eq:det_product} to compute $\det A$ for a circulant matrix $A$
takes $O(n^2)$ arithmetic operations, whereas Gaussian elimination does not
take advantage of the circulant structure and takes of order $n^3$
operations. If we are considering binary matrices, whose determinants are
integers, it is necessary to perform the operations in
$\C$ to sufficient precision to obtain a result with absolute error less
than $1/2$, so that the correct result can be found by rounding 
to the nearest integer.
{From} the Hadamard bounds \eqref{eq:Hadamard1}--\eqref{eq:Hadamard2},
this means that we may have to work with of order $n\log n$ bits of precision.

To avoid the problem of rounding errors altogether, 
we can work over a finite field.
If $p$ is a prime such that $p \equiv \modd 1 n$, and
$\rho$ is a primitive root (mod $p$), then\footnote{It is not
necessary to know a primitive root (mod $p$).  We can choose a random $a$,
compute $\omega = a^{(p-1)/n}$, and check if
$1, \omega, \omega^2,\ldots, \omega^{n-1}$
are distinct (mod $p$). If not, reject $\omega$ and repeat with another 
random $a$.  In this way we work in a (small) group of order
$n$, instead of a (large) group of order $p-1$, and there is no need
to factor $p-1$.
The expected number of iterations is $n/\phi(n) = O(\log\log n)$.} 
\[\omega := \rho^{(p-1)/n} \bmod p\]
is a primitive $n$-th root of unity in the finite field $F_p$, and we
can use~\eqref{eq:det_product} to compute $(\det A) \bmod p$.
If $U$ is an  upper bound on $|\det A|$,
and \hbox{$p \ge 2U+1$}, then the result is sufficient to determine
$\det A$. 
Thus, if we use a Hadamard bound for $U$,
the prime $p$ should have of order $n\log n$ bits.
Alternatively, we could use several smaller primes with a sufficiently 
large product, and reconstruct the
result using the Chinese Remainder Theorem.\footnote{Tests indicate
that, at least for $n \le 50$, it is faster to use a single prime.
One reason for
this is that the value $\det A$ needs to be reconstructed for each
circulant $A$, so the cost of the reconstruction steps is not
negligible.}

\section{Lyndon words and necklaces}	\label{sec:Lyndon}

The usual definition of a
\emph{Lyndon word} is a nonempty string that is strictly smaller in 
lexicographic order than all of its proper rotations.  
Thus, the first six Lyndon words over $\Sz$ are
$0$, $1$, $11$, $101$, $111$, and $1111$.
Lyndon words were introduced by Shirshov~\cite{Shirshov53} (who called them
``regular words'') and Lyndon~\cite{Lyndon54} (who called them ``standard
lexicographic sequences'').

Since we consider words of a fixed length $n$, it is convenient to use 
the concept of a (binary) necklace.
We say that $w = w_0\ldots w_{n-1}$ is a
\emph{necklace of length $n$} if $w$ is not larger 
(in the lexicographic order) than any of
its rotations.  This corresponds to Duval's
``representative of a class of words of
length $n$''~\cite[(3) on p.~258]{Duval88},
where two words are said to be
in the same class if one is a rotation of the other. 

For example, according to our definition,
the six necklaces of length $4$ over $\Sz$
are $0000$, $0001$, $0011$, $0101$, $0111$, and $1111$.
It can be seen that, if we strip off leading zeros, we obtain the first six
Lyndon words. Thus, the concepts of ``Lyndon word'' and ``necklace''
are closely related, and algorithms for one may often by modified
to apply to the other.

The number $K(n)$ of necklaces of length $n$ over a binary alphabet is
\begin{equation}
K(n) = \frac{1}{n}\sum_{d|n}2^{n/d}\phi(d) 
	= \frac{2^n}{n} + O\left(\frac{2^{n/2}}{n}\right),
	\label{eq:Lyndon_kt}
\end{equation}
where $\phi$ is Euler's phi function.
$K(n)$ is tabulated in OEIS \seqnum{A000031}.

If $A$ is a circulant, then $|\det A|$ is 
invariant under rotations of the first row $(a_0,\ldots,a_{n-1})$.
Thus, when searching for circulants of order~$n$ 
with maximal determinants, it is
sufficient to consider circulants whose first row is a necklace
of length~$n$.
{From}~\eqref{eq:Lyndon_kt}, this saves a factor of approximately~$n$.

In our computations we use two nontrivial algorithms related to
Lyndon words/necklaces.
One is the algorithm of Booth~\cite{Booth80}, which determines in linear
time if a word $w = w_0\ldots w_{n-1}$ is in fact a necklace.\footnote{We
use a simplified version of Booth's algorithm since we do not 
need to know the rotation that would convert $w$ into a necklace.}
Booth's algorithm is closely related to the initial phase of the
Knuth, Morris and Pratt fast pattern-matching algorithm~\cite{KMP-algorithm}.

The other algorithm that we use is Duval's algorithm~\cite{Duval88} which,
given a necklace of length~$n$, returns the
next necklace (of length~$n$) in lexicographic order\footnote{Duval's
paper~\cite{Duval88} considers Lyndon words but, using 
\cite[comment~(3)~on~p.~258]{Duval88},
we easily get a similar algorithm for necklaces.},
in amortized 
(i.e., average) constant time, see~\cite{Berstel94}. Using Duval's algorithm
we can cycle through all necklaces of length~$n$ in time
$O(2^n/n)$.

Other algorithms could be used.  For example, Shiloach~\cite{Shiloach81}
gives an algorithm that reduces the number of comparisons used by Booth's
algorithm. We used Booth's algorithm because it was sufficient for our
purposes, and simpler to implement than Shiloach's algorithm.
The overall complexity of our algorithms is dominated by the time
required to evaluate determinants using~\eqref{eq:det_product},
not by the time required to check or enumerate necklaces.

\section{Fast evaluation of circulant determinants}	\label{sec:fasteval}

Standard algorithms of linear algebra, such as Gaussian elimination,
require of order $n^3$ operations to evaluate the determinant of
an $n \times n$ matrix $A$.  Using formula~\eqref{eq:det_product}, this
can be reduced to order $n^2$ if $A$ is a circulant.  In fact, using
the fast Fourier transform (FFT), $O(n \log n)$ operations suffice.

However, in our application we can do even better. Because Duval's algorithm
takes constant time (on average), the number of symbols that are changed
as we go from one necklace to the next is $O(1)$ 
on average.\footnote{We find experimentally that the mean number
of symbols changed is 
$2+O(n/2^n)$ as $n \to \infty$. 
The limiting value $2$ is the same as the
mean number of bits changed when counting up in binary.}
Thus, each $\lambda_j$ value given by~\eqref{eq:lambda}
can be updated in $O(1)$ operations (on average), and the determinant,
given by~\eqref{eq:det_product}, can be updated with $O(n)$ operations
(on average).  Since there are $\simeq 2^n/n$ necklaces of
length $n$, the computation of all the relevant determinants
can be done with $O(2^n)$ operations.  The cost of precomputing a table
of powers $\omega^{jk}\; (0 \le j, k &lt; n)$ is negligible.

Note that we used the term ``operations'' rather than ``time'', because the
arithmetic operations need to be performed using of order $n\log n$ bits
of precision, as noted above.  Thus, the overall complexity
is $O(2^n M(n\log n))$, where $M(N)$ is the time required to multiply $N$-bit
numbers.

In theory, a slightly better complexity can be attained by using several
small primes and reconstructing the result via the Chinese Remainder
Theorem.  However, the cost of $O(2^n/n)$ reconstructions must be taken into
account.  In practice, $n$ is never large, because of the
exponentially growing factor $2^n$ in the complexity, so the difference
between the two approaches is essentially an implementation-dependent constant
factor.

\section{Parallel algorithms}		\label{sec:parallel}

Suppose we wish to use $P \ge 1$ processors in parallel. If the
$K = K(n) \simeq 2^n/n$ necklaces of length $n$ are 
$W_0 = 0\ldots 0, W_1, W_2, \ldots, W_{K-1} = 1\ldots 1$,
we would like processor $q$ ($0 \le q &lt; P$) to compute the determinants
corresponding (approximately) to necklaces
$W_{\lfloor{qK/P}\rfloor},\ldots,W_{\lfloor{(q+1)K/P}\rfloor-1}$.
The problem is how to determine
the starting point 
for processor~$q$,
without enumerating $W_1, W_2, \ldots, W_{\lfloor{qK/P}\rfloor}$.
Kociumaka {et al.\ }\cite{Kociumaka14} sketch
a deterministic polynomial-time algorithm for this problem,
but it is very complicated. We used a simpler, randomized algorithm.
\footnote{A similar algorithm, although not specifically intended for
parallel computation, is described by
Briggs and Ying~\cite{Briggs18}.
For 
related references,
see Ghosh and Pasupathy~\cite{Ghosh13}.}

The idea is to take a random sample of $T$ necklaces, each of
length~$n$.
Sort the sample, and then divide it into $P$ equal-sized
segments. Modify the initial segment to start with $W_0 = 0\ldots 0$ and the
final segment to end with $W_{K-1} = 1\ldots 1$.  Thus, each processor has
approximately $\mu = K/P$ of words to process.
Also, we know the necklace starting each segment, so we can use Duval's
algorithm to enumerate all necklaces in a segment.

How large does the sample size $T$ need to be?
Suppose the procedure just described gives the $q$-th processor $S_q$
necklaces to process, 
where $0 \le q &lt; P$ and
$S_0+\cdots+S_{P-1} = K = P\mu$.  
Define $\varepsilon_q$ by $S_q = (1+\varepsilon_q)\mu$,
so $\varepsilon_q$ measures the relative difference between $S_q$ 
and the mean $\mu$.
Using extreme-value theory it can be shown that,
as $\min(P, T/(P\ln P), 2^n/T) \to \infty$,
we have
\begin{equation}			\label{eq:maxdev}
\E[\max\{\varepsilon_0,\ldots,\varepsilon_{P-1}\}] 
  \sim \sqrt{\frac{2P\ln P}{T}}.
\end{equation}
Simulations show that~\eqref{eq:maxdev} gives a reasonable
approximation even for small~$P$, provided $2^n \ge T \ge P &gt; 1$. 
Thus, for a given (one-sided) tolerance $\varepsilon &gt; 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} &lt; 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}, &amp;\text{if } n \equiv \modd 0 4;\\
	    2(n-1)\,(n-2)^{(n-2)/2}, &amp;\text {if } n \equiv \modd 2 4;\\
	    (2n-1)^{1/2}\,(n-1)^{(n-1)/2}, &amp;\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 &gt; 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 &lt; 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) &lt; U_{01}(39)$.  Another counter-example is $n=51 = 3 \times 17$.
We find that $D_{01}(51) &lt; 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 &gt; 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)| &gt; 95$ for sufficiently small
$\x &gt; 0$.
In fact, 
$|\det A(0.241)| &gt; 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) &gt; 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 &gt; 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, &amp;\text{if $j$ is a quadratic residue modulo $n$, 
	$j \not\equiv \modd 0 n$};\\
 -1, &amp;\text{if $j$ is a quadratic non-residue modulo $n$};\\
 \phantom{+}0, &amp;\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
	&gt; \det A_{13}(x_3) \approx 7684.16
	&gt; \det A_{13}({\textstyle\frac12}) \approx 7659.73
	&gt; D_{01}(13) = 6561
	&gt; \det A_{13}(1) = 5103
	&gt; \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 &gt; 0$ gives $\det A(\x) &gt; 6912 = D_{\pm1}(9)$.
Indeed, we can take $\x=1$, as $\det A(1) = 8582 &gt; 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&gt;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 &gt; -\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 &gt; -\det A(\pm1) = 215055782117376.
\]
Since $215055782117376 = D_{\pm1}(22) = 2^{21}\times 102546588$ (see
Table~\ref{tab:c}), we have $|\det A(0)| &gt; 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 &gt; 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	       &amp; maximal 	&amp; ratio  &amp; lex-least &amp; lex-least \\ 
$n$	  &amp;  $|$determinant$|$	&amp; $D_{01}(n)/$ &amp; word &amp; word \\
 	  &amp; $D_{01}(n)$ &amp; $U_{01}(n)$ &amp; (decimal) &amp; (over $\{0,1\}$) \\
\hline
$1$ &amp; $1$ &amp; $1.0000$ &amp; $1$ &amp; \nsp{\tt 1} \\	
$2$ &amp; $1$ &amp; $1.0000$ &amp; $1$ &amp; \nsp{\tt 01} \\
$3$ &amp; $2$ &amp; $1.0000$ &amp; $3$ &amp; \nsp{\tt 011} \\
$4$ &amp; $3$ &amp; $1.0000$ &amp; $7$ &amp; \nsp{\tt 0111} \\
$5$ &amp; $4$ &amp; $0.8000$ &amp; $15$ &amp; \nsp{\tt 01111} \\
$6$ &amp; $9$ &amp; $0.7500$ &amp; $11$ &amp; \nsp{\tt 001011} \\
$7$ &amp; $32$ &amp; $1.0000$ &amp; $23$ &amp; \nsp{\tt 0010111} \\
$8$ &amp; $45$ &amp; $0.6923$ &amp; $47$ &amp; \nsp{\tt 00101111} \\
$9$ &amp; $95$ &amp; $0.6597$ &amp; $47$ &amp; \nsp{\tt 000101111} \\
$10$ &amp; $275$ &amp; $0.6152$ &amp; $55$ &amp; \nsp{\tt 0000110111} \\
$11$ &amp; $1458$ &amp; $1.0000$ &amp; $183$ &amp; \nsp{\tt 00010110111} \\
$12$ &amp; $2240$ &amp; $0.6145$ &amp; $439$ &amp; \nsp{\tt 000110110111} \\
$13$ &amp; $6561$ &amp; $0.6923$ &amp; $1527$ &amp; \nsp{\tt 0010111110111} \\
$14$ &amp; $19952$ &amp; $0.5759$ &amp; $751$ &amp; \nsp{\tt 00001011101111} \\
$15$ &amp; $131072$ &amp; $1.0000$ &amp; $2479$ &amp; \nsp{\tt 000100110101111} \\
$16$ &amp; $214245$ &amp; $0.5691$ &amp; $2935$ &amp; \nsp{\tt 0000101101110111} \\
$17$ &amp; $755829$ &amp; $0.6784$ &amp; $2935$ &amp; \nsp{\tt 00000101101110111} \\
$18$ &amp; $2994003$ &amp; $0.6505$ &amp; $9903$ &amp; \nsp{\tt 000010011010101111} \\
$19$ &amp; $19531250$ &amp; $1.0000$ &amp; $22427$ &amp; \nsp{\tt 0000101011110011011} \\
$20$ &amp; $37579575$ &amp; $0.6010$ &amp; $28023$ &amp; \nsp{\tt 00000110110101110111} \\
$21$ &amp; $134534444$ &amp; $0.6560$ &amp; $45999$ &amp; \nsp{\tt 000001011001110101111} \\
$22$ &amp; $577397064$ &amp; $0.6178$ &amp; $117623$ &amp; \nsp{\tt 0000011100101101110111} \\  
$23$ &amp; $4353564672$ &amp; $1.0000$ &amp; $340831$ &amp; \nsp{\tt 00001010011001101011111} \\
$24$ &amp; $10757577600$ &amp; $0.7060$ &amp; $843119$ &amp; \nsp{\tt 000011001101110101101111} \\
$25$ &amp; $31495183733$ &amp; $0.5787$ &amp; $638287$ &amp; \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     &amp; maximal  &amp; ratio to &amp; lex-least word \\
$n$	&amp; $|$determinant$|$	&amp; upper bound &amp; (decimal) \\
\hline
$26$ &amp; $154611524732$ &amp; $0.5744$ &amp; $957175$ \\
$27$ &amp; $738139162166$ &amp; $0.5442$ &amp; $1796839$ \\
$28$ &amp; $3124126889325$ &amp; $0.6101$ &amp; $5469423$ \\
$29$ &amp; $11937232425585$ &amp; $0.6069$ &amp; $6774063$ \\
$30$ &amp; $65455857159975$ &amp; $0.6271$ &amp; $37463883$ \\
$31$ &amp; $562949953421312$ &amp; $1.0000$ &amp; $77446231$ \\
$32$ &amp; $1395230053365015$ &amp; $0.6148$ &amp; $47828907$ \\
$33$ &amp; $5687258414265018$ &amp; $0.6123$ &amp; $196303815$ \\
$34$ &amp; $30551195956571643$ &amp; $0.5827$ &amp; $95151003$ \\
$35$ &amp; $300189270593998242$ &amp; $1.0000$ &amp; $1324935477$ \\
$36$ &amp; $809028975189744400$ &amp; $0.6309$ &amp; $1822895095$ \\
$37$ &amp; $3198686446402685263$ &amp; $0.5760$ &amp; $430812063$ \\
$38$ &amp; $19288701806345611347$ &amp; $0.5825$ &amp; $2846677239$ \\
$39$ &amp; $103227456252120723684$ &amp; $0.5161$ &amp; $10313700815$ \\
$40$ &amp; $529663503370085366373$ &amp; $0.5885$ &amp; $6269629671$ \\
$41$ &amp; $2311393009109010944326$ &amp; $0.5638$ &amp; $26764629467$ \\
$42$ &amp; $15469925980869995489631$ &amp; $0.6023$ &amp; $22992859983$ \\
$43$ &amp; $162805498773679522226642$ &amp; $1.0000$ &amp; $92035379515$ \\
$44$ &amp; $402826140168935435652453$ &amp; $0.5245$ &amp; $162368181483$ \\
$45$ &amp; $2268175963362305735661143$ &amp; $0.6192$ &amp; $226394696439$ \\
$46$ &amp; $12738408112895861486972391$ &amp; $0.5307$ &amp; $631304341299$ \\
$47$ &amp; $158993694406781688266883072$ &amp; $1.0000$ &amp; $4626135339999$ \\
$48$ &amp; $483776963047101724429782080$ &amp; $0.6179$ &amp; $924925407055$ \\
$49$ &amp; $2226275734022433928055705600$ &amp; $0.5715$ &amp; $1588449170843$ \\
$50$ &amp; $15940963431893953997118039375$ &amp; $0.5992$ &amp; $5455102172067$ \\
$51$ &amp; $86343902346653136953496818019$ &amp; $0.4706$ &amp; $12463552538547$ \\
$52$ &amp; $471252255596620483490068604560$ &amp; $0.5013$ &amp; $23418838481755$ \\
\hline
\end{tabular}
\end{center}
\caption{Maximal determinants of $\{0,1\}$-circulants, $25 &lt;  n \le 52$.}
\vspace*{-10pt}
\label{tab:b}
\end{table}

\begin{table}[H] 	
\begin{center}
\begin{tabular}{c|c|c|cc}
order	       &amp; maximal  	&amp; ratio  &amp; lex-least &amp; lex-least \\ 
$n$	  &amp;  scaled $|$det$|$	&amp; $D_{\pm}(n)/$ &amp; word &amp; word \\
 	  &amp; $D_{\pm1}(n)/2^{n-1}$ &amp; $U_{\pm}(n)$ &amp; (decimal) &amp; (over $\{\pm1\}$) \\
\hline
1 &amp; 1 &amp; 1.0000 &amp; 0 &amp; \nsp{\tt -} \\
2 &amp; 0 &amp; 0.0000 &amp; 0 &amp; \nsp{\tt --} \\
3 &amp; 1 &amp; 1.0000 &amp; 1 &amp; \nsp{\tt --+} \\
4 &amp; 2 &amp; 1.0000 &amp; 1 &amp; \nsp{\tt ---+} \\
5 &amp; 3 &amp; 1.0000 &amp; 1 &amp; \nsp{\tt ----+} \\
6 &amp; 4 &amp; 0.8000 &amp; 1 &amp; \nsp{\tt -----+} \\
7 &amp; 8 &amp; 0.6667 &amp; 11 &amp; \nsp{\tt ---+-++} \\
8 &amp; 18 &amp; 0.5625 &amp; 11 &amp; \nsp{\tt ----+-++} \\
9 &amp; 27 &amp; 0.4154 &amp; 11 &amp; \nsp{\tt -----+-++} \\
10 &amp; 44 &amp; 0.3056 &amp; 11 &amp; \nsp{\tt ------+-++} \\
11 &amp; 267 &amp; 0.5973 &amp; 39 &amp; \nsp{\tt -----+--+++} \\
12 &amp; 1024 &amp; 0.7023 &amp; 83 &amp; \nsp{\tt -----+-+--++} \\
13 &amp; 3645 &amp; 1.0000 &amp; 83 &amp; \nsp{\tt ------+-+--++} \\
14 &amp; 6144 &amp; 0.6483 &amp; 83 &amp; \nsp{\tt -------+-+--++} \\
15 &amp; 23859 &amp; 0.6886 &amp; 359 &amp; \nsp{\tt ------+-++--+++} \\
16 &amp; 50176 &amp; 0.3828 &amp; 691 &amp; \nsp{\tt ------+-+-++--++} \\
17 &amp; 187377 &amp; 0.4977 &amp; 1643 &amp; \nsp{\tt ------++--++-+-++} \\
18 &amp; 531468 &amp; 0.4770 &amp; 2215 &amp; \nsp{\tt ------+---+-+--+++} \\
19 &amp; 3302697 &amp; 0.7176 &amp; 9895 &amp; \nsp{\tt -----+--++-+-+--+++} \\
20 &amp; 10616832 &amp; 0.5436 &amp; 6483 &amp; \nsp{\tt -------++--+-+-+--++} \\
21 &amp; 39337984 &amp; 0.6291 &amp; 67863 &amp; \nsp{\tt ----+----+--+---+-+++} \\
22 &amp; 102546588 &amp; 0.5000 &amp; 21095 &amp; \nsp{\tt -------+-+--+--++--+++} \\ 
23 &amp; 568833245 &amp; 0.6087 &amp; 72519 &amp; \nsp{\tt ------+---++-++-+---+++}\\
24 &amp; 3073593600 &amp; 0.7060 &amp; 144791 &amp; \nsp{\tt ------+---++-+-++--+-+++} \\
25 &amp; 8721488875 &amp; 0.5724 &amp; 108199 &amp; \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     &amp; maximal scaled $|$det$|$ 	&amp; ratio to &amp; lex-least word\\
 $n$	  &amp;  $D_{\pm1}(n)/2^{n-1}$	&amp; upper bound &amp; (decimal)\\
\hline
26 &amp; 32998447572 &amp; 0.6064 &amp; 355463 \\
27 &amp; 164855413835 &amp; 0.6125 &amp; 604381 \\
28 &amp; 572108938470 &amp; 0.4218 &amp; 1289739 \\
29 &amp; 2490252810073 &amp; 0.4863 &amp; 1611219 \\
30 &amp; 10831449635712 &amp; 0.5507 &amp; 1680711 \\
31 &amp; 68045615234375 &amp; 0.6520 &amp; 6870231 \\
32 &amp; 282773291271138 &amp; 0.5023 &amp; 12817083 \\
33 &amp; 1592413932070703 &amp; 0.7017 &amp; 18635419 \\
34 &amp; 5234078743146888 &amp; 0.5635 &amp; 55100887 \\
35 &amp; 33374247484277975 &amp; 0.6366 &amp; 149009085 \\
36 &amp; 198124573871046186 &amp; 0.6600 &amp; 160340631 \\
37 &amp; 787413957917252603 &amp; 0.6140 &amp; 415804239 \\
38 &amp; 3195257068570067448 &amp; 0.5754 &amp; 829121815 \\
39 &amp; 22999238901574021485 &amp; 0.6946 &amp; 4737823097 \\
40 &amp; 117140061677844350646 &amp; 0.5857 &amp; 1446278811 \\
41 &amp; 536469708946538168543 &amp; 0.5961 &amp; 3001209959 \\
42 &amp; 2417648227367853639168 &amp; 0.5897 &amp; 19153917469 \\
43 &amp; 14611334654738350617599 &amp; 0.5689 &amp; 52222437727 \\
44 &amp; 65738632907943707712320 &amp; 0.4038 &amp; 20159598251 \\
45 &amp; 438910341492340511320163 &amp; 0.5715 &amp; 166482220965 \\
46 &amp; 2010768410464246499566152 &amp; 0.5489 &amp; 90422521191 \\
47 &amp; 12779930756727248097293989 &amp; 0.5324 &amp; 115099593371 \\
48 &amp; 100192997081088000000000000 &amp; 0.6302 &amp; 242235026743 \\
49 &amp; 408375323859124630659059549 &amp; 0.5216 &amp; 1416138805685 \\
50 &amp; 2152519997519833685106486024 &amp; 0.5526 &amp; 2380679727935 \\
51 &amp; 14098690136202107270366810369 &amp; 0.5300 &amp; 2716242515341 \\
52 &amp; 99371059004238555166801920000 &amp; 0.5416 &amp; 1758408815375 \\
\hline
\end{tabular}
\end{center}
\caption{Maximal scaled determinants of $\{\pm1\}$-circulants,
 $25 &lt;  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}

                                                                                

</pre></body></html>