Jump to main content
Circulant Hadamard

The Nontrivial Roots Cancel the Ones

Full overview · The Nontrivial Roots Cancel the Ones
Show the proof map

Every nonempty subset gives a nontrivial root at which the all-ones polynomial vanishes exactly.

Lemma (Vanishing away from one). Let be odd, , and let for a nonempty subset of the distinct prime divisors of . Each is a primitive th root. Then

This is an exact equality before any reduction modulo .

The all-ones polynomial

Let be odd, let be its distinct prime divisors, and use the primitive roots from Node 4. Define

The empty product is . For a nonempty subset , put . The orders of these roots are pairwise coprime, so has order exactly .

To check this, its order divides . For any , raising to the power kills all the other factors and leaves , since does not divide . Thus its order contains every prime factor of the squarefree integer , and must be .

In particular, and , because divides .

A finite geometric sum

The polynomial identity

therefore gives

This is an exact equality in the characteristic-zero domain

Cancel the nonzero factor in this domain to obtain

No cancellation in the reduction ring is needed. The value is already zero before reducing modulo .

Nine terms in three groups

For and , the nine terms are three copies of the same three roots:

Each group of three complex vectors closes into an equilateral triangle. The general geometric-sum identity is the same cancellation for every nontrivial evaluation used in the proof.

Output. Every nonempty-subset evaluation of vanishes exactly.

Source: the paper, Section 4, the evaluation of the all-ones sum after equation (4.11).

Back to The Final Contradiction