In una tavola pitagorica \(N \times N\) ci sono \(N^2\) interi: quanti sono quelli distinti? È un problema di Erdős di cui non si conosce ancora la soluzione esatta. Ce ne parla il nostro Alessandro Zaccagnini.
Il problema della tavola pitagorica
Al grande matematico ungherese Pál Erdős piaceva molto porre problemi e possiamo dire con certezza che amava in modo particolare quelli che riguardano i divisori dei numeri interi. All’apparenza, il problema del numero degli interi distinti sulla tavola pitagorica sembra banale e del tutto innocuo e invece è cosí difficile che non si conosce ancora la risposta precisa.
Cominciamo da un esempio familiare a tutti: sulla consueta tavola pitagorica \(10 \times 10\) ci sono 42 interi diversi sui 100 possibili; possiamo vedere che ci sono la maggior parte dei numeri interi relativamente piccoli, e poi cominciano a diradarsi. Tra i primi 20 interi mancano solo 11, 13, 17, 19, che non a caso sono numeri primi. Tra gli ultimi 20, da 81 a 100, ce sono solo 3, e cioè 81, 90, 100.
Analizziamola ancor piú da vicino, potremmo dire da un punto di vista statistico, colorando in modo diverso le caselle degli interi a seconda del numero di volte in cui compaiono: bianco per i numeri che compaiono una volta sola e poi rosso, azzurro e verde per i numeri che compaiono rispettivamente 2, 3 o 4 volte:
Come possiamo vedere, relativamente pochi numeri compaiono relativamente tante volte: 6 numeri compaiono una volta sola; 23 numeri compaiono due volte; 4 numeri compaiono tre volte; 9 numeri compaiono quattro volte. Gli interi distinti sono dunque \(6 + 23 + 4 + 9 = 42\). Notiamo che numeri come 36 (ma anche 42, 48, …), che pure hanno “tanti” divisori compaiono “poche” volte perché non possiamo contare le scomposizioni \(3 \cdot 12\) o \(2 \cdot 18\), che si trovano fuori dalla tavola pitagorica \(10 \times 10\). Un’altra cosa che vale la pena di notare è che ci sono solo 17 fra i 61 interi da 40 in poi, e dunque una netta minoranza. Se guardiamo il quadrato \(5 \times 5\) in basso a destra, vediamo che è prevalentemente colorato di rosso, mentre il quadrato \(6 \times 6\) in alto a sinistra è prevalentemente colorato di verde: gli interi relativamente piccoli compaiono un numero di volte che è vicino al numero totale dei loro divisori, mentre quelli grandi, ammesso che compaiano, ci sono solo una o due volte.
Mostriamo ora la tavola pitagorica \(12 \times 12\) colorata secondo lo schema precedente: qui avremo bisogno di due nuovi colori, il giallo per indicare gli interi che compaiono 5 volte e il blu per indicare gli interi che compaiono 6 volte.
Quindi, in \(\mathcal{TP}(12)\) ci sono \(59\) interi distinti: i 42 precedenti piú 12 multipli di 11 e 5 multipli di 12 che non erano presenti. Possiamo notare inoltre che alcuni interi come \(12\), \(24\) o \(36\) “cambiano colore” nel passare dalla precedente a questa, perché sono ora “disponibili” alcune nuove fattorizzazioni.
Ragioniamo in generale
Possiamo fare qualche considerazione valida in generale. Chiamiamo \(\mathcal{TP}(N)\) la tavola pitagorica \(N \times N\), cioè l’insieme \(\{ n \in \{ 1, 2, \dots, N^2 \} \colon n = a \cdot b\) per due interi \(a\), \(b \in [1, N] \}\) ossia \(\{ a \cdot b \colon a\), \(b \in [1, N] \}\). Chiamiamo \(a(N)\) il numero degli interi distinti in \(\mathcal{TP}(N)\). La simmetria rispetto alla “diagonale principale,” dovuta alla proprietà commutativa della moltiplicazione, implica che ci siano al massimo \(N (N – 1) / 2 + N = (N^2 + N) / 2\) interi distinti in \(\mathcal{TP}(N)\), cioè che \(a(N) \le (N^2 + N) / 2\). Alcuni interi però compaiono molte volte e questo fa diminuire ulteriormente il totale, come abbiamo appena visto nei casi particolari \(N = 10\) ed \(N = 12\).
I numeri primi fra \(N + 1\) ed \(N^2\) non possono comparire in \(\mathcal{TP}(N)\). Sono piú interessanti i numeri primi nell’intervallo \([1, N]\), perché li possiamo utilizzare per dimostrare che \(\mathcal{TP}(N)\) contiene parecchi interi distinti: infatti, possiamo usare loro multipli per creare insiemi disgiunti e questo ci permette di dare una stima dal basso per il numero che stiamo cercando di calcolare, cioè \(a(N)\). Vediamo una possibile “costruzione” nel caso della tavola pitagorica \(20 \times 20\), sulla quale ci sono in realtà \(152\) interi distinti. Gli insiemi \[\begin{aligned}
&\{ 2, 4 \} \\
&\{ 3, 6, 9 \} \\
&\{ 5, 10, 15, 20, 25 \} \\
&\{ 7, 14, 21, 28, 35, 42, 49 \} \\
&\{ 11, 22, 33, 44, \dots, 99, 110, 121 \} \\
&\{ 13, 26, 39, 52, \dots, 143, 156, 169 \} \\
&\{ 17, 34, 51, 68, \dots, 255, 272, 289 \} \\
&\{ 19, 38, 57, 76, \dots, 323, 342, 361 \} \\\end{aligned}\] sono mutuamente disgiunti e quindi contengono \(2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 = 77\) interi distinti, cioè \(a(20) \ge 77\). Il motivo per cui questi insiemi sono disgiunti è presto spiegato: non ci sono multipli di 3, 5, 7, 11, 13, 17 o 19 nel primo insieme, che quindi è disgiunto dagli altri sette; non ci sono multipli di 5, 7, 11, 13, 17 o 19 nel secondo insieme, che quindi è disgiunto dagli altri sei; non ci sono multipli di 7, 11, 13, 17 o 19 nel terzo insieme, che quindi è disgiunto dai successivi, e cosí via. Alla base di tutto questo, naturalmente, c’è il Teorema Fondamentale dell’Aritmetica. Gli elementi nella regione colorata nella figura qui sotto sono tutti distinti fra loro e quindi \(a(20)\) vale almeno quanto l’area colorata.
In generale, per il Teorema dei Numeri Primi, nell’intervallo \([1, N]\) ci sono approssimativamente \(N / \log N\) numeri primi quando \(N\) è molto grande. Qui e nel seguito, indicheremo con \(\log N\) il logaritmo naturale di \(N\), cioè in base \(\mathrm{e}\), dove \(\mathrm{e}\) è il numero di Nepero. Per ciascun numero primo \(p \in [1, N]\) consideriamo l’insieme dei suoi multipli da \(p\) fino a \(p^2\). Facendo qualche calcolo, otteniamo che ci sono almeno \(\approx N^2 / (2 \log N)\) interi distinti in \(\mathcal{TP}(N)\). In definitiva
per \(N\) grande. Informalmente, il fattore 2 nei denominatori dipende dal fatto che consideriamo solo metà tavola pitagorica per via della simmetria; il fattore \(\log N\) a sinistra dipende dalla densità dei numeri primi. Questo lascia in dubbio approssimativamente un fattore \(\log N\) fra il massimo e il minimo valore possibile per \(a(N)\).
In una serie di articoli scritti fra il 1955 e il 1960, Erdős ha dimostrato alcuni risultati sempre piú precisi: al primo dedicheremo il prossimo paragrafo, mentre l’ultimo dice che \(a(N)\) vale approssimativamente \(N^2 / (\log N)^b\), dove \(b = 0.08607 \dots\). L’enunciato preciso è piuttosto complicato: i lettori interessati lo possono trovare aprendo il menú a tendina.
Se vuoi approfondire, clicca qui
Definiamo implicitamente \(b(N)\) per mezzo della relazione \[a(N) = \frac{N^2}{(\log N)^{b(N)}} \qquad\text{in modo che}\qquad b(N) = \frac{2 \log N}{\log\log N} – \frac{\log a(N)}{\log\log N}.\] Erdős ha dimostrato che \[\lim_{N \to + \infty} b(N) = b \qquad\text{dove}\qquad b = 1 – \frac{1 + \log\log 2}{\log 2} \approx 0.08607 \dots\] Questo non dà ancora una formula asintotica per \(a(N)\), perché non sappiamo quanto rapidamente la successione \(b(N)\) tende verso il suo limite \(b\). Per esempio, anche se sapessimo dimostrare che \[b – \frac1{\log\log N} \le b(N) \le b + \frac1{\log\log N}\] per \(N\) sufficientemente grande, tra il massimo e il minimo valore possibile per \(a(N)\) ci sarebbe pur sempre in ballo un fattore \(\mathrm{e}^2\) perché \((\log N)^{1 / \log\log N} = \mathrm{e}\) per ogni \(N > \mathrm{e}\) (provare per credere!); se \(b(N)\) converge verso il suo limite ancor piú lentamente, il fattore in ballo può essere illimitato, perché l’incertezza è amplificata dall’esponenziazione che è implicita nel passaggio da \(b(N)\) ad \(a(N)\). In effetti, Kevin Ford ha dimostrato nel 2008[1 ]K. Ford, The distribution of integers with a divisor in a given interval, Ann.
Math. 168 (2008), 367–433 una relazione molto piú precisa di quella di Erdős, che però è piú debole di una formula asintotica vera e propria. Per la precisione, Ford ha dimostrato che il rapporto \[\frac{a(N)}{N^2 / \bigl( (\log N)^b (\log\log N)^{3 / 2} \bigr)}\] è limitato dall’alto e dal basso da due costanti positive. Questo fornisce finalmente l’ordine di grandezza corretto per la funzione \(a(N)\), ed equivale a dire che la funzione \(b(N)\) introdotta qui sopra ha l’andamento \[b(N) = b + \frac32 \cdot \frac{\log\log\log N}{\log\log N} + \frac{\beta(N)}{\log\log N}\] quando \(N \to +\infty\), dove \(\beta(N)\) indica una funzione limitata non meglio specificata, cioè una funzione per la quale \(\vert \beta(N) \vert \le B\) per ogni \(N \ge 3\), per un opportuno numero reale positivo \(B\). Quindi le due costanti positive di cui parlavamo prima sono \(\mathrm{e}^{-B}\) ed \(\mathrm{e}^B\). Se si riuscisse a dimostrare che \(\beta\) è una funzione infinitesima si avrebbe automaticamente la formula asintotica cercata.
Chi conosce i risultati sulla distribuzione dei numeri primi, e in modo particolare quelli di Erdős, non resterà troppo stupito della presenza della funzione logaritmo iterata tre volte!
La densità degli interi sulla tavola pitagorica
Qui non entriamo nel dettaglio della dimostrazione di Ford, che studia in realtà un problema molto piú generale, ma possiamo accennare alle idee che Erdős ha usato nel suo primo articolo del 1955, dove ha dimostrato che \(a(N) = o(N^2)\) cioè, con un linguaggio leggermente piú semplice ma equivalente, che \[\lim_{N \to + \infty} \frac{a(N)}{N^2} = 0.\] In altre parole, di gran lunga la maggior parte degli interi fra 1 ed \(N^2\)non stanno nella tavola pitagorica \(N \times N\). Non è semplicissimo mettere i puntini sulle i (in linguaggio rigorosamente matematico, sistemare gli \(\varepsilon\) e i \(\delta\)) all’argomento “statistico” di Erdős, ma è possibile dare almeno l’idea dietro la dimostrazione, che usa un teorema di Hardy & Ramanujan sul numero medio di fattori primi dei numeri interi.
Userò le virgolette per indicare un termine che dovrei definire in modo rigoroso, e per il quale faccio invece appello all’intuizione. Non è troppo difficile dimostrare che un “tipico” intero \(n \in [3, N]\) ha circa \(\log\log N\) fattori primi in totale, contati con la loro molteplicità; per esempio, un “tipico” intero con \(1000\) cifre ha circa \(8\) fattori primi in totale poiché \(\log\log(10^{1000}) \approx 7.74\), mentre \(\log\log(10^{2000})
\approx 8.43\), e quindi un “tipico” intero con 2000 cifre ne ha quasi 8 e mezzo. Questa è una conseguenza di uno degli importanti teoremi di Frits Mertens sulla distribuzione dei numeri primi dimostrati nella seconda metà dell’ottocento. Un ruolo piuttosto importante in questo discorso è il fatto che la funzione \(\log \log N\) è molto lentamente crescente, come abbiamo appena visto con un esempio numerico.
Hardy & Ramanujan fecero un passo in piú, studiando la varianza della funzione che conta il numero totale dei fattori primi di un intero \(n\). Questa risulta piuttosto piccola e quindi possiamo rendere quantitativamente piú precisa l’affermazione qui sopra: il numero degli interi \(n \le N\) il cui numero totale dei fattori primi si discosta da \(\log \log N\) in modo significativo è a sua volta piuttosto piccolo.
Erdős ha classificato i numeri fino ad \(N^2\) come “regolari” o “eccezionali” se hanno o non hanno la proprietà di avere un numero totale di fattori primi molto vicino al valore atteso \(\log\log(N^2) = \log \log N + \log 2\). Dal Teorema di Hardy & Ramanujan sappiamo che la maggioranza degli interi fino ad \(N^2\) è regolare; piú precisamente, abbiamo una stima dall’alto per i numeri eccezionali che non superano \(N^2\).
Quanti fattori primi in totale ha un numero sulla tavola pitagorica \(N \times N\)? Se \(n = a \cdot b\) con \(a\), \(b \le N\), ciascuno degli interi \(a\), \(b\) ha “tipicamente” \(\log \log N\) fattori primi in totale e quindi \(n\) ha “tipicamente” \(2 \log \log N\) fattori primi in totale. Dunque un “tipico” intero \(n\) sulla tavola pitagorica \(N \times N\) ha circa il doppio dei fattori primi di un intero regolare e per questo motivo è eccezionale.
Come calcolare \(a(N)\)
Ho già citato in un mio articolo precedente[2 ]A. Zaccagnini, Code di rospo e denti di drago — Formule per i numeri primi, Sito web MaddMaths! (2019), Online dal 9.2.2019 l’Online Encyclopedia of Integer Sequences, all’indirizzo https://oeis.org, una vera miniera di informazioni sulle successioni di numeri interi. La sua origine è un libro pubblicato nel 1973, che conteneva 2372 successioni; al momento attuale, il sito recensisce piú di 250000 sequenze. La successione di cui abbiamo parlato si trova all’indirizzo https://oeis.org/A027424. I primi 15 termini sono dati dalla tabella
Quando \(N\) è un numero primo, \(a(N) = a(N – 1) + N\), perché la tavola pitagorica \((N – 1) \times (N – 1)\) non contiene multipli di \(N\), e gli \(N\) interi sull’\(N\)-esima riga sono tutti “nuovi.” Quando \(N\) non è primo è piú difficile calcolare \(a(N)\) a partire da \(a(N – 1)\), perché alcuni degli interi sull’\(N\)-esima riga compaiono già nella tavola pitagorica \((N – 1) \times (N – 1)\): il recente algoritmo di Brent, Pomerance, Purdum & Webster[3 ]Richard Brent, Carl Pomerance, David Purdum, & Jonathan Webster, Algorithms for the multiplication table problem, Arxiv preprint http://arxiv.org/abs/1908.04251, 2019 riesce a fare questo passaggio in modo efficiente ed è stato utilizzato per calcolare i termini della successione \(a(N)\) con \(N < 2^{30}\). Al centro dell’algoritmo c’è il nostro vecchio amico Crivello di Eratostene!
Un nuovo sguardo
Presentiamo per concludere la tavola pitagorica \(\mathcal{TP}(40)\), dove lo sfondo azzurro delle caselle è tanto piú scuro quante volte il numero corrispondente compare in totale sulla tavola pitagorica stessa.
In questo caso l’occhio è ingannato dai pochi numeri che compaiono molte volte e che quindi rendono la tavola pitagorica molto scura e apparentemente molto densa. Se invece scriviamo ciascun intero una sola volta, sulla “prima” riga su cui appare, il risultato è questo:
compaiono solo 517 dei 1600 possibili interi. Si vede bene quanto siano speciali i numeri primi perché, come abbiamo osservato all’inizio, se \(p\) è primo allora tutti i suoi multipli dallo stesso \(p\) a \(p^2\) compaiono in \(\mathcal{TP}(p)\) ma non compaiono in \(\mathcal{TP}(p – 1)\), e quindi \(a(p) = a(p – 1) + p\). Ma i numeri primi sono in un certo senso “atipici.” Se guardiamo la riga corrispondente ad un numero composto \(N\), vediamo che solo i suoi multipli relativamente grandi non comparivano in righe precedenti, e quindi \(a(N) – a(N – 1)\) è ben piú piccolo di \(N\). Questo ci dà una misura “visiva” della ragionevolezza del primo teorema di Erdős ricordato sopra.
Un’ultima riflessione, a suggello di questo articolo: perfino la tavola pitagorica, una delle cose piú semplici del mondo, non ha ancora rivelato tutti i suoi segreti!
Richard Brent, Carl Pomerance, David Purdum, & Jonathan Webster, Algorithms for the multiplication table problem, Arxiv preprint http://arxiv.org/abs/1908.04251, 2019
This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish.AcceptRead More
Privacy & Cookies Policy
Privacy Overview
This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
Può essere considerata: la proprietà invariantiva della sottrazione ? “In una sottrazione, se aggiungiamo o togliamo la stessa quantità al minuendo e al sottraendo, il risultato finale (cioè, la differenza) non cambia.” In ogni riga ed in ogni colonna il valore iniziale non cambia ed è la differenza che si ottiene tra caselle successive in cui la casella più lontana dal valore iniziale è il minuendo e la casella precedente è il sottraendo. https://books.google.it/books?id=hSL5DwAAQBAJ&pg=RA1-PR108&lpg=RA1-PR108&dq=zaccagnini+propriet%C3%A0+invariantiva+della+sottrazione&source=bl&ots=jSXr5wwt5l&sig=ACfU3U0sfaEJ8fBXA4cBpXGbnqGsA9R23A&hl=it&sa=X&ved=2ahUKEwj1qpf_58bvAhUJ4aQKHbFUA9sQ6AEwFXoECBYQAw#v=onepage&q=zaccagnini%20propriet%C3%A0%20invariantiva%20della%20sottrazione&f=false