🔢 mathematics

Solution of Erd\H{o}s problem $\# 443$

Questo articolo risolve il problema n. 443 di Erdős dimostrando che la dimensione dell'intersezione tra gli insiemi di prodotti $\{k(m-k)\}$ e $\{l(n-l)\}$ è limitata da $(mn)^{o(1)}$ ma può comunque essere arbitrariamente grande.

Autori originali: Stijn Cambie

Pubblicato 2026-07-29

📖 4 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Stijn Cambie

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immaginate un mondo in cui i numeri non sono solo cifre fredde e dure, ma veri e propri giocatori in un gigantesco e invisibile gioco di nascondino. Questo è il regno della teoria dei numeri, un ramo della matematica che tratta gli interi come personaggi unici dotati di identità segrete. In questo gioco, spesso osserviamo degli "insiemi" — che non sono altro che parole altisonanti per indicare collezioni di numeri — creati seguendo una regola specifica. Per esempio, se prendete un numero, lo moltiplicate per il suo partner (il numero che, sommato all'altro, dà un totale determinato) e elencate tutti i risultati, otterrete un modello unico. I matematici amano chiedersi: "Se creo due modelli diversi usando regole diverse, quanti numeri avranno in comune?". È come chiedere quanti termini compaiono sia in un dizionario di poesia antica che in un dizionario di gergo moderno. La domanda può sembrare un rompicapo per un club di matematica, ma ci aiuta a comprendere l'architettura nascosta dei numeri, rivelando se i modelli siano rari, comuni o completamente imprevedibili.

Il documento di cui starete per sentire parlare affronta un enigma specifico posto dal leggendario matematico Paul Erdős. Egli si interrogava su due collezioni speciali di numeri. La prima collezione è composta prendendo un numero $m$ , scegliendo un numero più piccolo $k$ (da 1 fino a metà di $m$ ) e calcolando il prodotto $k(m-k)$ . La seconda collezione fa esattamente la stessa cosa, ma con un numero diverso, $n$ . La grande domanda è: man mano che questi numeri diventano enormi, quanti "amici comuni" (numeri che compaiono in entrambi gli elenchi) possono condividere? Erdős ipotizzò che, sebbene il numero di amici condivisi possa crescere, lo farebbe molto lentamente — così lentamente che, per qualsiasi minimo margine di errore scegliate, il conteggio sarebbe alla fine inferiore a una specifica formula matematica che coinvolge la dimensione dei numeri. Chiese anche se questo numero di amici condivisi potesse crescere senza mai fermarsi, o se avrebbe incontrato un soffitto.

L'autore di questo articolo, Stijn Cambie, agisce come un detective che risolve questo mistero vecchio di decenni. Egli conferma che il numero di amici condivisi è effettivamente illimitato, il che significa che può diventare grande quanto si desidera se si scelgono i numeri $m$ e $n$ giusti. Per dimostarlo, utilizza un trucco astuto: mostra che trovare un numero condiviso equivale a trovare un modo per scomporre una specifica differenza di quadrati in due pezzi più piccoli. Questo trasforma il problema nel conteggio dei "divisori" (i mattoni fondamentali) di un numero. Poiché sappiamo che alcuni numeri hanno un numero enorme di divisori, Cambie dimostra che possiamo sempre trovare coppie di $m$ e $n$ che creano un numero massiccio di amici condivisi.

Tuttavia, l'articolo impone anche un limite di velocità rigoroso a questa crescita. Cambie dimostra che, sebbene il numero di amici condivisi possa diventare enorme, esso cresce incredibilmente lentamente — così lentamente da rientrare nell'ipotesi del "margine minimo" fatta da Erdős. Egli mostra che il conteggio è limitato da una funzione che è essenzialmente "quasi costante" rispetto alla dimensione dei numeri coinvolti. In parole povere, anche se scegliete i numeri migliori per massimizzare la sovrapposizione, il numero di amici condivisi non esploderà mai; rimarrà sempre una minuscola frazione del totale dei numeri coinvolti.

Interessante è la svolta che il documento rivela nella storia: questo problema non era in realtà una nuova scoperta. L'autore nota che un matematico di nome Norbert Hegyvári aveva risolto esattamente questo problema 40 anni prima, ma la sua prova è stata pubblicata solo di recente. Quindi, mentre questo articolo fornisce una spiegazione fresca e chiara e conferma la risposta, lo stato di problema "risolto" appartiene in realtà a quel lavoro precedente, rimasto a lungo nascosto. Il documento non si limita a ipotizzare; fornisce una prova matematica, mostrando esattamente come si comporta il numero di amici condivisi e confermando che è sia illimitato che sorprendentemente piccolo rispetto alla dimensione dei numeri utilizzati.

Sintesi Tecnica: Soluzione del Problema di Erdős #443

Enunciato del Problema
Questo articolo affronta il Problema #443 posto da Erdős e Graham nel loro lavoro del 1980 [1]. Il problema riguarda due insiemi di interi generati dalle forme quadratiche $k(m-k)$ e $\ell(n-\ell)$ , dove $1 \le k \le m/2$ e $1 \le \ell \le n/2$ . Nello specifico, sia $S(m) = \{k(m-k) : 1 \le k \le m/2\}$ e $S(n) = \{\ell(n-\ell) : 1 \le \ell \le n/2\}$ . Le questioni centrali sono:

È possibile stimare il numero di interi comuni, denotato con $f(n, m) = \#(S(m) \cap S(n))$ ?
Tale numero è illimitato al variare di $m$ e $n$ ?
Il numero di elementi comuni è strettamente minore di $(mn)^\epsilon$ per ogni $\epsilon > 0$ quando $mn$ è sufficientemente grande?

Metodologia e Deduzione
L'autore, Stijn Cambie, adotta la notazione $f(n, m)$ e assume, senza perdita di generalità, che $m > n$ . Il nucleo della metodologia consiste nel trasformare la condizione di intersezione in una differenza di quadrati.

Osservando che $k(2m-k) = m^2 - (m-k)^2$ , l'autore pone $c = m-k$ . La condizione affinché un intero appartenga a entrambi gli insiemi, $k(2m-k) = \ell(2n-\ell)$ , viene riscritta come:
$m^2 - c^2 = n^2 - d^2$
dove $d = n-\ell$ . Riorganizzando i termini si ottiene:
$m^2 - n^2 = c^2 - d^2 = (c-d)(c+d)$
Questa trasformazione dimostra che il numero di soluzioni è limitato dalla metà del numero di divisori dell'intero $m^2 - n^2$ , denotato con $\tau(m^2 - n^2)$ . La restrizione che $c-d$ debba essere un divisore limitato da $\sqrt{m^2 - n^2}$ viene utilizzata per stabilire questo limite.

Risultati Chiave

Limite Superiore: L'articolo stabilisce che $f(n, m) \le \lfloor \tau(m^2 - n^2) / 2 \rfloor$ . Invocando il noto risultato relativo alla funzione divisore $\tau(x)$ , il quale afferma che $\tau(x) \le 2^{(1+o(1))\frac{\log x}{\log \log x}} = x^{o(1)}$ , l'autore conferma che $f(n, m) = (mn)^{o(1)}$ . Ciò conferma la congettura secondo cui il numero di interi comuni è minore di $(mn)^\epsilon$ per ogni $\epsilon > 0$ quando $mn$ è sufficientemente grande.
Illimitatezza: Per affrontare se il numero di interi comuni sia illimitato, l'autore considera il caso specifico in cui $m = n+1$ . In questo scenario, $m^2 - n^2 = 2n+1$ . Si mostra che il numero di soluzioni è correlato a $\lfloor \tau(2n+1)/2 \rfloor - 1$ . Poiché $\tau(x)$ è illimitato (raggiungendo valori elevati per numeri altamente composti), $f(2n+2, 2n)$ è illimitato. La costruzione mappa esplicitamente le fattorizzazioni di $2n+1 = pq$ (con $p \ge q \ge 2$ ) in soluzioni intere valide per $c$ e $d$ .

Significato e Rivendicazioni
L'articolo sostiene di fornire una soluzione completa al Problema di Erdős #443, confermando sia il tasso di crescita sub-polinomiale della dimensione dell'intersezione sia la sua natura illimitata.

L'autore include una nota specifica riguardante la storia della soluzione: Norbert Hegyvári [2] ha risolto questo problema indipendentemente 40 anni prima della pubblicazione di questa nota. Tuttavia, la prova di Hegyvári è stata pubblicata solo di recente, dopo la sottomissione di questa nota. L'articolo si pone come una verifica indipendente e una soluzione al problema, pur riconoscendo il lavoro precedente e ritardato di Hegyvári.

Riferimenti Citati nel Paper

[1] P. Erdős e R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, 1980.
[2] N. Hegyvári, (Soluzione del problema, pubblicata di recente).
[3] Risultato standard sulla funzione divisore $\tau(x)$ .

Articoli simili