Let α = 1 + a_{1}x + a_{2}x^{2} + ... where a_{n} = 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 + x^{2} = 1 + x^{2}.]

**Solution**

α^{2} = 1 + ∑ a_{n}^{2}x^{2n} because 2 = 0. Also a_{n}^{2} = a_{n}, so α^{2} = 1 + ∑ a_{n}x^{2n}. 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 + ∑ a_{n}x^{4n}.

So we now consider α^{4} + xα^{2} + α. It is convenient to consider separately the coefficients of x^{4n}, x^{4n+2} and x^{2n+1}.

Evidently the coefficient of x^{4n} is a_{n} + a_{4n}. But a_{4n} = a_{n}, since the binary expansion of 4n is just that for n with two zeros added at the end. Hence a_{n} + a_{4n} = 0. [This does not deal with the coefficient of x^{0}, but that is clearly 1 + 1 = 0 also.]

The coefficient of x^{4n+2} is just a_{4n+2}. But the binary expansion of 4n+2 ends ... 10, so a_{4n+2} = 0.

Finally, the coefficient of x^{2n+1} is a_{2n+1} + a_{n}. But the binary expansion of 2n+1 is the same as that for n with an extra 1 added at the end, so a_{2n+1} = a_{n} and a_{2n+1} + a_{n} = 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