Polinom liber de pătrate

În matematică un polinom liber de pătrate este un polinom definit peste un corp (sau, mai general, un domeniu de integritate) care nu are ca divizor vreun pătrat al unui polinom neconstant. Un polinom de o singură variabilă este liber de pătrate dacă și numai dacă nu are vreo rădăcină multiplă într-un corp algebric închis care conține coeficienții săi.

În cazul polinoamelor de o singură variabilă regula produsului implică că, dacă Format:Mvar² divide Format:Mvar, atunci Format:Mvar divide derivata Format:Mvar a lui Format:Mvar. Inversa este și ea valabilă în caracteristica zero și pentru polinoame peste un corp finit (sau, mai general, peste un corp perfect). Adică, în aceste cazuri, un polinom este liber de pătrate dacă și numai dacă Format:Math este cel mai mare divizor comun (cmmdc) al polinomului și al derivatei sale.

Descriere

O descompunere liberă de pătrate sau factorizare liberă de pătrate a unui polinom este o factorizare după puteri prin polinoame libere de pătrate

$f=a_1{a}_2^2{a}_3^3\cdots a_n^n=\prod _{k=1}^n{a}_k^k$

unde cele Format:Mvar care sunt neconstante sunt polinoame coprime în perechi. Fiecare polinom nenul admite o factorizare liberă de pătrate, care este unică până la înmulțirea și împărțirea factorilor cu constante nenule. Factorizarea liberă de pătrate este mult mai ușor de calculat decât factorizarea completă în factori Format:Ill-wd, prin urmare este adesea preferată atunci când factorizarea completă nu este cu adevărat necesară, ca și pentru descompunerea în fracții simple și obținerea integralelor nedefinite ale fracțiilor raționale. Factorizarea liberă de pătrate este primul pas al algoritmilor de factorizare ai polinoamelor care sunt implementați în programele de calcul simbolic. Prin urmare, algoritmul de factorizare liberă de pătrate este unul de bază în Format:Ill-wd.

Peste un corp cu caracteristica 0, câtul lui Format:Mvar prin cmmdc al său cu derivata sa este produsul Format:Mvar din descompunerea liberă de pătrate de mai sus. Peste un corp perfect cu caracteristică diferită de zero Format:Mvar, acest cât este produsul Format:Mvar astfel încât Format:Mvar nu este un multiplu al lui Format:Mvar. Alte calcule despre cmmdc și divizările exacte permit calcularea factorizării libere de pătrată. Pentru caracteristica zero, este cunoscut un algoritm mai bun, algoritmul lui Yun, care este descris mai jos. Format:Ill-wd este cel mult de două ori mai mare decât calculul cmmdc al polinomului de intrare și al derivatei sale. Mai precis, dacă Format:Mvar este timpul necesar pentru a calcula cmmdc al două polinoame de gradul Format:Mvar și câtul acestor polinoame prin cmmdc, atunci Format:Mvar este o limită superioară pentru timpul necesar pentru a calcula descompunerea liberă de pătrate.

De asemenea, există algoritmi cunoscuți pentru calcularea descompunerii liberă de pătrate a polinoamelor de mai multe variabile, care lucrează în general prin considerarea unui polinom de mai multe variabile ca fiind un polinom de o singură variabilă cu coeficienți polinomiali și aplicând recursiv un algoritm pentru o singură variabilă.

Algoritmul lui Yun

Această secțiune descrie algoritmul lui Yun pentru descompunerea liberă de pătrate a polinoamelor de o singură variabilă peste un corp cu caracteristica 0. Se procedează printr-o succesiune de calcule ale cmmdc și împărțiri exacte.

Intrarea este un polinom diferit de zero, Format:Mvar, iar primul pas al algoritmului constă în calcularea cmmdc Format:Mvar₀ al lui Format:Mvar și al derivatei sale Format:Mvar.

Dacă

$f=a_1{a}_2^2{a}_3^3\cdots a_k^k$

este factorizarea dorită, atunci

$a_0=a_2^1{a}_3^2\cdots a_k^{k-1},$

$f/a_0=a_1{a}_2{a}_3\cdots a_k$

și

$f^{\prime }/a_0=\sum _{i=1}^{k}i{a_i}^{\prime }{a}_1\cdots a_{i-1}{a}_{i+1}\cdots a_k.$

Dacă se pune $b_1=f/a_0$, $c_1=f^{\prime }/a_0$ și $d_1=c_1-{b_1}^{\prime }$, se obține

$\text{cmmdc}(b_1,d_1)=a_1,$

$b_2=b_1/a_1=a_2{a}_3\cdots a_n,$

și

$c_2=d_1/a_1=\sum _{i=2}^k(i-1){a_i}^{\prime }{a}_2\cdots a_{i-1}{a}_{i+1}\cdots a_k.$

Iterând până la $b_{k+1}=1$ se obțin toți $a_i.$

Acest lucru este formalizat într-un algoritm după cum urmează:

$a_0:=\text{cmmdc}(f,f^{\prime });b_1:=f/a_0;c_1:=f^{\prime }/a_0;d_1:=c_1-{b_1}^{\prime };i:=1;$

repetă

$a_i:=\text{cmmdc}(b_i,d_i);b_{i+1}:=b_i/a_i;c_{i+1}:=d_i/a_i;i:=i+1;d_i:=c_i-{b_i}^{\prime };$

până când $b=1;$

Rezultatul $a_1,\dots ,a_{i-1}.$

Gradul lui Format:Mvar și Format:Mvar este cu unu mai mic decât gradul lui Format:Mvar. Deoarece Format:Mvar este produsul Format:Mvar, suma gradelor Format:Mvar este gradul lui Format:Mvar. Pe măsură ce complexitatea calculelor și împărțirilor cu cmmdc crește mai mult decât liniar cu gradul, rezultă că timpul total de rulare al buclei de „repetare” este mai mic decât timpul de rulare al primei linii a algoritmului și că timpul total de rulare al algoritmului lui Yun este limitat superior de dublul timpului necesar pentru a calcula cmmdc al Format:Mvar și Format:Mvar și câtul lui Format:Mvar și Format:Mvar prin cmmdc al lor.

Rădăcina pătrată

În general, un polinom nu are rădăcină pătrată. Mai precis, majoritatea polinoamelor nu pot fi scrise ca pătratul altui polinom.

Un polinom are rădăcină pătrată dacă și numai dacă toți exponenții descompunerii libere de pătrate sunt pari. În acest caz, rădăcina pătrată se obține împărțind la 2 acești exponenți.

Astfel, problema de a decide dacă un polinom are rădăcină pătrată și de a calcula dacă aceasta există, este un caz particular de factorizare liberă de pătrate.