Let α = 1 + a1x + a2x2 + ... where an = 1 if every block of zeros in the binary expansion of n has even length, 0 otherwise. Prove that, if we calculate in the field of two elements, then α3 + xα + 1 = 0. [For example, calculating in this field, (1 + x)2 = 1 + x + x + x2 = 1 + x2.]
Solution
α2 = 1 + ∑ an2x2n because 2 = 0. Also an2 = an, so α2 = 1 + ∑ anx2n. The expression for α3 is not so convenient, but we notice that if we multiply the relation in the question by α then we get the powers 1, 2, 4 and clearly α4 = 1 + ∑ anx4n.
So we now consider α4 + xα2 + α. It is convenient to consider separately the coefficients of x4n, x4n+2 and x2n+1.
Evidently the coefficient of x4n is an + a4n. But a4n = an, since the binary expansion of 4n is just that for n with two zeros added at the end. Hence an + a4n = 0. [This does not deal with the coefficient of x0, but that is clearly 1 + 1 = 0 also.]
The coefficient of x4n+2 is just a4n+2. But the binary expansion of 4n+2 ends ... 10, so a4n+2 = 0.
Finally, the coefficient of x2n+1 is a2n+1 + an. But the binary expansion of 2n+1 is the same as that for n with an extra 1 added at the end, so a2n+1 = an and a2n+1 + an = 0 also.
We have established that α4 + xα2 + α = 0, but α ≠ 0, so α3 + xα + 1 = 0 as required.
© John Scholes
jscholes@kalva.demon.co.uk
1 Jan 2001