Tesi - Studio dei polinomi di quinto grado

Z

Di conseguenza , cosìcché

∀σ ∈ G G ⊂

(σ) = 1 A

n

Enunciamo ora per completezza il più importante Teorema riguardante la risolvente

polinomiale.

Teorema 2.3.4. Sia .

m = [G : H] = deg(R (F, T ))

G

Allora, se è squarefree, il suo gruppo di Galois (come sottogruppo di )

R (F, T ) S m

G

è uguale a , ove è il naturale omomorsmo tra gruppi da a dato dalla

Φ(G) Φ G S m

naturale azione sinistra di su .

G G/H

In particolare, la lista dei gradi dei fattori irriducibili di in è la stessa delle

R (F, T ) Z

G

lunghezze delle orbite dell'azione di su .

Φ(G) [1 . . . , m]

Ad esempio, ha radice in se e solo se è coniugato sotto ad un sottogruppo

G

R (F, t) G

Z

G

di .

H

Il Teorema che ora enunciamo senza dimostrazione è utile ai ni dell'Algoritmo

2.4.10, poiché determina una forte relazione tra i coecienti dei due polinomi conside-

rati.

Teorema 2.3.5 . Per ogni polinomio X

(sui Vincoli sui Fattori Polinomiali) i ∈

P = p X

i

0≤i≤n

2

!

poniamo . Sia e polinomi

X X X

2 i i

| |= | |

P p A = a X B = B X

C[X] i i i

i 0≤i≤m 0≤i≤n

a coecienti interi, e assumiamo che . Allora abbiamo che per ogni :

|

B A j

− −

n 1 n 1

| |≤ | | | |

b A + a

m

j −

j j 1

Teorema 2.3.6. Siano interi non necessariamente primi e sia Siano

p, q r = gcd(p, q)

e polinomi a coecienti interi soddisfacenti:

C, A, B, U V ≡ ≡

C AB U A + V B 1

q p

CAPITOLO 2. TEORIA DI GALOIS: FONDAMENTI E DEFINIZIONI10

e assumiamo che , , e

gcd(`(A), r) = 1 deg(U ) < deg(B) deg(V ) < deg(A) deg(C) =

.

deg(A) + deg(B)

Allora esistono polinomi tali che , , ,

≡ ≡

A , B A A B B `(A ) = `(A) deg(A ) =

1 1 1 q 1 q 1 1

, e

deg(B) deg(B ) = deg(B)

1 ≡

C A B

qr 1 1

In più, e sono unici modulo se è primo

A B qr r

1 1

Nota 2.3.7. La dimostrazione del Teorema è data dall'Algoritmo 2.4.8.

Proposizione 2.3.8. Sia , dove è la radice di un polinomio monico irridu-

L = η

Q(η)

cibile di grado e sia

∈

P (X) n

Z[X]  

1 X i

a η

α = i

 

d 0≤i≤n−1

la rappresentazione standard di qualche come in Notazione 2.2.13

∈

α L

n−1

Sia .

X i

A = a X

i

i=0

Allora il polinomio caratteristico è dato dalla formula:

C α −n −

C (X) = d R (P (Y ), dX A(Y ))

α Y

ove è la risultante ottenuta rispetto alla variabile .

R Y

Y

In particolare abbiamo: −n

N = d R(P (X), A(X))

K/Q

Dimostrazione. Per denizione

Y Y

− −

C = (X σ (α)) = (X A(σ (η))/d)

i i

α i i

Y

−n −n

− −

= d (dX A(η )) = d R (P (Y ), dX A(Y ))

i Y

i

dove le sono i coniugati di , cioè le radici di

η η P

i

Proposizione 2.3.9. Sia e , allora se e 0

∈ ∈ 6 6 ∃λ ∈

P (X) x P (x) = 0 P (x) = 0

C[X] C

tale che:

+

R

P (x)

− |

P x λ <| P (x)

0

P (x)

CAPITOLO 2. TEORIA DI GALOIS: FONDAMENTI E DEFINIZIONI11

2.4 Algoritmi

Algoritmo 2.4.1 . Siano , campo con .

(Divisione Euclidea) ∈ 6

A, B L[X] L B = 0

1. Siano , .

R = A Q = 0

2. Se allora termina l'algoritmo.

deg(R) < deg(B)

3. Poni `(R) deg(R)−deg(B)

S = X

`(B)

dopo di che , e vai al passo 2.

− ·

Q = Q + S R = R S B

Nota 2.4.2. La moltiplicazione al passo 3 non è propriamente una moltiplicazione

·

S B

tra polinomi ma una moltiplicazione scalare seguita da uno shift dei coecienti

Algoritmo 2.4.3 . Sia un anello e siano

(Algoritmo di Pseudo - Divisione) M ∈

A, B

, con . Sia inoltre e . Assumiamo che

M[X] 6

B = 0 m = deg(A), n = deg(B) d = `(B)

.

≥

m n

1. Poni −

R = A, Q = 0, e = m n + 1

2. Se allora e termina l'algoritmo

e

deg(R) < deg(B) q = d , Q = qQ, R = qR

3. Sia deg(R)−deg(B)

S = `(R)X

allora e torna al passo

· · − · −

Q = d Q + S, R = d R S B, e = e 1 2

Algoritmo 2.4.4 . Sia polinomio monico e sia

(Fattorizzazione Squarefree) ∈

A F p

la sua fattorizzazione squarefree, dove sono squarefree e a due a due

Y ii

A = A A i

i≥1

coprimi.

L'algoritmo trova i polinomi e restituisce le coppie per i valori di per cui

A (i, A ) i A

i i i

è non costante.

1. Sia e .

e = 1 T = A

0

2. Se è costante, termina l'algoritmo. Altrimenti poni ,

0

T T = gcd(T , T ) V = T /T

0 0 0

0

e .

k = 0

CAPITOLO 2. TEORIA DI GALOIS: FONDAMENTI E DEFINIZIONI12

e poniamo

3. Se è costante, deve essere della forma X j

t X

V T T (X) = j

p|j

j , e vai al passo 2.

X t X

T = e = pe

p

j

0 p|j

4. Poni . Se allora poni e .

|

k = k + 1 p k T = T /V k = k + 1

5. Sia , , e . Se è non costante

W = gcd(T, V ) A = V /W V = W T = T /V A

ek ek

restituisci . Vai al passo 3.

(ek, A )

ek

Algoritmo 2.4.5 . Siano , .

(della Sotto-Risultante) ∈ J J

A, B [X] U F D

1. Se o restituisci 0 e termina l'algoritmo.

A = 0 B = 0

Altrimenti sia , , , , , ,

a = cont(A) b = cont(B) A = A/a B = B/b g = 1 h = 1

e . Inne se scambia e e se in più

deg(B) deg(A)

s = 1 t = a b deg(A) < deg(B) A B

e sono dispari allora poni −1

deg(A) deg(B) s =

2. Sia . Se e sono dispari allora . Inne

− −s

δ = deg(A) deg(B) deg(A) deg(B) s =

troviamo tale che utilizzando l'Algoritmo 2.4.3.

δ+1

R `(B) A = BQ + R

3. Sia e .

δ

A = B B = R/(gh )

4. Poni , . Se vai al passo 2, altrimenti poni

1−δ δ

g = `(A) h = h g deg(B) > 0

restituisci e termina l'algoritmo.

1−deg(A) deg(A) · ·

h = h `(B) s t h

Algoritmo 2.4.6 . Siano dati due

(del calcolo del GCD mediante Sotto - Risultante)

polinomi , .

∈ J J

A, B U F D

1. Se allora scambia e . Se ora restituisci e termina

deg(B) > deg(A) A B B = 0 A

l'algoritmo.

Altrimenti sia , , , , ,

a = cont(A) b = cont(B) d = gcd(a, b) A = A/a B = B/b

e =1

g = 1 h

2. Sia . Utilizzando l'Algoritmo 2.4.3 troviamo tale che

−

δ = deg(A) deg(B) R

.

δ+1

`(B) A = BQ + R

Se vai al passo . Se , poni e vai al passo 4.

R = 0 4 deg(R) = 0 B = 1

3. Sia , , , e vai al passo 2.

δ 1−δ δ

A = B B = R/(gh ) g = `(A) h = h g

CAPITOLO 2. TEORIA DI GALOIS: FONDAMENTI E DEFINIZIONI13

4. Restituisci e termina l'algoritmo.

·

d B/cont(B)

Algoritmo 2.4.7 . Sia polinomio monico.

(Fattorizzazione in ) ∈

A [X]

F F

p p

1. Troviamo in tali che

A , . . . , A [X]

F

1 p

k

k

(1) .

Y ii

A = A

i=1

(2) sono coprimi e squarefree.

A i

Questa scomposizione è data dall'Algoritmo 2.4.4.

2. Per troviamo i polinomi tali che sia il prodotto di

∈

i = 1, . . . , k A [X] A

F p

i,d i,d

tutti i fattori irriducibili di . Perciò: .

Y

A A = A

i i i,d

d

3. Per ogni e fattorizza in fattori irriducibili di grado .

i d A deg(A )/d d

i,d i,d

4. Raggruppa tutti i fattori identici trovati, ordinandoli mediante il grado, restituisci

la fattorizzazione completa e termina l'algoritmo.

Algoritmo 2.4.8 . Assumiamo le notazioni del Teorema 2.3.6

(Sollevamento di Hensel)

e denotiamo con l'anello

M Z/rZ

1. Sia . Usando l'Algoritmo 2.4.1 sull'anello , troviamo

−

f = (C AB)/q mod r M

tale che

∈ −

t M [X] deg(V f AT ) < deg(A)

2. Sia un sollevamento di su avente lo stesso grado e sia un

−

A V f At B

Z[X]

0 0

sollevamento di su avente lo stesso grado. Restituisci

U f +Bt A = A+qA

Z[X] 1 0

, e termina l'algoritmo.

B = B + qB

1 0

Algoritmo 2.4.9 . Assumiamo perciò .

(Sollevamento Quadratico di Hensel) |

p q r = p

Dopo l'Algoritmo 2.4.8, questo algoritmo trova e tale che , ,

≡ ≡

U V U V V V

1 1 1 p 1 1 p

, e

deg(U ) < deg(B ) deg(V ) < deg(A )

1 1 1 1 ≡

U A + V B 1

1 1 1 1 pr

1. Sia . Usando l'Algoritmo 2.4.1 sull'anello

− −

g = (1 U A V B )/p mod r M =

1 1

troviamo tale che che è possibile poiché

∈ −

t M [X] deg(V g A t) < deg(A )

Z/rZ 1 1

è invertibile su .

`(A ) = `(A) M

1

CAPITOLO 2. TEORIA DI GALOIS: FONDAMENTI E DEFINIZIONI14

2. Sia un sollevamento di su avente il medesimo grado e sia un

U U g + B t V

Z[X]

0 1 0

sollevamento di su avente lo stesso grado. Restituisci ,

V g−A t U = U +pU

Z[X]

1 1 0

e termina l'algoritmo.

V = V + pV

1 0

Algoritmo 2.4.10 . Sia un polinomio non nullo.

(Fattorizzazione in ) ∈

A

Z Z

1. Sia , , , dove è ottenuto me-

0 0

c = cont(A) A = A/c U = A/ gcd(A, A ) gcd(A, A )

diante l'Algoritmo 2.4.6. Possiamo inoltre utilizzare in questo passo la scom-

posizione squarefree dell'Algoritmo 2.4.4 per abbassare ulteriormente il grado di

.

U

2. Per ogni trova sul campo e fermati quando questo è uguale a

0

p gcd(U, U ) gcd

F p

1. Per questo utilizziamo l'Algoritmo 2.4.7, trovando la fattorizzazione completa

p

di .

U mod p

3. Usando il Teorema 2.3.5 troviamo un vincolo per i coecienti dei fattori di

B U

di grado minore o uguale a . Scegli anché sia il più piccolo esponente

deg(U )/2 e

tale che e

p > 2`(U )B

4. Usando la generalizzazione degli Algoritmi 2.4.8 e 2.4.9, solleva la fattorizzazione

ottenuta al passo 2 ad una fattorizzazione . Sia

e

mod p e

≡

U `(U )U . . . U mod p

1 r

la fattorizzazione di e assumiamo gli monici.

e

U mod p U

i

Sia d = 1

5. Per ogni combinazione di fattori , dove in più abbiamo che

V̄ = U . . . U i = 1

i i d

1 d

se , troviamo l'unico polinomio tale che tutti i coecienti di

1 ∈

d = r