0

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?

Seetha Rama Raju Sanapala
  • 649
  • 1
  • 7
  • 17

1 Answers1

1

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)$$

Derek Elkins left SE
  • 485
  • 3
  • 7
  • 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. – Seetha Rama Raju Sanapala Mar 30 '16 at 10:58
  • 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. – Derek Elkins left SE Mar 30 '16 at 13:56