0
$\begingroup$

Suppose $f(x)=x^n+x^{n-1}+x^{n-2}+\cdots +x+1$ is a polynomial of degree $n$ defined over $\Bbb{Z}_2[x]$. When $a$, $b \in \Bbb{Z}_2$, we have $(a + b)^2 = a^2 + b^2$. This idea can be extended to any number of variables, that is, $(a_1+a_2+\cdots+a_r)^2=a_1^2+a_2^2+\cdots+a_r^2$, where $a_i \in \Bbb{2}$. Use this fact to help prove that if $t$ is a root of $f(x)$, then $t^2$ is a root of $f(x)$.

I understand that in $\mathbb{Z}_2$, the only elements are $0$ and $1$. $0^2=0$ and $1^2=1$. Is this all I need to prove that if $t$ is a root, so is $t^2$? Or am I missing something?

$\endgroup$
  • $\begingroup$ What’s the question? $\endgroup$ – Lubin Oct 9 at 18:38
  • $\begingroup$ Welcome to Math.SE! The community here prefers/expects questions to include something of what the asker knows. (What have you tried? Where are you stuck? etc) This information helps answerers tailor their responses to best serve you, without wasting time (theirs or yours) telling you things you already know or using techniques with which you are unfamiliar. (Plus, it helps convince people that you aren't simply trying to get them to do your homework for you.) Since comments are easily overlooked, edit your question to add clarifications. $\endgroup$ – Blue Oct 9 at 18:39
  • $\begingroup$ I understand that in Z2, the only elements are 0 and 1. 0^2=0 and 1^2=1. Is this all I need to prove that if t is a root, so is t^2? Or am I missing something? Thanks! $\endgroup$ – Candace Shortt Oct 9 at 18:54
  • 1
    $\begingroup$ You're missing something. The coefficients of your polynomial need to be in $\Bbb Z_2[x]$ but $t$ could be in some extension of that field. I suggest you edit your question to include the thought you expressed in your comment. That will help demonstrate that you are attempting to solve the problem yourself. $\endgroup$ – Robert Shore Oct 9 at 19:41
  • $\begingroup$ @CandaceShortt hows it looking? Still need any help? $\endgroup$ – C. Brendel Oct 10 at 8:12
2
$\begingroup$

HINT:

The fact that $t$ is a root means that

$$ f(t)=t^n+t^{n-1}+\ldots t^2+t+1=0. $$

Over the given field you have that

$$ (a+b)^2=a^2+b^2 $$

which is extendable for more terms, so

$$ (a+b+c)^2=a^2+b^2+c^2 $$

and so on.

What happens when you take

$$ t^n+t^{n-1}+\ldots t^2+t+1=0 $$

and raise both sides to the power of $2$?

Compare it with $f(t^2)$.

Hope this helps, otherwise ask in the comments

$\endgroup$
2
$\begingroup$

Given a polynomial $f\in\mathbb{Z}_2[x]$ it doesn't have to have a root in $\mathbb{Z}_2$. An example would be $f=x^4+x+1$ or more applicable to your case $g=x^4+x^3+x^2+x+1$. You can check that just by plugging $0$ and $1$ into the equations: $$f(0)=0^4+0+1=1\ne0\text{ and } f(1)=1^4+1+1=3=1\ne 0$$ aswell as $$g(0)=1\text{ and } g(1)=1$$ What now? There's a theorem in algebra that says that for any polynomial $f$ of degree $n$ over some field $K$ there is a bigger field $L$ that contains $K$ such that $f$ splits into exactly $n$ linear factors. The smallest such field is called to splitting field of $f$ over $K$. But splitting into linear factors means we have zeros in this extension field of $K$. The standard example is $f=x^2+1$ over the field $\mathbb{R}$ where $f$ does not have roots! The extension field where $f$ splits turns out to be $\mathbb{C}$, i.e. $f=x^2+1=(x+i)(x-i)$, so we have the roots $i$ and $-i$ in the extension $\mathbb{C}$ of $f$ over $\mathbb{R}$.

As it turns out every field $L$ (not only a splitting field of some polynomial) containing the field $K$ has the same characteristic as $K$, so $\text{char}(L)=\text{char}(K)$.

So now turning to your problem: Given the polynomial $f=x^n+x^{n-1}+\dots+x+1$ in $\mathbb{Z}_2[x]$ there is a field $L$ containing $\mathbb{Z}_2$ such that $f$ has exactly $n$-roots in $L$. Your exercise is probably to show that given a root $t\in L$ then $t^2$ is also such a root (If your exercise restricts the variable purely to $\mathbb{Z}_2$ then the exercise would be trivial, as $t^2=t$ for either $0$ or $1$. So lets assume otherwise). We find that: \begin{align} f(t^2)&=(t^2)^n+(t^2)^{n-1}+\dots+(t^2)+1\\&=(t^n)^2+(t^{n-1})^2+\dots+t^2+1^2 \end{align} Notice that in the last line I replaced $1$ with $1^2$. As hinted at in your exercise we have that $(x+y)^2=x^2+y^2$ in $\mathbb{Z}_2$. This holds in any field of characteristic $2$ (we have the same effect with $(x+y)^p$ for a field of characteristic $p$ - this is called the Frobenius homomorphism if you are intersted) and as we said any field extension of $\mathbb{Z}_2$ also has characterstic $2$ so especially our splitting field $L$ and we can use the neat fact of Frobenius: \begin{align} f(t^2)&=(t^n)^2+(t^{n-1})^2+\dots+t^2+1^2\\&=(t^n+t^{n-1}+\dots+t+1)^2\\&=(f(t))^2\\&=0^2\\&=0 \end{align} so $t^2$ is a root of $f$ aswell!

Any question? I'll gladly answer :)

$\endgroup$

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.