Multiplication Tables for Integers with Restricted Prime Factors

1. Contexte et Problématique

Le papier s'inscrit dans le cadre de la théorie probabiliste des nombres, en généralisant un résultat fondamental établi par Kevin Ford en 2008 concernant le problème de la table de multiplication d'Erdős.

• Le problème classique : Ford a déterminé l'ordre de grandeur du nombre d'entiers $H(x, y, 2y) \le x$ possédant un diviseur dans l'intervalle $(y, 2y]$. Pour $y \approx \sqrt{x}$, ce nombre est de l'ordre de $\frac{x}{(\log y)^\eta (\log \log y)^{3/2}}$, où $\eta = 1 - \frac{1+\log \log 2}{\log 2}$. Cela permet de résoudre le problème de la taille de la table de multiplication $A(N) = |\{ab : a,b \le N\}|$.
• La généralisation : L'objectif de Schlitt est d'étudier ce problème lorsque les entiers considérés sont restreints à un ensemble $S_Q$ dont les facteurs premiers appartiennent à un sous-ensemble infini $Q$ des nombres premiers.
• Hypothèse sur $Q$ : L'ensemble $Q$ possède une densité relative $\delta \in (0, 1]$. Plus précisément, le nombre d'éléments de $Q$ jusqu'à $x$ est approximé par $\frac{\delta x}{\log x}$ avec une erreur contrôlée.
  • Si $\delta = 1$, on retrouve le cas classique de Ford (tous les nombres premiers).
  • Si $\delta < 1$, on étudie des ensembles plus "rares" (par exemple, les entiers sans facteur premier dans certaines classes de congruence).

Le but est de déterminer l'ordre de grandeur de $H_Q(x, y, 2y)$, le nombre d'entiers dans $S_Q \cap [1, x]$ ayant un diviseur dans $(y, 2y]$, et d'en déduire la taille de la table de multiplication restreinte $A_Q(N) = |\{ab : a, b \in S_Q \cap [1, N]\}|$.

2. Méthodologie

La preuve suit la structure générale des travaux de Ford mais introduit des innovations techniques significatives, notamment dans la gestion des conditions aux limites géométriques.

A. Réduction à une somme de type Poisson

Le problème est d'abord réduit à l'estimation d'une somme combinatoire impliquant la fonction $L(a)$, qui mesure la "proximité" des diviseurs d'un entier $a$ (la mesure de Lebesgue de l'ensemble des $\log d$ pour $d|a$).
La quantité $H_Q(x, y, 2y)$ est liée à une somme de la forme :
$$\sum_{k} \frac{\lambda^k}{k!} \cdot \frac{v-k+1}{v}$$
où $\lambda = 2\delta \log \log y$ et $v = \lfloor \frac{1}{\log 2} \log \log y \rfloor$.

B. Bornes Inférieures et Conditions de Barrière

Pour établir la borne inférieure, l'auteur utilise une inégalité de Cauchy-Schwarz sur la fonction $L(a)$.

• Construction géométrique : L'auteur définit des ensembles d'entiers basés sur la répartition de leurs facteurs premiers dans des intervalles spécifiques.
• Innovation majeure : Contrairement aux travaux antérieurs (Ford, Koukoulopoulos) qui utilisaient des contraintes algébriques implicites, Schlitt impose des conditions de barrière fortes explicites sur les statistiques d'ordre normalisées. Il définit une région géométrique $Y_k(\tilde{v}, C)$ où les statistiques d'ordre $\xi_i$ doivent repousser la moyenne $i$ d'une marge de l'ordre de $(\min\{i, k-i\})^{1/7}$.
• Lien avec la théorie des probabilités : Cette approche exploite le phénomène selon lequel les marches aléatoires conditionnées à respecter une barrière faible respectent avec haute probabilité une barrière beaucoup plus forte. Cela permet d'utiliser des bornes précises sur les statistiques de Smirnov généralisées (Lemme 6.2).

C. Bornes Supérieures

La borne supérieure repose sur la décomposition des entiers en facteurs premiers et l'utilisation de la fonction $L(a)$ pour majorer la contribution des entiers ayant un diviseur dans l'intervalle cible. L'auteur partitionne la somme selon le nombre de facteurs premiers $\omega(a) = k$ et utilise des intégrales de volume multivariées $U_k(v)$ déjà étudiées par Ford et Koukoulopoulos, en fournissant des estimations précises pour ces volumes.

D. Analyse de la Transition de Phase

Une partie cruciale de la preuve (Section 5) consiste à analyser le comportement de la somme Poissonienne $\sum \frac{\lambda^k}{k!} \frac{v-k+1}{v}$ lorsque le paramètre $\lambda$ varie par rapport à $v$. L'auteur identifie un point critique $\lambda = v$, qui correspond à $\delta = \frac{1}{\log 4}$.

3. Résultats Principaux

Le théorème principal (Théorème 1.2) établit l'ordre de grandeur de $H_Q(x, y, 2y)$ uniformément pour tout $\delta \ge c > 0$. Le résultat dépend de la valeur de $\delta$ par rapport au seuil critique $\delta_c = \frac{1}{\log 4} \approx 0.7213$.

La formule asymptotique est :
$$H_Q(x, y, 2y) \asymp \frac{x}{(\log x)^{1-\delta}} \cdot \frac{1}{(\log y)^{G(\delta)}} \cdot E(y; \delta)$$

Où :

1. L'exposant $G(\delta)$ :

   • Si $\delta \le \frac{1}{\log 4}$ : $G(\delta) = 1 - \delta$.
   • Si $\delta \ge \frac{1}{\log 4}$ : $G(\delta) = \delta - 1 + \frac{\log(\delta \log 2)}{\log 2}$.
   • La fonction $G(\delta)$ est dérivable au point critique, assurant une transition continue de l'exposant logarithmique.

2. Le terme de transition $E(y; \delta)$ :
   Ce terme capture le comportement fin près du point critique.

   • Pour $\delta < \frac{1}{\log 4}$, $E(y; \delta)$ est constant ou dépend faiblement de $\log \log y$.
   • Pour $\delta > \frac{1}{\log 4}$, $E(y; \delta)$ décroît comme $(\log \log y)^{-3/2}$, reproduisant le comportement classique de Ford (cas $\delta=1$).
   • Au point critique $\delta = \frac{1}{\log 4}$, une transition de phase se produit, caractérisée par un changement de régime dans la dépendance en $\log \log y$.

Conséquence sur les tables de multiplication (Corollaire 1.3) :
Pour la taille de la table de multiplication restreinte $A_Q(N)$, on obtient :
$$A_Q(N) \asymp \frac{N^2}{(\log N)^{G(\delta) - \delta + 1}} E(N; \delta)$$

Interprétation Combinatoire :

• Si $\delta < \frac{1}{\log 4}$ : La taille de l'ensemble des produits $|S_Q(N) \cdot S_Q(N)|$ est de l'ordre de $|S_Q(N)|^2$. Cela signifie que la plupart des produits sont distincts (pas de "collisions" massives).
• Si $\delta \ge \frac{1}{\log 4}$ : La taille est $o(|S_Q(N)|^2)$. Il y a une surcharge de collisions, et la table de multiplication devient "dense" de manière différente.

4. Contributions Clés et Signification

1. Généralisation du théorème de Ford : Le papier étend le résultat de 2008 à une famille infinie d'ensembles d'entiers définis par des densités de facteurs premiers arbitraires $\delta \in (0, 1]$.
2. Découverte d'une Transition de Phase : L'auteur identifie et caractérise explicitement un point critique $\delta = 1/\log 4$. Ce point marque la frontière entre un régime où les produits sont majoritairement distincts et un régime où les collisions dominent. Ce seuil est lié à la structure des statistiques d'ordre des facteurs premiers.
3. Nouvelle Approche Géométrique : L'utilisation de conditions de barrière fortes explicites pour les statistiques d'ordre (au lieu de contraintes algébriques implicites) constitue une avancée méthodologique. Elle rend explicite le mécanisme géométrique sous-jacent aux bornes inférieures et simplifie l'application des résultats probabilistes classiques (statistiques de Smirnov).
4. Connexions Interdisciplinaires : Le résultat a des implications pour la théorie des marches aléatoires, les statistiques d'ordre, et la théorie des nombres probabiliste. Il répond également à des questions soulevées dans des travaux récents de Soundararajan, Xu et Ford sur les ensembles de produits et les fonctions multiplicatives aléatoires.

En résumé, ce papier fournit une compréhension complète et fine de la structure des diviseurs et des tables de multiplication pour des ensembles d'entiers à facteurs premiers restreints, révélant une transition de phase subtile mais fondamentale dictée par la densité relative $\delta$.