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.^[1] 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^⁠(d) implică că, dacă p² divide f, atunci p divide derivata f ' a lui f. 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ă 1 este cel mai mare divizor comun (cmmdc) al polinomului și al derivatei sale.

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

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

unde cele a_k care sunt neconstante sunt polinoame coprime în perechi.^[1] 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 ireductibili^⁠(d), 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 calculul formal^⁠(d).

Peste un corp cu caracteristica 0, câtul lui f prin cmmdc al său cu derivata sa este produsul a_i din descompunerea liberă de pătrate de mai sus. Peste un corp perfect cu caracteristică diferită de zero p, acest cât este produsul a_i astfel încât i nu este un multiplu al lui p. 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.^[1] Complexitatea sa de calcul^⁠(d) este cel mult de două ori mai mare decât calculul cmmdc al polinomului de intrare și al derivatei sale. Mai precis, dacă T_n este timpul necesar pentru a calcula cmmdc al două polinoame de gradul n și câtul acestor polinoame prin cmmdc, atunci 2T_n 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ă.^[2]

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.^[1] Se procedează printr-o succesiune de calcule ale cmmdc și împărțiri exacte.

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

Dacă

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

este factorizarea dorită, atunci

${\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}}$

și

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

Dacă se pune ${\displaystyle b_{1}=f/a_{0}}$, ${\displaystyle c_{1}=f^{\,\prime }/a_{0}}$ și ${\displaystyle d_{1}=c_{1}-b_{1}'}$, se obține

${\displaystyle {\text{cmmdc}}(b_{1},d_{1})=a_{1},}$

${\displaystyle b_{2}=b_{1}/a_{1}=a_{2}a_{3}\cdots a_{n},}$

și

${\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}.}$

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

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

${\displaystyle a_{0}:={\text{cmmdc}}(f,f^{\,\prime });\quad b_{1}:=f/a_{0};\quad c_{1}:=f^{\,\prime }/a_{0};\quad d_{1}:=c_{1}-b_{1}';\quad i:=1;}$

repetă

${\displaystyle a_{i}:={\text{cmmdc}}(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}';}$

până când ${\displaystyle b=1;}$

Rezultatul ${\displaystyle a_{1},\,\ldots \,,a_{i-1}.}$

Gradul lui c_i și d_i este cu unu mai mic decât gradul lui b_i. Deoarece f este produsul b_i, suma gradelor b_i este gradul lui f. 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 f și f ' și câtul lui f și f ' prin cmmdc al lor.

Î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.

Portal Matematică