'shifted' polynomial preserves validity of Eisenstein irreducibility criterion of original, in finite fields?

1,118

Solution 1

If $F$ is any field, and $p$ is any polynomial over $F$, and $a$ is any element of $F$, then $p(x)$ is irreducible over $F$ if and only if $p(x+a)$ is irreduible over $F$. This has nothing to do with Eisenstein. The proof will be a good exercise for you.

EDIT: $x^2+1$ is irreducible over the integers but not over the integers modulo $2$.

Solution 2

For the first question, the answer is of course yes, because if $q(x) = p(x+a)$, then $p(x) = q(x-a)$, so if $q(x)=r(x)s(x)$, then $p(x)=r(x-a)s(x-a)$.

For the second question, the answer is no, for example $x^2+1$ is irreducible over $\mathbb{Z}$, but $(x+1)(x+1) = x^2 + 1$ over $\mathbb{Z}_2$.

Share:
1,118

Related videos on Youtube

Cris Stringfellow
Author by

Cris Stringfellow

Updated on August 01, 2022

Comments

  • Cris Stringfellow
    Cris Stringfellow over 1 year

    This is not really research level, but I know not where else to ask it.

    The Eisenstein criterion for polynomial irreducibility over rationals or integers permits shifting the original (primitive) polynomial by substituting (x + a) in place of the original variable x, for some integer a. If the shifted polynomial is irreducible, then so was the original, since this shifting is an automorphism on the ring of polynomials over the rationals.

    Is the same shifting permitted over finite fields, such that the irreducibility of the shifted polynomial p(x) over finite field GF(q) with a < q guarantees the irreducibility of the original polynomial?

    Also, a second question, somewhat related, if a polynomial is irreducible over Z, is it irreducible over any finite field?

    • Dilip Sarwate
      Dilip Sarwate almost 11 years
      $x^2+1$ is irreducible over $\mathbb Z$ but equals $(x+2)(x+3)$ over $\mathbb F_5$.
  • KCd
    KCd almost 11 years
    I don't think you're answering his second question. My suspicion is that the second question is whether a polynomial irreducible over the integers is irreducible over some finite field. (I have learned through experience that sometimes when people write "any" they mean "some" rather than "all".) The answer to the question is no, and the simplest example is $x^4 + 10x^2 + 1$, which is irreducible over the integers but is reducible mod $p$ for every prime number $p$.
  • Cris Stringfellow
    Cris Stringfellow almost 11 years
    I think you are right KCd. I believe I meant 'if it is irreducible over integers, does that mean that it is never reducible?' -- I still don't understand how that can be. Can't there be a few primes under which a polynomial is irreducible and then we can say, that is it, it is now irreducible under every prime. Why aren't integers good enough for making it irreducible everywhere.
  • Cris Stringfellow
    Cris Stringfellow almost 11 years
    p(x+a) = sum(j_k.(x+a)**k), p(x) = sum(j_k.x**k). p(x+a) = p(x) + ( p(a) - j_0 ) + ( h(x,a) - j_0 ). I tried but I got stuck here. Alfonso's equations doesn't really make sense to me.
  • Gerry Myerson
    Gerry Myerson almost 11 years
    Give Alfonso's equations another look. Alfonso is telling you that if $q$ is a shift of $p$ then factors of $q$ are (identical) shifts of factors of $p$.
  • Gerry Myerson
    Gerry Myerson almost 11 years
    Cris, given any finite set of primes, there is a polynomial which is irreducible modulo all of those primes, but reducible modulo infinitely many other primes. Given any two finite sets of primes, there is a polynomial irreducible modulo each prime in the first set, and reducible modulo each prime in the second set.
  • Cris Stringfellow
    Cris Stringfellow almost 11 years
    Okay I will look at this again.
  • KCd
    KCd almost 11 years
    Cris: To see how how a polynomial irreducible over the integers could be modulo all primes,let's look at $x^4 - 10x^2 + 1$. (I wrote previously $x^4+10x^2+1$, which also works, but I change signs for a reason I'll explain later.) It has four real roots: $\pm\sqrt{2}\pm\sqrt{3}$ for all 4 choices of signs. If you collect these in parts you get 3 factorizations:$(x^2-2\sqrt{2}x-1)(x^2+2\sqrt{2}x-1)$, $(x^2-2\sqrt{3}x-1)(x^2+2\sqrt{3}x-1)$, and $(x^2-(5+2\sqrt{6})(x^2-(5-2\sqrt{6}))$. Although these factorizations were found over the real numbers (continued...)
  • KCd
    KCd almost 11 years
    they would make sense mod $p$ if 2 is a square, 3 is a square, or 6 is a square mod $p$ (when use the mod $p$ square root in place of $\sqrt{2}$, $\sqrt{3}$, or $\sqrt{6}$ to give meaning to the relevant factorization mod $p$). From elementary number theory, it is known that for any two integers $a$ or $b$ and any prime number $p$, either $a$, $b$, or $ab$ is a square modulo $p$. Therefore at least one of those factorizations into quadratics will make sense mod $p$, no matter what prime $p$ you use. For instance, taking $p = 7$, 2 is a square mod 7: $2 \equiv 3^2 \bmod 7$. [continued...]
  • KCd
    KCd almost 11 years
    Using 3 in place of $\sqrt{2}$ in the first factorization, we find $x^4 - 10x^2 + 1 \equiv (x^2 - 6x-1)(x^2+6x-1) \bmod 7$. Voila! As for $x^4 + 10x^2+1$, which I said factors mod $p$ for all $p$ in my initial comment, it has no real roots but it has 4 complex roots: $i(\pm\sqrt{2}\pm\sqrt{3})$ for all 4 choices of sign. You can go through a similar argument with this polynomial, using the 3 possible quadratic factorizations, to see at least one of them is going to make sense mod $p$ for any prime $p$ (basically use $\sqrt{-2}$ and $\sqrt{-3}$ in place of $\sqrt{2}$ and $\sqrt{3}).
  • Alfonso Fernandez
    Alfonso Fernandez almost 11 years
    @KCd Could you post this as an answer so that it's more legible to us and to people looking for this question in the future, and so that we can upvote?
  • Cris Stringfellow
    Cris Stringfellow almost 11 years
    so if q(x) = p(x + a) then if q(x) has factors, then p(x+a) has factors. q(x) = r(x)s(x), then p(x) = r(x-a)s(x-a) [because p(x) = q(x-a)], so if s(x) is a constant, then s(x-a) is constant, so if q(x) is irreducible, then p(x) is irreducible, and vice versa. Is that correct?
  • Cris Stringfellow
    Cris Stringfellow almost 11 years
    Okay KCd I follow your argument. We get x4 - 3x2 + 1 mod 7 and this has a root at 3 because 3 is a square mod 7 and the condition of a root is that it must be a square. Would 4 also work since 4 is congruent to 5**2 mod 7? I tried 4 and it also == 6 mod 7. Interesting about a,b,ab and p. If the polynomial had roots at cuberoot(2), would the requirements for a root mod p be that the root was a cube mod p? Also, is there any rule like a,b,ab mod p having a square for other radicals?
  • Gerry Myerson
    Gerry Myerson almost 11 years
    Yes. ${}{}{}{}$
  • KCd
    KCd almost 11 years
    Cris: There is a more conceptual explanation of what's going on using Galois theory and algebraic number theory (the polynomial can be normal with a noncyclic Galois group), but that would require too much background to describe for you. The special case of degree 4 can be done by that trick with $a, b$, and $ab \bmod p$ without needing anything more advanced. But I assure you there is a more general way to understand such examples, although for cubic polynomials it doesn't use radicals the way you are hoping.
  • Cris Stringfellow
    Cris Stringfellow almost 11 years
    KCd Can you point me in the best direction to get started?