Polinomi lliure de quadrats

En matemàtiques, un polinomi lliure de quadrats (també denominat polinomi sense quadrats, polinomi sense raïls repetides o polinomi sense raïls múltiples) és un polinomi definit sobre un cos (o més generalment, un domini d'integritat) que no té com divisor cap quadrat d'un polinomi no constant.^[1] Es diu que un polinomi està lliure de quadrats si i solament si no té multiplicitat en un cos algebraicamente tancat que conté els seus coeficients. Açò motiva que en aplicacions de física i ingenieria, un polinomi lliure de quadrats es denomina comunament com un polinomi sense raïls repetides.

Propietats

En el cas de polinomis d'una sola variable, la regla del producte implica que, si $p 2$ dividix a $f$ , llavors $p$ dividix a la derivada formal $f'$ de $f$ . Ho contrarie també és cert en característica zero i per a polinomis sobre un cos finito (o, més generalment, sobre un cos perfecte). És dir, en estos casos, un polinomi està lliure de quadrats si i solament si el màxim comú divisor del polinomi i de la seua derivada és $1$ .

Una descomposició lliure de quadrats o factorización sense quadrats d'un polinomi és una factorización en potències de polinomis lliures de quadrats

f = a_{1} a_{2}^{2} a_{3}^{3} \dots a_{n}^{n} = \prod_{k = 1}^{n} a_{k}^{k}

a on els $a k$ que no són constants són polinomis lliures de quadrats coprimos dos a dos (ací, dos polinomis es diu que són coprimos quan el seu màxim comú divisor és una constant; en atres paraules, que es verifica la coprimalidad sobre el cos de fraccions dels coeficients que es consideren).^[1] Tot polinomi distint de zero d'una factorización lliure de quadrats és única llevat per la multiplicació i divisió dels factors per constants distintes de zero. La factorización lliure de quadrats és molt més fàcil de calcular que la factorización completa en factors irreducibles i, per lo tant, a sovint es preferix quan la factorización completa no és realment necessària, com per a la descomposició descomposició en fraccions simples i integració simbòlica de fraccions. La factorización sense quadrats és el primer pas dels algoritmes de factorización de polinomis desenrollats en sistemes algebraics computacionals. Per tant, l'algoritme d'factorización lliure de quadrats és bàsic en el càlcul simbòlic.

Sobre un cos de característica 0, el cocient de $f$ pel seu màxim comú divisor sobre la seua derivada, és el producte de $a_{i}$ en la descomposició sense quadrats anterior. Sobre un cos perfecte de característica distinta de zero $p$ , este cocient és el producte de $a_{i}$ tal que $i$ no és un múltiple de $p$ . Els càlculs adicionals del màxim comú divisor (MCD) i les divisions exactes permeten calcular la factorización lliure de quadrats (consulte's factorización lliure de quadrats sobre un cos finito). En característica zero, es coneix un algoritme millor, l'algoritme de Yun, que es descriu a continuació.^[1] El seu complexitat computacional és, com a màxim, el doble del càlcul de el MCD del polinomi d'entrada i la seua derivada. Més precisament, si $T_{n}$ és el temps necessari per a calcular el MCD de dos polinomis de grau $n$ i el cocient d'estos polinomis per el MCD, llavors $2 T_{n}$ és un llímit superior del temps necessari per a calcular la descomposició lliure de quadrats.

També existixen algoritmes coneguts per al càlcul de la descomposició lliure de quadrats de polinomis, que procedixen generalment considerant un polinomi multivariable com un polinomi d'una variable en coeficients polinomiales, i aplicant recursivamente un algoritme d'una variable.^[2]

Algoritme de Yun

Esta secció descriu l'algoritme de Yun per a la descomposició sense quadrats, de polinomis d'una variable sobre un cos de característica 0.^[1] Procedix per mig d'una successió de càlculs del MCD i divisions exactes.

Per lo tant, l'entrada és un polinomi f distint de zero, i el primer pas de l'algoritme consistix en calcular el MCD a₀ de f i de la seua derivada formal f'.

Si

f = a_{1} a_{2}^{2} a_{3}^{3} \dots a_{k}^{k}

és la factorización desijada, es té que

a_{0} = a_{2}^{1} a_{3}^{2} \dots a_{k}^{k - 1},

f / a_{0} = a_{1} a_{2} a_{3} \dots a_{k}

i

f^{'} / a_{0} = \sum_{i = 1}^{k} i {a_{i}}^{'} a_{1} \dots a_{i - 1} a_{i + 1} \dots a_{k} .

Si es configuren $b_{1} = f / a_{0}$ , $c_{1} = f^{'} / a_{0}$ i $d_{1} = c_{1} - {b_{1}}^{'}$ , s'obté que

MCD (b_{1}, d_{1}) = a_{1},

b_{2} = b_{1} / a_{1} = a_{2} a_{3} \dots a_{n},

i

c_{2} = d_{1} / a_{1} = \sum_{i = 2}^{k} (i - 1) {a_{i}}^{'} a_{2} \dots a_{i - 1} a_{i + 1} \dots a_{k} .

Iterando este procés fins que $b_{k + 1} = 1$ es troben tots els $a_{i} .$

Açò es formalisa en un algoritme de la següent manera:

El grau de $c_{i}$ i $d_{i}$ és menor en una unitat que el grau de $b_{i} .$ Com $f$ és el producte de $b_{i},$ la suma dels graus de $b_{i}$ és el grau de $f .$ A mida que la complexitat dels càlculs i divisions de el MCD aumenta més que linealmente en el grau , es deduïx que el temps d'eixecució total del cicle de "repetició" és menor que el temps d'eixecució de la primera llínea de l'algoritme, i que el temps d'eixecució total de l'algoritme de Yun està llimitat pel doble del temps necessari per a calcular el MCD de $f$ i de $f^{'}$ i el cocient de $f$ i $f^{'}$ pel seu MCD.

Raïl quadrada

En general, un polinomi no té raïl quadrada. Més precisament, la majoria dels polinomis no es poden escriure com el quadrat d'un atre polinomi.

Un polinomi té una raïl quadrada si i solament si tots els exponents de la descomposició lliure de quadrats són parells. En este cas, la raïl quadrada s'obté dividint per 2 estos exponents.

Per lo tant, el problema de decidir si un polinomi té raïl quadrada i de calcular-la si existix, és un cas especial d'factorización lliure de quadrats.

Referències

↑ ^1,0 ^1,1 ^1,2 ^1,3 Yun, David Y.Y. (1976). «On square-free decomposition algorithms», SYMSAC '76 Proceedings of the third ACM symposium on Symbolic and algebraic computation, Association for Computing Machinery, pp. 26–35. doi:10.1145/800205.806320. ISBN 978-1-4503-7790-4.
↑ “Square-Free Algorithms in Positive Characteristic” (1996). Applicable Algebra in Engineering, Communication and Computing 7 (1): 1–14. doi:10.1007/BF01613611.

Referències

Este artícul conté una traducció derivada de «Polinomio libre de cuadrados» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[yun-1] 1,0 ^1,1 ^1,2 ^1,3 Yun, David Y.Y. (1976). «On square-free decomposition algorithms», SYMSAC '76 Proceedings of the third ACM symposium on Symbolic and algebraic computation, Association for Computing Machinery, pp. 26–35. doi:10.1145/800205.806320. ISBN 978-1-4503-7790-4.

[gianni-2] “Square-Free Algorithms in Positive Characteristic” (1996). Applicable Algebra in Engineering, Communication and Computing 7 (1): 1–14. doi:10.1007/BF01613611.

[1]

[2]