Etude du graphe divisoriel 6

Eric Saias · 2025

Read Etude du graphe divisoriel 6 by Eric Saias (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-12056.txt.

Introduction

Eric Saias, a solo author, studies the divisor graph, a web where each whole number is a point and two points are joined when one divides the other. He asks how many numbers up to a bound can be covered by a set of chains that do not overlap.

Saias proves that the best count sits between two bounds of the same shape. Both bounds grow with the bound on the numbers and shrink as the count of chains grows, through a log term. The result settles a question posed by Erdös, a noted figure in number theory. The work is part six of a series on this graph.

Catalog record

CREATOREric Saias
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-12056

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Etude du graphe divisoriel 6 Eric Saias Abstract 1 Introduction On appelle graphe divisoriel le graphe de la relation \mathcal{R}_{f} définie sur l’ensemble des entiers positifs par a \mathcal{R}_{f} b si et seulement si a divise b ou b divise a . On s’intéresse plus spécifiquement ici aux propriétés asymptotiques quand x tend vers +\infty de la restriction \mathcal{R}_{f}^{x} du graphe divisoriel aux entiers inférieurs ou égaux à x . Sur l’ensemble des entiers inférieurs ou égaux à x , on définit également la relation \mathcal{R}_{g}^{x} de la manière suivante où on note [a,b] le plus petit commun multiple des entiers a et b : a \mathcal{R}_{g}^{x} b si et seulement si [a,b]\leq x . On constate que si les entiers a et b sont en relation par \mathcal{R}_{f}^{x} , ils le sont également pour \mathcal{R}_{g}^{x} . Les graphes des relations \mathcal{R}_{f}^{x} et \mathcal{R}_{g}^{x} ont des propriétés communes. Cela justifie que l’on fasse quand c’est possible une étude simultanée de ces deux graphes. On appelle chaîne d’entiers \leq x pour \mathcal{R}_{f} (respectivement pour \mathcal{R}_{g}^{x} ) de longueur \ell , tout \ell –uplet (a_{1},a_{2},\ldots,a_{\ell}) d’entiers \leq x et deux à deux distincts tel que pour tout i vérifiant 1\leq i\leq\ell , on a a_{i} \mathcal{R}_{f} a_{i+1} (\mathrm{resp}.\ a_{i} \mathcal{R}_{g}^{x} a_{i+1}) . On notera a_{1}-a_{2}-\cdots-a_{\ell} cette chaîne. On désigne par f(x) (\mathrm{resp}\ g(x)) la longueur maximum d’une chaîne d’entiers \leq x pour \mathcal{R}_{f} (\mathrm{resp}\ \mathcal{R}_{g}^{x}) . On note \ell(\mathcal{C}) la longueur d’une chaîne \mathcal{C} . Soient \alpha et \beta deux fonctions définies sur une partie D de \mathbb{R}^{+} . On écrira \alpha(x)\ll\beta(x) ou \alpha(x)=O(\beta(x)) quand il existe un réel positif K tel que pour tout x élément de D , on a |\alpha(x)|\leq K|\beta(x)| . Quand on a simultanément \alpha(x)\ll\beta(x) et \beta(x)\ll\alpha(x) , on écrira \alpha(x)\asymp\beta(x) . A la suite des travaux de Pomerance [ 3 ] , Pollington [ 2 ] et Tenenbaum [ 12 ] sur l’asymptotique des fonctions f(x) et g(x) , j’ai montré au théorème 2 de [ 6 ] que (1.1) f(x)\asymp g(x)\asymp x/\log x. Weingartner (Corollary 1 de [ 22 ] ) a récemment donné une minoration explicite de f(x) : f(x)>0,76\dfrac{x}{\log x} , pour x suffisamment grand. Au vu de (1.1), Erdös [ 1 ] a posé la question de savoir comment ce résultat se généralise quand au lieu d’une seule chaîne, on en dispose de plusieurs. Cette question se subdivise en deux suivant que l’on demande aux chaînes d’être deux à deux disjointes ou non. De manière précise, désignons par f(x,y) (respectivement F(x,y) ) le cardinal maximum de l’ensemble des entiers représentés par l’union de y chaînes quelconques (resp. deux à deux disjointes) d’entiers \leq x pour \mathcal{R}_{f} . Désignons également par g(x,y) et G(x,y) les analogues respectifs de f(x,y) et F(x,y) quand on remplace la relation \mathcal{R}_{f} par la relation \mathcal{R}_{g}^{x} . Notons \log^{+}(z):=\max(\log z,1) . J’ai montré au théorème 1 de [ 8 ] que (1.2) \hskip 28.45274ptf(x,y)\asymp g(x,y)\asymp x\dfrac{\log^{+}y}{\log^{+}x},\hskip 85.35826pt\ \text{pour}\ x\geq y\geq 1. Le principal objet de ce présent travail est de donner cette fois-ci l’ordre de grandeur des fonctions F(x,y) et G(x,y) . Théorème 1.1 . Il existe deux réels K>c>0 tels que l’on a pour tous x\geq y\geq 1 c\,\frac{x}{\log^{+}(x/y)}\leq F(x,y)\leq G(x,y)\leq K\frac{x}{\log^{+}(x/y)}. On peut même demander que toutes les chaîne utilisées ont la même longueur, sans changer l’ordre de grandeur du nombre d’entiers représentés. Notons R(x,z) (respectivement T(x,z) ) le nombre maximum d’entiers représentés par des chaînes deux à deux disjointes pour \mathcal{R}_{f} (\mathrm{resp}.\ \mathcal{R}_{g}^{x}) d’entiers \leq x , et de longueur toutes égales à z . Théorème 1.2 . Il existe deux réels K>c>0 tels que pour tous entiers x et z vérifiant 1\leq z\leq f(x) , on a c\,\frac{x}{\log^{+}z}\leq R(x,z)\leq T(x,z)\leq K\frac{x}{\log^{+}z}. Revenons à la fonction F(x,y) . La question sous–jacente à son introduction est de quantifier combien de nouveaux entiers on peut représenter quand on dispose de plusieurs chaînes disjointes et non d’une seule. Remarquons que l’on a trivialement F(x,y)\leq yf(x) . Si cette majoration n’était pas très grossière, on pourrait avoir \limsup\limits_{y\rightarrow+\infty}\limsup\limits_{x\rightarrow+\infty}(F(x,y)/f(x))=+\infty comme c’est le cas quand on remplace F(x,y) par f(x,y) , d’après (1.2). Mais elle est de fait très grossière. En effet le théorème 1 montre que l’on a en particulier F(x,\sqrt{x})/f(x)\asymp 1 . Le nombre de nouveaux entiers représentés est donc très petit au regard du nombre de nouvelles chaînes dont on dispose. 2 Les ensembles \mathcal{A}(x) et \mathcal{B}(x) de Schinzelet Szekeres Dans ce travail on utilisera la lettre x pour désigner un élément générique de \mathbb{R}^{+*} , les lettres m et n pour désigner un élément générique de \mathbb{N}^{*} , et les lettres p et q pour désigner un nombre premier générique. Les lettres i , j , k et \ell serviront d’indice. Pour tout n\geq 2 , notons n=p_{1}p_{2}\cdots p_{k}\ \text{avec}\ p_{1}\geq p_{2}\geq\cdots\geq p_{k} la décomposition de n en facteurs premiers. On note \Omega(n)=k et P^{-}(n)=p_{k} . On convient de plus que \Omega(1)=0 et P^{-}(1)=+\infty . Notons à présent (2.1) S(n):=\left|\begin{matrix}&\max\limits_{1\leq j\leq k}\ p_{1}p_{2}\cdots p_{j-1}p_{j}^{2}&\text{si}\ n\geq 2\\ &\text{et}\hfill\\ &1\hfill&\text{si}\ n=1\end{matrix}\right. la fonction introduite par Schinzel et Szekeres dans [ 10 ] en 1959, et (2.2) \mathcal{A}(x):=\{n:S(n)\leq x\} et (2.3) \mathcal{B}(x)\!:=\!\{2\leq n\leq x\!:\!\!\max\limits_{1\,\leq\,j\,<\,k}p_{1}p_{2}\cdots p_{j-1}p_{j}^{2}\!\leq\!x\!<\!p_{1}p_{2}\cdots p_{k-1}p_{k}^{2}\} les ensembles qui lui sont directement associés. Le lien entre \mathcal{B}(x) et \mathcal{A}(x) provient du fait que les entiers de \mathcal{B}(x) sont les entiers \leq x n’appartenant pas à \mathcal{A}(x) , et minimaux pour la divisibilité (voir aussi les lemmes 2.2 et 2.4 ci–dessous). Remarquons dès à présent que l’on a (2.4) p\in\mathcal{B}(x)\Longleftrightarrow\sqrt{x}<p\leq x. Schinzel et Szekeres ont introduit ces objets pour répondre à une question d’Erdös [ 10 ] . Ruzsa [ 4 ] et Tenenbaum [ 11 ] et [ 12 ] ont montré qu’ils avaient plusieurs autres applications : aux entiers à diviseurs denses, au petit crible d’Erdös et Ruzsa, aux nombres pratiques et au graphe divisoriel, (voir dans l’ordre chronologique [ 5 ] , [ 6 ] , [ 7 ] , [ 8 ] , [ 14 ] , [ 15 ] , [ 16 ] , [ 17 ] , [ 18 ] , [ 19 ] , [ 20 ] , [ 13 ] , [ 21 ] , [ 9 ] et [ 22 ] ). On remarque que S(n) , \mathcal{A}(x) et \mathcal{B}(x) sont souvent définis un peu différemment dans la littérature. Mais ce sont sous la forme (2.1), (2.2) et (2.3) que l’on travaillera avec ces objets dans ce présent travail. Précisons le lien avec les entiers à diviseurs denses en désignant par 1=d_{1}(n)<d_{2}(n)<\cdots<d_{\tau(n)}(n)=n la suite croissante de ses diviseurs. On dit que n est à diviseurs z –denses quand \max_{1\leq i<\tau(n)}\frac{d_{i+1}(n)}{d_{i}(n)}\leq z. Le lien a été établi par Tenenbaum (lemme 2.2 de [ 11 ] ) et est donné par la formule suivante : Lemme 2.1 . Soit n\geq 2 . On a S(n)=n\ \max_{1\leq i<\tau(n)}\frac{d_{i+1}(n)}{d_{i}(n)}. L’étude des entiers à diviseurs denses est intéressante en soi (voir en particulier les travaux de Weingartner cités dans les références). Mais pour les questions relatives aux longues chaînes du graphe divisoriel (voir [ 12 ] , [ 6 ] , [ 8 ] , [ 9 ] et [ 22 ] ) ce sont les propriétés et interactions des ensembles \mathcal{A}(x) et \mathcal{B}(x) qui jouent le

Read the complete text