Open Journal of Discrete Mathematics
Vol.09 No.02(2019), Article ID:91574,10 pages
10.4236/ojdm.2019.92006
Irreducible Polynomials in ℤ[x] That Are Reducible Modulo All Primes
Shiv Gupta
Department of Mathematics, West Chester University, West Chester, USA
Copyright © 2019 by author(s) and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: December 20, 2018; Accepted: March 30, 2019; Published: April 2, 2019
ABSTRACT
The polynomial is irreducible in but is locally reducible, that is, it factors modulo p for all primes p. In this paper we investigate this phenomenon and prove that for any composite natural number N there are monic irreducible polynomials in which are reducible modulo every prime.
Keywords:
Irreducible Polynomial, Reducible Polynomial, Galois Theory
1. Introduction
The polynomials of the title of this article have been discussed by Brandl [1] , and Guralnick et al. [2] . Brandl’s paper excludes those N which are such that . These are precisely the composite integers N for which there is only one abstract group of order N. The paper by Guralnick et al. does show the existence of such polynomials for all composite N’s. Our proof of the same is different, more elementary, and in some cases even constructive.
We shall first enumerate the known results which we shall use in this article. Several of these results are true more generally but we shall state them as needed in this article.
1) Let be a non-constant polynomial. Then the Galois group of f(x) over acts transitively on its roots if and only if f(x) is a power of an irreducible polynomial over .
2) Let be finite normal extensions that is, splitting fields of some polynomial. Let denote the compositum of the fields , that is, the smallest subfield of containing . Then is a normal extension of and if and are coprime. Then
3) Every finite solvable group can be realized as a Galois group of some polynomials over . Same is true of the symmetric groups and alternating groups . We shall only need this result for cyclic groups, Frobenius groups and for the groups and [3] [4] and [5] .
4) Let be an irreducible polynomials of degree n. Let be its roots. Let r be an integer, and . Let denote the polynomial whose roots are all sums of r different . Then and and have the same splitting field [6] .
5) Let be a monic irreducible polynomial of degree n and p a prime which does not divide the discriminant of f(x). Let be the Galois group of over . Suppose that modulo p the polynomial factors into irreducible polynomials of degrees so . Then there is such that as a permutation on the n roots of , , where is acyclic permutation of length for . See [7] .
6) Let N be any composite natural number and be a monic irreducible polynomial of degree N whose Galois group over does not have any element of order N. Then is reducible modulo every prime. This is an immediate consequence of (5) above.
2. Theorem and Proof
Theorem: For every composite natural number N there is a monic irreducible polynomial of degree N which is reducible modulo every prime.
Case I N is not square-free
We write where and p is a prime which does not divide m. Let be any non-cyclic group of order and a cyclic group of order m. Let be an irreducible polynomial of degree with Galois group isomorphic to and be an irreducible polynomial of degree m with Galois group isomorphic to . Let and be splitting fields of and respectively. Let be the compositum of the fields and . Then is of degree N over and is isomorphic to and so it does not have any element of order N. Let α be any algebraic integer such that . Let be the minimum polynomial of α. Then is a monic irreducible polynomial of degree N and its Galois group does not have any element of order N and therefore has the desired property.
Case II N is square-free and gcd(N, φ(N)) > 1
In this case we can write where p, q are primes, p divides and . Let be a non-abelian group of order pq and a cyclic group of order m. Just as in the previous case we get a monic irreducible polynomial in of degree N whose Galois group does not contain an elementof order N.
Case III, N is square-free and gcd(N, φ(N)) = 1
In this case N is necessarily odd. First we assume that N is a product of just two primes. So let , where p and q are distinct primes, and p does not divide . Let t be the order of p modulo q. So is the smallest integer such that . Let be an elementary Abelian p-group of order and be a group of order q. We note that is isomorphic to and so its order is divisible by q. Let be the semi-direct product of by . Evidently G is not a direct product of and . Therefore is not a normal subgroup of G. We claim that is its own normalizer in G. For otherwisethe index of the normalizer of in G would be , for some r, 1 ≤ r < t which would contradict the fact that t is the smallest integer satisfying . Since has prime order q it is disjoint from its conjugates. Therefore G is a Frobenius group of order and every non-identity element of induces a fixed-point-free automorphism of .
Let be a normal extension of with Galois group isomorphic to G. Then . Let H be a subgroup of G of order and let be its fixed subfield.
Then by FTGT ({Fundamental Theorem of Galois Theory}) the field is of degree pq over . We also note that as H is not a normal subgroup of G, is not a normal extension of . Let α be an algebraic integer such that and let be its minimal polynomial over . Then is irreducible of degree pq.
We claim that is the splitting field of (i.e. it is the normal closure of the field ) and G is its Galois group over .
If the normal closure of were a proper subfield of then it would imply that G has a proper normal subgroup of order where , but this is not possible, as G is a Frobenius group. So is a monic irreducible polynomials of degree and its Galois group over does not have any element of order .
Finally assume that N and are coprime and N is a product of more than two primes. We write , where p, q are primes and . Let t = order of p modulo q. As discussed in the previous case let be a monic irreducible polynomial of degree pq whose Galois group is the semi-direct product of an elementary group of order by a cyclic group of order q and is a Frobenius group.
Let denote this Frobenius group of order and denote the splitting field of . Let be a cyclic group of order m and be a monic irreducible polynomialof degree m whose splitting field is and Galois group over is .
Let be the compositum of the fields and . Let and
We note the following:
1) ;
2) ;
3) ;
4) ;
5)
is a group of order
isomorphic to the direct product of aFrobenius group of order
and a cyclic group of order
6) The group G transitively permutes the nm algebraic numbers . So is an irreducible polynomial of degree , whose Galois group does not have any element of order N. This completes the proof of our theorem.
3. Alternate Methods
As we noticed the construction of irreducible polynomials in of odd composite degree N where , and whose Galois group does not contain an element of order N is not so straight forward. In some case such as or there is another interesting method of construction of such polynomials. In fact it works for most N’s (with very few exceptions) which are such that for some n and r such that . The method we are about to describe fails in cases where but the symmetric group does have an element of order N, as it happens when and .
As the symmetric group on 15 letters does have an element of order , namely a permutation which is a product of 3, 5 and a 7-cycle. Let be a monic irreducible polynomial of degree whose Galois group is isomorphic to either or . Let r be such that and . Further assume that does not have any element order N. We know that is n-transitive and is -transitive on n letters. Let denote a polynomial of degree whose roots are sum of all r different roots of . Let the roots of be , where 1 ≤ i ≤ N. The polynomials and let have the same splitting field. Since both . and transitively permute the N, roots of Let this polynomial is irreducible. So the polynomial let is the required polynomial of degree N, whose Galois group does not have any element of order N.
4. Examples
1) The first interesting case is for . Let be an irreduciblemonic polynomial of degree six whose Galois group over is isomorphic to symmetric oralternating group on five or six letters. Then is an irreducible monic polynomial whose Galois group is the same as that of and so does not have any element of order 15. Therefore is reducible modulo every prime. For instance let whose discriminant is . We note that
It follows that
is irreducible over and its Galois group G over
is 2-transitive on its roots and has a 3-cycle. Therefore G is isomorphic to
the alternating group on six letters [8] . We know that
is 4-transitive on six letters. Let
represent the polynomial of degree 15 whose
roots are the sumsof the roots of
taken two at a time. This polynomial turns out to be
The Galois group of this polynomial is the same as that of and so is isomorphic to
. As
has no element of order 15 this polynomial is reducible modulo every prime.
2) The second example is for. As
, we start with a some monic polynomial
of degree 7 with Galois group isomorphic to
or
. The polynomial of degree 35 whose roots are the sums of three different roots of
is the required polynomial whose Galois group (being isomorphic to
or
) does not have any element of order 35. To illustrate this we begin with the polynomial
of degree 7. We observe that the discriminant of the polynomial is
and
is irreducible modulo 5. Also
So is an irreducible polynomial of degree 7 whose discriminant is a square and Galois group G has a 3-cycle. So G is isomorphic to
[8] .
Suppose that the roots of are
. The polynomial
of degree
whose roots are
, is
This polynomial is irreducible over. As its Galois group is isomorphic to
which does not have any element of order 21 this polynomial is reducible modulo every prime.
The polynomial of degree
whose roots are
, is
This polynomial is irreducible over and its Galois group is isomorphic to
. As
does not have any element of order 35 this polynomial is reducible modulo every prime. Its discriminant is the following 311-digit number
Note: The composite natural numbers N below 100 which are such that are
Among these numbers the method described above works for N = 15, 35 and 91. This is so because,
, and
. As starting with a polynomial of degree 7 with Galois group isomorphic to
or
, we constructed an irreducible polynomial of degree 35 which is reducible modulo every prime, likewise starting with a polynomial of degree14 with Galois group isomorphic to
or
we can construct an irreducible polynomial of degree 91 which is reducible modulo every prime.
3) The method discussed in the previous examples above does not work for. For this we proceed as in the proof of our theorem. As the order of 11 modulo 3 is 2 we construct a Frobenius group G of order
which is a semi-direct product of
by a group of order 3. More specifically we extend the group
by the group
of order three where
is the automorphism of
given by
. It is easily seen that this automorphism has order three and is fixed-point-free.The resulting group, the semi-direct product of
by
is a Frobenius group of order 363 having the subgroup
as its kernel and the group
as its complement.
This Frobenius group of order 363 does not have any subgroup of order 33. Let be a normal extension whose Galois group is isomorphic to G.
Let H be a subgroup of G of order 11 and be its fixed subfield. By FTGT (Fundamental Theorem of Galois Theory) the field
has degree 33 over
. Let α be an algebraic integer such that
and let
be its minimum polynomial. As proved in the theorem this polynomial has degree 33 and its Galois group is a Frobenius group of order
which does not have any subgroup of order 33 andtherefore the irreducible polynomials
is reducible modulo every prime.
5. Construction of the Polynomials
It remains to be seen that given a degree n polynomial how we can compute the polynomial
, for
. This can be done with thehelp of the concept of the resultant of two polynomials. Let
be polynomials of degree and
respectively (so
) with coefficients in a field
. Let
be the zeros of
and
in some extension of
. Writing
and
as simply f and g, and resultant simply as Res we have
As this resultant is equal to the following determinant of order, its value can be computed with the help of any symbolic computation package such as MATHEMATICA.
In this determinant all the missing entries are zeros. The entries in the first m rows are the coefficients of and those in the last n rows are the coefficients of
. If f and g are polynomials in two variables x and y then we can determine their resultant with respect to any of the variable. For the discussion of the calculation of
for a given polynomial
it will be convenient to deal with monic polynomials. Let
be a polynomial of degree n with zeros
. The polynomial
can be regarded as a monic polynomial of degree n in y with coefficientsin the polynomial ring
. As a polynomial in y its n zeros are
. We note that
This observation and (and similar ones) will be used repeatedly in what follows. As before we let denote the monic polynomial of degree
with zeros
where
.
We shall show how to find for
. The method discussed can be easily generalized to larger values of r.
5.1. Computation of f2(x)
Let
Then is a polynomial of degree
with zeros
. So the
zeros of
are
and
, each appearing twice. Let
Then is a monic polynomial of degree n with zeros
. Therefore,
is a polynomial of degree
, with zeros
, each zeroappearing twice. Therefore,
is a polynomial of degree with zeros
.
5.2. Computation of f3(x)
We first note that, as a polynomial in y, has degree
and has roots
for
. In other words we can write
Let
Then is a polynomial of degree
whose zeros are of following types.
, each appearing three times.
We check that the total number adds up to the right degree, namely
We shall now find a polynomial with zeros. Let
Here as before we have multiplied by to ensure that the first polynomial in the argument of
is monic. We note that as a polynomial in y the roots of
are
, for
. Also
is a polynomial of degree
. In fact
So the zeros of are
and
. Let
So is a monic polynomial with zeros
and
is a monic polynomial of degree
with zeros
,
. We also note that
is a polynomial of degree with zeros
, each repeated three times. Therefore
is the required polynomial of degree.
6. Addendum
Bernard Dominique [9] sent us a list of following eighteen irreducible polynomials of degree 33 and informed us that these are reducible for all primes.
If the Galois group of any of these polynomials regarded as a permutation on its 33 roots had a 33-cycle then according to Cebotarev Density Theorem the density of primes p for which any of these polynomials is irreducible should be [10] . As there is no such prime
we believe that these polynomials are reducible for all primes. However, in the absence of any information about their Galois group we do not have a proof that any of these polynomials is locally reducible for all primes.
7. Conclusion
In this paper we have shown that for any composite natural number N there are polynomials of degree N with integer coefficients which are irreducible in but which are reducible modulo p for every prime p and we have given method of construction of such polynomials for various values of N.
Conflicts of Interest
The author declares no conflicts of interest regarding the publication of this paper.
Cite this paper
Gupta, S. (2019) Irreducible Polynomials in ℤ[x] That Are Reducible Modulo All Primes. Open Journal of Discrete Mathematics, 9, 52-61. https://doi.org/10.4236/ojdm.2019.92006
References
- 1. Brandl, R. (1986) Integer Polynomials That Are Reducible Modulo All Primes. American Mathematical Monthly, 93, 286-288. https://doi.org/10.1080/00029890.1986.11971807
- 2. Guralnick, R., Schacher, M.M. and Sonn, J. (2005) Irreducible Polynomials Which Are Locally Reducible Everywhere. Proceedings of the American Mathematical Society, 133, 3171-3177. https://doi.org/10.1090/S0002-9939-05-07855-X
- 3. Safarevic, I.R. (1956) Construction of Fields of Algebraic Numbers with a Given Soluble Galois Group. Isv. Nauk. SSSR, 18, 274.
- 4. Schur, I. (1930) Gleichungen ohne Affeckt. Gesammelte Abhandlungen, Band III, No. 67, 191-197.
- 5. Serre, J.-P. (2008) Topics in Galois Theory. A K Peters, Ltd.
- 6. Erbach, D.W., Fisher, J. and McKay, J. (1979) Polynomials with PSL (2,7) as Galois Group. Journal of Number Theory, 11, 69-75. https://doi.org/10.1016/0022-314X(79)90020-9
- 7. Lang, S. (1993) Algebra. 3rd Edition, Addison Wesley, Boston.
- 8. Wielandt, H. (1964) Finite Permutation Groups. Academic Press, New York.
- 9. Bernard Dominique, Email Communication.
- 10. Stevenhagen, P. and Lenstra, H.W. (1996) Chebotarev and His Density Theorem. The Mathematical Intelligencer, 18, 26-37. https://doi.org/10.1007/BF03027290