Jump to main content
Circulant Hadamard

Identify E(P) and Add the Sums

Full overview · Identify E(P) and Add the Sums
Show the proof map

Adding the two linear sums produces the alternating sum of normalized evaluations.

Lemma (The vanishing alternating sum). Let be odd, let be its distinct prime divisors, and put , with empty product . For the polynomials from the common sign array, set

The exact product identities from Node 6 imply

in .

The same combination as Node 5

Recall the polynomial

Both polynomial quotients are exact, with Gaussian-integer coefficients. Write , , , and . Evaluating and dividing by the unit gives the exact identity in

Node 7.3 shows that the alternating sum of each term on the left vanishes modulo . Add those two congruences in and use this identity term by term. Define

We obtain the general conclusion

The alternating signs come from splitting even and odd subsets before reduction. In the characteristic-two quotient, minus and plus coincide, but keeping these signs records how the sum arose from the exact product identities.

The two-evaluation picture

For , the subsets give and . The sum has two terms:

The values of acquire the same factor when passing from to . Since is a fixed complex-linear combination of them, it also satisfies . The nonzero denominator satisfies , so

Here exactly. With several distinct prime divisors, the general argument gives the congruence above without asserting one common rotation of all the evaluations.

Output. . This proof used the exact quotients defining . The Node 7 overview already combines this with the all-ones condition to finish . For general odd , Node 8 applies that condition to the full alternating sum and completes the argument.

Source: the paper, Section 4, the additive step leading to equation (4.11). The general all-ones substitution is developed in Node 8.

Back to From Products to Sums