A Test for Absolute Irreducibility of Polynomials with Rational Coefficients

Jean-Franois Ragot

Universit de Limoges

Algorithms Seminar

October 6, 1997

[summary by Bruno Salvy]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

While univariate polynomials with coefficients in a field k can always be factored as products of linear polynomials over the algebraic closure k of k, in the multivariate case irreducible polynomials over k may have arbitrary degree. A multivariate polynomial with coefficients in k which is irreducible over k is called absolutely irreducible and the decomposition of a multivariate polynomial as a product of absolutely irreducible polynomials is called its absolute factorization. Geometrically, absolutely irreducible polynomials correspond to irreducible algebraic varieties. Factorization is available in all the general computer algebra systems, but absolute factorization is much harder. There are algorithms that compute the absolute factorization of polynomials over Q and one of them is available in Maple. There are other algorithms that only test whether polynomials over Q are absolutely irreducible. Both these operations are computationally expensive. In this work, J.-F. Ragot gives a probabilistic test for absolute irreducibility.

1   Algorithms

The property on which are based the algorithms dealing with absolute irreducibility is related to simple solutions of polynomials.
Definition 1  Let k be a field. The polynomial f k[x1,...,xr] is said to have a simple solution at a point Pkr when
f I(P)\ I(P)2,
I(P) being the ideal of polynomials vanishing at P:
I(P):={g k[x1,...,xr], g(P)=0}.
For instance, the polynomials belonging to I(0)p are those that do not have any monomial of degree less than p.
Theorem 1   If f k[x1,...,xr] is irreducible over the perfect field k and has a simple solution at a point P kr, then f is absolutely irreducible.

Proof. Examples of perfect fields are fields of characteristic 0 and the fields Z/pZ (for prime p). The polynomial f being irreducible over k, its absolutely irreducible factors are conjugate over k. Thus if P cancels one of them it must cancel the other ones; simplicity then implies uniqueness.


For instance, the polynomial
f=x3+2xy+5x-3xy2-y3
can be seen to be irreducible over Q (e.g., by attempting to factor it). Since (0,0) is obviously a simple solution, f is absolutely irreducible.

One of the algorithms for absolute factorization then proceeds by constructing extension fields where the polynomials have simple solutions. Absolute factorization is thus reduced to factorization over algebraic extensions, which is possible but expensive when the degree of the extension is large.

Theorem 1 can also be used to prove absolute irreducibility when one can find simple solutions. While this is difficult in characteristic 0, it is relatively easier in characteristic p. Then, one can use the following theorem to obtain the conclusion over Q.
Theorem 2  [3] Let f be a polynomial in Z[x1,...,xr] and p be a prime number. If deg(f mod p)=deg(f) and fmod p is absolutely irreducible (i.e., over Fp) then f is absolutely irreducible (i.e, over Q).

For instance, the polynomial
g=x3+y3+7xy+4y+x2+5
is irreducible mod 5 and there (0,0) is a simple solution. Therefore, g is absolutely irreducible.

Now the good news is that by a theorem of Emmy Noether, there are only finitely many p for which an absolutely irreducible f over Q is not absolutely irreducible mod p. Moreover, there are also finitely many p for which f does not have simple solutions mod p. Combining these two results it is even possible to compute an explicit upper bound B(f) for the largest ``bad'' prime p. This gives a deterministic algorithm. However, the bound is so large that this approach is completely impractical. Instead, J.-F. Ragot's idea is to use a few prime numbers to check whether a polynomial is absolutely irreducible. This is implemented by a very simple procedure which loops over a finite set of prime numbers p until the polynomial is found to be irreducible modulo p and to have a simple root in Fp (success) or the set of prime numbers is exhausted (failure).

The remaining question is to evaluate the probability of success of this technique and bound the probability that a failure corresponds to an absolutely irreducible polynomial.

2   Probability Estimates

2.1   Irreducible Polynomials

Let q=pn for p a prime number and n a positive integer. The number of polynomials of degree at most d over Fq[X]=Fq[x1,...,xr] is qw(d,r) where w(d,r)=(
r+d
d
). From there and the fact that Fq[X] is a unique factorization domain it is possible to compute an exact formula for the number of irreducible polynomials of Fq[X] of degree at most d [1, 2]. Then very sharp inequalities can be obtained: for r2 and d3 the probability p that a polynomial of Fq[X] of degree at most d be reducible obeys
qr
q
w(d,r-1)
 



1-
5
q



p
qr
q
w(d,r-1)
 



1+
6
q



.

2.2   Polynomials having simple solutions

For any PFqr, the set of polynomials of degree at most d in I(P)\ I(P)2 is a subspace of the vector space Fq[X]d of polynomials of degree at most d. This makes it easier to compute the probability that a polynomial of degree d has a simple solution at a fixed point P or at a point P in a given set of points, since from the dimension D of a vector space over Fq, its cardinality is given by qD.

The quotients Fq[X]/I(P)q
We first consider the point P=0. There are w(p-1,r) monomials that cannot occur in a polynomial of I(0)p. In terms of dimensions, this is equivalent to
dim Fq[X]/I(0)p=w(p-1,r).     (1)
This enumeration applies to any point P possibly different from 0.

Chinese remainder theorem
If P1 P2 are two points of Fqr, it follows for instance from Bzout's theorem that Fq[X]=I(P1)p+I(P2)q for any p,q. One can therefore apply the Chinese remainder theorem which states the ring isomorphism
F q[X]/
n
i=1
I(Pi)
pi
 
=
n
i=1
F q[X]/I(Pi)
pi
 
,
when the points Pi, i=1,...,n are distinct. This translates into a result on the dimensions of the corresponding vector spaces:
dim


F q[X]/
n
i=1
I(Pi)
pi
 



=
n
i=1
dim F q[X]/I(Pi)
pi
 
.
It follows from (1) that the quantity D in the left-hand side is finite, and for any degree d D,
dim


F q[X]d
n
i=1
I(Pi)
pi
 



=w(d,r)-D.     (2)

Inclusion-Exclusion
Let again P1 P2 be two points of Fqr. Then the number of polynomials having a simple solution at either P1 or P2, or both, is the cardinality of
( I(P1)\ I(P1)2 ) ( I(P2)\ I(P2)2 )
= I(P1) I(P2)\ I(P1)2\ I(P2)2 \ ( I(P1) I(P2) )
( I(P1)2 I(P2) ) ( I(P1) I(P2)2 ) \ ( I(P1)2 I(P2)2 ) .
The cardinalities are evaluated from the right-hand side by (1) and (2), which gives for dw(1,r)=2r+2
2q
w(d,r)-w(0,r)
 
-2q
w(d,r)-w(1,r)
 
-q
w(d,r)-2w(0,r)
 
+2q
w(d,r)-w(0,r)-w(1,r)
 
-q
w(d,r)-2w(1,r)
 
=q
w(d,r)
 




1-
1-q
w(0,r)
 
+q
w(1,r)
 

2

 




.
This extends to the case of n distinct points P1,...,Pn to give that for d>(r+1)n, the proportion of polynomials in Fq[X]d having at least one simple solution at one of the Pi's is
1-


1-
1
q
+
1
qr+1



n



 
.     (3)
Now it is sufficient to take n=qr the cardinality of Fqr in the previous expression to obtain the probability that a random polynomial of degree d n has a simple solution at a point of Fqr.

Refining the Bound
The bound d qr that we have just derived can be made much more precise by having a better look at the quotient on the left-hand side of (2) in the case n=qr. The system of polynomials
{(x1q-x1)2,...,(xrq-xr)2}
generates the ideal of polynomials having multiplicity at least 2 at every point of Fqr. This ideal is responsible for the largest value of D in (2), whence the bound qr. It is easy to see that the system above is a Grbner basis of this ideal for the lexicographic order. This means that one can take a basis of the quotient (as a vector space) where the polynomials of largest degree have degree 2q-1. This way, one gets the following.
Proposition 1  [3] For d r(2q-1), the proportion of polynomials of Fq[X]d having a simple solution in Fqr is
1-


1-
1
q
+
1
qr+1



qr



 
.

2.3   Conclusion

We are interested in polynomials that are irreducible and have a simple solution. Using both previous results yields a bound on the complementary event: the probability that a polynomial of degree d>r(2p-1) is reducible or does not have a simple solution is upper bounded by
pr
p
w(d,r-1)
 



1+
6
p



+


1-
1
p
+
1
pr+1



pr



 
,
where the first term is neglectible compared to the second one, the sum being of order
exp(1/p)exp(-pr-1).
By taking several prime numbers p, we get a product of similar quantities which can be made as small as desired. Polynomials whose degree decreases when reduced mod p have to be taken into account, but their quantity does not change the final result much. Thus we get a bound on the probability that an absolutely irreducible polynomial hold the probabilistic algorithm in check.

References

[1]
Carlitz (L.). -- The distribution of irreducible polynomials in several indeterminates. Illinois Journal of Mathematics, vol. 7, 1963, pp. 371--375.

[2]
Carlitz (L.). -- The distribution of irreducible polynomials in several indeterminates. II. Canadian Journal of Mathematics, vol. 17, 1965, pp. 261--266.

[3]
Ragot (Jean-Franois). -- Sur la factorisation absolue des polynmes. -- PhD Thesis, Universit de Limoges, 1997.

This document was translated from LATEX by HEVEA.