I problemi posti da Erdős non finiscono mai. Recentemente c’è stato un notevole progresso su un una sua vecchia congettura sulla “densità” degli insieme di numeri interi. Per saperne di più e capire meglio di cosa si tratta lasciamo la parola al nostro Alessandro Zaccagnini.
Il matematico ungherese Pál Erdős, uno dei piú famosi del XX secolo, aveva l’abitudine di porre problemi. Alcuni di questi problemi possono sembrare molto semplici a prima vista, perché riguardano oggetti matematici ben noti come i numeri interi, i numeri primi, la divisibilità. Uno dei piú facili da enunciare riguarda una cosa familiare a tutti noi, e cioè la tavola pitagorica. In una tavola pitagorica \(N \times N\) ci sono \(N^2\) interi: quanti sono quelli distinti? Non si conosce ancora la risposta esatta. Ho parlato di vari di questi problemi, compreso quest’ultimo, proprio qui su MaddMaths!, negli articoli [1 ]A. Zaccagnini, 2015. “Terence Tao Dimostra Una Congettura Di Erdős (with a Little Help from His Friends).” Sito Web MaddMaths!https://maddmaths.simai.eu/divulgazione/focus/terence-tao-erdos/., [2 ]A. Zaccagnini, 2021. “La Tavola Pitagorica Come Non L’avete Mai Vista Prima!” Sito Web MaddMaths!https://maddmaths.simai.eu/divulgazione/focus/tavola-pitagorica/., [3 ]A. Zaccagnini, 2022. “Un Problema Di Erdős.” Sito Web MaddMaths!https://maddmaths.simai.eu/ricerca/un-problema-di-erdos/. e [4 ]A. Zaccagnini, 2023. “Un Vecchio Problema Di Erdős — Una Nuova Maggiorazione Nella Teoria Di Ramsey.” Sito Web MaddMaths!https://maddmaths.simai.eu/ricerca/erdos-ramsey/.. Il punto delle domande poste da Erdős è che la nostra conoscenza è piuttosto limitata anche in situazioni o ambiti che sembrano del tutto elementari. Recentemente c’è stato un progresso in uno di questi problemi: ce ne occupiamo in questo articolo. Ci chiediamo quanto debba essere “denso” un insieme di numeri interi positivi per essere sicuri che contenga qualche progressione aritmetica con un numero arbitrario di termini.
Cominciamo ricordando la definizione di progressione aritmetica: abbiamo un valore iniziale\(a\) e una ragione\(q\). Gli \(n\) numeri \(a\), \(a + q\), \(a + 2 q\), \(a + 3 q\), …, \(a + (n – 1) q\) costituiscono una progressione aritmetica con \(n\) termini. Due elementi consecutivi di una progressione differiscono per la stessa quantità \(q\). Nel seguito supporremo implicitamente che \(a\) e \(q\) siano numeri interi: in questo caso stiamo prendendo \(n\) interi consecutivi della classe di resto \(a\) modulo \(q\), cominciando proprio da \(a\). Per esempio, gli interi 1, 11, 21, 31, 41, 51, …, sono i primi termini di una progressione aritmetica di ragione \(q = 10\) e valore iniziale \(a = 1\).
Ci concentreremo sulle progressioni aritmetiche con tre termini, perché i recenti risultati di Thomas Bloom & Olof Sisask e di Zander Kelley & Raghu Meka riguardano proprio questo caso. Se \(x = a\), \(y = a + q\) e \(z = a + 2 q\) sono una progressione aritmetica con tre termini, possiamo notare che \(x + z = 2 y\). Il problema di cui parliamo riguarda l’esistenza di un’infinità di progressioni aritmetiche con tre termini in un insieme \(\mathcal{A}\) di numeri interi positivi, e in particolare di condizioni sufficienti sull’insieme \(\mathcal{A}\) affinché questa affermazione sia certamente vera. Possiamo dunque formulare questo problema in termini di risolubilità dell’equazione qui sopra: vogliamo sapere se è vero che l’equazione \[x + z = 2 y
\qquad\text{con $x, y, z \in \mathcal{A}$}\] ha infinite soluzioni o meno. La risposta non è scontata come vediamo per mezzo di alcuni esempi. Per comodità, talvolta consideriamo l’insieme \(\mathcal{A}\) come una successione crescente di interi positivi: \(\mathcal{A}= \{ a_1, a_2, a_3, \dots \}\) con la convenzione che \(a_1 < a_2 < a_3 < \dots\).
Non ci sono progressioni aritmetiche nell’insieme delle potenze di 2: infatti dovremmo avere \(2^a + 2^c = 2^{b + 1}\) con \(a > b \ge c \ge 0\), ma \(2^a + 2^c > 2^a \ge 2^{b + 1}\), e quindi l’equazione qui sopra non ha soluzioni. Questo ci dice che se l’insieme \(\mathcal{A}\) è una successione che cresce troppo velocemente può contenere solo un numero finito di progressioni aritmetiche con tre termini.
Anche i numeri di Fibonacci crescono esponenzialmente, come ci ricorda la formula di Binet, eppure contengono infinite progressioni aritmetiche a 3 termini, poiché \(f_{n + 3} + f_n = 2 f_{n + 2}\) per ogni \(n\). Il motivo è che questa successione, per quanto essenzialmente esponenziale, si ha \(f_{n + 1} < 2 f_n\) e questo è appena sufficiente a far sí che il problema dato abbia infinite soluzioni.
Che dire dei quadrati perfetti? In questo caso l’equazione \(a^2 – b^2 = b^2 – c^2\) ha infinite soluzioni, perfino aggiungendo il vincolo supplementare \(c = 1\)! Sapete trovarne qualcuna? L’equazione \(a^2 – 2 b^2 = \pm 1\) ha preso tradizionalmente il nome di Pell, per uno di quegli strani equivoci che talvolta capitano in matematica. Si tratta di un’equazione estremamente interessante, con una storia che risale agli albori della matematica, e le dedicherò un articolo in futuro.
Questi esempi mostrano che una condizione necessaria affinché \(\mathcal{A}\) contenga infinite progressioni aritmetiche con tre termini non è per niente ovvia; però l’esempio con le potenze di 2 mostra che l’insieme non può essere troppo rado, cioè la successione corrispondente crescere troppo in fretta.
Il problema di Erdős riguarda invece una possibile condizione sufficiente, cioè una condizione che, se soddisfatta, garantisca la tesi. Questa condizione riguarda la densità di un insieme \(\mathcal{A}\) di numeri naturali; in un certo senso, vogliamo misurare se possibile quanto sono frequenti i valori dell’insieme \(\mathcal{A}\) nell’insieme dei numeri naturali. Diamo una definizione informale; piú avanti metteremo qualche puntino sulle i, anche perché le definizioni possibili sono molte. Il concetto di densità è piuttosto elusivo: cominciamo con qualche esempio semplice per poi passare a casi piú impegnativi. I numeri pari hanno densità \(\frac12\), i numeri primi e i quadrati perfetti hanno densità \(0\), ed esistono insiemi che non hanno densità. Informalmente, la densità di un insieme ci dice qual è la probabilità che “pescando” a caso uno fra i primi \(N\) numeri interi, come se giocassimo a tombola, troviamo un numero appartenente all’insieme \(\mathcal{A}\) stesso, quando \(N\) è molto grande.
Proviamo a formalizzare: abbiamo un insieme \(\mathcal{A}\subseteq \mathbb{N}\). Per \(N \ge 1\) intero, consideriamo \(A(N) = \bigl\vert \mathcal{A}\cap [1, N] \bigr\vert\), cioè il numero degli elementi di \(\mathcal{A}\) che non superano \(N\). Questo ci dà la successione di numeri interi \(A(N)\) e calcoliamo il \[\lim_{N \to +\infty}
\frac{\bigl\vert \mathcal{A}\cap [1, N] \bigr\vert}N
=
\lim_{N \to +\infty}
\frac{A(N)}N,\] se questo limite esiste e vale \(\delta \in [0, 1]\). In questo caso diremo che \(\mathcal{A}\) ha densità naturale, o piú brevemente densità, \(\delta\). Per esempio, i numeri che terminano con la cifra 1 hanno densità \(\frac1{10}\) e in generale gli interi in una progressione aritmetica di ragione \(q\) hanno densità \(1 / q\): come abbiamo osservato prima, in sostanza prendiamo una classe di resto modulo \(q\). Dal Teorema dei Numeri Primi sappiamo che ci sono circa \(N / \log(N)\) numeri primi che non superano \(N\), e quindi la densità dei numeri primi è 0; è facile vedere che ci sono circa \(\sqrt{N}\) quadrati perfetti che non superano \(N\) e quindi anche la densità dei quadrati perfetti è 0, cosí come quella dei cubi o delle potenze di 2. Faccio notare esplicitamente che, anche in questo caso come in molti di quelli interessanti, c’è una interazione tra aritmetica, rappresentata dall’insieme \(\mathcal{A}\), e l’analisi matematica, dato che parliamo di limiti.
Nell’appendice matematica potete trovare un approfondimento sulla densità, compresa la “costruzione” di insiemi \(\mathcal{A}\) di densità assegnata cosí come di insiemi che non hanno densità. Qui ci limitiamo a osservare che ai nostri fini basta una proprietà piú debole dell’avere densità: l’insieme \(\mathcal{A}\) ha densità \(\delta \in (0, 1]\) se per \(N\) grande nell’intervallo \([1, N]\) ci sono circa \(\delta N\) elementi di \(\mathcal{A}\). Ebbene, per noi è sufficiente che per \(N\) grande nell’intervallo \([1, N]\) ci siano almeno\(\delta N\) elementi di \(\mathcal{A}\), per qualche \(\delta > 0\); se \(\delta\) è il massimo (meglio, l’estremo superiore) dei numeri con questa proprietà, diremo che \(\mathcal{A}\) ha densità inferiore\(\delta\).
Se la densità inferiore di un insieme \(\mathcal{A}\) è positiva, in un certo senso l’insieme contiene una progressione aritmetica “perturbata” ed è ragionevole pensare che l’insieme \(\mathcal{A}\) contenga tanti termini in progressione aritmetica, come si vede nell’esempio dell’insieme con densità \(1 / \sqrt{2}\) o nell’esempio dei numeri con prima cifra uguale ad 1, per i quali rimandiamo all’appendice.
Ben diverso è il discorso se la densità è nulla: in questo caso ci sono infinite possibilità qualitativamente diverse, come abbiamo visto sopra quando abbiamo parlato di numeri primi, quadrati, potenze, numeri di Fibonacci, o anche numeri fattoriali … La domanda di Erdős è questa: quali ipotesi alternativa dobbiamo fare su un insieme \(\mathcal{A}\) di densità nulla per garantire che contenga una progressione aritmetica arbitrariamente lunga? Una semplice formulazione della sua congettura riguarda una definizione di densità piú ampia di quella che abbiamo visto, e di cui ho già parlato in [5 ]A. Zaccagnini, 2022. “Un Problema Di Erdős.” Sito Web MaddMaths!https://maddmaths.simai.eu/ricerca/un-problema-di-erdos/.. Senza entrare in troppi dettagli, Erdős ha congetturato che se la serie \[\sum_{n \ge 1, \ n \in \mathcal{A}} \frac1n\] è divergente, allora l’insieme \(\mathcal{A}\) contiene progressioni aritmetiche arbitrariamente lunghe. È facile vedere che la serie qui sopra diverge se \(\mathcal{A}\) ha densità inferiore positiva, ma diverge anche per alcuni insiemi con densità nulla. Nel caso dei numeri primi, per cui la serie è divergente come dimostrato da Eulero nel XVIII secolo, la congettura di Erdős è stata dimostrata da Ben Green e Terence Tao in un importantissimo articolo pubblicato nel 2008 [6 ]Ben Green & Terence Tao. 2008. “The Primes Contain Arbitrarily Long Arithmetic Progressions.” Ann. Math., 2nd ser., 167 (2): 481–547..
I recenti lavori a cui ho alluso sopra, e cioè gli articoli di Bloom & Sisask [7 ]T. F. Bloom & O. Sisask. 2020. “Breaking the Logarithmic Barrier in Roth’s Theorem on Arithmetic Progressions.” https://arxiv.org/abs/2007.03528., Kelley & Meka [8 ]Z. Kelley & R. Meka. 2023. “Strong Bounds for 3-Progressions.” https://arxiv.org/abs/2302.05537., Bloom & Sisask [9 ]T. F. Bloom & O. Sisask, 2023. “The Kelley-Meka Bounds for Sets Free of Three-Term Arithmetic Progressions.” https://arxiv.org/abs/2302.07211., danno una risposta positiva per progressioni con tre termini. In realtà, tutti i risultati citati sono piú forti e la dimostrazione della congettura di Erdős con tre termini è un loro semplice corollario, ma la dimostrazione dei loro teoremi è piuttosto complicata e non è chiaro se si potranno estendere per fare un ulteriore passo avanti verso la dimostrazione completa della congettura di Erdős.
Approfondimenti: per saperne di più
clicca per leggere
Costruiamo un insieme di densità assegnata \(\delta \in (0, 1]\). Se \(\delta\) è razionale è facile e vediamo due diverse costruzioni. Se, poniamo, \(\delta = \frac35\), possiamo prendere a piacere 3 classi di resto modulo 5. Per esempio, se scegliamo le classi 1, 2, 4, l’insieme \[\mathcal{A} = \{ n \in \mathbb{N}\colon n \equiv 1, 2, 4 \bmod 5 \}\] contiene 3 interi ogni 5 ed ha densità \(\frac35\). Una costruzione alternativa è questa; prendiamo la funzione \(f(x) = \lfloor 5 x / 3 \rfloor\), dove \(\lfloor x \rfloor\) indica la parte intera del numero reale \(x\), e come insieme \(\mathcal{A}\) prendiamo l’immagine di \(f\) e cioè l’insieme \(\{ f(1), f(2), f(3), \dots \} = \{ 1, 3, 5, 6, 8, 10, \dots \}\). In effetti, stiamo prendendo gli elementi delle tre classi 0, 1, 3 modulo 5. In entrambi i casi, è facile vedere che \(A(N + 5) = A(N) + 3\) e quindi \(A(5 M) = 3 M\) per ogni intero \(M \ge 1\), per induzione. Se \(\delta\) è irrazionale non possiamo prendere esattamente 1 intero ogni \(1 / \delta\), ma possiamo pur sempre riutilizzare la seconda idea presentata qui sopra considerando l’insieme \(\mathcal{A}_\delta = \{ f(1), f(2), f(3), \dots \}\) dove \(f(x) = \lfloor x / \delta \rfloor\). Per esempio, un insieme con densità \(\delta = 1 / \sqrt{2}\) è \(\{ 1\), \(2\), \(4\), 5, 7, 8, 9, 11, 12, 14, 15, 16, 18, 19, \(\dots \}\). La funzione \(f\) trasforma gli interi 1, 2, …, \(M\) in \(M\) interi distinti nell’intervallo \([1, M / \delta]\) (distinti perché \(\delta \le 1\)); in altre parole, l’ultimo intervallo menzionato contiene \(M\) elementi dell’insieme \(\mathcal{A}_\delta\) e quindi \(\vert \mathcal{A}_\delta \cap [1, M / \delta] \vert / (M / \delta) \approx \delta\) per \(M\) grande. Vediamo ora un insieme che non ha densità, cioè un insieme per il quale il limite qui sopra non esiste. Proviamo a pensare ai numeri interi che hanno la prima cifra uguale ad 1. Quanti ce ne sono fino ad \(N = 1999\)? Sono il numero 1, gli interi da 10 a 19, quelli da 100 a 199 e quelli da 1000 a 1999; in totale \(1 + 10 + 100 + 1000 = 1111\), quindi circa il 56% dei primi 1999 interi. Quanti ce ne sono fino a \(N = 9999\)? Gli stessi di prima, quindi circa l’11% dei primi 9999 interi. In generale, chiamiamo densità inferiore e superiore dell’insieme \(\mathcal{A}\) i valori \[\underline{\delta}(\mathcal{A}) = \liminf_{N \to +\infty} \frac{\bigl\vert \mathcal{A}\cap [1, N] \bigr\vert}N, \qquad \overline{\delta}(\mathcal{A}) = \limsup_{N \to +\infty} \frac{\bigl\vert \mathcal{A}\cap [1, N] \bigr\vert}N.\] Naturalmente \(\underline{\delta}(\mathcal{A}) \le \overline{\delta}(\mathcal{A})\) qualunque sia l’insieme \(\mathcal{A}\); nell’insieme dei numeri interi che hanno prima cifra uguale ad 1 i due valori sono diversi, \(1 / 9\) e \(5 / 9\) rispettivamente. A me piace molto questo insieme, perché ci dà un esempio non troppo artificioso di una successione che ha minimo e massimo limite differenti. Usando successioni velocemente crescenti possiamo costruire insiemi che hanno contemporaneamente densità inferiore 0 e superiore 1. Con un po’ di ingegno possiamo costruire insiemi con prescritte densità inferiore e superiore. La densità introdotta da Erdős non è quella naturale, ma piuttosto quella cosiddetta logaritmica: ne ho parlato anche in [10 ]A. Zaccagnini, 2022. “Grafi E Numeri Primi.” Sito Web MaddMaths!https://maddmaths.simai.eu/ricerca/grafi-e-numeri-primi/.. Il nome deriva dal fatto che \[\sum_{n = 1}^N \frac1n \sim \log(N)\] quando \(N \to \infty\). Nel caso dell’insieme \(\mathcal{A}\) dei numeri naturali che hanno la prima cifra uguale ad 1, che come abbiamo visto sopra, non ha densità naturale, con qualche calcolo si può vedere che \[\sum_{n = 1, \ n \in \mathcal{A}}^N \frac1n \sim \frac{\log(2)}{\log(10)} \cdot \log(N).\] Quindi il concetto di densità naturale si estende ad altri insiemi che ne sono privi.
[Immagine di copertina creata con Bing Image creator]
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.
