Extremal densities for forbidden configurations in $S$-smooth numbers

1. Il Problema di Ricerca

Il lavoro si concentra su un problema di teoria dei numeri combinatoria e di densità estrema, generalizzando un classico problema introdotto da Graham, Witsenhausen e Spencer.

• Contesto: Sia $S = \{p_1, \dots, p_r\}$ un insieme finito di primi distinti ($r \ge 2$). Si definisce $M(S)$ il semigruppo moltiplicativo generato da $S$, i cui elementi sono i numeri $S$-lisci (numeri i cui fattori primi appartengono tutti a $S$).
• Obiettivo: Studiare la massima densità di un sottoinsieme $A$ di numeri $S$-lisci (limitati da $X$ o dai primi $k$ numeri $S$-lisci) che non contenga alcuna configurazione proibita della forma $\{n, p_1n, \dots, p_rn\}$.
• Definizioni Chiave:
  • $\Psi_S(X)$: Funzione di conteggio dei numeri $S$-lisci $\le X$.
  • $F_S(X)$: La massima cardinalità di un sottoinsieme di $M(S) \cap [1, X]$ privo della configurazione proibita.
  • $f_S(k)$: La massima cardinalità di un sottoinsieme dei primi $k$ numeri $S$-lisci privo della configurazione.
  • $G_S(N)$: La versione del problema sull'intervallo intero $[1, N]$ (non solo numeri $S$-lisci).

2. Metodologia

L'autore utilizza un approccio ibrido che combina teoria dei numeri analitica, geometria dei numeri e tecniche combinatorie.

• Trasformazione in Geometria: Il problema viene mappato nello spazio degli esponenti. Un numero $S$-lisso $n = p_1^{a_1} \dots p_r^{a_r}$ corrisponde a un vettore $(a_1, \dots, a_r) \in \mathbb{Z}_{\ge 0}^r$. La configurazione proibita $\{n, p_1n, \dots, p_rn\}$ corrisponde geometricamente a un "angolo unitario" (o "unit corner") nel reticolo: $\{a, a+e_1, \dots, a+e_r\}$, dove $e_i$ sono i vettori della base standard.
• Semplici Pesati: L'insieme dei numeri $S$-lisci $\le X$ corrisponde a un simplex reticolare pesato $\Sigma_S(u)$ definito da $\sum a_i \log p_i \le \log X$. Il problema diventa quindi trovare il più grande sottogruppo di $\Sigma_S(u)$ privo di angoli unitari.
• Stime Asintotiche:
  • Limite Inferiore: Utilizza un argomento di colorazione modulare. Definisce una colorazione $\chi(a) = \sum i \cdot a_i \pmod{r+1}$. Poiché ogni angolo unitario contiene esattamente un punto di ogni colore, rimuovendo la classe di colore più piccola si ottiene un insieme valido. Questo fornisce un limite inferiore di $\frac{r}{r+1}$.
  • Limite Superiore: Utilizza un'identità combinatoria basata su shift indietro (backward shifts) e conteggi di punti sui bordi del simplex per dimostrare che non si può superare significativamente la frazione $\frac{r}{r+1}$.
• Analisi Asintotica: Applica il teorema di Hardy-Ramanujan generalizzato (o stime classiche per i numeri lisci) per stimare la cardinalità del simplex $\Sigma_S(u)$.

3. Risultati Principali

A. Formula Asintotica per Numeri $S$-Lisci (Teorema 1.1)

Il risultato centrale è una formula asintotica precisa per $F_S(X)$ e $f_S(k)$:
$$F_S(X) = \frac{r}{r+1}\Psi_S(X) + O_S((\log X)^{r-1})$$
In termini di indice $k$ (dove $k \approx \Psi_S(X)$):
$$f_S(k) = \frac{r}{r+1}k + O_S(k^{(r-1)/r})$$
Ciò dimostra che la densità asintotica all'interno dell'insieme dei numeri $S$-lisci è esattamente $\frac{r}{r+1}$.

B. Densità sull'Intervallo Intero e Costante $\alpha_S$ (Corollario 1.2 e 1.3)

Il paper estende il risultato all'intervallo intero $[1, N]$, definendo $G_S(N)$. Viene provato che esiste una costante di densità $\alpha_S$ tale che:
$$G_S(N) = \alpha_S N + O_S((\log N)^r)$$
La costante $\alpha_S$ è data da:
$$\alpha_S = c_S \sum_{k \ge 1} \frac{\Delta f_S(k)}{d_k^{(S)}}$$
dove $c_S = \prod_{p \in S} (1 - 1/p)$ e $\Delta f_S(k) \in \{0, 1\}$ indica se il $k$-esimo numero $S$-lisso può essere aggiunto a un insieme ottimo.

• Stima Computabile: Vengono forniti limiti inferiori ($L_{S,N}$) e superiori ($U_{S,N}$) nidificati per calcolare $\alpha_S$ con precisione arbitraria, basati sulla somma delle code reciproche dei numeri $S$-lisci.

C. Sums Reciproche Non Periodiche (Proposizione 1.4)

Un risultato controintuitivo mostra che somme reciproche razionali su denominatori $S$-lisci non necessariamente derivano da sequenze binarie eventualmente periodiche.

• Viene costruita una sequenza binaria $(c_k)$ tale che $\sum \frac{c_k}{d_k^{(S)}} \in \mathbb{Q}$, ma la sequenza $(c_k)$ non è eventualmente periodica. Questo sfida l'intuizione comune sulla razionalità delle serie su insiemi moltiplicativi.

D. Caso Classico $S=\{2, 3\}$

Per il caso specifico dei numeri 3-lisci (numeri della forma $2^a 3^b$), l'autore:

• Recupera la costante classica di Graham-Spencer-Witsenhausen $\alpha = \alpha_{\{2,3\}}$.
• Deriva una formula esplicita per la coda della serie reciproca.
• Dimostra che non esiste una famiglia ottima nidificata ($A_1 \subseteq A_2 \subseteq \dots$) per questo caso, mostrando che la struttura degli insiemi ottimali non è monotona rispetto all'aggiunta di nuovi elementi.

4. Significato e Contributi

1. Generalizzazione: Estende i risultati noti per $S=\{2, 3\}$ a qualsiasi insieme finito di primi, fornendo una formula universale per la densità estrema $\frac{r}{r+1}$.
2. Precisione Asintotica: Fornisce non solo il termine principale, ma anche stime precise sull'errore ($O((\log X)^{r-1})$), collegando la teoria dei numeri lisci alla combinatoria estrema.
3. Strumenti Computazionali: Offre un metodo pratico e rigoroso per calcolare la costante di densità $\alpha_S$ per qualsiasi insieme $S$, utilizzando somme parziali e stime di code.
4. Teoria delle Serie: Contribuisce alla comprensione della struttura delle somme reciproche su semigruppi moltiplicativi, dimostrando che la razionalità non implica periodicità nella sequenza dei coefficienti.
5. Connessione Geometrica: Stabilisce un ponte chiaro tra problemi di "pattern avoidance" moltiplicativi e problemi di impacchettamento di angoli unitari in semplici reticolari pesati.

In sintesi, il paper risolve un problema aperto di lunga data sulla densità di insiemi privi di configurazioni moltiplicative all'interno dei numeri lisci, fornendo sia risultati teorici profondi che strumenti computazionali pratici.