Numero dei polinomi irriducibili a coefficienti in un campo finito Maurizio Cornalba

Numero dei polinomi irriducibili a coefficienti in un campo finito Maurizio Cornalba

3/5/2014

Sia q = p ^h , dove p ` e un numero primo e h ` e un intero positivo. Indichiamo con µ la funzione di M¨ obius:

µ(m) =







1 se m = 1

(−1) ^k se m ` e prodotto di k primi distinti 0 altrimenti

Vogliamo dimostrare il seguente risultato, dovuto a Gauss.

Teorema 1. Il numero dei polinomi monici irriducibili di grado n a coefficienti in F q ` e 1

n X

d   n

µ  n d

 q ^d

Sia P un polinomio monico irriducibile di grado n e sia α una sua radice. Allora F q [α] ha grado n su F q e quindi ` e isomorfo a F q

ⁿ

. Poich´ e F q

ⁿ

` e una estensione galoisiana di F q ne segue che P ha n radici distinte in F q

ⁿ

. Osserviamo anche che se due polinomi monici irriducibili hanno una radice comune essi coincidono, per l’unicit` a del polinomio minimo. Dunque il numero che dobbiamo calcolare ` e

1 n R _n

dove R _n ` e il numero degli elementi di F q

ⁿ

che hanno grado n su F q . In altre parole R _n = #

 F q

ⁿ

r

[

K sottocampo proprio di Fqn

K



Scriviamo n = Q `

i=1 p ^e _i

ⁱ

, dove p ₁ , . . . , p _` sono primi distinti. Notiamo che i sottocampi di F q

ⁿ

contenenti F q sono quelli della forma F q

^(n/d)

, dove d ` e un divisore di n, e che tra questi i sottocampi propri massimali sono i campi F _i = F _q

(n/pi)

. Dunque

R _n = #  F q

ⁿ

r

`

[

i=1

F i



(1)

Per calcolare la cardinalit` a dell’unione degli F i useremo un risultato combinatorio classico. Siano X 1 , . . . , X <sub>`</sub> insiemi finiti. Se i 1 , . . . , i s ∈ {1, . . . , `} poniamo X _i

₁

_{... i}

_s

= X i

1

∩ X _i

₂

∩ · · · ∩ X _i

_s

. Il risultato di cui faremo uso ` e il seguente

Lemma 1.

#

 [ ^`

i=1

X i



=

`

X

s=1

(−1) ^s−1 X

i

1

<i

2

<···<i

s

#(X i

1

... i

s

)

Dimostrazione. Ragioniamo per induzione su `. Se ` = 2 l’enunciato si riduce a #(X 1 ∪ X ₂ ) =

#(X ₁ ) + #(X ₂ ) − #(X ₁ ∩ X ₂ ). Se supponiamo il risultato dimostrato per unioni di meno di ` insiemi possiamo scrivere

#  [ ^`

i=1

X _i 

= #  ^`−1 [

i=1

X _i 

+ #(X <sub>`</sub> ) − #  <sup>`−1</sup> [

i=1

X _i 

∩ X _` 

=

`−1

X

s=1

(−1) ^s−1 X

i

1

<···<i

s

<`

#(X i

1

... i

s

) + #(X ` ) − #

 ^`−1 [

i=1

X i ∩ X _` 

=

`−1

X

s=1

(−1) ^s−1 X

i

1

<···<i

s

<`

#(X _i

₁

_{... i}

_s

) + #(X _` )

−

`−1

X

s=1

(−1) ^s−1 X

i

1

<···<i

s

<`

#(X _i

₁

_{... i}

_s

_` )

=

`

X

s=1

(−1) ^s−1 X

i

1

<i

2

<···<i

s

#(X i

1

... i

s

)

Applichiamo il lemma appena dimostrato alla (1) osservando che, quando i ₁ , . . . , i _s sono distinti, F _i

₁

_{... i}

_s

= F _i

₁

∩ F _i

₂

∩ · · · ∩ F _i

_s

= F

q

pi1···pisn

Si ottiene

R _n = q ⁿ +

`

X

s=1

(−1) ^s X

i

1

<···<i

s

#

 F q

n pi1···pis



= q ⁿ +

`

X

s=1

(−1) ^s X

i

1

<···<i

s

q

n pi1···pis

= q ⁿ +

`

X

s=1

X

i

1

<···<i

s

µ(p i

1

· · · p _i

_s

)q

n pi1···pis

Ponendo _p ⁿ

i1

···p

_is

= d e ricordando che µ(m) = 0 quando nella fattorizzazione di m vi sono primi ripetuti, ci` o equivale a

R _n = q ⁿ + X

d   n,d6=n

µ  n d



q ^d = X

d   n

µ  n d

 q ^d

che ` e quanto andava dimostrato.