# Square-free polynomial

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, ${\displaystyle f\in k[X]}$ is square-free if and only if ${\displaystyle b^{2}\nmid f}$ for every polynomial ${\displaystyle b\in k[X]}$ of positive degree.[1] In applications in physics and engineering, a square-free polynomial is commonly called a polynomial with no repeated roots. Such polynomials are called separable, but over a perfect field being separable is the same as being square-free.

A square-free decomposition or square-free factorization of a polynomial is a factorization into powers of square-free factors

${\displaystyle f=a_{1}a_{2}^{2}a_{3}^{3}\cdots a_{n}^{n}=\prod _{k=1}^{n}a_{k}^{k}\,}$

where those of the ak that are not equal to 1 are pairwise coprime square-free polynomials.[1] 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 ${\displaystyle f}$ by its GCD with its derivative is the product of the ${\displaystyle a_{i}}$ in the above square free decomposition. Over a perfect field of nonzero characteristic p, this quotient is the product of the ${\displaystyle a_{i}}$ such that i is not a multiple of p. Further GCD computations and exact divisions allow computing the square-free factorization (see square-free factorization over a finite field). In characteristic zero, a better algorithm is known, Yun's algorithm, which is described below.[1] Its computational complexity is, at most, twice that of the GCD computation of the input polynomial and its derivative. More precisely, if ${\displaystyle T_{n}}$ is the time needed to compute the GCD of two polynomials of degree ${\displaystyle n}$ and the quotient of these polynomial by the GCD, then ${\displaystyle 2T_{n}}$ is an upper bound for the time needed to compute the square free decomposition.

There are also known algorithms for the computation of the square-free decomposition of multivariate polynomials.[2]

## 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.[1] 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

${\displaystyle f=a_{1}a_{2}^{2}a_{3}^{3}\cdots a_{k}^{k}}$

is the desired factorization, we have thus

${\displaystyle a_{0}=a_{2}^{1}a_{3}^{2}\cdots a_{k}^{k-1},}$
${\displaystyle f/a_{0}=a_{1}a_{2}a_{3}\cdots a_{k}}$

and

${\displaystyle f'/a_{0}=\sum _{i=1}^{k}ia_{i}'a_{1}\cdots a_{i-1}a_{i+1}\cdots a_{k}.}$

If we set ${\displaystyle b_{1}=f/a_{0}}$, ${\displaystyle c_{1}=f'/a_{0}}$ and ${\displaystyle d_{1}=c_{1}-b_{1}'}$, we get that

${\displaystyle \gcd(b_{1},d_{1})=a_{1},}$
${\displaystyle b_{2}=b_{1}/a_{1}=a_{2}a_{3}\cdots a_{n},}$

and

${\displaystyle c_{2}=d_{1}/a_{1}=\sum _{i=2}^{k}(i-1)a_{i}'a_{2}\cdots a_{i-1}a_{i+1}\cdots a_{k}.}$

Iterating this process until ${\displaystyle b_{k+1}=1}$ we find all the ${\displaystyle a_{i}.}$

This is formalized into an algorithm as follows:

${\displaystyle a_{0}:=\gcd(f,f');\quad b_{1}:=f/a_{0};\quad c_{1}:=f'/a_{0};\quad d_{1}:=c_{1}-b_{1}';\quad i:=1;}$
repeat
${\displaystyle a_{i}:=\gcd(b_{i},d_{i});\quad b_{i+1}:=b_{i}/a_{i};\quad c_{i+1}:=d_{i}/a_{i};\quad i:=i+1;\quad d_{i}:=c_{i}-b_{i}';}$
until ${\displaystyle b=1;}$
Output ${\displaystyle a_{1},\ldots ,a_{i-1}.}$

The degree of ${\displaystyle c_{i}}$ and ${\displaystyle d_{i}}$ is one less than the degree of ${\displaystyle b_{i}.}$ As ${\displaystyle f}$ is the product of the ${\displaystyle b_{i},}$ the sum of the degrees of the ${\displaystyle b_{i}}$ is the degree of ${\displaystyle f.}$ As the complexity of GCD computations and divisions increase more than linearly with the degree, it follows that the total running time of the "repeat" loop is less than the running time of the first line of the algorithm, and that the total running time of Yun's algorithm is upper bounded by twice the time needed to compute the GCD of ${\displaystyle f}$ and ${\displaystyle f'}$ and the quotient of ${\displaystyle f}$ and ${\displaystyle f'}$ by their GCD.

## Notes

1. ^ a b c d Yun, David Y.Y. (1976). On square-free decomposition algorithms SYMSAC '76 Proceedings of the third ACM symposium on Symbolic and algebraic computation, p. 26-35.
2. ^ Gianni P., Trager B. (1996). Square-Free Algorithms in Positive Characteristic Applicable Algebra In Engineering, Communication And Computing, 7(1), p. 1-14.