AMM problem 12435

This is AMM problem 12435 that I solved with my friends Satvik Saha and Sohom Gupta.

Problem Statement -

For a positive integer $n$, let $d(n)$ be the number of positive divisors of $n$, let $\phi(n)$ be Euler's totient function, and let $q(n) = d(\phi(n)) / d(n)$. Find $\inf_n q(n)$ and $\sup_n q(n)$.

Solution -

We claim that $\inf_n q(n) = 0$ and $\sup_n q(n) = \infty$.

To show that $\sup_n q(n) = \infty$, note that $q(p) = d(p - 1) / 2$ for primes $p$, which can be made arbitrarily large. Indeed, for any $\ell \in \mathbb{N}$, the arithmetic progression $\{\ell!\, k + 1\}_{k \in \mathbb{N}}$ must contain a prime $p'$ (due to Dirichlet) whence $p' - 1 = \ell!\,k'$ has at least $M$ divisors so that $d(p' - 1) \geq \ell$.

Next, we show that $\inf_n q(n) = 0$. To do so, we choose arbitrary $m \in \mathbb{N}$ and find $N$ such that $q(N) \leq 1/2^{m - 1}$. Pick a sequence $\mathcal{Q}_m$ of $m$ primes $q_1 \leq \dots \leq q_m$ such that $q_m < 2q_1$; we will show later that this is always possible via the Prime Number Theorem. Let $\mathcal{P} = \{p_1, \dots, p_n\}$  be all the primes less than $q_1$. Note that each $q_i - 1$ and each $p_j - 1$ can be factored solely in terms of the primes from $\mathcal{P}$.

For $k_1, \dots, k_n \in \mathbb{N}$, consider

$$N = N(k_1, \dots, k_n) = p_1^{k_1}\cdots p_n^{k_n} \times q_1\cdots q_m,$$

With this, we have 

$$d(N) = (k_1 + 1)\cdots (k_n + 1)\times 2^m$$

and

\begin{align}\phi(N) &= p_1^{k_1 - 1} \cdots p_n^{k_n - 1} \times (p_1 - 1)\cdots (p_n - 1)\times (q_1 - 1)\cdots (q_m - 1)\\ &= p_1^{k_1 + \alpha_1 - 1} \cdots p_n^{k_n + \alpha_n - 1}\end{align}

where the integers $\alpha_j \geq 0$ depend only on $\mathcal{Q}_m$. Thus,

$$d(\phi(N)) = (k_1 + \alpha_1)\cdots (k_n + \alpha_n)$$

and

$$q(N(k_1, \dots, k_n)) = \left(\frac{k_1 + \alpha_1}{k_1 + 1}\right)\cdots \left(\frac{k_n + \alpha_n}{k_n + 1}\right) \times \frac{1}{2^m}.$$

Taking $\min\{k_1, \dots, k_n\} \to \infty$, we can make $q(N(k_1, \dots, k_n))$ arbitrarily close to $1/2^m$, in particular less than $1/2^{m - 1}$.

To prove the existence of $\mathcal{Q}_m$ for each $m \in \mathbb{N}$, it is enough to show that there is $n \in \mathbb{N}$ such that $[n, 2n]$ contains at least $m$ primes. By the Prime Number Theorem, the number of primes in $[n, 2n]$ is of the order

$$\frac{2n}{\log(2n)} - \frac{n}{\log(n)} \sim \frac{n}{\log(n)}$$

which grows arbitrarily large as $n \to \infty$.

Note : Here's an easier proof of $\inf_n q(n) = 0$ assuming that there are infinitely many Fermat primes. Consider the sequence

$$N=2^k\cdot F_1\dots F_n$$

where $F_1,\dots ,F_n$ are the first $n$ Fermat primes. This gives

$$q(N)=\frac{k+\alpha_1+\dots +\alpha_n}{k+1}\times \frac 1{2^n}$$

where $F_i=2^{\alpha_i}+1$. Taking $k$ and $n$ to infinity, we complete the proof.

Thanks to this argument, if $\inf_n q(n) \neq 0$, then that implies that there are only finitely many Fermat primes, which resolves a long standing conjecture about Fermat primes. Since that is highly unlikely, the $\inf$ has to be $0$ - this is a classic case of proof by existence of proof!