Jump to main content
Circulant Hadamard

Project to a Power-of-Two Cycle

Full overview · Project to a Power-of-Two Cycle
Show the proof map

Group positions by their residue on a shorter cycle; each new coefficient is an odd sum of signs.

Lemma (Projection to the power-of-two cycle). Write , where and is odd, so . Projecting a hypothetical sign polynomial to the cycle of length gives a polynomial with odd integer coefficients and

Every positive integer has a unique power of two times an odd part. The notation keeps the already chosen in .

Since divides , reducing exponents modulo defines a ring map from to the smaller group ring. Explicitly,

Each is a sum of the odd number of signs, so it is odd. These coefficients can exceed in absolute value; only their oddness is needed.

The projection preserves multiplication and sends to the inverse of the image of . It therefore commutes with star. Applying it to gives the claimed identity, with the same scalar . For , the four residue classes modulo each collect nine signs.

Source: the paper, Section 2.

Back to Restriction on the Order