In mathematics, a squarefree polynomial is a polynomial defined over a field or, more generally, a unique factorization domain that is not a multiple of the square of a non unit factor. In the important case of univariate polynomials over a field k, this means that, f \in k[X] is squarefree if and only if b^2 \nmid f for every polynomial b \in k[X] of positive degree.^{[1]} In applications in physics and engineering, a squarefree polynomial is commonly called a polynomial with no repeated roots (such polynomials are called separable, but over a perfect field that is the same as squarefree).
A squarefree decomposition or squarefree factorization of a polynomial is a factorization into powers of squarefree factors

f = a_1 a_2^2 a_3^3 \cdots a_n^n \,
where the a_{k} that are not equal to 1 are pairwise coprime squarefree polynomials.^{[1]} Every nonzero polynomial with coefficients in a field admits a squarefree factorization, which is unique up to the multiplication of the factors by non zero constants. The squarefree 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, like for the partial fraction decomposition and the symbolic integration of rational fractions. Squarefree factorization is the first step of the polynomial factorization algorithms which are implemented in computer algebra systems. Therefore, the algorithm of squarefree 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 squarefree is that the greatest common divisor of f and f ′ is 1. Over a perfect field, all irreducible polynomials are separable, so that condition is also necessary. If the polynomial is not square free, the product of the a_i in the above square free decomposition may be obtained as the quotient of f by its GCD with its derivative. Further GCD computations and exact divisions allow to compute the squarefree factorization (see squarefree 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 T_{n} is the time needed to compute the GCD of two polynomials of degree n and the quotient of these polynomial by the GCD, then 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 squarefree decomposition of multivariate polynomials.^{[2]}
Yun's algorithm
In this section we describe Yun's algorithm for the squarefree 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 a_{0} of f and its formal derivative f'.
If

f = a_1 a_2^2 a_3^3 \cdots a_k^k
is the desired factorization, we have thus

a_0 = a_2^1 a_3^2 \cdots a_k^{k1},

f/a_0 = a_1 a_2 a_3 \cdots a_k
and

f'/a_0 = \sum_{i=1}^k i a_i' a_1 \cdots a_{i1} a_{i+1} \cdots a_k.
If we set b_1=f/a_0, c_1=f'/a_0 and d_1=c_1b_1', we get that

\gcd(b_1,d_1) = a_1,

b_2=b_1/a_1 = a_2 a_3 \cdots a_n,
and

c_2=d_1/a_1 = \sum_{i=2}^k (i1) a_i' a_2 \cdots a_{i1} a_{i+1} \cdots a_k.
Iterating this process until b_{k+1}=1 we find all the a_i.
This is formalized into an algorithm as follows:
The degree of c_i and d_i is one less than the degree of b_i. As f is the product of the b_i, the sum of the degrees of the b_i is the degree of 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 f and f' and the quotient of f and f' by their GCD.
Notes

^ ^{a} ^{b} ^{c} ^{d} Yun, David Y.Y. (1976). On squarefree decomposition algorithms SYMSAC '76 Proceedings of the third ACM symposium on Symbolic and algebraic computation, p. 2635.

^ Gianni P., Trager B. (1996). SquareFree Algorithms in Positive Characteristic Applicable Algebra In Engineering, Communication And Computing, 7(1), p. 114.
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.