Problem:
Find all positive integers $n$ such that $\varphi^3(n) \leq n^2$.
Proposed by Alessandro Ventullo, Milan, Italy
Solution:
Clearly $n=1$ satisfies the condition. Let $n>1$ and let $n=\prod_{j=1}^m p_j^{k_j}$, where $p_j$ is the $j$-th prime and $k_j \in \mathbb{N}$ for $j=1,2,\ldots,m$. Since $f(n)=n^2$ and $\varphi(n)$ are multiplicative functions, then the given relation becomes $$\prod_{j=1}^m \varphi^3(p_j^{k_j}) \leq \prod_{j=1}^m p_j^{2k_j}.$$ We use the following Lemma.
Lemma.
Let $p$ be a prime number and let $k$ be a positive integer.
(a) If $k=0$, then $\varphi^3(p^k)=p^{2k}$.
(b) If $p \geq 5$, then
$$\varphi^3(p^k)>\dfrac{9}{4}p^{2k} \qquad \forall k \in \mathbb{N}^*. \qquad (1) $$
(c) If $p \geq 7$, then $$\varphi^3(p^k)>4p^{2k} \qquad \forall k \in \mathbb{N}^*. \qquad (2) $$
(d) If $p \geq 11$, then $$ \varphi^3(p^k)>8p^{2k} \qquad \forall k \in \mathbb{N}^*. \qquad (3) $$
Proof. It's a simple computation.
From the inequality (1) in the Lemma we must consider only the primes $p_1=2$ and $p_2=3$.
If $k_1>3$, then $$\varphi^3(2^{k_1})=(2^{k_1}-2^{k_1-1})^3=2^{3(k_1-1)} > 2^{2k_1}$$ and if $k_2>1$, then $$\varphi^3(3^{k_2})=(3^{k_2}-3^{k_2-1})^3=3^{3(k_2-1)}\cdot8 > 3^{2k_2}.$$ So, there are no solutions if $k_1=k_2=0$ and $k_j>0$ for some $j>2$ or $k_1>3$ and $k_2>1$. So, $k_1 \leq 3$ or $k_2 \leq 1$.
\begin{description}
(a) If $k_1=0$, then $n=\prod_{j=2}^m p_j^{k_j}$. As before, we conclude immediately that there are solutions only if $k_2 \leq 1$ and $k_j=0$ for all $j=1,2,\ldots,m$. So, $n=3$.
(b) If $k_1=1$, then $n=2a$, where $a$ is an odd number. Hence, $$\varphi^3(n)=\varphi^3(2a)=\varphi^3(2)\varphi^3(a)=\varphi^3(a).$$ We have to find $a$ odd such that $$\varphi^3(a) \leq 4a^2.$$ From the inequality (2) in the Lemma we must consider only the primes $p_2=3$ and $p_3=5$. If $k_2>2$, then $$\varphi^3(3^{k_2})=3^{3(k_2-1)}\cdot2^3>4\cdot3^{2k_2}$$ and if $k_3>1$, then $$\varphi^3(5^{k_3})=5^{3(k_3-1)}\cdot4^3>4\cdot5^{2k_3}$$ So, there are no solutions for $a$ if $k_2=k_3=0$ and $k_j>0$ for some $j>3$ or $k_2>2$ and $k_3>1$. It follows that $k_2 \leq 2$ or $k_3 \leq 1$.
(i) If $k_2=0$, then we have a solution if $k_3 \leq 1$, so $a \in \{1,5\}$, which gives $n \in \{2,10\}$.
(ii) If $k_2=1$, then $a=3b$, where $b$ is a natural number nondivisible by $2$ and $3$. Hence, $n=6b$ and $$\varphi^3(n)=\varphi^3(6b)=\varphi^3(6)\varphi^3(b)=8\varphi^3(b).$$ We have to find $b$ nondivisible by $2$ and $3$ such that $8\varphi^3(b) \leq 36b^2$, i.e. $$\varphi^3(b) \leq \dfrac{9}{2}b^2.$$ From the inequality (3) in the Lemma we must consider only the primes $p_3=5$ and $p_4=7$. If $k_3>1$, then $$\varphi^3(5^{k_3})=5^{3(k_3-1)}\cdot4^3>\dfrac{9}{2}\cdot5^{2k_3}$$ and if $k_4>1$, then $$\varphi^3(7^{k_4})=7^{3(k_4-1)}\cdot6^3>\dfrac{9}{2}\cdot7^{2k_4}$$ So, there are no solutions for $b$ if $k_3=k_4=0$ and $k_j>0$ for some $j>4$ or $k_3>1$ and $k_4>1$. It follows that $k_3 \leq 1$ or $k_4 \leq 1$. If $k_3=0$, then we have a solution if $k_4 \leq 1$, so $b \in \{1,7\}$, which gives $n \in \{6,42\}$. If $k_3=1$, then $b=5c$, where $c$ is a natural number nondivisible by $2,3,5$. Hence, $n=30c$ and $$\varphi^3(n)=\varphi^3(30c)=\varphi^3(30)\varphi^3(c)=512\varphi^3(c).$$ We have to find $c$ nondivisible by $2,3,5$ such that $512\varphi^3(c) \leq 900c^2$, i.e. $$\varphi^3(c) \leq \dfrac{225}{128}c^2.$$ From the inequality (2) in the Lemma we have no primes for $c$. So, $c=1$ and $n=30$.
(iii) If $k_2=2$, then $a=9b$, where $b$ is a natural number nondivisible by $2$ and $3$. Hence, $n=18b$ and $$\varphi^3(n)=\varphi^3(18b)=\varphi^3(18)\varphi^3(b)=216\varphi^3(b).$$ We have to find $b$ nondivisible by $2$ and $3$ such that $216\varphi^3(b) \leq 324b^2$, i.e. $$\varphi^3(b) \leq \dfrac{3}{2}b^2.$$ From the inequality (1) in the Lemma we have no primes for $b$. So, $b=1$ and $n=18$.
(iv) If $k_3=0$, then we have a solution if $k_2 \leq 2$, so $a \in \{1,3,9\}$, which gives $n \in \{2,6,18\}$.
(v) If $k_3=1$, then $a=5b$, where $b$ is a natural number nondivisible by $2$ and $5$. Hence, $n=10b$ and $$\varphi^3(n)=\varphi^3(10b)=\varphi^3(10)\varphi^3(b)=64\varphi^3(b).$$ We have to find $b$ nondivisible by $2$ and $5$ such that $64\varphi^3(b) \leq 100b^2$, i.e. $$\varphi^3(b) \leq \dfrac{25}{16}b^2.$$ From the inequality (2) in the Lemma we must consider only the prime $p_2=3$. If $k_2>1$, then $$\varphi^3(3^{k_2})=3^{3(k_2-1)}\cdot2^3>\dfrac{25}{16}\cdot3^{2k_2}.$$ So, there are no solutions for $b$ if $k_2=0$ and $k_j>0$ for some $j>3$ or $k_2>1$. It follows that $k_2 \leq 1$. If $k_2=0$, then $b=1$, which gives $n=10$. If $k_2=1$, then $b=3c$, where $c$ is a natural number nondivisible by $2,3,5$. Hence, $n=30c$ and we conclude as in point (ii).
(c) If $k_1=2$, then $n=4a$, where $a$ is an odd number. Hence, $$\varphi^3(n)=\varphi^3(4a)=\varphi^3(4)\varphi^3(a)=8\varphi^3(a).$$ We have to find $a$ odd such that $8\varphi^3(a) \leq 16a^2$, i.e. $$\varphi^3(a) \leq 2a^2.$$ From the inequality (1) in the Lemma we must consider only the prime $p_2=3$. If $k_2>1$, then $$\varphi^3(3^{k_2})=3^{3(k_2-1)}\cdot2^3>2\cdot3^{2k_3}.$$ So, there are no solutions for $a$ if $k_2=0$ and $k_j>0$ for some $j>2$ or $k_2>1$. It follows that $k_2 \leq 1$. If $k_2=0$, then $a=1$ and $n=4$. If $k_2=1$, then $a=3b$, where $b$ is a natural number nondivisible by $2$ and $3$. Hence, $n=12b$ and $$\varphi^3(n)=\varphi^3(12b)=\varphi^3(12)\varphi^3(b)=64\varphi^3(b).$$ We have to find $b$ nondivisible by $2$ and $3$ such that $64\varphi^3(b) \leq 144b^2$, i.e. $$\varphi^3(b) \leq \dfrac{9}{4}b^2.$$ From the inequality (1) in the Lemma we have no primes for $b$. So, $b=1$ and $n=12$.
(d) If $k_1=3$, then $n=8a$, where $a$ is an odd number. Hence, $$\varphi^3(n)=\varphi^3(8a)=\varphi^3(8)\varphi^3(a)=64\varphi^3(a).$$ We have to find $a$ odd such that $64\varphi^3(a) \leq 64a^2$, i.e. $$\varphi^3(a) \leq a^2.$$ We know that this inequality has a solution if $k_2 \leq 1$, so $a \in \{1,3\}$, which gives $n \in \{8,24\}$.
(e) If $k_2=0$, then $n=\prod_{\substack{j=1 \\ j \neq 2}}^m p_j^{k_j}$. As before, we conclude immediately that there are solutions only if $k_1 \leq 3$ and $k_j=0$ for all $j=1,2,\ldots,m$. So, $n \in \{2,4,8\}$.
(f) If $k_2=1$, then $n=3a$, where $a$ is a natural number nondivisible by $3$. Hence, $$\varphi^3(n)=\varphi^3(3a)=\varphi^3(3)\varphi^3(a)=8\varphi^3(a).$$ We have to find $a$ nondivisible by $3$ such that $8\varphi^3(a) \leq 9a^2$, i.e. $$\varphi^3(a) \leq \dfrac{9}{8}a^2.$$ From the inequality (1) in the Lemma we must consider only the prime $p_1=2$. If $k_1>2$, then $$\varphi^3(2^{k_1})=2^{3(k_1-1)}>\dfrac{9}{8}\cdot2^{2k_1}.$$ So, there are no solutions for $a$ if $k_1$ and $k_j>0$ for some $j>2$ or $k_1>2$. It follows that $k_1 \leq 2$, so $a \in \{1,2,4\}$, which gives $n \in \{1,6,12\}$.
In conclusion, we have $n \in \{1,2,3,4,6,8,10,12,18,24,30,42\}$.
Note: Let $$A_x=\{n \in \mathbb{N}^* \ | \ \varphi(n) \leq n^x\}.$$ Observe that the function $$g(x)=|A_x|$$ is increasing for $x \in [0,1)$. The problem tells us that $g(2/3)=12$. Moreover, it's easy to see that $g(0)=2$ and $g(1/2)=4$.
