Vrftsjtryk

$p(x) = x^4 + x +6$ .

I was to find if there is any root of multiplicity greater than $1$ in the field of characteristics $p$.

I was suggested to check every element of the $F_p$.

But a filed of characteristics $P$ means a field of order ${P^K}$ ..Why we did not consider the other elements of $F_{p^k}$?

Can anyone make me understand in simple language ?

Let us look at the question you have given again.

Given the polynomial $p(x) = x^4 +x + 6$, for which $q in mathbb N$ prime, is it true that $p(x)$ has a multiple root in "the field of characteristic $q$".

The question answered by egreg which was attached in the comments by you, has pretty much the same question, except that certain values of $q$ are given for checking.

This tells us that "the field of characteristic $q$" probably stands for $mathbb F_q$, which is the unique (upto isomorphism) field of $q$ elements, for example $mathbb Z over qmathbb Z$.

Let us recall what a multiple root means.

For this, we first state the "long division" theorem for fields :

If $f(x),g(x) in K[x]$ are two polynomials, with $g(x)$ non-zero, then there exist two polynomials $q(x)$ and $r(x)$ , such that $deg r < deg q$, and $f(x) = q(x)g(x) + r(x)$.

This is similar to polynomial long division, but applies in any field.

We all know what it means to be a root : in some generality, given a ring $R$ , an element $a in S$ where $S$ is an extension ring of $R$ (i.e. a ring containing $R$ as a subring) is said to be a root of $f(x) in R[x]$ if $f(a) = 0$, where $f(a)$ is an element of $S$, given by substituting $a$ in place of $x$ in $f$.

Now, we have the famous "remainder theorem" for figuring out when an element is a root of a polynomial : this is a corollary of the long division procedure.

Remainder Theorem : Let $f in K[x]$, where $K$ is a field. Let $L$ be an extension field of $K$(so, $f(x) in L[x]$ also, since the coefficients of $f$ lie in $K$ which lies inside $L$), and let $a in L$. Then, there exists a polynomial $q(x) in L[x]$ such that $f(x) = (x-a)q(x) + f(a)$.

Its corollary is :

As a consequence, $a$ is a root of $f$ if and only if $f(x)$ is a multiple of $(x-a)$ in the extension which $a$ belongs to.

Now, what does a multiple root mean? For this, we define multiplicity :

Given $f(x) in K[x]$ and $a in L$ a field extension of $K$ such that $a$ is a root of $f(x)$, the multiplicity of $a$ is the largest value of $k geq 1$ such that $(x-a)^k$ is a multiple of $f(x)$ in $L[x]$.

In particular,

$a$ is said to be a multiple root of $f(x)$ if the multiplicity of $a$ is greater than $1$ i.e. $(x-a)^2$ is a multiple of $f(x)$.

In particular, by the remainder theorem, $a$ is a multiple root of $f(x)$ implies that $a$ is a root, implies that $f(a) = 0$.

We add to this the following theorem : every polynomial in $K[x]$ of degree $n$ (in one variable) has at most $n$ roots , multiplicity included, in any extension field of $K$.

I briefly touch upon algebraic closure here. Given a field $F$, we say that a field $K$ is an algebraic closure of $F$, if $K$ is a field extension of $F$, and given any polynomial $f in F[x]$, all the roots of $F$ lie over $K$.

The fact is, that the algebraic closure of any finite field of characteristic $p$, is the union of all finite fields of characteristic $p$.

That is, given $f(x) in F_{p^k}[x]$, the roots of $f$ all lie in the infinite union $cup_{i=1}^infty F_{p^i}$.

In particular, since $f$ has only as many roots as its degree, the roots of $f$ all lie in $F_{p^N}$ for some large enough $N$ depending on $f$ (the union above is increasing, so being in a finite union of these sets is akin to being in the largest set).

How do we find multiple roots? Well, that can be done in two ways. egreg suggested a more elementary way, I suggested the more conventional way.

What egreg has done, is the following : To check if $a$ is a multiple root of $f$, we use the long division procedure to divide $x^4 + x + 6$ by $(x -a)^2$, where $a$ is treated like a constant.

This leads to the following :
$$
x^4 + x + 6 = (x-a)^2(x^2+2ax+3a^2) + ((4a^3+1)x + (6-3a^4)) tag{*}
$$

I won't explain the long division : do it just like how you do it for ordinary polynomials, and it will work out.

The above is an equality of polynomials in any field.

So, this means that $a$ is a multiple root if and only if the remainder term, which has been calculated as $(4a^3+1)x + (6-3a^4)$ , is zero.

A polynomial is equal to zero if and only if its coefficients are zero, that is if and only if $4a^3+1$ and $6-3a^4$ are both zero.

Where, equality to zero is different for different fields. For example, we have $2 = 0 in mathbb F_2$, but $2 neq 0 in mathbb F_3$.

Let us start solving the problem now. First of all, we need to note that we are interpreting $x^4+x+6$ as a polynomial over the finite field $mathbb F_q[x]$ and finding when a multiple root occurs, for each $q$.

Now, the roots of $x^4+x+6$ over $mathbb F_q[x]$, for each $q$, will all occur in $F_{q^k}$ for some $k$, because of the nature of the algebraic closure of $F_q[x]$. What that means, is that the equation $(*)$ needs to be considered only in finite fields $F_{q^k}$. That is, the remainder term , and the resulting equalities, are all equalities in $F_{q^k}$.

Crisply put : $a$ is a multiple root of $x^4+x+6$ over $F_{q}$, if and only if $4a^3+1 = 0$ and $6-3a^4 = 0$, where equality holds in some $F_{q^k}$ (basically, the one in which $a$ lies, since being a root of $x^4+x+6$ it must lie in some $F_{q^k}$). egreg checks for each $q$ , whether or not the second condition holds.

He starts with fields of characteristic $2$. So, the remainder term is going to lie in a field $F_{2^k}$. But he notes, that $4a^3 + 1 = 1 in mathbb F_{2^k}$, because $4a^3$ is always a multiple of $2$, and $F_{2^k}$ is of characteristic $2$. This means, that the remainder term has a non-zero $x$ coefficient, so cannot be zero in $F_{2^k}$. This is why, in fields of characteristic $2$, there can be no multiple root of $x^4+x+6$. (Note : nowhere above was the value of $k$ used : this is why egreg does not need to mention it in his answer, but I am doing so).

What about characteristic three? Here, again the remainder terms are being considered in $F_{3^k}$ for some $k$. But then, $6 - 3a^4 = 0 in mathbb F_{3^k}$ for every $k$, by the fact that the characteristic is $3$. For the second term, he performs reduction : $4a^3+1 = a^3+1$ in $F_{3^k}$ by the characteristic $3$ property. So the question is : can $a^3+1 = 0$ happen? It can , with $a= -1$. Hence, here, the remainder term can be made zero by taking $a = -1$. Hence, $-1$ is a multiple root of $x^4+x+6$ modulo $3$. As it turns out, $-1 in mathbb F_3$ itself, so we did not need to go into an extension for equality of the remainder terms.

Then comes the rest, which requires a somewhat separate section.

Note that $a = 0$ can never be a multiple root of $x^4+x+6$, because the remainder term, in any field, will have non-zero $x$ coeffcient ($4a^3+1$ becomes $1$). So $a neq 0$ is assumed. Usually, this means that $a$ is going to be inverted soon in the argument.

Now, egreg performs a brilliant manipulation : given that $4a^3+1 =0$ and $6-3a^4=0$, he wants to remove the large powers of $a$, so he does : $3a(4a^3+1) + 4(6-3a^4) = 0$, which simplifies to $3a+24 = 0$.

Now, if this inequality held in a field of characteristic $2$ or characteristic $3$, then this equation would simplify further, since $24$ is a multiple of $2$ and $3$.

However, if the chracteristic is not one of these, then we get $3(a+8) =0$, and since we are in an integral domain, and $3 neq 0$, we get $a = -8$. Conclusion : $a = -8$ is the only possibility for a multiple root of $x^4+x+6$ over $F_q$, where $q neq 2,3$ is prime. In other words, if $a$ is a multiple root of $x^4+x+6$ over $F_q$ for some $q neq 2,3$, then necessarily $a = -8$.

What are we going to do now? Check when $-8$ is a multiple root, of course, because it is sometimes, and it is not sometimes. How do we check? By plugging it into the remainder term. Plugging it in : $4a^3+1$ becomes $-2047$, and $6-3a^4$ gives $-12282$.

We want a field, where both these quantities $-2047$ and $-12282$ are zero. Of course, they are zero in a field of characteristic $q$, if and only if $q$ divides each of them. It is easy to check that $2047$ actually divides $12282$, and $2047 = 23 times 89$, so the only fields that work out are $mathbb F_{23}$ and $mathbb F_{89}$.

That is , the remainder term will be zero in $F_{23}$ and $F_{89}$ (we need not take powers, since $a = -8$ belongs to the original field itself).

Consequently, the description of the answer is the following :

• $x^4+x+6$ over $F_{q}$ has no multiple roots in $F_{q^k}$, if $q neq 3,23,89$.




• $x^4+x+6$ over $F_3$ has a multiple root $1$, and over $F_{23}$ and $F_{89}$ hass a multiple root $-8$.

Using Wolfram alpha, you can check that $x^4+x+6$ factorizes as $x(x+1)^3$ in $F_3$, then as $(x+8)^2(x^2+7x+8)$ in $F_{23}$, and $(x+8)^2(x+28)(x+45)$ in $F_{89}$.

This gives a complete answer to the problem, using egreg's approach.

To get on with my approach, we define the "formal derivative" of $f(x) in K[x]$, where $K$ is either a finite field or a number field, as the usual derivative $f'$ (The reason we need to be "formal" is because we are inventing the definition here, not deriving it by introducing limits / differential quotients etc). So for example, the formal derivative of $2x^2 + 3x+4$ is $4x+3$. However, when considered modulo $3$ for example, the derivative is just $x$ now.

The formal derivative allows us to capture multiple roots very well, for the following reason : suppose that $f$ is a polynomial in $K[x]$, and suppose $f$ has a multiple root $a$ in some extension $L$. Then, $f = (x-a)^2 times q(x)$ by the long division procedure, and taking the derivative using the product rule (it applies, one can check that) $f' = (x-a) times ((x-a)q'(x) + q(x))$. From the remainder theorem, we see that $f'(a) = 0$, or that $a$ is a root of $f$ and of $f'$. Or, $f$ and $f'$ have a common root, in some extension of $K$.

Conversely, if $f$ has no multiple roots, then one can check by going to the algebraic closure, that $f$ and $f'$ do not have common roots in any extension of $K$.

So, the question of $f$ having a multiple root boils down to $f$ and $f'$ sharing a multiple root in some extension of $K$.

Now, at this point, we have the Euclidean algorithm : something that finds a greatest common divisor of two polynomials, in a given field. I am sure you must know this algorithm : if not, look it up. It is similar to the one on the natural numbers.

In our case, we have $x^4+x+6$, whose formal derivative is $4x^3+1$. We have to find the gcd of these polynomials. I will explain. The $gcd$ will not change if we take $4(x^4+x+6)$ instead of $x^4+x+6$ unless we are in characteristic two, since this will just be a constant non-zero multiple of the original. In char two, this polynomial will be zero, so we will deal with that separately.

We see that $4(x^4 + x+6) - x(4x^3+1) = 3(x+8)$. This is just the general $gcd$ procedure, first step.

Next, $4x^3+1 = (x+8)(4x^2-32x+256) - 2047$, is the $gcd$ procedure, second step. We conclude, from the Eulidean algorithm on the polynomial ring $mathbb Q[x]$, that the $gcd$ is $1$, since here the remainder term is constant.

But that is the gcd for rational polynomials. Some steps above will collapse for finite fields, especially those for which any of the polynomial coefficients will collapse.

Let us look at the equation in step $1$ above. We have, first in char two, that the derivative is $1$, so there is no multiple root. In char $3$, the right hand side is zero, so in fact the algorithm stops there with the gcd equal to $4x^3+1$. So there is a multiple root here. For other characteristics, the right hand side is not zero, so we can proceed to look at other characteristics in equation $2$.

Here, we see that the remainder, which is $-2047$, is zero only in characteristic $23$
and characteristic $89$. So, there are multiple roots in these fields. For every other characteristic, the gcd is a non-zero constant, so the algorithm gives gcd 1 for every other char, hence giving the complete list of primes in which there is a multiple root.

So this is my way of doing things. Alternately, here is what the hint was suggesting to you.

The point is, that I mentioned earlier that $f$ has a multiple root if and only if $f$ and $f'$ shared a common root in some extension of $K$. This is exactly what your hint is : go forth to extensions of $F_q$, namely $F_{q^k}$, and find common roots of $f$ and $f'$.

However, in our case, $f' = 4x^3+1$ is a cubic polynomial. And these are special. Why?

Remember that degrees add when we multiply polynomials. That is, the degree of $fg$ is the sum of the degrees of $f$ and $g$. Now, if $f'$ is a product of two polynomials, then one of them must be degree less than or equal to $1$(Use the above fact). By the remainder theorem theorem, either $f'$ is irreducible or has a root. Has a root where? In $F_q$, of course, since it is over $F_q$ as a polynomial. Consequently, we only need to look for common roots of $f$ and $f'$ in $F_q$ and not any larger extension, because $f'$ will certainly have a root in $F_q$ if it is reducible.

But, in general this will not be true . Two polynomials may have non-trivial gcd, but not share a root over $F_q$ : such a root may be shared over a larger extension. In our case, it so happens that we need not go further.

So your procedure, will be to substitute different values in $F_q$ only, into $f$ and $f'$ and check what works. Of course, this is not working well, because having to deal with substituting $1,...,89$ for example with $F_{89}$ is not feasible. It is suggested that you follow either egreg or me for this sort of a problem next time round.