13 maggio 2019

Le due culture in Matematica

"I was thinking more of the tendency today for people
to develop whole areas of mathematics on their own,
in a rather abstract fashion. They just go on beavering
away. If you ask what is it all for, what is its signifi-
cance, what does it connect with, you find that they
don't know.
"
M. F. Atiyah [1]

Ai matematici capita spesso di lamentarsi del fatto che la Matematica (a differenza della Poesia, della Letteratura o della Filosofia) non sia ancora vista come una parte indispensabile del patrimonio culturale collettivo. Dopotutto, quante volte abbiamo incontrato persone, anche molto colte, affermare candidamente con un sorrisetto "eh, io di Matematica non ci capisco proprio nulla"? Eppure, nessuno avrebbe il coraggio di sostituire "Matematica" con "Shakespeare" senza il timore di apparire goffamente ignorante.

È quindi un po' paradossale che anche i matematici, all'interno della loro comunità, tendano a volte a replicare, più o meno inconsapevolmente, atteggiamenti di questo tipo. Capita, ad esempio, che i "theory builders" guardino con sufficienza i "problem solvers", e viceversa.

Non è raro che, dopo aver studiato per anni il formalismo fortemente astratto della Geometria Algebrica moderna (quello sviluppato da Grothendieck negli EGA, per intenderci), uno si senta autorizzato ad alzare il sopracciglio verso chi si dedica a "semplici" problemi di Combinatoria; allo stesso modo, chi si dedica alla Combinatoria può considerare il Geometra Algebrico à la Grothendieck come uno snob spocchioso che non è in grado neanche di sporcarsi le mani con un semplice problema di colorazione di un grafo.

Ovviamente, il discorso precedente è una iper-semplificazione, dato che molti matematici sviluppano teorie proprio allo scopo di risolvere problemi (il viceversa, tuttavia, è molto meno frequente). A volte però, come acutamente osservato da M. Atiyah nella citazione iniziale, la ricerca dell'astrazione viene fatta per sè, escludendo a priori qualsiasi tentativo di applicazione della teoria o di ibridazione fra le due "culture".

Il risultato è una mancanza di comunicazione all'interno della comunità che, se da una parte rallenta intrinsecamente la ricerca scientifica, dall'altra può avere implicazioni devastanti per la carriera delle persone: non è infrequente che un "theory builder" duro e puro si trovi in una commissione che deve giudicare un candidato "problem solver" o viceversa, con risultati immaginabili in fase di valutazione.

L'argomento è chiaramente troppo vasto per un semplice post; il lettore interessato può trovare una bella analisi nell'articolo di W. T. Gowers The two cultures in mathematics [2], che contiene anche una serie importante di esempi che mostrano come Matematica Discreta e Combinatoria, lungi dall'essere solo una vasta collezione di problemi individuali e di risultati sparsi, contengono al loro interno principi generali di vasta applicabilità, anche se la struttura soggiacente è meno esplicita che nel caso della Geometria Algebrica o dell'Analisi Funzionale.

Esempi illuminanti sono la dimostrazione di P. Erdős del Teorema di Ramsey per mezzo di una "colorazione random" (che, usando le parole di Gowers, "opened the floodgates of probabilistic arguments in combinatorics") e quella di V. Milman del Teorema di Dworesky  per mezzo di un argomento di tipo "concentrazione della misura" che, oltre a dare il via all'analisi geometrica asintotica negli spazi di Banach, si è rivelato fecondo in altre parti della Matematica come l'Analisi Armonica e la Teoria delle PDE.

L'articolo di Gowers termina con l'auspicio di una maggiore collaborazione fra i matematici appartenenti alle due "culture", pur osservando che "collaboration of this kind would require greater efforts on the part of problem-solvers to learn a bit of theory, and greater sympathy on the part of theoreticians towards mathematicians who do not know what cohomology is".

Magari ha senso concludere questo post come è iniziato, ovvero con una citazione di Atiyah [3]:
"... the ultimate justification for doing mathematics is intimately related with its overall unity. If we grant that, on purely utilitarian grounds, mathematics justifies itself by some of its applications, then the whole of mathematics acquires a rationale provided it remains a connected whole. Any part that drifts away from the main body of the field has then to justify itself in a more direct fashion".


Riferimenti.

[1] An interview with M. Atiyah, The Mathematical Intelligencer 6 (1984), 9-19
https://link.springer.com/content/pdf/10.1007%2FBF03024202.pdf
[2] W. T. Gowers: The two cultures in Mathematics
https://www.dpmms.cam.ac.uk/~wtg10/2cultures.pdf
[3] M. F. Atiyah, Identifying progress in mathematics, ESF conference in Colmar, C.U.P. (1985), 24-41.

19 aprile 2019

La costante di Apéry

È ben noto che i valori della funzione zeta di Riemann calcolati negli interi positivi pari possono essere espressi in termini dei numeri di Bernoulli $B_n$, e più precisamente che vale l'identità
\begin{equation*}
 \zeta(2n) = (-1)^{n+1} B_{2n} \frac{(2 \pi) ^{2n}}{2 (2n)!}.
\end{equation*} Siccome i numeri di Bernoulli sono razionali, segue che i valori $\zeta(2n)$ sono multipli razionali di potenze di $\pi$, in particolare per $n \geq1$ sono tutti numeri trascendenti. I primi valori di $\zeta(2n)$ sono i seguenti:

$\zeta(0) = -1/2$
$\zeta(2) = \pi^2/6$ (un celebre risultato d Eulero noto come identità di Basilea)
$\zeta(4) = \pi^4/90$
$\zeta(6) = \pi^6/945$

e, in generale, gli interi $a_n, \, b_n$ che compaiono nell'identità
\begin{equation*}
a_n \zeta(2n) = b_n \pi^{2n}
\end{equation*} sono rispettivamente gli elementi delle successioni OEIS A002432 e A046988.

Per quanto riguarda i valori $\zeta(2n+1)$ della funzione zeta calcolata negli interi positivi dispari, si sa invece molto di meno. 

Il valore $\zeta(1)$ corrisponde alla somma della serie armonica $$1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots,$$ che è divergente, e infatti $\zeta(s)$ ha un polo in $s=1$.  

Il valore successivo $$\zeta(3) = 1 + \frac{1}{2^3} + \frac{1}{3^3} + \frac{1}{4^3} + \ldots \simeq 1.20205 $$ è detto costante di Apéry, in onore del matematico francese R. Apéry che nel 1978 ne dimostrò l'irrazionalità [A79]. Dimostrazioni più semplici vennero in seguito proposte da F. Beuker [B79] e W. Zudilin [Z02]. Non è noto al momento se la costante di Apéry sia un numero trascendente. 

Il reciproco $1/\zeta(3) \simeq 0.831912 \ldots$ rappresenta la probabilità che tre numeri "scelti a caso" siano relativamente primi. Curiosamente, il valore $\zeta(3)$ compare anche in Elettrodinamica Quantistica, nel calcolo del momento angolare dell'elettrone.

Non è noto un analogo del Teorema di Apéry per altri valori del tipo $\zeta(2n+1)$, ma si hanno alcuni risultati parziali. Sappiamo ad esempio che infiniti tali valori sono irrazionali [R00], e che almeno uno fra $\zeta(5)$, $\zeta(7)$, $\zeta(9)$, $\zeta(11)$ deve essere irrazionale [Z01]

Riferimenti.

[A79] R. Apéry: Irrationalité de $\zeta(2)$ et $\zeta(3)$, Astérisque 61: 11–13 (1979).
[B79] F. Beuker: A note on the irrationality of $\zeta(2)$ et $\zeta(3)$, Bull. London Math. Soc. 11 (3) (1979), 268–272.
[Z02] W. Zudilin: An elementary proof of Apéry's theorem, arXiv:math/0202159 (2002).
[R00] T. Rivoal: La fonction zêta de Riemann prend une infinité de valeurs irrationnelles aux entiers impairs, Comptes Rendus de l'Académie des Sciences, Série I, 331 (4) (2000): 267–270.
[Z01] W. Zudilin: One of the numbers $\zeta(5), \, \zeta(7), \, \zeta(9), \, \zeta(11)$ must be irrational, Russ. Math. Surv., 56 (4) (2001), 774–776.

06 aprile 2019

La misura del mondo

Fra i romanzi che hanno fra i protagonisti un grande matematico, merita un posto a parte  "La misura del mondo" (il titolo originale è "Die Vermessung der Welt")  del giovane scrittore tedesco D. Kehlmann (1975). Pubblicato nel 2005 e diventato un immediato bestseller, ha fatto guadagnare al suo autore paragoni con Nabokov e Proust, per la complessità dell'intreccio e la sapiente e allo stesso tempo leggera descrizione dei personaggi.

A "misurare il mondo" sono due famosi scienziati tedeschi, il matematico C. F. Gauss e l'esploratore A. von Humboldt, accomunati da grandi affinità ma anche separati da profonde differenze. Ad un certo punto si incontreranno a Berlino per un congresso scientifico (con gioia di von Humboldt e fastidio di Gauss, che detesta viaggiare), e ciò finirà per segnare profondamente entrambi.

Gauss, nato in estrema povertà, mostra il suo immenso genio fin dall'infanzia, arrivando a scrivere le sue Disquisitiones Arithmeticae (che gli daranno fama imperitura) poco più che ventenne. Il "principe dei matematici" passa quasi tutta la sua vita a Gottinga, ossessionato dal ricordo della prima moglie Johanna morta di parto (che tuttavia aveva abbandonato nel letto nuziale per appuntare su un pezzo di carta la formula dei minimi quadrati) e amareggiato per l'ottusità e la lentezza di pensiero che riscontra negli altri individui, compresi la seconda moglie Minna e il figlio Eugene, trattati ai limiti del disprezzo. Nell'ultima parte della sua vita si appassiona al problema del magnetismo terrestre, anche per via degli scambi epistolari con il giovane fisico W. E. Weber, che proprio grazie a Gauss ottiene (appena ventisettenne) una cattedra a Gottinga.

Von Humboldt nasce invece nobile, e viene allevato con l'idea della futura grandezza sin dalla più tenera età. Ossessionato dall'idea di viaggiare, abbandona una promettente carriera diplomatica in Prussia e si lancia nell'esplorazione dell'Amazzonia, mappando il canale naturale fra l'Orenoco e il Rio delle Amazzoni, sfidando zanzare, rapide e cannibali, scalando vulcani, scoprendo miniere e ignorando completamente i rapporti con l'altro sesso. Nell'ultima parte della sua vita si entusiasma per un viaggio di esplorazione in Siberia organizzato per lui dallo Zar di Russia, ma il confronto con i viaggi compiuti da giovane, quando era in salute, libero e sconosciuto, si rivela impietoso.

Gauss vede poco con i suoi occhi, ma molto con la sua mente. Al contrario, von Humboldt non capisce una parola di Matematica, ma viaggia in lungo e in largo per ottenere in prima persona quante più informazioni possibili sul mondo reale.

Entrambi i personaggi sono sostanzialmente dei solitari, chiusi nella realtà che si sono costruiti e infastiditi dalla fama crescente che accompagna le loro scoperte. Nonostante le loro enormi differenze, di nascita come di carattere, sia Gauss che von Humboldt sono tormentati dalla medesima ossessione: ciascuno nel proprio ambito, acquisire un'enorme mole di conoscenza.

Copertina dell'edizione italiana (fonte: Amazon.it)

16 marzo 2019

L'irrazionalità di $\pi$

È oggi ben noto che $\pi$ è un numero irrazionale, ossia che non può essere scritto come quoziente di due interi.

La prima dimostrazione di questo fatto fu data da J. H. Lambert nel 1761, per mezzo di uno sviluppo in frazione continua della funzione tangente.

Un argomento differente venne fornito nel 1873 da C. Hermite, il quale fece vedere che $\pi^2$ è irrazionale utilizzando un ingegnoso argomento per assurdo basato sul calcolo integrale e sulla caratterizzazione di $\pi$ come la più piccola soluzione positiva dell'equazione $\cos \frac{x}{2}=0$.

Oggi esistono decine di dimostrazioni dell'irrazionalità di $\pi$, alcune delle quali accessibili anche agli studenti degli ultimi anni di scuola superiore. Una delle più semplici è probabilmente la seguente, dovuta a I. Niven [N47].

Supponiamo per assurdo che $\pi=a/b$, con $a$, $b$ interi positivi. Preso un arbitrario numero naturale $n,$ consideriamo i seguenti polinomi:
\begin{equation*}
\begin{split}
f(x) & = \frac{x^n(a-bx)^n}{n!} \\
F(x) & = f(x)-f^{(2)}(x)+f^{(4)}(x)- \cdots +(-1)^nf^{(2n)}(x).
\end{split}
\end{equation*} Un semplice calcolo mostra che $f(x)$ e tutte le sue derivate $f^{(j)}(x)$ assumono valori interi in $x=0$; inoltre, lo stesso vale per $x=\pi=a/b$, dato che $f(x)=f(a/b-x)$.

Dalle formule elementari di derivazione otteniamo
\begin{equation*}
\frac{\mathrm{d}}{\mathrm{d}x}[F'(x) \sin x - F(x) \cos x] = F''(x) \sin x + F(x) \sin x = f(x) \sin x,
\end{equation*} da cui, per il Teorema Fondamentale del Calcolo Integrale,
\begin{equation} \label{eq:calcolo}
\int_0^{\pi} f(x) \sin x \, \mathrm{d}x = \left[F'(x) \sin x - F(x) \cos x \right]_0^{\pi} = F(\pi)+F(0). \tag{$\heartsuit$}
\end{equation} Per quanto visto, la quantità $F(\pi)+F(0)$ è un intero, dato che lo sono tutte le quantità $f^{(j)}(0)$ e $f^{(j)}(\pi)$.

D'altra parte, per $0 <x <\pi$ abbiamo
\begin{equation*}
0 < f(x) \sin x < \frac{{\pi}^n a^n}{n!}.
\end{equation*} Ciò implica che, per $n$ sufficientemente grande, la funzione $f(x) \sin x$ è positiva ma arbitrariamente piccola in $(0, \, \pi)$, e quindi lo stesso è vero per il corrispondente integrale definito.

Allora si può scegliere $n$ in modo tale che il membro a sinistra di $\eqref{eq:calcolo}$ sia strettamente compreso fra $0$ e $1$, contraddizione.

I. Niven (fonte Wikipedia)

Riferimenti.

[N47] I. Niven: A simple proof that π is irrational, Bull. Amer. Math. Soc. 53  (1947).

23 febbraio 2019

Fattoriali e potenze perfette

Domanda. È possibile che il fattoriale $n!$ di un intero $n \geq 2$ sia una $k$-esima potenza perfetta, ossia un intero della forma $m^k$, con $k \geq 2$?
Usando il Postulato di Bertrand (o Teorema di Chebyshev), non è difficile dimostrare che la risposta è negativa.
Proposizione. Se $n \geq 2$, allora $n!$ non è una $k$-esima potenza perfetta.
Dimostrazione. Gli interi $2!=2$ e $3!=6$ non sono potenze perfette. Se $n≥4$, allora per il Postulato di Bertrand esiste un primo $p$ tale che $$\frac{n}{2} < p < n.$$ Siccome $p<n$, sicuramente $p$ divide $n!$. D'altra parte, il più piccolo multiplo non banale di $p$ è $2p$, che per ipotesi è maggiore di $n$ e quindi non compare nella produttoria che definisce $n!$. Ciò mostra che $p^2$ non divide $n!$, quindi $p^k$ non divide $n!$, il che implica che quest'ultimo non può essere una $k$-esima potenza perfetta.
                                                                                                                                                $\square$

Una dimostrazione del medesimo risultato che, invece del Postulato di Bertrand, usa la formula di De Polignac-Legendre (che fornisce la massima potenza con cui un primo $p$ divide $n!$) è proposta in [MSE31973].

Nel 1975, P. Erdős e J. L. Selfridge raffinarono l'argomento usato sopra e provarono che nessun prodotto di due o più interi consecutivi può essere una potenza perfetta. Il lettore interessato può consultare l'articolo originale [ES75] .

Un giovane P. Erdős (fonte: Guggenheim fundation)

Riferimenti.

09 febbraio 2019

Numeri di Liouville

Un numero reale si dice trascendente (su $\mathbb{Q}$) se non è radice di una equazione polinomiale a coefficienti interi. La precedente definizione implica che ogni numero trascendente è irrazionale (ma ovviamente non vale il viceversa, si pensi a $\sqrt{2}$) e che  l'insieme dei numeri algebrici (cioè, non trascendenti) è numerabile.

Pertanto, siccome l'insieme dei numeri reali ha cardinalità strettamente maggiore del numerabile, segue che "quasi tutti" i numeri reali sono trascendenti. Tuttavia, questo tipo di argomento nulla ci dice sulla trascendenza di uno specifico numero reale, che può essere molto difficile da dimostrare. Ad esempio, si sa che $\pi$ ed $e$ sono entrambi trascendenti, ma non è al momento noto se la loro somma $\pi+e$ lo sia.

Storicamente, i primi esempi espliciti di numeri trascendenti vennero forniti a metà dell'800 da J. Liouville, come conseguenza dei suoi importanti studi sull'approssimazione diofantea dei numeri irrazionali. Più precisamente, Liouville dimostrò nel 1844 il seguente fondamentale risultato:
Teorema. Supponiamo che $x$ sia un numero irrazionale tale che, per ogni intero positivo $n$, esistano interi $p$ e $q$, con $q>1$, tali che $$\left|x-\frac{p}{q}\right| < \frac{1}{q^n}.$$Allora $x$ è trascendente.
 Un esempio di numero reale che verifica le ipotesi del Teorema è la cosiddetta costante di Liouville
$$L= \sum_{n\geq 1} 10^{-n!},$$ ossia, in notazione decimale, $$L= 0.110001000000000000000001 \ldots, $$ dove la cifra $1$ compare nei posti decimali corrispondenti ai fattoriali degli interi.

I numeri reali che verificano le condizioni del Teorema vengono oggi chiamati numeri di Liouville; si noti che la diseguaglianza che li caratterizza ci dice che un numero trascendente di Liouville può essere approssimato "estremamente bene" da una successione di numeri razionali.

È attualmente noto che l'insieme $L$ dei numeri di Liouville è non-numerabile,  denso in $\mathbb{R}$ e di misura di Lebesgue $0$. Ciò implica che "quasi tutti" i numeri trascendenti non sono numeri di Liouville. Un esempio notevole di numero trascendente che non è di Liouville è $\pi$, come dimostrato da Mahler nel 1953 [M53].

Per maggiori informazioni sui numeri di Liouville (e più in generale sui numeri trascendenti) il lettore può consultare la monografia [MR14].

J. Liouville (fonte Wikipedia)

Riferimenti.

[M53] K. Mahler: On the Approximation of $\pi$, Nederl. Akad. Wetensch. Proc. Ser. A. 56/Indagationes Math. 15, 30-42, 1953.
[MR14] M. R. Murty, P. Rath: Transcendental Numbers, Springer 2014

27 gennaio 2019

Numeri perfetti

Un numero naturale si dice perfetto se è uguale alla somma dei suoi divisori escluso il numero stesso. Ad esempio, $6$, $28$, $496$ sono numeri perfetti, dato che

$6 = 1+2+3$
$28 = 1+2+4+7+14$
$496 = 1+2+4+8+16+31+62+124+248.$

La prima definizione nota di numero perfetto si trova nel Libro VII degli Elementi di Euclide, dove viene dimostrato che, se $p$ è un numero primo tale che $2^p-1$ sia ancora primo, allora $2^{p-1}(2^p-1)$ è un numero perfetto. Ad esempio, prendendo $p=2, \, 3, \, 5$ si ottengono i tre numeri perfetti $6, \, 28, \,496$ considerati sopra. 

I primi di tale tipo sono detti primi di Mersenne (successione OEIS A000668), e al momento non si sa se ne esistano in numero infinito. Sono noti 51 primi di Mersenne, il più grande dei quali è $2^{82589933} − 1$, scoperto a dicembre 2018, che ha $24862048$ cifre decimali. 

Due millenni dopo Euclide, Eulero dimostrò che, viceversa, ogni numero perfetto pari è della forma $2^{p-1}(2^p-1)$, dove $p$ è un primo di Mersenne. Pertanto, vi è una corrispondenza biunivoca fra numeri perfetti pari e numeri primi di Mersenne; in particolare, non è noto se esistano infiniti numeri perfetti pari.

L'esistenza di numeri perfetti dispari è uno dei problemi aperti più famosi e difficili in Teoria dei Numeri, per il quale si hanno solo alcuni risultati parziali. Ad esempio, si sa che un ipotetico numero perfetto dispari deve essere maggiore di $10^{1500}$, possedere almeno 10 fattori primi distinti e che i suoi due più grandi fattori primi devono essere maggiori di $10^8$ e $10^4$, rispettivamente. Tali restrizioni rendono praticamente impossibile la ricerca di un numero perfetto dispari per "brute force", almeno con i calcolatori elettronici attualmente disponibili.

Il teorico dei numeri statunitense C. Pomerance, basandosi su un argomento di tipo euristico, è giunto alla conclusione che i numeri perfetti dispari "non dovrebbero esistere". Maggiori informazioni sul suo argomento probabilistico (e in generale sul problema dell'esistenza di numeri perfetti dispari) possono essere trovati nel sito web  http://oddperfect.org/

10 gennaio 2019

Il Problema di Waring

Nel 1770 J. L. Lagrange dimostrò che ogni numero naturale è somma di al più quattro quadrati. Nello stesso anno, motivato da questo risultato, E. Waring propose quello che sarebbe poi diventato noto come
Problema di Waring. Dato un intero positivo $k$, esiste un (minimo) numero $g(k)$ tale che ogni numero naturale $n$ si scriva come somma di al più $g(k)$ potenze $k$-esime?
Banalmente $g(1)=1$, mentre il risultato di Lagrange, insieme al fatto che esistono numeri naturali che non si scrivono come somma di tre quadrati (ad esempio $7$), implica $g(2)=4$.

Nel 1909, D. Hilbert dimostrò [H09] che la risposta al Teorema di Waring è affermativa, ma le sue tecniche non erano costruttive, pertanto non davano indicazioni su come determinare esplicitamente i valore di $g(k)$ in funzione di $k$. Alcuni di tali valori vennero in seguito ricavati da differenti autori utilizzando metodi ad hoc:
  • $g(3)=9$ ($n=23$ è il minimo intero positivo che non è somma di $8$ cubi), vedi [W09, K12]
  • $g(4)=19$ ($n=79$ è il minimo intero positivo che non è somma di $18$ quarte potenze)
  • $g(5)=37$
  • $g(6)=73$, vedi [P40].
I valori attualmente conosciuti per $g(k)$ sono tabulati nella successione OEIS A002804, i cui primi termini sono $$1, 4, 9, 19, 37, 73, 143, 279, 548, 1079, 2132, 4223, 8384, 16673, 33203, 66190, 132055.$$ Una quantità correlata a $g(k)$ è $G(k)$, definito come il minimo intero tale che ogni numero naturale $n$ sufficientemente grande si possa esprimere come somma di al più $G(k)$ potenze $k$-esime. Ovviamente, si ha $G(k) \leq g(k)$ per ogni $k$, e l'eguaglianza vale se e solo se esistono infiniti numeri naturali che non si esprimono come somma di $g(k)-1$ potenze $k$-esime.

Siccome nessun intero congruente a $7 $ (modulo $8$) può essere rappresentato come somma di tre quadrati, si ha $G(2)=g(2)=4$. Il problema della determinazione di $G(k)$ è più difficile del corrispondente problema per $g(k)$, e infatti i valori di $G(k)$ per $k \geq 3$ non sono noti (eccetto $G(4)=16$, vedi [D39]), tuttavia si hanno a disposizione alcune stime. Ad esempio, si sa che $4 \leq  G(3) \leq 7 $.

In generale, usando il cosiddetto metodo del cerchio di Hardy e Littlewood, Vinogradov ha dimostrato il bound superiore $$G(k) \leq  k(3 \log k + 11).$$ Per ulteriori dettagli sull'argomento, il lettore può consultare il survey [VW02].

E. Waring (fonte Wikipedia) 

Riferimenti.

[D39] H. Davenport: On Waring's Problem for Fourth Powers, Ann. Math. 40 (1939), 731-747
[H09] D. Hilbert: Beweis für die Darstellbarkeit der ganzen Zahlen durch eine feste Anzahl $n$-ter Potenzen (Waringsches Problem)Mathematische Annalen  67 (3) (1909), 281–300.
[W09] A. Wieferich: Beweis des Satzes, daß sich eine jede ganze Zahl als Summe von höchstens neun positiven Kuben darstellen läßtMathematische Annalen 66 (1) (1909), 95–101.
[K12] A. Kempner: Bemerkungen zum Waringschen Problem, Mathematische Annalen 72 (3) (1912), 387–399.
[P40] S. S. Pillai: On Waring's problem $g(6)=73$, Proc. Indian Acad. Sci. 12 (1940), 30–40.
[VW02] R.C. Vaughan, T. Wooley: Waring Problem: a survey, in  Number Theory for the Millennium. III. Natick, MA: A. K. Peters. pp. 301–340. ISBN 978-1-56881-152-9.

24 dicembre 2018

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. 

04 dicembre 2018

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.