I recently came up with an argument for a subset of Bertrand's Postulate that I have not seen anywhere else. Perhaps, it is not valid. It is very short. Please let me know if I have made a mistake.

(1) Let $p_n > 50$ be the $n$th prime.

(2) Let $p_n -c$ be the highest integer that is divisible by $6$ and less than $p_n$ so that $c$ is either $1, 3,$ or $5$

(3) Let $S$ be the set of all integers $x$ such that $p_n < x < 2p_n$ and $\gcd(x,p_n-c)=1$

(4) Let $U \subseteq S$ be the set of integers $x$ such that $x \in S$ but $x$ is not a prime. Let $u$ be the number of elements in $U$.

(5) All such $x$ in $U$ must have a least prime factor $q$ such that $5 \le q < \sqrt{2p_n}$.

(6) In all cases, $5 < \frac{x}{q} < p_n$ so that $p_n < p_n - c + \frac{x}{q} < 2p_n$ and $\gcd(p_n-c+\frac{x}{q},p_n-c)=1$ So, to be clear, for each of the $u$ non-primes, there are $u$ integers of the form $\frac{x}{q}$ where $p_n-c + \frac{x}{q}$ is between $p_n$ and $2p_n$ and $(p_n-c + \frac{x}{q})$ is relatively prime to $p_n-c$.

(7) Since $p_n < p_n -c + p_n < 2p_n$, we have the interesting situation where there are $u$ elements of $S$ that are non-primes but at least $u+1$ elements in $S$. So, one number between $p_n$ and $2p_n$ must be prime.

(8) To be clear, the $u+1$ consists of the $u$ integers of the form $(p_n-c + \frac{x}{q})$ and the $1$ integer of the form $(p_n-c + p_n)$. All $u+1$ are relatively prime $p_n-c$ and all $u+1$ are between $p_n$ and $2p_n$ but only $u$ are non-primes.

Edit: I made a change in step #1 in response to a comment by coffeemath.

Thanks, Coffeemath!

In order for $5 < \frac{x}{q} < p_n$, it is necessary that $p_n > 50$

With this correction, $\frac{p_n}{\sqrt{2p_n}} < \frac{x}{q} < p_n$ and:

$\frac{\sqrt{p_n}}{\sqrt{2}} > \frac{5\sqrt{2}}{\sqrt{2}} = 5$

Edit 2: Added step (8) in attempt to make the $u+1$ and the $u$ count much clearer.

I made this change in response to questions asked in the comments.

Edit 3: I am not able to get past the observation made by coffeemath. I am accepting coffeemath's answer.

  • $\begingroup$ In (6) it would be $5 \le x/q <p_n$ no? $\endgroup$ – coffeemath Apr 3 '17 at 14:13
  • 1
    $\begingroup$ I had attempted to prevent this condition by saying that $p_n > 25$ but the more I think about it, this requires a correction. $\frac{x}{q} > \frac{p_n}{\sqrt{2p_n}}$ so to make it larger than $5$ (which is needed), $p_n$ must be greater than $50$. I'll update this. If $p_n > 50$, then $\frac{p_n}{\sqrt{2p_n}}$ is always greater than $5$. $\endgroup$ – Larry Freeman Apr 3 '17 at 14:29
  • 1
    $\begingroup$ IMO this needs a bit more explanation as to why at least $u+1$ elements in $S.$ [at least I don't immediately see that.] $\endgroup$ – coffeemath Apr 3 '17 at 14:39
  • $\begingroup$ I agree with cofeemath's comment. I don't see how to count the number of elements in $S$ that are prime or that are composite from this inequality $\endgroup$ – Stella Biderman Apr 3 '17 at 14:41
  • 1
    $\begingroup$ Not sure how $c$ can be $3$ - I would expect $c\in\{1,5\}$. Otherwise still thinking about this general line of proof... $\endgroup$ – Joffan Apr 3 '17 at 15:15

Suppose $p_n=53>50.$ Then $c=5$ and $p_n-c=48=2^4\cdot 3.$ So $S$ consists of $$55,59,61,65,67,71,73,77,79,83,85,89,91,95,97,101,103.$$ The elements of $U$ are the non-primes of this list, namely $$55,65,77,85,91,95.$$ Dividing each by its least prime factor gives respectively $11,13,11,17,13,19.$ These are the values of $x/q$ for $x \in U.$ Note they are not all distinct; two repeats. When we then calculate $p_n-c+x/q$ we get the list $$59,61,59,65,61,67.$$ Again we have nondistinct values, with $59,61$ there twice each. [also the $65$ isn't prime, don't know if that's the problem...] The repeats seem to mean a double count has occurred.

  • $\begingroup$ Thanks very much! This shows that the argument as currently stated is incorrect. :-). I will see if I can find a way to fix the double counting. If I cannot, I will accept your answer. $\endgroup$ – Larry Freeman Apr 4 '17 at 13:40
  • $\begingroup$ @LarryFreeman It would be nice if such a fix could be done, especially as the "usual" Bertrand proof is a bit involved! $\endgroup$ – coffeemath Apr 4 '17 at 13:55

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.