Study of the divisor graph. I (Q1925026)

This is the first in a series of papers by the author devoted to a detailed study of properties of the divisor graph, the graph obtained by taking as vertices the positive integers and connecting two integers by an edge if and only if one is a divisor of the other. A sequence \(C(x)= (n_i)_{1\leq i\leq l}\) of integers \(n_i\leq x\) is called a divisor chain of integers \(\leq x\) if it represents a simple path in the divisor graph, i.e., if the integers \(n_i\) are distinct and, for each \(i\), either \(n_i |n_{i+1}\) or \(n_{i+1} |n_i\) holds. The maximal length of such a chain has been investigated by several authors, most recently by \textit{G. Tenenbaum} [Sur un problème de crible et ses applications. II, Ann. Sci. Éc. Norm. Supér, IV. Sér. 28, 115-127 (1995; Zbl 0852.11048)]. In the present paper, the author considers another parameter associated with a divisor chain, namely the number of distinct ratios \(\max (n_i/n_{i+1}, n_{i+1}/n_i)\), \(1\leq i\leq l\), that the chain generates. Let \(R(x)\) denote the maximal number of such ratios as \(C(x)\) ranges over all divisor chains of integers \(\leq x\). The author shows that, for any fixed \(\varepsilon>0\) and all \(x>2\), \[ R(x)= \sqrt{8x} \left(1+O_\varepsilon \left({1 \over (\log x)^{1/2-\varepsilon}} \right) \right). \]