Jump to main content
Circulant Hadamard
Back to Proof map

Restriction on the Order

Full overview · Restriction on the Order
Show the proof map


2.1. Evaluate at 1

Dig in deeper

Undergraduate foundation

Substituting respects the relation . Every positive and negative power becomes one, so and

The row sum is an integer, hence is a square. The order-four row has sum ; an order- candidate would need sum or .


2.2. Pair the Dot-Product Terms

Dig in deeper

Undergraduate foundation

Choose two distinct rows, possible since . If their dot product has positive terms and negative terms, orthogonality gives , while . Thus is even.

Since is also a square, its positive square root is even. Writing gives

The remaining steps prove that this same is odd.


2.3. Project to a Power-of-Two Cycle

Write with and odd. Then . Reduce exponents modulo , defining

Each new coefficient sums signs, so it is odd. Projection preserves products and star, hence on the shorter cycle. For order , this collects nine signs into each of four positions; the resulting odd coefficients need not be signs.


2.4. Compare Opposite Coefficients

Dig in deeper

Accepted black box · Lemma 2.1

Suppose on a cycle of length , with integer coefficients and odd. Evaluate at a primitive th root . The specialized cyclotomic basis and valuation from Lemma 2.1 give : conjugation preserves , and the product has valuation .

Since , the basis coefficients of are the opposite differences. The coefficient statement therefore gives

For order , divisibility by forces opposite signs to agree, so the eighth shift repeats the row. The leaf proves the general deduction and states the standard cyclotomic input precisely.


2.5. Fold the Cycle

When , opposite odd coefficients agree modulo . Writing a pair as , its average is the odd integer . Project to the half-length cycle and divide by two. The new polynomial satisfies

Starting at , induction gives after folds. Every step with starts with , so it preserves odd coefficients. After folds, the length is and the norm is .


2.6. Odd Squares Modulo 8

If , the endpoint has odd coefficients . Taking the identity coefficient of its norm gives

Every odd square is modulo : for , , and is even. The left side is thus modulo , since its number of terms is a multiple of eight. The right side is modulo because is odd.

This contradiction forces , so is odd and .

Back to Proof map