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 $\varphi (n)$ be Euler's totient function, and let $q(n)=d(\varphi (n))/d(n)$. Find $\underset{n}{inf}q(n)$ and $\underset{n}{sup}q(n)$.

Solution -

We claim that $\underset{n}{inf}q(n)=0$ and $\underset{n}{sup}q(n)=\mathrm{\infty }$.

To show that $\underset{n}{sup}q(n)=\mathrm{\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^{\prime }$ (due to Dirichlet) whence $p^{\prime }-1=\ell !k^{\prime }$ has at least $M$ divisors so that $d(p^{\prime }-1)\ge \ell$.

Next, we show that $\underset{n}{inf}q(n)=0$. To do so, we choose arbitrary $m\in \mathbb{N}$ and find $N$ such that $q(N)\le 1/2^{m-1}$. Pick a sequence ${\mathcal{Q}}_m$ of $m$ primes $q_1\le \cdots \le 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{array}{rl}\varphi (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{array}$$

where the integers ${\alpha }_j\ge 0$ depend only on ${\mathcal{Q}}_m$. Thus,

$$d(\varphi (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 \mathrm{\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 \mathrm{\infty }$.

Note : Here's an easier proof of $\underset{n}{inf}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+\cdots +{\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 $\underset{n}{inf}q(n)\ne 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!