## Question

For what percentage of numbers does the below inequality hold?

$$ pi(2m) > frac{phi(2 m) -1}{2} $$

where $m$ is not a prime or $1$, $pi(m)$ is the number of primes less than $m$ and $phi$ is the Euler totient function.

## Background + Proof

I was trying to prove Goldbach’s Conjecture are realised I could do it for certain numbers.

Consider the following where $m$ is not a prime:

$$ (2m)! = 2m^2 (m^2 -1)(m^2 -4)(m^2 -9) dots (m^2 -(m-1)^2)$$

Notice, $(2m)!$ will contain primes of the form $p_k =m pm n leq 2m$. The number of such primes are $pi(2m)$. Further, the $m$ and $n$ must be co-prime. Then the number of possible “slots” of the form $m pm n$ which can house primes (disregarding $p_1 = 2$) are:

$$ S(m) = phi(2 m) -1 $$

To derive the above the following are considered:

$1$. If $m$ is even then $(m^2 – (text{even})^2) = text{even}$

$2$. $m$ is not a prime as mentioned before.

$3$. $m – (m-1)$ is cannot be a prime.

Now, if:

$$ pi(2m) > frac{S(m)}{2} $$

Then we can prove Goldbach’s conjecture for that number as that would imply one of the slots $m+n = p_i$ has a corresponding slot housing a prime $m+n =p_k$. And thus, if add both of them:

$$ 2m = p_i + p_k$$

## Example

Consider $m = 15 = 3 cdot 5$. After considering $30!$ eliminating “slots”:

$$ S(15) = (1-frac{1}{3})(1-frac{1}{5}) 30 – 1= 15 $$

where the remaining slots are:

$$ (m^2 -1),(m^2 -7^2),(m^2 -11^2),(m^2 -13^2),(m^2 -17^2),(m^2 -19^2),(m^2 -23^2),(m + 29) $$

However, the number of primes are $pi(30) = 10$. Since, there are more primes than “slots” available for them. Then one of the slots of the form $m$.

(Note, I didn’t read the background, just the question.)

One has

$$pi(2x) sim frac{2x}{log x}$$

by the prime number theorem and

and

$$phi(x) gg frac{e^{-gamma} x}{log log x}$$

by standard estimates (see the wikipedia page https://en.wikipedia.org/wiki/Euler%27s_totient_function), so since the latter grows much faster there can only be finitely many integers satisfying your inequality (and this finite set has density zero, obviously). More precisely, one has:

$$frac{n}{phi(n)} le e^{gamma} left( log log n + frac{2.5}{e^{gamma} log log n} right)$$

for all $n ge 3$ except for $n = 3 times 5 times 7 times 11 times 13 times 17 times 19 times 23$,

(See Lemma 4 here: https://empslocal.ex.ac.uk/people/staff/mrwatkin/zeta/grytczuk.pdf)

and

$$pi(x) < 1.25506 cdot frac{x}{log x}$$

for $x ge 17$ (see https://en.wikipedia.org/wiki/Prime-counting_function) and just from these inequalities (computing $phi(223092870)$ by hand) we already get

$$frac{phi(2x) – 1}{2} > pi(2x), quad x > 10^6$$

But then the smaller examples one can check by computer, and find the inequality you want holds for exactly $649$ integers, the largest one being $45045$ with

$$frac{phi(90090) – 1}{2} = 8639.5 < 8726 = pi(90090).$$

We can rephrase your question as: for which $m$ does

$$

pi(2m) geq frac{phi(2 m)}{2}

$$

hold, or equivalentely

$$

frac{phi(2m)}{pi(2m)} leq 2.

$$

Now for large enough $m$, $pi(m) approx frac{m}{log(m)}$, so this inequality becomes (roughly speaking)

$$

frac{phi(2m)log(m)}{m} leq 2.

$$

One expression for $phi(k)$ is $kprod_{p mid k}left(1-frac1pright)$, where the variable $p$ runs over the primes, so we can rewrite this as

$$

log(m)prod_{p mid 2m}left(1-frac1pright) leq 1.

$$

Taking logarithms on both sides,

$$

log(log(m)) + sum_{p mid 2m}logleft(1-frac1pright) leq 0.

$$

For large $p$, $-frac1p$ is a good approximation for $logleft(1-frac1pright)$, so the question becomes

$$

log(log(m)) – sum_{p mid 2m} frac1p leq 0.

$$

Now a standard approximation tells us that this last sum is approximately equal to $log(log(p))$ where $p$ is the largest prime in the sum. Clearly the largest prime in this sum will be much smaller than $m$, because we took the best case $m$: where $m$ is a product of lots of distinct small primes.

Thus your inequality should hold almost never.