Formula n° polinomi irriducibili di $ZZ_P$ (moebius)
Salve ragazzi , torno a postare per una domanda a stampo teorico, che mi incuriosisce.
A suo tempo, il mio professore di algebra 1 , ci propinò una formula che permette di calcolare il numero di polinomi monici irriducibili in $ZZ_p$ di grado $n$. (senza dimostrarla...)
Ve la presento :
Definisco $N_n(p) :=$ numero di polinomi monici di grado $n$ in $ZZ_p$
allora
$N_n(p)=1/n\sum_(s)\mu(s)p^(n/s)$
Ove la somma varia ai divisori $s$ di $n$ (incluso 1) e $\mu(s)$ è la formula combinatoria di Moebius
che assume valore $1$ se $s=1$ , $(-1)^k$ se $s$ è prodotto di k primi distinti , $0$ altrimenti.
domanda : che logica c'è dietro a questa formula? cosa mi assicura che veramente quella formula mi restituisce tutti i polinomi irriducibili di un dato grado?
Grazie mille
A suo tempo, il mio professore di algebra 1 , ci propinò una formula che permette di calcolare il numero di polinomi monici irriducibili in $ZZ_p$ di grado $n$. (senza dimostrarla...)
Ve la presento :
Definisco $N_n(p) :=$ numero di polinomi monici di grado $n$ in $ZZ_p$
allora
$N_n(p)=1/n\sum_(s)\mu(s)p^(n/s)$
Ove la somma varia ai divisori $s$ di $n$ (incluso 1) e $\mu(s)$ è la formula combinatoria di Moebius
che assume valore $1$ se $s=1$ , $(-1)^k$ se $s$ è prodotto di k primi distinti , $0$ altrimenti.
domanda : che logica c'è dietro a questa formula? cosa mi assicura che veramente quella formula mi restituisce tutti i polinomi irriducibili di un dato grado?
Grazie mille
Risposte
Non ti so rispondere esaustivamente, perchè non conosco bene la funzione di Moebius (l'ho pure studiata nel corso di istitutzioni di algebra superiore, ma non l'ho digerita bene).
Ti posso però dire, come saprai già, da dove prende le mosse la formula a cui fai riferimento. Si parte dal noto fatto che il polinomio \(\displaystyle x^{p^n}-x\) è il prodotto di tutti i polinomi monici irriducibili di grado \(\displaystyle s \) che divide \(\displaystyle n \); da cui, prendendo i gradi dei polinomi: \(\displaystyle p^n= \sum_{s|n}sN_s(p) \)
Ora dovrebbe intervenire in qualche modo la funzione di Moebius, ma non ricordo proprio
Ti posso però dire, come saprai già, da dove prende le mosse la formula a cui fai riferimento. Si parte dal noto fatto che il polinomio \(\displaystyle x^{p^n}-x\) è il prodotto di tutti i polinomi monici irriducibili di grado \(\displaystyle s \) che divide \(\displaystyle n \); da cui, prendendo i gradi dei polinomi: \(\displaystyle p^n= \sum_{s|n}sN_s(p) \)
Ora dovrebbe intervenire in qualche modo la funzione di Moebius, ma non ricordo proprio
Allora, con l'aiuto del sole ehm.. volevo dire di internet 
ho visto che si tratta della formula d'inversione di Moebius http://it.wikipedia.org/wiki/Formula_di_inversione_di_M%C3%B6bius
Prendi \(\displaystyle f(n)=p^n \) e \(\displaystyle g(s)=sN_{s}(p) \) e il gioco è fatto (si fa per dire perchè la formula andrebbe dimostrata):
\(\displaystyle N_{n}(p)= (1/n)g(n)= 1/n\sum_{s|n}\mu(s)p^{n/s}\)
Arrivi a questa conclusione partendo dalla considerazione che ho scritto sopra: \(\displaystyle p^n= \sum_{s|n}sN_s(p) \) visto che nella fornula di inversione si parte proprio da \(\displaystyle f(n)= \sum_{s|n}g(s) \) che implica \(\displaystyle g(n)=\sum_{s|n}\mu(s)f(n/s) \)
ho visto che si tratta della formula d'inversione di Moebius http://it.wikipedia.org/wiki/Formula_di_inversione_di_M%C3%B6biusPrendi \(\displaystyle f(n)=p^n \) e \(\displaystyle g(s)=sN_{s}(p) \) e il gioco è fatto (si fa per dire perchè la formula andrebbe dimostrata):
\(\displaystyle N_{n}(p)= (1/n)g(n)= 1/n\sum_{s|n}\mu(s)p^{n/s}\)
Arrivi a questa conclusione partendo dalla considerazione che ho scritto sopra: \(\displaystyle p^n= \sum_{s|n}sN_s(p) \) visto che nella fornula di inversione si parte proprio da \(\displaystyle f(n)= \sum_{s|n}g(s) \) che implica \(\displaystyle g(n)=\sum_{s|n}\mu(s)f(n/s) \)
"Kashaman":
Salve ragazzi , torno a postare per una domanda a stampo teorico, che mi incuriosisce.
A suo tempo, il mio professore di algebra 1 , ci propinò una formula che permette di calcolare il numero di polinomi monici irriducibili in $ZZ_p$ di grado $n$. (senza dimostrarla...)
Ve la presento :
Definisco $N_n(p) :=$ numero di polinomi monici di grado $n$ in $ZZ_p$
allora
$N_n(p)=1/n\sum_(s)\mu(s)p^(n/s)$
Ove la somma varia ai divisori $s$ di $n$ (incluso 1) e $\mu(s)$ è la formula combinatoria di Moebius
che assume valore $1$ se $s=1$ , $(-1)^k$ se $s$ è prodotto di k primi distinti , $0$ altrimenti.
domanda : che logica c'è dietro a questa formula? cosa mi assicura che veramente quella formula mi restituisce tutti i polinomi irriducibili di un dato grado?
Grazie mille
ciao francesco, ti ringrazio infinitamente per il tuo tempo dedicatomi ^^.
Ammetto che su wikipedia già guardai, ma capii poco. Forse per capirla a pieno, ho bisogno di strumenti superiori che non ho.
Diciamo che era per me più una curiosità , se il professore ce l'ha fatta vedere, allora , dato che siamo studenti del primo anno, era più per "cultura " personale che per vero studio. Probabilmente l'affronteremo nuovamente più in la nel tempo.
Tuttavia, sono ancora incuriosito.
Cosa rappresentano $f(n)$ e $g(s)$? quali sono la loro utilità?
Ammetto che su wikipedia già guardai, ma capii poco. Forse per capirla a pieno, ho bisogno di strumenti superiori che non ho.
Diciamo che era per me più una curiosità , se il professore ce l'ha fatta vedere, allora , dato che siamo studenti del primo anno, era più per "cultura " personale che per vero studio. Probabilmente l'affronteremo nuovamente più in la nel tempo.
Tuttavia, sono ancora incuriosito.
Cosa rappresentano $f(n)$ e $g(s)$? quali sono la loro utilità?
"Kashaman":
ciao francesco, ti ringrazio infinitamente per il tuo tempo dedicatomi ^^.
Ammetto che su wikipedia già guardai, ma capii poco. Forse per capirla a pieno, ho bisogno di strumenti superiori che non ho.
Diciamo che era per me più una curiosità , se il professore ce l'ha fatta vedere, allora , dato che siamo studenti del primo anno, era più per "cultura " personale che per vero studio. Probabilmente l'affronteremo nuovamente più in la nel tempo.
Tuttavia, sono ancora incuriosito.
Cosa rappresentano $f(n)$ e $g(s)$? quali sono la loro utilità?
Sono due funzioni definite sull'insieme dei numeri naturali (anche se si può fare un discorso più generale con funzioni definite su qualsiasi insieme parzialmente ordinato), legate tra loro proprio dal fatto che \(\displaystyle f(n)=\sum_{s|n}g(s) \), come lo sono le due che portano poi alla formula che hai scritto. Quello che manca però nella pagina di wikipedia è la cosa più importante, ossia la dimostrazione della formula d'inversione di Moebius!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo