Vizualizare sursă pentru „Polinom liber de pătrate”

În [[matematică]] un '''polinom liber de pătrate''' este un [[polinom]] definit peste un [[corp (matematică)|corp]] (sau, mai general, un [[domeniu de integritate]]) care nu are ca divizor vreun [[pătrat (algebră) |pătrat]] al unui polinom neconstant.<ref name="yun">{{en icon}} {{cite book |first=David Y.Y. |last=Yun |chapter=On square-free decomposition algorithms |doi=10.1145/800205.806320 |chapter-url=https://dl.acm.org/doi/10.1145/800205.806320 |title=SYMSAC '76 Proceedings of the third ACM symposium on Symbolic and algebraic computation'' |publisher=Association for Computing Machinery |year=1976 |isbn=978-1-4503-7790-4 |pages=26–35 |s2cid=12861227 }}</ref> Un polinom de o singură variabilă este liber de pătrate [[dacă și numai dacă]] nu are vreo [[multiplicitate |rădăcină multiplă]] într-un [[corp algebric închis]] care conține coeficienții săi.

În cazul polinoamelor de o singură variabilă [[Derivarea unui produs|regula produsului]] implică că, dacă {{mvar|p}}<sup>2</sup> divide {{mvar|f}}, atunci {{mvar|p}} divide [[derivată |derivata]] {{mvar|f&thinsp;'}} a lui {{mvar|f}}. Inversa este și ea valabilă în [[caracteristică (algebră) |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ă {{math|1}} 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
:<math>f = a_1 a_2^2 a_3^3 \cdots a_n^n =\prod_{k=1}^n a_k^k</math>
unde cele {{mvar|a<sub>k</sub>}} care sunt neconstante sunt polinoame [[coprim]]e în perechi.<ref name="yun"/> 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 {{ill-wd| Q1476663||ireductibili}}, prin urmare este adesea preferată atunci când factorizarea completă nu este cu adevărat necesară, ca și pentru [[Curbe eliptice|descompunerea în fracții simple]] și obținerea integralelor nedefinite ale [[fracție rațională |fracțiilor raționale]]. Factorizarea liberă de pătrate este primul pas al algoritmilor de factorizare ai polinoamelor care sunt implementați în [[Sistem algebric computerizat|programele de calcul simbolic]]. Prin urmare, algoritmul de factorizare liberă de pătrate este unul de bază în {{ill-wd| Q175515||calculul formal}}.

Peste un corp cu caracteristica 0, câtul lui {{mvar|f}} prin cmmdc al său cu derivata sa este produsul {{mvar|a<sub>i</sub>}} din descompunerea liberă de pătrate de mai sus. Peste un corp perfect cu caracteristică diferită de zero {{mvar|p}}, acest cât este produsul {{mvar|a<sub>i</sub>}} astfel încât {{mvar|i}} nu este un [[multiplu]] al lui {{mvar|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.<ref name="yun"/> {{ill-wd| Q5157286||Complexitatea sa de calcul}} este cel mult de două ori mai mare decât calculul cmmdc al polinomului de intrare și al derivatei sale. Mai precis, dacă {{mvar|T<sub>n</sub>}} este timpul necesar pentru a calcula cmmdc al două polinoame de gradul {{mvar|n}} și câtul acestor polinoame prin cmmdc, atunci {{mvar|2T<sub>n</sub>}} 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ă.<ref name="gianni">{{en icon}} {{cite journal |last1=Gianni |first1=P. |last2=Trager |first2=B. |title=Square-Free Algorithms in Positive Characteristic |journal=Applicable Algebra in Engineering, Communication and Computing |volume=7 |issue=1 |pages=1–14 |year=1996 |doi=10.1007/BF01613611 |s2cid=36886948 }}</ref>

== 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.<ref name="yun"/> Se procedează printr-o succesiune de calcule ale cmmdc și împărțiri exacte.

Intrarea este un polinom diferit de zero, {{mvar|f}}, iar primul pas al algoritmului constă în calcularea cmmdc {{mvar|a}}<sub>0</sub> al lui {{mvar|f}} și al derivatei sale {{mvar|f&thinsp;'}}.

Dacă
:<math>f = a_1 a_2^2 a_3^3 \cdots a_k^k</math>
este factorizarea dorită, atunci 
:<math>a_0 =  a_2^1 a_3^2 \cdots a_k^{k-1}, </math>
:<math>f/a_0 = a_1 a_2 a_3 \cdots a_k </math>
și
:<math>f^{\,\prime}/a_0 =  \sum_{i=1}^k i a_i' a_1 \cdots a_{i-1} a_{i+1} \cdots a_k.</math>

Dacă se pune <math>b_1=f/a_0</math>, <math>c_1=f^{\,\prime}/a_0</math> și <math>d_1=c_1-b_1'</math>, se obține
:<math>\text{cmmdc}(b_1,d_1) = a_1,</math>
:<math>b_2=b_1/a_1 = a_2 a_3 \cdots a_n,</math>
și
:<math>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.</math>

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

Acest lucru este formalizat într-un algoritm după cum urmează:
:<math> 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;</math> 
:repetă
::<math>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'; </math>
:până când <math>b=1;</math>
:Rezultatul <math>a_1,\,\ldots\,, a_{i-1}.</math>

Gradul lui {{mvar|c<sub>i</sub>}} și {{mvar|d<sub>i</sub>}} este cu unu mai mic decât gradul lui {{mvar|b<sub>i</sub>}}. Deoarece {{mvar|f}} este produsul {{mvar|b<sub>i</sub>}}, suma gradelor {{mvar|b<sub>i</sub>}} este gradul lui {{mvar|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 {{mvar|f}} și {{mvar|f&thinsp;'}} și câtul lui {{mvar|f}} și {{mvar|f&thinsp;'}} 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.

== Note ==
<references responsive/>

{{Portal|Matematică}}
{{Polinoame}}
{{Control de autoritate}}

[[Categorie:Polinoame]]
[[Categorie:Calcul formal]]