Abstract
We present results on testing the computation of bounds for polynomial divisors and give estimates for their heights. There are also given results on the irreducibility of polynomials and some methods for constructing irreducible polynomials. They are based on properties of Newton’s polygon. Finally we give applications to the irreducibility of univariate polynomials
over a discrete valuation domain. We give applications to bivariate polynomials.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 INTRODUCTION
A main problem in polynomial algebra is to decide if a polynomial over a unique factorization domain is irreducible. There exist many results that give sufficient conditions for the irreducibility, the so called irreducible polynomials. On the other hand the irreducibility can be decided using algorithms for polynomial factorization.
We shall discuss computational problems concerning irreducible polynomials. We shall first present results on the computation of sizes of polynomial divisors. In the second part we present irreducible criteria that use properties of Newton’s polygon.
2 POLYNOMIAL DIVISORS
We know that any univariate polynomial over a unique factorization domain can be uniquely decomposed in a product of irreducible polynomials. In particular, any univariate polynomial over the integers is a product of irreducible polynomials.
The classical methods invented by Newton and Kronecker give algorithmic methods for the factorization of univariate polynomials over the integers. They implicitely give also criteria for establishing if a polynomial is irreducible. Modern and more efficient methods were developed at the end of the 20th century, using reduction to the factorization over finite fields and suitable lifting methods.
I. Newton described in Arithmetica Universalis a device for computing the polynomial divisors of univariate divisors over the integers, see the section De inventione divisorum. His method is based on properties of finite differences and polynomial interpolation through finite differences. The method of Newton was improved by N. Bernoulli and F.T. Schubert (see [13]).
We consider a nonconstant reducible univariate polynomial \(P\) with integer coefficients and a divisor \(Q\) over the integers. We obtain new bounds for the coefficients of \(Q\) in function of the degree and of the coefficients of \(P\). These bounds are obtained using an inequality of Beauzamy and the multiplication by a suitable linear factor.
Let \(P\) be a nonconstant univariate polynomial with integer coefficients. If \(Q\) is a nontrivial divisor of \(P\) over \(\mathbb{Z}\) we are interested to give bounds for the absolute values of its coefficients in function of the coefficients and the degree of P. Such bounds are relevant in polynomial factorization and are expressed in function of the measure, the quadratic norm, the Bombieri norm and other polynomial sizes.
We refine an inequality of Beauzamy using the multiplication of the polynomial \(P\) by a suitable linear factor.
3 APPLICATIONS TO POLYNOMIAL FACTORIZATION
We obtain upper bounds for the size of polynomial factors of an univariate polynomial with integer coefficients.
Let \(P(X) = \sum\nolimits_{i = 0}^d {{{a}_{i}}{{X}^{i}}} \in \mathbb{Z}{\kern 1pt} [X]{\backslash }\mathbb{Z}.\) By a result of B. Beauzamy [2], if \(Q\) is a nontrivial divisor of \(P\) in \(\mathbb{Z}{\kern 1pt} [X]\) one has
where
Note that \({{[P]}_{2}}\) is the Bombieri’s norm of the polynomial P.
We first need an inequality similar to (1). Our inequality depends on a real parameter \(\alpha \) and suitable choices of it allows us to deduce refinements for the height of polynomial divisors of integer polynomials.
Theorem 1.Let\(Q\)be a nontrivial divisor of\(P\)in \(\mathbb{Z}[X]\), \(d = \text{deg}(P) \geqslant 2\). We have
for all\(\alpha \in \mathbb{R}{\backslash \{ } - 1,0,1\} \).
Proof. Suppose \(P = QR\) is a nontrivial factorization of \(P\) in \(\mathbb{Z}[X]\). This gives the factorization
of \(F = (X - \alpha )P\) in \(\mathbb{C}{\kern 1pt} [X]\). We put \(n = \text{deg}(Q)\).
Let us remind a useful inequality of B. Beauzamy, E. Bombieri, P. Enflo and H. Montgomery [1]:
If \(G\) and \(H\) are nonconstant polynomials over \(\mathbb{C}\) of degrees \(m\) and \(l\) respectively we have
By (2) this gives
Since the coefficients of \(R\) are integers we have, as in the proof of (1), \({{[R]}_{2}} \geqslant \sqrt 2 \). It follows that
Let \((X - \alpha )Q = \sum\nolimits_{j = 0}^{n + 1} \,{{{v}}_{j}}{{X}^{j}}\). We observe that
so
On the other hand
and \((d - n) + (n + 1 - j) + j = d + 1\). Therefore, as in [1],
which gives
By the inequality of M. Mignotte [10] we have
So (3) gives
Remark. It is not possible to obtain the previous result applying directly the inequality (1) because the polynomial \((X - \alpha )P(X)\) has no integer coefficients, an essential condition in the theorem of B. Beauzamy [2].
3.1 Some Examples
We consider first the polynomials studied in [1] and [11]:
The polynomial \({{F}_{5}}\) was considered by P.S. Wang [17] and M. Mignotte–P. Glesser [11]. Let \({{F}_{5}} = {{a}_{1}}{{a}_{2}}{{a}_{3}}{{a}_{4}}\) where
We denote by \({{B}_{1}}(P)\) the bound of Beauzamy (1) and by \({{B}_{2}}(P)\) our bound in Theorem 1.
Table 1
P | F 1 | F 2 | F 3 | F 4 | F 5 |
---|---|---|---|---|---|
B1(P) | 155.2 | 5145.1 | 16 531 988.3 | 13 962 915.8 | 3.8 × 102992 |
B2(P) | 97.9 | 3832.4 | 15 948 685.5 | 8 730 942.5 | 5.8 × 102990 |
Note that, for convenient values of the parameter \(\alpha \), we have \({{B}_{1}}({{F}_{5}}){\text{/}}{{B}_{2}}({{F}_{5}}) = 64.49\).
However, as in [2], we have the bad polynomials \({{(1 + X)}^{d}}\) and \({{X}^{d}} - 1\). If we take, for example, \(P(X) = {{X}^{d}} - 1\), we obtain
4 NEWTON’S POLYGON AND IRREDUCIBILITY CRITERIA
The Newton polygon was initially defined for bivariate polynomials. Another approach is to associate a Newton polygon to a univariate polynomial with the coefficients in a discrete valuation domain.
Let \(F(X) = \sum\nolimits_{i = 0}^d \,{{a}_{i}}{{X}^{{d - i}}} \in A{\kern 1pt} [X]\), where \((A,{v})\) is a discrete valuation domain.
The Newton polygon\(N(F)\) of the polynomial \(F\) is the lower convex hull of the set \(\left\{ {(d - i,\;{v}({{a}_{i}}));\;{{a}_{i}} \ne 0} \right\}\). The slope of the line joining the points \((d,{v}({{a}_{0}}))\) and \((d - i,{v}({{a}_{i}}))\) is \(\frac{{{v}({{a}_{0}}) - {v}({{a}_{i}})}}{i}\).
The Newton index\(e(F)\) of the polynomial \(F\) is the largest slope \(e(F)\) of these lines. More precisely,
G. Dumas [8] has studied the relationship between the Newton indices of two polynomials and the index of their product in the case of univariate integer polynomials with the valuation defined by powers of a prime \(p\).
If \({{F}_{1}}\) and \({{F}_{2}}\) are such polynomials, he established that the Newton polygon of the product \({{F}_{1}}{{F}_{2}}\) can be obtained by translating the edges of the polygons \(N({{F}_{1}})\) and \(N({{F}_{2}})\) in such a way that they compose a convex polygonal path with the slopes of the edges ordered increasingly.
Proposition 2. If \({{F}_{1}},{{F}_{2}} \in A{\kern 1pt} [X]{\backslash }A\) then \(e({{F}_{1}}{{F}_{2}}) = \max \left( {e({{F}_{1}}),e({{F}_{2}})} \right).\)
4.1 Irreducibility Tests
We consider polynomials \(F(X) = \sum\nolimits_{i = 0}^d \,{{a}_{i}}{{X}^{{d - i}}} \in A{\kern 1pt} [X]\) for which the Newton index could be attained for an index \(s \ne d\) and for which \({v}({{a}_{0}})\) could be nonzero. We have given in [16] the following results:
Theorem 3.Let\((A,{v})\)be a discrete valuation domain, and let\(F(X) = {{a}_{0}}{{X}^{d}} + {{a}_{1}}{{X}^{{d - 1}}} + \ldots + {{a}_{{d - 1}}}X + \)\({{a}_{d}} \in A{\kern 1pt} [X]\), with\({{a}_{0}}{{a}_{d}} \ne 0\)and \(d \geqslant 2\). We assume that there exists an index\(s \in \{ 1,2, \ldots ,d\} \)such that
(a) \(\frac{{{v}({{a}_{0}}) - {v}({{a}_{s}})}}{s} > \frac{{{v}({{a}_{0}}) - {v}({{a}_{i}})}}{i}\) for\(i \in \{ 1,2,...,d\} ,\;i \ne s\),
(b) \(\frac{{{v}({{a}_{0}}) - {v}({{a}_{s}})}}{s} - \frac{{{v}({{a}_{0}}) - {v}({{a}_{d}})}}{d} = \frac{1}{{ds}}\),
(c) \(\text{gcd}({v}({{a}_{0}}) - {v}({{a}_{s}}),s) = 1\).
Then the polynomial\(F\)is either irreducible in \(A{\kern 1pt} [X]\), or has a factor whose degree is a multiple of\(s\).
Theorem 4.Let\((A,{v})\)be a discrete valuation domain, and let\(F(X) = {{a}_{0}}{{X}^{d}} + {{a}_{1}}{{X}^{{d - 1}}} + \ldots + {{a}_{{d - 1}}}X + \)\({{a}_{d}} \in A{\kern 1pt} [X]\), with\({{a}_{0}}{{a}_{d}} \ne 0\)and \(d \geqslant 2\). We assume that there exists an index\(s \in \{ 1,2, \ldots ,d\} \)such that
(a) \(\frac{{{v}({{a}_{0}}) - {v}({{a}_{s}})}}{s} > \frac{{{v}({{a}_{0}}) - {v}({{a}_{i}})}}{i}\) for\(i \in \{ 1,2,...,d\} ,\;i \ne s\);
(b) \(\frac{{{v}({{a}_{0}}) - {v}({{a}_{s}})}}{s} - \frac{{{v}({{a}_{0}}) - {v}({{a}_{d}})}}{d} = \frac{u}{{ds}}\), with\(u \geqslant 2\);
(c) \(\text{gcd}({v}({{a}_{0}}) - {v}({{a}_{s}}),s) = 1\). Then one of the following conditions is satisfied:
(i) The polynomial\(F\)is irreducible in\(A{\kern 1pt} [X]\).
(ii) The polynomial\(F\)has a divisor whose degree is a multiple of\(s\).
(iii) The polynomial\(F\)admits a factorization\(F = {{F}_{1}}{{F}_{2}}\)and\(s\)divides \(\beta {{d}_{1}} - \alpha {{d}_{2}}\), for some \(\alpha ,\beta \in \{ 1,2, \ldots ,u - 1\} \), where \({{d}_{1}} = \text{deg}({{F}_{1}})\),\({{d}_{2}} = \text{deg}({{F}_{2}})\).
One of the oldest irreducibility criterion for univariate polynomials with coefficients in a valuation domain was given by G. Dumas [8] as a valuation approach to Schönemann–Eisenstein’s criterion for polynomials with integer coefficients ([15] and [9]).
Theorem 5 (G. Dumas). Let \(F(X) = \sum\nolimits_{i = 0}^d \,{{a}_{i}}{{X}^{{d - i}}}\) be a polynomial over a discrete valuation domain \(A\) , with valued field \((K,{v})\) . If the following conditions are fulfilled
(i) \({v}({{a}_{0}}) = 0\),
(ii) \(\tfrac{{{v}({{a}_{d}})}}{d} < \tfrac{{{v}({{a}_{i}})}}{i}\)for all\(i \in \{ 1,2, \ldots ,d - 1\} \),
(iii) \(({v}({{a}_{d}}),d) = 1\),
then the polynomial\(F(X)\)is irreducible in\(K[X]\).
Remark. We observe that Theorems 3 and 4 consider conditions that are not satisfied by Theorem 5 of G. Dumas.
With the notations in Theorem 3, one has the following result.
Corollary 6.If\(d \geqslant 4\)and \(s > d{\text{/}}2\), then the polynomial\(F\)is either irreducible, or has a divisor of degree\(s\).
Proof. If \(F\) would have a factor of degree \(ks\), with \(k \geqslant 2\), then we would obtain
a contradiction.
4.2 Examples
(1) Let \(F(X) = {{X}^{d}} + {{p}^{d}}{{X}^{2}} + {{p}^{{d - 2}}}(p - 1)X + {{p}^{{d - 1}}} \in \mathbb{Z}{\kern 1pt} [X]\), with \(d \geqslant 3\) and \(p\) a prime number, and let us consider the usual \(p\)-adic value on \(\mathbb{Z}\), denoted by \({v}\). Since
and
we may take \(s = d - 1\), and since \(s{v}({{a}_{d}}) - d{v}({{a}_{s}}) = {{(d - 1)}^{2}} - d(d - 2) = 1\), we conclude by Theorem 3 that \(F\) is either irreducible, or has a factor of degree \(d - 1\), and hence also a linear factor. On the other hand, one may easily check that \(F\) has no integer solutions, and hence is an irreducible polynomial.
(2) Let \(F(X,Y) = {{Y}^{d}} + q(X)Y + r(X) \in \mathbb{Z}{\kern 1pt} [X,Y]\), where \(q,r \in \mathbb{Z}{\kern 1pt} [X]\) with \(\text{deg}(q) = \text{deg}(r) = 1\). Using now the discrete valuation on \(\mathbb{Z}{\kern 1pt} [X]\) given by \({v}(h) = - \text{deg}(h)\) for \(h \in \mathbb{Z}{\kern 1pt} [X]\), we see that
so with the notation in Theorem 3 we have \(s = d - 1\). On the other hand, using the same notation we observe that
It follows that \(F\) is either irreducible in \(\mathbb{Z}{\kern 1pt} [X,Y]\), or has a linear factor with respect to Y.
(3) Let \(K\) be a field of characteristic zero, \(d \geqslant 4\) an integer, and let
We represent the polynomial \(F\) as
with \({{a}_{{d - 2}}}(X) = {{X}^{{d - 2}}} + X + 1\), \({{a}_{{d - 1}}}(X) = {{X}^{d}} + X + 1\) and \({{a}_{d}}(X) = {{X}^{{d + 1}}} + {{X}^{2}} + 1\). Using now the discrete valuation on \(K[X]\) given by \({v}(h) = - \text{deg}(h)\) for \(h \in K[X]\), we observe that
Therefore \(\tfrac{{{v}({{a}_{{d - 1}}})}}{{d - 1}} < \tfrac{{{v}({{a}_{{d - 2}}})}}{{d - 2}}\) and \(\tfrac{{{v}({{a}_{{d - 1}}})}}{{d - 1}} < \tfrac{{{v}({{a}_{d}})}}{d}\), so we may take \(s = d - 1\), and since \(s{v}({{a}_{d}}) - d{v}({{a}_{s}}) = 1\), we conclude by Theorem 3 that \(F\) is either irreducible in \(K{\kern 1pt} [X,Y]\), or has a factor whose degree with respect to \(Y\) is a multiple of \(d - 1\), that is \(F\) is either irreducible, or has a linear factor in Y.
CONCLUSIONS
We have obtained a refinement of a theorem of B. Beauzamy about the size of polynomial divisors. We have also obtained new irreducibility criteria based on the study of Newton’s polygon.
REFERENCES
E. Beauzamy, P. Bombieri, and H. Enflo, “Montgomery: Products of polynomials in many variables,” J. Number Theory 36, 219–245 (1990).
B. Beauzamy, “Products of polynomials and a priori estimates for coefficients in polynomial decompositions: A sharp result,” J. Symb. Comput. 13, 463–472 (1992).
S. Bhatia and S. K. Khanduja, “Difference polynomials and their generalizations,” Mathematika 48, 293–299 (2001).
A. Bishnoi, S. K. Khanduja, and K. Sudesh, “Some extensions and applications of the Eisenstein irreducibility criterion,” Dev. Math. 18, 189–197 (2010).
N. C. Bonciocat, “On an irreducibility criterion of Perron for multivariate polynomials,” Bull. Math. Soc. Sci. Math. Roum. 53 (101), 213–217 (2010).
N. C. Bonciocat, “Schönemann–Eisenstein–Dumas-type irreducibility conditions that use arbitrarily many prime numbers,” Commun. Algebra 43, 3102–3122 (2015).
N. C. Bonciocat, Y. Bugeaud, M. Cipu, and M. Mignotte, “Irreducibility criteria for sums of two relatively prime polynomials,” Int. J. Number Theory 9, 1529–1539 (2013).
G. Dumas, “Sur quelques cas d’irréducibilité des polynômes à coefficients rationnels,” J. Math. Pures Appl. 12, 191–258 (1906).
G. Eisenstein, “Über die Irreductibilität und einige andere Eigenschaften der Gleichung, von welcher die Theilung der ganzen Lemniscate abhängt,” J. Reine Angew. Math. 39, 160–182 (1850).
M. Mignotte, “An inequality on the greatest roots of a polynomial,” Elem. Math. 46, 86–87 (1991).
M. Mignotte and P. Glesser, “On the smallest divisor of a polynomial,” J. Symb. Comput. 17, 277–282 (1994).
M. Mignotte, D. Ştefănescu, Polynomials—An Algorithmic Approach (Springer-Verlag, 1999).
M. Mignotte and D. Ştefănescu, “La première mèthode gènèrale de factorisation des polynômes: Autour d’un mḿoire de F. T. Schubert,” Rev. d’Hist. Math. 7, 101–123 (2001).
L. Panaitopol and D. Ştefănescu, “On the generalized difference polynomials,” Pac. J. Math. 143, 341–348 (1990).
T. Schönemann, “Von denjenigen Moduln, welche Potenzen von Primzahlen sind,” J. Reine Angew. Math. 32, 93–105 (1846).
D. Ştefănescu, “Applications of the Newton index to the construction of irreducible polynomials,” in CASC'2014,Lecture Notes in Computer Science, Ed. by V. Gerdt, W. Koepf, W. Mayr, and E. Vorozhtsov (Springer, Berlin, 2014), Vol. 8660, pp. 460–471.
P. S. Wang, “Parallel univariate polynomial factorization on shared–memory multiprocessors,” Proceedings of ISSAC’90 (1990), pp. 145–151.
S. H. Weintraub, “A mild generalization of Eisenstein’s criterion, Proc. Am. Math. Soc. 141, 1159–1160 (2013).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ştefănescu, D. Computational Aspects of Irreducible Polynomials. Comput. Math. and Math. Phys. 60, 128–133 (2020). https://doi.org/10.1134/S0965542520010133
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0965542520010133