25 febbraio 2018

Il Postulato di Bertrand

Chebyshev said it, but I'll say it again: there's always a prime between $n$ and $2n.$
(N. J. Fine)

Nel 1845, J. Bertrand propose, verificandola sperimentalmente fino al valore $n=3000000$, la seguente congettura, che da allora divenne nota come
Postulato di Bertrand. Dato un numero naturale $n >1$, esiste sempre un numero primo $p$ tale che $n < p <  2n$.
Un immediato corollario è che il gap tra un numero primo e il successivo è minore del doppio del primo stesso; in altre parole, se $\{p_n\}$ indica la successione dei primi, si ha $p_{n+1} < 2p_n$. Un'altra interessante conseguenza è che la successione $\mathbb{P}$ formata da 1 e dai numeri primi è una "successione completa", nel senso che ogni numero naturale può scriversi come somma di elementi di $\mathbb{P}$, usando ogni elemento al più una sola volta.

Il Postulato di Bertrand può essere derivato dal Teorema dei Numeri Primi (TNP), osservando che, siccome $\log x$ è asintotico a $\log 2x$, allora il numero dei primi fra $1$ e $2n$ è asintoticamente il doppio del numero dei primi fra $1$ ed $n$, dunque il numero dei primi fra $n$ e $2n$ va asintoticamente come $2n/2 \log n=n/ \log n$, cioè vi sono in realtà molti più primi fra $n$ e $2n$ da quanto previsto dal Postulato. Tuttavia, quest'ultimo è un risultato molto meno difficile da dimostrare rispetto a TNP, e inoltre ha il suo interesse storico in quanto venne provato prima di esso. Il numero esatto di primi fra $n$ e $2n$ è tabulato nella successione OEIS A060715.

La prima dimostrazione del Postulato di Bertrand venne fornita nel 1852 da P. L. Chebyshev (la prima dimostrazione di TNP è del 1896), utilizzando metodi di Teoria Analitica dei Numeri [5]. Da allora il risultato è anche conosciuto come Teorema di Bertrand-Chebyshev. La dimostrazione di Chebyshev venne successivamente semplificata da S. Ramanujan, che fornì un argomento di una pagina basato su alcune proprietà della funzione Gamma, vedi [3].


P. L. Chebyshev (fonte: Wikipedia)

Nel 1932, nel suo primo articolo pubblicato (all'età di 19 anni) P. Erdős diede la prima dimostrazione elementare del Postulato di Bertrand. Qui "elementare" va inteso nel senso della Teoria dei Numeri, dove il termine non vuol dire "semplice", ma piuttosto "che non utilizza strumenti al di là dell'aritmetica".

Di fatto, la dimostrazione di Erdős  è piuttosto sofisticata, e si basa su una stima accurata dell'esponente con cui un primo $p$ divide il coefficiente binomiale $\binom{2n}{n}$. Tale stima permette di mostrare che, se non esistessero primi fra $n$ e $2n$, allora tale coefficiente crescerebbe asintoticamente meno di quanto atteso, giungendo ad una contraddizione per $n>4000$.

I dettagli possono essere trovati in [2] e nel bel libro [4], che raccoglie una serie di dimostrazioni brevi e particolarmente eleganti, nello stile amato da Erdős. Quest'ultimo pensava infatti che esistesse un Libro nel quale Dio aveva raccolto le dimostrazioni più belle, e che fosse compito dei matematici (ri)scoprirle. In realtà Erdős non era religioso, e a chi gli chiedeva se credesse in Dio soleva rispondere "You don't have to believe in God, but you should believe in The Book."


P. Erdős (fonte: Wikipedia) 

Il paradosso di Bertrand è stato nel corso del tempo generalizzato in varie direzioni. Ad esempio, oggi si sa che esiste sempre un primo fra $2n$ e $3n$ (M. El Bachraoui, 2006) e che esiste sempre un primo fra $3n$ e $4n$ (D. Hanson, 1973). Inoltre, è anche noto che quando $n$ tende all'infinito anche il numero di primi fra $3n$ e $4n$ tende all'infinito (A. Loo, 2011).

Un problema collegato è quello di determinare il minimo esponente $r$ tale che esista sempre un primo fra $n$ e $n+O(n^r)$, per $n$ sufficientemente grande. Il Postulato di Bertrand implica che $r$ è al più $1$, e il miglior risultato oggi disponibile è $r \leq 6/11$ (Lou-Yao, 1992).

E' interessante notare che problemi in apparenza simili al Postulato di Bertrand sono ancora oggi (2018) irrisolti. Ad esempio, non è noto se esista sempre un numero primo fra $n^2$ e $(n+1)^2$; si pensa che la risposta sia affermativa, e questa è nota come congettura di Legendre.

Riferimenti:

[1]
https://en.wikipedia.org/wiki/Bertrand%27s_postulate
[2] https://en.wikipedia.org/wi…/Proof_of_Bertrand%27s_postulate
[3] http://mathworld.wolfram.com/BertrandsPostulate.html
[4] M. Aigner, G. M. Ziegler, K. H. Hofmann: Proofs from THE BOOK, Fourth edition, Springer, 2009. ISBN 978-3-642-00855-9.
[5] P. L. Chebychev. Mémoire sur les nombres premiers. Journal de mathématiques pures et appliquées, Sér. 1, 366-390 (1852). (Proof of the postulate: 371-382)
[6] S. Ramanujan "A Proof of Bertrand's Postulate." J. Indian Math. Soc. 11, 181-182 (1919).


17 febbraio 2018

Il Problema di Burnside

Un gruppo $G$ si dice "periodico" se ogni elemento di $G$ ha ordine finito, cioè se per ogni $g \in G$ esiste $n=n(g)$ tale che $g^n=1$. Chiaramente ogni gruppo finito è periodico, ma il viceversa non è vero: un controesempio è il gruppo di Prüfer $\mathbb{Z}(p^{\infty})$, ossia il sottogruppo di $\mathbb{C}^{\ast}$ formato da tutte le radici $n$-esime dell'unità, al variare di $n \in \mathbb{N}$.

È facile vedere che il gruppo di Prüfer non può essere finitamente generato. Nel 1902, W. Burnside pose la seguente domanda, che era destinata a diventare uno dei problemi più importanti e fecondi della Teoria dei Gruppi:

Problema generale di Burnside. Sia $G$ un gruppo finitamente generato e periodico. È vero che $G$ è finito?
La risposta risultò essere negativa: infatti, nel 1964 Golod e Shafarevich costruirono un controesempio, ossia un gruppo infinito, finitamente generato e periodico. Più precisamente, essi dimostrarono che per ogni primo $p$ esiste un gruppo infinito con tre generatori in cui ogni elemento ha ordine una potenza di $p$. Tuttavia, in tale controesempio l'ordine di $g \in G$ non può essere uniformemente limitato.

Il controesempio descritto sopra portò a considerare una versione più debole del problema, in cui l'ordine di $g \in G$ è limitato da una costante fissata $n$, ossia $g^n=1$ con $n$ indipendente da $g$. Un tale gruppo è detto "gruppo di esponente $n$". Chiaramente, avere esponente finito implica essere periodico, ma il viceversa non è vero (il gruppo di Prüfer o quelli di Golod-Shafarevich forniscono controesempi). Si può dunque enunciare il
Problema di Burnside I. Sia $G$ un gruppo finitamente generato e di esponente finito. È vero che $G$ è finito?
Questo problema può essere riformulato in modo da considerare una particolare classe di gruppi finitamente generati, i cosiddetti gruppi di Burnside. Se $F_r$ è il gruppo libero su $r$ generatori e $n$ è un numero naturale fissato, definiamo il gruppo di Burnside $B(r, \, n)$ come il quoziente di $F_r$ per le infinite relazioni $\{x^n=1, \, x \in  F_r\}$.

È un esercizio standard di teoria dei gruppi verificare che ogni gruppo con $r$ generatori ed esponente $n$ è un'immagine omomorfa di $B(r, \ n)$, per cui possiamo riformulare il nostro problema come segue:
Problema di Burnside II. Per quali coppie $(r, \, n)$ il gruppo di Burnside $B(r, \, n)$ è finito?
La risposta generale a questo problema non è nota. Nel suo lavoro originale, Burnside notò che $B(1,\, n)$ è il gruppo ciclico di ordine $n$, mentre $B(r, \, 2)$ è il prodotto di $r$ copie di $\mathbb{Z}_2$, quindi in entrambi i casi si ottengono gruppi finiti. Più avanti, venne dimostrato che $B(r, \, 3)$, $B(r, \, 4)$ e $B(r, \, 6)$ sono gruppi finiti per ogni valore di $r$. Ad esempio, $B(r, \,3)$  è isomorfo al gruppo di Heisenberg sul campo con tre elementi, in particolare ha ordine $27$.

Si noti che al momento (2018) non si sa se $B(2, \, 5)$ sia un gruppo finito.

I primi controesempi al Problema di Burnside I vennero forniti da Novikov e Adian nel 1968: essi mostrarono che, per $n$ dispari e maggiore di $4381$, esistono gruppi di Burnside infiniti. Il bound sull'esponente venne poi abbassato da Adian a $665$. Per quanto riguarda il caso di esponente pari, che risultò notevolmente più difficile da trattare, i primi controesempi vennero forniti da S. V. Ivanov nel 1992: egli dimostrò che, per ogni $r >1$ e $n> 2^48$ e divisibile per $2^9$, il gruppo $B(r,\, n)$ è infinito.

Una importante variante del Problema di Burnside è il cosiddetto
Problema di Burnside ristretto. Sia $G$ un gruppo finito con $r$ generatori ed esponente $n$ (ad esempio, un gruppo finito della forma $B(r, \, n)$). È vero che l'ordine di $G$ può essere limitato da una costante che dipende solo da $r, \, n$?
In questo caso la risposta è affermativa, come dimostrato da E. Zelmanov nel 1991. Per questo suo importante risultato, a Zelmanov venne assegnata la medaglia Fields nel 1994.


Riferimenti:

[1]
https://en.wikipedia.org/wiki/Burnside_problem

[2]
http://www-history.mcs.st-and.ac.uk/H…/Burnside_problem.html

[3]
http://mathworld.wolfram.com/BurnsideProblem.html

03 febbraio 2018

Il Teorema della Base di Hilbert

The theory of invariants came into existence about the middle of the nineteenth century somewhat like Minerva: a grown-up virgin, mailed in the shining armor of algebra, she sprang forth from Cayley's Jovian head.
(H. Weyl)

Uno dei campi di ricerca matematica più attivi alla fine dell'800 era la cosiddetta Teoria degli Invarianti, creata da A. Cayley con il suo seminale lavoro "On the Theory of Linear Transformations" (1845).

In termini moderni, il problema può essere enunciato come segue. Si consideri uno spazio vettoriale $V$ di dimensione finita $n$ su un campo $\mathbb{K}$, e sia $S^r(V)$ la parte in grado $r$ della sua algebra simmetrica. Considerata l'azione naturale del gruppo $\mathsf{SL}(V)$, si vogliono determinare gli elementi di $S^r(V)$ che sono invarianti per tale azione.

Cayley si limitava al caso $V=\mathbb{C}[x_1,\ldots ,x_n]$, per cui $S^r(V)$ era dato dai polinomi omogenei di grado $r$ a coefficienti complessi in $n$ indeterminate, e considerava la sottoalgebra dei polinomi che erano invarianti per l'azione naturale di $\mathsf{SL}_n(\mathbb{C})$. Nella sua terminologia, egli cercava "gli invarianti delle forme $n$-arie di grado $r$". Il primo caso da trattare era ovviamente quello delle forme binarie, ossia dei polinomi omogenei di grado $r$ in $2$ variabili.

Il "re della teoria degli invarianti" era da tutti considerato P. Gordan, che nel 1868 aveva dimostrato, per mezzo di un complesso argomento computazionale, che l'algebra degli invarianti per le forme binarie (di ogni grado) è finitamente generata. I tentativi di Gordan di adattare la sua dimostrazione alle forme con più di due variabili, però, fallirono a causa della enorme complessità dei calcoli da effettuare.

La svolta arrivò 20 anni dopo, nel 1890, quando il giovane D. Hilbert stupì la comunità matematica con l'articolo [Hilb90], nel quale dimostrava il celebre
Teorema di Finitezza di Hilbert. L'algebra degli invarianti delle forme $n$-arie di grado $r$ è finitamente generata per ogni valore di $n, \, r$. 
La dimostrazione di Hilbert giunse come un fulmine a ciel sereno, non solo per la potenza del risultato ma soprattutto per la tecnica utilizzata. Fino ad allora, infatti, tutti gli sforzi per provare la finita generazione degli invarianti erano rivolti alla determinazione di una base esplicita caso per caso. Hilbert, invece, "tagliò il nodo gordiano" dando una dimostrazione esistenziale e non costruttiva, che risolveva tutti gli infiniti casi in un colpo solo.

Il suo argomento si basava su un risultato molto generale e di indipendente interesse, e la cui dimostrazione originale (per assurdo) è sostanzialmente la stessa riportata nei moderni testi di Algebra. Si tratta del celebre
Teorema della Base di Hilbert. Se $\mathbb{K}$ è un campo, ogni ideale di $\mathbb{K}[x_1, \ldots , x_n]$ è finitamente generato.
L'approccio di Hilbert al problema originale fu di applicare il suo Teorema di Finitezza all'ideale $J$ di $\mathbb{C}[x_1, \ldots, x_n]$ generato dai polinomi invarianti di grado positivo, deducendo che deve esistere un insieme finito di invarianti che genera $J$. Dopodiché, utilizzando l'operatore che oggi è chiamato "proiettore di Reynolds", concludeva che questo insieme finito di generatori di $J$ (come ideale) genera di fatto l'intero sottoanello degli invarianti polinomiali.

All'inizio non tutti compresero la portata rivoluzionaria delle argomentazioni di Hilbert. Secondo quanto narrato in [R70],  sembra che lo stesso Gordan si trovò a disagio nei loro confronti, giungendo ad affermare

Das ist nicht Mathematik. Das ist Theologie

(Questa non è matematica. Questa è teologia).

Più tardi, tuttavia, cambiò idea, anche perché nel frattempo Hilbert aveva fornito [Hilb93] un approccio costruttivo al suo Teorema della Base. Gordan giunse anche a semplificare uno dei passaggi nella dimostrazione hilbertiana (infatti, secondo alcuni, il suo paragone  con la teologia non era tanto critico, quanto sottilmente ironico).

Chi capì subito la potenza dei nuovi metodi fu invece F. Klein, secondo il quale il lavoro di Hilbert sugli invarianti era l'articolo più importante mai pubblicato fino ad allora su Mathematische Annalen. Da quel momento, Klein si adoperò in modo che Hilbert ottenesse una cattedra a Gottinga, cosa che avvenne nel 1895.

Dopo questo grande successo, Hilbert cambiò settore di ricerca, dedicandosi alla Teoria dei Numeri. A suo parere, infatti, la teoria degli invarianti era ormai morta. Effettivamente, l'argomento smise di essere soggetto di ricerca per quasi un secolo, e per trovare qualcuno che lo riportasse in vita bisognerà attendere gli anni '60 del '900 con D. Mumford e la sua Geometric Invariant Theory. Ma questa è un'altra storia.


Riferimenti:

[Hilb90] D. Hilbert: Ueber die Theorie der algebraischen Formen, Math. Ann. 36 (1890), 473–534.
[Hilb93] D. Hilbert: Ueber die vollen Invariantensysteme, Math. Ann. 42 (1893) pp. 313–373.
[R70] C. Reid: Hilbert, Springer (1970).