# Does this inequality hold true, in general?

Let

$$N = \prod_{i=1}^{\omega(N)}{{p_i}^{\alpha_i}}$$

be the prime factorization of the positive integer $N$.

Does the following inequality hold true in general?

$$\prod_{i=1}^{\omega(N)}{\frac{p_i}{p_i - 1}} < \frac{2\prod_{i=1}^{\omega(N)}{p_i}}{1 + \prod_{i=1}^{\omega(N)}{p_i}}$$

If not, for what particular values of $N$ does this inequality hold?

Note that $\omega(N)$ denotes the number of distinct prime factors of $N$.

It turns out that that inequality is true about 95% of the time.

As in my previous answer, cancel the numerator of each side to get the equivalent inequality

$\prod_{i=1}^{\omega(N)}{\dfrac{1}{p_i - 1}} < \dfrac{2}{1 + \prod_{i=1}^{\omega(N)}{p_i}}$ or $1 + \prod_{i=1}^{\omega(N)}{p_i} < 2\prod_{i=1}^{\omega(N)}(p_i - 1)$.

Dividing by $\prod_{i=1}^{\omega(N)}{p_i}$, and, using the fact that $\dfrac{\phi(n)}{n} =\prod_{i=1}^{\omega(N)}\dfrac{p_i-1}{p_i}$, this becomes $1+\dfrac{1}{\phi(n)} <2\dfrac{\phi(n)}{n}$.

Since $\dfrac{1}{\phi(n)}$ is small for large $n$, the proportion of $n$ satisfying this is the same as the proportion satisfying $\frac{1}{2} <\dfrac{\phi(n)}{n}$, or $2 >\dfrac{n}{\phi(n)}$.

At this point, I did a Google search for "density of euler phi function". The second link is http://www.ams.org/journals/proc/2007-135-09/S0002-9939-07-08771-0/S0002-9939-07-08771-0.pdf. This paper, by ANDREAS WEINGARTNER, is titled "THE DISTRIBUTION FUNCTIONS OF σ(n)/n AND n/ϕ(n)". Here is its abstract:

"Let σ(n) be the sum of the positive divisors of n. We show that the natural density of the set of integers n satisfying σ(n)/n ≥ t is given by $\exp\big(−e^{t e^{−γ}(1 + O(t^{−2}))}\big)$ , where γ denotes Euler’s constant. The same result holds when σ(n)/n is replaced by n/ϕ(n), where ϕ is Euler’s totient function."

This paper has clearly done the heavy lifting. If we put $t = 2$, and use $\gamma \approx 0.5772156649$ (I show each stage in the computation for checkability), $te^{-\gamma} = 1.1229189671$, $e^{te^{-\gamma}}=3.0738134815$, $\exp(-e^{te^{-\gamma}}) =0.0462444658$.

This is the density of $n$ for which $\dfrac{n}{\phi(n)} > 2$. The density for which $\dfrac{n}{\phi(n)} < 2$ is one minus this or $0.9537555342$.

• Thank you for your very comprehensive (and interesting!) answer, @martycohen. =) – Jose Arnaldo Bebita-Dris Jul 30 '13 at 1:31
• I apologize @martycohen, but I just spotted (today) what seems to be an "error" from the inequality $$1 + \prod_{i=1}^{\omega(N)}{p_i} < 2\prod_{i=1}^{\omega(N)}{(p_i - 1)},$$ from which we obtain, upon dividing through by $\prod_{i=1}^{\omega(N)}{p_i}$, $$1 + \frac{1}{N} < 2\frac{\phi(N)}{N}.$$ Thus, we get the inequality $$\frac{N}{\phi(N)} < \frac{2N}{N + 1}.$$ If $N > 1$, then $$I(N) = \frac{\sigma(N)}{N} < \frac{N}{\phi(N)} < \frac{2N}{N + 1},$$ where $I(N)$ is the abundancy index of $x$ and $\sigma(N)$ is the sum of divisors of $N$. – Jose Arnaldo Bebita-Dris Aug 7 '13 at 20:02
• This earlier MSE question of mine then appears relevant. In particular, MSE user Tharsis conjectures that ${\it all}$ odd deficient numbers satisfies $$I(N) = \frac{\sigma(N)}{N} < \frac{2N}{N + 1}.$$ – Jose Arnaldo Bebita-Dris Aug 7 '13 at 20:07
• Looking at your post beginning at the fourth sentence @martycohen, I can see that, since the inequality $$I(N) = \frac{\sigma(N)}{N} < \frac{N}{\phi(N)} < \frac{2N}{N + 1} < 2$$ from my earlier comment here results to the same inequality $$\frac{1}{2} < \frac{\phi(N)}{N}$$ from your fourth sentence in this post, the succeeding claims still hold true, I'd suppose? =) – Jose Arnaldo Bebita-Dris Aug 7 '13 at 22:25
• Please refer to this newer MSE question for more details. – Jose Arnaldo Bebita-Dris Aug 7 '13 at 22:27

We can cancel the numerator of each side to get the equivalent inequality

$\prod_{i=1}^{\omega(N)}{\dfrac{1}{p_i - 1}} < \dfrac{2}{1 + \prod_{i=1}^{\omega(N)}{p_i}}$ or $1 + \prod_{i=1}^{\omega(N)}{p_i} < 2\prod_{i=1}^{\omega(N)}(p_i - 1)$.

Let's look at the sum over primes $f(x) = \sum_{p < x} \ln (p-1)$. Since $\sum_{p < x} \ln p \approx x$ (from the prime number theorem),

\begin{align} f(x) &=\sum_{p < x} \ln (p-1)\\ &=\sum_{p < x} (\ln p+\ln(1-1/p))\\ &=\sum_{p < x} \ln p+\sum_{p < x}\ln(1-1/p)\\ &\approx x-\sum_{p < x}(1/p+1/(2p^2)+...)\\ &\approx x-\ln \ln x+C\\ \end{align}

From this, $e^{f(x)} \approx e^{x-\ln \ln x+C} = C_1 e^x/\ln x$.

If $N(x) = \prod_{p < x} p$ and $M(x) = \prod_{p < x} (p-1)$, $N(x) \approx e^x$ and $M(x) \approx C_1 e^x/\ln x$, $1+N(x) < 2M(x)$ means, for large enough $x$, $e^x < C_1 e^x/\ln x$, which is false.

So that inequality is often false.

• Thank you for your answer @martycohen! I think that your answer is somewhat inconsistent with what I was expecting, since the density of the integers that I "expect" to satisfy that inequality is a bit high - at least $\approx 0.831$, but then again, this is subject of course to an "underlying hypothesis". Again, my profuse thanks for taking the time to answer my MSE question. =) – Jose Arnaldo Bebita-Dris Jul 17 '13 at 7:22
• BTW, it can be shown that the inequality holds for odd primes and (odd) prime powers. It does ${\it not}$ hold for the (even) prime $2$. – Jose Arnaldo Bebita-Dris Jul 17 '13 at 7:25
• Please refer to this newer MSE question for more details. – Jose Arnaldo Bebita-Dris Aug 7 '13 at 22:28