Matematica Discreta Lezione del giorno 30 marzo 2009

Matematica Discreta

Lezione del giorno 30 marzo 2009

Abbiamo introdotto nella lezione scorso la teoria dei piani proiettivi: un piano proiettivo é per definizione un particolare tipo di 2-disegno di parametri (v,k,r

), in cui:

1) r

=1 (quindi ogni coppia di elementi è contenuta in 1 solo blocco) 2) l’intersezione di 2 qualunque blocchi distinti contiene un solo elemento.

Per analogia con la teoria della Geometria Proiettiva nel piano, abbiamo chiamato rette i blocchi di tale piano proiettivo, e punti gli elementi. (dunque per 2 punti di un piano proiettivo passa una sola retta e 2 rette distinte si intersecano in un solo punto): v rappresenta il numero totale di punti del piano proiettivo, mentre k rappresenta il numero di punti su ogni retta.

Ricordiamo che, per un risultato già dimostrato, un piano proiettivo, essendo un 2-disegno di parametri (v,k,r

=1), é in particolare anche un disegno di parametri (v,k,r) dove

r = r

(v-1)/(k-1) = (v-1)/(k-1)

Dunque, in un piano proiettivo di parametri (v,k,r

=1), ogni punto appartiene ad r=(v-1)/(k-1) rette (dunque per ogni punto passano (v-1)/(k-1) rette).

In uno degli esempi della lezione precedente, nel piano proiettivo di parametri (7,3,1) con rappresentazione grafica:

si può notare che per ognuno dei 7 punti passa un numero di rette uguale a (v-1)/(k-1)=6/2=3, come previsto teoricamente.

Ma in questo esempio notiamo anche che il numero r=3 (numero delle rette che passano per ogni punto) coincide con il numero k (numero di punti su ogni retta).

Ciò non é casuale:

Teorema. In un piano proiettivo di parametri (v,k,1), considerato anche come disegno di parametri (v,k, r=(v-1)/(k-1)), si ha necessariamente r=k.

(in pratica tale Teorema afferma appunto che il numero k di punti di ogni retta coincide con il numero r di rette che passano per ogni punto)

Dimostrazione.

Abbiamo già notato che ogni punto appartiene esattamente ad r rette, ed ogni retta contiene esattamente k punti.

Fissiamo una retta X (dunque di cardinalità k) ed un punto x non appartenente ad essa, sia Y={X

,

X

,….,X

} l’insieme delle r rette distinte che passano per x. Definiamo la funzione f: X  Y

associando al generico punto zX la retta X

(unica) passante per i punti x,z (sappiamo che per due punti passa una sola retta).

Tale funzione è iniettiva: se per assurdo fosse f(z)=f(w)=X

, con z,w punti distinti della retta X, per costruzione XX

conterrebbe i punti distinti z,w, contraddizione (2 rette si intersecano solo in un punto). La funzione f è anche surgettiva: qualunque sia la retta X

Y (cioé passante per il punto x), l’intersezione XX

contiene un singolo punto z, ed è ovvio che f(z)=X

(perché X

è appunto la retta passante per x,z). Essendo f biunivoca, si ha X= k = Y = r.

Dunque, in un piano proiettivo coincidono: il numero k di punti in ogni retta, e il numero r di rette passanti per ogni punto.

Dalla teoria dei disegni sappiamo però che il numero delle rette (blocchi) in un piano proiettivo é x

= (vr)/k = v ( dunque uguale al numero totale di punti del piano).

Tutte queste considerazioni ci portano ad affermare che in un piano proiettivo i punti e le rette hanno proprietà speculari (é il cosiddetto principio di dualità):

1) il numero di punti v é uguale al numero delle rette

2) il numero k di punti su ogni retta coincide con il numero r di rette passanti per un punto 3) per 2 punti distinti passa 1 sola retta e 2 rette distinte si intersecano in 1 solo punto

Cercheremo ora di esprimere i parametri di un piano proiettivo in funzione di 1 singolo parametro.

Sia dato un piano proiettivo di parametri (v,k,1). Abbiamo già notato che k = r = (v-1)/(k-1), da cui k(k-1) = v-1 v = k(k-1)+1

Se poniamo allora n = k-1 possiamo esprimere tutti i parametri in funzione di n:

k = n+1 , v = k(k-1)+1 = n(n+1)+1 = n

+n+1

Il numero naturale n così definito è detto ordine del piano proiettivo: dunque un piano proiettivo di ordine n è un 2-disegno di parametri (v=n

+n+1, k=n+1, r

=1) ed è anche un disegno di parametri (v=n

+n+1, k=n+1, r=n+1).

Riassumendo:

in un piano proiettivo di ordine n: il numero di punti (e anche il numero di rette) in totale è n

+n+1;

ogni “retta” contiene n+1 punti; per ogni punto passano n+1 rette; due rette distinte si incontrano esattamente in un punto”; per due punti distinti passa una e una sola retta.

L’esempio (citato sopra) di piano proiettivo di parametri (7,3,1) é dunque un esempio di piano proiettivo di ordine n=2 (perché n=k-1=3-1=2).

Il problema che si posero i matematici (fin dall’inizio del ‘900) fu allora il seguente: per quali valori di n esiste un piano proiettivo di ordine n ?

E’ facile costruire un piano proiettivo di ordine n=1; la sua rappresentazione grafica é un triangolo in cui i 3 punti sono i vertici del triangolo e le 3 rette sono i 3 lati:

Per n=2 abbiamo visto sopra un esempio di piano proiettivo.

Nella lezione precedente abbiamo visto rappresentazioni grafiche di piani proiettivi di ordine n=3 (di parametri (13,4,1)) e di ordine n=4 (di parametri (21,5,1)).

Utilizzando la teoria dei campi finiti (che studieremo in seguito) i matematici furono in grado di

costruire piano proiettivi di ordine n per tutti i valori di n che fossero potenza di un numero

primo: quindi per n=5,7,8,9,11,13 etc....

Restavano però dei “buchi”: é possibile costruire un piano proiettivo di ordine n=6 ? e di ordine n=10 ? e di ordine n=12 ? etc...

Il primo caso (in ordine di difficoltà) era il caso n=6: si trattava (se possibile) di costruire un piano con n

+n+1=6

+6+1=43 punti, e con 43 rette (ognuna contenente n+1=6+1=7 punti), in modo che per ogni coppia di punti passasse 1 sola retta e 2 rette si intersecassero in 1 solo punto.

Nessuno però riusciva a costruire un tale piano proiettivo, ma neanche a dimostrare che fosse impossibile costruirlo.

Un impulso essenziale alle ricerche si ebbe nel 1938, quando Bose scoprì una strana relazione della teoria dei piani proiettivi con una vecchia teoria studiata già di tempi di Eulero (alla fine del ‘700), e in sé molto “diversa” : quella dei “quadrati greco-latini”.

L’origine della teoria si fa risalire al “problema dei 36 ufficiali” di Eulero: in un articolo del 1792 Eulero affermò di essersi imbattuto nel seguente problema che lo aveva molto interessato:

vi sono 36 ufficiali di 6 gradi e 6 reggimenti differenti (sono presenti tutte le possibili coppie grado-

reggimento); se essi devono sfilare in parata disponendosi in un quadrato con 6 righe e 6 colonne, è

possibile fare in modo che in nessuna riga (e in nessuna colonna) vi siano ufficiali dello stesso

grado o dello stesso reggimento ?