Shortlist 2020, N6¶

Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : Cyprus

Concepts : Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs · AM-GM et moyennes

Solution officielle : Shortlist officielle 2020 (avec solutions), p. 81 (page 83 du PDF)

Énoncé¶

For a positive integer \(n\), let \(d(n)\) be the number of positive divisors of \(n\), and let \(\varphi(n)\) be the number of positive integers not exceeding \(n\) which are coprime to \(n\). Does there exist a constant \(C\) such that

\[\frac{\varphi(d(n))}{d(\varphi(n))} \leq C\]

for all \(n \geq 1\)?

Indices : les idées clés

Fonctions arithmétiques : formules multiplicatives de \(d\) et \(\varphi\) ; on choisit \(n\) pour que \(d(n)\) soit une puissance de \(2\) (fois une puissance d'un grand premier) et que \(\varphi(n)\) n'ait que de petits facteurs premiers.
Exposant énorme (solution 1) : avec \(n = (p_1 \cdots p_k)^{q-1} p_{k+1} \cdots p_{k+s}\), le rapport tend vers \(2^{s-1}\) quand le premier \(q\) tend vers l'infini.
Beaucoup de premiers entre \(N\) et \(2N\) (solution 1) : conséquence de la divergence de \(\sum 1/p\).
AM-GM (solution 2) : majore \(d(\varphi(n))\), combinée au théorème des nombres premiers.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2020 (deux solutions et deux remarques).

Réponse. Non, une telle constante n'existe pas.

Solution 1¶

Fixons \(N > 1\) ; soient \(p_1, \ldots, p_k\) tous les nombres premiers entre \(1\) et \(N\), et \(p_{k+1}, \ldots, p_{k+s}\) tous les premiers entre \(N + 1\) et \(2N\). Pour \(j \leq k + s\), tous les diviseurs premiers de \(p_j - 1\) sont au plus \(N\), donc

\[\prod_{j=1}^{k+s} (p_j - 1) = \prod_{i=1}^{k} p_i^{c_i}\]

pour certains exposants fixés \(c_1, \ldots, c_k\). Choisissons un nombre premier \(q\) très grand et considérons

\[n = (p_1 \cdots p_k)^{q-1} \cdot (p_{k+1} \cdots p_{k+s}).\]

Par les formules des fonctions arithmétiques \(d\) et \(\varphi\) :

\[\varphi(d(n)) = \varphi(q^k \cdot 2^s) = q^{k-1}(q - 1) 2^{s-1}\]

et

\[d(\varphi(n)) = d\left((p_1 \cdots p_k)^{q-2} \prod_{i=1}^{k+s} (p_i - 1)\right) = d\left(\prod_{i=1}^{k} p_i^{q-2+c_i}\right) = \prod_{i=1}^{k} (q - 1 + c_i),\]

donc

\[\frac{\varphi(d(n))}{d(\varphi(n))} = \frac{q^{k-1}(q - 1) 2^{s-1}}{\prod_{i=1}^{k} (q - 1 + c_i)} = 2^{s-1} \cdot \frac{q - 1}{q} \cdot \prod_{i=1}^{k} \frac{q}{q - 1 + c_i},\]

quantité aussi proche que l'on veut de \(2^{s-1}\) quand \(q\) est assez grand. Il reste à montrer que \(s\) peut être arbitrairement grand, c'est-à-dire qu'il peut y avoir arbitrairement beaucoup de nombres premiers entre \(N\) et \(2N\).

Cela découle par exemple du fait bien connu que \(\sum_{p \in \mathbb{P}} \frac{1}{p} = \infty\), la somme portant sur l'ensemble \(\mathbb{P}\) des nombres premiers. En effet, si pour une constante \(C\) il y avait toujours au plus \(C\) premiers entre \(2^\ell\) et \(2^{\ell+1}\), on aurait

\[\sum_{p \in \mathbb{P}} \frac{1}{p} = \sum_{\ell=0}^{\infty} \sum_{\substack{p \in \mathbb{P} \\ p \in [2^\ell, 2^{\ell+1})}} \frac{1}{p} \leq \sum_{\ell=0}^{\infty} \frac{C}{2^\ell} < \infty,\]

ce qui est une contradiction. \(\blacksquare\)

Solution 2¶

On utilise le théorème des nombres premiers : \(\pi(m) = \frac{m}{\log m}(1 + o(1))\) quand \(m \to \infty\), où \(\pi(m)\) est le nombre de premiers au plus égaux à \(m\) et \(\log\) le logarithme népérien.

Soit \(m > 5\) un grand entier et \(n := p_1 p_2 \cdots p_{\pi(m)}\) le produit de tous les premiers au plus égaux à \(m\). Alors \(\varphi(d(n)) = \varphi\left(2^{\pi(m)}\right) = 2^{\pi(m) - 1}\). Considérons

\[\varphi(n) = \prod_{k=1}^{\pi(m)} (p_k - 1) = \prod_{s=1}^{\pi(m/2)} q_s^{\alpha_s},\]

où \(q_1, \ldots, q_{\pi(m/2)}\) sont les premiers au plus égaux à \(m/2\). Chaque facteur \(p_k - 1\) apporte au plus un premier \(q_s > \sqrt{m}\) au produit \(\prod_s q_s^{\alpha_s}\) (car \(p_k - 1 < m\)), donc

\[\sum_{s :\, q_s > \sqrt{m}} \alpha_s \leq \pi(m) \quad \Longrightarrow \quad \sum_{s :\, q_s > \sqrt{m}} (1 + \alpha_s) \leq \pi(m) + \pi(m/2).\]

Par AM-GM puis l'inégalité \((A/x)^x \leq e^{A/e}\), on obtient

\[\prod_{s :\, q_s > \sqrt{m}} (\alpha_s + 1) \leq \left(\frac{\pi(m) + \pi(m/2)}{\ell}\right)^\ell \leq \exp\left(\frac{\pi(m) + \pi(m/2)}{e}\right),\]

où \(\ell\) est le nombre de facteurs du produit.

Précision ajoutée : le livret dit « \(\ell\) est le nombre de premiers de l'intervalle \((\sqrt{m}, m]\) » ; c'est le nombre de premiers \(q_s\) de \((\sqrt{m}, m/2]\) qui intervient, et la majoration finale vaut quel que soit \(\ell\).

Pour les \(i\) tels que \(q_i < \sqrt{m}\), on utilise la majoration triviale \(\alpha_i \leq \log_2(\varphi(n)) \leq \log_2 n < \log_2(m^m) < m^2\), d'où

\[\prod_{s=1}^{\pi(\sqrt{m})} (\alpha_s + 1) \leq \left(m^2\right)^{\sqrt{m}} = m^{2\sqrt{m}}.\]

En rassemblant,

\[d(\varphi(n)) = \prod_{s=1}^{\pi(m/2)} (\alpha_s + 1) \leq \exp\left(2\sqrt{m} \cdot \log m + \frac{\pi(m) + \pi(m/2)}{e}\right).\]

Le théorème des nombres premiers donne alors

\[\limsup_{m \to \infty} \frac{\log(d(\varphi(n)))}{m / \log m} \leq \limsup_{m \to \infty} \frac{2\sqrt{m} \cdot \log m}{m / \log m} + \limsup_{m \to \infty} \frac{\pi(m) + \pi(m/2)}{e \cdot m / \log m} = \frac{3}{2e},\]

tandis que, toujours par ce théorème,

\[\liminf_{m \to \infty} \frac{\log(\varphi(d(n)))}{m / \log m} = \liminf_{m \to \infty} \frac{\log\left(2^{\pi(m) - 1}\right)}{m / \log m} = \log 2.\]

Comme \(\frac{3}{2e} < \frac{3}{5} < \log 2\), le rapport \(\varphi(d(n)) / d(\varphi(n))\) peut être rendu arbitrairement grand. \(\blacksquare\)

Remarques¶

Remarque 1 (preuves élémentaires de la dernière étape de la solution 1). On peut éviter la divergence de \(\sum 1/p\). Supposons que pour une constante \(C\) et tout \(k \geq 1\), il y ait au plus \(C\) premiers entre \(2^k\) et \(2^{k+1}\). Écrivons \((2^n)! = \prod p^{\alpha_p}\), avec \(\alpha_p = \lfloor 2^n/p \rfloor + \lfloor 2^n/p^2 \rfloor + \cdots\) (formule de Legendre). Pour \(p \in [2^k, 2^{k+1})\), on a \(\alpha_p \leq 2^n/2^k + 2^n/2^{k+1} + \cdots = 2^{n-k+1}\), donc \(p^{\alpha_p} \leq 2^{(k+1) 2^{n-k+1}}\). Avec la minoration \((2m)! \geq m(m+1) \cdots (2m-1) \geq m^m\) pour \(m = 2^{n-1}\), on obtient

\[2^{(n-1) \cdot 2^{n-1}} \leq (2^n)! \leq \prod_{k=1}^{n-1} 2^{C(k+1) 2^{n-k+1}}, \quad \text{soit} \quad \sum_{k=1}^{n-1} C(k+1) 2^{1-k} \geq \frac{n-1}{2},\]

ce qui est faux pour \(n\) grand, puisque \(C(k+1)2^{1-k} < 1/3\) sauf pour un nombre fini de \(k\).

On obtient même élémentairement bien plus : la formule de \(\nu_p(n!)\) montre que si \(p^\alpha\) est la plus grande puissance de \(p\) divisant \(\binom{n}{n/2}\), alors \(p^\alpha \leq n\). En regardant la décomposition de \(\binom{n}{n/2}\) en facteurs premiers,

\[\pi(n) \geq \log_n \binom{n}{n/2} \geq \frac{\log(2^n / n)}{\log n} \geq \frac{n}{2 \log n}.\]

En particulier, pour une infinité de \(n\), il y a au moins \(\frac{n}{3 \log n}\) premiers entre \(n\) et \(2n\).

Remarque 2. La formulation originale demandait si \(d(\varphi(n)) \geq \varphi(d(n))\) pour tous les \(n\) sauf un nombre fini. Le comité de sélection a jugé la version présentée mieux adaptée à la Shortlist.