Square-free polynomial

In mathematics, a square-free polynomial is a polynomial with no non-trivial square factors, i.e, $f \in F[x]$ is square-free if and only if $b^2 \nmid f$ for every $b \in F[x]$ with non-zero degree. This definition implies that no factors of higher order can exist, either, for if b³ divided the polynomial, then b² would divide it also. In applications in physics and engineering, a square-free polynomial is much more commonly called a polynomial with no repeated roots.

Any square factor of a polynomial introduces a nontrivial common factor of f and its formal derivative f ′, so a necessary condition for f to be square-free is that the greatest common divisor of f and f ′ is 1. If the field F is perfect, then all irreducible polynomials over F are separable polynomials, and so if f is a square-free polynomial over a perfect field, then the condition that f and f ′ are coprime is also sufficient for f to be square-free.

A square-free factorization of a polynomial is a factorization into powers of square-free factors, i.e:

$f(x) = a_1(x) a_2(x)^2 a_3(x)^3 \cdots a_n(x)^n \,$

where the a_k(x) are pairwise coprime square-free polynomials. Clearly, any non-zero polynomial admits a square-free factorization, since it can be factored into irreducible factors and the multiplicity of each irreducible factor counted to determine which a_k(x) it is part of.

The utility of a square-free factorization is that it is generally easier to compute than a full irreducible factorization. For this reason, square-free factorization is often used as the first step in polynomial factorization or root-finding algorithms. It is also useful in the integration of rational functions via partial fractions (a method due to Hermite).

Over fields of characteristic 0, only differentiation, polynomial division, and GCD calculation (which can be done using the Euclidean algorithm) is required to compute the square-free factorization. Let f be a non-zero polynomial, decomposed into square-free factors as above. Consider any irreducible factor q of ƒ: we may write ƒ = q^kh, where k > 0 and $q\nmid h$. By the product rule,

$f'=k\,q^{k-1}q'h+q^kh'.$

As the characteristic is 0, q does not divide k, q′, or h, thus $q^k\nmid\gcd(f,f')$ and $q^{k-1}\mid\gcd(f,f')$. That is, the multiplicity of any irreducible factor in gcd(f,f') is one less than its multiplicity in f, so

$\gcd(f,f') = a_2a_3^2 \cdots a_n^{n-1}\text{ and }\frac{f}{\gcd(f,f')}= a_1a_2\cdots a_n.\,$

Now, if we compute recursively

$f_0=f,\ f_1=\gcd(f_0,f_0'),\ f_2=\gcd(f_1,f_1'),\ f_3=\gcd(f_2,f_2'),\dots$

we obtain the polynomials

$g_k:=\frac{f_{k-1}}{f_k}=a_ka_{k+1}\cdots a_n,$

from which we recover the square-free factors as a_k = g_k/g_k+1.

A modification of this algorithm also works for polynomials over finite fields, or more generally, perfect fields of non-zero characteristic p, if we know an algorithm to compute p-th roots of elements of the field.