2
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thank you for your very comprehensive (and interesting!) answer, @martycohen. =) $\endgroup$ – Jose Arnaldo Bebita-Dris Jul 30 '13 at 1:31
  • $\begingroup$ 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$. $\endgroup$ – Jose Arnaldo Bebita-Dris Aug 7 '13 at 20:02
  • $\begingroup$ 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}.$$ $\endgroup$ – Jose Arnaldo Bebita-Dris Aug 7 '13 at 20:07
  • $\begingroup$ 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? =) $\endgroup$ – Jose Arnaldo Bebita-Dris Aug 7 '13 at 22:25
  • $\begingroup$ Please refer to this newer MSE question for more details. $\endgroup$ – Jose Arnaldo Bebita-Dris Aug 7 '13 at 22:27
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. =) $\endgroup$ – Jose Arnaldo Bebita-Dris Jul 17 '13 at 7:22
  • $\begingroup$ 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$. $\endgroup$ – Jose Arnaldo Bebita-Dris Jul 17 '13 at 7:25
  • $\begingroup$ Please refer to this newer MSE question for more details. $\endgroup$ – Jose Arnaldo Bebita-Dris Aug 7 '13 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.