The circulant Hadamard conjecture

Proof. A ring generated over \Z by finitely many roots of unity is finitely generated as an abelian group: products of bounded powers of the roots span it. It is torsion-free because it is a subring of \C, and hence is free of finite rank. Every ideal, as a subgroup of this free abelian group, is finitely generated. Such a ring is therefore Noetherian, as are its localizations. This applies to A and to A[\xi], which is a localization of \Z[\eta,\xi].

We first determine the maximal ideal of A. Since p\nmid L, the polynomial X^L-1 has no repeated factor over \F_p. Thus \F_p[X]/(X^L-1) is a product of fields. Its quotient A_0/pA_0 is also a product of fields. Localizing at the chosen maximal ideal selects one field factor, so A/pA is a field and the maximal ideal of A is pA.

In a Noetherian local domain whose nonzero maximal ideal is generated by t, a nonzero nonunit can be divided by t. This division cannot continue indefinitely: the successive quotients would generate a strictly increasing chain of principal ideals, since equality at one step would, by cancellation, make t a unit. Thus every nonzero element is a unit times a power of t. Applied to A, this gives its integral valuation, with value 1 at p.

We now adjoin \xi. The polynomial \Phi_{p^k}(1+Y) is monic of degree D, has constant term p, and reduces to Y^D modulo p. The last assertion follows by reducing

in characteristic p. It is irreducible over \Frac(A) by Eisenstein’s argument. Here is the needed form of that argument. For a nonzero polynomial over \Frac(A), the minimum valuation of its coefficients is additive under multiplication: after scaling both polynomials to minimum zero, their nonzero reductions have nonzero product over the field A/pA. If a monic integral polynomial factors into monic polynomials, the two minima are at most zero and sum to zero; hence both factors have coefficients in A. A nontrivial factorization of \Phi_{p^k}(1+Y) would therefore reduce to two monic positive-degree factors of Y^D. Both constant terms would be divisible by p, contradicting the constant term p of their product.

It follows that A[\xi]\simeq A[X]/(\Phi_{p^k}(X)), giving the asserted basis. Every maximal ideal of this finite A-algebra contracts to a maximal ideal of A. Indeed, the quotient by such a maximal ideal is a field finite as a module over the corresponding quotient domain of A. The adjugate-matrix argument for multiplication on a finite generating set makes every element of that field integral over the subdomain. Applying a monic relation to the inverse of a nonzero element of the subdomain puts that inverse in the subdomain. The subdomain is therefore a field.

Write \pi=\xi-1 and k_0=A/pA. The reduction

has one maximal ideal. Thus A[\xi] is local with maximal ideal (p,\pi). The equation \Phi_{p^k}(1+\pi)=0 has the form

with the sum empty when D=1. The element u_\pi has residue one and is a unit. Hence the maximal ideal is (\pi), and p is a unit times \pi^D. The principal-ideal argument above now shows that every nonzero element of A[\xi] is a unit times a power of \pi, giving the stated valuation. Since p^\ell is a unit times \pi^{\ell D}, this description proves (2.3). The coefficient assertion follows from uniqueness in the free A-basis.□

Proof. For the matrix under consideration, the row norm (2.1) has already given n=2^{2s}u^2 as in (2.2). It remains to show s=1.

Project C_n onto C_{2^{2s}}. The image T of h has odd integer coefficients, each being a sum of u^2 signs, and

Suppose s\geq2. We describe an operation starting with

where every coefficient of T is odd. Use Lemma 2.1 with A=\Z_{(2)} and a primitive 2^k-th root \xi. Complex conjugation preserves A[\xi] and sends \xi-1 to the associate -\xi^{-1}(\xi-1). It therefore preserves the normalized valuation. Evaluating (2.4) gives

Write T=\sum_{j=0}^{2^k-1}t_jX^j. Its remainder modulo \Phi_{2^k}(X)=1+X^{2^{k-1}} is

The coefficient statement in Lemma 2.1, with \ell=t, shows that every displayed difference belongs to 2^t\Z_{(2)}. Each difference is an integer, so it is divisible by 2^t in \Z.

Let q:\Z[C_{2^k}]\to\Z[C_{2^{k-1}}] be the group projection. The coefficients of q(T)/2 are

They are odd integers: the two odd summands are congruent modulo 4, since t\geq2. Thus T'=q(T)/2 belongs to the smaller integer group ring. Projection commutes with the involution, and division of the projected norm by 4 gives

Starting with k=2s and t=s, perform this operation s-1 times. After j steps the indices are k=2s-j and t=s-j; every step starts with t\geq2. The final element has 2^{s+1} odd integer coefficients and product with its star equal to 4u^2. The identity coefficient of that product is the sum of the squares of those coefficients. Each odd square is 1 modulo 8, and 2^{s+1} is divisible by 8. The sum is therefore 0 modulo 8, whereas 4u^2 is 4 modulo 8. This contradiction proves s=1.□

Proof. All the values in the denominators are nonzero, since the product of the two corresponding values is the nonzero scalar p^e b. The ratios therefore begin as elements of \Frac(A[\rho]).

For e=1, the nonnegative integral valuations of F(1) and K(1) sum to 1, so one is a unit of A. Evaluation at \rho is congruent to evaluation at 1 modulo \rho-1. For that factor, the ratio is therefore a unit of residue 1. The two ratios multiply to 1, proving the same assertion for the other factor.

Suppose e\geq2. Let q:A[C_{p^e}]\to A[C_{p^{e-1}}] be the projection sending the chosen generator to the chosen generator. We will show that the projection of one factor is divisible by p in the smaller group ring. Evaluate at a primitive p^e-th root \xi, and put D=(p-1)p^{e-1} as in Lemma 2.1. The two nonnegative valuations sum to e, so at least one is at least 1. Interchange the factors if necessary so that F(\xi)\in pA[\xi].

Choose a polynomial representative of F and divide by the monic cyclotomic polynomial:

Since R(\xi)=F(\xi), the coefficient statement in Lemma 2.1 makes every coefficient of R divisible by p. Moreover q(\Phi_{p^e})=p. Thus q(F)\in pA[C_{p^{e-1}}], as required. Define

Then F'K'=p^{e-1}b. Cancellation of p is valid here because the target group ring is a free A-module. The evaluations at 1 and \rho factor through q, and scalar division cancels from their ratio. Thus both original comparison ratios are unchanged. Induction proves the assertion, whether the same factor or the other factor is divided at the next step.□

Proof. For (i), let d be the finite rank of the free additive group of B, as in the proof of Lemma 2.1. Multiplication by an element of B is thus an integer matrix. On complexifying this representation, the matrices for the generating roots of unity commute and have finite order. Each is diagonalizable, since its minimal polynomial divides some X^m-1, which has distinct complex roots. They are simultaneously diagonalizable: the eigenspaces of one are invariant under the others, and one repeats the argument on those eigenspaces.

On a common eigenvector, multiplication by any b\in B acts as a scalar \sigma(b). This is a well-defined unital ring homomorphism because it comes from the multiplication representation, so all relations between the root generators are respected. The multiplication matrix of z is diagonal in the same basis, with eigenvalues \lambda_1,\ldots,\lambda_d of modulus one. For each positive integer a, its a-th power has an integer characteristic polynomial. The coefficient of degree d-j has absolute value at most \binom dj. Only finitely many such polynomials can occur, so the union of their sets of roots is finite. Each sequence \lambda_j^a therefore takes only finitely many values. Since \lambda_j\ne0, two equal powers imply that \lambda_j has finite order. A common multiple of these orders makes the multiplication matrix the identity; applying it to 1\in B proves that a positive power of z is 1.

For (ii), write the order as p^a m with p\nmid m. If m>1, raising the root to the p^a-th power gives an element \zeta of order m and residue 1. In a domain, (\zeta-1)(1+\zeta+\cdots+\zeta^{m-1})=0 then implies

Its reduction says m=0 in the residue field, a contradiction. Thus m=1.□

Proof. Fix p\in I and a maximal ideal \m of B containing p. Let

Put

with empty products equal to 1. The root orders 4 and q\in I\setminus\{p\} are pairwise coprime, so \eta is a primitive L-th root, p\nmid L, and each original root is a power of \eta. Thus A_0=\Z[\eta] has the form required by Lemma 2.1. The ideal \m_0 is maximal: it is prime and contains p, and A_0/pA_0 is a product of fields as in that lemma.

Let p^e be the order of the p-component, so e=v_p(u^2). For p\notin S, evaluate every other component in xx^*=u^2 according to \chi_S, leaving the p-generator as a variable. This ring homomorphism produces two factors F,K\in A_0[C_{p^e}] with

Both factors already have coefficients in A_0: in the image of x^*, Gaussian coefficients are conjugated and the evaluated roots are inverted, and these operations preserve A_0. After localization, Lemma 3.1 therefore applies to these two factors. It gives

Every denominator inverted in A lies outside \m, so the natural inclusion of A[\rho_p] in B_{\m} is defined. In the residue field of B_{\m}, characteristic p gives (\rho_p-1)^p=\rho_p^p-1=0. Hence \rho_p-1 has residue zero, and the units in (3.4) retain residue 1 in B_{\m}. Pairing S with S\cup\{p\} yields the identity

Thus \Delta(x) is a unit of residue 1 in B_{\m}. The left side of (3.5) is the same element when the pairing direction changes. Applying the argument for every p\mid u and every maximal ideal over p gives this local conclusion at all of those ideals.

At a maximal ideal containing none of the prime divisors of u, the scalar u^2 is a unit. Equation (3.2) then makes every x_S a unit there. Consequently \Delta(x) belongs to B_{\m} for every maximal ideal \m of B. The intersection of these localizations inside \Frac(B) is B. Indeed, if z\notin B, the ideal

is proper. A maximal ideal \m containing it cannot have z\in B_{\m}: such membership would give z=a/s with s\notin\m, whereas sz=a\in B puts s in D_z. This proves \Delta(x)\in B.

Every unital homomorphism \sigma:B\to\C sends the root generators to roots of unity and commutes with complex conjugation on their integer polynomials. Applying it to (3.2) gives |\sigma(x_S)|=u. In particular these images are nonzero. Let P_0 and Q_0 be the products of the x_S with \eps_S=1 and \eps_S=-1, respectively. Then \Delta(x)=P_0/Q_0, and the preceding nonvanishing gives \sigma(Q_0)\ne0. Applying \sigma to Q_0\Delta(x)=P_0 in B therefore evaluates the fraction in (3.3). Since I\ne\varnothing,

It follows that |\sigma(\Delta(x))|=1. Lemma 3.3(i) makes \Delta(x) a root of unity.

For each p\in I, there is a maximal ideal of B containing p: the additive group of B is free of positive finite rank, so B/pB\ne0. At that ideal \Delta(x) has residue 1, so Lemma 3.3(ii) makes its order a power of p. The assertions about odd order and two distinct prime divisors follow.□

Proof. The expression 1+tL is a unit because it has residue 1, and L is unique because O is a domain and t\ne0. The exact identities

prove closure under multiplication and inversion. Reducing modulo \n proves additivity and the inverse rule.□

Proof of Theorem 1.1. The 1\times1 matrix (1) is an example, as is the circulant matrix with first row (1,1,1,-1) at order four; its three nontrivial autocorrelations vanish.

Suppose there were an example of another order. By Proposition 2.2, its order is 4u^2 with u>1 odd. Write P=C_{u^2} and use the coprime decomposition C_{4u^2}=C_4\times P. For a generator Z of C_4, write the first-row element as

This decomposition reindexes the coefficients of the row, so every coefficient of every H_j is a sign. Turyn’s Lemma 8 [17, p. 337] studies the four coset counts under an additional hypothesis on the ideals generated by the three nonprincipal character values; here each H_j records the signs at all elements of P. The normalized partial evaluations at Z=1,-1,i are

The fourth normalized evaluation, at Z=-i, is the coefficientwise conjugate of g. The coefficients of c and d are integers because their numerators are sums of four odd integers. The two half-differences in g are integral as well. Hence c,d\in\Z[P] and g\in\Z[i][P]. Evaluation at Z=1,-1,i commutes with the involution, so hh^*=4u^2 gives

Use the fixed notation I,B,\chi_S,x_S,\eps_S from Section 3, and set

Proposition 3.4 shows that R and W are roots of unity of odd order. Indeed, a quotient of roots whose orders divide odd integers m and n has order dividing mn. This applies even when an individual alternating product is nontrivial.

Choose a maximal ideal \m of B containing 2, which exists because B/2B\ne0, and put

All residues in the rest of the proof lie in this one field k. Every c_S,d_S,g_S is a unit of O, since its product with its complex conjugate is the odd integer u^2. The image of i in k is 1: in characteristic two, (i-1)^2=0, and k is a field. Thus 2,1+i,1-i belong to \n, and 2 and 1+i are nonzero in the characteristic-zero domain O.

For every S\subseteq I, define the local units

Expanding the alternating products gives

We now compare how these two families differ from 1.

Put b=(H_1+H_3)/2\in\Z[P]. Direct subtraction in \Z[i][P] gives the two exact differences

The common sign coefficients control the last bracket. Let J=\sum_{z\in P}z. Each coefficient of H_2+iH_3 has the form \alpha+i\beta, with \alpha,\beta\in\{-1,1\}, and differs from 1+i by an element of 2\Z[i]. Hence

The first difference in (4.5) has a factor 2. After substituting (4.6), the second has a factor 1+i, because i-1=i(1+i) and 2=(1+i)(1-i). Evaluating and dividing by the unit c_S therefore gives the following integral first-order terms in O:

The right sides establish the integrality of the two quotients. In particular

Adding the exact formulas makes the contribution of b_S disappear after reduction:

The displayed subgroup memberships give residue 1 for every r_S and w_S, and therefore for R and W. The orders of R and W are odd, so Lemma 3.3(ii) in residue characteristic two gives the exact equalities

A related character comparison of Leung and Schmidt also forces a root of unity of odd order to equal one by reducing modulo two [5, author manuscript, proof of Theorem 3.5, p. 10]. Lemma 4.1 applies with t=2 and with t=1+i. For the two families it gives

Both maps take values in k, reducing their respective integral quotients modulo the same maximal ideal \n. Apply them to the products in (4.4), using (4.10); the homomorphism and inverse rules give

Adding these identities in k and using (4.9) yields

For S\ne\varnothing, the character \chi_S is nontrivial. Choose z\in P with \chi_S(z)\ne1. Since multiplication by z permutes the summands of J, evaluation gives (\chi_S(z)-1)J_S=0 in the domain B, and hence J_S=0. For S=\varnothing, one has J_{\varnothing}=|P|=u^2 and \eps_{\varnothing}=1. The sum in (4.11) is therefore the unit u^2/c_{\varnothing} of O. Its residue cannot be zero. This contradiction excludes every order greater than four.□

Proof of Corollary 1.2. Suppose first that a is a Barker sequence of even length n>2. Its periodic autocorrelation at a nontrivial shift is

The product of the n sign summands in P_a(t) is (\prod_j a_j)^2=1, so an even number of those summands are negative. Consequently P_a(t)\equiv n\pmod4. Also C_a(t)\equiv n-t\pmod2. For t=2, both C_a(2) and C_a(n-2) are even; the Barker bound makes them zero. Thus P_a(2)=0, and 4\mid n. For every nontrivial shift, the Barker bounds give |P_a(t)|\leq2, while the congruence gives P_a(t)\equiv0\pmod4. Hence all these periodic autocorrelations vanish. The cyclic shifts of a form a real circulant Hadamard matrix. This classical implication appears in Turyn and Storer [16, p. 395, footnote 2]; see also [17, p. 330]. Theorem 1.1 now forces n=4. The only possible even lengths are therefore 2 and 4.

For odd n>1, Turyn and Storer proved nonexistence above length 13 [16]; the later proof of Schmidt and Willms [14, Theorem 1] gives the exact list n\in\{3,5,7,11,13\}. Examples exist at every listed length. The following table uses the examples recorded in [14, Section 1]. Here + and - denote 1 and -1; direct substitution in C_a(t) verifies the Barker property in each row.

□