Square-free polynomial

From Wikipedia, the free encyclopedia

In mathematics, a square-free polynomial is a polynomial with no 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 b3 divided the polynomial, then b2 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 separable polynomial is square-free. Conversely, if the field F is perfect, all square-free polynomials over F are separable. In particular, if f is a square-free polynomial over a perfect field, then the greatest common divisor of f and its formal derivative f ′ is 1.

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 ak(x) are pairwise coprime square-free polynomials. Clearly, any non-zero polynomial admits a square-free factorization, since it could be factored into irreducible factors and the multiplicity of each irreducible factor counted to determine which ak(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.

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 f: we may write f = qkh, 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} 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=\frac{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.