27 maggio 2018

Curve di ampiezza costante

Ricordiamo che, ata una curva piana chiusa $C$, regolare a tratti e che delimiti una regione convessa, una "retta di supporto" a $C$ è una retta che ha almeno un punto in comune con $C$ e nessun punto in comune con il suo interno.
Definizione.Una curva di ampiezza costante è una curva piana convessa tale che la distanza fra due coppie qualsiasi di rette di supporto parallele è indipendente dalle rette scelte. Tale distanza è appunto chiamata l'ampiezza della curva.
Intuitivamente, una curva di ampiezza costante è quindi una curva tale che può "essere fatta rotolare" fra due rette parallele senza alterarne la distanza. Un esempio immediato è la circonferenza: in tal caso vi è una sola retta di supporto in ogni punto (la retta tangente) e due rette di supporto sono parallele solo se i corrispondenti punti sono antipodali; pertanto la circonferenza ha ampiezza costante, pari al diametro. Questo è uno dei motivi per cui le ruote hanno forma circolare: se la loro forma fosse una curva di ampiezza non costante (ad esempio, un'ellisse) una piattaforma che si spostasse su di esse oscillerebbe su e giù durante il movimento.

Esistono curve di ampiezza costante diverse dalla circonferenza? Sorprendentemente, la risposta è affermativa, e l'esempio più famoso è dato dal cosiddetto triangolo di Rouleaux, così chiamato in onore del matematico e ingegnere F. Rouleaux (1829-1905), che insegnò alla Reale Scuola tecnica Superiore di Berlino. Esso si ottiene partendo da un triangolo equilatero e centrando col compasso in ciascuno dei vertici in modo da costruire tre archi di circonferenza che congiungono gli altri due vertici.

Il Triangolo di Rouleaux (il bordo della regione in giallo) è una curva ad ampiezza costante.

Come la circonferenza e ogni altra curva di ampiezza costante, il Triangolo di Rouleaux ruota esattamente all'interno di un quadrato (di lato pari all'ampiezza), mantenendosi in contatto con tutti e quattro i vertici durante la rotazione. Questa proprietà è stata sfruttata in ingegneria in modo sorprendente: nel 1914, H. J. Watts brevettò una punta per trapano, basata sul triangolo di Rouleaux, in grado di produrre fori quadrati!

Il trangolo di Rouleaux possiede molte altre interessanti proprietà. Una delle più importanti è che essa è la curva di ampiezza costante che ha la minima area per un'ampiezza data (questo è noto come teorema di Blaschke-Lebesgue); si noti che la diseguaglianza isoperimetrica implica che la curva di ampiezza costante che massimizza l'area è invece la circonferenza.

Il Triangolo di Rouleaux presenta tre punti angolosi nei vertici del triangolo equilatero di partenza; tali punti possono essere tuttavia "allisciati", ottendendo una curva di ampiezza costante e di classe $C^1$. Inoltre, è possibile costruire "poligoni di Rouleaux" partendo da poligoni regolari con più di tre lati: si ottengono in tal modo curve di ampiezza costante il cui gruppo di simmetria è il gruppo diedrale del poligono di partenza. Curiosamente, le monete britanniche da 20p e 50p sono eptagoni di Rouleaux.

Ancora più sorprendente del triangolo di Rouleaux è l'esistenza di curve di ampiezza costante asimmetriche. Una loro costruzione è spiegata nel bell'articolo di M. Gardner [Gard]. Gardner nota anche, opportunamente, che l'esistenza di simili curve impedisce che si possa verificare la circolarità della chiglia di un natante (ad esempio, di un sottomarino) controllando esclusivamente l'ampiezza in ogni suo punto: una chiglia potrebbe essere infatti mostruosamante sbilenca e superare tuttavia tale controllo. Per questo motivo, il controllo di circolarità viene effettuato applicando opportuni profili sagomati.

Esistono anche curve di ampiezza costante algebriche, cioè definite da un'equazione polinomiale della forma $f(x, \, y)=0$. Un esempio è presentato in [Rab] e la corrispondente equazione (di grado $8$) può essere trovata nella pagina Wikipedia dedicata all'argomento.


Riferimenti:

[Gard] M. Gardner: Curve di Ampiezza Costante, in Enigmi e Giochi Matematici, Vol. 4
[Rab] S. Rabinowitz: A Polynomial Curve of Constant Width, Missouri Journal of Mathematical Sciences 9 (1997), 23–27.

20 maggio 2018

Il teorema dell'Esagramma Mistico di Pascal

Il seguente notevole risultato venne scoperto nel 1639 dall'allora sedicenne matematico e filosofo francese Blaise Pascal (1623-1662):
Teorema. Si considerino nel piano proiettivo una conica $C$ e un esagono $X$ i cui vertici giacciono su $C$. Allora le tre coppie di rette che individuano lati opposti di $X$ si incontrano in tre punti che giacciono su una retta, detta la "retta di Pascal" dell'esagono $X$.
Esagono inscritto in una conica. La retta di Pascal è quella tratteggiata

Dati sei punti $\{P_1, \ldots, P_6\}$ non ordinati su una conica, essi possono essere congiunti per formare un esagono in $60$ modi distinti, e di conseguenza esistono $60$ rette di Pascal; l'insieme di tali rette è detto l'Esagramma Mistico relativo a $\{P_1, \ldots, P_6\}$, e per tale motivo il teorema di Pascal è anche detto teorema dell'Esagramma Mistico.

Il teorema di Pascal può essere visto come una generalizzazione del classico teorema di Pappo: infatti, quest'ultimo si ottiene nel caso limite in cui la conica $C$ degenera nell'unione $L_1+L_2$ di due rette. Si noti inoltre che è possibile dare un enunciato del teorema di Pascal anche nel piano affine, trattando opportunamente i casi in cui una o più coppie di rette diventino parallele; ad esempio, se due coppie di lati opposti definiscono rette parallele, allora lo stesso vale per tutte e tre le coppie di lati opposti, e non esiste nessuna retta di Pascal affine (in tal caso la retta di Pascal è la retta all'infinito).

L'inverso del teorema di Pascal è detto teorema di Braikenridge e Maclaurin:
Se le tre coppie di rette definite dai lati opposti di un esagono $X$ si incontrano in tre punti allineati, allora i vertici $\{P_1, \ldots, P_6\}$ di $X$ giacciono su una conica $C$ (che può essere degenere). Variando il sesto punto $P_6$, ciò permette di dare una costruzione proiettiva della conica determinata dai cinque punti $\{P_1, \ldots, P_5\}$.
Esistono numerose dimostrazioni del teorema di Pascal, sia sintetiche che analitiche. Qui ci limitiamo ad esporne una che si trova spesso nei testi introduttivi di Geometria Algebrica.
Dimostrazione. Siano $P_1, \,  P_2, \ldots, P_6$ i sei vertici ordinati dell'esagono $X$, e siano $l_1$,  $l_2$, $l_3$ le rette dei lati $P_1P_2$, $P_3P_4$, $P_5P_6$ e $m_1$, $m_2$, $m_3$ le rette dei lati $P_2P_3$, $P_4P_5$, $P_6P_1$. Sia $f$ la forma cubica $l_1l_2l_3$ e $g$ la forma cubica $m_1m_2m_3$, e si scelga uno scalare $\lambda$ tale che la forma cubica $f+\lambda g$ si annulli su un ulteriore punto $P$ di $C$ (che per semplicità consideriamo irriducibile, ma la dimostrazione può essere adattata anche nel caso di $C$ riducibile). Allora la cubica piana $D$ definita da $f+\lambda g=0$ e la conica $C$ hanno almeno sette punti in comune, dunque per il teorema di Bézout esse devono avere in comune una intera componente. Ciò vuol dire che $D$ si spezza nell'unione della conica $C$ e di una retta $L$, che risulta essere la retta di Pascal di $X$.
$\square$
Il teorema di Pascal può essere anche ottenuto come una conseguenza del teorema di Cayley-Bacharach per le cubiche piane: si veda il corrispondente articolo Wikipedia per ulteriori dettagli sull'argomento.

05 maggio 2018

L'algoritmo di Strassen

Quanto è dispendioso, dal punto di vista computazionale, moltiplicare due matrici $n \times n$?
La risposta che viene subito in mente è che servono al più $O(n^3)$ operazioni, dato che l'algoritmo standard (insegnato nei corsi base di Algebra Lineare) richiede $n \times n \times n=n^3$ moltiplicazioni e possiamo trascurare il contributo dato delle addizioni, computazionalmente irrilevante.

Nel 1969 V. Strassen, mentre cercava di dimostrare che l'algoritmo standard è ottimale, fece l'inaspettata scoperta che è possibile moltiplicare due matrici $2 \times 2$ utilizzando solo sette moltiplicazioni invece di otto. In suo onore, questo metodo di moltiplicazione matriciale è oggi chiamato algoritmo di Strassen.


V. Strassen nel 1979 (fonte Wikipedia)

L'algoritmo di Strassen può essere generalizzato a matrici $n \times n$, e permette di moltiplicare due tali matrici utilizzando $O(n^{\log_2(7)+o(1)}) = O(n^{2,8074})$ operazioni, invece delle $O(n^3)$ richieste dall'algoritmo standard. Con l'architettura dei moderni processori, implementare l'algoritmo di Strassen invece di quello usuale permette un guadagno in efficienza di circa il 20%, almeno per quanto riguarda matrici non strutturate e di grossa taglia ($n>2000$).

Essendo la moltiplicazione di matrici uno strumento centrale in ogni branca dell'Analisi Numerica, la scoperta di nuovi algoritmi di bassa complessità computazionale ha evidentemente un impatto drammatico sulla disciplina. Infatti, l'algoritmo di Strassen inaugurò un nuovo settore di ricerca noto come Fast Matrix Multiplication.

Al momento, uno degli algoritmi più veloci è quello di Coppersmith–Winograd, che ha una complessità computazionale pari a $O(n^{2,375477})$. Esistono anche algoritmi asintoticamente più efficienti, ma in pratica essi sono raramente implementati a causa delle enormi costanti che compaiono nell'espressione esplicita del tempo di esecuzione richiesto [2].

Notiamo che, in ogni caso, conoscere una matrice $n \times n$ richiede la conoscenza di tutti i suoi $n^2$ elementi, quindi la complessità computazionale di un'operazione binaria fra matrici deve essere almeno $O(n^2)$. Una sorprendente congettura (al momento non dimostrata) è che per ogni numero naturale $n$ e per ogni numero reale $\epsilon >0$ esiste un algoritmo capace di moltiplicare due matrici $n \times n$ con complessità computazionale $O(n^{2+ \epsilon})$. In altre parole, almeno asintoticamente, moltiplicare due matrici non dovrebbe essere più dispendioso che sommarle.

L'algoritmo di Strassen ha una moderna interpretazione nell'ambito della Geometria Algebrica e della Teoria delle Rappresentazioni. Le tecniche utilizzate hanno la loro origine nei lavori della scuola italiana sulle Varietà delle Secanti (inizio '900), si veda [1] per una trattazione sistematica dell'argomento.


Riferimenti:

[1] J. M. Landsberg: Geometry and Complexity Theory, Cambridge Studies in Advanced Mathematics 169, Cambridge University Press 2017.
[2] S. Robinson: Toward an Optimal Algorithm for Matrix Multiplication, SIAM News, 38 (9), 2005.