Gruppi ciclici e permutazioni

Il gruppo ciclico

Definizione gruppo ciclico

Abbiamo definito in Gruppi per la prima volta il significato di gruppo ciclico generato da un elemento del gruppo, questo insieme si è poi dimostrato essere un sottogruppo del gruppo

Un gruppo $G$ è chiamato ciclico se esiste un $a\in G$ tel per cui

$$G=\left\{a^n\mid n\in \mathbb{Z}\right\}$$

Dove a è chiamato elemento generatore.

Scriviamo $G=⟨a⟩$ per dire che $G$ è generato dall'elemento $a$. L'ordine del gruppo è la cardinalità:

$$ord(G)=|⟨a⟩|$$

Criterio $a^i=a^j$

Probabilmente ha qualche relazione con Teorema di Lagrange.

• note sull'enunciato entrambe le frecce $⟸$ sono abbastanza ovvie.

  Ragionando sul primo caso, nel caso in cui è infinito, se succedesse che $a^i=a^j\wedge i\ne j$ si avrebbe che l'ordine è finito, perché si ripeterebbe ogni tot, quindi dimostri così. Nel secondo caso credo sia così, ma non saprei come formalizzare la cosa.

• Dimostrazione Come si può notare, mi sto riducendo a una classe di resto con l'algoritmo di euclide nel secondo caso.

  

Questo è un teorema molto importante nei gruppi finiti, soprattutto, perché mi sta dicendo che ci possiamo sempre ridurre a una classe di resto per l'esponente.

Corollario 1 $\text{ Per ogni elemento di gruppo A, si ha che: }|A|=|⟨A⟩|$

Corollario 2

$a\in G,|a|=n\in \mathbb{N},k\in \mathbb{Z},a^k=e_g⟹n\mid k$

Osservazione

Questo fatto che la moltiplicazione fra due elementi funziona come una addizione fra due elementi in ${\mathbb{Z}}_n$ ci fa intuire come sia possibile un isomorfismo fra questi due gruppi.

Infatti esiste, dimostreremo poi che per ogni gruppo ciclico finito di ordine n esiste un isomorfismo con Zn (credo)

Relazione fra ordine $n,e$ un $k$ in $\mathbb{Z}$ e $gcd(n,k)$

• Dimostrazione

Questo teorema ci è molto utile per ridurre il generatore di un gruppo in un altro più gestibile o più semplice da manipolare

Corollario 1

In un gruppo ciclico, l'ordine di un elemento divide l'ordine del gruppo.

In simboli

$$a\in G,|a|=k,|G|=n,⟹k\mid n$$

(da notare l'ordine opposto dei divide rispetto al corollario 2 del teorema precedente)

Corollario 2 criterio $|a_i|=|a_j|$

Questo è molto simile al teorema precedente, ma ora stiamo parlando di ordine.

• Enunciato

  

• Dimostrazione

  

corollario 3 Generatori di gruppi ciclici finiti

Questo è un corollario del corollario 😂. In pratica afferma che

Il gruppo generato da $⟨a⟩$ è uguale a $⟨a^j⟩$ sse $gcd(n,j)=1$ con n l'ordine di a. cosa simile con $|a|=|a^j|⟺gcd(n,j)=1$

E avendo questo possiamo definire con concretezza di generatori del gruppo finito Zk

Corollario 4 Generatori di Zn

sia $k\in {\mathbb{Z}}_n$, k è un generatore sse $gcd(n,k)=1$.

la dimostrazione segue dal fatto che 1 è un generatore di Zn, e vogliamo che il gruppo generato da 1 e k sia lo stesso.

Classificazione di sottogruppi di gruppi ciclici

Teorema fondamentale dei gruppi ciclici

• Dimostrazione

Corollario Sottogruppi di Zn

Dal teorema fondamentale dei sottogruppi di gruppi ciclici abbiamo una caratterizzazione precisa dei sottogruppi presenti in Zn, sono in particolare tutti i divisori di n.

Numero di elementi di un un certo ordine in un gruppo ciclico

• Dimostrazione

  

Questo è anche una dimostrazione per Teorema di Lagrange#Teorema di Eulero.

Corollario 1 Numero di elementi di ordine d

• Enunciato

  

• Dimostrazione

  

Gruppi di permutazione

Decomposizione in cicli

Esiste una sintassi per scrivere le permutazioni con una notazione a cicli. Vogliamo dimostrare ora che questa sintassi è sempre possibile (quindi corrisponde a una equivalenza)

• Dimostrazione

  

  

La dimostrazione procede per via costruttiva, proponendo una specie di algoritmo per trovare tutti i cicli fino ad esaurimento di elementi nell’insieme.

Commutatività di cicli disgiunti

• Dimostrazione

  

Una volta letta la dimostrazione sembra una cosa ovvia, ma probabilmente l’idea è sulla scelta degli elementi iniziali?

Ordine di una permutazione (scomposizione con ordine di sottocicli)

• Dimostrazione

  

Decomposizione in permutazioni bicicle

• Dimostrazione

  

Proposizione

Questo lemma si può estendere a un caso più generale, dove si possono iniziare a distinguere permutazioni pari e dispari. Vedremo che avranno certe proprietà (legate alle matrici poi anche).

• Dimostrazione

  

  

Parità e disparità di 2-cicli

• Dimostrazione

  

L’insieme di permutazioni pari è un sottogruppo di Sn

• Dimostrazione

  Siano a, b due elementi di questo insieme, vogliamo dimostrare che $a{b}^{-1}\in S$ notiamo che per il teorema 5.5 $b^{-1}$ deve essere pari, perché altrimenti avrei che $e=b{b}^{-1}$ sarebbe scrivibile come un prodotto di permutazioni 2-cicle dispari. Inoltre, chiaramente un prodotto di 2 permutazioni pari è ancora pari (basta concatenare queste, che poi al massimo si eliminano a due a due). Ecco il sottogruppo.

Il gruppo alternante di n ha ordine n!

L’enunciato è proprio questo titolo, quindi non lo riporto (sul libro è il numero 5.7).

Invece riporto la definizione di gruppo alternante:

• Dimostrazione

  

Residui Quadratici

Si dice che $x\in G$ è un residuo quadratico nel suo gruppo se ha una radice quadrata in quel gruppo, ossia un $a\in G$ tale per cui $a^2=x$. Questo è di particolare interesse per robe di crittografia come per Asymmetric Cryptography.

Simbolo di Legendre

È il valore

$$x^{(p-1)/2}$$

È strettamente legata ai residui quadratici

Se $x\in Z_p$ è un residuo quadratico allora $x^{(p-1)/2}\equiv 1\mathrm{mod}p$. Computing modulo e-roots is as difficult as factorization.