Square-Free Polynomial

In mathematics, a square-free polynomial is a polynomial defined over a field (or more generally, an integral domain) that does not have as a divisor any square of a non-constant polynomial.

A univariate polynomial is square free if and only if it has no multiple root in an algebraically closed field containing its coefficients. This motivates that, in applications in physics and engineering, a square-free polynomial is commonly called a polynomial with no repeated roots.

In the case of univariate polynomials, the product rule implies that, if p2 divides f, then p divides the formal derivative f' of f. The converse is also true and hence, is square-free if and only if is a greatest common divisor of the polynomial and its derivative.

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

where those of the ak that are non-constant are pairwise coprime square-free polynomials (here, two polynomials are said coprime is their greatest common divisor is a constant; in other words that is the coprimality over the field of fractions of the coefficients that is considered). Every non-zero polynomial admits a square-free factorization, which is unique up to the multiplication and division 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 that are implemented in computer algebra systems. Therefore, the algorithm of square-free factorization is basic in computer algebra.

Over a field of characteristic 0, the quotient of by its greatest common divisor (GCD) with its derivative is the product of the in the above square-free decomposition. Over a perfect field of non-zero characteristic p, this quotient is the product of the 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. Its computational complexity is, at most, twice that of the GCD computation of the input polynomial and its derivative. More precisely, if is the time needed to compute the GCD of two polynomials of degree and the quotient of these polynomial by the GCD, then 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, that proceed generally by considering a multivariate polynomial as a univariate polynomial with polynomial coefficients, and applying recursively a univariate algorithm.

Yun's algorithm

This section describes 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 of computing the GCD a0 of f and its formal derivative f'.

If

    Square-Free Polynomial 

is the desired factorization, we have thus

    Square-Free Polynomial 
    Square-Free Polynomial 

and

    Square-Free Polynomial 

If we set Square-Free Polynomial , Square-Free Polynomial  and Square-Free Polynomial , we get that

    Square-Free Polynomial 
    Square-Free Polynomial 

and

    Square-Free Polynomial 

Iterating this process until Square-Free Polynomial  we find all the Square-Free Polynomial 

This is formalized into an algorithm as follows:

Square-Free Polynomial 
repeat
Square-Free Polynomial 
until Square-Free Polynomial 
Output Square-Free Polynomial 

The degree of Square-Free Polynomial  and Square-Free Polynomial  is one less than the degree of Square-Free Polynomial  As Square-Free Polynomial  is the product of the Square-Free Polynomial  the sum of the degrees of the Square-Free Polynomial  is the degree of Square-Free Polynomial  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 Square-Free Polynomial  and Square-Free Polynomial  and the quotient of Square-Free Polynomial  and Square-Free Polynomial  by their GCD.

Square root

In general, a polynomial has no square root. More precisely, most polynomials cannot be written as the square of another polynomial.

A polynomial has a square root if and only if all exponents of the square-free decomposition are even. In this case, a square root is obtained by dividing these exponents by 2.

Thus the problem of deciding if a polynomial has a square root, and of computing it if it exists, is a special case of square-free factorization.

Notes

References

Tags:

Square-Free Polynomial Yuns algorithmSquare-Free Polynomial Square rootSquare-Free PolynomialAlgebraically closed fieldConstant polynomialDivisibility (ring theory)Field (mathematics)Integral domainMathematicsMultiple rootPolynomialUnivariate polynomial

🔥 Trending searches on Wiki English:

VietnamNATOShōgun (novel)Maundy ThursdayWinston ChurchillIsaiah HartensteinHoly WeekBill GatesElizabeth IIAriana GrandeDavid CameronSolar eclipseJason StathamMichael KeatonShaitaan (2024 film)TenebraeBlackRockShogunFreddie MercuryYodha (2024 film)Rebekah NeumannBeetlejuice BeetlejuiceWilliam Adams (pilot)Benedict WongEarthPhilippinesSoaking (sexual practice)Nicolas Cage2022 FIFA World CupSunrisers HyderabadGoogleBad Boy RecordsEiza GonzálezIslamic StateAdolf HitlerRyan GoslingKanye WestCheryl HinesGeorge IIIBattle of BadrSibgatullah AnsariTelegram (software)South AfricaFormula OneMckenna GraceKristen WiigIsrael–Hamas warPassoverChristina ApplegateVinayak Damodar SavarkarBarbie (film)Caitlin ClarkSawai Mansingh Indoor StadiumHiroyuki SanadaList of United States cities by populationThe Amanda ShowRobert HanssenJoely RichardsonMahatma GandhiMia KhalifaEwan McGregorCanadaCleopatraMount TakaheBrandon ScottKen MilesXXXTentacionAlexander the GreatMalaysia Airlines Flight 370Lewis HamiltonSerbiaGeorgia (country)Elvis PresleyPeter principleNapoleonZoe SaldañaMasters of the Air🡆 More