Étude du graphe divisoriel 5

Éric Saias

doi:10.5802/jtnb.1276

Éric Saias ¹

¹ Sorbonne Université LPSM 4, place Jussieu 75252 Paris Cedex 05 (France)

Journal de théorie des nombres de Bordeaux, Tome 36 (2024) no. 1, pp. 175-214.

Résumé
Abstract

Le graphe divisoriel est le graphe non orienté dont les sommets sont les entiers strictement positifs et deux entiers sont reliés par une arête quand le petit divise le grand. On appelle chaîne de longueur $ℓ$ toute suite finie d’entiers strictement positifs $a_{1}, a_{2}, ..., a_{ℓ}$ deux à deux distincts tels que pour tout $i$ vérifiant $1 \leq i < ℓ$ , $a_{i}$ et $a_{i + 1}$ sont reliés par une arête du graphe divisoriel.

Notons $f (x)$ la longueur maximum d’une chaîne de la restriction du graphe divisoriel aux entiers inférieurs ou égaux à $x$ . Tenenbaum a donné un procédé constructif, directement transposable sous forme d’algorithme, qui établit l’existence d’une chaîne d’entiers $\leq x$ dont on sait maintenant qu’il fournit la minoration $f (x) \geq (c + o (1)) x / log x$ avec $c = 0, 07$ quand $x \to + \infty$ . On donne ici une variante de son procédé constructif qui permet d’obtenir $c = 0, 37$ pour la même minoration. On profite de l’occasion pour faire une large part aux mathématiques expérimentales.

Par ailleurs, on donne également une minoration d’une variante de la fonction $f (x)$ , qui permettra de répondre à une question d’Erdős dans un travail ultérieur.

The divisor graph is the non oriented graph whose vertices are the positive integers, two vertices being connected by an edge when the smallest one divides the largest one. We call chain of length $ℓ$ any finite sequence of pairwise distinct positive integers $a_{1}, a_{2}, ..., a_{ℓ}$ , such that, for $1 \leq i < ℓ$ , $a_{i}$ and $a_{i + 1}$ are connected by an edge in the divisor graph.

Let $f (x)$ denote the maximum length of the restriction of the divisor graph to the integers smaller than or equal to $x$ . Tenenbaum has given a constructive procedure, directly transposable in form of an algorithm, which establishes the existence of a chain of integers $\leq x$ , from which the lower bound $f (x) \geq (c + o (1)) x / log x$ is now known to follow, with $c = 0, 07$ when $x \to + \infty$ . We give here a variant of his constructive procedure that allows to get a similar lower bound with $c = 0, 37$ . We take advantage of the opportunity to make a large part to experimental mathematics.

Moreover, we also give a lower bound of a variant of the function $f (x)$ , which will enable us to answer a question of Erdős in a forthcoming paper.

Reçu le : 2022-06-09
Révisé le : 2023-06-30
Accepté le : 2023-09-15
Publié le : 2024-07-25

DOI : 10.5802/jtnb.1276

Classification : 11A05, 05C38
Mots clés : divisor graph

Affiliations des auteurs :

Éric Saias ¹

¹ Sorbonne Université LPSM 4, place Jussieu 75252 Paris Cedex 05 (France)

Licence :

CC-BY-ND 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@article{JTNB_2024__36_1_175_0,
     author = {\'Eric Saias},
     title = {\'Etude du graphe divisoriel 5},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {175--214},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {36},
     number = {1},
     year = {2024},
     doi = {10.5802/jtnb.1276},
     language = {fr},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1276/}
}

TY  - JOUR
AU  - Éric Saias
TI  - Étude du graphe divisoriel 5
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2024
SP  - 175
EP  - 214
VL  - 36
IS  - 1
PB  - Société Arithmétique de Bordeaux
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1276/
DO  - 10.5802/jtnb.1276
LA  - fr
ID  - JTNB_2024__36_1_175_0
ER  -

%0 Journal Article
%A Éric Saias
%T Étude du graphe divisoriel 5
%J Journal de théorie des nombres de Bordeaux
%D 2024
%P 175-214
%V 36
%N 1
%I Société Arithmétique de Bordeaux
%U https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1276/
%R 10.5802/jtnb.1276
%G fr
%F JTNB_2024__36_1_175_0

Éric Saias. Étude du graphe divisoriel 5. Journal de théorie des nombres de Bordeaux, Tome 36 (2024) no. 1, pp. 175-214. doi : 10.5802/jtnb.1276. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1276/

Bibliographie
Cité par

[1] Michel Balazard Unimodalité de la distribution du nombre de diviseurs premiers d’un entier, Ann. Inst. Fourier, Volume 40 (1990) no. 2, pp. 255-270 | DOI | Numdam | Zbl

[2] Arnaud Chadozeau Communication personnelle

[3] Pál Erdős On the density of some sequences of integers, Bull. Am. Math. Soc., Volume 50 (1948), pp. 685-692 | DOI | Zbl

[4] Pál Erdős; Robert Freud; Norbert Hegyvari Arithmetical properties of permutations of integers, Acta Math. Hung., Volume 41 (1983), pp. 169-176 | DOI | Zbl

[5] Pierre Mazet Recouvrements Hamiltoniens de certains graphes, Eur. J. Comb., Volume 27 (2006) no. 5, pp. 739-749 | DOI | Zbl

[6] Pierre Mazet; Éric Saias Étude du graphe divisoriel 4, Ann. Fac. Sci. Toulouse, Math., Volume 29 (2020) no. 4, pp. 971-975 | DOI | Numdam | Zbl

[7] Marzieh Mehdizadeh The multiplication table for smooth integers, J. Number Theory, Volume 219 (2021), pp. 172-197 | DOI | Zbl

[8] Paul Melotti; Éric Saias On path partitions of the divisor graph, Acta Arith., Volume 192 (2020) no. 4, pp. 329-339 | DOI | Zbl

[9] Andrew D. Pollington There is a long path in the divisor graph, Ars Comb., Volume 16-B (1983), pp. 303-304 | Zbl

[10] Carl Pomerance On the longest path in the divisor graph (Congressus Numerantium), Volume 40, Utilitas Mathematica Publishing Incorporated, 1983, pp. 291-304 | Zbl

[11] Carl Pomerance; Lola Thompson; Andreas Weingartner On integers $n$ for which $X^{n} - 1$ has a divisor of every degree, Acta Arith., Volume 175 (2016) no. 3, pp. 225-243 | Zbl

[12] Carl Pomerance; Andreas Weingartner On primes and practical numbers, Ramanujan J., Volume 57 (2022) no. 3, pp. 981-1000 | DOI | Zbl

[13] Éric Saias Etude du graphe divisoriel 6 (en préparation)

[14] Éric Saias Longeur maximale d’un chemin élémentaire du graphe divisoriel, C. R. Math. Acad. Sci. Paris, Volume 315 (1992) no. 5, pp. 507-509 | Zbl

[15] Éric Saias Sur l’utilisation de l’identité de Buchstab, Séminaire de théorie des nombres, Paris, France, 1991-92 (Progress in Mathematics), Volume 116, 1993, pp. 217-245 | DOI | Zbl

[16] Éric Saias Entiers à diviseurs denses, J. Number Theory, Volume 62 (1997) no. 1, pp. 163-191 | DOI | Zbl

[17] Éric Saias Applications des entiers à diviseurs denses, Acta Arith., Volume 83 (1998) no. 3, pp. 225-240 | DOI | Zbl

[18] Éric Saias Entiers à diviseurs denses II, J. Number Theory, Volume 86 (2001) no. 1, pp. 39-49 | DOI | Zbl

[19] Éric Saias Étude du graphe divisoriel II, Monatsh. Math., Volume 137 (2002) no. 4, pp. 301-312 | DOI | Zbl

[20] Andrzej Schinzel; George Szekeres Sur un problème de M. Paul Erdős, Acta Sci. Math., Volume 20 (1959), pp. 221-229 | Zbl

[21] Gérald Tenenbaum Sur un problème de crible et ses applications, Ann. Sci. Éc. Norm. Supér., Volume 19 (1986) no. 1, pp. 1-30 | DOI | Numdam | Zbl

[22] Gérald Tenenbaum Sur un problème de crible et ses applications. II : Corrigendum et étude du graphe divisoriel., Ann. Sci. Éc. Norm. Supér., Volume 28 (1995) no. 2, pp. 115-127 | DOI | Numdam | Zbl

[23] Gérald Tenenbaum Introduction à la théorie analytique et probabiliste des nombres, Belin, 2015

[24] Gérald Tenenbaum; Andreas Weingartner An Erdős–Kac theorem for integers with dense divisors, Q. J. Math., Volume 75 (2024), pp. 161-195 | DOI

[25] Andreas Weingartner Integers with dense divisors, J. Number Theory, Volume 108 (2004) no. 1, pp. 1-17 | DOI | Zbl

[26] Andreas Weingartner Integers with dense divisors II, J. Number Theory, Volume 108 (2004) no. 1, pp. 18-28 | DOI | Zbl

[27] Andreas Weingartner Integers with dense divisors $3$ , J. Number Theory, Volume 142 (2014), pp. 211-222 | DOI | Zbl

[28] Andreas Weingartner Practical numbers and the distribution of divisors, Q. J. Math., Volume 66 (2015) no. 2, pp. 743-758 | DOI | Zbl

[29] Andreas Weingartner On the constant factor in several related asymptotic estimates, Math. Comput., Volume 88 (2019) no. 318, pp. 1883-1902 | DOI | Zbl

[30] Andreas Weingartner An extension of the Siegel–Walfisz theorem, Proc. Am. Math. Soc., Volume 149 (2021) no. 11, pp. 4699-4708 | DOI | Zbl

[31] Andreas Weingartner The number of prime factors of integers with dense divisors, J. Number Theory, Volume 239 (2022), pp. 57-77 | DOI | Zbl

[32] Andreas Weingartner The mean number of divisors for rough, dense and practical numbers, Int. J. Number Theory, Volume 19 (2023) no. 10, pp. 2333-2351 | DOI | Zbl

Cité par Sources :