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 $b 3$ divided the polynomial, then $b 2$ 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 $a k (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 $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.

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 = q k h$ , 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.

Categories: Polynomials

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Square-free polynomial

From Wikipedia, the free encyclopedia

Views

Navigation

Interaction

Search