Matematica Discreta II
Lezione del giorno 17 dicembre 2007
Il fatto che per ogni potenza di un numero primo esistano 2 quadrati latini ortogonali non risolve in particolare il caso n=6 (oltre il caso n=2 che non ha soluzione, come già visto): Eulero formulò una congettura affermando che per tutti i numeri n della forma n=2+4k (con k intero 0) non esistevano 2 quadrati latini ortogonali di ordine n.
Nel 1901 Tarry dimostrò che in effetti non esistono 2 quadrati latini ortogonali di ordine n=6: egli esaminò tutti i casi possibili (riducendo il ragionamento ai cosiddetti “quadrati latini ridotti”, che hanno sia la prima riga che la prima colonna contenenti ordinatamente i numeri 1,2,..,n; tali quadrati sono 9408), e non trovò in nessun caso 2 quadrati latini ortogonali, dando così risposta negativa al problema dei 36 ufficiali di Eulero.
Ciò sembrava rafforzare la congettura di Eulero, ma Bose e Shrikande (1959) costruirono 2 quadrati latini ortogonali di ordine n=10=2+24 (smentendo la congettura) e nel 1960 gli stessi (insieme con Parker) dimostrarono che per ogni n2,6 esistono sempre 2 quadrati latini ortogonali di ordine n.
Già nel 1938 Bose aveva scoperto un notevole legame fra la teoria dei quadrati latini ortogonali e quella dei piani proiettivi, che ora illustreremo.
Fissato n>2, qual è il massimo numero m di quadrati latini di ordine n a 2 a 2 ortogonali ?
Prima osserviamo che se A=(a
ij), B=(b
ij) sono quadrati latini ortogonali (con elementi 1,2,….,n) e se f : {1,2….,n} {1,2,…..,n} è una funzione biunivoca (una cosiddetta “permutazione” di 1,2…,n) allora anche A=(a
ij), B
1=(f(b
ij)) sono quadrati latini ortogonali: infatti B
1è un quadrato latino (se per assurdo vi fossero per esempio nella riga i 2 elementi uguali f(b
ij)=f(b
ih), per l’iniettività di f si avrebbe b
ij=b
ihcontro l’ipotesi che B è un quadrato latino; per l’ortogonalità: se per assurdo vi fossero in 2 caselle diverse del quadrato “sovrapposto” 2 coppie uguali a
ij=a
ht, f(b
ij)=f(b
ht), si avrebbe a
ij=a
ht, b
ij=b
ht, contro l’ipotesi che A, B sono ortogonali.
Teorema. Fissato n>2, esistono al più (n-1) quadrati latini di ordine n a 2 a 2 ortogonali.
Siano A
1=(a
(1)ij), A
2=(a
(2)ij), ….., A
m=(a
(m)ij) m quadrati latini a 2 a 2 ortogonali.
Per quanto osservato sopra, con opportune permutazioni di 1,2…,n possiamo modificarli in modo che tutti abbiano nella prima riga in ordine in numeri 1,2….,n (mantenendo l’ortogonalità).
Consideriamo 2 quadrati A
h, A
t:considerando i loro elementi nella seconda riga e prima colonna si ha certamente a
(h)21 a
(t)21(se per assurdo fosse a
(h)21= a = a
(t)21, sovrapponendo A
he A
t, nella prima riga troveremmo in qualche casella la coppia (a,a), e nella prima casella della seconda riga la stessa coppia, contro l’ipotesi di ortogonalità fra A
he A
t).
D’altronde nessun quadrato A
hpuò avere a
(h)21=1 (non sarebbe più un quadrato latino, avendo nella prima colonna 2 valori uguali nella prima e seconda riga).
Quindi gli elementi nella seconda riga e prima colonna di tali quadrati sono diversi fra loro e >1, e i valori possibili di tali elementi sono i numeri 2,3,….,n: il numero m dei quadrati è dunque ≤n-1, e si ha la tesi.
Problema: per quali valori di n>2 esistono effettivamente (n-1) quadrati latini di ordine n a 2 a 2 ortogonali (il massimo possibile) ?
A partire da un campo finito K di cardinalità n (potenza di un primo), fissati 2 elementi a,b distinti e
non nulli, abbiamo costruito in corrispondenza 2 quadrati latini ortogonali di ordine n: se quindi
consideriamo i diversi (n-1) elementi non nulli di K, possiamo costruire (n-1) quadrati latini di
ordine n a 2 a 2 ortogonali. Il problema quindi ha risposta affermativa per tutti gli n che sono
potenza di un primo.
Ma (fino ad oggi) nessuno è riuscito a costruire (n-1) quadrati latini di ordine n a 2 a 2 ortogonali per un valore di n che non sia potenza di un primo.
Per n=6 il risultato di Tarry implica che non esistono 5 quadrati latini di ordine 6 a 2 a 2 ortogonali (non ne esistono neanche 2 ortogonali !!!).
Illustriamo ora la notevole relazione che esiste fra la teoria dei quadrati latini ortogonali e la teoria dei piani proiettivi, scoperta da Bose (1938):
Teorema. Dato n>2:
esiste un piano proiettivo di ordine n esistono (n-1) quadrati latini di ordine n a 2 a 2 ortogonali Dimostrazione.
: Siano A
1=(a
(1)ij), A
2=(a
(2)ij), ….., A
n-1=(a
(n-1)ij) (n-1) quadrati latini a 2 a 2 ortogonali.
Costruiamo il piano proiettivo di ordine n nel modo seguente.
Gli n
2+n+1 punti sono di 2 tipi:
- n+1 punti “speciali” indicati con x,y,z
1,z
2,…..,z
n-1- n
2punti coincidenti con le possibili coppie ordinate (j,k) di numeri j,k=1,….n Le n
2+n+1 rette (ognuna con n+1 punti) sono di 4 tipi:
- n rette indicate con X
1,X
2,…,X
n: ogni retta X
icontiene il punto “speciale” x e gli n punti (i,1), (i,2),….,(i,n)
- n rette indicate con Y
1,Y
2,…,Y
n: ogni retta Y
icontiene il punto “speciale” y e gli n punti (1,i), (2,i),….,(n,i)
- n(n-1) rette indicate con Z
is(con i=1,….,n-1; s=1,….,n): ogni retta Z
iscontiene il punto “speciale”
z
ie tutti i punti (j,k) tali che a
(i)jk=s (cioè tali che il quadrato A
inella casella di indici j,k contiene il valore s)
- la retta “speciale” S che contiene tutti gli n+1 punti “speciali”
Si dimostra, sfruttando le proprietà dei quadrati latini ortogonali, che si è costruito un piano proiettivo di ordine n.
[Nell’esempio dei 2 quadrati ortogonali di ordine 3:
A
1=
2 1 3
3 2 1
1 3 2
A
2=
1 2 3
2 3 1
3 1 2
