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

$${\rm H}(Q) \leqslant {{l}_{d}}\sqrt D ,$$
(1)

where

$${{l}_{d}} = \frac{{{{3}^{{3/4}}} \cdot {{3}^{{d/2}}}}}{{2\sqrt {\pi d} }},\quad D = [P]_{2}^{2} = \sum\limits_{i = 0}^d \,\frac{{a_{i}^{2}}}{{\left( {\begin{array}{*{20}{c}} d \\ i \end{array}} \right)}}.$$

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

$$H(Q) \leqslant \frac{1}{{\left| {\left| \alpha \right| - 1} \right|}}\frac{{{{3}^{{3/4}}} \cdot {{3}^{{\tfrac{{d + 1}}{2}}}}}}{{2\sqrt {\pi (d + 1)} }}{{[(X - \alpha )P]}_{2}}$$

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

$$F = \left( {(X - \alpha )Q} \right)R$$
(2)

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

$$\sqrt {\frac{{(m + l)!}}{{m!l!}}} {{[GH]}_{2}} \geqslant {{[G]}_{2}}{{[H]}_{2}}.$$

By (2) this gives

$${{[F]}_{2}} \geqslant \sqrt {\frac{{(n + 1)!(d - n)!}}{{(d + 1)!}}{\kern 1pt} } {{[(X - \alpha )Q]}_{2}}{\kern 1pt} {{[R]}_{2}}.$$

Since the coefficients of \(R\) are integers we have, as in the proof of (1), \({{[R]}_{2}} \geqslant \sqrt 2 \). It follows that

$${{[(X - \alpha )Q]}_{2}} \leqslant \sqrt {\frac{1}{2}\left( {\begin{array}{*{20}{c}} {d + 1} \\ {n + 1} \end{array}} \right)} {\kern 1pt} {{[F]}_{2}}.$$

Let \((X - \alpha )Q = \sum\nolimits_{j = 0}^{n + 1} \,{{{v}}_{j}}{{X}^{j}}\). We observe that

$$\frac{{{{{\left| {{{{v}}_{j}}} \right|}}^{2}}}}{{\left( {\begin{array}{*{20}{c}} {n + 1} \\ j \end{array}} \right)}} \leqslant [(X - \alpha )Q]_{2}^{2} \leqslant \frac{1}{2}\left( {\begin{array}{*{20}{c}} {d + 1} \\ {n + 1} \end{array}} \right)[F]_{2}^{2},$$

so

$$\left| {{{{v}}_{j}}} \right| \leqslant \sqrt {\frac{1}{2}\left( {\begin{array}{*{20}{c}} {d + 1} \\ {n + 1} \end{array}} \right)\left( {\begin{array}{*{20}{c}} {n + 1} \\ j \end{array}} \right)} {\kern 1pt} {{[F]}_{2}}.$$

On the other hand

$$\frac{1}{2}\left( {\begin{array}{*{20}{c}} {d + 1} \\ {n + 1} \end{array}} \right)\left( {\begin{array}{*{20}{c}} {n + 1} \\ j \end{array}} \right) = \frac{{(d + 1)!}}{{2(d - n)!(n + 1 - j)!j{\kern 1pt} !}}$$

and \((d - n) + (n + 1 - j) + j = d + 1\). Therefore, as in [1],

$$\sqrt {\frac{1}{2}\left( {\begin{array}{*{20}{c}} {d + 1} \\ {n + 1} \end{array}} \right)\left( {\begin{array}{*{20}{c}} {n + 1} \\ j \end{array}} \right)} \leqslant \frac{{{{3}^{{3/4}}} \cdot {{3}^{{\tfrac{{d + 1}}{2}}}}}}{{2\sqrt {(d + 1)\pi } }} = {{l}_{{d + 1}}},$$

which gives

$${\rm H}\left( {(X - \alpha )Q} \right) \leqslant {{l}_{{d + 1}}}{\kern 1pt} {{[F]}_{2}}.$$
(3)

By the inequality of M. Mignotte [10] we have

$$\left| {\left| \alpha \right| - 1} \right|{\rm H}(Q) \leqslant {\rm H}\left( {(X - \alpha )Q} \right).$$

So (3) gives

$${\rm H}(Q) \leqslant \frac{1}{{\left| {\left| \alpha \right| - 1} \right|}}{{l}_{{d + 1}}}{\kern 1pt} {{[F]}_{2}}.$$

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]:

$$F1 = {{x}^{8}} + {{x}^{6}} + 10{{x}^{4}} + 10{{x}^{3}} + 8{{x}^{2}} + 2x + 8,$$
$$F2 = {{x}^{{15}}} + 30{{x}^{{14}}} + 5{{x}^{{13}}} + 2{{x}^{2}} + 5x + 2,$$
$$\begin{gathered} F3 = 904050{{x}^{7}} + 1479450{{x}^{6}} - 2336817{{x}^{5}} - 3403088{{x}^{4}} + 2021847{{x}^{3}} \\ + \;1477766{{x}^{2}} - 1006566x + 170694, \\ \end{gathered} $$
$$\begin{gathered} F4 = {{x}^{{18}}} + 9{{x}^{{17}}} + 45{{x}^{{16}}} + 126{{x}^{{15}}} + 189{{x}^{{14}}} + 27{{x}^{{13}}} - 540{{x}^{{12}}} - 1215{{x}^{{11}}} + 1377{{x}^{{10}}} + 15444{{x}^{9}} \\ + \;46899{{x}^{8}} + 90153{{x}^{7}} + 133893{{x}^{6}} + 125388{{x}^{5}} + 29160{{x}^{4}} - 32076{{x}^{3}} + 26244{{x}^{2}} - 8748x + 2916. \\ \\ \end{gathered} $$

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

$$\begin{gathered} a1 = 8192{{x}^{{10}}} + 20480{{x}^{9}} + 58368{{x}^{8}} - 161792{{x}^{7}} + 198656{{x}^{6}} + 199680{{x}^{5}} \\ - \;414848{{x}^{4}} - 4160{{x}^{3}} + 171816{{x}^{2}} - 48556x + 469, \\ \end{gathered} $$
$$\begin{gathered} a2 = 8192{{x}^{{10}}} + 12288{{x}^{9}} + 66560{{x}^{8}} - 22528{{x}^{7}} - 138240{{x}^{6}} + 572928{{x}^{5}} \\ - \;90496{{x}^{4}} - 356032{{x}^{3}} + 113032{{x}^{2}} + 23420x - 8179,\;cr, \\ \end{gathered} $$
$$\begin{gathered} a3 = 4096{{x}^{{10}}} + 8192{{x}^{9}} + 1600{{x}^{8}} - 20608{{x}^{7}} + 20032{{x}^{6}} + 87360{{x}^{5}} - 105904{{x}^{4}} \\ + \;18544{{x}^{3}} + 11888{{x}^{2}} - 3416x + 1, \\ \end{gathered} $$
$$\begin{gathered} a4 = 4096{{x}^{{10}}} + 8192{{x}^{9}} - 3008{{x}^{8}} - 30848{{x}^{7}} + 21056{{x}^{6}} + 146496{{x}^{5}} - 221360{{x}^{4}} \\ + \;1232{{x}^{3}} + 144464{{x}^{2}} - 78488x + 11993. \\ \end{gathered} $$

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

$${{B}_{1}}(P){\text{/}}{{B}_{2}}(P) = \sqrt {\frac{{2{{{(d + 1)}}^{3}}}}{{2d(d + 2)}}} > 1\quad {\text{for}}\;{\text{all}}\quad d \geqslant 1.$$

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,

$$e(F) = \mathop {\max }\limits_{1 \leqslant i \leqslant d} \frac{{{v}({{a}_{0}}) - {v}({{a}_{i}})}}{i}.$$

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

$$d > ks > k\frac{d}{2} \geqslant d,$$

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

$$\frac{{{v}({{a}_{{d - 1}}})}}{{d - 1}} = \frac{{d - 2}}{{d - 1}} < \frac{d}{{d - 2}} = \frac{{{v}({{a}_{{d - 2}}})}}{{d - 2}}$$

and

$$\frac{{{v}({{a}_{{d - 1}}})}}{{d - 1}} = \frac{{d - 2}}{{d - 1}} < \frac{{d - 1}}{d} = \frac{{{v}({{a}_{d}})}}{d},$$

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

$$\frac{{{v}(q)}}{{d - 1}} = \frac{{ - 1}}{{d - 1}} < \frac{{ - 1}}{d} = \frac{{{v}(r)}}{d},$$

so with the notation in Theorem 3 we have \(s = d - 1\). On the other hand, using the same notation we observe that

$$s{v}({{a}_{d}}) - d{v}({{a}_{s}}) = (d - 1){v}(r) - d{v}(q) = 1.$$

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

$$F(X,Y) = {{Y}^{d}} + ({{X}^{{d - 2}}} + X + 1){{Y}^{2}} + ({{X}^{d}} + X + 1)Y + {{X}^{{d + 1}}} + {{X}^{2}} + 1 \in K{\kern 1pt} [X,Y].$$

We represent the polynomial \(F\) as

$$F(X,Y) = {{Y}^{d}} + {{a}_{{d - 2}}}(X){{Y}^{2}} + {{a}_{{d - 1}}}(X)Y + {{a}_{d}}(X)$$

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

$$\frac{{{v}({{a}_{{d - 2}}})}}{{d - 2}} = - 1,\quad \frac{{{v}({{a}_{{d - 1}}})}}{{d - 1}} = - \frac{d}{{d - 1}}\quad {\text{and}}\quad \frac{{{v}({{a}_{d}})}}{d} = - \frac{{d + 1}}{d}.$$

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.