Introduction
The result
A Hadamard matrix of order n n n is an n × n n \times n n × n matrix H H H with entries ± 1 \pm1 ± 1 and H H T = n I n HH^{\mathrm{T}} = nI_n H H T = n I n [31 ] . The Hadamard conjecture, usually attributed to Paley [59 ] , is that one exists for every n n n divisible by 4. By 2014 the multiples of 4 up to 2000 for which none was known were 4 v 4v 4 v for the twelve primes v = 167 , 179 , 223 , 283 , 311 , 347 , 359 , 419 , 443 , 479 , 487 , 491 v = 167, 179, 223, 283, 311, 347, 359, 419, 443, 479, 487, 491 v = 167 , 179 , 223 , 283 , 311 , 347 , 359 , 419 , 443 , 479 , 487 , 491 [7 , 12 , 20 , 58 , 65 , 67 ] .1 The list has not changed since then [7 , 19 ] . Its smallest member, 668, had been the least order in doubt since Kharaghani and Tayfeh-Rezaie constructed order 428 in 2004 [36 ] . It was the subject of recent partial results [24 , 60 ] and of a conjecture that would give a matrix of this order through a Legendre pair of length 333 [38 Conj. 1] (§7). We give a Hadamard matrix of each of the twelve orders, and a second, inequivalent one of order 668, labelled 668′ below (Table 1).
Theorem 1 (Twelve new orders). Hadamard matrices of orders 668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948 and 1964 exist.
The proof is a finite verification: Tables A1–A2 determine one matrix of each order explicitly, through (1), Proposition 2 and Theorem 5, and [83 ] gives them in machine-readable form (§6). The printed matrices differ from the files released publicly earlier [1 ] only in the conventions stated in §6.2, except that 668′ is not among those files. Consequently a Hadamard matrix of order n n n is known for every n ≡ 0 ( m o d 4 ) n \equiv0 \pmod{4} n ≡ 0 ( mod 4 ) with n ≤ 2000 n \leq2000 n ≤ 2000 . Egan, Kotsireas, London and Ó Catháin [23 ] 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 ⋅ 599 = 4 \cdot599 = 4 ⋅ 599 . Readers who want the context in which the twelve orders sit should start there.
The main idea
Let G G G be a finite abelian group and let a 1 , … , a 4 : G → { ± 1 } a_1,\ldots,a_4:G\to\{\pm1\} a 1 , … , a 4 : G → { ± 1 } be four functions, the blocks . Write PSD ( χ ) = ∑ f ∣ a f ^ ( χ ) ∣ 2 \operatorname{PSD}(\chi)=\sum_f|\widehat{a_f}(\chi)|^2 PSD ( χ ) = ∑ f ∣ a f ( χ ) ∣ 2 for their total power spectrum, where a ^ \widehat{a} a is the discrete Fourier transform on G G G and the characters χ \chi χ are the frequencies (§ 1.5 ). The Goethals–Seidel array K K K of § 2 is a ± 1 \pm1 ± 1 matrix of order 4 ∣ G ∣ 4|G| 4∣ G ∣ with K K T = I 4 ⊗ ∑ f A f A f T KK^{\mathsf T}=I_4\otimes\sum_f A_fA_f^{\mathsf T} K K T = I 4 ⊗ ∑ f A f A f T , where A f = ( a f ( y − x ) ) x , y A_f=(a_f(y-x))_{x,y} A f = ( a f ( y − x ) ) x , y is the group matrix of a f a_f a f , the G G G -circulant matrix it generates, and the eigenvalues of ∑ f A f A f T \sum_f A_fA_f^{\mathsf T} ∑ f A f A f T are the numbers PSD ( χ ) \operatorname{PSD}(\chi) PSD ( χ ) . So K K K is a Hadamard matrix exactly when the spectrum is flat: PSD ( χ ) = 4 ∣ G ∣ \operatorname{PSD}(\chi)=4|G| PSD ( χ ) = 4∣ G ∣ for every character χ \chi χ .
All twelve orders are n = 4 v n=4v n = 4 v with v v v prime, and the standard method takes G = Z v G=\mathbb{Z}_v 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 a_f a f under a group M M M of multipliers (maps x ↦ h x x\mapsto hx x ↦ h x of Z v \mathbb{Z}_v Z v ), of odd order t > 1 t>1 t > 1 dividing v − 1 v-1 v − 1 . Invariance forces every row sum r f = ∑ x a f ( x ) r_f=\sum_xa_f(x) r f = ∑ x a f ( x ) to be ≡ ± 1 ( m o d 2 t ) \equiv\pm1\pmod{2t} ≡ ± 1 ( mod 2 t ) , because the non-zero elements fall into ( v − 1 ) / t (v-1)/t ( v − 1 ) / t orbits of size t t t , an even number of them, and flatness at the trivial character forces r 1 2 + ⋯ + r 4 2 = 4 v r_1^2+\cdots+r_4^2=4v r 1 2 + ⋯ + r 4 2 = 4 v . For five of the twelve primes the two demands are compatible for some t t t , and the known method succeeds (§ 5.1 ).
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 G G of order slightly less than v v v , surrounded by a border of b b b rows and columns, its width (Figure 1 ). We call its four blocks the core . Unlike v v v , the order ∣ G ∣ = v − b / 4 |G|=v-b/4 ∣ G ∣ = v − b /4 can have several small factors (§ 5 ).
Figure 1. The bordered array H H H . Each row of E E E and each column of D D D has four segments, constant on the cosets of N N N and summing to zero. Below: the first row of E E E for q = 4 q=4 q = 4 with the frame of Table 2; ± k \pm^k ± k is k k k equal signs, k = 41 k=41 k = 41 for order 668′.
A border can repair a spectrum that is flat except at a few characters. Let N N N be a subgroup of G G G of even index q q q , take b = 4 ( q − 1 ) b=4(q-1) b = 4 ( q − 1 ) , so that ∣ G ∣ = v − ( q − 1 ) |G|=v-(q-1) ∣ G ∣ = v − ( q − 1 ) , and ask that PSD ( χ ) = n \operatorname{PSD}(\chi)=n PSD ( χ ) = n at every character except the q − 1 q-1 q − 1 non-trivial characters of the quotient Q = G / N Q=G/N Q = G / N . If PSD \operatorname{PSD} PSD has a common value at those, Parseval’s identity forces that value to be b b b . (Parseval gives ∑ χ PSD ( χ ) = 4 ∣ G ∣ 2 \sum_\chi\operatorname{PSD}(\chi)=4|G|^2 ∑ χ PSD ( χ ) = 4∣ G ∣ 2 ; with the value n = 4 ∣ G ∣ + b n=4|G|+b n = 4∣ G ∣ + b at the other ∣ G ∣ − q + 1 |G|-q+1 ∣ G ∣ − q + 1 characters, a common value c c c at these q − 1 q-1 q − 1 must satisfy ( q − 1 ) ( n − c ) = ∣ G ∣ b = 4 ( q − 1 ) ∣ G ∣ (q-1)(n-c)=|G|b=4(q-1)|G| ( q − 1 ) ( n − c ) = ∣ G ∣ b = 4 ( q − 1 ) ∣ G ∣ , that is, c = n − 4 ∣ G ∣ = b c=n-4|G|=b c = n − 4∣ G ∣ = b .) Then n I − K K T nI-KK^{\mathsf T} n I − K K T is ∣ G ∣ |G| ∣ G ∣ times the orthogonal projection onto a space V V V of dimension b b b : the vectors each of whose four segments is constant on the cosets of N N N and has zero sum. The b b b columns of D D D must form an orthogonal basis of V V V consisting of ± 1 \pm1 ± 1 vectors, and so must the b b b rows of E E E . The corner is then forced, C = − E K T D / ( 4 ∣ G ∣ ) C=-EK^{\mathsf T}D/(4|G|) C = − E K T D / ( 4∣ G ∣ ) , and it satisfies C C T = b I CC^{\mathsf T}=bI C C T = b I automatically. Once such D D D and E E E are chosen, the one requirement that can fail is that the entries of C C C be ± 1 \pm1 ± 1 .
Whether a core can be so bordered depends only on its sums over the cosets of N N N , which are 4 q 4q 4 q integers; so bordering is a finite problem on the small group Q Q 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 8 ). These are the widths b = 12 , 20 , 28 b=12,20,28 b = 12 , 20 , 28 . The case q = 2 q=2 q = 2 , width 4, is classical. Throughout, a width-b b b matrix is a Hadamard matrix assembled from a core and a border of width b b b , and a width-b b 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 [23 ] , whose b b b is also the border width; in the phrase two circulant cores of [8 , 40 ] each block is a core, whereas here the core is all four blocks together.
What is gained is freedom in the choice of G G G . For v = 479 v=479 v = 479 , for example, v − 1 = 2 ⋅ 239 v-1=2\cdot239 v − 1 = 2 ⋅ 239 admits no usable multiplier group, but v − 3 = 476 = 2 2 ⋅ 7 ⋅ 17 v-3=476=2^2\cdot7\cdot17 v − 3 = 476 = 2 2 ⋅ 7 ⋅ 17 , and G = Z 2 2 × Z 119 G=\mathbb{Z}_2^2\times\mathbb{Z}_{119} G = Z 2 2 × Z 119 has a group of automorphisms of order 12 and quotients of orders 68 and 28 through which the search can be organised (§ 5.5 ). For order 668 we give both a width-4 and a width-12 matrix: the second search was far smaller than the first (Table 1). It was small because it looked only for cores with three fibres of a mixed type (§ 5.6 ), the fewest possible (Lemma 10 ); with so few, the core condition splits into four nearly independent systems.
Which order uses which method
In every search we fix a cell: the group G G G , a group M M M of its automorphisms (the multiplier group ) under which every block is required to be invariant, and, for a bordered array (§ 3.2 ), a subgroup N ≤ G N \le G N ≤ G . A block is then one sign per M M M -orbit, and (2), or for bordered arrays its analogue (3) or (4), is one quadratic equation per orbit of ⟨ M , − 1 ⟩ \langle M,-1\rangle ⟨ M , − 1 ⟩ on the non-zero elements of G G G . The columns signs and eqs of Table 1 count the signs of all four blocks and the equations. For example, the row of order 1916 describes the cell with G = Z 2 × Z 119 G = \mathbb{Z}_2 \times\mathbb{Z}_{119} G = Z 2 × Z 119 , a multiplier group of order 12 and N = Z 119 N = \mathbb{Z}_{119} N = Z 119 , which has 184 signs and 29 equations.
The row-sum condition of §1.2 can be met for v = 223 , 283 , 311 , 487 , 491 v = 223, 283, 311, 487, 491 v = 223 , 283 , 311 , 487 , 491 , with some odd t > 1 t > 1 t > 1 dividing v − 1 v - 1 v − 1 , and for none of the other seven primes. For v = 167 , 179 , 347 , 359 , 479 v = 167, 179, 347, 359, 479 v = 167 , 179 , 347 , 359 , 479 , v − 1 v - 1 v − 1 is twice a prime and the only odd t > 1 t > 1 t > 1 is ( v − 1 ) / 2 (v - 1)/2 ( v − 1 ) /2 . For this t t t the possible row sums are ± 1 \pm1 ± 1 , ± ( v − 2 ) \pm(v - 2) ± ( v − 2 ) and ± v \pm v ± v , and no four of their squares sum to 4 v 4v 4 v . For v = 419 , 443 v = 419, 443 v = 419 , 443 there are proper odd divisors but no suitable row sums. A bordered cell is most readily searched by compression (§ 4.2 ) when ∣ G ∣ = v − ( q − 1 ) |G| = v - (q - 1) ∣ G ∣ = v − ( q − 1 ) has several small factors, giving G G G small quotients and automorphisms of small order fixing N N N . At width 4 this is so for v = 419 , 443 v = 419, 443 v = 419 , 443 , where ∣ G ∣ = 2 ⋅ 11 ⋅ 19 |G| = 2 \cdot11 \cdot19 ∣ G ∣ = 2 ⋅ 11 ⋅ 19 , 2 ⋅ 13 ⋅ 17 2 \cdot13 \cdot17 2 ⋅ 13 ⋅ 17 . For v = 167 , 179 v = 167, 179 v = 167 , 179 the group Z 2 × Z w \mathbb{Z}_2 \times\mathbb{Z}_w Z 2 × Z w , w = ( v − 1 ) / 2 w = (v - 1)/2 w = ( v − 1 ) /2 , has order twice a prime, and we searched it with no symmetry. For v = 347 , 359 , 479 v = 347, 359, 479 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 ∣ |G| ∣ G ∣ has several small factors (Table 1).
Table 1 (PDF p. 3). The thirteen matrices. GS is the array (1) with circulant blocks on Z v \mathbb{Z}_v Z v (§ 2.1 ), and Bb is the bordered array of width b b b over G G G , with ∣ G ∣ = v − b / 4 |G| = v - b/4 ∣ G ∣ = v − b /4 (§§§ 3.1 , § 3.2 ). The columns signs and eqs are those of § 1.3 . The column log 2 \log_2 log 2 ops gives log 2 \log_2 log 2 of the number of pair sums formed up to the first matrix (§ 4.1 ), or for 892 in the complete matching; ≈ \approx ≈ marks entries estimated from the list sizes. The last column gives the subsection of § 5 , and 668′ is the second, width-12 matrix of order 668.
Contributions
To our knowledge each of the following two things is new: bordered Goethals–Seidel arrays wider than 4 with a Hadamard corner (Theorem 5 ), and compression [21 , 52 , 72 ] organised as lifting through two quotients at once for four blocks under a multiplier group (§ 4.4 ). Egan, Kotsireas, London and Ó Catháin recovered the construction of Theorem 5 from the released matrices and state it as [23 Thm. 7] ; it has since given further orders [23 §4] . The change of variables we used for the width-4 cores of orders 668, 716 and 1676 (§4.3) is not new. It replaces the two halves a ( 0 , ⋅ ) a(0,\cdot) a ( 0 , ⋅ ) and a ( 1 , ⋅ ) a(1,\cdot) a ( 1 , ⋅ ) of each block on Z 2 × Z w \mathbb{Z}_2 \times\mathbb{Z}_w Z 2 × Z w by their half-sum S S S and half-difference T T T , which are ( 0 , ± 1 ) (0,\pm1) ( 0 , ± 1 ) -functions on Z w \mathbb{Z}_w Z w with complementary supports, and it turns condition (3) 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 [56 ] 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 (§4.3). Miyamoto’s own applications of his theorem take the two parts from conference matrices and other auxiliary matrices; ours come from searches (§ 7 ). Seberry and Yamada restated his theorem in terms of their M-structures [64 , 65 ] , and the same passage to half-sums and half-differences takes base sequences to T-sequences [65 , 75 ] . 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 \mathbb{Z}_2^2 Z 2 2 , which has four parts in place of two and to which Miyamoto’s theorem does not apply (§§4.3, § 5.6 ). The Goethals–Seidel array with blocks invariant under a multiplier group, searched with candidate lists and matching, and the width-4 array are classical (§ 7 ).
The thirteen searches differ enormously in cost, and this bears on what each matrix shows (§ 6.3 , Appendix § 12 ). 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 2^{162} 2 162 and 2 174 2^{174} 2 174 sequences per block to matchings of about 2 59 2^{59} 2 59 and 2 66 2^{66} 2 66 pair sums, and these matchings were then carried out by computation. The count roughly doubles with each unit of w w w , so the approach does not extend far. By our estimate the counted operations of the order-716 search alone cost 2 ⋅ 10 7 2 \cdot10^7 2 ⋅ 1 0 7 to 8 ⋅ 10 7 8 \cdot10^7 8 ⋅ 1 0 7 core-hours, most of the computation counted in this paper (more than nine tenths at the counts of Table 1) 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 (§ 6 ). Proposition 8 and the counts of Appendix § 11 rest on enumerations by computer, and Theorem 1 does not use them.
An off-the-shelf constraint solver was used in preliminary screening (compare [6 ] ); neither it nor learned generators [79 ] produced any of the objects printed here.
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. 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 § 6.1 , the timing program and the estimates of Appendix § 12 date from it, which is why the appendix estimates the cost of the searches and cannot report the hardware and time they used.
Notation
1.5. Notation. Throughout, G G G is a finite abelian group written additively, and vectors and matrices are indexed by its elements; Z v = { 0 , 1 , … , v − 1 } \mathbb{Z}_v=\{0,1,\ldots,v-1\} Z v = { 0 , 1 , … , v − 1 } , so indices start from 0. A function a : G → R a\colon G \to\mathbb{R} a : G → R (below with values in { 0 , ± 1 } \{0,\pm1\} { 0 , ± 1 } or in Z \mathbb{Z} Z ) is a vector in R G \mathbb{R}^G R G , with ⟨ a , a ′ ⟩ = ∑ x a ( x ) a ′ ( x ) \langle a,a'\rangle=\sum_x a(x)a'(x) ⟨ a , a ′ ⟩ = ∑ x a ( x ) a ′ ( x ) ; 1 \mathbf{1} 1 is the all-ones vector, 1 S \mathbf{1}_S 1 S the indicator vector of a set S S S , and 1 { P } \mathbf{1}\{P\} 1 { P } is 1 if the statement P P P holds and 0 otherwise. The characters χ \chi χ of G G G are the frequencies, a ^ ( χ ) = ∑ x a ( x ) χ ( x ) \hat{a}(\chi)=\sum_x a(x)\chi(x) a ^ ( χ ) = ∑ x a ( x ) χ ( x ) is the un-normalised discrete Fourier transform of a a a , and χ = 1 \chi=1 χ = 1 is the trivial character, so zero frequency, so a ^ ( 1 ) = ⟨ a , 1 ⟩ \hat{a}(1)=\langle a,1\rangle a ^ ( 1 ) = ⟨ a , 1 ⟩ is the row sum of a a a .
The group matrix A = ( a ( y − x ) ) x , y A=(a(y-x))_{x,y} A = ( a ( y − x ) ) x , y is the G G G -circulant matrix generated by a a a (a group-developed matrix in the terminology of [33 , 13 ] ); for G = Z v G=\mathbb{Z}_v G = Z v it is the circulant matrix with first row a a a . Every character is an eigenvector, A χ = a ^ ( χ ) χ A\chi=\hat{a}(\chi)\chi A χ = a ^ ( χ ) χ and A T χ = a ^ ( χ ) χ A^{\mathsf{T}}\chi=\hat{a}(\chi)\chi A T χ = a ^ ( χ ) χ . So A A T AA^{\mathsf{T}} A A T has the eigenvalues ∣ a ^ ( χ ) ∣ 2 |\hat{a}(\chi)|^2 ∣ a ^ ( χ ) ∣ 2 , and it is the group matrix of the periodic autocorrelation PAF a ( s ) = ⟨ a , a ( ⋅ + s ) ⟩ \operatorname{PAF}_a(s)=\langle a,a(\cdot+s)\rangle PAF a ( s ) = ⟨ a , a ( ⋅ + s )⟩ , the inner product of a a a with its shift by s s s . Conditions on ∑ f PAF a f \sum_f \operatorname{PAF}_{a_f} ∑ f PAF a f and on the power spectrum ∑ f ∣ a ^ f ∣ 2 \sum_f |\hat{a}_f|^2 ∑ f ∣ a ^ f ∣ 2 are therefore two forms of the same statement, and Parseval’s identity is ∑ χ ∣ a ^ ( χ ) ∣ 2 = ∣ G ∣ ⟨ a , a ⟩ \sum_\chi|\hat{a}(\chi)|^2=|G|\langle a,a\rangle ∑ χ ∣ a ^ ( χ ) ∣ 2 = ∣ G ∣ ⟨ a , a ⟩ . The matrix R R R is the reflection ( R u ) ( x ) = u ( − x ) (Ru)(x)=u(-x) ( R u ) ( x ) = u ( − x ) , and R A R = A T RAR=A^{\mathsf{T}} R A R = A T . For a subgroup L L L of G G G , L ⊥ L^\perp L ⊥ is the set of characters that are trivial on L L L , that is the characters of G / L G/L G / L pulled back to G G G (composed with the quotient map). Below, N N N is always a subgroup, not a dimension, and k = ∣ N ∣ k=|N| k = ∣ N ∣ . Appendix § 10 is a glossary.
Goethals–Seidel arrays and the circulant method
For a 1 , … , a 4 : G → { ± 1 } a_1,\ldots,a_4:G\to\{\pm1\} a 1 , … , a 4 : G → { ± 1 } , with the group matrices A f A_f A f and the reflection R R R of § 1.5 , the Goethals–Seidel array [29 ] (over an abelian group, [76 ] ) is
K ( a 1 , … , a 4 ) = ( A 1 A 2 R A 3 R A 4 R − A 2 R A 1 A 4 T R − A 3 T R − A 3 R − A 4 T R A 1 A 2 T R − A 4 R A 3 T R − A 2 T R A 1 ) , K K T = K T K = I 4 ⊗ ∑ f A f A f T , (1) K(a_1,\ldots,a_4)=
\begin{pmatrix}
A_1 & A_2R & A_3R & A_4R\\
-A_2R & A_1 & A_4^{\mathsf T}R & -A_3^{\mathsf T}R\\
-A_3R & -A_4^{\mathsf T}R & A_1 & A_2^{\mathsf T}R\\
-A_4R & A_3^{\mathsf T}R & -A_2^{\mathsf T}R & A_1
\end{pmatrix},
\qquad
KK^{\mathsf T}=K^{\mathsf T}K=I_4\otimes\sum_f A_fA_f^{\mathsf T}, \tag*{(1)} K ( a 1 , … , a 4 ) = A 1 − A 2 R − A 3 R − A 4 R A 2 R A 1 − A 4 T R A 3 T R A 3 R A 4 T R A 1 − A 2 T R A 4 R − A 3 T R A 2 T R A 1 , K K T = K T K = I 4 ⊗ f ∑ A f A f T , (1)
and ∑ f A f A f T \sum_f A_fA_f^{\mathsf T} ∑ f A f A f T is the group matrix of ∑ f PAF a f \sum_f \operatorname{PAF}_{a_f} ∑ f PAF a f (§ 1.5 ). The identity holds because group matrices of an abelian group commute and R A f R = A f T RA_fR=A_f^{\mathsf T} R A f R = A f T : each A f R A_fR A f R and A f T R A_f^{\mathsf T}R A f T R is symmetric, and the off-diagonal blocks of K K T KK^{\mathsf T} K K T cancel in pairs. Hence K K K is a Hadamard matrix of order 4 ∣ G ∣ 4|G| 4∣ G ∣ exactly when
∑ f PAF a f ( s ) = 0 ( s ≠ 0 ) , equivalently ∑ f ∣ a ^ f ( χ ) ∣ 2 = 4 ∣ G ∣ for every χ , (2) \sum_f \operatorname{PAF}_{a_f}(s)=0\qquad(s\ne0),
\qquad\text{equivalently}\qquad
\sum_f|\widehat a_f(\chi)|^2=4|G|\ \text{ for every }\chi, \tag*{(2)} f ∑ PAF a f ( s ) = 0 ( s = 0 ) , equivalently f ∑ ∣ a f ( χ ) ∣ 2 = 4∣ G ∣ for every χ , (2)
i.e. when the sets X f = { a f = − 1 } X_f=\{a_f=-1\} X f = { a f = − 1 } are 4 4 4 -{ ∣ G ∣ ; ∣ X 1 ∣ , … , ∣ X 4 ∣ ; λ } \{|G|;|X_1|,\ldots,|X_4|;\lambda\} { ∣ G ∣ ; ∣ X 1 ∣ , … , ∣ X 4 ∣ ; λ } supplementary difference sets with λ = ∑ f ∣ X f ∣ − ∣ G ∣ \lambda=\sum_f|X_f|-|G| λ = ∑ f ∣ X f ∣ − ∣ G ∣ . The row sums r f = a ^ f ( 1 ) r_f=\widehat a_f(1) r f = a f ( 1 ) then satisfy ∑ f r f 2 = 4 ∣ G ∣ \sum_f r_f^2=4|G| ∑ f r f 2 = 4∣ G ∣ .
Circulant blocks constant on the cosets of a multiplier group
With G = Z v G=\mathbb{Z}_v G = Z v for a prime v v v and no border, (1) is the setting of Đoković [17 ] and of Đoković, Golubitsky and Kotsireas [20 ] (orders 764 and 1004 among others), whose cell we use unchanged; Đoković’s order 956 [16 ] is of the same kind. In the classical theory a multiplier t t t of a difference set D D D may move it to a translate, t D = D + g tD=D+g t D = D + g [5 ] ; here, as in [23 ] , invariance t D = D tD=D t D = D is required. Let t > 1 t>1 t > 1 be an odd divisor of v − 1 v-1 v − 1 , put 2 m = ( v − 1 ) / t 2m=(v-1)/t 2 m = ( v − 1 ) / t , and let g g g be a primitive root modulo v v v . The cosets of the subgroup M M M of order t t t (so t = ∣ M ∣ t=|M| t = ∣ M ∣ ) in Z v ∗ \mathbb{Z}_v^\ast Z v ∗ are
O j = { g j + 2 m u : 0 ≤ u < t } , j ∈ Z 2 m , O_j=\{g^{j+2mu}:0\le u<t\},\qquad j\in\mathbb{Z}_{2m}, O j = { g j + 2 m u : 0 ≤ u < t } , j ∈ Z 2 m ,
and − O j = O j + m -O_j=O_{j+m} − O j = O j + m . Here M M M acts on Z v \mathbb{Z}_v Z v by multiplication, and a sequence invariant under M M M is one that is constant on the orbits of M M M , namely on { 0 } \{0\} { 0 } and on each O j O_j O j . A sequence a ∈ { ± 1 } Z v a\in\{\pm1\}^{\mathbb{Z}_v} a ∈ { ± 1 } Z v constant on each coset is given by e 0 = a ( 0 ) e_0=a(0) e 0 = a ( 0 ) and ε = ( ε 0 , … , ε 2 m − 1 ) \varepsilon=(\varepsilon_0,\ldots,\varepsilon_{2m-1}) ε = ( ε 0 , … , ε 2 m − 1 ) , where ε j \varepsilon_j ε j is its value on O j O_j O j . Its row sum r = e 0 + t ∑ j ε j r=e_0+t\sum_j\varepsilon_j r = e 0 + t ∑ j ε j is therefore ≡ ± 1 ( m o d 2 t ) \equiv\pm1\pmod{2t} ≡ ± 1 ( mod 2 t ) , because ∑ j ε j \sum_j\varepsilon_j ∑ j ε j , a sum of 2 m 2m 2 m signs, is even. Its autocorrelation is constant on each union O i ∪ O i + m O_i\cup O_{i+m} O i ∪ O i + m , so (2) becomes m m m equations in the values PAF a ( i ) = PAF a ( g i ) \operatorname{PAF}_a(i)=\operatorname{PAF}_a(g^i) PAF a ( i ) = PAF a ( g i ) , 0 ≤ i < m 0\le i<m 0 ≤ i < m . The cell thus has 4 ( 2 m + 1 ) 4(2m+1) 4 ( 2 m + 1 ) signs and m m m equations.
Bordered arrays
Width 4: the Wallis–Whiteman array
In the classical case the core lives on Z 2 w \mathbb{Z}_{2w} Z 2 w and is bordered by 4 rows and columns. Up to multiplying every block by the character of order 2 of Z 2 w \mathbb{Z}_{2w} Z 2 w , it is the case q = 2 q=2 q = 2 of Theorem 5 (Remark 7(ii)). The array is the Wallis–Whiteman array [77 Thm. 4.17] , so named in [47 , 48 ] : a Goethals–Seidel array (1) surrounded by a border of four rows and columns. Wallis and Whiteman gave such a border for four blocks of equal size on a group of odd order [76 Thm. 12] , and in the same paper adapted the unbordered Goethals–Seidel array from circulants to abelian groups [76 Thm. 11] . In this paper the name always means the bordered array.
Proposition 2 (Wallis–Whiteman). Let a 1 , … , a 4 ∈ { ± 1 } Z 2 w a_1,\ldots,a_4\in\{\pm1\}^{\mathbb{Z}_{2w}} a 1 , … , a 4 ∈ { ± 1 } Z 2 w satisfy
∑ f PAF a f ( s ) = − 4 ( s ≠ 0 ) , (3) \sum_f\operatorname{PAF}_{a_f}(s)=-4\qquad(s\ne0), \tag*{(3)} f ∑ PAF a f ( s ) = − 4 ( s = 0 ) , (3) ordered so that the row sums are ( 2 , 0 , 0 , 0 ) (2,0,0,0) ( 2 , 0 , 0 , 0 ) , and let 1 = ( 1 , … , 1 ) T ∈ Z 2 w \mathbf{1}=(1,\ldots,1)^{\mathsf T}\in\mathbb{Z}^{2w} 1 = ( 1 , … , 1 ) T ∈ Z 2 w . Then
( C 0 E 0 ⊗ 1 T D 0 ⊗ 1 K ( a 1 , … , a 4 ) ) , C 0 = ( − + + − + + + − + + + − − − − − ) , D 0 = ( + + + − − − + − − + + − + − − − ) , E 0 = − 1 2 C 0 D 0 T , \left(
\begin{array}{cc}
C_0 & E_0\otimes\mathbf{1}^{\mathsf T}\\
D_0\otimes\mathbf{1} & K(a_1,\ldots,a_4)
\end{array}
\right),
\qquad
C_0=
\begin{pmatrix}
- & + & + & -\\
+ & + & + & -\\
+ & + & + & -\\
- & - & - & -
\end{pmatrix},
\qquad
D_0=
\begin{pmatrix}
+ & + & + & -\\
- & - & + & -\\
- & + & + & -\\
+ & - & - & -
\end{pmatrix},
\qquad
E_0=-\frac{1}{2}C_0D_0^{\mathsf T}, ( C 0 D 0 ⊗ 1 E 0 ⊗ 1 T K ( a 1 , … , a 4 ) ) , C 0 = − + + − + + + − + + + − − − − − , D 0 = + − − + + − + − + + + − − − − − , E 0 = − 2 1 C 0 D 0 T , is a Hadamard matrix of order 4 ( 2 w + 1 ) 4(2w+1) 4 ( 2 w + 1 ) .
Summing (3) over s s s gives ∑ f r f 2 = 8 w − 4 ( 2 w − 1 ) = 4 \sum_f r_f^2=8w-4(2w-1)=4 ∑ f r f 2 = 8 w − 4 ( 2 w − 1 ) = 4 , since ∑ s PAF a f ( s ) = r f 2 \sum_s\operatorname{PAF}_{a_f}(s)=r_f^2 ∑ s PAF a f ( s ) = r f 2 and PAF a f ( 0 ) = 2 w \operatorname{PAF}_{a_f}(0)=2w PAF a f ( 0 ) = 2 w . Each r f r_f r f is even, being a sum of 2 w 2w 2 w signs, so the row sums are ( ± 2 , 0 , 0 , 0 ) (\pm2,0,0,0) ( ± 2 , 0 , 0 , 0 ) in some order, and reordering the blocks and negating one if necessary gives ( 2 , 0 , 0 , 0 ) (2,0,0,0) ( 2 , 0 , 0 , 0 ) . The matrix E 0 E_0 E 0 has the rows ( − , − , − , + ) (-,-,-,+) ( − , − , − , + ) , ( − , − , + , − ) (-,-,+,-) ( − , − , + , − ) , ( − , + , − , − ) (-,+,-,-) ( − , + , − , − ) and ( + , − , − , − ) (+,-,-,-) ( + , − , − , − ) .
Proof of Proposition 2. By (3) , ∑ f A f A f T \sum_f A_f A_f^{\mathsf{T}} ∑ f A f A f T is the group matrix of the function equal to 8 w 8w 8 w at 0 and − 4 -4 − 4 elsewhere, that is n I − 411 T nI-4\mathbf{1}\mathbf{1}^{\mathsf{T}} n I − 4 1 1 T with n = 8 w + 4 n=8w+4 n = 8 w + 4 . So K K K falls short of a Hadamard matrix only along the all-ones vector of each of its four block rows. Since A f 1 = A f T 1 = r f 1 A_f\mathbf{1}=A_f^{\mathsf{T}}\mathbf{1}=r_f\mathbf{1} A f 1 = A f T 1 = r f 1 and R 1 = 1 R\mathbf{1}=\mathbf{1} R 1 = 1 , we have K ( z ⊗ 1 ) = ( K r z ) ⊗ 1 K(z\otimes\mathbf{1})=(K_rz)\otimes\mathbf{1} K ( z ⊗ 1 ) = ( K r z ) ⊗ 1 for z ∈ R 4 z\in\mathbb{R}^4 z ∈ R 4 , where K r K_r K r is the array (1) with the numbers r f r_f r f in place of the blocks; for r = ( 2 , 0 , 0 , 0 ) r=(2,0,0,0) r = ( 2 , 0 , 0 , 0 ) , K r = 2 I 4 K_r=2I_4 K r = 2 I 4 .
The matrices C 0 , D 0 , E 0 C_0,D_0,E_0 C 0 , D 0 , E 0 are Hadamard matrices of order 4. Write H H H for the displayed matrix. The three blocks of H H T HH^{\mathsf{T}} H H T are therefore C 0 C 0 T + 2 w E 0 E 0 T = ( 4 + 8 w ) I 4 C_0C_0^{\mathsf{T}}+2wE_0E_0^{\mathsf{T}}=(4+8w)I_4 C 0 C 0 T + 2 w E 0 E 0 T = ( 4 + 8 w ) I 4 ; C 0 D 0 T ⊗ 1 T + 2 E 0 ⊗ 1 T = 0 C_0D_0^{\mathsf{T}}\otimes\mathbf{1}^{\mathsf{T}}+2E_0\otimes\mathbf{1}^{\mathsf{T}}=0 C 0 D 0 T ⊗ 1 T + 2 E 0 ⊗ 1 T = 0 , by the definition of E 0 E_0 E 0 ; and D 0 D 0 T ⊗ 11 T + K K T = 4 I 4 ⊗ 11 T + I 4 ⊗ ( n I − 411 T ) = n I D_0D_0^{\mathsf{T}}\otimes\mathbf{1}\mathbf{1}^{\mathsf{T}}+KK^{\mathsf{T}}=4I_4\otimes\mathbf{1}\mathbf{1}^{\mathsf{T}}+I_4\otimes(nI-4\mathbf{1}\mathbf{1}^{\mathsf{T}})=nI D 0 D 0 T ⊗ 1 1 T + K K T = 4 I 4 ⊗ 1 1 T + I 4 ⊗ ( n I − 4 1 1 T ) = n I . □
The known algebraic families of cores for this array [48 Thm. 1.1] do not cover the w w w we need: we use the array with Z 2 w = Z 2 × Z w \mathbb{Z}_{2w}=\mathbb{Z}_2\times\mathbb{Z}_w Z 2 w = Z 2 × Z w for w = 83 , 89 , 209 , 221 w=83,89,209,221 w = 83 , 89 , 209 , 221 .
Terminology. Egan, Kotsireas, London and Ó Catháin [23 §2.1] call four ± 1 \pm1 ± 1 sequences satisfying (3) a Legendre quadruple , a name modelled on Legendre pairs [26 ] (two sequences, with sum − 2 -2 − 2 in place of − 4 -4 − 4 ). They state Proposition 2 for circulant blocks with a differently signed border [23 Thm. 5] . The Wallis–Whiteman array is also among the arrays that Seberry and Yamada’s M-structures unify [64 ] .
Example 3 (Order 12). Take w = 1 w=1 w = 1 , so G = Z 2 G=\mathbb{Z}_2 G = Z 2 , and a 1 = ( + , + ) a_1=(+,+) a 1 = ( + , + ) , a 2 = a 3 = a 4 = ( + , − ) a_2=a_3=a_4=(+,-) a 2 = a 3 = a 4 = ( + , − ) . The autocorrelations at s = 1 s=1 s = 1 are 2 , − 2 , − 2 , − 2 2,-2,-2,-2 2 , − 2 , − 2 , − 2 , with sum − 4 -4 − 4 , and the row sums are ( 2 , 0 , 0 , 0 ) (2,0,0,0) ( 2 , 0 , 0 , 0 ) , so Proposition 2 gives a Hadamard matrix of order 12.
Theorem 5 below replaces the all-ones vector of each block by the ( q − 1 ) (q-1) ( q − 1 ) -dimensional space of zero-sum functions on Q = G / N Q=G/N Q = G / N (for q = 2 q=2 q = 2 the two are related by the twist of Remark 7(ii)).
Wider borders with a Hadamard corner
Suppose H H H , of the shape of Figure 1 , is a Hadamard matrix of order n n n , with corner C C C of order b b b and K = K ( a 1 , … , a 4 ) K=K(a_1,\ldots,a_4) K = K ( a 1 , … , a 4 ) . Then H H T = n I HH^{\mathsf{T}}=nI H H T = n I is three equations:
(a) K K T + D D T = n I KK^{\mathsf{T}}+DD^{\mathsf{T}}=nI K K T + D D T = n I , \qquad (b) C D T + E K T = 0 CD^{\mathsf{T}}+EK^{\mathsf{T}}=0 C D T + E K T = 0 , \qquad (c) C C T + E E T = n I b CC^{\mathsf{T}}+EE^{\mathsf{T}}=nI_b C C T + E E T = n I b .
Since D D D has b b b columns, (a) requires n I − K K T nI-KK^{\mathsf{T}} n I − K K T to be positive semidefinite of rank at most b b b . By (1) its eigenvalues are the numbers n − PSD ( χ ) n-\operatorname{PSD}(\chi) n − PSD ( χ ) , each four times. So PSD may differ from n n n at no more than b / 4 b/4 b /4 characters. The simplest arrangement is that these are the q − 1 q-1 q − 1 non-trivial characters of a quotient Q = G / N Q=G/N Q = G / N , with b = 4 ( q − 1 ) b=4(q-1) b = 4 ( q − 1 ) , and that PSD takes one value on them; by Parseval’s identity that value is b b b . This is condition (4) below.
Let N N N be a subgroup of G G G of even index q q q , let Q = G / N Q=G/N Q = G / N , with quotient map π : G → Q \pi:G\to Q π : G → Q , and put
∣ G ∣ = q k , b = 4 ( q − 1 ) , n = 4 ∣ G ∣ + b . |G|=qk,\qquad b=4(q-1),\qquad n=4|G|+b. ∣ G ∣ = q k , b = 4 ( q − 1 ) , n = 4∣ G ∣ + b .
For the second matrix of order 668, for instance, G = Z 2 2 × Z 41 G=\mathbb{Z}_2^2\times\mathbb{Z}_{41} G = Z 2 2 × Z 41 and N = Z 41 N=\mathbb{Z}_{41} N = Z 41 , so q = 4 q=4 q = 4 , k = 41 k=41 k = 41 , b = 12 b=12 b = 12 and n = 4 ⋅ 164 + 12 n=4\cdot164+12 n = 4 ⋅ 164 + 12 . We say that four functions a 1 , … , a 4 : G → { ± 1 } a_1,\ldots,a_4:G\to\{\pm1\} a 1 , … , a 4 : G → { ± 1 } satisfy the core condition for ( G , N ) (G,N) ( G , N ) , or form a core , if
∑ f PAF a f ( s ) = { − b , s ∈ N ∖ { 0 } , 4 , s ∉ N , equivalently ∑ f ∣ a f ^ ( χ ) ∣ 2 = { b , χ ≠ 1 , χ ∣ N = 1 , n , otherwise . (4) \sum_f \operatorname{PAF}_{a_f}(s)=
\begin{cases}
-b, & s\in N\setminus\{0\},\\
4, & s\notin N,
\end{cases}
\qquad\text{equivalently}\qquad
\sum_f\lvert\widehat{a_f}(\chi)\rvert^2=
\begin{cases}
b, & \chi\ne1,\ \chi|_N=1,\\
n, & \text{otherwise}.
\end{cases} \tag*{(4)} f ∑ PAF a f ( s ) = { − b , 4 , s ∈ N ∖ { 0 } , s ∈ / N , equivalently f ∑ ∣ a f ( χ ) ∣ 2 = { b , n , χ = 1 , χ ∣ N = 1 , otherwise . (4)
where the second form includes χ = 1 \chi=1 χ = 1 , at which it reads ∑ f r f 2 = n \sum_f r_f^2=n ∑ f r f 2 = n . The two forms are equivalent because ∑ f PAF a f ( s ) = n 1 { s = 0 } − ( 4 q 1 N ( s ) − 4 ) \sum_f\operatorname{PAF}_{a_f}(s)=n\mathbf{1}_{\{s=0\}}-(4q\mathbf{1}_N(s)-4) ∑ f PAF a f ( s ) = n 1 { s = 0 } − ( 4 q 1 N ( s ) − 4 ) for all s s s , and the function 4 q 1 N − 4 4q\mathbf{1}_N-4 4 q 1 N − 4 has transform 4 ∣ G ∣ 4|G| 4∣ G ∣ at the non-trivial characters in N ⊥ N^\perp N ⊥ and 0 elsewhere. Equivalently, the sets X f = { a f = − 1 } X_f=\{a_f=-1\} X f = { a f = − 1 } form a divisible difference family relative to N N N [57 Def. 1.1] : a non-zero element of the group is a difference within these sets exactly ∑ f ∣ X f ∣ − ∣ G ∣ − ( q − 1 ) \sum_f|X_f|-|G|-(q-1) ∑ f ∣ X f ∣ − ∣ G ∣ − ( q − 1 ) times if it lies in N N N and ∑ f ∣ X f ∣ − ∣ G ∣ + 1 \sum_f|X_f|-|G|+1 ∑ f ∣ X f ∣ − ∣ G ∣ + 1 times otherwise.
The array (1) is defined by the same formula for integer-valued functions. The theorem is stated in the following terms.
Let β f ( c ) = ∑ x ∈ c a f ( x ) \beta_f(c)=\sum_{x\in c}\!a_f(x) β f ( c ) = ∑ x ∈ c a f ( x ) for c ∈ Q c\in Q c ∈ Q be the coset sums , the compression of each block to Q Q Q . By the second form of (4) , since β f ^ ( θ ) = a f ^ ( θ ∘ π ) \widehat{\beta_f}(\theta)=\widehat{a_f}(\theta\circ\pi) β f ( θ ) = a f ( θ ∘ π ) , they satisfy ∑ f ∣ β f ^ ( θ ) ∣ 2 = b \sum_f|\widehat{\beta_f}(\theta)|^2=b ∑ f ∣ β f ( θ ) ∣ 2 = b for every character θ ≠ 1 \theta\ne1 θ = 1 of Q Q Q and ∑ f β f ^ ( 1 ) 2 = n \sum_f\widehat{\beta_f}(1)^2=n ∑ f β f ( 1 ) 2 = n .
We call the quadruple ( β f ) f (\beta_f)_f ( β f ) f , taken modulo adding constants (which do not matter, by Remark 7(ii)), the coset table of the core.
The border of Theorem 5 is built from balanced vectors ℓ ∈ { ± 1 } Q \ell\in\{\pm1\}^Q ℓ ∈ { ± 1 } Q , those with ∑ c ℓ ( c ) = 0 \sum_c\ell(c)=0 ∑ c ℓ ( c ) = 0 , which exist only for even q q q .
A word is a vector in { ± 1 } 4 q = ( { ± 1 } Q ) 4 \{\pm1\}^{4q}=(\{\pm1\}^Q)^4 { ± 1 } 4 q = ({ ± 1 } Q ) 4 whose four segments, one per block position, are balanced.
Let K β = K ( β 1 , … , β 4 ) K_{\beta}=K(\beta_{1},\ldots,\beta_{4}) K β = K ( β 1 , … , β 4 ) be the array (1) over Q Q Q , a 4 q × 4 q 4q \times4q 4 q × 4 q integer matrix. Rows and columns of K K K and K β K_{\beta} K β , rows of D D D and of the matrix D Q D_{Q} D Q of Theorem 5 , and columns of E E E and E Q E_{Q} E Q , are indexed by pairs ( f , x ) (f,x) ( f , x ) with x ∈ G x \in G x ∈ G , respectively ( f , c ) (f,c) ( f , c ) with c ∈ Q c \in Q c ∈ Q , the block position f f f major.
Lemma 4 (Pull-backs). For ℓ : Q → R \ell: Q \to\mathbb{R} ℓ : Q → R call ℓ ∘ π \ell\circ\pi ℓ ∘ π its pull-back to G G G , and pull back vectors of ( R Q ) 4 (\mathbb{R}^{Q})^{4} ( R Q ) 4 segment by segment. Let A ‾ f \overline{A}_{f} A f be the group matrix of β f \beta_{f} β f over Q Q Q , and R ‾ \overline{R} R the matrix R R R over Q Q Q . Then (i) ⟨ ℓ ∘ π , ℓ ′ ∘ π ⟩ = k ⟨ ℓ , ℓ ′ ⟩ \langle\ell\circ\pi,\ell' \circ\pi\rangle=k\langle\ell,\ell'\rangle ⟨ ℓ ∘ π , ℓ ′ ∘ π ⟩ = k ⟨ ℓ , ℓ ′ ⟩ ; (ii) A f ( ℓ ∘ π ) = ( A ‾ f ℓ ) ∘ π A_{f}(\ell\circ\pi)=(\overline{A}_{f}\ell)\circ\pi A f ( ℓ ∘ π ) = ( A f ℓ ) ∘ π , A f T ( ℓ ∘ π ) = ( A ‾ f T ℓ ) ∘ π A_{f}^{\mathsf{T}}(\ell\circ\pi)=(\overline{A}_{f}^{\mathsf{T}}\ell)\circ\pi A f T ( ℓ ∘ π ) = ( A f T ℓ ) ∘ π and R ( ℓ ∘ π ) = ( R ‾ ℓ ) ∘ π R(\ell\circ\pi)=(\overline{R}\ell)\circ\pi R ( ℓ ∘ π ) = ( R ℓ ) ∘ π . Hence K K K and K T K^{\mathsf{T}} K T send the pull-back of a vector u ∈ ( R Q ) 4 u\in(\mathbb{R}^{Q})^{4} u ∈ ( R Q ) 4 to the pull-backs of K β u K_{\beta}u K β u and K β T u K_{\beta}^{\mathsf{T}}u K β T u .
Proof. Part (i) holds because each coset of N N N has k k k elements. For (ii), ( A f ( ℓ ∘ π ) ) ( x ) = ∑ y a f ( y − x ) ℓ ( π y ) = ∑ c ∈ Q β f ( c − π x ) ℓ ( c ) (A_{f}(\ell\circ\pi))(x)=\sum_{y}a_{f}(y-x)\ell(\pi y)=\sum_{c\in Q}\beta_{f}(c-\pi x)\ell(c) ( A f ( ℓ ∘ π )) ( x ) = ∑ y a f ( y − x ) ℓ ( π y ) = ∑ c ∈ Q β f ( c − π x ) ℓ ( c ) , and the other two identities are proved in the same way. The last statement follows because K K K and K β K_{\beta} K β are built by the same formula (1) . □ \square □
Theorem 5 (Bordered array with a Hadamard corner). Let a 1 , … , a 4 a_{1},\ldots,a_{4} a 1 , … , a 4 satisfy (4) , with coset table ( β f ) (\beta_{f}) ( β f ) . Let D Q ∈ { ± 1 } 4 q × b D_{Q}\in\{\pm1\}^{4q\times b} D Q ∈ { ± 1 } 4 q × b have pairwise orthogonal words as columns and E Q ∈ { ± 1 } b × 4 q E_{Q}\in\{\pm1\}^{b\times4q} E Q ∈ { ± 1 } b × 4 q pairwise orthogonal words as rows, such that all entries of C = − 1 4 q E Q K β T D Q C=-\frac{1}{4q}E_{Q}K_{\beta}^{\mathsf{T}}D_{Q} C = − 4 q 1 E Q K β T D Q are ± 1 \pm1 ± 1 . Let D ( f , x ) , j = ( D Q ) ( f , π x ) , j D_{(f,x),j}=(D_{Q})_{(f,\pi x),j} D ( f , x ) , j = ( D Q ) ( f , π x ) , j and E i , ( f , x ) = ( E Q ) i , ( f , π x ) E_{i,(f,x)}=(E_{Q})_{i,(f,\pi x)} E i , ( f , x ) = ( E Q ) i , ( f , π x ) be the pull-backs to G G G . Then
H = ( C E D K ( a 1 , … , a 4 ) ) H=\begin{pmatrix} C & E \\ D & K(a_{1},\ldots,a_{4}) \end{pmatrix} H = ( C D E K ( a 1 , … , a 4 ) ) is a Hadamard matrix of order n = 4 ∣ G ∣ + 4 ( q − 1 ) n=4|G|+4(q-1) n = 4∣ G ∣ + 4 ( q − 1 ) , and C C C is a Hadamard matrix of order 4 ( q − 1 ) 4(q-1) 4 ( q − 1 ) .
Proof. Let Π \Pi Π be the orthogonal projection of R G \mathbb{R}^{G} R G onto the functions constant on N N N -cosets with zero sum, and let V V V be the space of vectors in ( R G ) 4 (\mathbb{R}^{G})^{4} ( R G ) 4 each of whose four segments lies in the range of Π \Pi Π . Equivalently, each segment lies in the span of the non-trivial characters in N ⊥ N^{\perp} N ⊥ . So V V V has dimension 4 ( q − 1 ) = b 4(q-1)=b 4 ( q − 1 ) = b , and the orthogonal projection onto it is I 4 ⊗ Π I_{4}\otimes\Pi I 4 ⊗ Π .
Step 1 (the defect of K K K ). By (4) , n I − ∑ f A f A f T nI-\sum_{f}A_{f}A_{f}^{\mathsf{T}} n I − ∑ f A f A f T is the group matrix of 4 q 1 N − 4 4q\mathbf{1}_{N}-4 4 q 1 N − 4 . The group matrix of 1 N \mathbf{1}_{N} 1 N is k k k times the projection onto the functions constant on cosets of N N N , and that of the constant 1 1 1 is ∣ G ∣ |G| ∣ G ∣ times the projection onto the constants. Since q k = ∣ G ∣ qk=|G| q k = ∣ G ∣ , this gives n I − ∑ f A f A f T = 4 ∣ G ∣ Π nI-\sum_{f}A_{f}A_{f}^{\mathsf{T}}=4|G|\Pi n I − ∑ f A f A f T = 4∣ G ∣Π , and by (1) n I − K K T = n I − K T K = 4 ∣ G ∣ ( I 4 ⊗ Π ) nI-KK^{\mathsf{T}}=nI-K^{\mathsf{T}}K=4|G|(I_{4}\otimes\Pi) n I − K K T = n I − K T K = 4∣ G ∣ ( I 4 ⊗ Π ) .
Step 2 (the borders are orthogonal bases of V V V ). The columns of D D D are pull-backs of words, so they lie in V V V . By Lemma 4(i) they are pairwise orthogonal and each has squared length 4 q k = 4 ∣ G ∣ 4qk=4|G| 4 q k = 4∣ G ∣ , and there are b = dim V b=\dim V b = dim V of them. Hence D T D = 4 ∣ G ∣ I b D^{\mathsf{T}}D=4|G|I_{b} D T D = 4∣ G ∣ I b and D D T = 4 ∣ G ∣ ( I 4 ⊗ Π ) DD^{\mathsf{T}}=4|G|(I_{4}\otimes\Pi) D D T = 4∣ G ∣ ( I 4 ⊗ Π ) . With Step 1 this is (a). The same holds for the rows of E E E : E E T = 4 ∣ G ∣ I b EE^{\mathsf{T}}=4|G|I_{b} E E T = 4∣ G ∣ I b .
Step 3 (K acts on V through Q). Each A ‾ f \overline{A}_{f} A f and A ‾ f T \overline{A}_{f}^{\mathsf{T}} A f T preserves the zero-sum functions on Q Q Q , and so does R ‾ \overline{R} R ; so by the same Lemma 4 K K K and K T K^{\mathsf{T}} K T map V V V into itself. By the same lemma K T D K^{\mathsf{T}}D K T D is the pull-back of K β T D Q K_{\beta}^{\mathsf{T}}D_{Q} K β T D Q , and E K T D = k E Q K β T D Q EK^{\mathsf{T}}D=kE_{Q}K_{\beta}^{\mathsf{T}}D_{Q} E K T D = k E Q K β T D Q . Hence C = − E K T D / ( 4 ∣ G ∣ ) C=-EK^{\mathsf{T}}D/(4|G|) C = − E K T D / ( 4∣ G ∣ ) .
Step 4 (the remaining blocks). Now C D T = − E K T D D T / ( 4 ∣ G ∣ ) = − E K T ( I 4 ⊗ Π ) = − E K T CD^{\mathsf{T}}=-EK^{\mathsf{T}}DD^{\mathsf{T}}/(4|G|)=-EK^{\mathsf{T}}(I_{4}\otimes\Pi)=-EK^{\mathsf{T}} C D T = − E K T D D T / ( 4∣ G ∣ ) = − E K T ( I 4 ⊗ Π ) = − E K T , because the columns of K E T KE^{\mathsf{T}} K E T lie in V V V . This is (b). Next, C C T = E K T ( I 4 ⊗ Π ) K E T / ( 4 ∣ G ∣ ) = E K T K E T / ( 4 ∣ G ∣ ) CC^{\mathsf{T}}=EK^{\mathsf{T}}(I_{4}\otimes\Pi)KE^{\mathsf{T}}/(4|G|)=EK^{\mathsf{T}}KE^{\mathsf{T}}/(4|G|) C C T = E K T ( I 4 ⊗ Π ) K E T / ( 4∣ G ∣ ) = E K T K E T / ( 4∣ G ∣ ) . By Step 1, K T K K^{\mathsf{T}}K K T K acts on V V V as multiplication by n − 4 ∣ G ∣ = b n-4|G|=b n − 4∣ G ∣ = b . So C C T = ( b / 4 ∣ G ∣ ) E E T = b I b CC^{\mathsf{T}}=(b/4|G|)EE^{\mathsf{T}}=bI_{b} C C T = ( b /4∣ G ∣ ) E E T = b I b , and with E E T = 4 ∣ G ∣ I b EE^{\mathsf{T}}=4|G|I_{b} E E T = 4∣ G ∣ I b this is (c). By hypothesis C C C has entries ± 1 \pm1 ± 1 , so H H H is a ± 1 \pm1 ± 1 matrix with H H T = n I HH^{\mathsf{T}}=nI H H T = n I , and C C C is a Hadamard matrix of order b b b . □ \square □
Conversely, let (4) hold and let H H H of the shape of Figure 1 be a Hadamard matrix. By (a) and Step 1, D D T = 4 ∣ G ∣ ( I 4 ⊗ Π ) DD^{\mathsf{T}}=4|G|(I_{4}\otimes\Pi) D D T = 4∣ G ∣ ( I 4 ⊗ Π ) , so the columns of D D D lie in V V V , D D D has rank b b b , and ( D T D ) 2 = D T ( D D T ) D = 4 ∣ G ∣ D T D (D^{\mathsf{T}}D)^{2}=D^{\mathsf{T}}(DD^{\mathsf{T}})D=4|G|D^{\mathsf{T}}D ( D T D ) 2 = D T ( D D T ) D = 4∣ G ∣ D T D gives D T D = 4 ∣ G ∣ I b D^{\mathsf{T}}D=4|G|I_{b} D T D = 4∣ G ∣ I b ; the same argument applied to H T H = n I H^{\mathsf{T}}H=nI H T H = n I treats E E E . Since a ± 1 \pm1 ± 1 vector of V V V is the pull-back of a word, the conditions on D Q D_{Q} D Q and E Q E_{Q} E Q in Theorem 5 are necessary as well as sufficient. Theorem 5 is the construction that Egan, Kotsireas, London and Ó Catháin state as [23 Thm. 7] , which they recovered from the matrices released in [1 ] . Their subgroup S S S of index k k k is our N N N of index q q q , and their K K K , E E E and F F F play the roles of C C C , E Q E_{Q} E Q and D Q D_{Q} D Q . They take the corner K K K as given, while here it is forced by D Q D_{Q} D Q and E Q E_{Q} E Q .
We call a pair ( D Q , E Q ) (D_{Q},E_{Q}) ( D Q , E Q ) as in the theorem a frame for the coset table, and the question whether a given coset table has a frame its frame problem . (The word has nothing to do with frames in the sense of harmonic analysis.)
Example 6 (Order 28 with a border of width 12). Take G = Q = Z 2 2 G=Q=\mathbb{Z}_{2}^{2} G = Q = Z 2 2 and N = 0 N=0 N = 0 , so k = 1 k=1 k = 1 , q = 4 q=4 q = 4 , b = 12 b=12 b = 12 and n = 28 n=28 n = 28 , with the elements in the order ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 0 ) , ( 1 , 1 ) (0,0),(0,1),(1,0),(1,1) ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 0 ) , ( 1 , 1 ) . Let a 1 = ( + , − , − , − ) a_{1}=(+,-,-,-) a 1 = ( + , − , − , − ) , a 2 = ( − , − , − , + ) a_{2}=(-,-,-,+) a 2 = ( − , − , − , + ) ,
a 3 = ( − , + , − , − ) a_3 = (-,+,-,-) a 3 = ( − , + , − , − ) and a 4 = ( + , + , + , + ) a_4 = (+,+,+,+) a 4 = ( + , + , + , + ) . Each of a 1 , a 2 , a 3 a_1,a_2,a_3 a 1 , a 2 , a 3 has autocorrelation 0 at every s ≠ 0 s \ne0 s = 0 , and a 4 a_4 a 4 has autocorrelation 4, so ∑ f PAF a f = 4 \sum_f \operatorname{PAF}_{a_f}=4 ∑ f PAF a f = 4 off N = { 0 } N=\{0\} N = { 0 } : this is the core condition (4) (the case s ∈ N ∖ { 0 } s \in N \setminus\{0\} s ∈ N ∖ { 0 } is empty). The row sums are ( − 2 , − 2 , − 2 , 4 ) (-2,-2,-2,4) ( − 2 , − 2 , − 2 , 4 ) , with squares summing to 28. Here β f = a f \beta_f=a_f β f = a f , and this is the coset table named in the caption of Table 2 : β 1 , β 2 , β 3 \beta_1,\beta_2,\beta_3 β 1 , β 2 , β 3 exceed their other values by 2 on ( 0 , 0 ) (0,0) ( 0 , 0 ) , ( 1 , 1 ) (1,1) ( 1 , 1 ) , ( 0 , 1 ) (0,1) ( 0 , 1 ) , and β 4 \beta_4 β 4 is constant. So the printed frame applies as it stands. Since π \pi π is the identity, D = D Q D=D_Q D = D Q , E = E Q E=E_Q E = E Q and K = K β K=K_\beta K = K β , and Figure 2 shows the resulting Hadamard matrix of order 28, with corner C = − E Q K β T D Q / 16 C=-E_QK_\beta^{T}D_Q/16 C = − E Q K β T D Q /16 .
Figure 2. The Hadamard matrix of order 28 of Example 6: corner C C C top left, E = E Q E=E_Q E = E Q top right, D = D Q D=D_Q D = D Q bottom left, and K ( a 1 , … , a 4 ) K(a_1,\ldots,a_4) K ( a 1 , … , a 4 ) in 4 × 4 4 \times4 4 × 4 blocks bottom right. Each row of E E E and each column of D D D is a word.
Table 2. The frame for Q = Z 2 2 Q = \mathbb{Z}_2^2 Q = Z 2 2 used for orders 668 ′ 668' 66 8 ′ and 1916 (§§§ 5.6 , § 5.5 ): the 12 columns of D Q D_Q D Q (left) and the 12 rows of E Q E_Q E Q (right). An entry i i i or i ˉ \bar{i} i ˉ in row f f f means that the word’s segment in block position f f f is θ i \theta_i θ i or − θ i -\theta_i − θ i , where θ i ( x ) = ( − 1 ) x i \theta_i(x) = (-1)^{x_i} θ i ( x ) = ( − 1 ) x i (i = 1 , 2 i = 1, 2 i = 1 , 2 ) and θ 3 = θ 1 θ 2 \theta_3 = \theta_1\theta_2 θ 3 = θ 1 θ 2 are the non-trivial characters of Q Q Q . It frames the coset table in which β 1 \beta_1 β 1 , β 2 \beta_2 β 2 and β 3 \beta_3 β 3 exceed their other values by 2 on the cosets ( 0 , 0 ) (0,0) ( 0 , 0 ) , ( 1 , 1 ) (1,1) ( 1 , 1 ) and ( 0 , 1 ) (0,1) ( 0 , 1 ) respectively, and β 4 \beta_4 β 4 is constant; this is the coset table of both matrices as printed in Table A2.
Table 2.
The two width-12 matrices of Table 1, 668 ′ 668' 66 8 ′ and 1916, differ from this one only in that each border entry is repeated k = 41 k=41 k = 41 or 119 times and the 4 × 4 4 \times4 4 × 4 blocks of K K K become 164 × 164 164 \times164 164 × 164 or 476 × 476 476 \times476 476 × 476 . The corner C C C is the same 12 × 12 12 \times12 12 × 12 matrix in all three, because the three coset tables agree modulo constants.
Keep D Q D_Q D Q and take E Q = D Q T E_Q=D_Q^{T} E Q = D Q T instead. Its rows are again twelve pairwise orthogonal words, so every other hypothesis of Theorem 5 holds, and C C T = 12 I CC^{T}=12I C C T = 12 I still holds, but C C C has entries in { 0 , ± 1 2 , ± 1 , ± 3 2 , ± 2 } \{0,\pm\frac{1}{2},\pm1,\pm\frac{3}{2},\pm2\} { 0 , ± 2 1 , ± 1 , ± 2 3 , ± 2 } . The bordered matrix then satisfies H H T = 28 I HH^{T}=28I H H T = 28 I but is not a ± 1 \pm1 ± 1 matrix.
Remark 7. (i) Since words are balanced, adding a constant to a β f \beta_f β f changes nothing, so the hypothesis involves the core only through its coset table. Hence one frame serves every core with that coset table, over any G G G and N N N with the same quotient Q Q Q . For given Q Q Q the core condition admits only finitely many coset tables modulo constants. Indeed, by Parseval’s identity ∑ f ∑ c ( β f ( c ) − β ˉ f ) 2 = b ( q − 1 ) / q \sum_f\sum_c(\beta_f(c)-\bar{\beta}_f)^2=b(q-1)/q ∑ f ∑ c ( β f ( c ) − β ˉ f ) 2 = b ( q − 1 ) / q , where β ˉ f \bar{\beta}_f β ˉ f is the mean of β f \beta_f β f , and the differences β f ( c ) − β f ( c ′ ) \beta_f(c)-\beta_f(c') β f ( c ) − β f ( c ′ ) are even integers.
(ii) For q = 2 q=2 q = 2 the balanced vectors are ± ( 1 , − 1 ) \pm(1,-1) ± ( 1 , − 1 ) . Let η \eta η be the pull-back of the non-trivial character of Q Q Q . Multiplying each block by η \eta η turns (4) into (3) , and, for a suitable frame, the array of Theorem 5 into that of Proposition 2. The reason is that η ( x ) η ( y ) = η ( y − x ) = η ( − x − y ) \eta(x)\eta(y)=\eta(y-x)=\eta(-x-y) η ( x ) η ( y ) = η ( y − x ) = η ( − x − y ) , since η 2 = 1 \eta^2=1 η 2 = 1 ; so conjugation by I 4 ⊗ diag ( η ) I_4\otimes\operatorname{diag}(\eta) I 4 ⊗ diag ( η ) turns A f A_f A f into the group matrix of η a f \eta a_f η a f and fixes R R R , and PAF η a ( s ) = η ( s ) PAF a ( s ) \operatorname{PAF}_{\eta a}(s)=\eta(s)\operatorname{PAF}_a(s) PAF η a ( s ) = η ( s ) PAF a ( s ) .
Frames
To find a frame, given the 4 q × 4 q 4q \times4q 4 q × 4 q integer matrix K β K_\beta K β , to find b b b pairwise orthogonal words d 1 , … , d b d_1,\ldots,d_b d 1 , … , d b and b b b pairwise orthogonal words e 1 , … , e b e_1,\ldots,e_b e 1 , … , e b with ∣ e i K β T d j ∣ = 4 q |e_iK_\beta^Td_j|=4q ∣ e i K β T d j ∣ = 4 q for all i , j i,j i , j . There are 6, 20, 70 balanced vectors for q = 4 , 6 , 8 q = 4, 6, 8 q = 4 , 6 , 8 , hence 6 4 = 1296 6^4 = 1296 6 4 = 1296 , 20 4 = 160 000 20^4 = 160\,000 2 0 4 = 160 000 and 70 4 = 24 010 000 70^4 = 24\,010\,000 7 0 4 = 24 010 000 words, and we sought frames by depth-first search over words (Appendix C).
The four matrices of widths 12, 20 and 28 use three frames, printed in Table A2 . That each satisfies the hypotheses of Theorem 5 is checked by a few small matrix products. Negating, translating (a f ↦ a f ( ⋅ + z ) a_f \mapsto a_f(\cdot+ z) a f ↦ a f ( ⋅ + z ) , z ∈ G z \in G z ∈ G ) or inverting (a f ↦ a f ( − ⋅ ) a_f \mapsto a_f(-\cdot) a f ↦ a f ( − ⋅ ) ) single blocks of a core, and permuting its blocks, preserve (4) and act on the coset table by the corresponding moves.
Table A2.
Proposition 8 (Frames for q = 4 , 6 , 8 q = 4, 6, 8 q = 4 , 6 , 8 ; computer-assisted). Let N ≤ G N \leq G N ≤ G have index q ∈ { 4 , 6 , 8 } q \in\{4, 6, 8\} q ∈ { 4 , 6 , 8 } . Every core for ( G , N ) (G,N) ( G , N ) yields, by Theorem 5 , a Hadamard matrix of order 4 ∣ G ∣ + 4 ( q − 1 ) 4|G| + 4(q - 1) 4∣ G ∣ + 4 ( q − 1 ) : for q = 4 q = 4 q = 4 with no adjustment of the core, for q = 6 q = 6 q = 6 after at most a common translation of its four blocks, and for q = 8 q = 8 q = 8 after adjusting the core within its class under the moves.
Proof. By Remark 7(i) only the coset table matters. We enumerated the admissible coset tables (Appendix C) by computer, reduced them to classes by the moves and the isomorphisms defined there, and found a frame for a representative of each class named in the column “frames found” of Table C1, for q = 4 q = 4 q = 4 for every table. The frames are in [83 ] and are not printed here, apart from the three used for Theorem 1 . □
Rows D D D and E E E of Table A2 for orders 668 ′ 668' 66 8 ′ and 1916 are the frame of Table 2 in the hexadecimal encoding of Appendix A. For instance, the first row of E Q E_Q E Q has segments θ 2 , θ 2 , − θ 1 , − θ 3 \theta_2, \theta_2, -\theta_1, -\theta_3 θ 2 , θ 2 , − θ 1 , − θ 3 ; it is the word 55C9 of Table A2, and its pull-back is the row shown in the lower part of Figure 1 , where the cosets of N N N are contiguous because G G G is ordered lexicographically.
Search methods
The bordered cells of Table 1 have between 168 and 712 free signs, too many for direct matching. Two methods reduce them to matchings of practicable size. The first is a change of variables along a factor Z 2 \mathbb{Z}_2 Z 2 or Z 2 2 \mathbb{Z}_2^2 Z 2 2 of G G G that splits the condition into parts with no common variables (§4.3), used for orders 668, 716, 1676 and 668'. Along Z 2 \mathbb{Z}_2 Z 2 , for orders 668, 716 and 1676, it is the decomposition of Miyamoto’s main theorem and gives two parts, the half-sums and the half-differences. Along Z 2 2 \mathbb{Z}_2^2 Z 2 2 , for 668', it is the analogous decomposition into four parts, to which Miyamoto’s theorem does not apply; there the four parts are free of common variables only after the signs at three exceptional positions, the mixed fibres of § 5.6 , have been fixed. The second is lifting through two quotients of G G G at once under a multiplier group (§ 4.4 ), used for 1772 and 1916 and, in variant forms, for 1388 and 1436.
Table 1.
Matching
The searches below solve equations p 1 + p 2 + p 3 + p 4 = p 0 p_1 + p_2 + p_3 + p_4 = p_0 p 1 + p 2 + p 3 + p 4 = p 0 in which each p f p_f p f ranges over a finite list L f \mathcal{L}_f L f of integer vectors, by exact meet-in-the-middle matching [20 , 41 ] . Here p f p_f p f is the vector of autocorrelations of a candidate for block f f f , one coordinate per equation, and p 0 p_0 p 0 is the prescribed right-hand side. One tabulates the sums p 1 + p 2 p_1 + p_2 p 1 + p 2 in a hash table indexed by (part of) the vector and probes it with p 0 − p 3 − p 4 p_0 - p_3 - p_4 p 0 − p 3 − p 4 . When the table would be too large, both sides are partitioned by the value of the pair sum at a few coordinates, and corresponding parts are matched one at a time. Forming one pair sum p 1 + p 2 p_1 + p_2 p 1 + p 2 or p 0 − p 3 − p 4 p_0 - p_3 - p_4 p 0 − p 3 − p 4 counts as one operation. The column log 2 \log_2 log 2 ops of Table 1 counts these operations. It includes the matching that list compressed solutions (§ 4.2 ) but not list generation. Appendix D converts these counts to processor time and cost.
If the parts likeliest to contain a solution are visited first, a matching that is stopped at its first solution does only the work up to that part. This is why “first” is far below “complete” in Table 3 .
Table 3. The circulant constructions of § 5.1 . Here h = g ( v − 1 ) / t h=g^{(v-1)/t} h = g ( v − 1 ) / t generates M M M , the row sums are in the order of (1) , and ( ∣ X 1 ∣ , … , ∣ X 4 ∣ ; λ ) (|X_1|,\ldots,|X_4|;\lambda) ( ∣ X 1 ∣ , … , ∣ X 4 ∣ ; λ ) are the parameters of the supplementary difference sets X f = { a f = − 1 } X_f=\{a_f=-1\} X f = { a f = − 1 } . The lists are reduced modulo rotation and reversal; L 1 , L 2 \mathcal{L}_1,\mathcal{L}_2 L 1 , L 2 are inserted and L 3 , L 4 \mathcal{L}_3,\mathcal{L}_4 L 3 , L 4 probed, and for v = 223 v=223 v = 223 , L 3 \mathcal{L}_3 L 3 is a subsample of L 1 = L 2 \mathcal{L}_1=\mathcal{L}_2 L 1 = L 2 . The columns complete and first give log 2 \log_2 log 2 of the number of operations in a complete matching and up to the first solution († \dagger † : estimated, not counted), and sols the distinct quadruples found before the matching was stopped; for v = 223 v=223 v = 223 it ran to completion.
Compression
For a subgroup L ≤ G L \le G L ≤ G , the sums a L ( c ) = ∑ x ∈ c a ( x ) a^{L}(c) = \sum_{x \in c} a(x) a L ( c ) = ∑ x ∈ c a ( x ) of a function over the cosets c c c of L L L satisfy [21 , 22 ]
∑ f PAF a f L ( d ) = ∑ s ∈ d ∑ f PAF a f ( s ) ( d ∈ G / L ) . (5) \sum_f \operatorname{PAF}_{a_f^L}(d) = \sum_{s \in d} \sum_f \operatorname{PAF}_{a_f}(s) \qquad(d \in G/L). \tag*{(5)} f ∑ PAF a f L ( d ) = s ∈ d ∑ f ∑ PAF a f ( s ) ( d ∈ G / L ) . (5)
Both sides are the sum of a f ( x ) a f ( y ) a_f(x)a_f(y) a f ( x ) a f ( y ) over f f f and over the pairs with y − x ∈ d y-x \in d y − x ∈ d . In the Fourier domain compression is subsampling: the transform of a L a^L a L at a character θ \theta θ of G / L G/L G / L is a ^ \hat{a} a ^ at θ \theta θ pulled back to $G. So a L a^L a L retains exactly the values of a ^ \hat{a} a ^ at the frequencies in L ⊥ L^\perp L ⊥ ; for a cyclic group these are the multiples of ∣ L ∣ |L| ∣ L ∣ . Equation (5) is this statement for ∑ f ∣ a ^ f ∣ 2 \sum_f |\hat{a}_f|^2 ∑ f ∣ a ^ f ∣ 2 . The right-hand side is fixed by (2) , (4) or (3) , so the four compressed blocks satisfy a system of the same kind on G / L G/L G / L , with integer entries. At d = 0 d=0 d = 0 the left-hand side is ∑ f ∑ c a f L ( c ) 2 \sum_f \sum_c a_f^L(c)^2 ∑ f ∑ c a f L ( c ) 2 .
In a cell, the compression of each block to G / L G/L G / L lies in the finite set C f C_f C f of compressions of M M M -invariant ± 1 \pm1 ± 1 vectors on G G G , restricted to the block’s row sum when the search fixes it. Condition (5) is one equation per orbit of ⟨ M , − 1 ⟩ \langle M,-1\rangle ⟨ M , − 1 ⟩ on G / L G/L G / L , the zero coset included. We call the quadruples in ∏ f C f \prod_f C_f ∏ f C f satisfying all of these equations the compressed solutions of the cell on G / L G/L G / L . They include the compression of every solution in the cell, and for G / L G/L G / L with up to a few dozen M M M -orbits they can be listed by matching with L f = C f L_f = C_f L f = C f , directly or through a chain of intermediate quotients.
Decoupling along Z2 (Miyamoto's decomposition) and Z2xZ2
Let G = Z 2 × G ′ G = \mathbb{Z}_2 \times G' G = Z 2 × G ′ and write a function a ∈ { ± 1 } G a \in\{\pm1\}^{G} a ∈ { ± 1 } G as
a ( x , y ) = S ( y ) + ( − 1 ) x T ( y ) , S ( y ) = 1 2 ( a ( 0 , y ) + a ( 1 , y ) ) , T ( y ) = 1 2 ( a ( 0 , y ) − a ( 1 , y ) ) , a(x,y) = S(y) + (-1)^x T(y), \qquad S(y) = \tfrac{1}{2}\bigl(a(0,y) + a(1,y)\bigr), \qquad T(y) = \tfrac{1}{2}\bigl(a(0,y) - a(1,y)\bigr), a ( x , y ) = S ( y ) + ( − 1 ) x T ( y ) , S ( y ) = 2 1 ( a ( 0 , y ) + a ( 1 , y ) ) , T ( y ) = 2 1 ( a ( 0 , y ) − a ( 1 , y ) ) ,
so that S , T : G ′ → { 0 , ± 1 } S,T : G' \to\{0,\pm1\} S , T : G ′ → { 0 , ± 1 } have complementary supports. This is the Fourier transform in the Z 2 \mathbb{Z}_2 Z 2 coordinate only: a ^ ( 1 , ψ ) = 2 S ^ ( ψ ) \hat{a}(1,\psi) = 2\hat{S}(\psi) a ^ ( 1 , ψ ) = 2 S ^ ( ψ ) and a ^ ( sgn , ψ ) = 2 T ^ ( ψ ) \hat{a}(\operatorname{sgn},\psi) = 2\hat{T}(\psi) a ^ ( sgn , ψ ) = 2 T ^ ( ψ ) for every character ψ \psi ψ of G ′ G' G ′ , where sgn \operatorname{sgn} sgn is the non-trivial character of Z 2 \mathbb{Z}_2 Z 2 .
In matrix form this is the decomposition on which Miyamoto’s main theorem [56 ] rests. Order G G G with the Z 2 \mathbb{Z}_2 Z 2 coordinate major, and let U U U and V V V be the group matrices of S S S and T T T over G ′ G' G ′ . The group matrix of a a a is then
A = ( U + V U − V U − V U + V ) , P A P = ( 2 U 0 0 2 V ) , P = 1 2 ( I I I − I ) . A = \begin{pmatrix} U+V & U-V \\ U-V & U+V \end{pmatrix}, \qquad PAP = \begin{pmatrix} 2U & 0 \\ 0 & 2V \end{pmatrix}, \qquad P = \frac{1}{\sqrt{2}}\begin{pmatrix} I & I \\ I & -I \end{pmatrix}. A = ( U + V U − V U − V U + V ) , P A P = ( 2 U 0 0 2 V ) , P = 2 1 ( I I I − I ) .
Here U U U and V V V are ( 0 , ± 1 ) (0,\pm1) ( 0 , ± 1 ) -matrices of disjoint support whose sum and difference are ± 1 \pm1 ± 1 matrices. This is the form of the blocks T i j T_{ij} T ij from which Miyamoto assembles his Hadamard matrices [56 (4.3)] ; his T i j T_{ij} T ij are ± 1 \pm1 ± 1 matrices of order 2 m 2m 2 m , and are not to be confused with the half-differences T f T_f T f of this section. Seberry and Yamada reformulated his results in terms of M-structures, orthogonal matrices of order 4 t 4t 4 t divided into sixteen t × t t \times t t × t blocks [64, 85], [65 , 8 ] , a notion that also covers the Goethals–Seidel and Wallis–Whiteman arrays; see also [66 ] and [67 ] . Conjugate condition (3) , which reads ∑ f A f A f T = ( 8 w + 4 ) I − 4 J \sum_f A_f A_f^{\mathsf T} = (8w+4)I - 4J ∑ f A f A f T = ( 8 w + 4 ) I − 4 J with J J J the all-ones matrix, by the orthogonal matrix P P P . Since P J P = diag ( 2 J , 0 ) PJP = \operatorname{diag}(2J,0) P J P = diag ( 2 J , 0 ) , it becomes
∑ f U f U f T = ( 2 w + 1 ) I − 2 J , ∑ f V f V f T = ( 2 w + 1 ) I \sum_f U_f U_f^{\mathsf T} = (2w+1)I - 2J, \qquad\sum_f V_f V_f^{\mathsf T} = (2w+1)I f ∑ U f U f T = ( 2 w + 1 ) I − 2 J , f ∑ V f V f T = ( 2 w + 1 ) I
on G ′ = Z w G' = \mathbb{Z}_w G ′ = Z w . Read entry by entry, this is (6) below.
Miyamoto’s main theorem [56 ] [84] concerns sixteen pairs ( U i j , V i j ) (U_{ij},V_{ij}) ( U ij , V ij ) , 1 ≤ i , j ≤ 4 1 \le i,j \le4 1 ≤ i , j ≤ 4 , of ( 0 , ± 1 ) (0,\pm1) ( 0 , ± 1 ) -matrices of order m m m , assembled with fixed signs into two matrices M ( U i j ) M(U_{ij}) M ( U ij ) and M ( V i j ) M(V_{ij}) M ( V ij ) of order 4 m 4m 4 m . Its hypotheses are that every U i j ± V i j U_{ij} \pm V_{ij} U ij ± V ij is a ± 1 \pm1 ± 1 matrix [56 (4.1)] , that the row sums are 1 1 1 for the U i j U_{ij} U ij and 0 0 0 for the other V i j V_{ij} V ij [56 (4.2)] , and that
M ( U i j ) M ( U i j ) T = ( 2 m + 1 ) I − 2 I 4 ⊗ J , M ( V i j ) M ( V i j ) T = ( 2 m + 1 ) I M(U_{ij})M(U_{ij})^{\mathsf T} = (2m+1)I - 2I_4 \otimes J, \qquad M(V_{ij})M(V_{ij})^{\mathsf T} = (2m+1)I M ( U ij ) M ( U ij ) T = ( 2 m + 1 ) I − 2 I 4 ⊗ J , M ( V ij ) M ( V ij ) T = ( 2 m + 1 ) I
[56 (4.9), (4.10)] . Its conclusion is that a bordered array built from the blocks T i j T_{ij} T ij is a Hadamard matrix of order 8 m + 4 8m+4 8 m + 4 . Now take m = w m=w m = w , and for M ( U i j ) M(U_{ij}) M ( U ij ) and M ( V i j ) M(V_{ij}) M ( V ij ) take the Goethals–Seidel arrays K ( U 1 , … , U 4 ) K(U_1,\ldots,U_4) K ( U 1 , … , U 4 ) and K ( V 1 , … , V 4 ) K(V_1,\ldots,V_4) K ( V 1 , … , V 4 ) of (1) , which have Miyamoto’s pattern of signs. Hypothesis (4.1) holds because each U f ± V f U_f \pm V_f U f ± V f is a ± 1 \pm1 ± 1 matrix. Hypothesis (4.2) holds because the U f U_f U f have row sums 1 2 r f \frac{1}{2}r_f 2 1 r f , which are ( 1 , 0 , 0 , 0 ) (1,0,0,0) ( 1 , 0 , 0 , 0 ) . Conditions (4.9) and (4.10) are the two equations displayed above, by the identity in (1) . His theorem therefore gives a Hadamard matrix of order 8 w + 4 8w+4 8 w + 4 , and it is the matrix of Proposition 2 up to the ordering of G G G and the order and signs of the four border rows and columns. So the four width-4 matrices of this paper, of orders 668, 716, 1676 and 1772, are instances of Miyamoto’s main theorem. This says nothing about how they were found: in [56 §5] the pairs ( U i j , V i j ) (U_{ij}, V_{ij}) ( U ij , V ij ) are built from conference matrices and other auxiliary matrices, whereas the U f U_f U f and V f V_f V f here come from the searches of §§§ 5.2 –§ 5.4 . In the restatement of Seberry and Yamada, the hypotheses above are conditions (iii)–(vi) of [64 Thm. 34] (conditions 3–6 of [65 Thm. 8.10] ), under which they obtain an M-structure Hadamard matrix of order 4 ( 2 n + 1 ) 4(2n+1) 4 ( 2 n + 1 ) , here with n = w n=w n = w ; [64 Lemma 26] ([65 Lemma 8.6] ) is the case of four pairs whose members are pairwise amicable.
Since PAF a ( 0 , s ) = 2 PAF S ( s ) + 2 PAF T ( s ) \operatorname{PAF}_{a}(0,s)=2\operatorname{PAF}_{S}(s)+2\operatorname{PAF}_{T}(s) PAF a ( 0 , s ) = 2 PAF S ( s ) + 2 PAF T ( s ) and PAF a ( 1 , s ) = 2 PAF S ( s ) − 2 PAF T ( s ) \operatorname{PAF}_{a}(1,s)=2\operatorname{PAF}_{S}(s)-2\operatorname{PAF}_{T}(s) PAF a ( 1 , s ) = 2 PAF S ( s ) − 2 PAF T ( s ) , the width-4 condition (3) on Z 2 × Z w \mathbb{Z}_2 \times\mathbb{Z}_w Z 2 × Z w is equivalent to
∑ f PAF T f ( s ) = 0 , ∑ f PAF S f ( s ) = − 2 ( s ≠ 0 ) , ∑ f ∣ supp T f ∣ = 2 w + 1. (6) \sum_f \operatorname{PAF}_{T_f}(s)=0,\qquad\sum_f \operatorname{PAF}_{S_f}(s)=-2\quad(s\ne0),\qquad\sum_f \lvert\operatorname{supp} T_f\rvert=2w+1. \tag*{(6)} f ∑ PAF T f ( s ) = 0 , f ∑ PAF S f ( s ) = − 2 ( s = 0 ) , f ∑ ∣ supp T f ∣ = 2 w + 1. (6)
Once the supports W f = supp T f W_f=\operatorname{supp}T_f W f = supp T f are fixed, the two conditions in (6) share no variable (the T T T -signs are supported on W f W_f W f , the S S S -signs on the complements), so any solution of one combines with any solution of the other on the same supports. A search for 8 w 8w 8 w coupled signs becomes a search over quadruples of supports ( W 1 , … , W 4 ) (W_1,\ldots,W_4) ( W 1 , … , W 4 ) , which we call support systems , followed by two independent searches of 2 w + 1 2w+1 2 w + 1 and 2 w − 1 2w-1 2 w − 1 signs, whose costs add rather than multiply. We call the two conditions of (6) , on the T f T_f T f and on the S f S_f S f , the T T T half and the S S S half. The separation is a property of Miyamoto’s decomposition, not of our search: his theorem puts one condition on the half-sums and one on the half-differences, and the two are tied to each other only through their supports. What this paper adds is a necessary condition on the supports (feasibility, below), the enumeration of support systems of a restricted shape (§ 5.2 ), and the matching of the two halves.
Example 9 (The decoupling on Z 6 \mathbb{Z}_6 Z 6 ). Take w = 3 w=3 w = 3 and, on Z 6 \mathbb{Z}_6 Z 6 (positions 0 , … , 5 0,\ldots,5 0 , … , 5 ), a 1 = + + + − + − a_1=+++-+- a 1 = + + + − + − , a 2 = + + − + − − a_2=++-+-- a 2 = + + − + − − , a 3 = + + + − − − a_3=+++--- a 3 = + + + − − − , a 4 = + + − + − − a_4=++-+-- a 4 = + + − + − − . Then ∑ f PAF a f ( s ) = − 4 \sum_f\operatorname{PAF}_{a_f}(s)=-4 ∑ f PAF a f ( s ) = − 4 for s = 1 , … , 5 s=1,\ldots,5 s = 1 , … , 5 and the row sums are ( 2 , 0 , 0 , 0 ) (2,0,0,0) ( 2 , 0 , 0 , 0 ) , so Proposition 2 gives a Hadamard matrix of order 28. Under i ↦ ( i m o d 2 , i m o d 3 ) i\mapsto(i\bmod2,i\bmod3) i ↦ ( i mod 2 , i mod 3 ) , a ( 0 , y ) a(0,y) a ( 0 , y ) is a a a at positions 0 , 4 , 2 0,4,2 0 , 4 , 2 and a ( 1 , y ) a(1,y) a ( 1 , y ) is a a a at positions 3 , 1 , 5 3,1,5 3 , 1 , 5 , for y = 0 , 1 , 2 y=0,1,2 y = 0 , 1 , 2 . Then S 1 = ( 0 , 1 , 0 ) S_1=(0,1,0) S 1 = ( 0 , 1 , 0 ) , T 1 = ( 1 , 0 , 1 ) T_1=(1,0,1) T 1 = ( 1 , 0 , 1 ) ; S 2 = ( 1 , 0 , − 1 ) S_2=(1,0,-1) S 2 = ( 1 , 0 , − 1 ) , T 2 = ( 0 , − 1 , 0 ) T_2=(0,-1,0) T 2 = ( 0 , − 1 , 0 ) ; S 3 = ( 0 , 0 , 0 ) S_3=(0,0,0) S 3 = ( 0 , 0 , 0 ) , T 3 = ( 1 , − 1 , 1 ) T_3=(1,-1,1) T 3 = ( 1 , − 1 , 1 ) ; S 4 = ( 1 , 0 , − 1 ) S_4=(1,0,-1) S 4 = ( 1 , 0 , − 1 ) , T 4 = ( 0 , − 1 , 0 ) T_4=(0,-1,0) T 4 = ( 0 , − 1 , 0 ) . The supports of the T f T_f T f have sizes 2 , 1 , 3 , 1 2,1,3,1 2 , 1 , 3 , 1 , with total 7 = 2 w + 1 7=2w+1 7 = 2 w + 1 ; ∑ f PAF T f ( 1 ) = 0 \sum_f\operatorname{PAF}_{T_f}(1)=0 ∑ f PAF T f ( 1 ) = 0 and ∑ f PAF S f ( 1 ) = − 2 \sum_f\operatorname{PAF}_{S_f}(1)=-2 ∑ f PAF S f ( 1 ) = − 2 ; the T f T_f T f have sums ( 2 , − 1 , 1 , − 1 ) (2,-1,1,-1) ( 2 , − 1 , 1 , − 1 ) , with squares summing to 7 7 7 , and the S f S_f S f have sums ( 1 , 0 , 0 , 0 ) (1,0,0,0) ( 1 , 0 , 0 , 0 ) .
Not every support system can carry solutions. Summing (6) gives ∑ f ( ∑ y T f ( y ) ) 2 = 2 w + 1 \sum_f(\sum_y T_f(y))^2=2w+1 ∑ f ( ∑ y T f ( y ) ) 2 = 2 w + 1 , the middle-frequency condition of [44 ] (it is the value 8 w + 4 8w+4 8 w + 4 of ∑ f ∣ a ^ f ( sgn , 1 ) ∣ 2 \sum_f|\widehat{a}_f(\operatorname{sgn},1)|^2 ∑ f ∣ a f ( sgn , 1 ) ∣ 2 , divided by 4). Since ∑ y S f ( y ) = r f / 2 \sum_y S_f(y)=r_f/2 ∑ y S f ( y ) = r f /2 , the normalisation r = ( 2 , 0 , 0 , 0 ) r=(2,0,0,0) r = ( 2 , 0 , 0 , 0 ) gives ( ∑ y S f ( y ) ) f = ( 1 , 0 , 0 , 0 ) (\sum_y S_f(y))_f=(1,0,0,0) ( ∑ y S f ( y ) ) f = ( 1 , 0 , 0 , 0 ) . Let ν ( s ) = ∑ f # { y ∈ W f : y + s ∈ W f } \nu(s)=\sum_f\#\{y\in W_f:y+s\in W_f\} ν ( s ) = ∑ f # { y ∈ W f : y + s ∈ W f } . Reducing the T T T -condition modulo 2 shows that ν ( s ) \nu(s) ν ( s ) is even for every s ≠ 0 s\ne0 s = 0 , and the S S S -condition at shift s s s is a sum of ∑ f # { y : y , y + s ∉ W f } = 4 w − 2 ( 2 w + 1 ) + ν ( s ) = ν ( s ) − 2 \sum_f\#\{y:y,y+s\notin W_f\}=4w-2(2w+1)+\nu(s)=\nu(s)-2 ∑ f # { y : y , y + s ∈ / W f } = 4 w − 2 ( 2 w + 1 ) + ν ( s ) = ν ( s ) − 2 terms ± 1 \pm1 ± 1 equal to − 2 -2 − 2 , which forces ν ( s ) ≥ 2 \nu(s)\geq2 ν ( s ) ≥ 2 . Call a support system feasible if ν ( s ) ≥ 2 \nu(s)\geq2 ν ( s ) ≥ 2 for all s ≠ 0 s\ne0 s = 0 . The last 4 4 4 are even and at least 2 2 2 for every s ≠ 0 s\ne0 s = 0 . Fix a feasible support system, sums σ f = ∑ y T f ( y ) \sigma_f=\sum_yT_f(y) σ f = ∑ y T f ( y ) with ∑ f σ f 2 = 2 w + 1 \sum_f\sigma_f^2=2w+1 ∑ f σ f 2 = 2 w + 1 and σ f ≡ ∣ W f ∣ ( m o d 2 ) \sigma_f\equiv|W_f|\pmod2 σ f ≡ ∣ W f ∣ ( mod 2 ) for the T T T half, and the sums ( 1 , 0 , 0 , 0 ) (1,0,0,0) ( 1 , 0 , 0 , 0 ) for the S S S half. Each half of (6) then asks for four sign vectors of prescribed sums, the values of T f T_f T f on its support or of S f S_f S f off it, whose autocorrelation vectors have a prescribed sum. We solved each half by matching the first two blocks against the last two, and verified every match exactly.
Along Z 2 2 \mathbb{Z}_2^2 Z 2 2 . For G = Z 2 2 × G ′ G=\mathbb{Z}_2^2\times G' G = Z 2 2 × G ′ and each character θ \theta θ of G ′ = Z 2 2 G'=\mathbb{Z}_2^2 G ′ = Z 2 2 , put a ( θ ) = 1 2 ∑ x θ ( x ) a ( x , ⋅ ) a^{(\theta)}=\frac{1}{2}\sum_x\theta(x)a(x,\cdot) a ( θ ) = 2 1 ∑ x θ ( x ) a ( x , ⋅ ) , the θ \theta θ -part of a a a . Likewise the θ \theta θ -parts are, up to the factor 1 2 \frac{1}{2} 2 1 , the Fourier transform in the Z 2 2 \mathbb{Z}_2^2 Z 2 2 coordinate only. The four θ \theta θ -parts are integer functions on G ′ G' G ′ , and
a ( x , y ) = 1 2 ∑ θ θ ( x ) a ( θ ) ( y ) , PAF a ( ζ , s ) = ∑ θ θ ( ζ ) PAF a ( θ ) ( s ) . a(x,y)=\frac{1}{2}\sum_\theta\theta(x)a^{(\theta)}(y),\qquad\operatorname{PAF}_a(\zeta,s)=\sum_\theta\theta(\zeta)\operatorname{PAF}_{a^{(\theta)}}(s). a ( x , y ) = 2 1 θ ∑ θ ( x ) a ( θ ) ( y ) , PAF a ( ζ , s ) = θ ∑ θ ( ζ ) PAF a ( θ ) ( s ) .
With N = G ′ N=G' N = G ′ , of index 4, and v = n / 4 = ∣ G ∣ + 3 v=n/4=|G|+3 v = n /4 = ∣ G ∣ + 3 (so that b = 12 b=12 b = 12 ), the core condition (4) is equivalent to four conditions, one per θ \theta θ :
∑ f PAF a f ( θ ) ( s ) = − 4 ⋅ 1 { θ ≠ 1 } ( s ≠ 0 ) , ∑ f ∑ y a f ( θ ) ( y ) 2 = v − 4 ⋅ 1 { θ ≠ 1 } . (7) \sum_f\operatorname{PAF}_{a_f^{(\theta)}}(s)=-4\cdot\mathbf{1}_{\{\theta\ne1\}}\quad(s\ne0),\qquad\sum_f\sum_y a_f^{(\theta)}(y)^2=v-4\cdot\mathbf{1}_{\{\theta\ne1\}}. \tag*{(7)} f ∑ PAF a f ( θ ) ( s ) = − 4 ⋅ 1 { θ = 1 } ( s = 0 ) , f ∑ y ∑ a f ( θ ) ( y ) 2 = v − 4 ⋅ 1 { θ = 1 } . (7)
Here the sums ∑ y a f ( θ ) ( y ) = 1 2 β ^ f ( θ ) \sum_y a_f^{(\theta)}(y)=\frac{1}{2}\widehat{\beta}_f(\theta) ∑ y a f ( θ ) ( y ) = 2 1 β f ( θ ) are 1 2 r f \frac{1}{2}r_f 2 1 r f for θ = 1 \theta=1 θ = 1 and are otherwise fixed by the coset table (§ 3.2 ). This is the analogue of Miyamoto’s decomposition with four parts in place of two: the character table H 4 H_4 H 4 of Z 2 2 \mathbb{Z}_2^2 Z 2 2 takes the place of ( 1 1 1 − 1 ) \left(\begin{smallmatrix}1&1\\1&-1\end{smallmatrix}\right) ( 1 1 1 − 1 ) , and (7) has four conditions where (6) has two. Miyamoto’s theorem does not apply to it: the border has width 12, not 4. Unlike S S S and T T T , the four θ \theta θ -parts need not have disjoint supports. A fibre a ( ⋅ , y ) a(\cdot,y) a ( ⋅ , y ) at which more than one θ \theta θ -part is non-zero is a mixed fibre (§ 5.6 ), and mixed fibres are the only places where the four conditions (7) share variables. So the four conditions separate only once the signs of the mixed fibres are fixed, as they are in the search for 668 ′ 668' 66 8 ′ (§ 5.6 ).
Lifting through two quotients
To fix ideas, take order 1772: G = Z 2 × Z 13 × Z 17 G = \mathbb{Z}_2 \times\mathbb{Z}_{13} \times\mathbb{Z}_{17} G = Z 2 × Z 13 × Z 17 . A block is two layers, one for each element of Z 2 \mathbb{Z}_2 Z 2 , and each layer is a 13 × 17 13 \times17 13 × 17 array of signs. Compressing along Z 17 \mathbb{Z}_{17} Z 17 records the 13 row sums μ i \mu_i μ i of each layer, 26 numbers in all; compressing along Z 13 \mathbb{Z}_{13} Z 13 records the 17 column sums κ j \kappa_j κ j , 34 numbers. A compressed solution on G / Z 17 G/\mathbb{Z}_{17} G / Z 17 prescribes all the row sums of all four blocks, and one on G / Z 13 G/\mathbb{Z}_{13} G / Z 13 all the column sums. The pair is compatible if, block by block, some M M M -invariant array of signs has both sets of margins.
± ± ⋯ ± ± μ 0 ± ± ⋯ ± ± μ 1 ⋮ ⋮ ⋮ ± ± ⋯ ± ± μ 12 κ 0 κ 1 ⋯ κ 15 κ 16 \begin{array}{cccccc|c}
\pm& \pm& \cdots& \pm& \pm& & \mu_0 \\
\pm& \pm& \cdots& \pm& \pm& & \mu_1 \\
\vdots& & & & \vdots& & \vdots\\
\pm& \pm& \cdots& \pm& \pm& & \mu_{12} \\
\hline
\kappa_0 & \kappa_1 & \cdots& \kappa_{15} & \kappa_{16} & &
\end{array} ± ± ⋮ ± κ 0 ± ± ± κ 1 ⋯ ⋯ ⋯ ⋯ ± ± ± κ 15 ± ± ⋮ ± κ 16 μ 0 μ 1 ⋮ μ 12
Turner, Kotsireas, Bulutoglu and Geyer [72 ] lift two sequences through two coprime compressions at once, via 0/1 matrices with prescribed row and column sums [27 , 61 ] . We do the same for four blocks under an imposed multiplier group, in three steps, with L 1 , L 2 ≤ G L_1,L_2 \leq G L 1 , L 2 ≤ G fixed by M M M , L 1 ∩ L 2 = 0 L_1 \cap L_2 = 0 L 1 ∩ L 2 = 0 and both quotients small.
We list the compressed solutions on G / L 1 G/L_1 G / L 1 and on G / L 2 G/L_2 G / L 2 .
We determine the compatible pairs, those for which for each f f f some M M M -invariant ± 1 \pm1 ± 1 block has both prescribed coset-sum vectors; this is a separate computation for each block.
Under a compatible pair we list for each block its decompressions , the M M M -invariant ± 1 \pm1 ± 1 vectors with both prescribed coset-sum vectors (we use the same word when the coset sums on one quotient only are prescribed), and match the four lists exactly on all equations of the cell.
Under M M M the Gale–Ryser criterion does not decide which margins are jointly realisable, so for order 1772 this was tabulated by running through the M M M -invariant patterns of a layer, of which there are 2 25 2^{25} 2 25 because M M M has 25 orbits on Z 221 \mathbb{Z}_{221} Z 221 .
Under a single compressed solution on one quotient a block can still have too many decompressions to list (§ 5.7 ); prescribing the sums on a second quotient as well shortens the lists.
When a quotient is too large for the first step, we use one of two variants. The first samples decompressions under one compressed solution on the small quotient and matches their coset sums on the large one (order 1388). The second is nesting: a descending chain of subgroups, each level’s matching conditioned on a solution of the level above, multi-level in the sense of [52 ] (order 1436). Every search of §§§ 5.3 –§ 5.5 , § 5.7 and § 5.8 is a chain of lists of compressed solutions followed by a final matching on the signs (for order 1676 the S S S half plays the part of the compressed level, since 2 S 2S 2 S is the compression of a a a along Z 2 \mathbb{Z}_2 Z 2 ). They differ only in the quotients used, their order, and whether a level is listed or sampled.
The thirteen matrices
Circulant blocks: orders 892, 1132, 1244, 1948, 1964
For v = 223 , 283 , 311 , 487 , 491 v = 223, 283, 311, 487, 491 v = 223 , 283 , 311 , 487 , 491 we take G = Z v G = \mathbb{Z}_v G = Z v in the cell of § 2.1 , with the parameters and row sums of Table 3 . For v = 283 v = 283 v = 283 the only t t t with suitable row sums is 3, hence m = 47 m = 47 m = 47 (compare m ≤ 25 m \leq25 m ≤ 25 in [20 ] ). For v = 487 v = 487 v = 487 and 491 we used t = 9 t = 9 t = 9 and 7 for the smaller m m m , rather than 3 and 5, for which suitable row sums also exist. We found the sequences of Table A1 by the matching method of [17 , 20 ] over the candidate lists of Table 3 .
Table A1. The sequences of the circulant constructions of § 5.1 (orders 892, 1132, 1244, 1948, 1964): for each a f a_f a f the value e 0 = a f ( 0 ) e_0=a_f(0) e 0 = a f ( 0 ) followed by ϵ 0 ϵ 1 ⋯ ϵ 2 m − 1 \epsilon_0\epsilon_1\cdots\epsilon_{2m-1} ϵ 0 ϵ 1 ⋯ ϵ 2 m − 1 , where ϵ j \epsilon_j ϵ j is the value of a f a_f a f on O j = { g j + 2 m u m o d v : 0 ≤ u < t } O_j=\{g^{j+2^m u}\bmod v:0\leq u<t\} O j = { g j + 2 m u mod v : 0 ≤ u < t } , with v , t , g , m v,t,g,m v , t , g , m as in Table 3 : ( v , t , g ) = ( 223 , 3 , 3 ) , ( 283 , 3 , 3 ) , ( 311 , 5 , 17 ) , ( 487 , 9 , 3 ) , ( 491 , 7 , 2 ) (v,t,g)=(223,3,3),(283,3,3),(311,5,17),(487,9,3),(491,7,2) ( v , t , g ) = ( 223 , 3 , 3 ) , ( 283 , 3 , 3 ) , ( 311 , 5 , 17 ) , ( 487 , 9 , 3 ) , ( 491 , 7 , 2 ) , 2 m = ( v − 1 ) / t 2m=(v-1)/t 2 m = ( v − 1 ) / t .
For each block, a tabu search [8 ] on ε \varepsilon ε collected a list L f \mathcal{L}_f L f of M M M -invariant sequences of row sum r f r_f r f with F ( a ) = ∑ i P a ( i ) 2 F(a) = \sum_i P_a(i)^2 F ( a ) = ∑ i P a ( i ) 2 below a fixed cut-off (compare the power-spectral-density test of [26 ] ). Since each P a ( i ) P_a(i) P a ( i ) is the common value of PAF a \operatorname{PAF}_a PAF a on the 2 t 2t 2 t shifts in O i ∪ O i + m O_i \cup O_{i+m} O i ∪ O i + m , F ( a ) F(a) F ( a ) is 1 / ( 2 t ) 1/(2t) 1/ ( 2 t ) times ∑ s ≠ 0 PAF a ( s ) 2 \sum_{s \ne0} \operatorname{PAF}_a(s)^2 ∑ s = 0 PAF a ( s ) 2 , the energy of Bernasconi’s model [3 ] with periodic boundary conditions (§ 7 ). A uniformly random ± 1 \pm1 ± 1 sequence on Z v \mathbb{Z}_v Z v , with no invariance imposed, has expected F = m v F = mv F = m v ; the sequences of Table A1 have F F F between 0.08 m v 0.08mv 0.08 m v and 0.14 m v 0.14mv 0.14 m v . Egan, Kotsireas, London and O’Catháin measure the same quantity: their flatness Φ f \Phi_f Φ f is essentially F / ( m v ) F/(mv) F / ( m v ) , and they find 0.08 < Φ f < 0.14 0.08 < \Phi_f < 0.14 0.08 < Φ f < 0.14 . From the spectra alone, they infer that only nearly flat sequences were searched at these orders [23 §3, Table 2] ; the cut-off of this step is that restriction. Sequences with smaller F F F make a match likelier but are exponentially rarer, and we chose cut-off and list size to balance the two.
(2) We reduced each list modulo reversal and the rotations a ( y ) ↦ a ( g − ρ y ) a(y)\mapsto a(g^{-\rho}y) a ( y ) ↦ a ( g − ρ y ) , ρ ∈ Z m \rho\in\mathbb{Z}_m ρ ∈ Z m , which shift ( P a ( i ) ) i (P_a(i))_i ( P a ( i ) ) i cyclically. Reversal is a ( y ) ↦ a ( − y ) a(y)\mapsto a(-y) a ( y ) ↦ a ( − y ) , which leaves P a P_a P a unchanged and sends ϵ j \epsilon_j ϵ j to ϵ j + m \epsilon_{j+m} ϵ j + m .
(3) We then matched over the lists and rotations, with one rotation enumerated on the insertion side and two on the probe side as in [20 ] , so that a complete matching is m ∣ L 1 ∣ ∣ L 2 ∣ + m 2 ∣ L 3 ∣ ∣ L 4 ∣ m|\mathcal{L}_1||\mathcal{L}_2|+m^2|\mathcal{L}_3||\mathcal{L}_4| m ∣ L 1 ∣∣ L 2 ∣ + m 2 ∣ L 3 ∣∣ L 4 ∣ operations. A common rotation of all four blocks is a symmetry, so only three rotations are free. The parts were the values of the pair sum at the first few coordinates; except for v = 223 v=223 v = 223 we visited the likeliest parts first.
For each row of Table 3 the four sequences of Table A1 satisfy (2) , and the array (1) built from them is the Hadamard matrix of Theorem 1 of that order. The further quadruples for v = 311 v=311 v = 311 and 487 487 487 counted in the last column of Table 3 are in [83 ] .
Width 4, no symmetry: orders 668 and 716
For 668 = 4 ⋅ 166 + 4 668=4\cdot166+4 668 = 4 ⋅ 166 + 4 and 716 = 4 ⋅ 178 + 4 716=4\cdot178+4 716 = 4 ⋅ 178 + 4 we take G = Z 2 × Z w G=\mathbb{Z}_2\times\mathbb{Z}_w G = Z 2 × Z w with w = 83 , 89 w=83,89 w = 83 , 89 prime, and impose no symmetry, so there are 8 w 8w 8 w signs and w w w equations. We found the cores by the decoupling (6) of §4.3, that is, by Miyamoto’s decomposition of each block into S S S and T T T .
A block on Z 166 \mathbb{Z}_{166} Z 166 with row sum 0 is one of ( 166 83 ) ≈ 2 162 \binom{166}{83}\approx2^{162} ( 83 166 ) ≈ 2 162 sequences, so matching whole blocks two against two would mean pairing lists of about 2 162 2^{162} 2 162 sequences each. The decoupling replaces this by a choice of supports and two smaller matchings. Heuristically, a random support system is feasible with probability about 2 − ( w − 1 ) / 2 2^{-(w-1)/2} 2 − ( w − 1 ) /2 : since ν ( s ) = ν ( − s ) \nu(s)=\nu(-s) ν ( s ) = ν ( − s ) there are ( w − 1 ) / 2 (w-1)/2 ( w − 1 ) /2 parity conditions, each met with probability about 1 2 \frac{1}{2} 2 1 , while ν ( s ) ≥ 4 \nu(s)\ge4 ν ( s ) ≥ 4 is far from binding for random supports, so feasible systems must be constructed rather than drawn. The matching below partitions the pair sums by their values at the shifts where the equations have fewest terms, and a sum of few signs takes few values. For interval-like supports the equations at the largest shifts have few terms; for the system of the order-668 matrix of Table A2 , ν ( s ) \nu(s) ν ( s ) falls from 158 at s = 1 s=1 s = 1 to 14, 12, 10 at s = 39 , 40 , 41 s=39,40,41 s = 39 , 40 , 41 , whereas random supports of the same sizes would give about 83 at every shift.
We restricted to supports that are cyclic intervals with at most one point removed and one point adjoined, the types of Table A3 , and listed the feasible support systems of that shape up to translation and reflection of each support. We listed them by a meet-in-the-middle on the parity vectors ( ν ( s ) m o d 2 ) s (\nu(s)\bmod2)_s ( ν ( s ) mod 2 ) s ; this gave a few hundred thousand systems at each of w = 83 w=83 w = 83 and 89. The steps below describe the search of one half on one system.
Table A3. Feasible supports ( W 1 , … , W 4 ) (W_1,\ldots,W_4) ( W 1 , … , W 4 ) in Z w \mathbb{Z}_w Z w carrying solutions of the decoupled conditions (6) (§4.3). Each W f W_f W f is described by its size ∣ W f ∣ |W_f| ∣ W f ∣ and its type: (arc) [ 0 , ∣ W f ∣ ) [0,|W_f|) [ 0 , ∣ W f ∣ ) ; (hx) [ 0 , ∣ W f ∣ + 1 ) ∖ { x } [0,|W_f|+1)\setminus\{x\} [ 0 , ∣ W f ∣ + 1 ) ∖ { x } ; (ey) [ 0 , ∣ W f ∣ − 1 ) ∪ { y } [0,|W_f|-1)\cup\{y\} [ 0 , ∣ W f ∣ − 1 ) ∪ { y } ; (hx ey) [ 0 , ∣ W f ∣ ) ∖ { x } ∪ { y } [0,|W_f|)\setminus\{x\}\cup\{y\} [ 0 , ∣ W f ∣ ) ∖ { x } ∪ { y } , up to a translation and reflection of each W f W_f W f separately. The column σ \sigma σ gives ( ∑ y T f ( y ) ) f (\sum_y T_f(y))_f ( ∑ y T f ( y ) ) f , in all cases ( ∑ y S f ( y ) ) f = ( 1 , 0 , 0 , 0 ) (\sum_y S_f(y))_f=(1,0,0,0) ( ∑ y S f ( y ) ) f = ( 1 , 0 , 0 , 0 ) . The last column gives the numbers of solutions on the T T T side and on the S S S side that were used to assemble the matrices in the data (each half-search was stopped after about two solutions; for the third row a second solution on each side was found and not used). †: the systems of the matrices of orders 668 and 716 in Table A2; the entries of Table 1 for these orders estimate the cost of their two half-searches.
With the supports and the sums fixed (σ f \sigma_f σ f for the T T T half, ( 1 , 0 , 0 , 0 ) (1,0,0,0) ( 1 , 0 , 0 , 0 ) for the S S S half), list f f f consists of all sign vectors of its length ℓ \ell ℓ and prescribed sum σ \sigma σ , ( ℓ ( ℓ + σ ) / 2 ) \binom{\ell}{(\ell+\sigma)/2} ( ( ℓ + σ ) /2 ℓ ) in number; the lengths are ∣ W f ∣ |W_f| ∣ W f ∣ and w − ∣ W f ∣ w-|W_f| w − ∣ W f ∣ , which can be read off Table A3 . This gives about 2 38 2^{38} 2 38 per block at w = 83 w=83 w = 83 and 2 41 2^{41} 2 41 at w = 89 w=89 w = 89 , so each side of the matching has about 2 76 2^{76} 2 76 , respectively 2 82 2^{82} 2 82 , pairs.
Treating the equations as independent gives a heuristic count of about 2 17 2^{17} 2 17 solutions per half for the two systems marked † \dagger † in Table A3 .
We partitioned both sides by the values of the pair sum at the largest shifts, where the equations have fewest terms, and matched one pair of corresponding parts at a time by hashing on the remaining shifts.
(4) Within a part we discarded every pair sum whose values at the remaining shifts were improbably large for a solution. This filter can also discard solutions; no other step of the matching can.
(5) We visited the likeliest parts first and stopped each half at its first solutions. Since a half has many solutions, only a small fraction of the pairs of step 1 is formed. The entries of Table 1 for these two orders are estimates for the two halves together; at order 716 the two halves cost about the same. Appendix D recomputes these estimates from the list sizes.
We took one support system per profile ( ν ( s ) ) s (\nu(s))_s ( ν ( s ) ) s , on which, apart from the list sizes, the heuristic count of step 2 depends, and searched an S S S half once its T T T half had a solution. Among the systems we searched, we found solutions on both halves for five at w = 83 w=83 w = 83 and one at w = 89 w=89 w = 89 (Table A3 ). The two marked there give the matrices of Table A2. The arc shape leaves a visible trace in the solutions. Write v ( y ) v(y) v ( y ) for the vector ( a f ( y ) ) f (a_f(y))_f ( a f ( y ) ) f of signs across the four blocks and pair y y y with y + w y+w y + w , as in §4.3. The pair v ( y ) , v ( y + w ) v(y),v(y+w) v ( y ) , v ( y + w ) spans a line when y y y lies in all four supports or in none, and a plane otherwise; so the second case occurs exactly where the four supports disagree, at positions fixed by the support system before any sign is chosen. For the core of order 668 these are y = 19 , 39 , 40 , 42 , 60 , 61 y=19,39,40,42,60,61 y = 19 , 39 , 40 , 42 , 60 , 61 : three near w / 2 w/2 w /2 , where arcs of different lengths end, and three isolated ones, a point removed from the centre of one arc and points adjoined near the antipodes of the centres of two others. For order 716 they are 23, 43–46 and 66, of the same two kinds. The isolated positions are where the feasibility conditions favour them. For a cyclic interval I I I in Z w \mathbb{Z}_w Z w , removing the point at its centre (when the length is odd) or adjoining the point antipodal to its centre (when it is even) changes ∣ I ∩ ( I + s ) ∣ |I\cap(I+s)| ∣ I ∩ ( I + s ) ∣ by an even number at every s s s , because both points are fixed by the reflection of Z w \mathbb{Z}_w Z w that preserves I I I ; a point at distance d d d from these positions changes the parity of ∣ I ∩ ( I + s ) ∣ |I\cap(I+s)| ∣ I ∩ ( I + s ) ∣ at 4 d 4d 4 d shifts. A hole at the centre or an extra near the antipode is therefore the way to change the size of a support by one while keeping the parity of every ν ( s ) \nu(s) ν ( s ) under control, and for arcs that start at 0 and have length about w / 2 w/2 w /2 these points lie near w / 4 w/4 w /4 and 3 w / 4 3w/4 3 w /4 . Random supports of the same sizes, aligned as favourably as possible by translating and reflecting each, typically disagree at 52–57 and 58–61 positions (at 49–58 and 56–63 over 400 random draws for each w w w ).
Width 4: order 1676
For 1676 = 4 ⋅ 418 + 4 =4\cdot418+4 = 4 ⋅ 418 + 4 we take G = Z 2 × Z 209 G=\mathbb{Z}_2\times\mathbb{Z}_{209} G = Z 2 × Z 209 , with w = 209 = 11 ⋅ 19 w=209=11\cdot19 w = 209 = 11 ⋅ 19 . The multiplier group M = ⟨ 26 ⟩ ≤ Z 209 ∗ M=\langle26\rangle\leq\mathbb{Z}_{209}^{*} M = ⟨ 26 ⟩ ≤ Z 209 ∗ , of order 15, acts on the second coordinate. It does not contain − 1 -1 − 1 and has 21 orbits on Z 209 \mathbb{Z}_{209} Z 209 (twelve of size 15, six of size 3, two of size 5, and { 0 } \{0\} { 0 } ), so there are 168 signs and 21 equations. We found the core by the decoupling (6) under M M M : the functions S f S_f S f and T f T_f T f are constant on orbits, with complementary supports, and each half of (6) is 10 equations, one per orbit of ⟨ M , − 1 ⟩ \langle M,-1\rangle ⟨ M , − 1 ⟩ on the non-zero elements of Z 209 \mathbb{Z}_{209} Z 209 . The twenty-first equation is the support-size condition of (6) . We solved the S S S half first, by matching over all orbit-constant functions Z 209 → { 0 , ± 1 } \mathbb{Z}_{209}\to\{0,\pm1\} Z 209 → { 0 , ± 1 } , keyed by support size and autocorrelation vector, with the four support sizes summing to 2 w − 1 2w-1 2 w − 1 . The matching on these keys is the entry of Table 1. The T T T half, with one sign per orbit outside the support of S f S_f S f , is then a small exact matching, which we ran over solutions of the S S S half until some extended to cores.
Width 4: order 1772
For 1772 = 4 ⋅ 442 + 4 =4\cdot442+4 = 4 ⋅ 442 + 4 we take G = Z 2 × Z 221 G=\mathbb{Z}_2\times\mathbb{Z}_{221} G = Z 2 × Z 221 , with w = 221 = 13 ⋅ 17 w=221=13\cdot17 w = 221 = 13 ⋅ 17 . The multiplier group M = ⟨ 55 ⟩ ≤ Z 221 ∗ M=\langle55\rangle\leq\mathbb{Z}_{221}^{*} M = ⟨ 55 ⟩ ≤ Z 221 ∗ , of order 12, acts on the second coordinate. Again − 1 ∉ M -1\notin M − 1 ∈ / M , and there are 200 signs and 29 equations. We found the core by the two-quotient lifting of § 4.4 , with L 1 = Z 17 L_1=\mathbb{Z}_{17} L 1 = Z 17 and L 2 = Z 13 L_2=\mathbb{Z}_{13} L 2 = Z 13 . Miyamoto’s decomposition was not used in this search; the resulting matrix is nontheless an instance of his main theorem, like every matrix of Proposition 2 (§4.3). We found about 2.2 ⋅ 10 10 2.2\cdot10^{10} 2.2 ⋅ 1 0 10 and 384 000 compressed solutions, on G / Z 17 G/\mathbb{Z}_{17} G / Z 17 and on G / Z 13 G/\mathbb{Z}_{13} G / Z 13 . We decided compatibility block by block from the table of jointly realisable margins of § 4.4 , before any sign was chosen. Under a compatible pair there are at most 8100 decompressions per block, which we matched exactly on all 29 equations. The entry of Table 1 is governed by the two matchings that list the compressed solutions.
Width 12: order 1916
For 1916 = 4 ⋅ 476 + 12 =4\cdot476+12 = 4 ⋅ 476 + 12 we take G = Z 2 2 × Z 119 G=\mathbb{Z}_2^2\times\mathbb{Z}_{119} G = Z 2 2 × Z 119 , 119 = 7 ⋅ 17 119=7\cdot17 119 = 7 ⋅ 17 , N = Z 119 N=\mathbb{Z}_{119} N = Z 119 and Q = Z 2 2 Q=\mathbb{Z}_2^2 Q = Z 2 2 . The multiplier group M M M , of order 12, is generated by ( x 1 , x 2 , y ) ↦ ( x 2 , x 1 + x 2 , 115 y ) (x_1,x_2,y)\mapsto(x_2,x_1+x_2,115y) ( x 1 , x 2 , y ) ↦ ( x 2 , x 1 + x 2 , 115 y ) (of order 3 on Z 2 2 \mathbb{Z}_2^2 Z 2 2 , while 115 has order 12 modulo 119), and there are 184 signs and 29 equations. We found the core by the two-quotient lifting of § 4.4 through G / Z 7 ≅ Z 2 2 × Z 17 G/\mathbb{Z}_7\cong\mathbb{Z}_2^2\times\mathbb{Z}_{17} G / Z 7 ≅ Z 2 2 × Z 17 and G / Z 17 ≅ Z 2 2 × Z 7 G/\mathbb{Z}_{17}\cong\mathbb{Z}_2^2\times\mathbb{Z}_7 G / Z 17 ≅ Z 2 2 × Z 7 . We found about 1.8 ⋅ 10 4 1.8\cdot10^4 1.8 ⋅ 1 0 4 compressed solutions on the first quotient, determined for each of them the compatible compressed solutions on the second, and under compatible pairs listed the decompressions of each block and matched them on the remaining equations. The entry of Table 1 covers the first list and the matching up to the first core. Table A2 gives one such core, moved to the coset table of Table 2 (§ 3.3 ) and bordered by that frame, with row sums ( 6 , 6 , 38 , 20 ) (6, 6, 38, 20) ( 6 , 6 , 38 , 20 ) . The move translates two of the blocks. This is why [23 Table 1] finds two generators of the released matrix invariant under a group of order 12 and the other two only under a group of order 4.
Width 12, no symmetry: the second matrix of order 668
For 668 = 4 ⋅ 164 + 12 668 = 4 \cdot164 + 12 668 = 4 ⋅ 164 + 12 we take G = Z 2 2 × Z 41 G = \mathbb{Z}_2^2 \times\mathbb{Z}_{41} G = Z 2 2 × Z 41 , N = Z 41 N = \mathbb{Z}_{41} N = Z 41 and Q = Z 2 2 Q = \mathbb{Z}_2^2 Q = Z 2 2 , and impose no symmetry, so there are 656 signs and 83 equations. We found the core by the fourfold decoupling (7) of §4.3, with v = 167 v = 167 v = 167 , arranged so that the core condition becomes four independent systems on Z 41 \mathbb{Z}_{41} Z 41 , one per character θ \theta θ of Z 2 2 \mathbb{Z}_2^2 Z 2 2 , each of 20 equations in 40 signs (41 for θ = 1 \theta= 1 θ = 1 ).
Call a f ( ⋅ , y ) ∈ { ± 1 } Q a_f(\cdot,y) \in\{\pm1\}^Q a f ( ⋅ , y ) ∈ { ± 1 } Q , for y ∈ G ′ y \in G' y ∈ G ′ , a fibre . A fibre is either ± θ ′ \pm\theta' ± θ ′ for one character θ ′ \theta' θ ′ , and then a f ( θ ) ( y ) = ± 2 ⋅ 1 { θ = θ ′ } a_f^{(\theta)}(y) = \pm2 \cdot1_{\{\theta= \theta'\}} a f ( θ ) ( y ) = ± 2 ⋅ 1 { θ = θ ′ } , or it has sum ± 2 \pm2 ± 2 . In the second case all four values a f ( θ ) ( y ) a_f^{(\theta)}(y) a f ( θ ) ( y ) are ± 1 \pm1 ± 1 , with an odd number of minus signs, and we call the fibre mixed . A pattern is an assignment of a character or the label mixed to each ( f , y ) (f,y) ( f , y ) . A pattern fixes every supp a f ( θ ) \operatorname{supp} a_f^{(\theta)} supp a f ( θ ) , and given the pattern the four conditions (7) share only the signs of the mixed fibres. A fibre ± θ ′ \pm\theta' ± θ ′ contributes to the θ ′ \theta' θ ′ -part only, so its sign is a variable of that one condition; a mixed fibre contributes ± 1 \pm1 ± 1 to all four θ \theta θ -parts.
The fibre types of the core of order 668′ ' ′ in Table A2 , with the values of the four θ \theta θ -parts at a fibre of each type, are as follows.
As checks, 4 ⋅ 41 + 3 = 167 = v 4 \cdot41 + 3 = 167 = v 4 ⋅ 41 + 3 = 167 = v and 4 ⋅ 40 + 3 = 163 = v − 4 4 \cdot40 + 3 = 163 = v - 4 4 ⋅ 40 + 3 = 163 = v − 4 , the second equation of (7) , and 41 + 3 ⋅ 40 + 3 = 164 = 4 ⋅ 41 41 + 3 \cdot40 + 3 = 164 = 4 \cdot41 41 + 3 ⋅ 40 + 3 = 164 = 4 ⋅ 41 is the number of fibres.
The pattern was fixed in the following steps; each is marked as forced by (7) or as chosen.
Number of mixed fibres: forced modulo 4, then chosen. In the second equation of (7) for θ = 1 \theta= 1 θ = 1 a constant fibre contributes 4, a mixed fibre 1 and any other fibre 0, so the number of mixed fibres is 3 modulo 4, and we allowed exactly three. (Lemma 10 below gives this count for every core on a group Z 2 2 × G ′ \mathbb{Z}_2^2 \times G' Z 2 2 × G ′ whose subgroup N N N meets Z 2 2 × { 0 } \mathbb{Z}_2^2 \times\{0\} Z 2 2 × { 0 } trivially.)
Where they lie: forced, then chosen at no cost. For θ ≠ 1 \theta\ne1 θ = 1 the coset table makes 1 2 β ^ f ( θ ) \frac{1}{2}\widehat{\beta}_f(\theta) 2 1 β f ( θ ) equal to ± 1 \pm1 ± 1 in three blocks and 0 in the fourth, f 0 f_0 f 0 say (Appendix C), and in each block this value has the parity of the number of its mixed fibres. Hence block f 0 f_0 f 0 has no mixed fibre and each other block has one, which we put at y = 0 y = 0 y = 0 by translating the block.
The other fibres: forced. By the same equations, of the other fibres in all four blocks, 41 are constant and, for each θ ≠ 1 \theta\ne1 θ = 1 , 40 are ± θ \pm\theta ± θ .
Parity: chosen; balance: forced. We also required the number of fibres assigned to each θ ≠ 1 \theta\ne1 θ = 1 to be even in every block. The sum conditions then force the values ± 2 \pm2 ± 2 of each non-trivial θ \theta θ -part to be balanced within every block. They also force a f ( θ ) ( 0 ) = 1 2 β f ( θ ) a_f^{(\theta)}(0) = \frac{1}{2}\beta_f^{(\theta)} a f ( θ ) ( 0 ) = 2 1 β f ( θ ) for θ ≠ 1 \theta\ne1 θ = 1 and f ≠ f 0 f \ne f_0 f = f 0 , and hence a f ( 1 ) ( 0 ) a_f^{(1)}(0) a f ( 1 ) ( 0 ) , since a mixed fibre has an odd number of minus signs. All signs of the mixed fibres are then fixed, so the four conditions (7) share no variable.
Lemma 10 (Mixed fibres are forced). Let G = Z 2 2 × G ′ G = \mathbb{Z}_2^2 \times G' G = Z 2 2 × G ′ , let a 1 , … , a 4 a_1,\ldots,a_4 a 1 , … , a 4 be a core for ( G , N ) (G,N) ( G , N ) , and suppose that N ∩ ( Z 2 2 × { 0 } ) = 0 N \cap(\mathbb{Z}_2^2 \times\{0\}) = 0 N ∩ ( Z 2 2 × { 0 }) = 0 . Let m m m be the number of mixed fibres in the four blocks together, and for each character θ \theta θ of Z 2 2 \mathbb{Z}_2^2 Z 2 2 let c θ c_\theta c θ be the number of fibres equal to ± θ \pm\theta ± θ . Then
4 c 1 + m = ∣ G ∣ + 3 , 4 c θ + m = ∣ G ∣ − 1 ( θ ≠ 1 ) . (8) 4c_1 + m = |G| + 3,\qquad4c_\theta+ m = |G| - 1 \quad(\theta\ne1). \tag*{(8)} 4 c 1 + m = ∣ G ∣ + 3 , 4 c θ + m = ∣ G ∣ − 1 ( θ = 1 ) . (8)
In particular m ≡ 3 ( m o d 4 ) m \equiv3 \pmod4 m ≡ 3 ( mod 4 ) , so every such core has at least three mixed fibres. For four blocks on G G G satisfying the Goethals–Seidel condition (2) instead, the same count gives 4 c θ + m = ∣ G ∣ 4c_\theta+ m = |G| 4 c θ + m = ∣ G ∣ for every θ \theta θ , so m ≡ 0 ( m o d 4 ) m \equiv0 \pmod4 m ≡ 0 ( mod 4 ) and m = 0 m = 0 m = 0 is not excluded.
Proof. Write P = ∑ f P A f a f P = \sum_f P A_f a_f P = ∑ f P A f a f . Since θ ( x ) θ ( x ′ ) = θ ( x ′ − x ) \theta(x)\theta(x') = \theta(x' - x) θ ( x ) θ ( x ′ ) = θ ( x ′ − x ) , expanding the square gives
∑ f ∑ y ∈ G ′ a f ( θ ) ( y ) 2 = 1 4 ∑ ζ ∈ Z 2 2 P ( ζ , 0 ) . (9) \sum_f \sum_{y \in G'} a_f^{(\theta)}(y)^2 = \frac{1}{4}\sum_{\zeta\in\mathbb{Z}_2^2} P(\zeta,0). \tag*{(9)} f ∑ y ∈ G ′ ∑ a f ( θ ) ( y ) 2 = 4 1 ζ ∈ Z 2 2 ∑ P ( ζ , 0 ) . (9)
By (4) , P ( 0 ) = 4 ∣ G ∣ P(0)=4|G| P ( 0 ) = 4∣ G ∣ , and P ( ζ , 0 ) = 4 P(\zeta,0)=4 P ( ζ , 0 ) = 4 for ζ ≠ 0 \zeta\ne0 ζ = 0 because ( ζ , 0 ) ∉ N (\zeta,0)\notin N ( ζ , 0 ) ∈ / N . So the right side is ∣ G ∣ + 3 |G|+3 ∣ G ∣ + 3 for θ = 1 \theta=1 θ = 1 and ∣ G ∣ − 1 |G|-1 ∣ G ∣ − 1 otherwise. On the left, a fibre ± θ ′ \pm\theta' ± θ ′ contributes 4 to the sum for θ ′ \theta' θ ′ and 0 to the others, and a mixed fibre contributes 1 to each. This gives (8) , and m ≡ 3 ( m o d 4 ) m\equiv3\pmod{4} m ≡ 3 ( mod 4 ) because ∣ G ∣ = 4 ∣ G ′ ∣ |G|=4|G'| ∣ G ∣ = 4∣ G ′ ∣ . Under (2) , P ( ζ , 0 ) = 0 P(\zeta,0)=0 P ( ζ , 0 ) = 0 for ζ ≠ 0 \zeta\ne0 ζ = 0 , and the right side is ∣ G ∣ |G| ∣ G ∣ for every θ \theta θ . □
For the present cell, (8) is the second equation of (7) . The lemma also applies to the cells of orders 1916 and 1436, where N = Z 119 N=\mathbb{Z}_{119} N = Z 119 and N = 2 Z 8 × Z 11 N=2\mathbb{Z}_{8}\times\mathbb{Z}_{11} N = 2 Z 8 × Z 11 meet Z 2 2 × { 0 } \mathbb{Z}_2^2\times\{0\} Z 2 2 × { 0 } trivially; their printed cores, found by lifting through quotients, have 219 of 476 and 203 of 352 fibres mixed, about half, against exactly three here.
We found a pattern and signs by growing the pattern one θ \theta θ -part at a time, each stage a matching of two blocks against two on the 20 equations of that θ \theta θ -part. The lists, one per block, consisted of a pattern for that θ \theta θ -part together with balanced signs, and we took patterns symmetric under y ↦ − y y\mapsto-y y ↦ − y in the three blocks that have a mixed fibre. For two non-trivial θ \theta θ -parts in turn we sampled lists of about 10 4 10^4 1 0 4 patterns with signs per block among the fibres still free, and kept the first solution. For the third non-trivial θ \theta θ -part we matched over all its patterns among the remaining fibres. For each distinct pattern among the solutions of this stage, the θ \theta θ -part of the trivial character lives on the complementary fibres; we applied a parity test at each shift like the feasibility test of §4.3, then a matching over its 41 signs. We repeated these stages until a pattern carried a solution of the last one.
Any of the 9408 frames for its coset table, such as that of Table 2 , borders the core (Theorem 5 ). The resulting matrix, in Table A2 with row sums ( 14 , − 18 , − 2 , − 12 ) (14,-18,-2,-12) ( 14 , − 18 , − 2 , − 12 ) , is inequivalent by 4-profiles [10 ] to every width-4 matrix of order 668 in [83 ] . The 4-profile of a Hadamard matrix records how often each value of ∣ ∑ h a j h b j h c j h d j ∣ | \sum h_{a j}h_{b j}h_{c j}h_{d j} | ∣ ∑ h aj h bj h c j h d j ∣ occurs over the sets { a , b , c , d } \{a,b,c,d\} { a , b , c , d } of four rows; it is unchanged by permuting and negating rows and columns.
The width-12 search was far smaller than the width-4 search at the same order (Table 1): the fourfold decoupling gives four conditions of 20 equations in about 40 signs each, instead of two conditions of 41 equations in about 166 signs each. The price is the three mixed fibres forced by Lemma 10. Fixing them first, all at y = 0 y=0 y = 0 , is what made the four conditions independent.
Width 20: order 1388
For 1388 = 4 ⋅ 342 + 20 =4\cdot342+20 = 4 ⋅ 342 + 20 we take G = Z 6 × Z 57 G=\mathbb{Z}_6\times\mathbb{Z}_{57} G = Z 6 × Z 57 , N = Z 57 N=\mathbb{Z}_{57} N = Z 57 and Q = Z 6 Q=\mathbb{Z}_6 Q = Z 6 , so that k = ∣ N ∣ = 57 k=|N|=57 k = ∣ N ∣ = 57 is odd. The multiplier group M M M , of order 6, is generated by ( x , y ) ↦ ( − x , 11 y ) (x,y)\mapsto(-x,11y) ( x , y ) ↦ ( − x , 11 y ) , and there are 280 signs and 39 equations. We found the core by the sampled form of the two-quotient lifting (§ 4.4 ). Write Z 3 ′ \mathbb{Z}'_3 Z 3 ′ for the subgroup of order 3 of Z 57 \mathbb{Z}_{57} Z 57 .
We found about 7.6 ⋅ 10 6 7.6\cdot10^6 7.6 ⋅ 1 0 6 compressed solutions on G / Z 19 G/\mathbb{Z}_{19} G / Z 19 (order 18, ten equations counting d = 0 d=0 d = 0 ).
The complementary quotient G / Z 3 ′ G/\mathbb{Z}'_3 G / Z 3 ′ (order 114, 16 equations, again counting d = 0 d=0 d = 0 , 12 of them not implied by those on G / Z 19 G/\mathbb{Z}_{19} G / Z 19 ) is too large for its compressed solutions to be listed. Even under a single compressed solution on G / Z 19 G/\mathbb{Z}_{19} G / Z 19 a block still has 2 37 2^{37} 2 37 –2 43 2^{43} 2 43 decompressions, too many for matching on the equations of G / Z 3 ′ G/\mathbb{Z}'_3 G / Z 3 ′ . We therefore fixed one compressed solution on G / Z 19 G/\mathbb{Z}_{19} G / Z 19 , drew uniformly random decompressions of each block with the prescribed Z 19 \mathbb{Z}_{19} Z 19 -coset sums, and recorded their Z 3 ′ \mathbb{Z}'_3 Z 3 ′ -coset sums. We drew 2 20 2^{20} 2 20 of them for each block; uniform sampling is easy because the constraint splits into ten independent pieces, one per orbit of M M M on G / Z 19 G/\mathbb{Z}_{19} G / Z 19 .
We then matched the sampled coset-sum vectors on the 16 equations of G / Z 3 ′ G/\mathbb{Z}'_3 G / Z 3 ′ . This matching gave about 1.5 ⋅ 10 5 1.5\cdot10^5 1.5 ⋅ 1 0 5 consistent quadruples of coset-sum data.
Finally, for each resulting quadruple of coset-sum data consistent on both quotients, we listed all decompressions, only a few thousand per block, and matched them exactly on all 39 equations.
Table A2 gives one core found in this way, with row sums ( 6 , 10 , 26 , 24 ) (6,10,26,24) ( 6 , 10 , 26 , 24 ) . The frame used is half-turn-invariant up to sign (Appendix § 11 ); the half-turn is c ↦ c + 3 c\mapsto c+3 c ↦ c + 3 on all four segments.
Width 28: order 1436
For 1436 = 4 ⋅ 352 + 28 =4\cdot352+28 = 4 ⋅ 352 + 28 we take G = Z 2 2 × Z 8 × Z 11 G=\mathbb{Z}_2^2\times\mathbb{Z}_8\times\mathbb{Z}_{11} G = Z 2 2 × Z 8 × Z 11 and, writing x = ( x 1 , x 2 , x 3 , x 4 ) ∈ G x=(x_1,x_2,x_3,x_4)\in G x = ( x 1 , x 2 , x 3 , x 4 ) ∈ G , put π ( x ) = ( x 1 , x 2 , x 3 m o d 2 ) \pi(x)=(x_1,x_2,x_3\bmod2) π ( x ) = ( x 1 , x 2 , x 3 mod 2 ) , so that N ≅ Z 4 × Z 11 N\cong\mathbb{Z}_4\times\mathbb{Z}_{11} N ≅ Z 4 × Z 11 and Q = Z 2 3 Q=\mathbb{Z}_2^3 Q = Z 2 3 . The group M = ⟨ 3 ⟩ ≤ Z 11 ∗ M=\langle3\rangle\leq\mathbb{Z}_{11}^{*} M = ⟨ 3 ⟩ ≤ Z 11 ∗ of order 5 acts on the last coordinate, with 96 orbits per block (32 fixed points with x 4 = 0 x_4=0 x 4 = 0 and 64 orbits of size 5), so there are 384 signs and 51 equations. We sought cores with the constant coset table over Z 2 3 \mathbb{Z}_2^3 Z 2 3 (Appendix § 11 ): β f \beta_f β f constant except on one common coset, where it exceeds its other values by 2, 2, 2, 4, its excess . Since k = ∣ N ∣ = 44 k=|N|=44 k = ∣ N ∣ = 44 is even, the β f \beta_f β f are even-valued, so the row sums are ≡ 2 ( m o d 16 ) \equiv2\pmod{16} ≡ 2 ( mod 16 ) for the three blocks with excess 2 and ≡ 4 ( m o d 16 ) \equiv4\pmod{16} ≡ 4 ( mod 16 ) for the fourth. The condition ∑ f β f ( 1 ) 2 = 1436 \sum_f\beta_f(1)^2=1436 ∑ f β f ( 1 ) 2 = 1436 then leaves three possibilities for the row sums, τ 1 = { − 30 , − 14 , − 14 , − 12 } \tau_1=\{-30,-14,-14,-12\} τ 1 = { − 30 , − 14 , − 14 , − 12 } , τ 2 = { − 30 , 18 , − 14 , 4 } \tau_2=\{-30,18,-14,4\} τ 2 = { − 30 , 18 , − 14 , 4 } , τ 3 = { 18 , 18 , 2 , − 28 } \tau_3=\{18,18,2,-28\} τ 3 = { 18 , 18 , 2 , − 28 } as multisets, the excesses being taken positive. The matrix of Table A2 has row sums τ 2 \tau_2 τ 2 .
The fixed-point signs satisfy a congruence of the classical kind [46 , 73 ] (compare [60 ] ).
Lemma 11 (A congruence modulo 20). Let a 1 , … , a 4 a_1,\ldots,a_4 a 1 , … , a 4 be a core in this cell, let L = Z 11 L=\mathbb{Z}_{11} L = Z 11 , and for a coset c c c of L L L let ξ f ( c ) \xi_f(c) ξ f ( c ) be the value of a f a_f a f at the M M M -fixed point of c c c . Then ∑ f PAF ξ f ( d ) ≡ Λ ( d ) ( m o d 20 ) \sum_f \operatorname{PAF}_{\xi_f}(d) \equiv\Lambda(d) \pmod{20} ∑ f PAF ξ f ( d ) ≡ Λ ( d ) ( mod 20 ) for d ≠ 0 d \ne0 d = 0 in G / L G/L G / L , where Λ ( d ) = ∑ s ∈ d ∑ f PAF a f ( s ) \Lambda(d)=\sum_{s\in d}\sum_f \operatorname{PAF}_{a_f}(s) Λ ( d ) = ∑ s ∈ d ∑ f PAF a f ( s ) .
Proof. Each coset c c c of L = Z 11 L=\mathbb{Z}_{11} L = Z 11 consists of one M M M -fixed point y c y_c y c and two orbits of size 5. Its sum is therefore ξ ( c ) + 5 ω ( c ) \xi(c)+5\omega(c) ξ ( c ) + 5 ω ( c ) with ξ ( c ) = a ( y c ) ∈ { ± 1 } \xi(c)=a(y_c)\in\{\pm1\} ξ ( c ) = a ( y c ) ∈ { ± 1 } and ω ( c ) ∈ { 0 , ± 2 } \omega(c)\in\{0,\pm2\} ω ( c ) ∈ { 0 , ± 2 } . Now
PAF ξ + 5 ω ( d ) − PAF ξ ( d ) = 25 PAF ω ( d ) + 5 ∑ c ξ ( c ) ( ω ( c + d ) + ω ( c − d ) ) . \operatorname{PAF}_{\xi+5\omega}(d)-\operatorname{PAF}_{\xi}(d)=25\operatorname{PAF}_{\omega}(d)+5\sum_c \xi(c)\bigl(\omega(c+d)+\omega(c-d)\bigr). PAF ξ + 5 ω ( d ) − PAF ξ ( d ) = 25 PAF ω ( d ) + 5 c ∑ ξ ( c ) ( ω ( c + d ) + ω ( c − d ) ) .
and both PAF ω ( d ) \operatorname{PAF}_{\omega}(d) PAF ω ( d ) and the last sum are divisible by 4. Indeed, PAF ω = 4 PAF ω / 2 \operatorname{PAF}_{\omega}=4\operatorname{PAF}_{\omega/2} PAF ω = 4 PAF ω /2 , and the last sum can be regrouped as ∑ c ω ( c ) ( ξ ( c − d ) + ξ ( c + d ) ) \sum_c\omega(c)\bigl(\xi(c-d)+\xi(c+d)\bigr) ∑ c ω ( c ) ( ξ ( c − d ) + ξ ( c + d ) ) , in which each term is a product of two even numbers. Hence compressing (4) to G / L G/L G / L (order 32) by (5) gives the congruence. □
The coset sums β f \beta_f β f , that is the coset table together with the row sums, also fix the sums of the ξ f \xi_f ξ f over N / L N/L N / L -cosets (the four cosets of L L L inside a coset of N N N ), since such a sum is ≡ β f ( m o d 10 ) \equiv\beta_f\pmod{10} ≡ β f ( mod 10 ) and is one of − 4 , − 2 , 0 , 2 , 4 -4,-2,0,2,4 − 4 , − 2 , 0 , 2 , 4 , which are distinct modulo 10.
Lemma 12 (The row sums τ 1 \tau_1 τ 1 do not occur). In this cell no core with the constant coset table has row sums τ 1 \tau_1 τ 1 .
Proof. Take d = ( 0 , 0 , 4 ) d=(0,0,4) d = ( 0 , 0 , 4 ) , the element of order 2 of N / L ≅ Z 4 N/L\cong\mathbb{Z}_4 N / L ≅ Z 4 ; there Λ ( d ) = 11 ⋅ ( − 28 ) = − 308 ≡ 12 ( m o d 20 ) \Lambda(d)=11\cdot(-28)=-308\equiv12\pmod{20} Λ ( d ) = 11 ⋅ ( − 28 ) = − 308 ≡ 12 ( mod 20 ) . Translation by d d d maps each coset of N / L N/L N / L to itself, and the four signs of ξ \xi ξ on a coset contribute 4, 0 or ± 4 \pm4 ± 4 to PAF ξ ( d ) \operatorname{PAF}_{\xi}(d) PAF ξ ( d ) according as their sum is ± 4 \pm4 ± 4 , ± 2 \pm2 ± 2 or 0. For τ 1 \tau_1 τ 1 these sums equal the β f \beta_f β f : − 4 -4 − 4 seven times and − 2 -2 − 2 once for the block of row sum − 30 -30 − 30 ; − 2 -2 − 2 seven times and 0 once for each block of row sum − 14 -14 − 14 ; − 2 -2 − 2 seven times and 2 once for the block of row sum − 12 -12 − 12 . Hence ∑ f PAF ξ f ( d ) = 28 ± 4 ± 4 \sum_f\operatorname{PAF}_{\xi_f}(d)=28\pm4\pm4 ∑ f PAF ξ f ( d ) = 28 ± 4 ± 4 , which is 0, 8 or 16 modulo 20, never 12, contradicting Lemma 11. □
For τ 2 \tau_2 τ 2 and τ 3 \tau_3 τ 3 the same count gives 36 + 4 j 36+4j 36 + 4 j with j j j a sum of eight signs, which allows 12 (mod 20) (for j = − 6 j=-6 j = − 6 or 4). We continued with τ 2 \tau_2 τ 2 .
Write 4 Z 8 4\mathbb{Z}_8 4 Z 8 and 2 Z 8 2\mathbb{Z}_8 2 Z 8 for the subgroups of orders 2 and 4 of the Z 8 \mathbb{Z}_8 Z 8 factor. The subgroups used are
L = Z 11 < 4 Z 8 × L < N = 2 Z 8 × L , 4 Z 8 < 2 Z 8 . L=\mathbb{Z}_{11}<4\mathbb{Z}_8\times L<N=2\mathbb{Z}_8\times L,\qquad4\mathbb{Z}_8<2\mathbb{Z}_8. L = Z 11 < 4 Z 8 × L < N = 2 Z 8 × L , 4 Z 8 < 2 Z 8 .
We generated compressed solutions on G / L G/L G / L with row sums τ 2 \tau_2 τ 2 by a chain of matchings (§ 4.2 ) through G / ( 4 Z 8 × L ) G/(4\mathbb{Z}_8\times L) G / ( 4 Z 8 × L ) ; the one used fixes all ξ f ( c ) \xi_f(c) ξ f ( c ) and ω f ( c ) \omega_f(c) ω f ( c ) (notation of the proof of Lemma 11) and leaves one free sign on each coset with ω f ( c ) = 0 \omega_f(c)=0 ω f ( c ) = 0 . These signs enter the conditions compressed to G / 2 Z 8 G/2\mathbb{Z}_8 G /2 Z 8 and G / 4 Z 8 G/4\mathbb{Z}_8 G /4 Z 8 only through their sums over N / L N/L N / L -cosets and over pairs of L L L -cosets, so we matched on these quotients and on G G G , each level conditioned on the one above, in the nested lifting of § 4.4 :
Table 1 (PDF p. 17).
The three nested matchings found about 3.5 ⋅ 10 4 3.5\cdot10^4 3.5 ⋅ 1 0 4 , then about 4.1 ⋅ 10 6 4.1\cdot10^6 4.1 ⋅ 1 0 6 consistent quadruples of sums, and finally the cores. Step 5 gave 9672 cores over the compressed solution on G / L G/L G / L fixed in step 2, all in [83 ] , and the entry of Table 1 counts the whole computation for it. The constant-table frame of Appendix § 11 , moved to their coset table, borders any of them, and Table A2 gives one.
Checking the matrices, and the data
Recipes
Each of the thirteen matrices can be rebuilt from the printed tables by one of three recipes. In Table A2 a hex string is zero-padded at the end: take the leading ∣ G ∣ |G| ∣ G ∣ bits and drop the rest (for order 668 a block is 42 hex digits, 168 bits, of which the first 166 are used). For width 4 that table indexes the blocks cyclically, on Z 2 w \mathbb{Z}_{2w} Z 2 w , the isomorphism with the Z 2 × Z w \mathbb{Z}_2\times\mathbb{Z}_w Z 2 × Z w of Table 1 is i ↦ ( i m o d 2 , i m o d w ) i\mapsto(i\bmod2,i\bmod w) i ↦ ( i mod 2 , i mod w ) . In lexicographic order the last coordinate runs fastest: on Z m 1 × ⋯ × Z m r \mathbb{Z}_{m_1} \times\cdots\times\mathbb{Z}_{m_r} Z m 1 × ⋯ × Z m r the element ( x 1 , … , x r ) (x_1,\ldots,x_r) ( x 1 , … , x r ) has index ( ( … ( ( x 1 m 2 + x 2 ) m 3 + x 3 ) … ) m r + x r ((\ldots((x_1m_2+x_2)m_3+x_3)\ldots)m_r+x_r (( … (( x 1 m 2 + x 2 ) m 3 + x 3 ) … ) m r + x r , counting from 0.
Circulant orders 892, 1132, 1244, 1948, 1964 (v , t , g v,t,g v , t , g from Table 3 ; signs from Table A1 ; K K K is the array (1)):
M 2 = ( v − 1 ) / t M2=(v-1)/t M 2 = ( v − 1 ) / t . For f = 1 … 4 f=1\ldots4 f = 1 … 4 read e 0 e0 e 0 and eps [ 0 … M 2 − 1 ] \operatorname{eps}[0\ldots M2-1] eps [ 0 … M 2 − 1 ] .
a f [ 0 ] = e 0 a_f[0]=e0 a f [ 0 ] = e 0 ; a f [ g ( j + M 2 u ) m o d v ] = eps [ j ] a_f[g^{(j+M2u)} \bmod v]=\operatorname{eps}[j] a f [ g ( j + M 2 u ) mod v ] = eps [ j ] for 0 ≤ j < M 2 0\leq j<M2 0 ≤ j < M 2 , 0 ≤ u < t 0\leq u<t 0 ≤ u < t .
A f [ x ] [ y ] = a f [ ( y − x ) m o d v ] A_f[x][y]=a_f[(y-x)\bmod v] A f [ x ] [ y ] = a f [( y − x ) mod v ] ; R [ x ] [ y ] = 1 R[x][y]=1 R [ x ] [ y ] = 1 if x + y = 0 m o d v x+y=0\bmod v x + y = 0 mod v , else 0.
H H H is the array K ( a 1 , … , a 4 ) K(a_1,\ldots,a_4) K ( a 1 , … , a 4 ) . Check H H T = 4 v I HH^{\mathsf T}=4vI H H T = 4 v I .
Width 4: orders 668, 716, 1676, 1772 (blocks from Table A2; the array of Proposition 2):
a f = a_f= a f = the first 2 w 2w 2 w bits of the hex string, most significant bit first; bit 1 means − 1 -1 − 1 .
A f A_f A f , R R R and the array K K K as above, modulo 2 w 2w 2 w .
H = [ [ C 0 , E 0 × 1 T ] , [ D 0 × 1 , K ] ] H=[[C0,E0\mathbin{\times}1^{\mathsf T}],[D0\mathbin{\times}1,K]] H = [[ C 0 , E 0 × 1 T ] , [ D 0 × 1 , K ]] , with 1 1 1 the all-ones column of length 2 w 2w 2 w : E 0 × 1 T E0\mathbin{\times}1^{\mathsf T} E 0 × 1 T is 4 × 8 w 4\times8w 4 × 8 w (each entry of E 0 E0 E 0 becomes a row of 2 w 2w 2 w equal entries), and D 0 × 1 D0\mathbin{\times}1 D 0 × 1 is 8 w × 4 8w\times4 8 w × 4 (each entry of D 0 D0 D 0 becomes a column of 2 w 2w 2 w equal entries). Check H H T = ( 8 w + 4 ) I HH^{\mathsf T}=(8w+4)I H H T = ( 8 w + 4 ) I .
Widths 12, 20, 28: orders 668′, 1916, 1388, 1436 (blocks and frames from Table A2; Theorem 5 ):
Decode a f a_f a f as in the width-4 recipe (the first ∣ G ∣ |G| ∣ G ∣ bits), elements of G G G in lexicographic order. For 1436 the four blocks are printed in the order a 1 , … , a 4 a_1,\ldots,a_4 a 1 , … , a 4 in which they enter the array, and their sums (− 14 -14 − 14 , 18, − 30 -30 − 30 , 4) are listed in that same order. A f [ x ] [ y ] = a f ( y − x ) A_f[x][y]=a_f(y-x) A f [ x ] [ y ] = a f ( y − x ) and R [ x ] [ y ] = [ x + y = 0 ] R[x][y]=[x+y=0] R [ x ] [ y ] = [ x + y = 0 ] , computed in G G G . pi ( x ) = ( x 1 , x 2 ) \operatorname{pi}(x)=(x_1,x_2) pi ( x ) = ( x 1 , x 2 ) for 668′ and 1916; pi ( x ) = x 1 \operatorname{pi}(x)=x_1 pi ( x ) = x 1 for 1388; pi ( x ) = ( x 1 , x 2 , x 3 m o d 2 ) \operatorname{pi}(x)=(x_1,x_2,x_3\bmod2) pi ( x ) = ( x 1 , x 2 , x 3 mod 2 ) for 1436.
Decode the b b b words of row D D D (columns of D Q D_Q D Q ) and of row E E E (rows of E Q E_Q E Q ): 4 q 4q 4 q bits each, most significant bit first, bit 1 meaning − 1 -1 − 1 ; bit number f ∗ q + ( index of c in Q ) f*q+(\text{index of }c\text{ in }Q) f ∗ q + ( index of c in Q ) , f = 0 … 3 f=0\ldots3 f = 0 … 3 , is the entry at block position f + 1 f+1 f + 1 and coset c c c (Q Q Q in lexicographic order).
β f [ c ] = ∑ a f [ x ] \beta_f[c]=\sum a_f[x] β f [ c ] = ∑ a f [ x ] over the x x x with pi ( x ) = c \operatorname{pi}(x)=c pi ( x ) = c .
K K K = the array K K K over G G G from the a f a_f a f ; K b K_b K b = the same array over Q Q Q from the β f \beta_f β f .
C = − ( E Q K b T D Q ) / ( 4 q ) C=-(E_QK_b^{\mathsf T}D_Q)/(4q) C = − ( E Q K b T D Q ) / ( 4 q ) . Check that every entry is + 1 +1 + 1 or − 1 -1 − 1 .
D [ ( f , x ) ] [ j ] = D Q [ ( f , pi ( x ) ) ] [ j ] D[(f,x)][j]=D_Q[(f,\operatorname{pi}(x))][j] D [( f , x )] [ j ] = D Q [( f , pi ( x ))] [ j ] ; E [ i ] [ ( f , x ) ] = E Q [ i ] [ ( f , pi ( x ) ) ] E[i][(f,x)]=E_Q[i][(f,\operatorname{pi}(x))] E [ i ] [( f , x )] = E Q [ i ] [( f , pi ( x ))] .
H = [ [ C , E ] , [ D , K ] ] H=[[C,E],[D,K]] H = [[ C , E ] , [ D , K ]] . Check H H T = n I HH^{\mathsf T}=nI H H T = n I .
The three recipes, run on Table A1 and A2 as printed in exact integer arithmetic, give thirteen matrices with H H T = n I HH^{\mathsf T}=nI H H T = n I . The core conditions (2), (3) and (4) and the stated row sums also hold. Every block is invariant under the multiplier group stated for its cell, after undoing the translations noted for order 1916. The matrix of Figure 2 is a Hadamard matrix with a Hadamard corner. The row sums and the numbers of multiplier orbits agree with [23 ] , Tables 1–Table 2 .
Relation to the public files
The files released publicly before this paper [1 ] give one matrix of each of the twelve orders, as a decoder script and an encoded list of signs. They are built from the sequences and blocks of Table A1 and A2, with two differences of convention. (i) For nine orders, the four of width 4 and the five circulant ones, they use R = ( 1 { x + y = − 1 } ) R=({1\{x+y=-1\}}) R = ( 1 { x + y = − 1 } ) in place of R = ( 1 { x + y = 0 } ) R=({1\{x+y=0\}}) R = ( 1 { x + y = 0 } ) . For the five circulant orders the two matrices differ only by shifting the rows and columns of every block by ( v + 1 ) / 2 (v+1)/2 ( v + 1 ) /2 , which fixes each A f A_f A f and carries one R R R to the other. For the four width-4 orders no such shift exists, and they are different Hadamard matrices from the same sequences; for order 668 the released one is inequivalent to that of Table A2. (ii) For order 1388 they index G G G as Z 2 × Z 3 × Z 57 \mathbb{Z}_2\times\mathbb{Z}_3\times\mathbb{Z}_{57} Z 2 × Z 3 × Z 57 instead of Z 6 × Z 57 \mathbb{Z}_6\times\mathbb{Z}_{57} Z 6 × Z 57 , identifying u ∈ Z 6 u\in\mathbb{Z}_6 u ∈ Z 6 with ( x , y ) ∈ Z 2 × Z 3 (x,y)\in\mathbb{Z}_2\times\mathbb{Z}_3 ( x , y ) ∈ Z 2 × Z 3 by u = 3 x + 2 y u=3x+2y u = 3 x + 2 y , that is x = u m o d 2 x=u\bmod2 x = u mod 2 and y = − u m o d 3 y=-u\bmod3 y = − u mod 3 . This is not the usual map u ↦ ( u m o d 2 , u m o d 3 ) u\mapsto(u\bmod2,u\bmod3) u ↦ ( u mod 2 , u mod 3 ) . For order 1916 the printed blocks are those of the released matrix.
Cost of the searches
Appendix D estimates what the pair sums counted in Table 1 cost, from timings of the two inner loops of a matching and from the current list price of rented processors (Table D1 ). The search for order 716 dominates: 2 ⋅ 10 7 2\cdot10^7 2 ⋅ 1 0 7 to 8 ⋅ 10 7 8\cdot10^7 8 ⋅ 1 0 7 core-hours, about US$1–4 million, which at the accounts of Table 1 is more than nine tenths of the total. The width-4 search for order 668 and the circulant searches for orders 1132 and 1964 cost between 7 ⋅ 10 4 7\cdot10^4 7 ⋅ 1 0 4 and 6 ⋅ 10 5 6\cdot10^5 6 ⋅ 1 0 5 core-hours each, and the other nine searches together under 5 000 core-hours. These figures cover the counted operations only. The hardware and the time actually used are not recorded in this paper.
Table D1. Estimated cost of the pair sums counted in Table 1, in decreasing order. The column n s ns n s is the time allowed per pair sum on one core, and the last column is the cost at US$0.051 per core-hour.
The supplementary data
The supplementary data [83 ] hold the thirteen matrices with their defining data, the frame catalogues of Appendix C, and the further cores and matrices mentioned in the text, all in the conventions of this paper. A script rebuilds every matrix from its defining data and re-checks H H T = n I HH^{\mathsf T}=nI H H T = n I , the defining conditions and every frame and core stated or listed; it also recounts the admissible coset tables, but it does not check that the lists of frames, cores or solutions are complete. Apart from the constraint solver mentioned in §1 and existing libraries, all programs were written for this work, mainly in C, C++ and Python. The search programs themselves are not part of [83 ] .
Solutions of the two halves on the same supports combine freely, and one system at w = 83 w = 83 w = 83 gave two T T T - and three S S S -solutions, so the solutions used give 6 + 1 + 1 + 1 + 1 = 10 6 + 1 + 1 + 1 + 1 = 10 6 + 1 + 1 + 1 + 1 = 10 matrices of order 668, pairwise inequivalent by their 4-profiles [10 ] . The data [83 ] contain these and further inequivalent matrices of order 668, at least 20 in all; the further ones are the matrix of § 5.6 and matrices obtained by reordering the blocks before assembly or by the convention R = ( { 1 ∣ x + y = − 1 } ) R = (\{1\mid x + y = -1\}) R = ({ 1 ∣ x + y = − 1 }) of the public files (§ 6.2 ).
Data availability. Theorem 1 rests only on Appendix A. The supplementary data [83 ] have not been publicly deposited.
Related work
Arrays and borders. Borders of widths 1, 2 and 4 are in the literature: width 1 in Paley’s construction [59 ] , width 2 in the constructions with two circulant cores [26 , 40 ] (see also [70 , 53 ] and the paragraph on Legendre pairs below), and width 4 in the array of Wallis and Whiteman [77 Thm. 4.17] . The closest construction we know is that of Momihara and Yamada [57 Thm. 4.1] , who border a two-block divisible difference family relative to a subgroup of index u − 1 u - 1 u − 1 by all rows but the first of a Hadamard matrix of order u u u , pulled back from the quotient group, with corner − 11 T -11^{\mathsf T} − 1 1 T , and obtain symmetric Hadamard matrices of order u 2 u^2 u 2 . Theorem 5, recovered from the released matrices as [23 Thm. 7] , has since given orders 2636 and 3964 (Kumar [45 ] ) and 5788 and 8476 (Egan et al.; 8476 had been settled earlier by Jones [35 ] , from T T T -matrices of order 163) with q = 4 q = 4 q = 4 and order 3356 (Kumar [45 ] ) with q = 8 q = 8 q = 8 , and a related border of width 12 relative to a subgroup of index 3 gave order 2148 [45 ] . Relative difference sets [25 ] are the divisible difference families of § 3.2 with no differences in N ∖ { 0 } N \setminus\{0\} N ∖ { 0 } .
Miyamoto’s construction and M M M -structures. Miyamoto’s main theorem [56 §4] gives a Hadamard matrix of order 8 m + 4 8m + 4 8 m + 4 from a pair of ( 0 , ± 1 ) (0, \pm1) ( 0 , ± 1 ) -matrices of order 4 m 4m 4 m whose sum and difference are ± 1 \pm1 ± 1 matrices, under a condition on row sums and one further condition on each matrix of the pair (§4.3). The four width-4 matrices of this paper, of orders 668, 716, 1676 and 1772, are instances of that theorem: the pair consists of the Goethals–Seidel arrays of the half-sums S f S_f S f and of the half-differences T f T_f T f of the two halves of the four blocks. What differs is the source of the pair. Miyamoto builds his pairs from conference matrices and other auxiliary matrices [56 ] [85], and the related constructions of Yamada [82 ] likewise start from an auxiliary Hadamard, skew-Hadamard or conference matrix of order comparable to the blocks. Our pairs were found by computer search: for orders 668, 716 and 1676 by solving the condition on the half-sums and the condition on the half-differences separately, which is possible because the two are tied only through their supports (§§§ 5.2 , § 5.3 ), and for order 1772 by lifting through two quotients (§ 5.4 ). The core of 668 was found with an analogous decomposition along Z 2 \mathbb{Z}_2 Z 2 , which has four parts (§ 5.6 ); Miyamoto’s theorem does not apply to it, and we make no statement relating the matrices with wider borders to his theorem. Seberry and Yamada restated Miyamoto’s theorem in terms of M M M -structures [64 Thm. 34] , [65 Thm. 8.10] and proved multiplication theorems for Hadamard and Williamson-type matrices in the same terms [64 , 66 ] ; see also [67 ] . Egan et al. note that a symmetry hypothesis is missing from Corollary 2 of [56 ] and Corollary 8.8(1) of [65 ] (see [23 Remark 8] ). That hypothesis concerns those corollaries, not the main theorem.
Legendre pairs. A Legendre pair of length ℓ \ell ℓ is a pair of ± 1 \pm1 ± 1 sequences a , b a,b a , b of length ℓ \ell ℓ with PAF a ( s ) + PAF b ( s ) = − 2 \operatorname{PAF}_a(s) + \operatorname{PAF}_b(s) = -2 PAF a ( s ) + PAF b ( s ) = − 2 for all s ≠ 0 s \ne0 s = 0 ; it gives a Hadamard matrix of order 2 ℓ + 2 2\ell+ 2 2 ℓ + 2 with two circulant cores and a border of width 2. The array, and the equivalent condition on a pair of subsets of an abelian group of odd order, go back to Szekeres [70 , 71 ] : his complementary difference sets are such pairs with one block skew, which he built from cyclotomic classes to obtain skew Hadamard matrices. The existence criterion with no skewness and no cyclotomic structure, for an arbitrary odd length, was formulated independently by Mednīanık [53 ] , as his basic lemma on Hadamard matrices of half-circulant type (two n n n -subsets of Z 2 n − 1 \mathbb{Z}_{2n-1} Z 2 n − 1 whose differences together cover every non-zero element exactly n n n times), and by Fletcher, Gysin and Seberry [26 ] , who named the pairs and searched for them by the discrete Fourier transform. Medianik’s Theorems 1 and 2 recover the prime lengths from quadratic residues, with the remark that the resulting matrices are not of the form of Paley’s matrices of the same order, and [54 ] adds products of twin primes. The conjecture that a Legendre pair exists for every odd ℓ \ell ℓ , Kotsireas’s structured Hadamard conjecture [37 ] , would imply the Hadamard conjecture. The length-333 conjecture of [38 ] mentioned in § 1.1 is of this kind; the matrices of order 668 given here are of a different form, and the Legendre quadruples of § 3.1 are the width-4 analogue.
Multipliers and matching. The Goethals–Seidel array is recalled in § 2 . With circulant blocks it generalises Williamson’s method [80 ] and has been the setting of most computer constructions since Đoković [14 ] . Infinite families of Williamson matrices are known [74 ] , but some odd orders have none: 35 [15 ] , and 47, 53 and 59 [32 ] . Blocks invariant under a multiplier group go back to Hunt and Wallis [34 ] (see also [30 ] ), and Đoković [17 , 18 ] and Đoković, Golubitsky and Kotsireas [20 ] combine them with candidate lists and meet-in-the-middle matching [41 ] , the method of five of our orders (§ 2.1 ).
Compression. Compression is a tool also used for difference sets [2 , 46 , 73 ] . As in [21 ] and the recent searches for Legendre pairs and periodic Golay pairs [42 , 43 , 52 , 72 ] , we solve the compressed problem first and lift its solutions afterwards. The change of variables of §4.3 is, along Z 2 \mathbb{Z}_2 Z 2 , Miyamoto’s decomposition [56 , 64 ] ; it is also the classical sum-and-difference device of base and T-sequences [65 , 75 ] , and 2 S 2S 2 S is the 2-compression of a [21 ] . Kotsireas, Koutschan and Winterhof [44 ] also treat the two cosets a ( 0 , ⋅ ) a(0,\cdot) a ( 0 , ⋅ ) , a ( 1 , ⋅ ) a(1,\cdot) a ( 1 , ⋅ ) separately, fixing one sum on each, whereas in the variables S , T S,T S , T all the constraints separate.
T-matrices. T-matrices go back to Cooper and Wallis [11 ] and, as four-symbol δ \delta δ -codes, to Turyn [75 ] ; they give Hadamard matrices of order 4 v 4v 4 v in the Goethals–Seidel array [65 Thm. 3.6] , and these constructions can be phrased in terms of orthogonal designs [28 ] . Their relation to the quadruples of this paper is that of Turyn [75 Thm. 2] . Identify the block index f f f with Z 2 2 \mathbb{Z}_2^2 Z 2 2 and put t θ ( x ) = 1 4 ∑ f θ ( f ) a f ( x ) t_\theta(x)=\frac{1}{4}\sum_f\theta(f)a_f(x) t θ ( x ) = 4 1 ∑ f θ ( f ) a f ( x ) for the four characters θ \theta θ of Z 2 2 \mathbb{Z}_2^2 Z 2 2 . Since the character table of Z 2 2 \mathbb{Z}_2^2 Z 2 2 is a Hadamard matrix of order 4,
∑ f PAF a f ( s ) = 4 ∑ θ PAF t θ ( s ) ( s ∈ G ) . (10) \sum_f \operatorname{PAF}_{a_f}(s)=4\sum_\theta\operatorname{PAF}_{t_\theta}(s)\qquad(s\in G). \tag*{(10)} f ∑ PAF a f ( s ) = 4 θ ∑ PAF t θ ( s ) ( s ∈ G ) . (10)
If ∏ f a f ( x ) = + 1 \prod_f a_f(x)=+1 ∏ f a f ( x ) = + 1 at every x x x , the t θ t_\theta t θ are ( 0 , ± 1 ) (0,\pm1) ( 0 , ± 1 ) -functions with disjoint supports covering G G G , and (2) says exactly that their group matrices are T-matrices; this is the case s = 1 s=1 s = 1 of the product theorem of Seberry and Yamada for M-structures [64 Thm. 4] , whose original version is Turyn’s [75 Thm. 9] , as stated in [23 §4] . None of the thirteen cores is of this kind, even after the moves of § 3.3 : for each of them, the number of x x x with ∏ f a f ( x ) = − 1 \prod_f a_f(x)=-1 ∏ f a f ( x ) = − 1 , minimised over translations and inversions of single blocks and over the choice of sign class, is between 19% and 37% of ∣ G ∣ |G| ∣ G ∣ . For ten of the cores this lies within the range found for random quadruples with the same row sums and multiplier group. The cores of orders 716 and 668 (width 4), which have arc supports, and the core of order 1436 are lower than about 99% of such quadruples: 25%, 25% and 19%, against medians of 29%, 28% and 24%. Orders 668 and 716 would also follow from Turyn-type sequences T T ( 56 ) TT(56) T T ( 56 ) and T T ( 60 ) TT(60) T T ( 60 ) , as Best, Đoković, Kharaghani and Ramp pointed out [4 ] (see [23 §3] ); T T ( n ) TT(n) T T ( n ) is known for even n ≤ 44 n\le44 n ≤ 44 [4 , 50 ] , and, by a further search of London and Kotsireas cited in [23 Table 3] , for n = 46 n=46 n = 46 , and that table lists the orders at which T-matrices are known, among them recent ones of Schneider [62 ] , Schumer [63 ] and Jones [35 ] . Kharaghani and Tayfeh-Rezaie obtained order 428 in this way, from Turyn-type sequences of length 36 [36 ] , and London [49 ] and London and Kotsireas [50 ] construct further Turyn-type sequences.
Low-autocorrelation sequences. The quantity F F F minimised in § 5.1 is, up to the factor 2 t 2t 2 t , the energy ∑ s ≠ 0 PAF a ( s ) \sum_{s\ne0}\operatorname{PAF}_a(s) ∑ s = 0 PAF a ( s ) of Bernasconi’s Ising model [3 ] with periodic boundary conditions. Configurations of the periodic model with a single off-peak autocorrelation value of least possible size (the perfect sequences of Mertens and Bessennodt, which are ground states) correspond to cyclic difference sets [55 ] , and conditions (2) , (3) and (4) are the analogous statements for four sequences with prescribed sums of autocorrelations. Objective functions of this kind underlie earlier heuristic and annealing searches for Hadamard matrices and complementary sequences [8 , 39 , 69 ] .
Analysis of the released matrices, and current status. Egan, Kotsireas, London and Ó Catháin [23 ] analysed the twelve matrices released in [1 ] : the groups, borders, multiplier groups and row sums of their generators, and the flatness of their spectra. The release gave the matrices without any account of how they were found, and their reading of the structure from the data alone, including the recovery of Theorem 5, is accurate in every particular that this paper can check. Their paper is also a survey of the constructions that reach orders up to 10 000. It gives matrices of sixteen orders that had no published construction, five of which Schumer [63 ] and Jones [35 ] had already posted; it notes twenty-two more that others settled while it was being written, most of them by Cooley [9 ] and Kumar [45 ] ; and it counts 95 orders up to 10 000 as open when it appeared, the least being 2396. This paper is confined to how thirteen matrices were found; theirs is the survey of the field as it now stands. Their list of open problems includes questions on group-developed matrices; for the general theory of such matrices see [33 , 13 ] . Kumar’s repository [45 ] holds matrices, each with a certificate and an exact verifier, at 34 of the orders that [7 Table 4] lists as unresolved, up to 11 804. Four of them, 3732, 4492, 5020 and 5932, are among the sixteen constructed in [23 ] , there with multiplier groups of the same orders 31, 33, 50 and 39; Kumar’s are dated in his repository to commits of 11 and 13 October 2026, with a first dated release on 14 October, and [23 ] appeared on 19 October. Cooley’s repository [9 ] has another matrix of order 3732, different from Kumar’s.
The width-4 array and its names. Proposition 2 appears in several forms. Spence [68 Thm. 2.1] states it for the cyclic group in terms of the complementary sets 4 − { 2 w ; w + 1 , w , w , w ; 2 w } 4-\{2w; w+1, w, w, w; 2w\} 4 − { 2 w ; w + 1 , w , w , w ; 2 w } (restated as [7 Thm. 7] ), and Yamada [82 Thm. 1] states the same border around a quaternion-type array. For blocks as in Proposition 2, the sets X f = { a f = − 1 } X_f = \{a_f = -1\} X f = { a f = − 1 } form a difference family [76 Lemma 1] with parameters ( 2 w ; w − 1 , w , w , w ; 2 w − 2 ) (2w; w-1, w, w, w; 2w-2) ( 2 w ; w − 1 , w , w , w ; 2 w − 2 ) , of a kind considered by Whiteman [78 ] and Spence [68 ] and called type H ∗ H^* H ∗ in [47 , 48 ] . Egan, Kotsireas, London and O Catháin call such quadruples Legendre quadruples [23 §2.1] .
Orders 892, 1132 and 1948. Lou, Xia and Xia [51 ] , which we have been unable to consult, describe a construction method for T-matrices of prime order 6 m + 1 = a 2 + 3 b 2 6m+1=a^2+3b^2 6 m + 1 = a 2 + 3 b 2 (which would give Hadamard matrices of order 4 ( 6 m + 1 ) 4(6m+1) 4 ( 6 m + 1 ) [65 ] ); its abstract names no order, and its predecessor [81 ] is a computer search reaching 6 m + 1 ≤ 79 6m+1 \le79 6 m + 1 ≤ 79 . The primes 223, 283 and 487 are of that form, but the later lists still give 892 [7 , 19 ] , 1132 and 1948 [7 ] as open, so as far as we can tell these orders are not settled there.
Acknowledgements
Acknowledgements. This work was supervised by Levent Alpöge, Saul Reynolds-Haertle and Philippe Voinov, who followed it with curiosity and encouragement and made no mathematical contribution. We thank Erisa Hasani, Abhinav Nellore and Rachel Ward for the corrections of attribution and emphasis that they proposed (§1.4) and for their help with the description of the solutions found without symmetry.
Disclosure
Disclosure. Erisa Hasani, Abhinav Nellore and Rachel Ward wish to disclose that they received no payment from Anthropic for their work on this paper and signed no non-disclosure agreement.
References
Appendix A. Defining data
Encoding of Table A2 . A block a f a_f a f on G = Z m 1 × ⋯ × Z m r G = \mathbb{Z}_{m_1} \times\cdots\times\mathbb{Z}_{m_r} G = Z m 1 × ⋯ × Z m r is the bit string ( 1 { a f ( x ) = − 1 } ) x ∈ G (1\{a_f(x)=-1\})_{x\in G} ( 1 { a f ( x ) = − 1 } ) x ∈ G , with x x x in lexicographic order of ( x 1 , … , x r ) (x_1,\ldots,x_r) ( x 1 , … , x r ) , 0 ≤ x i < m i 0 \leq x_i < m_i 0 ≤ x i < m i . It is written in hexadecimal, most significant bit first, zero-padded at the end to a multiple of four bits. The blocks are listed in the order a 1 , … , a 4 a_1,\ldots,a_4 a 1 , … , a 4 in which they enter K ( a 1 , … , a 4 ) K(a_1,\ldots,a_4) K ( a 1 , … , a 4 ) in (1) , with A f A_f A f and R R R as in § 1.5 .
For width b = 4 b=4 b = 4 the blocks are indexed cyclically (Z 2 w ≅ Z 2 × Z w \mathbb{Z}_{2w}\cong\mathbb{Z}_2\times\mathbb{Z}_w Z 2 w ≅ Z 2 × Z w by the Chinese remainder theorem). The four sequences on Z 2 w \mathbb{Z}_{2w} Z 2 w satisfy ∑ f PAF a f ( s ) = − 4 \sum_f \operatorname{PAF}_{a_f}(s)=-4 ∑ f PAF a f ( s ) = − 4 for s ≠ 0 s\ne0 s = 0 with row sums ( 2 , 0 , 0 , 0 ) (2,0,0,0) ( 2 , 0 , 0 , 0 ) , and the matrix is that of Proposition 2: the printed blocks go into it as they stand.
For order 1916 the blocks printed below are those of the released matrix, i.e. translates within Q Q Q of M M M -invariant blocks, the translation being the move that fits them to the printed frame. The M M M -invariance statement of § 5.5 refers to the untranslated blocks, and the row sums are ( 6 , 6 , 38 , 20 ) (6,6,38,20) ( 6 , 6 , 38 , 20 ) . For order 1436 the blocks are printed in the order ( − 14 , 18 , − 30 , 4 ) (-14,18,-30,4) ( − 14 , 18 , − 30 , 4 ) of their sums (row sums τ 2 \tau_2 τ 2 of § 5.8 ).
For b ≥ 12 b\geq12 b ≥ 12 the quotient map π : G → Q \pi:G\to Q π : G → Q is the projection to the first two coordinates (Q = Z 2 2 Q=\mathbb{Z}_2^2 Q = Z 2 2 ), to the first coordinate (Q = Z 6 Q=\mathbb{Z}_6 Q = Z 6 ), or x ↦ ( x 1 , x 2 , x 3 m o d 2 ) x\mapsto(x_1,x_2,x_3\bmod2) x ↦ ( x 1 , x 2 , x 3 mod 2 ) (Q = Z 2 3 Q=\mathbb{Z}_2^3 Q = Z 2 3 , for G = Z 2 × Z 2 × Z 8 × Z 11 G=\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_8\times\mathbb{Z}_{11} G = Z 2 × Z 2 × Z 8 × Z 11 ). Rows D D D and E E E list the b b b columns of D Q D_Q D Q and the b b b rows of E Q E_Q E Q , each a word of 4 q 4q 4 q bits (block position f = 1 , … , 4 f=1,\ldots,4 f = 1 , … , 4 major, Q Q Q in lexicographic order minor, bit 1 for entry − 1 -1 − 1 ) in hexadecimal. The corner is C = − E Q K β T D Q / ( 4 q ) C=-E_QK_\beta^TD_Q/(4q) C = − E Q K β T D Q / ( 4 q ) and H = ( C E D K ) H=\left(\begin{smallmatrix}C&E\\D&K\end{smallmatrix}\right) H = ( C D E K ) with D , E D,E D , E the pull-backs along π \pi π (Theorem 5 ).
Table A2 (PDF p. 25). Blocks and frames of the bordered constructions.
Glossary
Cell (§ 1.3 ): the group G G G , the multiplier group M M M and, for bordered arrays, the subgroup N N N . Core (§ 1.2 ): the four blocks of a bordered array; a width-b b b core or width-b b b matrix is one whose border has width b b b . Coset table (§ 3.2 ): the coset sums ( β f ) (\beta_f) ( β f ) modulo constants; admissible (Appendix C) if it meets the parity and spectral conditions. Word (§ 3.2 ): a vector in { ± 1 } Q \{\pm1\}^{Q} { ± 1 } Q with four balanced segments. Frame (§ 3.2 ): a pair ( D Q , E Q ) (D_Q,E_Q) ( D Q , E Q ) satisfying the hypotheses of Theorem 5 . Legendre quadruple (§ 3.1 , after [23 ] ): four ± 1 \pm1 ± 1 sequences satisfying (3) . M-structure (§4.3): an orthogonal matrix of order 4 t 4t 4 t divided into sixteen t × t t \times t t × t blocks, in the terminology of Seberry and Yamada [64 ] . Miyamoto’s decomposition (§4.3): a ( x , y ) = S ( y ) + ( − 1 ) x T ( y ) a(x,y)=S(y)+(-1)^xT(y) a ( x , y ) = S ( y ) + ( − 1 ) x T ( y ) for a block a a a on Z 2 × G ′ \mathbb{Z}_2 \times G' Z 2 × G ′ , where S S S and T T T are the half-sum and the half-difference of the two halves a ( 0 , ⋅ ) a(0,\mathord\cdot) a ( 0 , ⋅ ) and a ( 1 , ⋅ ) a(1,\mathord\cdot) a ( 1 , ⋅ ) of the block. Moves (§ 3.3 ): negating, translating or inverting single blocks, and permuting blocks. Support system (§4.3): the supports ( W 1 , … , W 4 ) (W_1,\ldots,W_4) ( W 1 , … , W 4 ) of the T f T_f T f ; feasible if ν ( s ) \nu(s) ν ( s ) is even and at least 4 for every s ≠ 0 s \ne0 s = 0 . θ \theta θ -part (§4.3): a ( θ ) = 1 2 ∑ x θ ( x ) a ( x , ⋅ ) a^{(\theta)}=\frac{1}{2}\sum_x\theta(x)a(x,\mathord\cdot) a ( θ ) = 2 1 ∑ x θ ( x ) a ( x , ⋅ ) . Fibre, mixed, pattern (§ 5.6 ): the vector a f ( ⋅ , y ) ∈ { ± 1 } Q a_f(\mathord\cdot,y)\in\{\pm1\}^{Q} a f ( ⋅ , y ) ∈ { ± 1 } Q ; a fibre with sum ± 2 \pm2 ± 2 ; a character or the label mixed for each fibre. Compressed solution (§ 4.2 ): a quadruple of compressions satisfying (5) ; two of them, on two quotients, are compatible (§ 4.4 ) if they are realised together by M M M -invariant blocks. Decompression (§ 4.4 ): an M M M -invariant ± 1 \pm1 ± 1 block with prescribed coset sums.
The frame enumerations
An admissible coset table is a quadruple of integer functions β f \beta_f β f on Q Q Q , taken modulo constants, whose values all have the parity of k = ∣ N ∣ k=|N| k = ∣ N ∣ (modulo constants, this says that the values of each β f \beta_f β f have a common parity) and which satisfies ∑ f ∣ β f ^ ( θ ) ∣ 2 = 4 ( q − 1 ) \sum_f|\widehat{\beta_f}(\theta)|^2=4(q-1) ∑ f ∣ β f ( θ ) ∣ 2 = 4 ( q − 1 ) for every θ ≠ 1 \theta\ne1 θ = 1 .
Moves (§ 3.3 ) change the core, and hence the matrix. To border every core it therefore suffices to frame one coset table in each class under the moves and to adjust the core within its class.
Isomorphisms. Call the frame problems of β \beta β and β ′ \beta' β ′ isomorphic if K β ′ = U K β V K_{\beta'}=UK_\beta V K β ′ = U K β V for signed permutation matrices U , V U,V U , V of the word coordinates that map words to words. Then ( D Q , E Q ) ↦ ( U D Q , E Q V ) (D_Q,E_Q)\mapsto(UD_Q,E_QV) ( D Q , E Q ) ↦ ( U D Q , E Q V ) is a bijection between their frames. A common automorphism ϕ \phi ϕ of Q Q Q applied to all four segments gives such an isomorphism from β \beta β to β ∘ ϕ \beta\circ\phi β ∘ ϕ , with U = V − 1 = I 4 ⊗ P ϕ U=V^{-1}=I_4\otimes P_\phi U = V − 1 = I 4 ⊗ P ϕ , where P ϕ P_\phi P ϕ is the permutation matrix of the automorphism, and a common translation by an element of order 2 2 2 gives one with U = I U=I U = I and V V V the corresponding permutation.
Counting. Frames are counted up to reordering and negating the columns of D Q D_Q D Q and, independently, the rows of E Q E_Q E Q (which changes only C C C ), not up to the moves.
An isomorphism from β \beta β to itself is a symmetry that can be imposed on a frame to shrink the search. We call a frame invariant under such a symmetry if the symmetry maps each column of D Q D_Q D Q to a column or to minus a column, and likewise each row of E Q E_Q E Q ; that is, invariant up to sign.
All frame searches below are depth-first searches over words, or over orbits of words under an imposed symmetry. They choose columns d d d of D Q D_Q D Q and rows e e e of E Q E_Q E Q alternately, keeping a new word if it is orthogonal to those already on its side and has ∣ e K β T d ∣ = 4 q |eK_{\beta}^{T}d|=4q ∣ e K β T d ∣ = 4 q against those on the other.
q = 4 q=4 q = 4 , width 12 12 12 . For Q = Z 2 2 Q=\mathbb{Z}_2^2 Q = Z 2 2 the six balanced vectors are the non-trivial characters and their negatives, and parity forces ( ∣ β f ^ ( θ ) ∣ ) f (|\widehat{\beta_f}(\theta)|)_f ( ∣ β f ( θ ) ∣ ) f to be the same arrangement of ( 2 , 2 , 2 , 0 ) (2,2,2,0) ( 2 , 2 , 2 , 0 ) for all three non-trivial characters. Indeed, write β f = c o n s t + 2 u f \beta_f=\mathrm{const}+2u_f β f = const + 2 u f with u f u_f u f integer-valued. For θ ≠ 1 \theta\ne1 θ = 1 , β f ^ ( θ ) = 2 u f ^ ( θ ) \widehat{\beta_f}(\theta)=2\widehat{u_f}(\theta) β f ( θ ) = 2 u f ( θ ) , and u f ^ ( θ ) ≡ ∑ c u f ( c ) \widehat{u_f}(\theta)\equiv\sum_c u_f(c) u f ( θ ) ≡ ∑ c u f ( c ) (mod 2 2 2 ) whatever θ \theta θ is; so each β f ^ ( θ ) \widehat{\beta_f}(\theta) β f ( θ ) is even, 12 = 4 + 4 + 4 + 0 12=4+4+4+0 12 = 4 + 4 + 4 + 0 is the only way to write 12 as a sum of four even squares, and the block with the 0 is the same for all three θ \theta θ . The four positions of the 0 and the signs of the nine values ± 2 \pm2 ± 2 give 4 ⋅ 4 ⋅ 2 9 = 2048 4\cdot4\cdot2^9=2048 4 ⋅ 4 ⋅ 2 9 = 2048 admissible coset tables. Of the 115 776 sets of 12 pairwise orthogonal words up to sign, exactly 9408 occur as the columns of a frame for a given admissible coset table, each with exactly one set of rows. These counts and the classes of Table C1 are results of our computer enumeration, on which independently written programs agree; Proposition 8 rests on them, and Theorem 1 does not.
Table C1. Admissible coset tables and frames for the quotients Q Q Q of order 4, 6, 8. Columns: ordered admissible tables; classes under the moves; classes under the moves and common automorphisms of Q Q Q ; frames found; adjustment of the core; orders using them.
q = 6 q=6 q = 6 , width 20 20 20 . For Q = Z 6 Q=\mathbb{Z}_6 Q = Z 6 only 2 of the 20 balanced vectors are ± \pm ± -characters. Since β f − k \beta_f-k β f − k is even and constants do not matter, the coset tables to be framed are the same for every k k k . For a representative of each of the 6624 classes under translation, inversion and negation applied to all four blocks at once there is a frame invariant under an involution of its frame problem, usually the half-turn c ↦ c + 3 c\mapsto c+3 c ↦ c + 3 on all four segments [83 ] . Common inversion, negation and translation by 3 are isomorphisms of the frame problem, so every core whose coset table lies in such a class can be bordered after at most a common translation of its four blocks.
q = 8 q = 8 q = 8 , width 28. For each of the three abelian groups of order 8, Q = Z 2 3 Q = Z_2^3 Q = Z 2 3 , Z 2 × Z 4 Z_2 \times Z_4 Z 2 × Z 4 , Z 8 Z_8 Z 8 , a frame exists for a representative of each class under the moves and common automorphisms, 16 classes in all, each exhibited in [83 ] with a core on Q × Z 3 Q \times Z_3 Q × Z 3 and the resulting Hadamard matrix of order 124. Call a coset table constant if each β f \beta_f β f is constant outside one common coset. The constant coset tables lie in a single class under the moves, for each Q Q Q . A Singer cycle of Z 2 3 Z_2^3 Z 2 3 is an automorphism of order 7 that permutes the seven non-zero elements cyclically. For the constant coset table over Z 2 3 Z_2^3 Z 2 3 a depth-first search over orbits of a Singer cycle finds a frame within a few hundred nodes, and this is the frame of the matrix of order 1436.
Estimated cost of the counted operations
This appendix estimates what the operations counted in Table 1 cost in processor time and in money. It does not report what was spent. It was written without the search programs or their logs (§ 1.4 ), and the hardware and the time actually used for the searches are not recorded in this paper.
The counts. The column log 2 \log_2 log 2 ops of Table 1 is the number of pair sums formed up to the first matrix (§ 4.1 ). Four entries are counts (orders 892, 1132, 1676, 1964); the others, marked ≈ \approx ≈ , are estimates from list sizes. The two largest, for orders 668 and 716, can be recomputed from § 5.2 and Table A3 . For the system of order 668, the lists of step (1) have 2 35.9 2^{35.9} 2 35.9 to 2 40.9 2^{40.9} 2 40.9 members and the two sides of a half hold 2 77.3 2^{77.3} 2 77.3 pairs together on the T T T half and 2 77.5 2^{77.5} 2 77.5 on the S S S half. A count of the kind in step (2) is the product of the four list sizes and, for each shift s s s , the probability that a sum of ν ( s ) \nu(s) ν ( s ) random signs (of ν ( s ) − 2 \nu(s)-2 ν ( s ) − 2 for the S S S half) takes the required value. One shift should be omitted, because the equations of the other shifts and the prescribed sums imply the equation there. This gives 2 16 2^{16} 2 16 –2 18 2^{18} 2 18 solutions per half, according to the shift omitted, in agreement with the 2 17 2^{17} 2 17 of step (2). A matching that visits its parts in random order therefore forms about 2 60 2^{60} 2 60 pair sums for each solution of a half. For order 716 the same computation gives 2 83.5 2^{83.5} 2 83.5 pairs, 2 15 2^{15} 2 15 –2 18 2^{18} 2 18 solutions and about 2 66 2^{66} 2 66 pair sums for each solution of a half. For the two halves together this is about 2 61 2^{61} 2 61 and 2 67 2^{67} 2 67 , where Table 1 has ≈ 59 \approx59 ≈ 59 and ≈ 66 \approx66 ≈ 66 for a matching that visits the likeliest parts first. The two entries are thus uncertain by a factor of several.
The rates. To turn counts into time we timed the two inner loops of a matching. The timing program, pairsum_bench.c, was written for this appendix and is appended to the TeX source of this paper; it is not one of the search programs (§ 6.4 ). Its data are autocorrelation vectors of random members of the first two lists of the T T T half at order 668, each stored as 41 bytes padded to 64. On one core of a 2.1 GHz Intel Xeon processor with AVX-512, in a virtual machine, we measured the following.
Forming a pair sum and testing each of its coordinates against a threshold, as in step (4) of § 5.2 , takes 0.8–1.2 ns: one 512-bit addition and one comparison per pair. The time does not depend on the fraction of pairs that pass.
Forming a pair sum, hashing it, and inserting it in or looking it up in a table that fits in the second-level cache takes 7–13 ns when the table is made of 64-byte buckets and 22–29 ns with plain open addressing, for vectors of 48 coordinates of 8 or 16 bits. With a table of 1 GiB it takes 65–105 ns, so the parts of § 4.1 should be small enough for the table to stay in the cache.
With both cores of the machine busy, the rates per core were the same. Table D1 accordingly allows 1–4 ns per pair sum for orders 668 and 716, where every pair sum is filtered and only those that pass are hashed, and 7–30 ns for the other orders, where every pair sum is hashed. The figure of 4 ns corresponds to a tenth of the pair sums passing the filter. The fraction that passed in the searches is not recorded; for the order-668 system, a threshold that keeps two thirds of the solutions passes 6 to 9 per cent of the pair sums.
The price. We take the list price of a rented server of the present generation with AVX-512: 192 cores for US$9.85 per hour on demand, that is US$0.051 per core-hour. The spot price of the same machine in the same week was about a quarter of this.2
What the table shows. First, the search for order 716 is in a class of its own: 2 ⋅ 10 7 2 \cdot10^7 2 ⋅ 1 0 7 to 8 ⋅ 10 7 8 \cdot10^7 8 ⋅ 1 0 7 core-hours, which is 12 to 49 years on one 192-core machine or 4 to 18 days on a thousand of them, and about US$1–4 million on demand. At the counts of Table 1 it is more than nine tenths of the total, and it remains the greater part if its count is too high by the factor of several allowed above. Second, three searches cost between 7 ⋅ 10 4 7 \cdot10^4 7 ⋅ 1 0 4 and 6 ⋅ 10 5 6 \cdot10^5 6 ⋅ 1 0 5 core-hours each, that is US$3 600 to US$33 000: order 668 with the border of width 4, and orders 1132 and 1964 by the circulant method. Third, the other nine searches together cost 1 100 to 4 900 core-hours, under US$300, nearly all of it for order 892, whose matching was run to completion. Each of the four searches with wide borders cost between a fraction of a core-hour and 150 core-hours.
The search of § 5.2 does not scale. From w = 83 w = 83 w = 83 to w = 89 w = 89 w = 89 its count rises by a factor of 2 7 2^7 2 7 , so it roughly doubles with each unit of w w w .
What the table leaves out. The figures are for the counted operations alone, at rates measured on a reference kernel. They exclude the generation of the lists, which for orders 668 and 716 have up to 2 43 2^{43} 2 43 members and cannot be held in memory; the four further support systems at w = 83 w = 83 w = 83 of Table 3 on which both halves were solved; the support systems and candidate sets that were searched without success, whose number is not recorded; and the preliminary screening mentioned in § 1.4 . Nor are they lower bounds. A faster kernel or a better-organised matching would reduce them, and we have not timed the loops on graphics processors, to which loop (a) is well suited.