\documentclass{amsart} \usepackage[letterpaper,margin=1in]{geometry} \usepackage{amssymb,mathtools} \usepackage[normalem]{ulem} \usepackage{xcolor} \usepackage{array,booktabs,float} \usepackage{enumitem} \raggedbottom \usepackage[colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,urlcolor=blue!45!black]{hyperref} % --------------------------------------------------------------- % Revision markup: \add, \del and the addblock environment mark every change % from the original write-up. % Compile with % pdflatex hadamard-revised the paper % pdflatex "\def\REDLINE{1}\input{hadamard-revised}" the paper with the changes shown: % additions in red, deletions struck through % --------------------------------------------------------------- % The timing program of Appendix D, pairsum_bench.c, follows \end{document}, % where TeX ignores it. To extract it: % sed -n '/^%%%% begin pairsum_bench.c/,/^%%%% end pairsum_bench.c/p' hadamard-revised.tex | sed '1d;$d' > pairsum_bench.c % --------------------------------------------------------------- \newif\ifredline \ifdefined\REDLINE \redlinetrue \fi \definecolor{addcol}{RGB}{200,0,0} \definecolor{delcol}{RGB}{110,110,110} \ifredline \makeatletter \DeclareRobustCommand{\addlinks}{\def\@linkcolor{addcol}\def\@citecolor{addcol}\def\@urlcolor{addcol}} \DeclareRobustCommand{\dellinks}{\def\@linkcolor{delcol}\def\@citecolor{delcol}\def\@urlcolor{delcol}} \makeatother \newcommand{\add}[1]{{\color{addcol}\addlinks#1}} \newcommand{\del}[1]{{\color{delcol}\dellinks\sout{#1}}} \newenvironment{addblock}{\color{addcol}\addlinks}{} \else \newcommand{\add}[1]{#1} \newcommand{\del}[1]{} \newenvironment{addblock}{}{} \fi \newtheorem{theorem}{Theorem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \theoremstyle{definition} \newtheorem{example}[theorem]{Example} \newtheorem{remark}[theorem]{Remark} \newtheorem{definition}[theorem]{Definition} \newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\PAF}{\mathrm{PAF}} \newcommand{\PSD}{\mathrm{PSD}} \newcommand{\one}{\mathbf{1}} \newcommand{\T}{\mathsf{T}} \newcommand{\pf}{\sum\nolimits_f} \DeclareMathOperator{\supp}{supp} \setlength{\emergencystretch}{2em} \begin{document} \title[Hadamard matrices of twelve orders below 2000]{Hadamard matrices of orders 668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948 and 1964} \author{Claude} \ifredline\address{\del{Anthropic}}\fi \date{\del{October }\add{November }2026} \subjclass[2020]{Primary 05B20; Secondary 05B10, 05-08, 05-11} \keywords{Hadamard matrix, supplementary difference sets, divisible difference family, Goethals--Seidel array, bordered array, multiplier group, compression of sequences, meet-in-the-middle search\add{, Miyamoto's construction, M-structures, T-matrices}} \thanks{Preprint; not yet peer-reviewed.} \begin{abstract} We construct Hadamard matrices of orders 668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948 and 1964, the twelve multiples of 4 below 2000 for which none was known, and a second, inequivalent matrix of order 668. Five come from the Goethals--Seidel array with circulant blocks invariant under a multiplier group, four from the width-4 bordered array of Wallis and Whiteman, and four from bordered Goethals--Seidel arrays of widths 12, 20 and 28 whose corner is itself a Hadamard matrix. To our knowledge borders wider than 4 with a Hadamard corner are new\add{; the first two arrays are classical}. \add{The four matrices with a border of width 4, of orders 668, 716, 1676 and 1772, are instances of a theorem of Miyamoto on Hadamard matrices of order $8m+4$, which Seberry and Yamada restated with their M-structures; the matrices to which the theorem applies were found here by computer search. The searches differ greatly in size. Those for the wider borders formed at most about $2^{44}$ pairs of candidate blocks. Those for orders 716 and 668 with a border of width 4, made with no multiplier group, formed about $2^{66}$ and $2^{59}$, and these two matrices, that of order 716 above all, are results of large-scale computation more than of a new construction.} \del{Consequently }\add{With these matrices,} a Hadamard matrix of order $n$ is known for every $n\equiv 0\pmod 4$ with $n\le 2000$. \end{abstract} \maketitle \ifredline \noindent{\small\textbf{Redline.} Changes from the original write-up are marked: text added is shown in \textcolor{addcol}{red}, and text deleted is shown \textcolor{delcol}{\sout{struck through}}.}\par\medskip \fi \section{Introduction} \subsection{The result}\label{sec:result} A \emph{Hadamard matrix} of order $n$ is an $n\times n$ matrix $H$ with entries $\pm1$ and $HH^{\T}=nI_n$ \add{\cite{Had93}}. The Hadamard conjecture\add{, usually attributed to Paley \cite{r36},} is that one exists for every $n$ divisible by $4$. By 2014 the multiples of $4$ up to $2000$ for which none was known were $4v$ for the twelve primes $v=167$, $179$, $223$, $283$, $311$, $347$, $359$, $419$, $443$, $479$, $487$, $491$ \cite{r3,r6,r11,r35,r39,r40}.\footnote{See \S\ref{sec:related} on a construction method that may bear on orders 892, 1132 and 1948.} The list has not changed since then \cite{r3,r10}. Its smallest member, $668$, had been the least order in doubt since Kharaghani and Tayfeh-Rezaie constructed order $428$ in 2004 \cite{r21}. It was the subject of recent partial results \cite{r14,r37} and of a conjecture that would give a matrix of this order through a Legendre pair of length $333$ \cite[Conj.~1]{r22} \add{(\S\ref{sec:related})}. We give a Hadamard matrix of each of the twelve orders, and a second, inequivalent one of order $668$, labelled $668'$ below (Table~\ref{tab:thirteen}). \begin{theorem}[Twelve new orders]\label{thm:main} Hadamard matrices of orders $668$, $716$, $892$, $1132$, $1244$, $1388$, $1436$, $1676$, $1772$, $1916$, $1948$ and $1964$ exist. \end{theorem} The proof is a finite verification: Tables~A1--A2 determine one matrix of each order explicitly, through \eqref{eq:GS}, Proposition~\ref{prop:WW} and Theorem~\ref{thm:border}, and \cite{r52} gives them in machine-readable form (\S\ref{sec:check}). The printed matrices differ from the files released publicly earlier \add{\cite{ann}} only in the conventions stated in \S\ref{sec:public}, except that $668'$ is not among those files. Consequently a Hadamard matrix of order $n$ is known for every $n\equiv0\pmod 4$ with $n\le 2000$. \add{Egan, Kotsireas, London and \'O Cath\'ain \cite{EKLO} have analysed the structure of the twelve released matrices, working from the matrices alone. Their paper is also a survey of how Hadamard matrices are constructed and of the orders each method reaches, a far broader landscape than the present one; it counts $95$ orders up to $10\,000$ as still open when it appeared, the least being $2396=4\cdot 599$. Readers who want the context in which the twelve orders sit should start there.} \subsection{The main idea} \leavevmode\del{For four functions $a_1,\dots,a_4\colon G\to\{\pm1\}$ on a finite abelian group $G$, the blocks, write }\add{Let $G$ be a finite abelian group and let $a_1,\dots,a_4\colon G\to\{\pm1\}$ be four functions, the \emph{blocks}. Write} $\PSD(\chi)=\pf|\hat a_f(\chi)|^2$ for their total power spectrum, where $\hat a$ is the discrete Fourier transform on $G$ and the characters $\chi$ are the frequencies (\S\ref{sec:notation}). The Goethals--Seidel array $K$ of \S\ref{sec:GS} is a $\pm1$ matrix of order $4|G|$ with $KK^{\T}=I_4\otimes\pf A_fA_f^{\T}$, where $A_f=(a_f(y-x))_{x,y}$ is the group matrix of $a_f$, the $G$-circulant matrix it generates, and the eigenvalues of $\pf A_fA_f^{\T}$ are the numbers $\PSD(\chi)$. So $K$ is a Hadamard matrix exactly when the spectrum is flat: $\PSD(\chi)=4|G|$ for every character $\chi$. All twelve orders are $n=4v$ with $v$ prime, and the standard method takes $G=\Z_v$. A group of prime order has no proper non-trivial subgroup, hence no quotient to work through, and the structure the standard method imposes is invariance of each $a_f$ under a group $M$ of multipliers (maps $x\mapsto hx$ of $\Z_v$), of odd order $t>1$ dividing $v-1$. Invariance forces every row sum $r_f=\sum_x a_f(x)$ to be $\equiv\pm1\pmod{2t}$\add{, because the non-zero elements fall into $(v-1)/t$ orbits of size $t$, an even number of them}, and flatness at the trivial character forces $r_1^2+\dots+r_4^2=4v$. For five of the twelve primes the two demands are compatible for some $t$, and the known method succeeds (\S\ref{sec:circ}). For the other seven primes no row sums suitable for that method exist, and we use bordered Goethals--Seidel arrays: a Goethals--Seidel array over an abelian group $G$ of order slightly less than $v$, surrounded by a border of $b$ rows and columns, its \emph{width} (Figure~\ref{fig:array}). We call its four blocks the \emph{core}. Unlike $v$, the order $|G|=v-b/4$ can have several small factors (\S\ref{sec:matrices}). \begin{figure}[ht] \[ \renewcommand{\arraystretch}{1.25} \begin{array}{c|c|cccc} & b & \multicolumn{4}{c}{4|G|}\\ \hline b & C & E^{(1)} & E^{(2)} & E^{(3)} & E^{(4)}\\ \hline & D^{(1)} & A_1 & A_2R & A_3R & A_4R\\ & D^{(2)} & -A_2R & A_1 & A_4^{\T}R & -A_3^{\T}R\\ 4|G| & D^{(3)} & -A_3R & -A_4^{\T}R & A_1 & A_2^{\T}R\\ & D^{(4)} & -A_4R & A_3^{\T}R & -A_2^{\T}R & A_1 \end{array} \] \[ \bigl(\,{+}^k\,{-}^k\,{+}^k\,{-}^k \;\big|\; {+}^k\,{-}^k\,{+}^k\,{-}^k \;\big|\; {-}^k\,{-}^k\,{+}^k\,{+}^k \;\big|\; {-}^k\,{+}^k\,{+}^k\,{-}^k\,\bigr) \] \caption{The bordered array $H$. Each row of $E$ and each column of $D$ has four segments, constant on the cosets of $N$ and summing to zero. Below: the first row of $E$ for $q=4$ with the frame of Table~\ref{tab:frame}; ${\pm}^k$ is $k$ equal signs, $k=41$ for order $668'$.}\label{fig:array} \end{figure} A border can repair a spectrum that is flat except at a few characters. Let $N$ be a subgroup of $G$ of even index $q$, take $b=4(q-1)$, so that $|G|=v-(q-1)$, and ask that $\PSD(\chi)=n$ at every character except the $q-1$ non-trivial characters of the quotient $Q=G/N$. If $\PSD$ has a common value at those, Parseval's identity forces that value to be $b$. \add{(Parseval gives $\sum_\chi\PSD(\chi)=4|G|^2$; with the value $n=4|G|+b$ at the other $|G|-q+1$ characters, a common value $c$ at these $q-1$ must satisfy $(q-1)(n-c)=|G|\,b=4(q-1)|G|$, that is, $c=n-4|G|=b$.)} Then $nI-KK^{\T}$ is $4|G|$ times the orthogonal projection onto a space $V$ of dimension $b$: the vectors each of whose four segments is constant on the cosets of $N$ and has zero sum. The $b$ columns of $D$ must form an orthogonal basis of $V$ consisting of $\pm1$ vectors, and so must the $b$ rows of $E$. The corner is then forced, $C=-EK^{\T}D/(4|G|)$, and it satisfies $CC^{\T}=bI$ automatically. Once such $D$ and $E$ are chosen, the one requirement that can fail is that the entries of $C$ be $\pm1$. Whether a core can be so bordered depends only on its sums over the cosets of $N$, which are $4q$ integers; so bordering is a finite problem on the small group $Q$, separate from the search for the core. For quotient groups of order $4$, $6$ and $8$ it always can, after at most translating, inverting, negating or permuting the blocks of the core; we verified this by computer (Proposition~\ref{prop:frames}). These are the widths $b=12,20,28$. The case $q=2$, width $4$, is classical. \add{Throughout, a \emph{width-$b$ matrix} is a Hadamard matrix assembled from a core and a border of width $b$, and a \emph{width-$b$ core} is a core for such a border; the width is that of the border, not of the matrix or the core. This follows the usage of \cite{EKLO}, whose $b$ is also the border width; in the phrase \emph{two circulant cores} of \cite{r4,r23} each block is a core, whereas here the core is all four blocks together.} What is gained is freedom in the choice of $G$. For $v=479$, for example, $v-1=2\cdot239$ admits no usable multiplier group, but $v-3=476=2^2\cdot7\cdot17$, and $G=\Z_2^2\times\Z_{119}$ has a group of automorphisms of order $12$ and quotients of orders $68$ and $28$ through which the search can be organised (\S\ref{sec:1916}). For order $668$ we give both a width-4 and a width-12 matrix: the second search was far smaller than the first (Table~\ref{tab:thirteen}). \add{It was small because it looked only for cores with three fibres of a mixed type (\S\ref{sec:668b}), the fewest possible (Lemma~\ref{lem:defects}); with so few, the core condition splits into four nearly independent systems.} \subsection{Which order uses which method}\label{sec:which} In every search we fix a \emph{cell}: the group $G$, a group $M$ of its automorphisms (the \emph{multiplier group}) under which every block is required to be invariant, and, for a bordered array (\S\ref{sec:wide}), a subgroup $N\le G$. A block is then one sign per $M$-orbit, and \eqref{eq:flat}, or for bordered arrays its analogue \eqref{eq:WW} or \eqref{eq:core}, is one quadratic equation per orbit of $\langle M,-1\rangle$ on the non-zero elements of $G$. The columns \emph{signs} and \emph{eqs} of Table~\ref{tab:thirteen} count the signs of all four blocks and the equations. For example, the row of order $1916$ describes the cell with $G=\Z_2^2\times\Z_{119}$, a multiplier group of order $12$ and $N=\Z_{119}$, which has $184$ signs and $29$ equations. The row-sum condition of \S1.2 can be met for $v=223,283,311,487,491$, with some odd $t>1$ dividing $v-1$, and for none of the other seven primes. For $v=167,179,347,359,479$, $v-1$ is twice a prime and the only odd $t>1$ is $(v-1)/2$. For this $t$ the possible row sums are $\pm1$, $\pm(v-2)$ and $\pm v$, and no four of their squares sum to $4v$. For $v=419,443$ there are proper odd divisors but no suitable row sums. A bordered cell is most readily searched by compression (\S\ref{sec:compression}) when $|G|=v-(q-1)$ has several small factors, giving $G$ small quotients and automorphisms of small order fixing $N$. At width $4$ this is so for $v=419,443$, where $|G|=2\cdot11\cdot19$, $2\cdot13\cdot17$. For $v=167,179$ the group $\Z_2\times\Z_w$, $w=(v-1)/2$, has order twice a prime, and we searched it with no symmetry. For $v=347,359,479$ it would again have order twice a prime, and we used width $20$ for $347$, width $28$ for $359$ and width $12$ for $479$, where $|G|$ has several small factors (Table~\ref{tab:thirteen}). \setcounter{table}{0} \begin{table}[ht] \caption{The thirteen matrices. GS is the array \eqref{eq:GS} with circulant blocks on $\Z_v$ (\S\ref{sec:circcell}), and B$b$ is the bordered array of width $b$ over $G$, with $|G|=v-b/4$ (\S\S\ref{sec:width4}, \ref{sec:wide}). The columns \emph{signs} and \emph{eqs} are those of \S\ref{sec:which}. The column $\log_2$ ops gives $\log_2$ of the number of pair sums formed up to the first matrix (\S\ref{sec:matching}), or for $892$ in the complete matching; $\approx$ marks entries estimated from the list sizes. The last column gives the subsection of \S\ref{sec:matrices}, and $668'$ is the second, width-12 matrix of order $668$.}\label{tab:thirteen} \centering\footnotesize \setlength{\tabcolsep}{3.5pt} \begin{tabular}{rrlllrrrrll} \toprule order & $v$ & array & $G$ & $|G|$ & $|M|$ & signs & eqs & $\log_2$ ops & method & \S\\\midrule 668 & 167 & B4 & $\Z_2\times\Z_{83}$ & $166=2\cdot83$ & 1 & 664 & 83 & $\approx59$ & decoupling along $\Z_2$ & 5.2\\ $668'$ & 167 & B12 & $\Z_2^2\times\Z_{41}$ & $164=2^2\cdot41$ & 1 & 656 & 83 & $\approx44$ & decoupling along $\Z_2^2$ & 5.6\\ 716 & 179 & B4 & $\Z_2\times\Z_{89}$ & $178=2\cdot89$ & 1 & 712 & 89 & $\approx66$ & decoupling along $\Z_2$ & 5.2\\ 892 & 223 & GS & $\Z_{223}$ & 223 & 3 & 300 & 37 & 49 & method of \cite{r11} & 5.1\\ 1132 & 283 & GS & $\Z_{283}$ & 283 & 3 & 380 & 47 & 56 & method of \cite{r11} & 5.1\\ 1244 & 311 & GS & $\Z_{311}$ & 311 & 5 & 252 & 31 & $\approx34$ & method of \cite{r11} & 5.1\\ 1388 & 347 & B20 & $\Z_6\times\Z_{57}$ & $342=2\cdot3^2\cdot19$ & 6 & 280 & 39 & $\approx41$ & two quotients, sampled & 5.7\\ 1436 & 359 & B28 & $\Z_2^2\times\Z_8\times\Z_{11}$ & $352=2^5\cdot11$ & 5 & 384 & 51 & $\approx40$ & two quotients, nested & 5.8\\ 1676 & 419 & B4 & $\Z_2\times\Z_{209}$ & $418=2\cdot11\cdot19$ & 15 & 168 & 21 & 42 & decoupling along $\Z_2$, under $M$ & 5.3\\ 1772 & 443 & B4 & $\Z_2\times\Z_{221}$ & $442=2\cdot13\cdot17$ & 12 & 200 & 29 & $\approx36$ & two quotients & 5.4\\ 1916 & 479 & B12 & $\Z_2^2\times\Z_{119}$ & $476=2^2\cdot7\cdot17$ & 12 & 184 & 29 & $\approx35$ & two quotients & 5.5\\ 1948 & 487 & GS & $\Z_{487}$ & 487 & 9 & 220 & 27 & $\approx38$ & method of \cite{r11} & 5.1\\ 1964 & 491 & GS & $\Z_{491}$ & 491 & 7 & 284 & 35 & 55 & method of \cite{r11} & 5.1\\\bottomrule \end{tabular} \end{table} \subsection{Contributions}\label{sec:contributions} To our knowledge each of the following \del{three}\add{two} things is new: bordered Goethals--Seidel arrays wider than $4$ with a Hadamard corner (Theorem~\ref{thm:border})\add{, and}\del{; the decoupling of the width-4 condition on $\Z_2\times\Z_w$ into two searches without common variables (\mbox{\S\ref{sec:decoupling}}); and} compression \cite{r12,r32,r42} organised as lifting through two quotients at once for four blocks under a multiplier group (\S\ref{sec:lifting}). \add{Egan, Kotsireas, London and \'O Cath\'ain recovered the construction of Theorem~\ref{thm:border} from the released matrices and state it as \cite[Thm.~7]{EKLO}; it has since given further orders \cite[\S4]{EKLO}.} \add{The change of variables we used for the width-4 cores of orders $668$, $716$ and $1676$ (\S\ref{sec:decoupling}) is not new. It replaces the two halves $a(0,\cdot)$ and $a(1,\cdot)$ of each block on $\Z_2\times\Z_w$ by their half-sum $S$ and half-difference $T$, which are $(0,\pm1)$-functions on $\Z_w$ with complementary supports, and it turns condition \eqref{eq:WW} into one system on the half-sums and one on the half-differences; once the supports are fixed, the two systems have no variable in common. This is the decomposition on which Miyamoto's main theorem \cite{r33} rests, and the two systems are the two conditions of that theorem. All four of our width-4 matrices are instances of the theorem, that of order $1772$ included, although its core was found by another method (\S\ref{sec:decoupling}). Miyamoto's own applications of his theorem take the two parts from conference matrices and other auxiliary matrices; ours come from searches (\S\ref{sec:related}). Seberry and Yamada restated his theorem in terms of their M-structures \cite{SY90,r39}, and the same passage to half-sums and half-differences takes base sequences to T-sequences \cite{r39,r44}. What we add there is computational: a necessary condition on the supports, and an enumeration of the support systems that meet it. For the second matrix of order $668$ we used the analogous change of variables along $\Z_2^2$, which has four parts in place of two and to which Miyamoto's theorem does not apply (\S\S\ref{sec:decoupling}, \ref{sec:668b}).} The Goethals--Seidel array with blocks invariant under a multiplier group, searched with candidate lists and matching, and the width-4 array are classical (\S\ref{sec:related}). \add{The thirteen searches differ enormously in cost, and this bears on what each matrix shows (\S\ref{sec:cost}, Appendix~D). The matrices from wide borders, the construction that is new here, were cheap to find: at most about $150$ core-hours each by our estimate. Four matrices came from large matchings on classical arrays: those of orders $1132$ and $1964$ by the known circulant method, and those of orders $668$ and $716$ on the width-4 array with no symmetry. For the last two, the decomposition, the feasibility condition and the restriction to interval-like supports reduce a choice among about $2^{162}$ and $2^{174}$ sequences per block to matchings of about $2^{59}$ and $2^{66}$ pair sums, and these matchings were then carried out by computation. The count roughly doubles with each unit of $w$, so the approach does not extend far. By our estimate the counted operations of the order-$716$ search alone cost $2\cdot10^{7}$ to $8\cdot10^{7}$ core-hours, most of the computation counted in this paper (more than nine tenths at the counts of Table~\ref{tab:thirteen}) and about US\$$1$--$4$ million at current list prices for rented processors; the nine cheapest searches together cost under US\$$300$. The matrix of order $716$ is therefore a result of computation on a scale open to few, more than of a new construction; the width-4 matrix of order $668$ came from a search of about the cost of those for orders $1132$ and $1964$, and owes more to that search than to a new construction.} The matrices are printed in Appendix~A and can be checked directly (\S\ref{sec:check}). Proposition~\ref{prop:frames} and the counts of Appendix~C rest on enumerations by computer, and Theorem~\ref{thm:main} does not use them. An off-the-shelf constraint solver was used in preliminary screening (compare \cite{r2}); neither it nor learned generators \cite{r48} produced any of the objects printed here. \emph{How the work was done.} The constructions and searches reported here were carried out by Claude, an AI system made by Anthropic. The constructions, proofs, code and the text of this paper are the system's. \add{The text was afterwards edited by Claude working with Erisa Hasani, Abhinav Nellore and Rachel Ward, who proposed corrections of attribution and of emphasis. That editing was done from the text and the printed data, without the search programs or their logs. The re-run of the recipes on the printed tables reported in \S\ref{sec:recipes}, the timing program and the estimates of Appendix~D date from it, which is why the appendix estimates the cost of the searches and cannot report the hardware and time they used.} \subsection{Notation}\label{sec:notation} Throughout, $G$ is a finite abelian group written additively, and vectors and matrices are indexed by its elements; $\Z_v=\{0,1,\dots,v-1\}$, so indices start from $0$. A function $a\colon G\to\R$ (below with values in $\{0,\pm1\}$ or in $\Z$) is a vector in $\R^G$, with $\langle a,a'\rangle=\sum_x a(x)a'(x)$; $\one$ is the all-ones vector, $\one_S$ the indicator vector of a set $S$, and $1\{P\}$ is $1$ if the statement $P$ holds and $0$ otherwise. The characters $\chi$ of $G$ are the frequencies, $\hat a(\chi)=\sum_x a(x)\chi(x)$ is the un-normalised discrete Fourier transform of $a$, and $\chi=1$ is the trivial character, the zero frequency; so $\hat a(1)=\langle a,\one\rangle$ is the row sum of $a$. The group matrix $A=(a(y-x))_{x,y}$ is the $G$-circulant matrix generated by $a$ \add{(a group-developed matrix in the terminology of \cite{Horadam,dLF})}; for $G=\Z_v$ it is the circulant matrix with first row $a$. Every character is an eigenvector, $A\chi=\hat a(\chi)\chi$ and $A^{\T}\chi=\overline{\hat a(\chi)}\,\chi$. So $AA^{\T}$ has the eigenvalues $|\hat a(\chi)|^2$, and it is the group matrix of the periodic autocorrelation $\PAF_a(s)=\langle a,a(\cdot+s)\rangle$, the inner product of $a$ with its shift by $s$. Conditions on $\pf\PAF_{a_f}$ and on the power spectrum $\PSD=\pf|\hat a_f|^2$ are therefore two forms of the same statement, and Parseval's identity is $\sum_\chi|\hat a(\chi)|^2=|G|\langle a,a\rangle$. The matrix $R$ is the reflection $(Ru)(x)=u(-x)$, and $RAR=A^{\T}$. For a subgroup $L$ of $G$, $L^\perp$ is the set of characters that are trivial on $L$, that is the characters of $G/L$ pulled back to $G$ (composed with the quotient map). Below, $N$ is always a subgroup, not a dimension, and $k=|N|$. Appendix~B is a glossary. \section{Goethals--Seidel arrays and the circulant method}\label{sec:GS} For $a_1,\dots,a_4\colon G\to\{\pm1\}$, with the group matrices $A_f$ and the reflection $R$ of \S\ref{sec:notation}, the Goethals--Seidel array \cite{r18} (over an abelian group, \cite{r45}) is \begin{equation}\label{eq:GS} K(a_1,\dots,a_4)=\begin{pmatrix} A_1 & A_2R & A_3R & A_4R\\ -A_2R & A_1 & A_4^{\T}R & -A_3^{\T}R\\ -A_3R & -A_4^{\T}R & A_1 & A_2^{\T}R\\ -A_4R & A_3^{\T}R & -A_2^{\T}R & A_1 \end{pmatrix},\qquad KK^{\T}=K^{\T}K=I_4\otimes\pf A_fA_f^{\T}, \end{equation} and $\pf A_fA_f^{\T}$ is the group matrix of $\pf\PAF_{a_f}$ (\S\ref{sec:notation}). The identity holds because group matrices of an abelian group commute and $RA_fR=A_f^{\T}$: each $A_fR$ and $A_f^{\T}R$ is symmetric, and the off-diagonal blocks of $KK^{\T}$ cancel in pairs. Hence $K$ is a Hadamard matrix of order $4|G|$ exactly when \begin{equation}\label{eq:flat} \pf\PAF_{a_f}(s)=0\quad(s\ne0),\qquad\text{equivalently}\qquad \pf|\hat a_f(\chi)|^2=4|G|\ \text{for every }\chi, \end{equation} i.e.\ when the sets $X_f=\{a_f=-1\}$ are $4$-$\{|G|;|X_1|,\dots,|X_4|;\lambda\}$ supplementary difference sets with $\lambda=\pf|X_f|-|G|$. The row sums $r_f=\hat a_f(1)$ then satisfy $\pf r_f^2=4|G|$. \subsection{Circulant blocks constant on the cosets of a multiplier group}\label{sec:circcell} With $G=\Z_v$ for a prime $v$ and no border, \eqref{eq:GS} is the setting of {\DJ}okovi\'c \cite{r8} and of {\DJ}okovi\'c, Golubitsky and Kotsireas \cite{r11} (orders 764 and 1004 among others), whose cell we use unchanged\add{; {\DJ}okovi\'c's order 956 \cite{Dj94} is of the same kind}. \add{In the classical theory a multiplier $t$ of a difference set $D$ may move it to a translate, $tD=D+g$ \cite{BJL}; here, as in \cite{EKLO}, invariance $tD=D$ is required.} Let $t>1$ be an odd divisor of $v-1$, put $2m=(v-1)/t$, and let $g$ be a primitive root modulo $v$. The cosets of the subgroup $M$ of order $t$ (so $t=|M|$) in $\Z_v^*$ are \[ O_j=\{g^{j+2mu}:0\le u #include #include #include #include #include #ifdef _OPENMP #include #endif #if defined(__AVX512BW__) #include #define HAVE_AVX512 1 #else #define HAVE_AVX512 0 #endif #define W 83 #define H 41 /* shifts 1..41 */ #define VB 64 /* bytes per int8 vector (41 used) */ static double now(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec + 1e-9 * t.tv_nsec; } static uint64_t rng_s[4]; static inline uint64_t rotl(uint64_t x, int k) { return (x << k) | (x >> (64 - k)); } static uint64_t rnd(void) { /* xoshiro256** */ uint64_t r = rotl(rng_s[1] * 5, 7) * 9, t = rng_s[1] << 17; rng_s[2] ^= rng_s[0]; rng_s[3] ^= rng_s[1]; rng_s[1] ^= rng_s[2]; rng_s[0] ^= rng_s[3]; rng_s[2] ^= t; rng_s[3] = rotl(rng_s[3], 45); return r; } /* supports of the order-668 system: sizes (44,39,41,43), types e61; h19 e41; h2; e60 */ static int supp[4][W], supp_n[4]; static const int sigma[4] = {10, 3, 3, 7}; static void make_supports(void) { int L[4] = {43, 39, 42, 42}; int hole[4] = {-1, 19, 2, -1}, extra[4] = {61, 41, -1, 60}; for (int f = 0; f < 4; f++) { int n = 0; for (int y = 0; y < L[f]; y++) if (y != hole[f]) supp[f][n++] = y; if (extra[f] >= 0) supp[f][n++] = extra[f]; supp_n[f] = n; } } /* a uniformly random sign vector on W_f with sum sigma_f, and its PAF at shifts 1..41 */ static void random_p(int f, int8_t *out) { int n = supp_n[f], plus = (n + sigma[f]) / 2, T[W]; int idx[W]; memset(T, 0, sizeof T); for (int i = 0; i < n; i++) idx[i] = supp[f][i]; for (int i = 0; i < n; i++) { /* Fisher-Yates */ int j = i + (int)(rnd() % (uint64_t)(n - i)), t = idx[i]; idx[i] = idx[j]; idx[j] = t; T[idx[i]] = (i < plus) ? 1 : -1; } memset(out, 0, VB); for (int s = 1; s <= H; s++) { int acc = 0; for (int y = 0; y < W; y++) acc += T[y] * T[(y + s) % W]; out[s - 1] = (int8_t)acc; } } /* 64-bit hash of nq 64-bit words (multiply-fold, in the style of wyhash) */ static inline uint64_t mum(uint64_t a, uint64_t b) { __uint128_t m = (__uint128_t)a * b; return (uint64_t)m ^ (uint64_t)(m >> 64); } static inline uint64_t hash_words(const uint64_t *q, int nq) { static const uint64_t K[12] = { 0xA0761D6478BD642Full, 0xE7037ED1A0B428DBull, 0x8EBC6AF09C88C6E3ull, 0x589965CC75374CC3ull, 0x1D8E4E27C47D124Full, 0xEB44ACCAB455D165ull, 0x9E3779B97F4A7C15ull, 0xC2B2AE3D27D4EB4Full, 0x165667B19E3779F9ull, 0x27D4EB2F165667C5ull, 0xD6E8FEB86659FD93ull, 0xFF51AFD7ED558CCDull}; uint64_t h = 0; for (int i = 0; i + 1 < nq; i += 2) /* independent multiplies: no serial chain */ h ^= mum(q[i] ^ K[i], q[i + 1] ^ K[i + 1]); h ^= h >> 29; return h | 1; /* never 0 (0 marks an empty slot) */ } /* ---------- filter kernel: count pairs passing |p1+p2| <= thr in every coordinate ---------- */ static uint64_t filter_block(const int8_t *A, int na, const int8_t *B, int nb, const uint8_t *thr, uint32_t *keep) { uint64_t cnt = 0; #if HAVE_AVX512 __m512i t = _mm512_loadu_si512(thr), t2 = _mm512_add_epi8(t, t); for (int i = 0; i < na; i++) { __m512i a = _mm512_add_epi8(_mm512_loadu_si512(A + (size_t)i * VB), t); /* a + thr */ for (int j = 0; j < nb; j++) { __m512i s = _mm512_add_epi8(a, _mm512_loadu_si512(B + (size_t)j * VB)); /* pass iff 0 <= p1+p2+thr <= 2 thr in every coordinate; survivors are appended without a branch (the slot is always written, the count advances on a pass) */ keep[cnt] = ((uint32_t)i << 16) | (uint32_t)j; cnt += (_mm512_cmpgt_epu8_mask(s, t2) == 0); } } #else uint8_t thr2[VB]; for (int k = 0; k < VB; k++) thr2[k] = (uint8_t)(2 * thr[k]); for (int i = 0; i < na; i++) { const int8_t *a = A + (size_t)i * VB; for (int j = 0; j < nb; j++) { const int8_t *b = B + (size_t)j * VB; uint8_t bad = 0; /* byte accumulator: vectorises (NEON, AVX2) */ for (int k = 0; k < VB; k++) { uint8_t s = (uint8_t)((uint8_t)a[k] + (uint8_t)b[k] + thr[k]); bad |= (uint8_t)(s > thr2[k]); } keep[cnt] = ((uint32_t)i << 16) | (uint32_t)j; cnt += !bad; } } #endif return cnt; } /* ---------- hash kernels ---------- */ /* int8 vectors, 48 bytes hashed (41 used) */ static inline uint64_t sum_hash8(const int8_t *a, const int8_t *b) { uint64_t q[6]; #if HAVE_AVX512 __m512i s = _mm512_add_epi8(_mm512_loadu_si512(a), _mm512_loadu_si512(b)); uint64_t buf[8]; _mm512_storeu_si512(buf, s); memcpy(q, buf, 48); #else int8_t s[48]; for (int k = 0; k < 48; k++) s[k] = (int8_t)(a[k] + b[k]); memcpy(q, s, 48); #endif return hash_words(q, 6); } /* int16 vectors, 48 coordinates = 96 bytes */ static inline uint64_t sum_hash16(const int16_t *a, const int16_t *b) { uint64_t q[12]; #if HAVE_AVX512 __m512i s0 = _mm512_add_epi16(_mm512_loadu_si512(a), _mm512_loadu_si512(b)); __m256i s1 = _mm256_add_epi16(_mm256_loadu_si256((const __m256i *)(a + 32)), _mm256_loadu_si256((const __m256i *)(b + 32))); uint64_t buf[12]; _mm512_storeu_si512(buf, s0); _mm256_storeu_si256((__m256i *)(buf + 8), s1); memcpy(q, buf, 96); #else int16_t s[48]; for (int k = 0; k < 48; k++) s[k] = (int16_t)(a[k] + b[k]); memcpy(q, s, 96); #endif return hash_words(q, 12); } static inline void tab_insert(uint64_t *tab, uint64_t mask, uint64_t h) { uint64_t i = (h >> 7) & mask; while (tab[i] != 0 && tab[i] != h) i = (i + 1) & mask; tab[i] = h; } static inline int tab_probe(const uint64_t *tab, uint64_t mask, uint64_t h) { uint64_t i = (h >> 7) & mask; while (tab[i] != 0) { if (tab[i] == h) return 1; i = (i + 1) & mask; } return 0; } /* bucketed table: one 64-byte line of 8 keys per bucket plus a fill count; an insert appends to its bucket and a probe compares the key with the whole line, both without branches */ static inline void bkt_insert(uint64_t *tab, uint8_t *fill, uint64_t bmask, uint64_t h) { uint64_t b = (h >> 7) & bmask; unsigned c = fill[b]; tab[b * 8 + (c & 7)] = h; fill[b] = (uint8_t)(c + (c < 8)); /* a ninth key overwrites (rare) */ } static inline int bkt_probe(const uint64_t *tab, uint64_t bmask, uint64_t h) { uint64_t b = (h >> 7) & bmask; #if HAVE_AVX512 return _mm512_cmpeq_epi64_mask(_mm512_load_si512(tab + b * 8), _mm512_set1_epi64((long long)h)) != 0; #else int hit = 0; for (int k = 0; k < 8; k++) hit |= (tab[b * 8 + k] == h); return hit; #endif } int main(int argc, char **argv) { double secs = (argc > 1) ? atof(argv[1]) : 2.0; /* seconds per measurement */ int nthreads = 1; #ifdef _OPENMP nthreads = omp_get_max_threads(); #endif make_supports(); rng_s[0] = 0x243F6A8885A308D3ull; rng_s[1] = 0x13198A2E03707344ull; rng_s[2] = 0xA4093822299F31D0ull; rng_s[3] = 0x082EFA98EC4E6C89ull; /* blocks of list 1 and list 2 that fit in the L1 cache together: 256 + 256 vectors = 32 KiB */ enum { NA = 256, NB = 256, NBLK = 64 }; int8_t *L1 = aligned_alloc(64, (size_t)NA * NBLK * VB), *L2 = aligned_alloc(64, (size_t)NB * NBLK * VB); for (int i = 0; i < NA * NBLK; i++) random_p(0, L1 + (size_t)i * VB); for (int i = 0; i < NB * NBLK; i++) random_p(1, L2 + (size_t)i * VB); /* int16 copies padded to 48 coordinates */ int16_t *M1 = aligned_alloc(64, (size_t)NA * NBLK * 96), *M2 = aligned_alloc(64, (size_t)NB * NBLK * 96); for (int i = 0; i < NA * NBLK; i++) for (int k = 0; k < 48; k++) { M1[(size_t)i * 48 + k] = (int16_t)(L1[(size_t)i * VB + (k % H)] * 3); M2[(size_t)i * 48 + k] = (int16_t)(L2[(size_t)i * VB + (k % H)] * 3); } printf("pairsum_bench: %s kernel, %d thread(s), %.1f s per measurement\n", HAVE_AVX512 ? "AVX-512BW" : "portable (compiler-vectorised)", nthreads, secs); /* overlap counts nu_1(s)+nu_2(s): variance of a coordinate of p1+p2 */ double sd[H]; for (int s = 1; s <= H; s++) { int nu = 0; for (int f = 0; f < 2; f++) { int in[W] = {0}; for (int i = 0; i < supp_n[f]; i++) in[supp[f][i]] = 1; for (int y = 0; y < W; y++) nu += in[y] && in[(y + s) % W]; } sd[s - 1] = sqrt((double)nu); } /* ---- filter kernel at several thresholds (c standard deviations per coordinate) ---- */ printf("\nfilter kernel (step (4) of section 5.2): pairs/s per thread, pass rate\n"); double cs[] = {0.0, 1.2, 1.5, 1.8, 2.2, 100.0}; for (unsigned ci = 0; ci < sizeof cs / sizeof cs[0]; ci++) { uint8_t thr[VB]; for (int k = 0; k < VB; k++) thr[k] = 63; /* padding and partition shifts: no test */ for (int k = 0; k < 35; k++) { /* shifts 1..35 are filtered */ double t = cs[ci] * sd[k]; thr[k] = (uint8_t)(t > 63 ? 63 : t); } uint64_t pairs = 0, pass = 0; double t0 = now(), el = 0; #pragma omp parallel reduction(+ : pairs, pass) { uint32_t *keep = malloc(sizeof(uint32_t) * (NA * NB + 1)); int tid = 0; #ifdef _OPENMP tid = omp_get_thread_num(); #endif for (int rep = 0; now() - t0 < secs; rep++) { int ba = (rep * 7 + tid * 13) % NBLK, bb = (rep * 11 + tid * 5) % NBLK; pass += filter_block(L1 + (size_t)ba * NA * VB, NA, L2 + (size_t)bb * NB * VB, NB, thr, keep); pairs += (uint64_t)NA * NB; } free(keep); } el = now() - t0; printf(" threshold %5.1f sd: %8.3e pairs/s per thread = %5.2f ns/pair, pass rate %.2e\n", cs[ci], pairs / el / nthreads, 1e9 * el * nthreads / pairs, (double)pass / pairs); } /* ---- hash kernels: every pair sum is hashed and inserted, then as many are probed ---- */ printf("\nhash kernel (section 4.1): every pair sum hashed and inserted or probed\n"); struct { const char *name; int log2slots; int wide; int bucketed; } cfg[] = { {"open addressing, int8 x48, table 1 MiB (in L2)", 17, 0, 0}, {"open addressing, int16 x48, table 1 MiB (in L2)", 17, 1, 0}, {"open addressing, int8 x48, table 1 GiB ", 27, 0, 0}, {"bucketed, int8 x48, table 1 MiB (in L2)", 17, 0, 1}, {"bucketed, int16 x48, table 1 MiB (in L2)", 17, 1, 1}, {"bucketed, int8 x48, table 1 GiB ", 27, 0, 1}, {"bucketed, int16 x48, table 1 GiB ", 27, 1, 1}, }; for (unsigned c = 0; c < sizeof cfg / sizeof cfg[0]; c++) { uint64_t slots = 1ull << cfg[c].log2slots, mask = slots - 1; uint64_t nb = slots / 8, bmask = nb - 1; /* buckets of 8 keys */ uint64_t per_part = cfg[c].bucketed ? slots / 4 : slots / 2; /* 2 keys per bucket, or load 1/2 */ uint64_t ops = 0, hits = 0; double t0 = now(), el; #pragma omp parallel reduction(+ : ops, hits) { uint64_t *tab = aligned_alloc(64, slots * 8); uint8_t *fill = malloc(nb); int tid = 0; #ifdef _OPENMP tid = omp_get_thread_num(); #endif for (int part = 0; now() - t0 < secs || part == 0; part++) { memset(tab, 0, slots * 8); memset(fill, 0, nb); /* insertion side: per_part pair sums from blocks of L1 x L2 */ uint64_t done = 0; for (int rep = 0; done < per_part; rep++) { int ba = (part * 3 + rep + tid) % NBLK, bb = (part * 5 + rep * 7 + (rep / NBLK) * 5 + tid * 3) % NBLK; for (int i = 0; i < NA && done < per_part; i++) for (int j = 0; j < NB && done < per_part; j++, done++) { uint64_t h = cfg[c].wide ? sum_hash16(M1 + ((size_t)ba * NA + i) * 48, M2 + ((size_t)bb * NB + j) * 48) : sum_hash8(L1 + ((size_t)ba * NA + i) * VB, L2 + ((size_t)bb * NB + j) * VB); if (cfg[c].bucketed) bkt_insert(tab, fill, bmask, h); else tab_insert(tab, mask, h); } } /* probe side: as many pair sums again (different blocks, so almost all miss) */ done = 0; for (int rep = 0; done < per_part; rep++) { int ba = (part * 3 + rep + tid + 31) % NBLK, bb = (part * 5 + rep * 7 + (rep / NBLK) * 5 + tid * 3 + 17) % NBLK; for (int i = 0; i < NA && done < per_part; i++) for (int j = 0; j < NB && done < per_part; j++, done++) { uint64_t h = cfg[c].wide ? sum_hash16(M2 + ((size_t)ba * NA + i) * 48, M1 + ((size_t)bb * NB + j) * 48) : sum_hash8(L2 + ((size_t)ba * NA + i) * VB, L1 + ((size_t)bb * NB + j) * VB); h ^= 0x5555555555555554ull; hits += cfg[c].bucketed ? bkt_probe(tab, bmask, h) : tab_probe(tab, mask, h); } } ops += 2 * per_part; } free(tab); free(fill); } el = now() - t0; printf(" %s: %8.3e pair sums/s per thread = %6.2f ns each (false hits %llu)\n", cfg[c].name, ops / el / nthreads, 1e9 * el * nthreads / ops, (unsigned long long)hits); } return 0; } %%%% end pairsum_bench.c