# What is wrong with this effort to generalize Bertrand's Postulate using the Inclusion-Exclusion Principle

The following argument is too elementary to be true but I am not clear where the error is. I would appreciate it if you could call out what is logically wrong or provide a counter example to one claim in the argument.

Let $n \ge 128$ be an integer.

Let $1 \le a \le n$ be an integer.

Let lpf$(x)$ be the least prime factor of $x$.

Let $\frac{n}{4}\#$ be the primorial for $\left\lfloor\frac{n}{4}\right\rfloor$.

Claim: There is at least one prime between $an$ and $an+n$.

(1) Either lpf($x) \le \sqrt{x}$ or $x$ is a prime.

(2) There are at least $3$ integers $x$ where $an < x \le (an+n)$ and $\gcd(x,\frac{n}{4}\#)=1$.

The details for this argument are found here.

(3) There is at most $1$ integer $x$ where $an < x \le (an+n)$ and $n \ge$ lpf$(x) \ge \frac{n}{4}$

The details for this argument are found here.

(4) So, at least $2$ integers $x$ where $an < x \le (an+n)$ have lpf$(x) > n$

(5) But for $m < (n^2+n)$, if lpf$(m) > n$, then lpf$(m) > \sqrt{m}$ and $m$ is a prime.

(6) It follows that at least one integer $x$ where $an < x < (an+n)$ is prime.

Edit 1: Gerhard Paseman has pointed out a problem with my assumption used in the original argument for step (2).

For this reason, I am now using this argument for step (2).

• Interesting idea look at the number of primes between $an$ and $(a+1)n$ for $a=1,\cdots ,n$ ... From the Betrand postulate to the (nearly) Legendre conjecture ... Thanks for idea ! ... Oh, no idea what is wrong with the above arguement ...$\ddot \smile$ – Donald Splutterwit Jun 5 '17 at 15:18
• Thanks, Donald. This one has been keeping me up at night for the last week. I am very interested in finding the problem. :-) – Larry Freeman Jun 5 '17 at 16:17
• @LarryFreeman, you might want to try posting this question to MathOverflow, to see what the number theory experts there would say... – Jose Arnaldo Bebita-Dris Jun 7 '17 at 15:14
• Thanks @Jose for the suggestion! I have posted a question on mo related to the Heilbronn-Rohrbach Inequality which will hopefully provide insights on the validity of Claim 2. – Larry Freeman Jun 7 '17 at 17:44
• what does "too elementary to be true" mean? Is $2+2=4$ too elementary to be true? Do you have a specific $a$ and $n$ that provide a counterexample? – Mirko Jun 10 '17 at 1:33

This answer falls short of what might be considered an adequate response, but does offer good evidence for the veracity of what is stated in the question.

The assertion : There is at least $1$ prime in the interval $(an,(a+1)n]$ for $1 \leq a \leq n$ & $n \geq 2$ , is true (IMO).

Given a value of $n$, how many primes are there between $n$ and $2n$ ? Of course Bertrands postulate states that there is at least one. Classic proofs of this are given by Ramanujan & Erdos, they are closely related to original proof given by Chebyshev.

How many primes are there between $2n$ & $3n$ or $3n$ or $4n$ or $\cdots$ or $an$ & $(a+1)n$ ?

The following bar chart shows how many are primes are in each interval for the value $n=6$ (The red line indicates a frequency of three). This pictorially represents that the intervals $[1,6],[7,12],[13,18],[19,24],[25,30],[31,36],[37,42]$ contain $3,2,2,2,1,1,2$ primes respectively.

Numerical experimentation certainly suggests the answer there is at least one prime in each interval $(an,(a+1)n]$ for $1 \leq a \leq n$ & $n \geq 2$. So (we believe) the major claim of the question is true & the restriction $n \geq 128$ can be relaxed to $n \geq 2$.

We shall now look more closely at assertion (2). Firstly we shall tighten, the constraint that the values are coprime to the "quarter primorial", to require the values to be prime.

So we are interested in the question: When do all the intervals $(an,(a+1)n]$ contain at least $3$ primes ?

For "small" values of $n$ the assertion is of course negative. The first value when this phenomena occurs is when $n=26$.

It also fails for the n-values $27,30,31,37,38,39,\color{red}{40}$.

So (we believe) a slightly modified version of assertion (2) is ture for $n \geq 41$.

We include the graph for $n=128$ as this value lowest limit used in the question.