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
$$ G = \left\{ a^{n} \mid n \in \mathbb{Z} \right\} $$Dove a è chiamato elemento generatore.
$$ ord(G) = \lvert \langle a \rangle \rvert $$Criterio $a^{i} = a^{j}$

-
note sull’enunciato entrambe le frecce $\impliedby$ sono abbastanza ovvie.
Ragionando sul primo caso, nel caso in cui è infinito, se succedesse che $a^i = a^j \land i \neq 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| = |\langle A\rangle|$
Corollario 2
$a\in G, |a| = n \in \mathbb{N}, k \in \mathbb{Z}, a^k = e_g \implies n \mid k$
Osservazione
Questo fatto che la moltiplicazione fra due elementi funziona come una addizione fra due elementi in $\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,\implies k \mid n $$(da notare l’ordine opposto dei divide rispetto al corollario 2 del teorema precedente)
Corollario 2 criterio $\lvert a_{i} \rvert = \lvert a_{j} \rvert$
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 $\langle a \rangle$ è uguale a $\langle a^j \rangle$ sse $gcd(n, j) = 1$ con n l’ordine di a. cosa simile con $|a| = |a^j| \iff 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 $ab^{-1} \in S$ notiamo che per il teorema 5.5 $b^{-1}$ deve essere pari, perché altrimenti avrei che $e = bb^{-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
$$ x^{(p - 1)/2} $$È strettamente legata ai residui quadratici
Se $x \in Z_{p}$ è un residuo quadratico allora $x^{(p-1)/2} \equiv 1 \mod p$. Computing modulo e-roots is as difficult as factorization.