# What is the convex-hull of the set $\{ (n,\varphi(n)) : n\in \mathbb N \} \subset \mathbb R^2$

I know that set $$E=\{ (n,\varphi(n)) : n\in \mathbb N \} \subset \mathbb R^2$$ has infinitely many points on the line $y=x-1$, which suggests this line to be included in the upper part of the convex-hull. However I don't really see what's going on at the bottom. That is what is the convex-hull of $E$?

Thanks.

Let $0 < c < 1$. Then there are infinitely many $n$ such that $\varphi(n) < cn$, and thus the line $y = c(x-1) + 1$ $(x \geq 1$) is included in the convex hull.

The convex hull is hence the triangle-shaped area determined by the lines $y = x$, ($x \geq 1$) and $y = 1$.

EDIT: Proof for the claim above. If $P_k = p_1 p_2 \ldots p_k$ is the product of first $k$ primes, then $\varphi(P_k) / P_k = \prod_{i = 1}^k (1 - \frac{1}{p_i})$ converges to zero as $k \rightarrow \infty$. See for example here.

• An infinite product which approaches $0$ is said to diverge to zero, not to converge. See here. Commented Mar 9, 2014 at 15:18
• OK. Vote changed to +1, because you have the most elementary proof here. (by the way, the product is $0$ because $\sum\frac1{p_i}=\infty$ - this is maybe known little more) Commented Mar 9, 2014 at 15:19
• Also, and more importantly, the $y = cx + 1$ is not quite correct. When $x = 1$, this is not in the convex hull. I think you mean $y = c(x - 1) + 1$, but even then, you need some more details to show exactly WHY this line is contained in the convex hull. Commented Mar 9, 2014 at 15:20
• @Goos: Thanks, fixed. The line is in the convex hull since: (a) $y = x-1$ is in the convex hull (b) for infinitely many $n$, there is a point $(n, \varphi(n))$ between the lines $y = c(x-1) + 1$ and $y = 1$.
– spin
Commented Mar 9, 2014 at 15:52
• @spin Thanks for clarifying, that is a good argument. Commented Mar 9, 2014 at 15:56

Relevant facts:

For infinitely many $n$, we have $$\varphi(n) < \frac{n}{e^\gamma \log \log n} \tag{1}$$ See here. But the constant $e^\gamma$ doesn't really matter. In fact, the simpler condition given in spin's answer suffices; i.e. that for any $0 < c < 1$, there are infinitely many $n$ such that $$\varphi(n) < cn \tag{2}$$

Claim: The convex hull $\text{conv } E$ is given by $$\{(1,1)\} \cup \left\{ (x,y) \; : \; 1 < y < x. \right\}.$$

Proof. Fix any real $x > 1$. For any $n$, $\text{conv } E$ contains the line segment between $(1,1)$ and $(n, \varphi(n))$. In particular, it contains the point $\left(x, \frac{\varphi(n) - 1}{n-1} (x-1) + 1\right)$.

For any $0 < c < 1$, find an $n$ satisfying (2). Then $\text{conv } E$ contains the point $(x,y)$ with $$y = \frac{\varphi(n) - 1}{n-1} (x-1) + 1 < \frac{cn - 1}{n-1} (x-1) + 1 < \frac{cn}{n / 2} (x-1) + 1 = \frac{c}{2} (x - 1) + 1$$ As $c \to 0$, this gives us points arbitrarily close to $(x, 1)$ in $\text{conv } E$. On the other hand, if we pick $n$ to be a large prime, $$y = \frac{\varphi(n) - 1}{n-1} (x-1) + 1 = \frac{n - 2}{n-1} (x-1) + 1 = \left(1 - \frac{1}{n-1} \right) (x-1) + 1$$ Since there are infinitely many primes, this gives us points arbitrarily close to $(x, x)$ in $\text{conv } E$.

For any two points $(x, y_1)$ and $(x,y_2)$, the segment between them is contained in $\text{conv } E$. Therefore, $\{x\} \times (1, x) \subset \text{conv } E$.

$x$ was arbitrary, so we have $\{ (x,y) \; : \: 1 < y < x \} \subset \text{conv } E$. Adding the point $(1,1)$, we arrive at a convex set containing $(n, \phi(n))$ for all $n$, so this must be the entire convex hull.

Here is a more precise bound in case you find it useful, even though the question is already answered.

It was shown by Nicolas, that for infinitely many positive integers $n$ we have $\displaystyle \frac{n}{\varphi(n)}>e^{\gamma}\log \log n$ where $\gamma$ is the Euler constant. You can find details in J.-L. Nicolas. Petites valeurs de la fonction d’Euler. J. Number Theory 17 (1983), 375–388.