A Test for Absolute Irreducibility of Polynomials with Rational Coefficients

A Test for Absolute Irreducibility of Polynomials with Rational Coefficients

Jean-François 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[x₁,...,x_r] is said to have a simple solution at a point PÎk^r when

fÎ I(P)\ I(P)²,

I(P) being the ideal of polynomials vanishing at P:

I(P):={gÎ k[x₁,...,x_r], 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[x₁,...,x_r] is irreducible over the perfect field k and has a simple solution at a point PÎ k^r, 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=x³+2xy+5x-3xy²-y³

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[x₁,...,x_r] and p be a prime number. If deg(f mod p)=deg(f) and fmod p is absolutely irreducible (i.e., over F_p) then f is absolutely irreducible (i.e, over Q).

For instance, the polynomial

g=x³+y³+7xy+4y+x²+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 F_p (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=pⁿ for p a prime number and n a positive integer. The number of polynomials of degree at most d over F_q[X]=F_q[x₁,...,x_r] is q^w(d,r) where w(d,r)=(

r+d

). From there and the fact that F_q[X] is a unique factorization domain it is possible to compute an exact formula for the number of irreducible polynomials of F_q[X] of degree at most d [1, 2]. Then very sharp inequalities can be obtained: for r³2 and d³3 the probability p that a polynomial of F_q[X] of degree at most d be reducible obeys

q^r

w(d,r-1)

æ
ç
ç
è

ö
÷
÷
ø

£ p £

q^r

w(d,r-1)

æ
ç
ç
è

ö
÷
÷
ø

2.2 Polynomials having simple solutions

For any PÎF_q^r, the set of polynomials of degree at most d in I(P)\ I(P)² is a subspace of the vector space F_q[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 F_q, its cardinality is given by q^D.

The quotients F_q[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 F_q[X]/I(0)^p=w(p-1,r). (1)

This enumeration applies to any point P possibly different from 0.

Chinese remainder theorem

If P₁¹ P₂ are two points of F_q^r, it follows for instance from Bézout's theorem that F_q[X]=I(P₁)^p+I(P₂)^q for any p,q. One can therefore apply the Chinese remainder theorem which states the ring isomorphism

_q[X]/

i=1

I(P_i)

p_i

i=1

_q[X]/I(P_i)

p_i

when the points P_i, i=1,...,n are distinct. This translates into a result on the dimensions of the corresponding vector spaces:

dim

æ
ç
ç
è

_q[X]/

i=1

I(P_i)

p_i

ö
÷
÷
ø

i=1

dim F

_q[X]/I(P_i)

p_i

It follows from (1) that the quantity D in the left-hand side is finite, and for any degree d³ D,

dim

æ
ç
ç
è

_q[X]_dÇ

i=1

I(P_i)

p_i

ö
÷
÷
ø

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

Inclusion-Exclusion

Let again P₁¹ P₂ be two points of F_q^r. Then the number of polynomials having a simple solution at either P₁ or P₂, or both, is the cardinality of

(

I(P₁)\ I(P₁)²

)

(

I(P₂)\ I(P₂)²

)

= I(P₁)È I(P₂)\ I(P₁)²\ I(P₂)² \

(

I(P₁)Ç I(P₂)

)

(

I(P₁)²Ç I(P₂)

)

(

I(P₁)Ç I(P₂)²

)

(

I(P₁)²Ç I(P₂)²

)

The cardinalities are evaluated from the right-hand side by (1) and (2), which gives for d³w(1,r)=2r+2

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)

w(d,r)

æ
ç
ç
ç
è

æ
è

1-q

w(0,r)

w(1,r)

ö
ø

ö
÷
÷
÷
ø

This extends to the case of n distinct points P₁,...,P_n to give that for d>(r+1)n, the proportion of polynomials in F_q[X]_d having at least one simple solution at one of the P_i's is

æ
ç
ç
è

q^r+1

ö
÷
÷
ø

. (3)

Now it is sufficient to take n=q^r the cardinality of F_q^r in the previous expression to obtain the probability that a random polynomial of degree d³ n has a simple solution at a point of F_q^r.

Refining the Bound

The bound d³ q^r 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=q^r. The system of polynomials

{(x₁^q-x₁)²,...,(x_r^q-x_r)²}

generates the ideal of polynomials having multiplicity at least 2 at every point of F_q^r. This ideal is responsible for the largest value of D in (2), whence the bound q^r. It is easy to see that the system above is a Gröbner 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 F_q[X]_d having a simple solution in F_q^r is

æ
ç
ç
è

q^r+1

ö
÷
÷
ø

q^r

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

p^r

w(d,r-1)

æ
ç
ç
è

ö
÷
÷
ø

æ
ç
ç
è

p^r+1

ö
÷
÷
ø

p^r

where the first term is neglectible compared to the second one, the sum being of order

exp(1/p)exp(-p^r-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-François). -- Sur la factorisation absolue des polynômes. -- PhD Thesis, Université de Limoges, 1997.

This document was translated from L^AT_EX by H^EV^EA.

1 Algorithms

2 Probability Estimates

2.1 Irreducible Polynomials

2.2 Polynomials having simple solutions

The quotients Fq[X]/I(P)q

Chinese remainder theorem

Inclusion-Exclusion

Refining the Bound

2.3 Conclusion

References

The quotients F_q[X]/I(P)^q