Results 1 to 15 of 15

Math Help - Polynom over finite field

  1. #1
    Member
    Joined
    May 2008
    Posts
    75

    Cool Polynom over finite field

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Banach View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    75
    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 .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2008
    Posts
    75
    Isomorphism, have you had any idea concerning the problem?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Banach View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Opalg View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by ThePerfectHacker View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    May 2008
    Posts
    75
    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...
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    May 2008
    Posts
    75
    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 ...
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Banach View Post
    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.

    Quote Originally Posted by Banach View Post
    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}.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    May 2008
    Posts
    75
    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?
    Last edited by Banach; May 13th 2008 at 11:08 AM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    May 2008
    Posts
    75
    Would you like to see the proof that in any finite field each Element can be written as sum of two squares?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Opalg View Post
    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).

    Quote Originally Posted by Banach View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Banach View Post
    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.
    Last edited by ThePerfectHacker; May 13th 2008 at 01:15 PM.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    May 2008
    Posts
    75
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finite Field
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: April 18th 2011, 06:02 PM
  2. Splitting Field of a Polynomial over a Finite Field
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 1st 2011, 03:45 PM
  3. finite field
    Posted in the Advanced Algebra Forum
    Replies: 8
    Last Post: September 20th 2009, 02:58 AM
  4. Finite field
    Posted in the Advanced Algebra Forum
    Replies: 18
    Last Post: August 28th 2009, 07:26 PM
  5. Finite Field
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: February 9th 2009, 09:08 PM

Search Tags


/mathhelpforum @mathhelpforum