ANNALES

DE LA FACULTÉ
DES SCIENCES

DE
TOULOUSE
Mathématiques

PIERRE MAZET ET ERIC SAIAS

Étude du graphe divisoriel 4

Tome XXIX, n° 4 (2020), p. 971-975.

<http://afst.centre-mersenne.org/item?id=AFST_2020_6_29_4_971_0>

© Université Paul Sabatier, Toulouse, 2020, tous droits réservés.

L'accès aux articles de la revue « Annales de la faculté des sciences de Toulouse Mathématiques » (http://afst.centre-mersenne.org/), implique l'accord avec les conditions générales d'utilisation (http://afst.centre-mersenne.org/legal/). Toute reproduction en tout ou partie de cet article sous quelque forme que ce soit pour tout usage autre que l'utilisation à fin strictement personnelle du copiste est constitutive d'une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright.

cedram

Article mis en ligne dans le cadre du

Centre de diffusion des revues académiques de mathématiques

http://www.centre-mersenne.org/
# Étude du graphe divisoriel 4 (*)

PIERRE MAZET (1) ET ERIC SAIAS (2)

**RÉSUMÉ.** — Nous montrons qu'il existe une permutation $f$ des entiers positifs telle que pour tout $n \ge 2$, $ppcm(f(n), f(n+1)) \le cn(\log n)^2$, où $c$ est une constante positive. Cela améliore des résultats d'Erdős, Freud et Hegyvári (1983), et de Chen et Ji (2011).

**ABSTRACT.** — We show that there exists a permutation $f$ of the positive integers such that for all $n \ge 2$, $lcm(f(n), f(n+1)) \le cn(\log n)^2$, where $c$ is a positive constant. It improves previous results of Erdős, Freud and Hegyvári (1983), and of Chen and Ji (2011).

## 1. Introduction

Appelons chaîne-permutation du graphe divisoriel de $\mathbb{N}^*$ (ou plus simplement chaîne-permutation) toute application bijective $f: \mathbb{N}^* \to \mathbb{N}^*$ telle que $f(n)$ est un diviseur ou un multiple de $f(n+1)$ pour tout entier $n \ge 1$. Il est facile de construire des chaînes-permutations. Voici les premières valeurs de l'une d'entre elles :

$$1 - 2 - (2 \times 3) - 3 - (3 \times 4) - 4 - (4 \times 5) - 5 - (5 \times 7) - 7 - (7 \times 8) - 8\dots$$

On a ici $\limsup_{n \to +\infty} f(n)/n^2 = 1/4$. Le résultat principal de cet article, énoncé ci-dessous, montre que la convergence vers l'infini de $f(n)$ peut être beaucoup plus lente.

**THÉORÈME 1.1.** — Il existe une constante $c_1$ et une chaîne-permutation $f$ telles que pour tout $n \ge 2$, on a

$$f(n) \le c_1 n(\log n)^2.$$

<footnote>(*) Reçu le 26 juillet 2018, accepté le 6 février 2019.</footnote>

<footnote>(1) — piermazet@laposte.net</footnote>

<footnote>(2) Sorbonne Université, UMR8001, LPSM, 4 Place Jussieu 75252 Paris Cedex 05 (France) — eric.saias@upmc.fr</footnote>

<footnote>Article proposé par Damian Rössler.</footnote>
Intéressons-nous maintenant à des permutations de $N^*$ qui ne sont pas nécessairement des chaînes-permutations. Notons $[a, b]$ le plus petit commun multiple des entiers $a$ et $b$. En 1981, Erdős, Freud et Hegyvári ont montré qu'il existe une constante $c_2$ et une permutation $f$ de $N^*$ telles que pour tout $n \ge 3$, on a

$$[f(n), f(n+1)] \le n \exp\{c_2\sqrt{\log n} \log \log n\}$$

(voir [2, théorème 3]). En modifiant légèrement la permutation choisie par Erdős, Freud et Hegyvári, Chen et Ji [1] ont montré trente ans plus tard que l'on peut remplacer la fonction à l'intérieur de l'accolade par $(2\sqrt{2} + o(1))\sqrt{\log n \log \log n}$. Il découle immédiatement de notre théorème une amélioration de leur résultat.

**COROLLAIRE 1.2.** — Il existe une constante $c_3$ et une permutation $f$ de $N^*$ telles que pour tout $n \ge 2$, on a

$$[f(n), f(n+1)] \le c_3 n (\log n)^2.$$

Signalons que Tenenbaum [6] conjecture que l'on peut remplacer l'expression à droite du signe $\le$ dans cette dernière formule par $n(\log n)^{1+o(1)}$. L'exposant 1 de $\log n$ serait alors optimal car on sait que ([4, théorème 3]) pour toute permutation $f$ de $N^*$, on a

$$\limsup_{n \to +\infty} \frac{[f(n), f(n+1)]}{n \log n} > 0.$$

Pour établir le théorème, on utilise une construction de chaîne finie due à Tenenbaum (voir [6, paragraphe 4]) et un résultat relatif aux entiers à diviseurs denses ([3, théorème 1]) (pour la définition de ces termes, voir le paragraphe suivant). Même si cela ne nous est pas utile ici, signalons au passage que le récent travail de Weingartner [7] fournit un équivalent asymptotique de la fonction de comptage des entiers à diviseurs $y$-denses, uniforme en $y$.

## 2. Notations

Appelons chaîne toute application injective $f: N^* \to N^*$ telle que $f(n)$ est un diviseur ou un multiple de $f(n+1)$ pour tout entier $n \ge 1$. Appelons aussi chaîne finie de longueur $l$ tout $l$-uplet $C = a_1, a_2, \dots, a_l$ d'entiers positifs deux à deux distincts et tels que $a_i$ est un diviseur ou un multiple de $a_{i+1}$ pour tout entier $i$ de l'intervalle $[1, l-1]$. On notera longueur($C$) := $l$.

On note pour tout entier $n \ge 2$, $P^+(n)$ (respectivement $P^-(n)$) le plus grand (resp. petit) facteur premier de $n$. On pose de plus $P^+(1) = 1$.
On note

$$
F(n) := \begin{cases} 1 & (n = 1) \\ \max\{dP^{-}(d) : d|n, d > 1\} & (n \ge 2). \end{cases}
$$

On dit qu’un entier $n$ est à diviseurs $y$-denses si $F(n) \le yn$. Cette dénomination provient de l’identité

$$
\frac{F(n)}{n} = \max_{1 \le i < \tau(n)} \frac{d_{i+1}(n)}{d_i(n)}
$$

où $1 = d_1(n) < d_2(n) < \cdots < d_{\tau(n)}(n) = n$ désigne la suite croissante des diviseurs de $n$ (voir [5, lemme 2.2]).

3. Preuve du théorème

Soit $p$ un nombre premier.

Au paragraphe 4 de [6], Tenenbaum construit une famille de chaînes finies
$\Gamma(x, p)$ pour tout réel $x \ge 2$. On s'intéresse ici au cas particulier $x = 2p^2$
pour lequel on a les quatre propriétés suivantes.

• $\Gamma(8, 2) = 1 - 2$.

• Pour tout $p \ge 3$, $\Gamma(2p^2, p) = 1 - p - \cdots - 2$.

* Pour tout $p$, $\Gamma(2p^2, p)$ est constituée d'entiers $m$ sans facteur carré et tels que $m \le 2p^2$, $P^+(m) \le p$.

* Pour tout $p$, $\Gamma(2p^2, p)$ contient tous les entiers $m$ sans facteur carré et tels que $F(m) \le p^2$.

Cette dernière propriété combinée avec le théorème 1 de [3] entraîne l'existence d'une constante $c > 0$ telle que pour tout $p$

$$
\operatorname{longueur}(\Gamma(2p^2, p)) \geq cp^2 / \log p. \qquad (3.1)
$$

Nous modifions légèrement $\Gamma(2p^2, p)$ en considérant la chaîne finie $\mathcal{D}(p)$
obtenue en déplaçant dans $\Gamma(2p^2, p)$ le 1 initial pour le mettre en final, puis
en multipliant le tout par le nombre premier $p^*$ suivant immédiatement $p$.
On a donc pour $p \ge 3$, $\mathcal{D}(p) = p^*p - \cdots - 2p^* - p^*$.

Soit $f_0$ la suite commençant à 1, puis obtenue par concatenation des $\mathcal{D}(p)$.

$$
f_0 : 1 - \mathcal{D}(2) - \mathcal{D}(3) - \mathcal{D}(5) - \mathcal{D}(7) - \dots
$$

On vérifie que $f_0$ est une chaîne formée d'entiers sans facteur carré. On pose
$q_0 = 1$.
On construit alors par récurrence une suite croissante $(q_k)_{k \ge 0}$ de nombres égaux à 1 ou premiers et des chaînes $f_k$ construites à partir de $f_0$ en remplaçant, pour $p \le q_k$, la chaîne finie $\mathcal{D}(p)$ par une chaîne finie $\mathcal{C}(p)$ à définir.

Supposons construits $q_0 \le q_1 \le \dots \le q_{k-1}$, $\mathcal{C}(p)$ pour $p \le q_{k-1}$ ainsi donc que $f_0, f_1, \dots, f_{k-1}$. Si $k$ est dans l'image de $f_{k-1}$, on pose $q_k = q_{k-1}$, il n'y a pas de nouvelle chaîne finie $\mathcal{C}(p)$ à définir et donc $f_k = f_{k-1}$.

On suppose dorénavant que $k$ n'est pas dans l'image de $f_{k-1}$.

On choisit $q_k$ un nombre premier tel que $q_k > q_{k-1}$ et

$$q_k \ge k^2. \tag{3.2}$$

On définit alors $\mathcal{C}(p)$ pour $q_{k-1} < p \le q_k$ de la manière suivante.

* Si $q_{k-1} < p < q_k$, on pose $\mathcal{C}(p) = \mathcal{D}(p)$.

* Si $p = q_k$, on choisit $\mathcal{C}(p) = pk^2 - k - p^*pk^2 - \mathcal{D}(p)$.

Le fait que $\mathcal{D}(p)$ est formée d'entiers sans facteur carré assure que les éléments de $\mathcal{C}(p)$ sont deux à deux distincts et donc que $\mathcal{C}(p)$ est une chaîne finie.

On pose alors

$$f_k : 1 - \mathcal{C}(2) - \mathcal{C}(3) - \dots - \mathcal{C}(q_k) - \mathcal{D}(q_k^*) - \mathcal{D}(q_k^{**}) - \dots$$

et on vérifie que c'est une chaîne. On définit enfin

$$f = \lim_{k \to +\infty} f_k = 1 - \mathcal{C}(2) - \mathcal{C}(3) - \mathcal{C}(5) - \dots - \mathcal{C}(p) - \dots$$

et on vérifie que c'est une chaîne-permutation.

Le début de cette chaîne-permutation est formée des trois entiers $1-6-3$, et est suivie de la chaîne finie $\mathcal{C}(3)$. Soit $n \ge 4$; il existe donc un nombre premier $p$ tel que $f(n) \in \mathcal{C}(p^*)$. En utilisant notamment (3.2), on a $f(n) \le 2p^{*2}p^{**} \asymp p^3$. Par ailleurs notons $r$ un nombre premier générique. On a en utilisant (3.1) et le théorème des nombres premiers

$$n \ge \sum_{r \le p} \text{longueur}(\mathcal{C}(r)) \ge \sum_{r \le p} r^2 / \log r \asymp p^3 / (\log p)^2.$$

On en déduit que $f(n) \ll n(\log n)^2$. Cela conclut la démonstration du théorème.

## Bibliographie

[1] Y. G. CHEN & C. S. JI, « The permutation of integers with small least common multiple of two subsequent terms », *Acta Math. Hung.* **132** (2011), n° 4, p. 307-309.

[2] P. ERDÖS, R. FREUD & N. HEGYVÁRI, « Arithmetical properties of permutations of integers », *Acta Math. Hung.* **41** (1983), n° 1-2, p. 169-176.
[3] E. SAIAS, « Entiers à diviseurs denses. I », *J. Number Theory* **62** (1997), n° 1, p. 163-191.

[4] ———, « Applications des entiers à diviseurs denses », *Acta Arith.* **83** (1998), n° 3, p. 225-240.

[5] G. TENENBAUM, « Sur un problème de crible et ses applications », *Ann. Sci. Éc. Norm. Supér.* **19** (1986), n° 1, p. 1-30.

[6] ———, « Sur un problème de crible et ses applications II. Corrigendum et étude du graphe divisoriel », *Ann. Sci. Éc. Norm. Supér.* **28** (1995), n° 2, p. 115-127.

[7] A. WEINGARTNER, « Practical numbers and the distribution of divisors », *Q. J. Math* **66** (2015), n° 2, p. 743-758.