Prove by elementary means that $n\#\geq 3n$ for $n\geq 5$, where $n\#$ is the primorial function.

Question

Prove by elementary means that $$n\#\geq 3n$$ for $n\geq 5$, where $n\#$ is the primorial function.

update: I have found an elementary proof, see my answer to my question. The remainder of this post is the original question:

From the replies this is no longer a conjecture but is a fact!

So far the only derivations given are based on Bertrand's postulate and that does work.

The idea emerged from another post where I now realise that the argument I gave leading to this question was a flawed argument, so I am removing that reference. In fact that reference now refers here instead!:

https://math.stackexchange.com/a/3748110/804099

Instead the correct argument is this:

I want to show that $n\#-2,n\#-3,...,n\#-n$ are consecutive composite numbers in descending order, where $n>=5$. Let $p$ be a prime factor of $m$, where $2<=m<=n$. Then $p$ is a common factor of $n\#$ and $m$, and $n\#-m=p*((n\#-m)/p)$. For this to be composite we need the second factor greater than 1, ie $(n\#-m)/p>1$, ie $n\#-m>p$ ie $n\#>m+p$. Now if $n\#>=3n$ is true, then $n\#>=3n>n+n>=m+p$ and we have the result.

The remaining question is whether someone can give an elementary direct proof which doesnt refer to Bertrand's postulate.

The primorial of $n$ is the product of all primes $p\leq n$, e.g. $6\#=2\cdot 3\cdot 5=30$.

The best I have proven directly is that if $n\geq5$ is a product of distinct primes, then it is true.

Because if $n$ is even then $n-1$ is odd and coprime to $n$: let $p$ be any prime factor of $n-1$.

whereas if $n$ is odd then $n-2$ is odd and coprime to $n$: let $p$ be any prime factor of $n-2$,

In both cases, $p$ is odd and thus $p\geq3$ and also $p$ is coprime to $n$.

$n\#\geq pn$ because the RHS divides the LHS as its a product of distinct primes, as $n$ is a product of distinct primes and $p$ is not a factor of $n$. Thus $n\#\geq pn\geq3n$.

But I am unable to progress on more general $n\geq5$ without referencing Bertrand's postulate which says that for any integer $N>3$ there is a prime $N<p<2N-2$ . As the primorial function whizzes upwards with enormous speed, the result seems very likely, but has eluded me so far! It took some work to establish the result for $n\geq5$ a product of distinct primes.

UPDATE: I have proved it without reference to Bertrand's postulate, see my answer to my question.

Establishing the result for other categories of $n\geq5$ will also be useful.

Answer 1

For $5\le p_k\le n< p_{k+1}$, to prove $n\# \ge 3n$ it is sufficient to prove $p_k\#>3p_{k+1}$. Since $5=p_3$, $p_k\#\ge 2\cdot 3\cdot p_k = 6p_k$.

So you need to show that $6p_k\ge 3p_{k+1} \Rightarrow 2p_k>p_{k+1}$

This last formulation is known as Bertrand's postulate, which has been proved, although the proof is beyond a simple exposition in this forum.

Answer 2

EUREKA!

I have found an elementary solution to the problem that for $n>=5$ we have $n\#>=3*n$

the proof is as follows,

for $n>=5$ we have $n\#>=5\#=2*3*5=30$, so $N=n\#/3-3>=7$, now $n\#/3$ is an integer because $3$ is a factor of $n\#$, so $N=n\#/3-3$ is an integer 7 or higher, thus it has a prime factor $q$. But $q$ is coprime to $n\#$ because if $p$ is a prime $p<=n$ and its not 3, then it divides $n\#/3$ and thus cannot divide $N$, and if $p$ is 3, it cannot divide $n\#/3-3$. Thus $n\#/3>n\#/3-3>q>n$, and so $n\#>3*n$ QED!

I can then generalise the theorem to arbitrarily good lower bounds, as follows:

If $M$ is a product of distinct primes $p$, where the largest one is $P$, then if $n>=P$ AND $n\#>M^2+M$, then $M$ divides $n\#$, so $n\#/M$ is an integer and $n\#/M>M+1$ thus $T=n\#/M-M>=2$ so there exists a prime factor $q$ of $T$ but we must have $q>n$, because if $q<=n$ then either $q$ is a factor of $M$, but then its not a factor of $T$ a contradiction; or its a factor of $n\#/M$ but then also its not a factor of $T$ another contradiction. Thus $n\#/M >n\#/M-M>=q>n$, and so $n\#>M*n$ in fact $n\#/M-M>=n+1$ so $n\#>=M*n+M+M^2$

We thus have a theorem: if $M$ is a product of distinct primes $p$ where the largest is $P$, and if $n>=P$ AND $n\#>=M^2+M+1$ THEN $n\#>=M*n+M+M^2$, a lower bound for $n\#$

(where all the inequalities have been paraphrased as $>=$ rather than $>$ to avoid misquoting. What I am really saying is $P$ divides $M$ divides $P\#$. For $M=1$ we dont need the condition $n>=P$)

as an application, let $M=2*3*5=30$, here $P=5$, so if $n>=5$ and $n\#>=30^2+30+1=931$ then $n\#>=30*n+930$. To have $n\#>=931$ we need just that $n>=11$, so the example theorem is:

if $n>=11$ then $n\#>=30*n+930$

for the case of $n=11$ it says $n\#=2310>=1260$.

for the original case of $M=3$, here $P=3$, so if $n>=3$ AND $n\#>=3*3+3+1=13$, then $n\#>=3*n+12$, but $n\#>=13$ means $n>=5$ and we get the original inequality, that for all $n>=5$, we have $n\#>=3*n+12$

I can also generalise the inequality thus: let $t$ be a product of distinct primes, with biggest one $P$, and let $T$ be the same product of primes but with some or none of the exponents boosted. eg if $t=2*5*11*13$ then an example of $T$ is $2*5^9*11^2*13$

Assume $n>=P$, and $n\#>=t*T+2*t$, then clearly $t$ is a divisor of $n\#$, ie $n\#/t$ is integer. If we look at $X=n\#/t-T$ then $n\#$ and $T$ have disjoint prime factors and in totality these are all the primes up to $n$. Thus all prime factors of $X$ are greater than $n$. As $X=n\#/t-T>=2$, $X$ has at least one prime factor $q$, and so $X=n\#/t-T>=q>n$, ie $n\#/t-T>=n+1$, thus $n\#-T*t>=t*n+t$ ie $n\#>=t*n+t+T*t$ and we have the generalisation:

if $t$ is a product of distinct primes, with maximum one $P$, and if $T$ is the same product but with some or none of the exponents boosted, then if $n>=P$ AND $n\#>=t*T+2*t$ then $n\#>=t*n+t+T*t$

example: $t=2*3*5=30$ and $T=2^2*3*5=60$, $P=5$, so if $n>=5$ AND $n\#>=30*60+2*30=1860$ which is the same as $n>=11$, then $n\#>=30*n+30+60*30=30*n+1830$

which paraphrases to:

if $n>=11$ then $n\#>=30*n+1830$.

for the case of $n=11$, it says $11\#=2310>=30*11+1830=330+1830=2160$ which is a more accurate estimate than the one earlier.

The optimal lower bounds for $n$ will be prime, eg $n>=11$, and for a particular lower bound for $n$ eg $n>=q$, eg $q=11$ we can maximise the constant factor of $n$ for the lower bound for $n\#$, by manually finding the maximum $q>=2*t+t^2$, and then the maximum $q>=2*t+t*T$ for this $t$. eg for $q=11$, manually we find $t=2*3*7=T$ and get the following theorem:

if $n>=11$ then $n\#>=42*n+1806$,

for $n=11$ this says $2310=11\#>=42*11+1806=2268$ and for $n=12$ this says $2310=12\#>=42*12+1806=2310$

Further to a question by Keith Backman, $M$ and $t$ are squarefree and $>1$, for the case where $M=1$ or $t=T=1$, you can drop the condition that $n>=P$ as the proofs work then without that condition. When I say product of distinct primes I mean the factorisation is eg $2*7*11*13*23*37$, but not eg $2*3*3$, because the second and 3rd primes are the same, namely $3$ here and also that there is at least one prime eg $M=3$, $t=5,T=25$ are ok. I need $n>=max(primefactors(M))=P$ for the proof to work, unless $M=1$ when that condition can be omitted.

with my original post I blundered as regards non squarefree, but I have corrected that error, so reread my editted posts.

Now if the original inequality really is equivalent to Bertrand's Postulate, then we could get a proof of that, but I dont know how to proceed!