What is special about the theorem that over GF(2), $f^2(X) = f(X^2)$? There is a some 10-line proof for the same in "page no.42, Shu Lin, Daniel J. Costello-Error Control Coding (2nd Edition)-Prentice Hall (2004)" I think the fact is more general and can be proved straight away. I feel that $f^m(X) = f(X^n)$ because in GF(2), $A^m=A=A^n$ where A is any polynomial, variable or constant from/over GF(2)and m and n are any two positive integers. Am I missing some important point here?


You are confusing polynomials, elements of $\text{GF}(2)[X]$, with coefficients, elements of $\text{GF}(2)$. Admittedly, it's certainly the case that as functions $\text{GF}(2)\to\text{GF}(2)$, any polynomial (or any function at all) will be equal to its (pointwise) power for any exponent greater than 0 which no doubt adds to the confusion. Still, as polynomials (roughly, finite lists of coefficients), they need not be equal. For example, $X^2 \neq X$ in $\text{GF}(2)[X]$ simply by definition. With fields of characteristic $0$, evaluation is injective as a function $F[X]\to F^F$, so conflating polynomials with the functions they represent is not as much of a problem.

So for $f(X) = 1+X$, $$f(X)^3 = (1+X)^3 = 1 + 3X + 3X^2 + X^3 = 1 + X + X^2 + X^3 \neq 1+X^3 = f(X^3)$$

  • $\begingroup$ In the polynomials over GF(2), how many solutions does 1+$X^{10}$ = 0 have? Over complex field we know that it has 10 solutions. $\endgroup$ Mar 30 '16 at 10:58
  • $\begingroup$ Like normal, we try to factor into linear factors. From the theorem referenced, we immediately see that it factors as $(1+X^5)^2$, and $1+X^5$ factors as $(1+X)(1+X+X^2+X^3+X^4)$. By substituting each of $1$ and $0$ into $1+X+X^2+X^3+X^4$ we see that it has no root and so no linear factors. In total, $1+X^{10} = 0$ has solution $1$ with multiplicity $2$. You would need to extend the field if you want to get the other solutions. $\endgroup$ Mar 30 '16 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.