2
$\begingroup$

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.

$\endgroup$
16
  • $\begingroup$ To prove the consecutive composites , you do not need the inequality. For the inequality, is Bertrand's postulate easy enough or do you want an even more elementary proof ? $\endgroup$ – Peter Jul 7 '20 at 15:38
  • 1
    $\begingroup$ Do you accept Bertrand's Postulate as elementary? It has an elementary proof, and it is widely known. $\endgroup$ – Batominovski Jul 7 '20 at 17:26
  • $\begingroup$ @Peter but I need the inequality because $n\#-m=(n\#/m-1)*m$ could have first factor 1, eg for $n=4$, $n\#-n=6-4=2$ is prime and also $n\#-3=4\#-3=6-3=3$ also prime. As regards Bertrand's postulate, that would do it because it says for any $n$ there is a prime $n<p<2n-2$. if $n=2t$ is even we have $t<p<2t-2=n-2$, so if $n>=5$, we have $t>=3$ and $n\#>=p\#>=2*3*p=6*p>6*t=3*n$ if instead $n=2t+1$ is odd, we have $t<p<2t-2=n-3$. so if $n>=7$ we have $t>=3$ and $n\#>=p\#>=2*3*p=6*p>=6*t+6=3*n+3>3*n$. for odd $n=5$ we verify directly, $n\#=30>=15=3*5=3*n$. $\endgroup$ – Commenter Jul 7 '20 at 17:56
  • $\begingroup$ You could have much better lower bounds for $n$# that could still be proven. What exactly do you want to prove ? Is it something with prime gaps near a primorial ? $\endgroup$ – Peter Jul 7 '20 at 17:59
  • $\begingroup$ @Peter I just feel my inequality is vastly weaker than Bertrand's postulate, so feel there must be a more lightweight proof. $\endgroup$ – Commenter Jul 7 '20 at 18:00
1
$\begingroup$

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!

$\endgroup$
9
  • 1
    $\begingroup$ Nice work. Essentially, the quantitative bound from Euclid’s proof of the infinitude of primes, while much weaker than Bertrand, is sufficient here. Bertrand would imply something like $n# \gg c^{(\log n)^2}$ which is a significantly stronger bound. I don’t think it’s equivalent. $\endgroup$ – Erick Wong Jul 9 '20 at 3:12
  • $\begingroup$ Looks like a great insight to me. The only thing I would make clear is that when you say $M$ is a product of distinct primes $p$, you mean strictly that any particular prime is a factor of $M$ only once, i.e. $M$ is square free; I think that this is implied but not specifically stated. Otherwise, $\frac{n\#}{M}$ will not be an integer. $\endgroup$ – Keith Backman Jul 9 '20 at 15:28
  • $\begingroup$ @Erick Wong, could you redo that formula because it didnt format correctly! $\endgroup$ – Commenter Jul 9 '20 at 15:47
  • 1
    $\begingroup$ @Erick Wong, but at the same time I also am interested in more sophisticated ways of deriving things than the standard method! I find it interesting when there are incomparably different methodologies to accomplish something. At uni, some of our lecturers said its good to have coordinate free definitions and derivations. Essentially what I am saying is that methodology itself is something to study and one can assess the methodology of a derivation and eg consider the total work to derive from first principles, including the work to derive the results quoted eg Bertrands Postulate! $\endgroup$ – Commenter Jul 10 '20 at 0:51
  • 1
    $\begingroup$ @Erick Wong I have managed to prove some further things using elementary methods, in particular that if p>=5 is prime and q is the next prime, then the sets {p#-2,p#-3,...,p#-(q-1)} and {p#+2,...,p#+q-1} are all disjoint AND composite, no overlapping. Also if r is the next prime after q, then q#-p#>=q+r, Bertrand obviously gives a much better bound for r, namely 2q. Bertrand repeatedly presents simpler proofs, Its like different gears! elementary, Bertrand, PNT. I think we should call it Joseph Bertrand's postulate to disambiguate from Bertrand Russell! $\endgroup$ – Commenter Jul 14 '20 at 16:20
0
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ The author wants an even simpler argument. $\endgroup$ – Peter Jul 7 '20 at 18:11
  • 1
    $\begingroup$ Bertrand's postulate is quite a tough result, whereas my inequality seems very weak, thus it is philosophically unsatisfactory to use a very powerful result to prove a weak result. $n\#$ grows thus: $1,2,6,6,30,30,210,210,210,210,2310,2310,30030,30030,30030,30030,510510,etc$ we want bigger than $n/a,n/a,n/a,n/a,15,18,21,24,27,30,33,36,39,42,45,48,51,etc$ respectively, seems MUCH WEAKER than Bertrand's postulate! $\endgroup$ – Commenter Jul 7 '20 at 18:20
  • 1
    $\begingroup$ @Keith Backman you say that essentially I am on a fool's errand for the general case! But do you think there could be a simple proof for some specific genres of numbers other than products of distinct primes, or do you think its a fools errand for anything other than products of distinct primes? $\endgroup$ – Commenter Jul 7 '20 at 19:58
  • 1
    $\begingroup$ @Commenter Don't be too negative about your instincts. My point is that using the approach I outlined you have to prove something for some value of $m$, and Bertrand's Postulate proves that something for $m=2$. Nobody is aware of any other approach at present, and lots of people have thought about this long and hard, so proof by another route is not likely. Nonetheless, unknown things remain unknown until they are discovered, so it is not impossible that you or some other mathematician might develop a different line of attack which is simpler than Bertrand. $\endgroup$ – Keith Backman Jul 8 '20 at 15:28
  • 2
    $\begingroup$ @Keith Backman I have found a trivial solution of the inequality, and also a trivial solution for finding arbitrarily good lower bounds, see my answer to my post. If it really is equivalent to Bertrand's Postulate, then we could get a trivial solution to that, but I dont know how to proceed. $\endgroup$ – Commenter Jul 9 '20 at 2:35

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.