Full overview · Correlation IdentityShow the proof map
Each coefficient of h(X)h*(X) is a dot product with a cyclic shift of the original row.
The coefficient identity
Let be arbitrary integers and set in . For , write for the coefficient of in the unique representative of of degree less than .
Proposition. With all coefficient subscripts taken modulo ,
Proof. Expand in this group ring:
A term contributes to exactly when . Thus , which gives the formula. The list is the original list shifted places to the right, so the sum is its dot product with the first row.
Equivalently, the complete product is
The order-four calculation
For the first row :
Shift
Right-shifted row
Thus . The coefficient identity itself does not require sign coefficients; signs will enter when the constant coefficient is set equal to .
Output. One product records all cyclic dot products, for arbitrary integer rows.