Campi di Galois

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Campi di Galois

Messaggio da giobimbo »

Non si spaventi chi non ha studiato algebra astratta, il problema in discussione consiste nello scomporre una tabella di nxn elementi in n tabelle di n elementi ciascuna. Tra l'altro mi sembra di aver già proposto tempo fa qualcosa di simile, seppure molto più semplice.
Grosso modo, un campo di Galois è un insieme di n elementi (n=p numero primo oppure n=q potenza di un primo) dotati di una struttura algebrica definita da due tabelle che spiegano come sommare e moltiplicare tra loro gli n elementi. La tabella di addizione è un gruppo commutativo; la tabella di moltiplicazione è - limitatamente agli elementi non nulli - ancora un gruppo commutativo. In particolare si ha che il prodotto è distributivo rispetto alla somma e tale stretto rapporto tra le due operazioni è dovuto al fatto che la tabella moltiplicativa è nascosta nella tabella additiva. Vediamo come ricavarla.
PRIMA FASE - Scomposizione
Sia n=p=5, per esempio, allora la tabella additiva (sotto a sinistra) corrisponde a quella del gruppo ciclico con 5 elementi e userò n come elemento neutro invece di zero, così come il 12 è l'elemento neutro nell'aritmetica dell'orologio, come il 9 è l'elemento neutro nella prova del nove. Spostiamo poi le colonne in modo da avere tutti gli elementi neutri nella diagonale principale (sotto al centro) e infine eliminiamo la prima riga e la prima colonna (sotto a destra).

5 1 2 3 4 ..... 5 4 3 2 1
1 2 3 4 5 ..... 1 5 4 3 2 ..... 5 4 3 2
2 3 4 5 1 ..... 2 1 5 4 3 ..... 1 5 4 3
3 4 5 1 2 ..... 3 2 1 5 4 ..... 2 1 5 4
4 5 1 2 3 ..... 4 3 2 1 5 ..... 3 2 1 5

La tabella 4x4 deve essere ora scomposta in 4 sotto-tabelle primitive di cui:
1) una, chiamata primitiva neutra, contiene tutti gli elementi neutri e 0 in tutti gli altri posti;
2) le altre devono contenere gli elementi 1, 2, 3, 4 disposti in righe e colonne diverse, tutti 0 negli altri posti.
L'unica scomposizione è dunque:

5 0 0 0 ..... 0 4 0 0 ..... 0 0 3 0 ..... 0 0 0 2
0 5 0 0 ..... 0 0 0 3 ..... 1 0 0 0 ..... 0 0 4 0
0 0 5 0 ..... 2 0 0 0 ..... 0 0 0 4 ..... 0 1 0 0
0 0 0 5 ..... 0 0 1 0 ..... 0 2 0 0 ..... 3 0 0 0

Sia ora n=q=3*3=9, partendo dal gruppo ciclico con 9 elementi ricaviamo le tabelle:

9 1 2 3 4 5 6 7 8 ..... 9 2 1 6 8 7 3 5 4
1 2 9 4 5 3 7 8 6 ..... 1 9 2 7 6 8 4 3 5 ..... 9 2 7 6 8 4 3 5
2 9 1 5 3 4 8 6 7 ..... 2 1 9 8 7 6 5 4 3 ..... 1 9 8 7 6 5 4 3
3 4 5 6 7 8 9 1 2 ..... 3 5 4 9 2 1 6 8 7 ..... 5 4 9 2 1 6 8 7
4 5 3 7 8 6 1 2 9 ..... 4 3 5 1 9 2 7 6 8 ..... 3 5 1 9 2 7 6 8
5 3 4 8 6 7 2 9 1 ..... 5 4 3 2 1 9 8 7 6 ..... 4 3 2 1 9 8 7 6
6 7 8 9 1 2 3 4 5 ..... 6 8 7 3 5 4 9 2 1 ..... 8 7 3 5 4 9 2 1
7 8 6 1 2 9 4 5 3 ..... 7 6 8 4 3 5 1 9 2 ..... 6 8 4 3 5 1 9 2
8 6 7 2 9 1 5 3 4 ..... 8 7 6 5 4 3 2 1 9 ..... 7 6 5 4 3 2 1 9

PROBLEMA: scomporre la tabella 8x8 in primitive (ci sono diverse scomposizioni possibili).

giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Messaggio da giobimbo »

SECONDA FASE - Trovare la scomposizione giusta
Questa fase è riservata a chi sa moltiplicare tra loro le matrici o le permutazioni.
Trasformiamo le 4 primitive dell'esempio con n=p=5, sostituendo con 1 tutti i numeri diversi da zero, ottenendo:

1 0 0 0 ..... 0 1 0 0 ..... 0 0 1 0 ..... 0 0 0 1
0 1 0 0 ..... 0 0 0 1 ..... 1 0 0 0 ..... 0 0 1 0
0 0 1 0 ..... 1 0 0 0 ..... 0 0 0 1 ..... 0 1 0 0
0 0 0 1 ..... 0 0 1 0 ..... 0 1 0 0 ..... 1 0 0 0

Se pensiamo a tali tabelle come fossero matrici, esse prendono il nome di matrici di permutazione e il prodotto di due matrici di permutazione è sempre una matrice di permutazione. Ovviamente le matrici di permutazione 4x4 sono in numero di 4!=4*3*2*1=24, quindi quelle trovate dalla scomposizione sono solo una parte, ma una parte particolare. Infatti il prodotto di due qualsiasi di tali matrici è sempre una delle quattro: esse formano un gruppo.
Per matrici più grandi la moltiplicazione diventa difficoltosa, forse è meglio trasformarle in permutazioni e operare con esse. Moltiplicando ognuna delle matrici sopra per il vettore colonna [1 2 3 4] otteniamo, in ordine, i vettori colonna [1 2 3 4], [3 1 4 2], [2 4 1 3] e [4 3 2 1], cioè le permutazioni (1 2 3 4), (3 1 4 2), (2 4 1 3) e (4 3 2 1). Il prodotto di due qualsiasi di tali permutazioni è sempre una delle quattro: esse formano un gruppo.
Un altro semplice modo di trasformare le tabelle in permutazioni consiste nello scrivere il numero di riga degli 1, procedendo dalla prima colonna in avanti. Per esempio, nella seconda tabella si ha 1 nella terza riga (scrivo 3), 1 nella prima riga (scrivo 1), 1 nella quarta riga (scrivo 4) e 1 nella seconda riga (scrivo 2): dunque (3 1 4 2) è la permutazione corrispondente.

PROBLEMA: trovare la scomposizione S di cui le primitive, trasformate in matrici di permutazione o in permutazioni, formano un gruppo (cioè il prodotto di due primitive qualsiasi deve dare sempre una primitiva di S).

Da notare che, mentre per ogni altro valore di n dalla scomposizione in primitive si ricava solo il campo di Galois, da n=9 si ricava anche un anello (un campo è un anello con certe proprietà aggiuntive).

Rispondi