Gruppi di permutazione: basi e punti mossi

[Studente Anonimo]

Sia [tex]G[/tex] un gruppo finito che agisca transitivamente e fedelmente su un insieme [tex]\Omega[/tex] anch'esso finito, con [tex]|\Omega| \geq 2[/tex].

Chiamiamo "base" di tale azione un sottoinsieme [tex]\Gamma[/tex] di [tex]\Omega[/tex] tale che se un elemento [tex]g \in G[/tex] fissa ogni elemento di [tex]\Gamma[/tex] allora e' l'identita', e di cardinalita' minima con questa proprieta'. Denotiamo tale cardinalita' minima con [tex]b(G)[/tex].

Dato [tex]g \in G[/tex] indichiamo con [tex]\text{supp}(g)[/tex] l'insieme degli elementi di [tex]\Omega[/tex] non fissati da [tex]g[/tex]. Definiamo [tex]\mu(G)[/tex] come il minimo dei [tex]|\text{supp}(g)|[/tex] quando [tex]g[/tex] varia in [tex]G-\{1\}[/tex].

1. Calcolare per esempio [tex]b(G)[/tex] e [tex]\mu(G)[/tex] quando [tex]G = C_n,\ S_n,\ A_n[/tex] nell'azione naturale su [tex]\{1,...,n\}[/tex] e di [tex]\text{GL}(m,q)[/tex] nell'azione naturale su [tex]{\mathbb{F}_q}^m-\{0\}[/tex].

2. Date le notazioni di cui sopra dimostrare che [tex]\mu(G) \cdot b(G) \geq |\Omega|[/tex].

Fonte: esercizi di Martin Liebeck alla scuola estiva di teoria dei gruppi a Venezia. Conosco una soluzione.

Note: il primo punto e' standard, per fare il secondo bisogna avere qualche buona idea, ma non sono richieste nozioni particolari oltre a quelle esposte (e' richiesta solo un po' di confidenza con le azioni dei gruppi).

[j18eos]

Ma per azione naturale cosa intendi?

[Studente Anonimo]

"j18eos":Ma per azione naturale cosa intendi?

Ogni sottogruppo [tex]H[/tex] di [tex]S_n[/tex] agisce sull'insieme [tex]\{1,...,n\}[/tex] nel seguente modo ovvio ("naturale"):

[tex]H \times \{1,...,n\} \to \{1,...,n\}[/tex],
[tex](\sigma,i) \mapsto \sigma(i)[/tex].

Scrivendo [tex]C_n[/tex] intendo per esempio il sottogruppo di [tex]S_n[/tex] generato dal [tex]n[/tex]-ciclo [tex](1...n)[/tex].

[j18eos]

Mi sembrava troppo banale ecco perché l'ho chiesto!

[j18eos]

Inizio a rispondere al caso in cui [tex]$G=C_n$[/tex]!

Sia [tex]$C_n=\langle c\rangle=\{c^k\in C_n\mid k\in I_0^{n-1}\}$[/tex](1)(2), volendo considerare l'azione naturale [tex]$\alpha$[/tex] di [tex]$C_n$[/tex] su [tex]$\Omega=I_1^n$[/tex], a meno d'equivalenze, essa è: [tex]$\alpha:\forall c^k\in C_n\rightarrow\dot\exists (1\hdots n)^k\in S_{\Omega}=S_n$[/tex].

Risulta che [tex]$\forall k\in I_1^{n-1},\,\mathrm{supp}(\alpha(c^k))=\Omega$[/tex], quindi [tex]$\mu(C_n)=n,\,b(C_n)=1$[/tex] (3); in quanto ogni [tex]$\alpha(c^k)\neq\iota_{\Omega}$[/tex] non fissa nessun elemento.

§§§

(1) L'elemento [tex]$c$[/tex] è un generatore di [tex]$C_n$[/tex]!

(2) In questo post e nei successivi pongo [tex]$\forall a
(3) Per l'escluso caso che sia [tex]$\Omega=\{1\}$[/tex] è [tex]$S_1=\{\iota_{\{1\}}\}$[/tex], quindi: [tex]$S_1-\{\iota_{\{1\}}\}=\emptyset$[/tex] e [tex]$\mu(C_1)$[/tex] non è definito.

[j18eos]

Continuo a rispondere al caso in cui [tex]$G=S_n$[/tex], indicata con [tex]$\beta$[/tex] l'azione naturale di [tex]$S_n$[/tex] su [tex]$\Omega=I_1^n$[/tex], si ha che essa è un suo automorfismo di [tex]$S_n$[/tex] (1) ed, a meno d'equivalenze, è [tex]$\beta:\forall\sigma\in S_n\rightarrow\dot\exists\sigma\in S_n$[/tex].

A differenza di prima, [tex]$\mu(S_n)=2$[/tex] per la presenza dei 2-cicli o trasposizioni (2), [tex]$b(S_n)=n-1$[/tex] in quanto una permutazione potendo spostare un solo elemento lo fissa per il suo essere una funzione biettiva.

§§§

(1) Dovendo essere [tex]$\beta\in\mathrm{Hom}(S_n;S_n)$[/tex] ed una immersione del sostegno di [tex]$S_n$[/tex] in se. Aggiungo che [tex]$\forall n\in\mathbb{N}-\{6\},\,\mathrm{Aut}S_n\cong S_n;\,\mathrm{Aut}S_6\cong C_2\ltimes S_6$[/tex].

(2) Come li si voglia chiamare!

[j18eos]

Dovresti modificare dicendo che [tex]$\mu(G)=\exists\iff G\neq\{1\}$[/tex] oppure conviene porre per definizione [tex]$\mu(\{1\})=0$[/tex]? Oppure ho solo sclerato?

Nella (remota) ipotesi che non stia sclerando dovrebbe essere [tex]$\mu(G)\cdot b(G)\geq|\Omega|:G\neq\{1\}$[/tex]!

[Studente Anonimo]

Hai ragione, ho modificato. Grazie

[j18eos]

Prego!

[j18eos]

Sia [tex]$G=\mathbb{A}_n$[/tex], si indichi con [tex]$\gamma$[/tex] l'azione naturale di [tex]$\mathbb{A}_n$[/tex] su [tex]$\Omega=I_1^n$[/tex], a meno d'equivalenze, essa è: [tex]$\gamma:\forall\sigma\in\mathbb{A}_n\rightarrow\dot\exists\sigma\in S_n$[/tex].

In questo caso [tex]$\mu(\mathbb{A}_n)=3$[/tex] a causa dei 3-cicli, mentre [tex]$b(\mathbb{A}_n)=n-2$[/tex]; le spiegazioni in spoiler visto che si deve un pò ragionare!

Volendo che [tex]$\gamma$[/tex] sia transitiva deve essere [tex]$n\geq3$[/tex], poiché [tex]$\mathbb{A}_1=\mathbb{A}_2=\{1\}$[/tex] agisce transitivamente solo sugli insiemi singleton e nelle ipotesi su [tex]$\Omega$[/tex] è esplicitamente [tex]$|\Omega|\geq2$[/tex]; ciò giustifica appieno l'asserzione su [tex]$\mu(\mathbb{A}_n)$[/tex].

Poiché le permutazioni pari e non identiche spostano almeno [tex]$3$[/tex] elementi distinti si ha che una base ha almeno [tex]$n-2$[/tex] elementi; infatti, potendo muovere solo 2 elementi si hanno come permutazioni non identiche solo le trasposizioni, le quali non sono permutazioni pari, quindi l'asserto.

In particolare si ritrova che [tex]$\mathbb{A}_3\simeq C_3,\,b(\mathbb{A}_3)=1=b(C_3)$[/tex].

OUT OF SELF: Il mio sesto senso ha ragione; ora si inizia a ballare!

[Studente Anonimo]

"j18eos":[tex]$b(\mathbb{A}_n)=\begin{cases}n\iff n\equiv1(\mathrm{Mod}2)\\ n-1\iff n\equiv0(\mathrm{Mod}2)\end{cases}$[/tex].

Non sarei cosi' d'accordo

(*) OUT OF SELF @Martino: Credo che nelle ipotesi bisogna ipotizzare [tex]$G\neq\{1\}$[/tex]!

Se guardi ho specificato [tex]|\Omega|\geq 2[/tex]. Dal momento che [tex]G[/tex] agisce su [tex]\Omega[/tex] transitivamente si deve avere [tex]|G| \geq |\Omega| \geq 2[/tex].
Avrei potuto anche scrivere [tex]G \neq \{1\}[/tex] ma preferisco far discendere proprieta' su G da [tex]\Omega[/tex], mi sembra piu' pulito. Non chiedermi perche'

[j18eos]

"Martino":...Avrei potuto anche scrivere [tex]G \neq \{1\}[/tex] ma preferisco far discendere proprieta' su G da [tex]\Omega[/tex], mi sembra piu' pulito. Non chiedermi perche'

Spiritoso!

[j18eos]

OUT OF SELF Ma tu guarda un pò a che ora trovo il tempo per dedicarmi all'ultima parte del primo punto. -_-

Supposto che [tex]$\mathbb{F}_q^m$[/tex] indichi lo spazio vettoriale numerico sul campo [tex]$\mathbb{F}_q$[/tex] (finito di ordine [tex]$q$[/tex]) [tex]$m$[/tex]-dimensionale e non l'insieme degli elementi del medesimo che sono radici [tex]$m$[/tex]-sime di elementi dello stesso; ecco la soluzione in spoiler.

Come azione naturale mi è venuta in mente l'azione [tex]$\phi:\forall M\in\mathrm{GL}(m;q)\rightarrow\dot\exists(\forall v\in\mathbb{F}_q^m-\{0\}\rightarrow\dot\exists M\times v\in\mathbb{F}_q^m-\{0\})\in\mathrm{Sym}(\mathbb{F}_q^m-\{0\})$[/tex]; spero di essere chiaro nella notazione.
Poiché ogni matrice [tex]$M$[/tex] in [tex]$\mathrm{GL}(m;q)$[/tex] determina un [tex]$\mathbb{F}_q$[/tex]-automorfismo di [tex]$\mathbb{F}_q^m$[/tex] che ad ogni vettore [tex]$v$[/tex] associa il vettore [tex]$M\times v$[/tex], sicché [tex]$b(\mathrm{GL}(m;q))=m$[/tex] in quanto al fissare una base di [tex]$\mathbb{F}_q^m$[/tex] si fissano tutti i suoi vettori e quindi si ha l'identità.
Sia [tex]$E=\{e_k\in\mathbb{F}_q^m\}_{k\in I_1^m}$[/tex] una base di [tex]$\mathbb{F}_q^m$[/tex], da quanto scritto una permutazione non identica [tex]$\phi(M)$[/tex] non fissa tutti gli elementi di [tex]$E$[/tex], quindi deve essere, senza ledere generalità, [tex]$e_1^{\phi(M)}=ae_1$[/tex] ove [tex]$a\in\mathbb{F}_q^\#$[/tex](*) e ciò impone che sia [tex]$q\neq2$[/tex]. In tali ipotesi se fosse [tex]$m=1$[/tex] allora ogni [tex]$\phi(M)$[/tex] fissa solo lo [tex]$0$[/tex] di [tex]$\mathbb{F}_q$[/tex] e quindi [tex]$\mu(\mathrm{GL}(1;q))=q-1,\,q\neq2$[/tex]. Sia [tex]$m\geq2$[/tex] allora [tex]$\forall k\in I_2^m,\,e_k^{\phi(M)}=e_k$[/tex], quindi [tex]$\phi(M)$[/tex] fissa il sottospazio [tex]$\mathbb{E}=\langle e_k\in\mathbb{F}_q^m\mid k\in I_2^m\rangle$[/tex], il quale ha [tex]$q^{m-1}-1$[/tex] vettori non nulli; da ciò si ha che [tex]$\mu(\mathrm{GL}(m;q))=|\mathbb{F}_q^m-\{0\}|-|\mathbb{E}-\{0\}|=q^m-1-(q^{m-1}-1)=q^m-1-q^{m-1}+1=q^m-q^{m-1},\,q\neq2$[/tex].
Tale ragionamento resta valido se [tex]$q=2;\,m\geq2,\,e_1^{\phi(M)}=e_1+\sum_{k=2}^me_k$[/tex]

§§§

(*) Pongo [tex]$\mathbb{F}_q^\#=\mathbb{F}_q-\{0\}$[/tex].

Dato che sono le 2 a.m. non sono nemmeno di chiamarmi Armando (leggi sotto), figuriamoci del ragionamento ora sbattuto on line.

EDIT: Ho appurato alcune precisazioni e correzioni; i dubbi espressi li eliminerò allo scadere delle [tex]$24$[/tex] ore dalla pubblicazione, a meno di correzioni prevenute.

EDIT2: Modificato alle [tex]$1:05$[/tex] secondo l'orologio del forum e secondo la parola data.

EDIT3: Trovato l'errore. L'avevo predetto!

EDIT4: Soluzione parziale... per adesso!

EDIT5: Manca un solo caso!

[Studente Anonimo]

"j18eos":Risulta che: [tex]$\mu(\mathrm{GL}(m;q))=q-1$[/tex], in quanto ogni matrice [tex]$M$[/tex] in [tex]$\mathrm{GL}(m;q)$[/tex] determina un [tex]$\mathbb{F}_q$[/tex]-automorfismo di [tex]$\mathbb{F}_q^m$[/tex] che ad ogni vettore [tex]$v$[/tex] associa il vettore [tex]$M\times v$[/tex], per cui; eccezione per la matrice identità, si determina almeno una permutazione che fissa un sottospazio [tex]$1$[/tex]-dimensionale [tex]$\mathbb{E}$[/tex] di [tex]$\mathbb{F}_q^m$[/tex] e fissa i vettori di [tex]$\mathbb{F}_q^m-\mathbb{E}$[/tex], e poiché [tex]$\mathbb{E}$[/tex] è composto da [tex]$q$[/tex] vettori; poiché si è estromesso il vettore nullo da [tex]$\mathbb{F}_q^m$[/tex], si ha quanto calcolato

Questo purtroppo e' sbagliato: per esempio [tex]\mu(GL(2,2)) = \mu(S_3) = 2[/tex].

Ah, ti ricordo che devi ancora trovare [tex]b(A_n)[/tex] (il fatto che [tex]b(A_3)=1[/tex] contraddice quello che hai scritto nell'intervento prima).

[j18eos]

"Martino":...Questo purtroppo e' sbagliato...

Lo scrivo anche qui che avevo predetto la presenza di un errore.

"Martino":...Ah, ti ricordo che devi ancora trovare [tex]b(A_n)[/tex] (il fatto che [tex]b(A_3)=1[/tex] contraddice quello che hai scritto nell'intervento prima).

Guarda che ho corretto! Ed in particolare concordano i risultati con l'essere [tex]$b(\mathbb{A}_3)=3$[/tex].

[Studente Anonimo]

Scusa non avevo visto. Comunque:

"j18eos":In questo caso [tex]$\mu(\mathbb{A}_n)=3$[/tex] a causa dei 3-cicli, mentre [tex]$b(\mathbb{A}_n)=n$[/tex];

Sono d'accordo che [tex]\mu(A_n)=3[/tex], ma non sono d'accordo su [tex]b(A_n)=n[/tex]. Per esempio si ha [tex]b(A_3)=1[/tex] (come ti dicevo).

[j18eos]

Non avevo capito che [tex]$b(\mathbb{A}_3)=1$[/tex] in quanto pensavo che fossi riferito all'errore precedente! Scusami te.

[j18eos]

Speriamo che l'aria di Bologna abbia avuto un buon effetto!

OUT OF SELF: Come matematico ho l'orribile difetto di imparare molto dagli errori. -_-

[Studente Anonimo]

Aspetta, quali interventi hai modificato? Per la prossima volta non sarebbe meglio inserire un nuovo intervento? Se non non capisco piu' nulla attendo una tua risposta prima di controllare.

[j18eos]

Non ho voluto scrivere un nuovo post per aggiustare il preesistente, comunque ho modificato il caso sul gruppo [tex]$GL(n;q)$[/tex].

[Studente Anonimo]

Io trovo un po' di confusione.

"j18eos":Sia [tex]$E=\{e_k\in\mathbb{F}_q^m\}_{k\in I_1^m}$[/tex] una base di [tex]$\mathbb{F}_q^m$[/tex], da quanto scritto una permutazione non identica [tex]$\phi(M)$[/tex] non fissa tutti gli elementi di [tex]$E$[/tex], quindi deve essere, senza ledere generalità, [tex]$e_1^{\phi(M)}=ae_1$[/tex] ove [tex]$a\in\mathbb{F}_q^\#$[/tex](*) e ciò impone che sia [tex]$q\neq2$[/tex].

Da quanto dici qui io capisco che l'idea che hai e' chiara e giusta, ma oltre a non giustificare quello che dici (perche' [tex]e_1^{\phi(M)}=ae_1[/tex]? Dovresti fare una dimostrazione un attimo piu' dettagliata) escludi un caso (il caso [tex]q=2[/tex]) che in realta' non crea problemi, basta usare un argomento un po' diverso da quello che usi (senza peraltro dirlo) tu.

Se posso farti una piccola critica, ti dico che secondo me usi una notazione impegnativa per dire cose semplici e non espliciti le idee. Immagino che tu abbia in mente le matrici, ma non parli mai di autovettori e forme diagonali (di questo stiamo parlando, no? I punti fissi sono gli autovettori di autovalore 1, e tu immagini matrici diagonali con sulla diagonale tutti uni meno un'entrata - ma allora perche' non lo dici?).