1. GEOMETRIE DI GALOIS

Una calotta di PG(r,q) è un insieme di punti a 3 a 3 non allineati (generalizza il concetto di arco piano in dimensione maggiore di due); è completa se ogni punto dello spazio è allineato con due suoi punti. Le calotte complete sono particolarmente interessanti in teoria dei codici in quanto equivalenti ai codici lineari quasi-perfetti di ridondanza r+1 e distanza minima 4 definiti su GF(q) . Infatti è in virtù dei legami tra la teoria dell’Informazione e le Geometrie di Galois, che la problematica, posta da B. Segre negli anni '50, di determinare le cardinalità per cui una calotta completa esiste, ha stimolato molte ricerche in questi ultimi anni, supportate in alcuni casi da un elaborato calcolo elettronico. È complicato sviluppare una teoria generale che risponda a tale problematica poiché le proprietà geometriche, combinatorie, e talvolta anche gruppali, possono variare notevolmente nei piani finiti, a seconda del comportamento aritmetico dell'ordine, come già stato riscontrato in Teoria dei Numeri. Pochi risultati sono conosciuti in proposito e, naturalmente la conoscenza della cardinalità dei più grandi (è il cosiddetto “packing problem”; l’importanza di tale problematica è stata ribadita nel 1995 nel Convegno “R.C. Bose Memorial Conference on Statistical Design and related Combinatorics” – Fort-Collins, Colorado), o dei più piccoli n-archi o n-calotte completi in PG(r,q) è di fondamentale importanza. Solo nel caso di dimensioni due e tre è nota la massima cardinalità di calotte complete per via teorica (R.C. Bose 1947, B. Seiden 1950, B. Quist 1952): nel caso bidimensionale per q dispari è q+1 (ovali) mentre per q pari è q+2 (iperovali); in dimensione tre risulta q^2 + 1 (quadrica ellittica).

La mia ricerca in questo ambito ha prodotto risultati nelle seguenti direzioni:

1.1. ARCHI PIANI

Ogni arco di PG(r,q), mediante una successione di proiezioni si trasforma in un arco piano: ciò rende geometricamente significativi gli archi piani nel contesto delle Geometrie di Galois.

Nell'affrontare la problematica posta da B. Segre ho seguito sia un approccio che utilizza la geometria algebrica su campi finiti, sia un approccio che utilizza metodi combinatori.

Lo studio delle connessioni fra Geometria Finita e Teoria delle Curve Algebriche è iniziato negli anni '50 con i fondamentali lavori dello stesso Segre, ed ha ricevuto un notevole impulso dalla fine degli anni '80 con lo sviluppo della Teoria di Stöhr-Voloch sul numero dei punti razionali di una curva algebrica definita sopra un campo finito. L'idea centrale di tale teoria è che curve con molti punti razionali devono avere proprietà di non classicità. Lo studio di curve non classiche è lo strumento principale con cui sono stati ottenuti recenti ed importanti risultati sulle possibili cardinalità di archi completi di PG(2,q). Più precisamente la seconda più grande cardinalità per archi completi non è nota in generale, e per essa sono note soltanto alcune limitazioni, dovute fra gli altri a B. Segre, J.F. Voloch, J.A. Thas, J.W.P. Hirschfeld e G. Korchmáros. Le dimostrazioni di questi risultati sono tutte basate sull'idea originaria di Segre, ovvero associare ad un n-arco di PG(2,q) una curva algebrica definita sopra il campo finito GF(q) di ordine q, tale che il numero dei suoi punti GF(q)-razionali sia maggiore o uguale di n(q-n+2). Tale curva algebrica viene detta inviluppo dell'arco.

In [18] sono studiate le componenti di inviluppi di archi di cardinalità sufficientemente alta, nel caso q dispari. In particolare si concentra l'attenzione sulle componenti che contengono punti speciali - ovvero punti razionali dell'inviluppo, che non siano né singolari né punti di flesso. Stimando con la Teoria di Stöhr-Voloch il numero dei loro punti razionali è possibile dare una limitazione alla cardinalità dell'arco completo, che dipende soltanto da q e dall'ultimo ordine alla Frobenius della serie lineare tagliata su tale componente dalle coniche del piano. Vengono inoltre determinate esplicitamente le classi di curve che possono essere componenti irriducibili di archi completi di cardinalità alta. Tali curve sono curve classiche rispetto alla serie lineare tagliata dalle rette ma non classiche, né classiche alla Frobenius rispetto a quella tagliata dalle coniche. Tali risultati hanno motivato ulteriori studi di tali classi di curve, fra cui i lavori di A.Aguglia-G.Korchmáros e di M.Giulietti, nei quali si ottengono nuovi risultati sul loro numero di punti razionali.

In [29] si costruiscono archi altamente simmetrici utilizzando la quartica di Klein, e la sestica di Wiman, che risultano essere le curve algebriche piane non singolari rispettivamente di grado 4 e 6 massimamente simmetriche cioe' aventi gruppo di automorfismi che raggiunge il massimo ordine per curve algebriche piane non singolari di grado fissato, definite sul campo dei numeri complessi.

Precisamente in [29] sono state definite immersioni di PSL(2,7) e A_6 in PGL(3,k), ove k e' un campo algebricamente chiuso: esse costituiscono un ingrediente essenziale per dimostrare che l’insieme dei flessi della quartica e della sestica, rispettivamente in numero di 24 e 72, costituiscono archi per quasi tutte le caratteristiche con gruppi di automorfismi PSL(2,7) e A_6; tali archi, inoltre, risultano completi per quelle caratteristiche ove i numeri 24 e 72 cadono nell’intervallo delle cardinalità teoricamente ammissibili per la completezza. Sempre in [29] si prova l'unicita' della sestica di Wiman come curva massimamente simmetrica di grado 6. In realta' i gradi 4 e 6 sono le uniche eccezioni al risultato generale il quale afferma che a meno di proiettività la curva di Fermat è l'unica curva algebrica piana non singolare massimamente simmetrica: tale risultato e' stato provato in [13] per grado primo minore di 20 ed in generale in [AC20] e [65]. Tale generalizzazione ha richiesto un elaborato studio preliminare di teoria di gruppi al fine di determinare proprietà generali necessarie per sottogruppi di PGL(3,k) rispetto ai quali le curve in esame risultino invarianti. Sulla scia di questo risultato ha recentemente intrapreso lo studio di superfici altamente simmetriche di PG(3,k). In [AC28] si determinano la prima e la seconda cubica non singolari e massimamente simmetriche, utilizzando tecniche elementari che coinvolgono matrici.

In [84] sono state ottenute per ogni primo p ≥ 5 tutte le Zp-invarianti superfici quartiche non singolari a meno di equivalenza proiettiva. Come conseguente risultato si ottiene che il gruppo di automorfismi proiettivo di una superficie quartica non singolare di PG(3,k) ha cardinalità del tipo 2^a 3^b 5^c 7^d con c, d ≤ 1.

In [55], utilizzando l'immersione di A_6 in PGL(3,k) definita in [29], sono stati studiati gli archi di piani proiettivi che sono invarianti rispetto all'azione del gruppo alterno A_6, ottenendo per alcuni valori di q archi piani completi di cardinalità minore rispetto a quelli finora conosciuti.

Particolare attenzione si è poi dedicata alla determinazione degli archi completi di cardinalità piccola, con la finalità di risolvere, ove possibile (sembrando da un punto di vista generale il problema non trattabile) il problema centrale della determinazione dell'ordine minimo. È una problematica largamente inesplorata: quando ha preso avvio la mia ricerca, la conoscenza dell'ordine minimo in PG(2,q) era limitata a q=16 e costruzioni generali note di archi completi riguardavano cardinalità appartenenti alla parte centrale dello spettro.

In [6], [19], [37], [AC16] e [59] si è determinato l'ordine minimo in PG(2,q) per 17<=q<=32 ed anche lo spettro di archi completi con relativa classificazione a meno di automorfismi per q<=27. Per ottenere questi risultati di classificazioni e dimostrazioni di non esistenza è stato necessario l'ausilio di un elaborato calcolo elettronico basato fortemente su proprietà geometrico-gruppali, vista la crescita esponenziale della difficoltà al crescere di q. A questo scopo sono stati sviluppati algoritmi che usano le proprietà geometriche di simmetria degli spazi considerati in modo da ridurre il numero di casi da considerare e da evitare la determinazione di molte copie isomorfe della stessa soluzione. In particolare è stato messo a punto un algoritmo ibrido che combina una fase di classificazione e una fase di ricerca esaustiva basata su backtracking. Il vantaggio di questo approccio è che le informazioni sulla simmetria degli oggetti cercati ottenute durante la classificazione vengono ulteriormente usate nella fase successiva consentendo di eliminare casi che risultano equivalenti a casi già esaminati.

In [39] viene determinata una costruzione di archi, ottenuti aggiungendo ad arco prefissato altamente saturante orbite del suo stabilizzatore. Questo approccio fornisce in particolare archi completi di cardinalità più piccola di quelli conosciuti in precedenza per q=37, il primo caso tuttora aperto per la determinazione dell'ordine minimo.

In [9] viene presentata una costruzione geometrico-gruppale di una famiglia infinita di archi piani di cardinalità bassa, che in casi particolari fornisce archi di ordine minimo.

In [30] sia mediante il "manipolare" le orbite dei gruppi di simmetria che agiscono su PG(2,q), sia mediante algoritmi randomizzati ed euristici, sono stati determinati un gran numero di esempi di archi completi piani di cardinalità piccola in PG(2,q), q<1000 che suggeriscono delle congetture a carattere generale per l’andamento delle cardinalità prossime a quelle di ordine minimo.

Raffinando un algoritmo greedy randomizzato sviluppato in [30] per la ricerca di esempi di insiemi con proprietà estremali interessanti, ha permesso di effettuare una ricerca più mirata al crescere di q, determinando gli esempi descritti in [AC19], [42], [52], [AC22] e [56]: in molti casi tali esempi forniscono nuove limitazioni per la lunghezza minima di archi piani completi. La massa di dati prodotta dagli algoritmi euristici è stata analizzata in [AC24] e [AC29], dove è stato valutato l’andamento asintotico della limitazione sulla lunghezza minima di archi piani completi.

In [60], [AC27], [67], [AC30], [68] e [71] vengono proposti nuovi tipi di upper bounds per la cardinalita' minima di archi completi in PG(2, q).

In [41] si è sviluppata in piani di ordine 2^{4h+2} una procedura per la costruzione di archi strettamente transitivi  che risultano completi per q <=2^18. Inoltre nello stesso lavoro si determinano sottoinsiemi di PG(2,q) strettamente transitivi ottenuti come orbite di un sottogruppo di Singer.

In [AC17], [52] e [58] sono state definite costruzioni generali per archi completi aventi molti punti comuni con una conica. Inoltre in [AC17] e [58] vengono descritti, come unione di oggetti simmetrici, degli archi completi aventi (q+3)/2 punti su una conica e rispettivamente 4 e 3 punti fuori, controesempi ad un risultato del 1977 di G. Pellegrino secondo il quale per q=1 (mod 4) un arco completo avente (q+3)/2 punti su una conica può averne al più due esterni ad essa.

Un sottoinsieme di una conica viene chiamato quasi completo se puo' essere esteso ad un arco piano mediante l'utilizzo dei punti rimanenti della conica, con l'aggiunta del suo nucleo nel caso di caratteristica pari. In [82] vengono ottenuti nuovi upper bounds per la piu' piccola cardinalita' di un sottoinsieme quasi completo. Questi upper bounds vengono ad incrementare il numero di coppie (N,q) per cui risulta provato che ogni curva razionale normale in PG(N,q) e' un (q+1)-arco completo o equivalentemente, che un generalizzato [q + 1,N + 1, q ? N + 1]q doubly-extended Reed-Solomon codice non puo' essere esteso ad un codice con parametri [q + 2, N+ 2, q ? N + 1]q .

Gli ovali hanno la proprietà di ammettere in ogni punto un'unica tangente. In [AC11] e in [46] vengono considerati sottinsiemi del piano con tale proprietà, i cosiddetti semiovali. Il loro studio oltre ad avere un interesse geometricamente intrinseco, è motivato dalle applicazioni in crittografia (L. M. Batten 2000). Vengono dati teoremi di caratterizzazione, costruzioni, risultati di non esistenza. Si costruiscono inoltre nuovi esempi di semiovali di cardinalità grande. In [72] si determinano costruzioni e bounds per la cardinalità di semiovali contenuti nella curva Hermitiana.

I semiovali si generalizzano ai t-semiarchi, cioe' agli insiemi con la proprieta' che il numero delle tangenti in ciascuno dei suoi punti e' uguale a t. In [66] viene fornita la classificazione completa dei 2-semiarchi per q<=7 , lo spettro delle cardinalita' per q<=9 ed esempi sporadici per q>=11. In diversi casi i risultati di classificazione sono ottenuti con prove teoriche.

1.2. (n,k)-ARCHI PIANI

Una naturale generalizzazione nel piano del concetto di arco è quello di (n,k)-arco (o arco di specie k), ossia un insieme di n punti a (k+ 1) a (k + 1) non allineati.

Un esempio naturale di (n,k)-arco di PG(2,q) è dato dall'insieme dei punti GF(q)-razionali di una curva algebrica piana definita su GF(q) priva di componenti lineari, dove k è il numero di tali punti e d è il grado della curva. In generale un tale (k,d)-arco è incompleto. In [17] viene affrontato l'interessante problema di determinare in quali casi questa tipologia di (n,k)-archi sono completi. Tale problema è stato inizialmente posto da Hirschfeld e Voloch, i quali hanno dato una risposta parziale nel caso k=3. A parte le coniche e le cubiche, pochi altri esempi erano noti, fra cui la curva Hermitiana. La curva Hermitiana risulta essere non singolare e non classica alla Frobenius rispetto alla serie lineare tagliata dalle rette del piano. La domanda naturale è stata allora se l'insieme dei punti razionali di ogni curva non classica alla Frobenius rispetto alle rette è un (n,k)-arco completo. In [17] si dimostra un Teorema che fornisce una risposta affermativa sotto l'ulteriore condizione che il grado della curva duale sia minore di q+1. Tale condizione risulta essere soddisfatta da una curva sporadica definita sopra GF(8). Per un recente risultato di J. Top, quest’ultima curva e la quartica di Fermat sopra GF(9) sono le uniche curve di genere 3 definite su GF(q) con più di 2q + 6 punti razionali. In [17] inoltre, vengono presentati differenti esempi di (n,k)-archi completi derivanti da curve algebriche: si sottolinea che in molti di questi casi non erano conosciute tali strutture geometriche con stessi parametri.

In [76] si e' affrontato e risolto teoricamente il problema di determinare quando una curva algebrica piana singolare assolutamente irriducibile risulta completa come (n,3)-arco in PG(2,q).

Anche ad un (n,k)-arco piano è possibile associare un codice lineare di lunghezza n e dimensione 3. La sua capacità di correzione di errori risulta tanto migliore quanto più è grande la differenza n-k e quindi fissata la specie k risultano particolarmente ambiti gli (n,k)-archi piani di lunghezza massima (packing problem).

La specie 3 risulta particolarmente interessante in quanto gli (n,3)-archi del piano corrispondono ai codici lineari NMDS di dimensione 3 (mentre un codice MDS di parametri [n,k,d] ha distanza minima pari al massimo valore possibile n-k+1, cioè difetto di Singleton uguale a zero, un codice è NMDS se insieme al suo duale ha difetto di Singleton uguale a uno). In [10], [26] si è risolto il packing problem per archi di specie 3 in PG(2,11) e PG(2,13), provando che le cardinalità più grandi per un (n,3)-arco sono rispettivamente 21 e 23 e fornendo la classificazione degli esempi di ordine massimo. Ciò è stato ottenuto con un procedimento di ricerca esaustiva che si appoggia fortemente su relazioni geometriche tra archi di specie 2 e di specie 3 ([AC7]) e che usa proprietà di equivalenza proiettiva di particolari configurazioni. In [AC7], oltre a determinare un lower bound nel piano sulle massime cardinalità di un (m,r-1)-arco contenuto in un (n,r)-arco, sono stati determinati archi di specie 3 di cardinalità grande per q>=16, alcuni dei quali risultano di lunghezza massima sotto l’ipotesi di contenenza di archi di cardinalità fissata. Recentemente anche in PG(2,16) il packing problem per (n,k)-archi è stato risolto ([AC23], [64]). Vista la difficoltà esponenziale del problema al crescere di q, si è pervenuti alla soluzione utilizzando ulteriori vincoli geometrici sulla struttura delle soluzioni che consentono di tagliare rami delle spazio di ricerca che si riesce a dimostrare non possono condurre alla soluzione attesa.

Questi risultati definitivi rispetto il packing problem hanno fornito nuove limitazioni per l'esistenza di codici NMDS in PG(2,q), q=11,13,16, e permesso, mediante l'utilizzo di procedimenti di estensione, di dimostrare la non esistenza di altri codici NMDS ad essi correlati ([15], [64]). In particolare in [15] nuovi esempi di codici NMDS di lunghezza massima sono stati ottenuti.

Inoltre partendo da risultati di classificazione di (n,3)-archi ([14], [25]) abbiamo ottenuto nuovi risultati riguardanti l’esistenza e la classificazione di codici NMDS ([AC1], [33]). In particolare in [14] vengono fornite le classificazioni in PG(2,q), q=7,8,9, di tutti gli archi di specie 3 riguardati in termini di codici NMDS.

Salendo di dimensione, se si utilizzano solo procedimenti di estensione per la determinazione di codici NMDS, i tempi richiesti diventano eccessivamente lunghi: un primo passo per ridurre i tempi di esecuzione è stato quello di intercalare procedimenti di classificazione a procedimenti di estensione. Per ridurre la complessità computazionale del programma di classificazione si è introdotto un procedimento di preclassificazione, basato sull’utilizzo di un invariante del codice facilmente calcolabile ([AC2]): questa tecnica consente di determinare una partizione dell’insieme in esame in sottoinsiemi contenenti una o poche classi di equivalenza da cui la successiva fase di classificazione risulta avere nelle applicazioni un costo lineare. Inoltre si è rivelata utile per effettuare classificazioni una caratterizzazione fornita in [AC4] dei codici AMDS (più generali degli NMDS in quanto non si richiedono informazioni sul duale). Ciò ha reso possibile determinare per ogni dimensione la lunghezza massima dei codici NMDS su GF(q), q=7,8,9 ([33]).

I risultati ottenuti hanno risolto numerosi casi aperti presenti nei database specializzati, come http://www.win.tue.nl/~aeb/voorlincod.html (attualmente non più aggiornato), http://mint.sbg.ac.at e http://www-ma4.upc.es/~simeon/codebounds.html.

Un codice si dice ottimale rispetto al limite di Griesmer quando n>(k-2)q+k. In [41] vengono studiati in dettaglio gli (n, k)-archi costituiti dalle orbite di punti sotto l’azione di una potenza del ciclo di Singer di PG(2, q): in alcuni casi essi raggiungono il limite di Griesmer.

1.3. CALOTTE IN PG(r,q), r >2

Come già accennato, Segre aveva sottolineato l'importanza della determinazione dello spettro delle cardinalità di calotte complete in PG(r,q), ed in particolare dei valori estremi, in virtù delle applicazioni. Per esempio le calotte complete di cardinalità minima danno luogo, a parità di ridondanza, ai codici quasi-perfetti con densità più vicina a quella dei codici perfetti.

Prima della metà degli anni Novanta due sole famiglie infinite di calotte complete erano state costruite, entrambi in spazi proiettivi 4-dimensionali: una dovuta a B. Segre (1959) ed una a G.Tallini (1964). Nel 1996 in [4] abbiamo determinato, utilizzando una tecnica induttiva, una costruzione generale di calotte complete, valida per q pari in spazi proiettivi di ogni dimensione. Esse risultano di cardinalità piccola dell'ordine di grandezza q^{r/2} in dimensione pari e 3q^{(r-1)/2} in dimensione dispari (vicino ad un lower bound ottenibile con metodi combinatorici. In particolare esse risultano di ordine di grandezza inferiore a quello relativo alle calotte complete note in dimensione quattro (2q^2).

In [AC33] e [75], utilizzando metodi probabilistici, vengono determinate calotte complete in PG(N, q) di cardinalita' O(q^((N-1)/2)(logq)^300). Questo risultato costituisce un upper bound molto vicino al lower bound triviale e migliora quelli conosciuti in letteratura per calotte di piccola cardinalità in spazi proiettivi di ogni dimensione.

Per quanto riguarda risultati definitivi relativamente alla minima cardinalità di calotte complete, la mia ricerca si è concentrata nella dimensione 3 e 4: nel 1998 ([7],[8]), si è risolto il problema per q=5 e q=3, primi casi aperti nelle rispettive dimensioni. Per risolvere il problema nei due casi rispettivamente successivi, in PG(3,7) ed in PG(4,4), è stato necessario un elaborato studio teorico che ha permesso di ridurre i tempi eccessivamente lunghi per una ricerca esaustiva ([34],[49]). In particolare, il raggiungimento del risultato in PG(3,7), con relativa classificazione delle calotte complete di ordine minimo, è stato possibile ([34]) oltre che per l’utilizzazione di alcune proprietà gruppali e della graph-theoretical Ramsey theory, per la relazione che lega l’eventuale esistenza di [15,4,11]_₇ e [16,4,12]_₇ codici alla totalità degli archi di specie 3 della cardinalità seconda più grande e di quella massima. Precisamente, avendo a disposizione la classificazione di tali 3-archi ([25]) si è provata la non esistenza dei codici sopra menzionati e quindi la riduzione consistente di alcune configurazioni iniziali nella ricerca esaustiva. In [49] particolarmente utile è stato l'uso della non esistenza di [n,5,d]_₄ codici con 18<=n<=24 e d>=n-7 che permettono di introdurre vincoli sulla struttura delle sezioni iperpiane di calotte complete in PG(4,4). In [3], [11] e [12] vengono forniti procedimenti geometrici per la costruzione di famiglie di calotte complete di cardinalità piccola in PG(3, q), q dispari, le quali in alcuni casi sono risultate quelle di ordine minimo. In [32] viene considerato il problema in spazi proiettivi binari di qualsiasi dimensione, determinando famiglie infinite di calotte complete piccole. Rimanendo nel caso binario, in [AC3] e [36] vengono costruite famiglie infinite di calotte complete in spazi proiettivi di dimensione crescente usando una tecnica di “addition of space lift”, che consente di produrre esempi di cardinalità in un ampio intervallo dello spettro ammissibile.

In [5], [7], [8], [24], [AC12], [42], [49], [AC26], [AC35] e [AC36], [79] e [80] è stato affrontato il problema degli spettri di calotte complete in varie dimensioni, determinando classificazioni di alcune cardinalità.

In [47] si perfeziona la tecnica induttiva presentata in [4] ampliando notevolmente la classe di calotte piane che possono essere prese come base della costruzione induttiva: il risultato principale è la determinazione per q>8 e per ogni dimensione r>2 di un nuovo upper bound per la minima cardinalità di calotte complete. Inoltre nello stesso lavoro viene introdotta la nozione sum-point per una calotta completa piana, che ha costituito un ausilio per ottenere un miglioramento del nuovo upper bound per q<=2^15.

Per quanto riguarda la massima cardinalità di calotte complete in [42] vengono forniti nuovi upper bounds in dimensioni 5<=d<=9, per alcuni valori di q.

In dimensione 3, essendo nota la massima cardinalità, l'attenzione è sulla seconda più grande: in [AC8] e [44] per q primo dispari, q=2 (mod 3), q>=11, una nuova famiglia infinita di calotte complete di cardinalità (q^{2}+q+8)/2 è stata costruita. Essa fornisce un nuovo lower bound sulla seconda cardinalità più grande per calotte complete. Una leggera variante di questa costruzione fornisce per q=5 una delle due 20-calotte complete della seconda cardinalità più grande. Inoltre in [44], studiando sezioni piane della costruzione si è stabilito che l'unico 14-arco completo in PG(2, 17) contiene 10 punti su una conica. Questo fornisce un controesempio ad un risultato generale del 1977 di G. Pellegrino secondo il quale per q=1 (mod 4) un arco completo avente (q+3)/2 punti su una conica può averne al più due esterni ad essa. 

1.4. INSIEMI SATURANTI

Gli insiemi saturanti di uno spazio proiettivo generalizzano il concetto di calotta completa. Precisamente un sottinsieme S di PG(r,q) viene detto s-saturante se s è il minimo intero tale che per ogni punto P di PG(r,q) esistono s+1 punti di S il cui sottospazio generato contiene P. Nel caso s=1 tale proprietà equivale al fatto che le bisecanti di S ricoprono lo spazio proiettivo. Di particolare interesse è la costruzione di insiemi saturanti minimali (non contenenti sottinsiemi propri saturanti) di cardinalità piccola in virtù dei legami con i codici di ricoprimento e con altre aree della Combinatorica quali i disegni di esperimento ed il problema del grado/diametro in teoria dei grafi. La problematica della determinazione della minima cardinalità per insiemi saturanti risulta più complessa rispetto al caso delle calotte complete in quanto si hanno minori vincoli geometrici.

Il migliore upper bound generale noto per la minima cardinalità riguardo gli 1-saturanti del piano proviene da stime probabilistiche (E. Boros, T. Szonyi, K. Tichler, 2005): esso è comunque abbastanza lontano da una limitazione inferiore che può essere ottenuta da un semplice argomento di conteggio. Per quanto riguarda valori esatti della minima cardinalità nel piano, in [20] si è risolto il problema per q<=16 e successivamente in [AC21], [59] e [61] per q<=23, con relativa classificazione degli esempi. È stato inoltre determinato lo spettro delle cardinalità e classificati tutti gli esempi per q<=13.

In [22] vengono fornite stime di alcuni parametri estremali di insiemi saturanti minimali in PG(n,q) e viene introdotto un concetto di densità saturante che consente di ottenere nuovi lower bounds per i più piccoli insiemi saturanti minimali. Nello stesso lavoro viene determinata anche la più grande cardinalità di un insieme 1-saturante minimale.

In [AC3] e [36] vengono effettuate costruzioni di insiemi 1-saturanti minimali negli spazi proiettivi binari PG(r,2). Alcune costruzioni forniscono insiemi con una struttura particolarmente simmetrica connessa con rette interne, poligoni ed orbite dei gruppi stabilizzatori. Come esempio si è esaminato un 11-insieme in PG(4,2), chiamato “Pentagono a centro”. A partire da esempi di queste costruzioni si determinano famiglie infinite di insiemi 1-saturanti in spazi di dimensione crescente. Si è inoltre fornita la classificazione completa degli insiemi 1-saturanti minimali in basse dimensioni.

Ad un n-insieme s-saturante in PG(r,q) si può associare un codice di ricoprimento [n,n-(r+1)]_R con raggio R=s+1. In [23] vengono fornite nuove costruzioni di famiglie infinite di codici di ricoprimento con R=2,3 e codimensione crescente. La base di queste costruzioni induttive è costituita da insiemi saturanti ottenuti negli articoli precedenti. L’interesse di tali costruzioni sta nel fatto che permettono di ottenere codici con bassa densità di ricoprimento.

In [AC6] e [31] viene introdotto il concetto di codice di ricoprimento localmente ottimale in corrispondenza alla proprietà di minimalità per insiemi saturanti e si forniscono costruzioni di famiglie infinite di tali codici. Sempre per lo stesso tipo di codici vengono effettuate classificazioni in "piccole geometrie" (per piccoli valori della codimensione e di q) utilizzando algoritmi scritti in Magma che effettuano una ricerca in ampiezza che sfrutta proprietà di equivalenza proiettiva ed effettua preclassificazioni basate sul calcolo di invarianti, quali ad esempio la distanza minima. Vengono inoltre determinati nuovi upper bonds e lower bounds rispettivamente per le lunghezze minime e massime.

In [AC13], [AC14] e [50] si è proseguito lo studio degli insiemi r-saturanti in spazi di dimensione maggiore di 3. Uno strumento innovativo che è stato utilizzato è la nozione di blocking set forte, che specializza quella classica di blocking set di specie n. In particolare sono state determinate, mediante la tecnica di costruzioni concatenanti, nuove famiglie infinite di insiemi saturanti di cardinalità piccola in dimensione arbitraria che danno luogo a codici di ricoprimento q-ari che hanno densità di ricoprimento asintotica migliore rispetto a quelle finora conosciute.

In [AC25], [62], [69] e [AC34], viene introdotto un concetto di insieme s-saturante multiplo e si è provato che sono il corrispondente geometrico nel caso lineare di codici di ricoprimento multipli dei “farthes-off points” (MCF). Una applicazione di tali codici può essere trovata nel "football pool problem", ad esempio nel ridurre le previsioni per moltiplicare una vincita. Per tali codici MCF si introduce un concetto di densità saturante multipla, come caratteristica di qualità: per risparmiare risorse i più ambiti sono quelli di densità più bassa possibile, che in linguaggio geometrico equivalgono ad insiemi saturanti multipli di minima lunghezza. Inoltre negli stessi lavori si forniscono costruzioni di 1-saturanti multipli di cardinalità piccola che migliorano l'upper bound di Boros et al., determinato da risultati probabilistici sugli 1-saturanti classici. Infine si considerano Almost Perfect MCF (APMCF) codici, cioe' codici per i quali ciascuna parola a distanza R dal codice appartiene ad esattamente μ sfere centrate nelle parole codice e le loro connessioni con uniformly packed codes, two-weight codes, and subgroups of Singer groups. In [73] si propongono alcuni metodi algebrici che consentono di determinare codici APMCF di densita' uguale a 1 (ottimale) o prossima ad 1 e si determinano classificazioni. In [78] usando sia un approccio probabilistico, sia un approccio costruttivo induttivo per i saturanti multipli, si ottengono nuovi upper bounds.

1.5. MODELLO CICLICO DI PG(r,q) e ARCHI

Studiando l’inverso additivo di rette nel modello ciclico di PG(r,q), in [16] è stato generalizzato un risultato di M.Hall, il quale afferma che nel modello ciclico del piano proiettivo di Galois l’inverso additivo di una retta è una conica; in particolare si è ottenuto che per l’inverso additivo di una retta ci sono due possibilità: o è un (q+1)-arco o è contenuto in un iperpiano. In dimensione 3 il risultato è più forte in quanto la seconda possibilità si restringe ad una retta. Si è poi generalizzato quest’ultimo risultato a spazi di dimensione superiore a 3.

1.6. SPREADS E BLOCKING SETS

Si è considerato il problema della determinazione di maximal partial spreads in PG(3,q), cioè insiemi di rette mutualmente sghembe tali che ogni retta dello spazio proiettivo intersechi almeno una retta di un tale insieme. Le maximal partial spreads sono state inizialmente studiate da Dale Mesner nel 1967. Il migliore upper bound attuale per la loro cardinalità è stato trovato da Aart Blokhuis, determinato a partire dai suoi risultati sui blocking sets. Nello studio di tale problematica in PG(3,7), O. Heden ha provato che tale upper bound non può essere migliorato in generale. Il primo caso aperto, per q dispari, era q=9 con possibili cardinalità 75 e 76. In [40] si è eliminata la seconda possibilità: un lavoro preliminare [38] è stata la determinazione e classificazione di opportuni blocking sets in PG(2,9) che hanno costituito la base per l’effettuazione dello studio geometrico delle possibili configurazioni di holes (punti non appartenenti alla spread). Usando inoltre un risultato di Blokhuis-Metsch sui pesi di spazi e sottospazi affini, si è pervenuti al risultato. In [L1] con analogo approccio si elimina anche la prima possibilità, risolvendo completamente il problema.

Sempre nell’ambito dei blocking sets ho intrapreso lo studio delle “partizioni” di PG(2,q); più precisamente la finalità è determinare il massimo numero di blocking sets minimali disgiunti. In [35] si è provato che in PG(2,q) è possibile costruire cq blocking sets disgiunti, con c circa uguale ad 1/3, e si è esteso il risultato ad alcune classi di piani non desarguesiani. Inoltre si è mostrato che una congettura di M.Kriesell (2000) secondo la quale esistono q/2 blocking sets disgiunti in un piano di ordine q, non quadrato, può essere “forse” migliorata, avendo determinato per q=8 cinque blocking sets minimali disgiunti.

Parallelamente ho affrontato lo studio dei blocking sets in piani di Moebius. Non esistevano costruzioni generali e pochi erano i limiti conosciuti: L. Lovasz ha provato che ogni piano di Moebius di ordine q contiene un blocking set di cardinalità minore di 3qlogq mentre Bruen e Rotschild hanno dimostrato che per q>=9 le cardinalità si mantengono più grandi di 2q-1. In [27], dopo aver determinato lo spettro delle cardinalità con relativa classificazione, per piccoli valori di q, si è dimostrato che comunque si consideri un numero naturale C, esiste una costante q(C) tale che se un piano di Moebius ha ordine q>q(C), allora ogni blocking set di esso ha almeno 2q + C punti.