Jump to main content
Circulant Hadamard

Fold the Cycle

Full overview · Fold the Cycle
Show the proof map

Average opposite coefficients to halve the cycle while preserving oddness and dividing the scalar norm by four.

Lemma (One fold). Suppose has odd coefficients on a cycle of length and , with and odd. Averaging opposite coefficients gives an integer polynomial with odd coefficients on the cycle of length and

Node 2.4 gives , hence modulo . Write . Then

is an odd integer. For instance, and average to .

Let reduce exponents modulo . Opposite coefficients add under this ring map, so , where . Projection commutes with star, giving

The integer group ring is free as an abelian group, so equality can be divided coefficientwise by . This proves the new norm identity.

For the iteration, suppose and start with Node 2.3's polynomial , with length and norm . Inductively, after folds, for ,

and all coefficients are odd. The case is the projection. If , then , so the one-fold lemma applies and proves the next case. After exactly folds, the length is and the norm is . This is the endpoint used in Node 2.6.

Source: the paper, Section 2.

Back to Restriction on the Order