Jump to main content
Circulant Hadamard

Cancel Before Reducing

Full overview · Cancel Before Reducing
Show the proof map

Cancel the common factor in characteristic zero before reducing the two resulting sums modulo one plus i.

Lemma (Cancel before reducing). In , let be either or . If satisfy , then

Applied to the equal products from Node 7.1, this makes each of the two alternating sums of divided differences vanish in the same quotient ring.

Combine the two inputs

Let be the distinct prime divisors of , put , and abbreviate , , . Node 7.1 gives equal products over even and odd subsets. Node 7.2 expands each side exactly. For either family, subtracting the two sides cancels the constant terms and gives an equality of the form

Here is the sum of the even-subset linear terms minus the sum of the odd-subset linear terms. The element collects the difference of the two remaining terms after factoring out .

The ring is a domain, and both choices of , namely and , are nonzero. Cancel in this original ring:

Only now reduce modulo . Both choices of belong to this ideal, since . Hence .

Apply this to both products

For the family, use . The cancellation gives

for some . For the family, use :

for some . The quotients in these sums were formed as elements of in Node 7.2; we are reducing those existing elements.

Reducing the original product equality first would lose the information: every factor becomes . We cannot divide by the residue of , because that residue is zero. Cancellation in is the step that preserves the linear terms. The quotient ring need not be a field or a domain.

When , each side has one factor, so both remainders vanish. The two displayed sums are then exactly zero, agreeing with the common rotation picture.

Output. Two alternating sums vanish modulo in the same ring. They can now be added term by term.

Source: the paper, Lemma 4.1 and its application after equation (4.10).

Back to From Products to Sums