Il Problema delle Otto Regine

È tempo di Natale, le famiglie si riuniscono e dai cassetti vengono tirate fuori le scatole con i giochi. Giochi elettronici, di ruolo, di carte e, ovviamente, giochi da scacchiera. Fra questi ultimi, gli scacchi sono sicuramente fra quelli che hanno dato vita al maggior numero di rompicapo matematici. Uno dei più celebri è il

Problema delle Regine. Data una scacchiera $n \times n$, qual è il massimo numero di regine che possono essere poste su di essa, in modo tale che nessuna attacchi le rimanenti?

Siccome ogni regina può muoversi in orizzontale, verticale e diagonale, il problema è equivalente a quello di disporre il massimo numero di pedine sulla scacchiera, in maniera tale che non ve ne siano due sulla stessa riga, colonna o diagonale. Da ciò segue che il massimo numero di regine non può superare $n$, e non è difficile dimostrare che su ogni scacchiera di ordine almeno $4$ esiste almeno una soluzione con esattamente $n$ regine.

Molto più difficile è il problema di descrivere tutte le soluzioni o, almeno, un insieme completo di soluzioni a meno di rotazioni e riflessioni (le cosiddette "soluzioni fondamentali"). Per la scacchiera $4 \times 4$ vi è una sola soluzione fondamentale, per quella $5 \times 5$ ve ne sono due, e di nuovo solo una per quella $6 \times 6$. Il numero di soluzioni fondamentali per la scacchiera $7 \times 7$ è sei, quella classica $8 \times 8$ ne possiede dodici, quella $9 \times 9$ quarantasei e quella $10 \times 10$ novantadue.

Il numero totale di soluzioni al variare di $n$ è tabulato nella sequenza OEIS A000170, mentre quello di soluzioni fondamentali è tabulato nella sequenza OEIS A002562. Al momento, non esiste una formula chiusa per il numero di soluzioni in funzione di $n$, tuttavia sono stati pubblicati algoritmi di tipo "bit vector encoding" per produrre tutte le soluzioni [3].

Il problema originale, per la scacchiera 8x8, fu formulato da M. Bezzel nella rivista berlinese Schachzeitung nel 1848, e le $12$ soluzioni fondamentali vennero pubblicate per la prima volta da F. Nauck nella rivista di Lipsia Illustrierte Zeitung (1850). La prima dimostrazione che esse esauriscono tutte le possibilità, basata sulla teoria dei determinanti, fu data da J. W. Glaisher nel 1874. Vi è esattamente una soluzione fondamentale in cui non esistono tre regine allineate, quella indicata col numero (10) in [1].

Le 12 soluzioni fondamentali sulla scacchiera $8 \times 8$ (fonte: Wolfram MathWorld)

Per maggiori notizie sul Problema delle Otto Regine, e sui problemi correlati in cui le regine sono sostituite con altri pezzi degli scacchi, il lettore può consultare [2].

Nota computazionale. Nella pagina Wikipedia [1] si può trovare il seguente script in Pascal per determinare una soluzione al Problema delle Otto Regine:

program eightqueen1(output);
 
var i : integer; q : boolean;
    a : array[ 1 .. 8] of boolean;
    b : array[ 2 .. 16] of boolean;
    c : array[ -7 .. 7] of boolean;
    x : array[ 1 .. 8] of integer;
 
procedure try( i : integer; var q : boolean);
    var j : integer;
    begin 
    j := 0;
    repeat 
        j := j + 1; 
        q := false;
        if a[ j] and b[ i + j] and c[ i - j] then
            begin 
            x[ i    ] := j;
            a[ j    ] := false; 
            b[ i + j] := false; 
            c[ i - j] := false;
            if i < 8 then
                begin
                try( i + 1, q);
                if not q then
                    begin 
                    a[ j] := true; 
                    b[ i + j] := true; 
                    c[ i - j] := true;
                    end
                end 
            else 
                q := true
            end
    until q or (j = 8);
    end;
 
begin
for i :=  1 to  8 do a[ i] := true;
for i :=  2 to 16 do b[ i] := true;
for i := -7 to  7 do c[ i] := true;
try( 1, q);
if q then
    for i := 1 to 8 do write( x[ i]:4);
writeln
end.

Riferimenti.

[1] https://en.wikipedia.org/wiki/Eight_queens_puzzlehttps://en.wikipedia.org/wiki/Eight_queens_puzzle
[2] M. Gardner: Enigmi e giochi matematici, Vol. 4.
[3] Z. Qiu: Bit-vector encoding of $n$-queen problem. ACM SIGPLAN Notices. 37 (2) (2002), 68-70. 

Il porisma di Steiner

In geometria, il termine porisma viene spesso utilizzato per indicare una configurazione di oggetti che in generale non esiste e che tuttavia, non appena esiste, esiste in un’infinità di casi.  Uno dei porismi più famosi è quello che prende il nome dal matematico svizzero  J. Steiner (1796-1863), e che riguarda catene di circonferenze tangenti fra loro e a due circonferenze date. L’enunciato preciso è il seguente:

Porisma di Steiner. Siano $A$ e $B$ due circonferenze disgiunte nel piano, con $A$ interna a $B$. Supponiamo  che esista una catena di circonferenze $C_1, \ldots, C_n$, aventi le seguenti proprietà:

1. Ogni circonferenza $C_i$ è tangente alla precedente e alla successiva, e inoltre $C_n$ è tangente a $C_1$ (in altre parole, la catena è chiusa); 
2. Ogni $C_i$ è tangente sia ad $A$ che a $B$. 

Allora esistono infinite catene siffatte, tutte ottenibili da una fissata per mezzo di rotazioni. Inoltre, ogni circonferenza $C$, tangente sia ad $A$ che a $B$, è membro di una tale catena.

Una catena di circonferenza che verifica i punti (1) e (2) sopra è detta catena (chiusa) di Steiner. Dunque il Porisma di Steiner può essere anche enunciato dicendo che, se $A$ e $B$ ammettono una catena di Steiner formata da $n$ elementi, allora ne ammettono infinite.

Catene di Steiner (fonte Wikipedia)

Una bella dimostrazioni di questo sorprendente risultato è contenuta nel Capitolo 6 del libro di H. S. M. Coxeter [C89]. L’idea è quella di considerare una particolare inversione del piano, che trasformi le due circonferenze $A$ e $B$ in due circonferenze concentriche $A’$, $B’$. Siccome una tale inversione manda circonferenze tangenti in circonferenze tangenti, è ora sufficiente dimostrare l’enunciato per  $A’$, $B’$, nel qual caso è ovvio.

Si noti che questo argomento permette anche di dedurre che i punti di tangenza delle circonferenze della catena giacciono a loro volta su una circonferenza. Inoltre, un semplice calcolo mostra che i centri delle circonferenze della catena giacciono su un’ellisse, avente per fuochi i centri di $A$ e $B$.

Nel caso degenere in cui le circonferenze $A$, $B$ sono tangenti internamente in un punto $p$, è possibile considerare una particolare inversione che manda $p$ all’infinito, trasformando $A$ e $B$ in due rette parallele. La stessa dimostrazione di prima mostra che in tal caso esistono infinite catene di Steiner per $A$ e $B$, ciascuna delle quali formata a sua volta da un numero infinito di circonferenze (il cui raggio tende a zero man mano che esse si avvicinano a $p$). Questa situazione è trattata in dettaglio nel Capitolo 3 di [N97].

Riferimenti.

[C89] H. S. M. Coxeter: Introduction to Geometry, 2nd edition, Wiley and Sons 1989
[N97]  T. Needham: Visual Complex Analysis, Clarendon Press 1997.

Il teorema di Sylvester-Gallai

Nel 1944, il matematico ungherese T. Gallai pubblicò una dimostrazione del seguente
risultato, rispondendo in tal modo ad un quesito posto nel 1883 da J. J. Sylvester:

Teorema. Consideriamo un insieme finito di punti di $\mathbb{R}^2$ tali che una retta passante per due qualsiasi di essi ne contenga un terzo. Allora tutti i punti sono allineati.

In altre parole, dato un insieme di punti non tutti allineati nel piano reale, esiste almeno una retta che contiene esattamente due di essi. Osserviamo che il teorema sussiste anche nel piano proiettivo $\mathbb{RP}^2$, dato che una configurazione finita di punti in tale piano può essere trasformata in una configurazione nel piano euclideo senza cambiare l'insieme delle rette che li congiungono, semplicemente scegliendo come retta all'infinito una retta che non contenga nessuno dei punti.

Oggi sono note molte dimostrazioni differenti del Teorema di Sylvester-Gallai. Una discussione di quella originale di Gallai può trovarsi in [BM90], mentre nella corrispondente pagina Wikipedia ne sono riportate altre due.

La prima, dovuta a L. M. Kelly, è di carattere geometrico elementare, e utilizza un argomento per assurdo basato sull'esistenza di una coppia (retta congiungente due punti, terzo punto) tale che gli elementi della coppia abbiano distanza minima fra tutte le possibili coppie di tale tipo.

La seconda, dovuta a E. Melchior, utilizza la teoria delle dualità, considerando la configurazione di rette in $(\mathbb{RP}^2)^*$, duale della data configurazione di punti in $\mathbb{RP}^2$, e mostrando  con un delicato argomento topologico che, se tali rette non passano tutte per un punto, allora esiste almeno un punto di $(\mathbb{RP}^2)^*$ per il quale passano esattamente due di esse.

È importante notare che il teorema di Silvester-Gallai non può essere generalizzato al piano

complesso $\mathbb{C}^2$ o, equivalentemente, al piano proiettivo $\mathbb{CP}^2$. Infatti, per un ben noto risultato di geometria algebrica elementare, i 9 punti di flesso di una cubica piana liscia $C_3$ in $\mathbb{CP}^2$ (ossia, di una curva definita da un'equazione omogenea di terzo grado $F(x, \, y, \, z)=0$) hanno la proprietà che la retta passante per due qualsiasi di essi ne contiene anche un terzo. Ciò è un'immediata conseguenza del fatto che i 9 punti di flesso di $C_3$ corrispondono esattamente ai punti di 3-torsione nella legge di gruppo sulla curva (definita da "tre punti hanno somma nulla se e solo se essi sono allineati").

Tali 9 punti di flesso, insieme alle 12 rette che li congiungono,  formano la cosiddetta configurazione di Hesse, indicata anche con il simbolo $9_4 12_3$, dato che vi sono 3 punti su ogni retta e 4 rette per ogni punto. Dal teorema di Sylvester-Gallai segue che la configurazione di Hesse non può essere realizzata su $\mathbb{R}$, cioè che i 9 flessi di una cubica liscia non possono avere tutti coordinate reali.

La configurazione di Hesse (fonte Wikipedia)

Riferimenti.

[BM90] P. Borwein, W. O. J. Moser: A survey of Sylvester's problem and its  generalizations, Aequationes mathematicae 40 (1), 111-135 (1990)

L'equazione funzionale di Cauchy

Problema. Supponiamo di avere una funzione $f \colon \mathbb{R} \to \mathbb{R}$ tale che $f(x+y)=f(x)+f(y)$ per ogni $x, \, y \in \mathbb{R}$. È vero che  $f$ è una funzione lineare, ossia della forma $f(x)= kx$ per un fissato $k \in \mathbb{R}$?

L’equazione funzionale

\begin{equation} \label{eq:Cauchy}
f(x+y)=f(x)+f(y)\tag{$*$}
\end{equation} è detta equazione funzionale di Cauchy. È facile rendersi conto che, se $f \colon \mathbb{Z}  \to  \mathbb{Z}$ verifica $(*)$, allora $f$ è lineare sugli interi. Infatti si ha

\begin{equation*}
f(2)=f(1+1)=f(1)+f(1)=f(1) \cdot 2,
\end{equation*} da cui, iterando, si ottiene $f(n)=f(1) \cdot n$, cioè $f(n)=kn$ con $k=f(1)$. Una semplice variante di questo argomento mostra che, se $f \colon \mathbb{Q}  \to \mathbb{Q}$ soddisfa l'equazione funzionale di Cauchy, allora $f$ è lineare sui razionali.

Quando invece si considerano funzioni $f  \colon \mathbb{R}  \to \mathbb{R}$, la natura delle soluzioni cambia radicalmente. Nel 1821, A. L. Cauchy dimostrò, nel suo seminale Cours d’Analyse, che ogni funzione reale che soddisfi $(*)$ e che sia anche continua è necessariamente lineare. Successivamente, nel 1875, G. Darboux provò che, per garantire la linearità, è sufficiente la continuità di $f$ in un solo punto [D75], e cinque anni dopo fece vedere che basta supporre che esista un intervallo nel quale $f$ sia monotona [D80].

La questione venne completamente risolta nel 1905 da G. Hamel [H05], dal cui lavoro risultò che la generica soluzione dell’equazione funzionale di Cauchy su $\mathbb{R}$ è una funzione patologica, cioè non lineare. Il procedimento di Hamel per ricavare le sue soluzioni patologiche era non costruttivo, e faceva uso di quella che oggi viene chiamata una base di Hamel di $\mathbb{R}$ come $\mathbb{Q}$-spazio vettoriale, la cui esistenza è equivalente all’assioma di scelta.

G. Hamel (fonte: Berliner Mathematische Gesellschaft)

Per quanto detto sopra, ogni soluzione patologica dell’equazione funzionale di Cauchy è necessariamente discontinua in ogni punto e non-monotona in ogni intervallo. Si può anche far vedere che ogni tale funzione è non-misurabile secondo Lebesgue. Per maggiori particolari sull’equazione funzionale di Cauchy e sulle proprietà delle sue soluzioni patologiche, il lettore può consultare [MSE423492].


Riferimenti.

[D75] G. Darboux: Sur la composition des forces en statique, Bulletin des Sciences Mathématiques et Astronomiques 9 (1875), 281-299.
[D80] G. Darboux: Sur le théorème fondamental de la Géométrie projective, Mathematische Annalen 17 (1880), 55-61.
[H05] G. Hamel: Eine Basis aller Zahlen und die unstetigen Lösungen der Funktionalgleichung $f(x+y)=f(x)+f(y)$, Mathematische Annalen 60 (1905), 459-462.
[MSE423492] https://math.stackexchange.com/questions/423492/overview-of-basic-facts-about-cauchy-functional-equation

Il progetto Polymath

La visione usuale che il profano ha del matematico è quella di un genio solitario che lavora duramente, e possibilmente nell’isolamento più totale, per trovare la soluzione a qualche problema enormemente difficile.

Sebbene ciò sia ancora vero in alcuni casi (si pensi alla storia della soluzione dell’Ultimo Problema di Fermat da parte di A. Wiles), in realtà i matematici moderni tendono sempre più spesso a collaborare fra loro, in modo da beneficiare ciascuno delle competenze e abilità degli altri. Tuttavia, il numero di persone che lavorano insieme ad un singolo progetto è in genere piuttosto basso, tre-quattro al massimo, nulla in confronto alle decine o addirittura centinaia di persone che possono firmare un lavoro di Medicina o di Fisica delle particelle.

Un’eccezione a questa regola è fornita dal Progetto Polymath, lanciato nel 2009 (quasi come esperimento sociale) dal matematico britannico T. Gowers, Medaglia Fields nel 1998, in un famoso post sul suo blog, dal titolo “Is massively collaborative mathematics possible?"

T. Gowers (fonte: Wikipedia)

Gowers si domandava se fosse possibile attaccare problemi matematici irrisolti per mezzo di uno sforzo collaborativo da attuare su una piattaforma virtuale, ed arrivare in tal modo ad una soluzione che fosse la sintesi del lavoro di un grande numero di persone.

Le 225 risposte al post segnarono la nascita di Polymath, che fino ad oggi ha dato vita a 16 progetti. Fra questi, i seguenti si sono rivelati particolarmente fruttuosi:

• Polymath 1, avente lo scopo di trovare una formula combinatoria per la densità nel teorema di Hales-Jewett. Il progetto ha visto la collaborazione di 40 persone, che hanno pubblicato due lavori sotto lo pseudonimo collettivo D.H.J. Polymath. 
• Polymath 5, avente lo scopo di risolvere il problema della discrepanza di Erdős. Il progetto non raggiunse il suo scopo; tuttavia, poco tempo dopo, T. Tao trovò una soluzione, basandosi anche su alcuni risultati parziali di Polymath 5. 
• Polymath 8, avente lo scopo di migliorare il bound di Y. Zhang sui primi a distanza limitata. Il progetto fu un successo, riuscendo ad abbassare il valore iniziale di circa 6 milioni ottenuto da Zhang fino a 4680. Successivamente, una ramificazione del progetto (Polymath8b) utilizzò delle nuove tecniche introdotte da J. Maynard per arrivare fino a 246. Questi risultati sono stati pubblicati in due articoli, il primo in Algebra e Number Theory e il secondo in  Research in Matematical Sciences, ancora una volta sotto lo pseudonimo D.H.J. Polymath. 

Nel 2016 è anche nato uno spin-off di Polymath chiamato Crowdmath, rivolto agli studenti delle scuole superiori e dei primi anni di università.

Curve che riempiono il quadrato

Alla fine dell'800, il sorprendente risultato di G. Cantor, secondo cui l'intervallo unitario $I=[0, \, 1]$
può essere messo in corrispondenza biunivoca con il quadrato $Q=I \times I$, aveva spinto i matematici a domandarsi se fosse possibile realizzare una corrispondenza biettiva e continua fra $I$ e $Q$.

La risposta risultò essere negativa: in termini moderni, siccome $I$ è uno spazio compatto e $Q$ è uno spazio di Hausdorff, per risultati standard di topologia generale una tale mappa dovrebbe essere
un omeomorfismo, il che è assurdo dato che $I$ può essere disconnesso togliendo un punto, mentre $Q$ non ha questa proprietà. 

Tuttavia, nel 1890, il matematico italiano G. Peano dimostrò il seguente sorprendente 

risultato [Pe890]:

Teorema. Esiste un'applicazione suriettiva e continua $\alpha \colon  I \to Q$.

In altre parole, Peano aveva scoperto l'esistenza di una curva continua che riempie tutto il quadrato, e che oggi viene appunto detta curva di Peano. Si tratta di un oggetto inaspettato, data l'idea intuitiva che in genere si possiede di "curva". Si noti che, per quanto osservato prima, la curva di Peano deve necessariamente auto-intersecarsi, dato che se $\alpha$ fosse iniettiva allora sarebbe un omeomorfismo. 

G. Peano (fonte Wikipedia)

La costruzione di Peano è basata su un procedimento di espansione ternaria dei numeri reali; leggendo l'articolo originale, però, ci si rende conto che l'autore aveva ben presente la costruzione della sua curva come limite uniforme di curve lineari a tratti. Questa idea venne esplicitata l'anno dopo da D. Hilbert, il cui lavoro [Hilb891] contiene il disegno delle successive iterazioni che convergono ad una curva che riempie il quadrato, una variante della curva di Peano oggi nota come curva di Hilbert.

Le prime sei iterazioni nella costruzione della curva di Hilbert (fonte Wikipedia).

Lievi modifiche delle costruzioni di Peano e Hilbert permettono di costruire curve continue che riempiono tutto l'ipercubo $n$-dimensionale $I^n$, ed anche curve (senza estremi) che riempiono lo spazio euclideo $n$-dimensionale $\mathbb{R}^n$. Per tali motivi si parla talvolta di  space-filling curves.

Oggi sono noti molti esempi di curve siffatte (curva di Sierpinski, curva di Moore, curva di Lebesgue). Sono tutti esempi di curve frattali, quindi non regolari. Infatti, dal lemma di Sard segue  che non può esistere una space-filling curve ovunque differenziabile. Si noti tuttavia che, mentre le curve di Peano e Hilbert non sono differenziabili in alcun punto, nell'esempio di Lebesgue si ha differenziabilità quasi ovunque.

L'esistenza di curve che riempiono il quadrato fa sorgere in modo naturale la seguente domanda:
è possibile caratterizzare gli spazi topologici che sono immagine continua dell'intervallo unitario $I$?
La risposta è affermativa, ed è fornita dal celebre

Teorema di Hahn–Mazurkiewicz. Uno spazio topologico $X$ è immagine continua di $I$ se e solo se $X$ compatto, connesso, localmente connesso e $2$-numerabile.

Infine, è anche possibile costruire curve continue e iniettive (ma non suriettive) $\alpha \colon I \to  Q$ la cui immagine ha area positiva: sono le cosiddette curve di Osgood.

Per maggiori dettagli sull'argomento di questo post, il lettore può consultare la monografia dedicata [Sa94].

Riferimenti:

[Pe890] G. Peano: Sur une courbe, qui remplit toute une aire plane,
Mathematische Annalen 36 (1) (1890), 157–160, doi:10.1007/BF01199438
[Hilb891] D. Hilbert: Ueber die stetige Abbildung einer Line auf ein Flächenstück,
Mathematische Annalen 38 (3) (1891): 459–460, doi:10.1007/BF01199431
[Sa94] H. Sagan: Space-Filling Curves, Universitext, Springer-Verlag (1994).

Formule che calcolano i numeri primi

Da qualche giorno circola sui social network la notizia che un tredicenne di Reggio Calabria avrebbe addirittura "scoperto una formula che potrebbe risolvere il grattacapo che impegna i matematici da più o meno tremila anni", ovvero "una formula in grado di calcolare tutti i numeri primi in successione". Non c'è bisogno di dirlo, tale scoperta "potrebbe essere usata per rinforzare le password dei nostri account virtuali, quelle bancarie per esempio". O anche per decrittarle, si intende.

L'articolo sul giovane prodigio non è stato postato su una rivista specializzata, ma sul sito del noto programma televisivo "Le Iene", non proprio il massimo in fatto di autorevolezza quando si parla di scienza (emblematico il caso del servizio che creò allarmismi ingiustificati sull'esperimento SOX nel Gran Sasso). Per quanto riguardo la "formula", essa "non può essere divulgata" in quanto il giovanotto teme che "qualcuno possa appropriarsene e prendersi i meriti di quella che potrebbe essere una scoperta grandiosa. Ed è infatti questo il motivo che ha spinto la mamma di Rubens a contattare la redazione de le Iene". E ti pareva.

Come qualcuno possa appropriarsi di qualcosa che viene divulgato pubblicamente dal suo scopritore non è in effetti molto chiaro. Nell'attesa che il mistero venga svelato, e volendo magari parlare realmente di Matematica invece di fare solo sensazionalismo, vale la pena ricordare che "formule che calcolano i primi" ne esistono già parecchie, vedi [2] e [3]. Il (grosso) problema è che non sono molto efficienti, per cui nella pratica è più conveniente utilizzare metodi classici, come il crivello di Eratostene o qualche sua variante.

Non è in realtà difficile dimostrare che non esiste nessun polinomio $P(n)$ non costante a coefficienti interi in una variabile $n$ che assuma valori primi per ogni intero positivo $n$ (o per tutti gli $n$ meno un numero finito di essi). Infatti, se $P(1)=p$ con $p$ primo, allora $P(1)$ è congruo a zero (mod $p$). Da qui segue facilmente che  $P(1+kp)$ è congruo a zero (mod $p$) per ogni $k \in \mathbb{Z}$. Dunque $P(1+kp)$ è primo se e solo se è uguale a $p$, e un polinomio che assume infinite volte il valore $p$ è necessariamente costante.

Un esempio famoso (legato in modo non banale alle spirali di Ulam e ai numeri di Heegner) è il polinomio $n^2+n+41$, che produce numeri primi per ogni $n \leq 39$. Per $n=40$ il valore assunto è invece $1681=41 \times 41$.

Siccome l'insieme dei primi è computazionalmente numerabile, segue dal Teorema di Matiyasevich che esso può essere descritto per mezzo di un sistema di equazioni diofantee. Jones e i suoi collaboratori hanno determinato nel 1976 un sistema esplicito di tali equazioni, il che ha permesso di scrivere un polinomio in 26 variabili, a coefficienti interi, tale che l'insieme dei suoi valori interi positivi coincida con l'insieme dei numeri primi [3]. Per risultati generali della teoria è possibile trovare un polinomio di questo tipo con solo $10$ variabili, ma in tal caso il grado è enorme (dell'ordine di $10^{45}$).

Un altro esempio di formula che produce solo valori primi è $$f(n) = \lfloor A^{3^n} \rfloor,$$ dove $A=1.3063778838630806904686144926 \ldots$  è la cosiddetta costante di Mills (il valore di A è calcolato supponendo vera l'ipotesi di Riemann). Non si sa al momento se $A$ sia o meno irrazionale. I numeri prodotti dalla formula sopra sono detti "primi di Mills", e sono tabulati nella successione OEIS A051254: $$2, 11, 1361, 2521008887, 16022236204009818131831320183, \ldots$$ La formula di Mills, come altre "formule che calcolano i primi", per quanto interessante dal punto di vista teorico ha scarso valore pratico, dato che non vi è modo di calcolare esplicitamente la costante $A$ senza già conoscere a priori la successione dei primi.

Riferimenti:

[1] https://en.wikipedia.org/wiki/Formula_for_primes
[2] http://mathworld.wolfram.com/PrimeFormulas.html
[3] Jones, James P.; Sato, Daihachiro; Wada, Hideo; Wiens, Douglas: Diophantine representation of the set of prime numbers, American Mathematical Monthly 83 (6), 449–464.

La classificazione dei gruppi semplici finiti

Es wäre von dem grössten Interesse, wenn eine Uebersicht des sämmtlichen einfachen Gruppen von einer endlichen Zahl von Operationen gegeben werden könnte. 
(Sarebbe del massimo interesse, se fosse possibile dare una classificazione di tutti i gruppi semplici di ordine finito). [4, p. 1]


Un gruppo è detto semplice se non possiede sottogruppi normali non banali. Per il teorema di Jordan–Hölder sulle serie di composizione, i gruppi semplici finiti possono essere visti come "blocchi elementari" che permettono di costruire per estensioni successive tutti i gruppi finiti, pertanto la loro classificazione costituisce un problema centrale nella teoria.

Un esempio banale di gruppo semplice finito è dato dai gruppi ciclici $\mathbb{Z}_p$ di ordine primo. Un esempio più sofisticato è fornito dai gruppi alterni $A_n$, con $n \geq 5$; di fatto, la semplicità di $A_n$ è alla base della moderna dimostrazione del teorema di Abel-Ruffini sulla non-risolubilità per radicali della generica equazione algebrica di grado almeno $5$.

Il problema (enormemente difficile) della classificazione dei gruppi semplici finiti è anche noto come Programma di Gorenstein, per via dei due fondamentali lavori scritti da D. Gorenstein negli anni 1982-83 che risolvevano quasi completamente la questione, lasciando aperti alcuni casi (i cosiddetti "quasithin groups") che vennero trattati successivamente da Aschbacher e Smith (2004, 2011). Il risultato finale è il seguente, vedi [1]:

Teorema. Se $G$ è un gruppo semplice finito, allora siamo in uno dei seguenti casi:

(1) $G$ è isomorfo a $\mathbb{Z}_p$ per un dato primo $p$;
(2) $G$ è isomorfo ad $A_n$ per un dato $n \geq 5$;
(3) $G$ è un gruppo finito di tipo Lie;
(4) $G$ è isomorfo ad uno dei cosiddetti $27$ gruppi sporadici.

Nei casi (1), (2), (3) si hanno famiglie infinite di gruppi; invece, ogni gruppo sporadico in (4) è unico a meno di isomorfismi.

Il più piccolo gruppo sporadico, di ordine 7920, venne scoperto da E. L. Mathieu nel 1861, ed in suo onore è oggi indicato con M11. Il gruppo sporadico più grande è invece il cosiddetto "Fischer-Griess monster" M, costruito (a mano!) nel R. Griess nel 1982 e il cui ordine è pari a $$ 808017424794512875886459904961710757005754368000000000.$$ Come stimolante lettura divulgativa sulla storia dei gruppi sporadici e dei loro scopritori il lettore può consultare [2].

La dimostrazione completa del Teorema di Classificazione dei gruppi semplici finiti richiede diverse migliaia di pagine, ed è basata sui numerosi articoli scritti nel corso di circa 100 anni da matematici come Mathieu, Janko, Conway, Fisher, Higma, Suzuki, Feit, Thompson, Griess, Aschbacher, Gorenstein, etc.

A partire dal 1985, gli sforzi dei teorici dei gruppi sono concentrati sulla cosiddetta "Dimostrazione di seconda generazione", che si propone di semplificare gli argomenti, eliminando ogni ridondanza ed usando tecniche più moderne e generali che permettano di trattare vari casi contemporaneamente.

Alcune parti della dimostrazione sono state anche verificate al computer tramite il linguaggio Coq; un esempio è il fondamentale e difficile teorema di Feit-Thompson ("Ogni gruppo finito di ordine dispari è risolubile"), verificato da G. Gonthier e i suoi collaboratori nel 2013, vedi [3].

Riferimenti:

[1] https://en.wikipedia.org/wiki/List_of_finite_simple_groups
[2] M. Ronan: Il mostro e la simmetria, Cortina Editore 2007.
[3] G. Gonthier et al.: A Machine-Checked Proof of the Odd Order Theorem, Lecture Notes in Computer Sciences 7998 (2013), https://doi.org/10.1007/978-3-642-39634-2_14.
[4] O Holder: Die einfachen Gruppen in ersten und Zweiten Hundert der Ordnungszahlen, Mathematische Annalen 40 (1892), 55-88.

"A Doubter's Almanac" di Ethan Canin

Per una curiosa coincidenza, nei torridi giorni di agosto in cui tutte le reti sociali celebravano la meritata medaglia Fields di Alessio Figalli, ero intento a leggere questo lo strano romanzo "A doubter's almanac'' di Ethan Canin, scoperto grazie ad una recensione sui Notices AMS.

Il protagonista è Milo Andret, un giovane scontroso ed introverso che trascorre una solitaria infanzia nei boschi del Michigan settentrionale, e che è dotato di un singolare talento matematico che lo porta ad essere ammesso al prestigioso programma dottorale dell'Università di Berkley.

Nella sua tesi di dottorato Andret risolve l'immaginaria Congettura di Malosz, un difficilissimo problema topologico che eludeva gli sforzi dei matematici da decenni, e grazie a questo exploit ottiene una cattedra a Princeton, la medaglia Fields e la fama mondiale.

Spinto da un'ambizione e un egoismo pari solo al suo talento, Andret si rimette subito all'opera attaccando la (anch'essa immaginaria) Congettura di Abendroth, un problema di Topologia Algebrica ritenuto difficile quanto l'Ipotesi di Riemann. Lavorando senza sosta giorno e notte, e sostenuto solo da forti dosi di bourbon e sesso, Milo arriva vicinissimo alla meta, ma viene battuto in extremis da un giovane matematico di Palo Alto, che pubblica una soluzione prima di lui.

Questa débâcle segna di fatto la fine della carriera di Andret, che non sarà mai più matematicamente produttivo, e finirà per essere consumato dalle sue ossessioni, circondato da una famiglia disfunzionale i cui membri hanno ereditato sia il suo genio che la sua instabilità mentale.

L'autore del romanzo non è un matematico, ma ha ricevuto un dottorato in medicina ad Harvard, e la cosa si vede da alcune piccole imprecisioni tecniche che tuttavia non guastano la godibilità e l'eleganza della scrittura.

Più che la matematica in sè, comunque, il tema del libro è il rapporto fra genio e auto-distruzione, ambizione e ossessione, amore e tormento. Nulla di veramente originale, in verità, ma forse a qualcuno sarà capitato almeno una volta di pensare "Sarei disposto a distruggere la mia vita e quella di chi mi ama, in cambio della medaglia Fields?"

Il problema di Didone

Devenere locos ubi nunc cernis
ingentia moenia arcemque novae Karthaginis surgentem,
mercatique solum Byrsam, de nomine facti,
quantum possent circumdare taurino tergo.

(Virgilio, Eneide, Libro I)

La leggenda riportata da Virgilio narra di Didone, la regina dei Fenici che, fuggita in Africa dopo l'assassinio del marito ad opera del fratello, chiese al re locale Yarba di concederle una quantità di terra che potesse essere circondata dalla pelle di un toro. Il re accettò, parendogli una richiesta molto modesta, al che Didone fece tagliare la pelle in striscioline sottili, che unì insieme per formare una lunga corda con la quale circondò ciò che sarebbe diventato il futuro insediamento di Cartagine.

Nell'attuare il suo piano, Didone si trovò davanti a ciò che può essere considerato il primo problema isoperimetrico della storia, che per questo motivo è anche noto come

Problema di Didone. Determinare la figura geometrica piana che massimizza l'area, a parità di perimetro.

I geometri antichi intuirono che la risposta corretta è "il cerchio", ma le prime dimostrazioni rigorose vennero trovate solo nella seconda metà dell'800.

I primi tentativi di approcciare il problema risalgono al tempo dei greci. Zenodoro (150 a.C.) dimostrò che, a parità di perimetro, se esiste un $n$-agono che massimizza l'area questo deve essere regolare, e che dati due poligoni regolari con lo stesso perimetro quello con più lati ha l'area maggiore. Inoltre, metodi di esaustione simili a quelli di Archimede facevano vedere che il cerchio ha un area maggiore di ogni poligono regolare con lo stesso perimetro.

Questi risultati non risolvono il problema di Didone, in quanto non è affatto chiaro a priori che una figura di area massima esista, anche se per lungo tempo questo sottile aspetto della questione non venne considerato.

Per oltre 1900 anni non vi furono ulteriori progressi, finché verso il 1750 Eulero (e poi Lagrange) approcciarono analiticamente il problema per mezzo di quelle che oggi chiamiamo "equazioni di Eulero-Lagrange", che costituiscono la base del moderno Calcolo delle Variazioni.

Il metodo analitico forniva (correttamente) l'equazione di una circonferenza come bordo della figura massimizzante l'area; tuttavia, come rilevato da Weierstrass, esso lasciava ancora aperta la questione dell'esistenza della soluzione.

Il passo finale venne compiuto da J. Steiner: grazie ad un ingegnoso metodo geometrico che oggi è chiamato in suo onore simmetrizzazione di Steiner, egli dimostrò che è possibile trasformare una regione chiusa $D$ di $\mathbb{R}^2$, con bordo regolare a tratti, in modo che la sua area rimanga invariata e il perimetro decresca.

Simmetrizzazione di Steiner

Si può far vedere che, applicando una successione di simmetrizzazioni rispetto ad opportune rette, la successione di figure che si ottiene converge ad un cerchio, avente la stessa area di $D$, rispetto alla metrica di Hausdorff. Come osservato da Edler e Steiner, questo è sufficiente a dimostrare che ogni dominio del piano con lo stesso perimetro del cerchio ha area minore di esso, completando la soluzione del problema di Didone nel piano.

L'analogo problema in dimensione superiore ("determinare il dominio di $\mathbb{R}^n$ di massimo volume a parità di area della superficie") ha ancora per soluzione la palla $n$-dimensionale; tuttavia, la dimostrazione è molto più delicata che nel piano, e si basa su alcune fondamentali diseguaglianze scoperte da Brunn, Minkowski e Lyusternik.

Lo studio del problema isoperimetrico in dimensione superiore ha motivato le ricerche della scuola italiana riguardo la definizione di "area" nel caso di domini non lisci, e in particolare i lavori (oggi considerati classici) di Caccioppoli e De Giorgi sull'argomento.

Per maggiori dettagli sull'argomento di questo post, il lettore può consultare [Ban17].

Riferimenti:

[Ban17] C. Bandle: Dido's problem and its impact in modern mathematics, Notices AMS 64 (Volume 9), Ottobre 2017.

Varietà lineari a tratti: Hauptvermutung

Una varietà topologica $M$ si dice lineare a tratti (o PL = "piecewise-linear") se esiste su di essa un atlante tale che le funzioni di transizione siano funzioni lineari a tratti. Si tratta di una proprietà lievemente più forte dell'esistenza di una triangolazione.

La categoria PL delle varietà lineari a tratti sta quindi in mezzo fra quella TOP delle varietà topologiche e quella DIFF delle varietà differenziabili. È importante notare che le funzioni lineari a tratti sono di classe $C^0$ ma non $C^1$, dato che è ben noto che la categoria delle varietà $C^1$ è equivalente a DIFF (cioè, che ogni atlante di classe $C^1$ è equivalente ad uno liscio).

Inoltre, le inclusioni DIFF $\subset$ PL $\subset$ TOP sono entrambe strette.

Infatti, ricordiamo innanzitutto che ogni varietà differenziabile ammette una struttura PL (per via di un teorema di Whitehead [W40], che afferma che ogni varietà liscia è triangolabile), ma non vale il viceversa. In altre parole, vi sono varietà PL che non ammettono nessun atlante di classe $C^{\infty}$ (cioè, che non sono "allisciabili"). Il primo esempio di questo tipo venne costruito da M. Kervaire in [K60]: si tratta di una varietà PL di dimensione 10, ottenuta con una tecnica di topologia differenziale detta "plumbing" a partire dai fibrati tangenti di due 5-sfere; in suo onore, varietà di questo tipo vengono oggi chiamate varietà di Kervaire.

Inoltre, esistono varietà topologiche che non possiedono nessuna strutture PL, ed altre che ne possiedono infinite.

Storicamente, il problema della triangolabilità delle varietà topologiche è noto come "Hauptvermutung". La triangolabilità delle varietà di dimensione 2 è stata dimostrata da T. Radó nel 1920, e quella delle varietà di dimensione 3 da E. Moise nel 1950. Quindi i primi controesempi possono presentarsi solo da dimensione 4 in poi.

Oggi si sa che, per una varietà topologica $M$, l'ostruzione a possedere una struttura PL è data dalla  classe di Kirby-Siebermann $$k(M) \in H^4(M,  \, \mathbb{Z}_2).$$ Se $\dim(M) \geq 5$ e $M$ è compatta, allora esiste una struttura PL su $M$ se e solo se $k(M)=0,$ e in questo caso il numero di strutture PL differenti è parametrizzato da $H^3(M,  \, \mathbb{Z}_2)$, in particolare esse sono in numero al più finito.

In dimensione $4$ le cose sono radicalmente differenti: in tal caso la categoria PL coincide con la categoria DIFF, ed esistono $4$-varietà topologiche compatte e semplicemente connesse che possiedono infinite strutture PL distinte (S. Donaldson).

Inoltre, M. Friedman trovò nel 1982 l'esempio noto come varietà E8, una 4-varietà topologica compatta e semplicemente connessa che non solo non ammette nessuna struttura PL, ma addirittura non è neanche omeomorfa ad un complesso simpliciale. Esempi con la stessa proprietà, in ogni dimensione maggiore o uguale a $5$, sono stati costruiti più recentemente da C. Manolescu  in [Ma16].


Riferimenti:

[K60] M. Kervaire: A manifold which does not admit any differentiable structure, Comm. Math. Helv. 34 (1960), 257–270.

[Ma16 ] C. Manolescu: $\mathrm{Pin}(2)$-equivariant Seiberg–Witten Floer homology and the Triangulation Conjecture, Journal of the American Mathematical Society 29 (2016), 147 -176.

[W40] J. H. C. Whitehead: On $C^1$-Complexes,  Annals of Mathematics. Second Series. 41 (4) (1940), 809–824.

Apologia di un matematico

A mathematician, like a painter or a poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas
(G. H. Hardy)

G. H. Hardy (1877-1947) fu uno dei più importanti matematici inglesi del '900, attivo soprattutto nel campo della Teoria Analitica dei Numeri. Le sue collaborazioni con J. Littlewood (1885-1977) e S. Ramanujan (1887-1920) portarono a numerosi fondamentali risultati, fra cui il celebre Metodo del Cerchio, che permise di utilizzare gli strumenti dell'Analisi Complessa e dell'Analisi Armonica allo studio del comportamento asintotico della funzione di partizione degli interi.

Hardy è considerato colui che "portò il rigore nella matematica britannica", ed il suo sodalizio scientifico con Littlewood era talmente famoso che H. Bohr arrivò ad affermare "oggi vi sono solo tre grandi matematici in Inghilterra: Hardy, Littlewood e Hardy-Littlewood".

Nel 1940, in quella che doveva essere l'ultima parte della sua vita, Hardy pubblicò A Mathematician's Apology, un breve saggio che oggi è considerato un classico dell'autobiografia scientifica.

"Apologia" qui va inteso non come "richiesta di perdono", ma piuttosto nel senso che Platone dà all'Apologia di Socrate: una spiegazione delle proprie azioni, e del perché si sia agito secondo coscienza. Al contrario di Socrate, tuttavia, Hardy era un ateo convinto, dunque le sue giustificazioni non sono rivolte a Dio, ma solo agli uomini.

Vi furono almeno due elementi che spinsero il matematico inglese a scrivere l'Apologia. In primo luogo, all'età di 62 anni e dopo un attacco di cuore, Hardy sentiva di avere perso la propria vena creativa (nel corso di tutta la vita affermò che la ricerca matematica era un'attività per gente giovane) e infatti, nella prefazione alla ristampa del 1967, C. P. Snow definisce l'opera come "a passionate lament for creative powers that used to be and that will never come again". In secondo luogo, lo scoppio della Seconda Guerra Mondiale, e gli orrori che ne derivarono, spinsero Hardy (che fu sempre un pacifista convinto) a ribadire che lo scopo dei matematici deve essere quello di ricercare la conoscenza come fine a se stessa, e non di applicarla agli strumenti di morte dell'industria bellica.

Tutta l'Apologia è pervasa dal senso del Bello, dato che Hardy considerava la matematica una forma d'arte al pari della musica, della pittura o della scultura: addirittura, per convincere il lettore di questo fatto, ad un certo punto include la dimostrazione data da Euclide dell'infinità dei numeri primi, e quella dell'irrazionalità di $\sqrt{2}$. Due esempi "old but gold", definiti "un banco di prova: se il lettore è incapace di apprezzarli, è improbabile che sappia apprezzare qualcosa della Matematica".

Un capitolo importante dell'Apologia è la descrizione del rapporto dell'autore con il genio autodidatta Ramanujan (che meriterebbe un post a parte): Hardy, persona fredda e distaccata, definito da Littlewood "un omosessuale non praticante", lo chiama "l'unico incidente romantico della mia vita".

Alcune delle affermazioni fatte da Hardy possono apparire ingenue col senno di poi: ad esempio, quella che non ci possano essere contributi importanti dati alla Matematica da gente oltre i 50 anni (adesso che la materia non è più un'occupazione d'élite, non è raro trovare importanti teoremi dimostrati da matematici sessantenni o anche più anziani) e soprattutto quella che la Teoria dei Numeri, la regina della Matematica secondo Gauss, non abbia applicazioni pratiche: per ironia della sorte, oggi la Teoria dei Numeri è fondamentale per l'industria militare e la cybersecurity, a causa dei suoi profondi legami con la Teoria dei Codici e la Crittografia.

Idiosincrasie e affermazioni datate a parte, l'Apologia di un Matematico è comunque un documento sincero e commovente, che rivela il grande amore dell'autore per il suo lavoro, e anche la sua umiltà di fondo, che traspare in una delle frasi conclusive dell'opera:

"Ancor oggi nei momenti di depressione, quando mi trovo a dover ascoltare gente pedante e presuntuosa, mi dico: Beh, io ho fatto qualcosa che voi non sareste mai stati capaci di fare: ho collaborato con Littlewood e Ramanujan, su un piano quasi di parità".

G. H. Hardy (fonte Wikipedia)

Il teorema di invarianza del dominio

Se $m$ ed $n$ sono due interi positivi, allora non è difficile dimostrare che $\mathbb{R}^m$ e $\mathbb{R}^n$ sono diffeomorfi se e solo se $m=n$. Infatti, un diffeomorfismo induce un isomorfismo lineare fra gli spazi tangenti, e due spazi vettoriali di dimensione finita sono isomorfi se e solo se hanno la stessa dimensione.

La questione diventa molto più sottile quando si passa dalla categoria differenziale a quella topologica. Chiaramente, $\mathbb{R}$ non è omeomorfo a $\mathbb{R}^n$ se $n>1$, per il semplice fatto che un punto sconnette $\mathbb{R}$ ma non $\mathbb{R}^n$; ma cosa si può dire nel caso generale?

Non si può sperare di adattare l'argomento precedente utilizzando sottospazi lineari di dimensione maggiore di zero. Infatti, è senz'altro vero (ad esempio) che una retta sconnette $\mathbb{R}^2$ ma non $\mathbb{R}^n$ con $n>2$; tuttavia, l'immagine di una retta tramite un'applicazione di classe $C^0$ ma non $C^1$ può essere un oggetto ben diverso da una retta, addirittura una curva di tipo Peano che riempie tutto lo spazio. Di fatto, la presenza di tali applicazioni continue "patologiche" è l'ostacolo essenziale ad una trattazione "elementare" del problema.

La questione venne risolta dal matematico olandese L.E.J. Brouwer, che, nel 1912, pubblicò [1] la prima dimostrazione completa di quello è oggi conosciuto come

Teorema di invarianza del dominio. Gli spazi topologici $\mathbb{R}^m$ e $\mathbb{R}^n$ sono omeomorfi se e solo se $m=n$.

La dimostrazione di Brouwer fa uso del teorema di punto fisso che oggi porta il suo nome; invece, nei moderni libri di testo (vedi ad esempio [2, Theorem 2.26]), si trova in genere la seguente dimostrazione che fa uso dell'omologia singolare.

Dimostrazione. Se $\mathbb{R}^m$ e $\mathbb{R}^n$ sono omeomorfi, allora lo stesso vale per gli spazi $\mathbb{R}^m$ meno un punto e $\mathbb{R}^n$ meno un punto, che si retraggono rispettivamente su $S^{m-1}$ e $S^{n-1}.$ Siccome la sfera $S^k$ ha omologia non banale solo in gradi $0$ e $k$, e i gruppi di omologia sono invarianti omotopici, segue $m-1=n-1$, cioè $m=n$.

$\square$

Si possono dare dimostrazioni analoghe usando invarianti topologici, diversi dall'omologia, che distinguano sfere di dimensioni differenti: ad esempio la coomologia (il cui comportamento sulle sfere, via dualità di Poincaré, è analogo a quello dell'omologia) o i gruppi di omotopia superiore (per i quali $\pi_i(S^k)=0$ se $i <k$, mentre $\pi_k(S^k)=\mathbb{Z}$).

A volte, in letteratura, con Teorema di Invarianza del Dominio si indica il seguente risultato, da cui quello enunciato sopra scaturisce come semplice conseguenza (vedi [3]):

Teorema. Se $U$ è un aperto non vuoto di $\mathbb{R}^n$ e $f \colon U \to \mathbb{R}^n$ è una mappa continua e iniettiva, allora $V=f(U)$ è aperto e la restrizione $f \colon U \to V$ è un omeomorfismo.

Dal punto di vista storico, questa è la versione da cui il risultato prende il suo nome, dato che, classicamente, il termine "dominio" indicava un aperto connesso di $\mathbb{R}^n$. Una dimostrazione, basata su tecniche omologiche standard, può essere trovata in [2, Theorem 2B.3].

Riferimenti:

[1] L. E. J. Brouwer: Beweis der Invarianz des n-dimensionalen Gebiets, Mathematische Annalen 71 (1912), p. 305–315; vedi anche Mathematische Annalen 72 (1912), p. 55–56.
[2] A. Hatcher: Algebraic Topology, Cambridge University Press (2009).
[3] https://en.wikipedia.org/wiki/Invariance_of_domain

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.

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.

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.

Il gioco del 15

Tutti noi da bambini abbiamo giocato a quello che viene comunemente chiamato il gioco del 15. Si tratta di una cornice di legno o plastica di forma quadrata, nella quale vi sono $15$ blocchi quadrati uguali (numerati da $1$ a $15$) che possono scorrere in alto, in basso, a destra e a sinistra utilizzando lo spazio fornito dal quadrato mancante. Lo scopo del gioco è partire da una configurazione in cui i blocchi sono disordinati e arrivare alla configurazione di partenza in cui essi sono numerati consecutivamente e lo spazio vuoto è in basso a destra.

Le origini del rompicapo non sono completamente chiare. Sebbene l’enigmista Sam Loyd (1841-1911) ne reclamò spesso la paternità, sembra che sia stato in realtà inventato da un certo Noyes Palmer Chapman a New York nel 1874. Esso divenne estremamente popolare in America ed Europa a partire dal 1880.

Nel 1889 Loyd offrì un premio di 1000 dollari a chiunque fosse stato in grado di risolvere la configurazione in cui tutti i numeri sono al loro posto, tranne il $14$ e il $15$ che sono scambiati fra loro.

In realtà Loyd era sicuro di non dover sborsare nulla, dato che nel 1879 Johnson e Story avevano completato l’analisi matematica del gioco, scoprendo che un invariante completo che distingue le configurazioni ammissibili da quelle non ammissibili è costituito dalla parità della corrispondente permutazione e dalla taxicab distance (numero di righe più numero di colonne) del quadrato vuoto dal quadrato in basso a destra. Questo segue dal fatto che ogni mossa effettuata cambia contemporaneamente sia la parità della configurazione che la taxicab distance.

Di conseguenza, se lo spazio vuoto si trova in basso a destra, una configurazione è ammissibile se e solo se essa corrisponde ad una permutazione pari di $\{1, \ldots,15\}$. In particolare, la configurazione proposta da Loyd non è ammissibile, dato che corrisponde alla trasposizione $(14 \; 15)$, che è una permutazione dispari. Questo è un esempio tipico in cui un semplice controllo di parità permette di risolvere elegantemente un problema che sembra a prima vista intrattabile senza l'uso della forza bruta (enumerazione di tutte le configurazioni).

La configurazione impossibile di Sam Loyd

Esistono anche versioni del rompicapo con più di $15$ tasselli, e in generale ha senso chiedersi quale sia il massimo numero di mosse necessarie per risolvere una configurazione nel caso con $n^2-1$ tasselli. Al crescere di n questo è un problema NP-difficile.

Nel caso del gioco del $15$, il massimo numero di mosse necessarie è $80$ (vi sono esattamente $17$ configurazioni che richiedono $80$ mosse). Per il gioco con $24$ tasselli, si sa che il numero massimo di mosse è compreso fra $152$ e $208$. Per $35$ o più tasselli, limitare il numero massimo di mosse necessarie è al momento un problema aperto.


Riferimenti:

A. F. Archer: A modern treatment of the 15 puzzle, The American Mathematical Monthly 106 (1999), 793–799.

J. J. Rotman: Advanced Modern Algebra (Second Edition), Chapter I. Graduate Studies in Mathematics 114, American Mathematical Society (2010).

Gundlagenstreit, parte II. Frosch-Mäuse Krieg

Non intendo prendere posizione in questa guerra fra rane e topi
A. Einstein (lettera a M. Born, 1928)

Il 30 ottobre 1928, C. Carathéodory rese visita a Brouwer nella sua casa a Laren, nei pressi di Amsterdam, e gli consegnò una lettera scritta da Hilbert in persona nelle quale gli veniva comunicata la sua estromissione dall'editorial board dei Mathematische Annalen, sulla base di "incompatibilità riguardo a questioni fondamentali".

Brouwer, individuo nervoso ed emotivamente instabile, non era tipo da lasciar correre quella che considerava una intollerabile offesa alla sua persona e alla sua professionalità. Dopo essersi congedato in maniera turbolenta da Carathéodory, cominciò a preparare la contromossa.

I Mathematische Annalen erano all'epoca già pubblicati da Springer, che li aveva rilevati dall'editore originale Teubner, e il frontespizio della rivista elencava due tipi di redattori: i redattori capo ("Herausgeber") D. Hilbert, A. Einstein, O. Blumenthal, C. Carathéodory e i collaboratori ("Mitarbeiter") L. Bieberbach, H. Bohr, L. E. J. Brouwer, R. Courant, W. v. Dyck, O. Hölder, T. von Karman, A. Sommerfeld. Il contratto stipulato con la casa editrice non spiegava in dettaglio la distinzione fra i due tipi di redattori, nè chiariva se un redattore capo potesse arrogarsi il diritto di licenziare un collaboratore, per cui Brouwer minacciò di portare la contesa in tribunale.

Hilbert aveva messo tutto il peso del suo prestigio e della sua autorità, che erano immensi, nella crociata contro Brouwer. Quest'ultima non era originata soltanto dalla disputa sui fondamenti, ma nasceva anche da profonde differenze personali e politiche fra i due. All'inizio le loro relazioni erano amichevoli, e Hilbert rispettava i contributi matematici di Brouwer a tal punto da offrirgli una cattedra a Gottinga (che Brouwer non accettò). Successivamente, tuttavia, Brouwer (pur essendo olandese) appoggiò le tesi del nazionalismo germanico, e giunse al punto di criticare aspramente la partecipazione della delegazione dei matematici tedeschi, guidata da Hilbert, al congresso di Bologna del 1928.

Ad Hilbert, per il quale nazionalismi e politica non dovevano avere nulla a che fare con la scienza, questo tipo di atteggiamento risultava semplicemente odioso. Inoltre, Hilbert era all'epoca malato di anemia perniciosa, e temeva che Brouwer potesse approfittare della sua debolezza fisica per impadronirsi della direzione degli Annalen. Sembra invece senza fondamento l'accusa (citata ad esempio in [R70]) secondo cui Brouwer voleva essere referee esclusivo per i lavori dei matematici olandesi spediti alla rivista, che teneva poi per anni sulla scrivania prima di formulare un giudizio.

Il maggiore alleato di Brouwer nel comitato editoriale era Bieberbach, che già molto prima dell'avvento al potere dei nazisti aveva manifestato le sue ferventi posizioni nazionaliste; ma anche Blumenthal e Carathéodory, per quanto venerassero Hilbert e non volessero contrastarlo, erano legati da sentimenti di amicizia verso Brouwer, e desideravano una soluzione della vicenda che concedesse a quest'ultimo l'onore delle armi. Essi arrivarono al punto di consigliare a Brouwer di presentare volontariamente le sue dimissioni in modo da evitare lo scandalo dell'estromissione, ma il matematico olandese fu irremovibile e ribadì che, se necessario, Hilbert e i suoi fedelissimi avrebbero dovuto rispondere al giudice delle loro azioni.

L'ago della bilancia nella contesa era Einstein: il suo prestigio scientifico e i suoi standard morali erano tali che chiunque l'avesse avuto dalla sua parte sarebbe stato quasi sicuro di vincere la partita. Nelle sue lettere private a Hilbert, Einstein afferma che Brouwer "...è, con il dovuto rispetto per la sua mente di prim'ordine, uno psicopatico" e che, dunque, "sarebbe meglio lasciarlo libero di fare il giullare", definendone l'estromissione dagli Annalen "un procedimento che non posso nè approvare nè giustificare". Pertanto, Einstein era deciso a mantenere nella faccenda la più ferma neutralità, non volendo mischiarsi in quella che, con malcelato disprezzo, chiamava "una guerra fra rane e topi" (Frosch-Mäuse Krieg).

L'impasse venne infine superata con uno stratagemma suggerito da Carathéodory: visto che Brouwer non intendeva dimettersi, e che non era chiaro se potesse essere legalmente licenziato, la soluzione migliore era sciogliere l'intero comitato editoriale e costituirne uno nuovo. La cosa era possibile da contratto, essendo giunti al Volume 100 della rivista; infatti, il Volume 101 mostra un nuovo frontespizio, nel quale compaiono solo tre redattori: D. Hilbert, O. Blumenthal e E. Hecke. Per confrontare i frontespizi dei volumi 100 e 101, si guardino i link alle rispettive versioni digitalizzate [MathAnn100] e [MathAnn101].

Apparentemente, Brouwer reagì a questa soluzione di compromesso con una certa mitezza. Per un po' continuò a lamentarsi, poi capì che la guerra era finita e che erano andati tutti a casa, e nel 1935 fondò una nuova rivista, Compositio Mathematica, ancora oggi attiva e prestigiosa. Sarebbe morto solo nel 1966, ma la sua carriera scientifica era terminata: il rinnovamento del comitato editoriale dei Mathematische Annalen sancì di fatto la fine della Grundlagenstreit.

Riferimenti:

[MathAnn100] https://gdz.sub.uni-goettingen.de/id/PPN235181684_0100
[MathAnn101] https://gdz.sub.uni-goettingen.de/id/PPN235181684_0101
[vanDalen2011] D. van Dalen: The Selected Correspondence of L.E.J. Brouwer, Springer 2011
[vanDalen2013] D. van Dalen: L.E.J. Brouwer – Topologist, Intuitionist, Philosopher, Springer 2013
[R70] C. Reid: Hilbert, Springer 1970.

Nota: Il testo [vanDalen2013] è una completa biografia di L. E. J. Brouwer, mentre [vanDalen2011] è una raccolta della sua corrispondenza privata e scientifica.