In mathematics, a square-free polynomial is a polynomial defined over a field (or more generally, a unique factorization domain) that does not have as a factor any square of a non-unit factor. In the important case of univariate polynomials over a field k, this means that,
A square-free decomposition or square-free factorization of a polynomial is a factorization into powers of square-free factors
where those of the ak that are not equal to 1 are pairwise coprime square-free polynomials. Every non-zero polynomial with coefficients in a field admits a square-free factorization, which is unique up to the multiplication of the factors by non zero constants. The square-free factorization is much easier to compute than the complete factorization into irreducible factors, and is thus often preferred when the complete factorization is not really needed, as for the partial fraction decomposition and the symbolic integration of rational fractions. Square-free factorization is the first step of the polynomial factorization algorithms which are implemented in computer algebra systems. Therefore, the algorithm of square-free factorization is basic in computer algebra.
In the case of univariate polynomials over a field, any multiple factor of a polynomial introduces a nontrivial common factor of f and its formal derivative f ′, so a sufficient condition for f to be square-free is that the greatest common divisor of f and f ′ is 1. This condition is also necessary over a field of characteristic 0 or, more generally, over a perfect field, because over such a field, every irreducible polynomial is separable, and thus coprime with its derivative.
Over a field of characteristic 0, the quotient of
There are also known algorithms for the computation of the square-free decomposition of multivariate polynomials.
Yun's algorithm
In this section we describe Yun's algorithm for the square-free decomposition of univariate polynomials over a field of characteristic 0. It proceeds by a succession of GCD computations and exact divisions.
The input is thus a non zero polynomial f, and the first step of the algorithm consists in computing the GCD a0 of f and its formal derivative f'.
If
is the desired factorization, we have thus
and
If we set
and
Iterating this process until
This is formalized into an algorithm as follows:
The degree of