Elementi di certi ordini
Ho un dubbio che non riesco a chiarire.
Come faccio a dire quanti elementi in un gruppo hanno esattamente quell'ordine?
ad esempio in $S_n$ quanti elementi hanno ordine $n$? quindi mi sto chiedendo quanti non hanno un ordine inferiore a $n$...
e per un generico $k|n$?
Forse la domanda è un po' troppo vaga...
Però forse il problema è risolvibile almeno in $S_p$ con p primo?
Non saprei da dove iniziare il ragionamento.. Se un elemento ha ordine $k$ in $S_n$ sicuramente non contiene cicli di lunghezza $l$ minore di $k$, infatti questi sicuramente hanno ordine $<=l$.
Un ciclo di lunghezza $k$ può avere ordine $
come li conto?
Come faccio a dire quanti elementi in un gruppo hanno esattamente quell'ordine?
ad esempio in $S_n$ quanti elementi hanno ordine $n$? quindi mi sto chiedendo quanti non hanno un ordine inferiore a $n$...
e per un generico $k|n$?
Forse la domanda è un po' troppo vaga...
Però forse il problema è risolvibile almeno in $S_p$ con p primo?
Non saprei da dove iniziare il ragionamento.. Se un elemento ha ordine $k$ in $S_n$ sicuramente non contiene cicli di lunghezza $l$ minore di $k$, infatti questi sicuramente hanno ordine $<=l$.
Un ciclo di lunghezza $k$ può avere ordine $
come li conto?
Risposte
Premetto che il problema combinatorio che poni è (secondo me) molto complesso.
Scritto un elemento [tex]g \in S_n[/tex] come prodotto di cicli disgiunti, il suo ordine è il mcm delle lunghezze dei cicli della decomposizione.
Riguardo il tuo esempio, non credo che esista un modo utilmente esplicito di calcolare il numero degli elementi di ordine [tex]n[/tex] in [tex]S_n[/tex]. Tieni conto che c'è ben altro oltre agli [tex]n[/tex]-cicli: per esempio in [tex]S_{10}[/tex] l'elemento [tex](12)(34567)[/tex] ha ordine 10. E per la cronaca [tex](123)(45678)[/tex] ha ordine [tex]15 > 10[/tex]. Spero si veda da questo esempio che il problema ha una certa complessità combinatoria.
L'esponente di un gruppo è per definizione il mcm degli ordini dei suoi elementi. Per esempio l'esponente di [tex]S_n[/tex] risulta essere [tex]\text{mcm}(1,2, ... ,n)[/tex]. Forse riesci a trovare qualcosa su internet riguardo a questo. Nel caso, ti suggerisco di cercarlo in inglese. C'è molta letteratura sugli esponenti, anche se dubito che ci sia molto sul gruppo simmetrico.
Prima di domandarsi quanti sono gli elementi di un dato ordine è utile sapere se ce ne sono (ed è ovviamente un problema molto più facile). In [tex]S_n[/tex] ci sono sicuramente elementi di ordini [tex]1, ... ,n[/tex] ma dopo [tex]n[/tex] cosa succede? Dipende dalla natura aritmetica dei numeri dopo [tex]n[/tex] (per esempio se [tex]n+1[/tex] è primo allora [tex]S_n[/tex] non ha elementi di ordine [tex]n+1[/tex]).
Ti segnalo questo articolo di Jon Grantham del 1995 (non so se lo visualizzi), in cui si trova una stima dall'alto per il massimo primo (!) che divide il massimo ordine (!) di un elemento di [tex]S_n[/tex] (l'antifona è: se già questo massimo ordine è difficile da capire, figuriamoci gli altri!).
Ti riporto un estratto di questo stesso articolo, che forse può chiarirti un po' le idee.
"crypto4":No, in [tex]S_n[/tex] esistono elementi di ordine anche più grande di [tex]n[/tex]. Vedi sotto.
ad esempio in $S_n$ quanti elementi hanno ordine $n$? quindi mi sto chiedendo quanti non hanno un ordine inferiore a $n$...
e per un generico $k|n$?$k | n!$ vorrai dire
Scritto un elemento [tex]g \in S_n[/tex] come prodotto di cicli disgiunti, il suo ordine è il mcm delle lunghezze dei cicli della decomposizione.
Riguardo il tuo esempio, non credo che esista un modo utilmente esplicito di calcolare il numero degli elementi di ordine [tex]n[/tex] in [tex]S_n[/tex]. Tieni conto che c'è ben altro oltre agli [tex]n[/tex]-cicli: per esempio in [tex]S_{10}[/tex] l'elemento [tex](12)(34567)[/tex] ha ordine 10. E per la cronaca [tex](123)(45678)[/tex] ha ordine [tex]15 > 10[/tex]. Spero si veda da questo esempio che il problema ha una certa complessità combinatoria.
L'esponente di un gruppo è per definizione il mcm degli ordini dei suoi elementi. Per esempio l'esponente di [tex]S_n[/tex] risulta essere [tex]\text{mcm}(1,2, ... ,n)[/tex]. Forse riesci a trovare qualcosa su internet riguardo a questo. Nel caso, ti suggerisco di cercarlo in inglese. C'è molta letteratura sugli esponenti, anche se dubito che ci sia molto sul gruppo simmetrico.
Prima di domandarsi quanti sono gli elementi di un dato ordine è utile sapere se ce ne sono (ed è ovviamente un problema molto più facile). In [tex]S_n[/tex] ci sono sicuramente elementi di ordini [tex]1, ... ,n[/tex] ma dopo [tex]n[/tex] cosa succede? Dipende dalla natura aritmetica dei numeri dopo [tex]n[/tex] (per esempio se [tex]n+1[/tex] è primo allora [tex]S_n[/tex] non ha elementi di ordine [tex]n+1[/tex]).
Ti segnalo questo articolo di Jon Grantham del 1995 (non so se lo visualizzi), in cui si trova una stima dall'alto per il massimo primo (!) che divide il massimo ordine (!) di un elemento di [tex]S_n[/tex] (l'antifona è: se già questo massimo ordine è difficile da capire, figuriamoci gli altri!).
Ti riporto un estratto di questo stesso articolo, che forse può chiarirti un po' le idee.
ovviamente volevo dire $n!$ l'ordine di $S_n$...
Aspetta.. proviamo a vedere il caso $S_p$ primo. (non capisco perchè hai considerato $S_{p+1}$..)
Quanti saranno gli elementi di $S_p$ di ordine p? questi sono sicuramente i $p$-cicli perchè non ci sono i casi del prodotto di cicli di lunghezza un divisore di p...
quindi sono?: $(p-1)!$ cioè $(123...p)$ e posso scambiare in $(p-1)!$ modi le cifre $(2...p)$.
o sono $(p-1)!+1$?
Aspetta.. proviamo a vedere il caso $S_p$ primo. (non capisco perchè hai considerato $S_{p+1}$..)
Quanti saranno gli elementi di $S_p$ di ordine p? questi sono sicuramente i $p$-cicli perchè non ci sono i casi del prodotto di cicli di lunghezza un divisore di p...
quindi sono?: $(p-1)!$ cioè $(123...p)$ e posso scambiare in $(p-1)!$ modi le cifre $(2...p)$.
o sono $(p-1)!+1$?
Giusto, se [tex]p[/tex] è un numero primo gli elementi di ordine [tex]p[/tex] in [tex]S_p[/tex] sono tutti e soli i [tex]p[/tex]-cicli, e il loro numero è [tex](p-1)![/tex].
perfetto.
Ora voglio generalizzare a $S_{pq}$ e prendiamo come esempio $S_6$.
Voglio trovare gli elementi di ordine k. Fino a k=6 è banale.. e direi fino a k=12 è banale. Ma da lì in poi quanti sono? diciamo per k=30.
Innanzitutto ce ne sono di ordine 30?
Come posso contarli?
Ora voglio generalizzare a $S_{pq}$ e prendiamo come esempio $S_6$.
Voglio trovare gli elementi di ordine k. Fino a k=6 è banale.. e direi fino a k=12 è banale. Ma da lì in poi quanti sono? diciamo per k=30.
Innanzitutto ce ne sono di ordine 30?
Come posso contarli?
A mano, usando la decomposizione in cicli disgiunti.
Prendi [tex]g \in S_6[/tex] e considera la sua decomposizione in cicli disgiunti. Se c'è un 2-ciclo allora quello che resta ha ordine 1, 2, 3 oppure 4, quindi [tex]|g| \leq 6[/tex]. Se c'è un 3-ciclo e non ci sono 2-cicli allora quello che resta ha ordine 1, 2 oppure 3 e quindi [tex]|g| \leq 6[/tex]. Se c'è un 4-ciclo allora [tex]|g|=4[/tex], se c'è un 5-ciclo allora [tex]|g|=5[/tex], e c'è un 6-ciclo allora [tex]|g|=6[/tex]. Quindi gli elementi di [tex]S_6[/tex] hanno ordini 1, 2, 3, 4, 5, 6.
Ma fare un esercizio del genere ha senso solo per gradi bassi, già con un generico [tex]S_{pq}[/tex] la cosa diventa impraticabile.
Prendi [tex]g \in S_6[/tex] e considera la sua decomposizione in cicli disgiunti. Se c'è un 2-ciclo allora quello che resta ha ordine 1, 2, 3 oppure 4, quindi [tex]|g| \leq 6[/tex]. Se c'è un 3-ciclo e non ci sono 2-cicli allora quello che resta ha ordine 1, 2 oppure 3 e quindi [tex]|g| \leq 6[/tex]. Se c'è un 4-ciclo allora [tex]|g|=4[/tex], se c'è un 5-ciclo allora [tex]|g|=5[/tex], e c'è un 6-ciclo allora [tex]|g|=6[/tex]. Quindi gli elementi di [tex]S_6[/tex] hanno ordini 1, 2, 3, 4, 5, 6.
Ma fare un esercizio del genere ha senso solo per gradi bassi, già con un generico [tex]S_{pq}[/tex] la cosa diventa impraticabile.
sembra così strano che in un gruppo con $6!$ elementi l esponente sia solo 6..
Infatti non lo è. [tex]6[/tex] è il massimo ordine di un elemento di [tex]S_6[/tex]. L'esponente di [tex]S_6[/tex] è il mcm (minimo comune multiplo) degli ordini, cioè [tex]\text{mcm}(1,2,3,4,5,6)=60[/tex].
Vorrei provare a impostare il problema di deterinare gli elementi di ordine $n$ in $S_n$ nel caso in cui $n=pq$ prodotto di primi distinti. Studiamo la struttura ciclica di una permutazione di ordine $pq$. Se è vero quello che ho trovato in questo pdf http://www.dm.unipi.it/~gaiffi/Algebra1/Pages/dispense2.pdf a pag 3, il numero di k-cicli distinti in $S_n$ è ${n!}/{(n-k)!k}$. In base a questa formula ci sono $(pq-1)!$, pq-cicli in $S_{pq}$. Se una permutazione di ordine $pq$ non è un pq-ciclo allora deve essere prodotto di un certo numero di p-cicli distinti e di un certo numero di q-cicli distinti. Sia $x$ il numero di p-cicli e $y$ il numero di q-cicli della permutazione in oggetto. Allora possiamo impostare il sistema di disuguaglianze
${(px+qy<=pq),(0
Mi sembra evidente per le limitazioni poste e il fatto che $x$ e $y$ devono essere interi, che questo sistema ha un numero finito di soluzioni. Sia $S$ l'insieme delle soluzioni. Allora ogni coppia $(x,y) \in S$ rappresenta la struttura ciclica di una possibile permutazione di ordine $pq$ con $x$ p-cicli e $y$ q-cicli. Ora ci domandiamo quante sono le permutazioni con struttura $(x,y)$ in $S_{pq}$ ?? Per capirlo proviamo a costruirne una. Prima di tutto dobbiamo metterci un p-ciclo. Possiamo scegliere fra ${pq!}/{(pq-p)!p}$ p-cicli distinti. Scelto il primo ci rimangono $pq-p$ elementi di ${1,...,pq}$. Supponiamo di voler costruire un secondo p-ciclo, allora sempre utilizzando la solita formula abbiamo ${(pq-p)!}/{(pq-2p)!p}$ possibilità di sceglierlo e cosi via $x$ volte. Quindi alla fine le possibilità di scegliere i nostri p-cicli sono $\prod_{k=1}^x {(pq-(k-1)p)!}/{(pq-kp)!p}$. Siccome ogni termine si semplifica col successivo (e portando fuori $1/p$) questa produttoria diventa ${pq!}/{(pq-px)!p^x}$. Una volta scelti gli $x$ p-cicli ci rimangono $pq-px$ oggetti con cui costruire gli $y$ q-cicli. Con ragionamento analogo a quello precedente otteniamo che le possibilità di scelta sono $\prod_{h=1}^y {(pq-px-(h-1)q)!}/{(pq-px-hq)!q}$ che semplificata viene ${(pq-px)!}/{(pq-px-qy)!q^y}$. Adesso moltiplichiamo le possibiltà di costruire i p-cicli per quelle di costruire i q-cicli ${pq!}/{(pq-px)!p^x} * {(pq-px)!}/{(pq-px-qy)!q^y}$ $= {pq!}/ {(pq-px-qy)!p^xq^y}$ Adesso ricordando che dobbiamo fare questo per ogni coppia $(x,y)$ e aggiungendo il numero di pq-cicli otteniamo
$(pq-1)!+\sum_{(x,y) \in S} {pq!}/ {(pq-px-qy)!p^xq^y}$
Essendo $S$ l'isieme delle soluzioni del sistema suddetto.
Ammesso che sia giusto non è comunque una soluzione esplicita ma riconduce il problema alla ricerca delle soluzioni intere di un sistema di disuguaglianze, cosa che può fare un computer.
${(px+qy<=pq),(0
Mi sembra evidente per le limitazioni poste e il fatto che $x$ e $y$ devono essere interi, che questo sistema ha un numero finito di soluzioni. Sia $S$ l'insieme delle soluzioni. Allora ogni coppia $(x,y) \in S$ rappresenta la struttura ciclica di una possibile permutazione di ordine $pq$ con $x$ p-cicli e $y$ q-cicli. Ora ci domandiamo quante sono le permutazioni con struttura $(x,y)$ in $S_{pq}$ ?? Per capirlo proviamo a costruirne una. Prima di tutto dobbiamo metterci un p-ciclo. Possiamo scegliere fra ${pq!}/{(pq-p)!p}$ p-cicli distinti. Scelto il primo ci rimangono $pq-p$ elementi di ${1,...,pq}$. Supponiamo di voler costruire un secondo p-ciclo, allora sempre utilizzando la solita formula abbiamo ${(pq-p)!}/{(pq-2p)!p}$ possibilità di sceglierlo e cosi via $x$ volte. Quindi alla fine le possibilità di scegliere i nostri p-cicli sono $\prod_{k=1}^x {(pq-(k-1)p)!}/{(pq-kp)!p}$. Siccome ogni termine si semplifica col successivo (e portando fuori $1/p$) questa produttoria diventa ${pq!}/{(pq-px)!p^x}$. Una volta scelti gli $x$ p-cicli ci rimangono $pq-px$ oggetti con cui costruire gli $y$ q-cicli. Con ragionamento analogo a quello precedente otteniamo che le possibilità di scelta sono $\prod_{h=1}^y {(pq-px-(h-1)q)!}/{(pq-px-hq)!q}$ che semplificata viene ${(pq-px)!}/{(pq-px-qy)!q^y}$. Adesso moltiplichiamo le possibiltà di costruire i p-cicli per quelle di costruire i q-cicli ${pq!}/{(pq-px)!p^x} * {(pq-px)!}/{(pq-px-qy)!q^y}$ $= {pq!}/ {(pq-px-qy)!p^xq^y}$ Adesso ricordando che dobbiamo fare questo per ogni coppia $(x,y)$ e aggiungendo il numero di pq-cicli otteniamo
$(pq-1)!+\sum_{(x,y) \in S} {pq!}/ {(pq-px-qy)!p^xq^y}$
Essendo $S$ l'isieme delle soluzioni del sistema suddetto.
Ammesso che sia giusto non è comunque una soluzione esplicita ma riconduce il problema alla ricerca delle soluzioni intere di un sistema di disuguaglianze, cosa che può fare un computer.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo