Kvadratfritt polynom

I matematik är ett kvadratfritt polynom ett polynom som definieras över ett fält (eller mer allmänt, en integraldomän ) som inte har som divisor någon kvadrat av ett icke-konstant polynom . Ett univariat polynom är kvadratfritt om och endast om det inte har någon multipelrot i ett algebraiskt slutet fält som innehåller dess koefficienter. Detta motiverar att, i tillämpningar inom fysik och teknik, kallas ett kvadratfritt polynom vanligtvis för ett polynom utan upprepade rötter .

I fallet med univariata polynom innebär produktregeln att om p ² delar f , så delar p den formella derivatan   f ' av f . Det omvända är också sant och därför $f$ kvadratfri om och endast om $1$ är en största gemensamma divisor för polynomet och dess derivata.

En kvadratfri nedbrytning eller kvadratfri faktorisering av ett polynom är en faktorisering till potenser av kvadratfria polynom

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

där de av a _k som är icke-konstanta är parvisa coprime square-fria polynom (här sägs två polynom att coprime är deras största gemensamma divisor är en konstant; med andra ord det är coprimaliteten över fältet av bråkdelar av koefficienterna som anses). Varje polynom som inte är noll tillåter en kvadratfri faktorisering, som är unik upp till multiplikation och division av faktorerna med konstanter som inte är noll. Den kvadratfria faktoriseringen är mycket lättare att beräkna än den fullständiga faktoriseringen till irreducerbara faktorer, och är därför ofta att föredra när den fullständiga faktoriseringen egentligen inte behövs, som för den partiella bråknedbrytningen och den symboliska integrationen av rationella bråk . Kvadratfri faktorisering är det första steget i polynomfaktoriseringsalgoritmerna som är implementerade i datoralgebrasystem . Därför är algoritmen för kvadratfri faktorisering grundläggande i datoralgebra .

Över ett fält med karakteristik 0 är kvoten av $f$ av dess GCD med dess derivata produkten av $a_{i}$ i ovanstående kvadratfria nedbrytning. Över ett perfekt fält av icke-noll karakteristik p , är denna kvot produkten av a $\displaystyle a_{i}}$ så att i inte är en multipel av p . Ytterligare GCD-beräkningar och exakta divisioner tillåter beräkning av den kvadratfria faktoriseringen (se kvadratfri faktorisering över ett ändligt fält ) . I karakteristiken noll är en bättre algoritm känd, Yuns algoritm, som beskrivs nedan. Dess beräkningskomplexitet är som mest dubbelt så stor som GCD-beräkningen av ingångspolynomet och dess derivata. Närmare bestämt, om $T_{n}$ är den tid som behövs för att beräkna GCD för två polynom av grad $n$ och kvoten för dessa polynom med GCD, då $2T_{n}$ är en övre gräns för den tid som behövs för att beräkna kvadratens fria nedbrytning.

Det finns också kända algoritmer för beräkning av den kvadratfria sönderdelningen av multivariata polynom , som i allmänhet fortsätter genom att betrakta ett multivariat polynom som ett univariat polynom med polynomkoefficienter, och rekursivt tillämpa en univariat algoritm.

Yuns algoritm

Det här avsnittet beskriver Yuns algoritm för kvadratfri nedbrytning av univariata polynom över ett fält med karakteristisk 0 . Det fortsätter genom en följd av GCD- beräkningar och exakta divisioner.

₀ Ingången är således ett polynom f som inte är noll , och det första steget i algoritmen består av att beräkna GCD a för f och dess formella derivata f' .

Om

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

är den önskade faktoriseringen har vi alltså

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

och

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

Om vi ​​sätter $b_{1}=f/a_{0}$ , $c_{1}=f'/a_{0}$ och ${\displaystyle d_{1}=c_{1}-b_{1}'} ,$ vi får det

$\gcd(b_{1},d_{1})=a_{1},$

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

och

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

Genom att iterera denna process tills $b_{k+1}=1$ hittar vi alla $a_{i}.$

Detta formaliseras till en algoritm enligt följande:

$a_{0}:=\gcd(f,f');\quad b_{1}:=f/a_{0};\quad c_{1}:=f'/a_{0};\ quad d_{1}:=c_{1}-b_{1}';\quad i:=1;$ upprepa $a_{i}:=\gcd(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}';$ tills $b=1;$ Utmatning $a_{1},\ldots ,a_{i-1}.$

Graden av $c_{i}$ och $d_{i}$ är en mindre än graden av $b_{i}.$ Eftersom $f$ är produkten av $b_{i},$ summan av graderna av $b_{i}$ är graden av $f.$ Eftersom komplexiteten för GCD-beräkningar och -divisioner ökar mer än linjärt med graden, följer det att den totala körtiden för "upprepa"-slingan är mindre än körtiden för den första raden i algoritmen, och att den totala körtiden för Yuns algoritm är övre gränsen till två gånger den tid som behövs för att beräkna GCD för $f$ och $f'$ och kvoten av $f$ och ${ \displaystyle f'}$ av deras GCD.

Roten ur

I allmänhet har ett polynom ingen kvadratrot . Mer exakt kan de flesta polynom inte skrivas som kvadraten på ett annat polynom.

Ett polynom har en kvadratrot om och bara om alla exponenter för den kvadratfria nedbrytningen är jämna. I det här fallet erhålls en kvadratrot genom att dividera dessa exponenter med 2.

Således är problemet med att avgöra om ett polynom har en kvadratrot, och att beräkna det om det finns, ett specialfall av kvadratfri faktorisering.