Polynom over finite field

**Banach** · May 12th 2008, 02:07 PM

Hi people! I would like to show that the polynom f=x^4-16x^2+4 is reducible over any finite field K. Unfortunately I do not have any ideas how to do this (maybe by using that any element in K can be written as sum of two squares). Has anybody got a hint for me? This would be veeeery nice

. Nice greetings

**Isomorphism** · May 13th 2008, 01:22 AM

Originally Posted by Banach

Has really nobody got an idea...?

Do you have anymore information about K? Like the characteristic or something. As it stands now, I dont think what you said is true.

**Banach** · May 13th 2008, 01:44 AM

No, unfortunately this is all. I have already shown that it is irreducible over \IQ which is not of great help i suppose. A K is finite it follows easily that the characteristic is a prime p and |K|=p^n. I think the hint I gave in brackets in the first post is the key to the solution. I hope we can find it

?

PS: I am pretty sure that the claim is true

.

**Banach** · May 13th 2008, 07:25 AM

Isomorphism, have you had any idea concerning the problem?

**Opalg** · May 13th 2008, 07:34 AM

Originally Posted by Banach

I would like to show that the polynomial f(x)=x^4-16x^2+4 is reducible over any finite field K.

The polynomial f(x) can be factorised over the real field as

$x^4-16x^2+4 = (x^2-2)^2 - 12x^2 = (x^2-2+2\sqrt3\,x)(x^2-2-2\sqrt3\,x)$

or as

$x^4-16x^2+4 = (x^2+2)^2 - 20x^2 = (x^2+2+2\sqrt5\,x)(x^2+2-2\sqrt5\,x)$

or as

$x^4-16x^2+4 = (x^2-8)^2 - 60 = (x^2 - 8+2\sqrt{15})(x^2 - 8-2\sqrt{15})$ .

So $x^4-16x^2+4$ is reducible over any field of charactistic p for which any of the numbers 3, 5 or 15 is a quadratic residue mod p. But if 3 and 5 are quadratic non-residues (mod p), then 15 will be a quadratic residue (mod p). Therefore $x^4-16x^2+4$ is reducible over any field of finite charactistic.

**ThePerfectHacker** · May 13th 2008, 07:47 AM

Originally Posted by Opalg

So $x^4-16x^2+4$ is reducible over any field of charactistic p for which any of the numbers 3, 5 or 15 is a quadratic residue mod p. But if 3 and 5 are quadratic non-residues (mod p), then 15 will be a quadratic residue (mod p). Therefore $x^4-16x^2+4$ is reducible over any field of finite charactistic.

I was also trying to solve this with quadradic residues. But you managed to find how to do it.

. The only thing I am worried about is that was only established for finite fields $|K| = p$ . What about $|K| = p^n$ ? The concept of quadradic residues and non-residues no longer applies to such fields because they are not isomorphic to the modolu field. To get around this problem it might be sufficient to note that the prime subfield of $|K| = p^n$ is isomorphic to the modolu field and the argument follows.

**Opalg** · May 13th 2008, 08:08 AM

Originally Posted by ThePerfectHacker

The only thing I am worried about is that was only established for finite fields $|K| = p$ . What about $|K| = p^n$ ? The concept of quadradic residues and non-residues no longer applies to such fields because they are not isomorphic to the modolu field. To get around this problem it might be sufficient to note that the prime subfield of $|K| = p^n$ is isomorphic to the modolu field and the argument follows.

Exactly. I was careful to talk about the characteristic of K rather than the order of K. If char(K) = p then p is a prime, and GF(p) is embedded in K as multiples of the identity.

**Banach** · May 13th 2008, 08:15 AM

Thank you for your answers. The only problem is that i have not heard anything about quadradic residues yet. The hint i was given was: Any element in a finite field can be written as sum of 2 squares. Can you explain your solution to me using this argument since i do not know anything about quadradic residues? This would be very helpful...

**Banach** · May 13th 2008, 08:38 AM

Or if this is not possible, could you please explain your solution to me: Why is

reducible over any field of charactistic p for which any of the numbers 3, 5 or 15 is a quadratic residue mod p? Why does this follow out of the factorisations made by you? (You see, i still do not quite understand the idea of quadradic residues).

And secondly why is - in any finite field - either 3, 5 or 15 a quadradic residue? I hope you are patient with me

...

**Opalg** · May 13th 2008, 09:09 AM

Originally Posted by Banach

The hint i was given was: Any element in a finite field can be written as sum of 2 squares. Can you explain your solution to me using this argument since i do not know anything about quadradic residues? This would be very helpful...

I can't help you there. I didn't even know the theorem that every element in a finite field can be written as sum of two squares, and I don't see how to use it to tackle this problem.

Originally Posted by Banach

Or if this is not possible, could you please explain your solution to me: Why is

reducible over any field of charactistic p for which any of the numbers 3, 5 or 15 is a quadratic residue mod p? Why does this follow out of the factorisations made by you? (You see, i still do not quite understand the idea of quadradic residues).

And secondly why is - in any finite field - either 3, 5 or 15 a quadradic residue? I hope you are patient with me

...

This will be much easier.

A quadratic residue is simply a number that is a square (in a given field). For example, in the field $\mathbb{Z}_7$ the elements 1, 2 and 4 are quadratic residues ( $1 = 1^2,\;2 = 3^2,\; 4 = 2^2$ ). The other three nonzero elements of $\mathbb{Z}_7$ (3, 5 and 6) are quadratic non-residues because they are not equal to the square of any element of the field.

In the field $\mathbb{Z}_p$ of integers mod p (an odd prime), exactly half of the nonzero elements are quadratic residues, and they form a subgroup (under multiplication). The map from $\mathbb{Z}_p^*$ (the multiplicative group of nonzero elements of $\mathbb{Z}_p$ ) to the additive group $\mathbb{Z}_2$ which takes r to 0 if r is a quadratic residue, and to 1 if r is a quadratic non-residue, is a homomorphism. This shows that if r and s are quadratic non-residues (mod p) then their product rs is a quadratic residue. (In particular if 3 and 5 are quadratic non-residues then 15 will be a quadratic residue.)

So, to take a specific example: in the field $\mathbb{Z}_7$ , neither 3 nor 5 is a quadratic residue. But 15=1, which obviously has the square root 1. Now take the factorisation $x^4-16x^2+4 = (x^2 - 8+2\sqrt{15})(x^2 - 8-2\sqrt{15})$ , and replace √15 by 1. This gives the result $x^4-16x^2+4 = (x^2 - 8+2)(x^2 - 8-2) = (x^2 +1)(x^2 +4)$ over the field $\mathbb{Z}_7$ .

Another example: in $\mathbb{Z}_{13}$ , 3 is a quadratic residue, because 4^2 = 3. In the factorisation $x^4-16x^2+4 = (x^2-2+2\sqrt3\,x)(x^2-2-2\sqrt3\,x)$ , replace √3 by 4, and you get $x^4-16x^2+4 = (x^2-2+8x)(x^2-2-8x)$ over the field $\mathbb{Z}_{13}$ .

**Banach** · May 13th 2008, 09:53 AM

Thank you for your competent answer. This is what i thought it could be

. Alright it is clear to me that in any finite field that encloses 3 and 5, one of the elements 3, 5, 3*5 is a square. Now i understood that.

Therefore, i just have to finish off the cases where 3 and 5 do not belong to the field.
(1) char(K)=2, then f = (x^2*x^2)
(2) char(K)=3, then f = (x^2+1)^2
(3) char(K)=5, then f=(x^2+2)^2

It is |K|=p^n, p prime and p>5 for any other finite field K. This means that K encloses an isomorphic copy of Z/pZ and hence the elements 3 and 5. This finishes the proof.

Are these thoughts correkt?

**Banach** · May 13th 2008, 11:09 AM

Would you like to see the proof that in any finite field each Element can be written as sum of two squares?

**ThePerfectHacker** · May 13th 2008, 11:53 AM

Originally Posted by Opalg

The map from $\mathbb{Z}_p^*$ (the multiplicative group of nonzero elements of $\mathbb{Z}_p$ ) to the additive group $\mathbb{Z}_2$ which takes r to 0 if r is a quadratic residue, and to 1 if r is a quadratic non-residue, is a homomorphism.

Usually this map is defined to be 1 for residues and -1 for non-residues, called Legendre symbol (and 0 for the coset of 0).

Originally Posted by Banach

Would you like to see the proof that in any finite field each Element can be written as sum of two squares?

I would like to see your version of the proof.

**ThePerfectHacker** · May 13th 2008, 12:55 PM

Originally Posted by Banach

Would you like to see the proof that in any finite field each Element can be written as sum of two squares?

I was thinking about this theorem.
It seems to me we can use Jacobi sums not to just prove that any element can be written as a sum of two squares in $\mathbb{Z}_p$ but we can even count the number of ways this can be done.

(If $p$ is an odd prime).

1)Let $\chi : \mathbb{Z}^{\text{x}}_p \mapsto \mathbb{C}^{\text{x}}$ be a Dirichlet charachter. This means $\chi (ab) = \chi (a) \chi (b)$ . We also define $\chi (0) = 0$ . For example, the Legendre symbol is defined to be $\chi (a) = 1$ if $a$ is quadradic residue mod p, and $\chi (a) = -1$ if $a$ is a quadradic non-residue mod p. We also define $\chi (0) = 0$ . It is simple to check the the Legendre symbol is a Dirichlet charachter.

2)Given the equation over the finite field, $x^2 = a$ there are no solutions if $\chi (a) = -1$ . There are two solutions (if $x_0$ is one solution then $p-x_0$ is the other one) if $\chi (a) = 1$ . And there is precisely one solution if $\chi (a) = 0$ , i.e. $a=0$ and so $x=0$ is the only solution. Let $N(x^2 = a)$ be the number of solutions to the equation $x^2 = a$ . We can summarize by saying that $N(x^2 = a) = 1 + \chi (a)$ .

3)Suppose $r\not = 0$ . We wish to count the number of pairs $(x,y)$ so that $x^2 + y^2 = r$ . Note that the number of such pairs is equal to $\sum_{a+b=r}N(x^2=a)N(y^2=b)$ , where $a+b=r$ ranges over all elements in $\mathbb{Z}_p$ . By #2 we can write $\sum_{a+b=r} (1+\chi (a))(1+\chi (b)) = p + \sum_{a=0}^{p-1}\chi (a) + \sum_{b=0}^{p-1}\chi (b) + \sum_{a+b=r}\chi (a)\chi (b)$ . Here we use a simple fact that the sum of Legendre symbol over all values is zero. We are left with $p+\sum_{a+b=r}\chi (a)\chi (b)$ .

4)It remains to compute $\sum_{a+b=r}\chi(a)\chi (b)$ . Note this sum is equivalent to $\sum_{c+d=1}\chi (rc)\chi (rd)$ (here we using fact that $r\not = 0$ ). But, $\chi (rc)\chi (rd) = \chi (r)^2\chi (c) \chi (d) = \chi (c) \chi (d)$ .
Thus, we are left with $\sum_{c+d=1}\chi (c) \chi (d)$ .

5)Now, if $d\not =0$ then $\chi (d) = \chi ^{-1} (d)$ because $\chi (d) \chi (d) = 1$ .
Thus, $\sum_{c+d=1}\chi (c)\chi (d) = \sum_{c+d=1}^{d\not = 0}\chi (c) \chi^{-1} (d) = \sum_{c+d=1}^{d\not = 0}\chi (c/d) = \sum_{c\not = 1} \chi \left( \frac{c}{1-c} \right) =$ $\sum_{n\not = -1} \chi (n) = -\chi(-1)$

6)But $\chi (-1) = (-1)^{(p-1)/2}$ (this is a theorem about Legendre symbols). Thus, $N(x^2+y^2 = r) = p - (-1)^{(p-1)/2}$ . Since $p - (-1)^{(p-1)/2} > 0$ it follows every non-zero element is a sum of two squares. Of course zero is an element of two squares so every element is in fact a sum of two squares.

**Banach** · May 14th 2008, 07:21 AM

Thank you for this detailed reply. I do not understand everything that you have written but it sounds very interesting. Have to work into that a bit more!

Claim: In any finite field K each element can be written as sum of two squares.

Proof:
Let f be the grouphomomorphism K*->K*, a |-> a^2. We distinguish between 2 cases:

(1) |K|=2^n: Let b be in Ker(f) => 1=f(b)=b^2. Since 1= (-1), b=1 => f injective and as |K|< oo f is a Bijection, so any element in K is a square.

(2) |K|=p^n=q, p prime, p>2: Ker(f)={1, -1}. As K*/Ker(f) is isomorphic to Im(f) it follows from Lagrange that |K*|/|Ker(f)|=(q-1)/2=Im(f)=:A. Since 0 is also a square it follows: |A|=(q+1)/2.
Define now B:={x-b^2}, x in K. It easily follows that |B|=(q+1)/2. As |K|=q, at least one Element y is in A and B => y=z^2 and y=x-b^2 => x=b^2+z^2. This holds for any x in K, which finishes the proof.

Two more questions:
(1) Can you confirm my thoughts from post 11?
(2) Is there a kind of editor to produce formulas in this forum?

Nice greetings, Banach

Thread: Polynom over finite field

LinkBack

Thread Tools

Display

Polynom over finite field

Similar Math Help Forum Discussions

Finite Field

Splitting Field of a Polynomial over a Finite Field

finite field

Finite field

Finite Field

Search Tags