Jump to main content
Circulant Hadamard

All Coefficients Become 1

Full overview · All Coefficients Become 1
Show the proof map

The exact sign formula for E(P) reduces to a polynomial with one in every coefficient position.

Lemma (Every coefficient has residue one). Let be a positive integer, and form from the same four sign polynomials as in Node 5.1. In ,

The polynomial is the all-ones polynomial.

The congruence means that every coefficient of is divisible by .

Proof from the two inputs

The exact formula from Node 5.1 is

The half-sum has integer coefficients. Since , its whole contribution is divisible by . Therefore

Write

Gaussian parity, proved in Node 5.2, says that for every . Reducing each coefficient gives the claimed all-ones polynomial.

This proves a congruence; the original coefficients of need not equal . The calculation uses only the common sign array, so it does not need the norm identities or the oddness of .

Evaluate at one

Substitution gives . If is odd, then

For , the nine coefficient positions become nine ones; four pairs vanish in characteristic two, leaving one. Oddness is used here, after the coefficient congruence has already been proved.

What the next nodes receive

Along with , retain the divisibilities established while forming :

Divisibility here is coefficientwise in the group ring. These differences supply the sign input for Node 6. The all-ones congruence will be used in the final contradiction after the product identities have been converted to an additive relation.

Source: the paper, Section 4, equations (4.5)–(4.9).

Back to Signs Become All Ones