# Analyzing whether there is always a prime between $n^2$ and $n^2+n$

I was working on generalizing the theorem of Sylvester and Schur when it occurred to me that the argument showed that there was always a prime between $n^2$ and $n^2+n$

I am sure there must be a mistake since the argument is too simple. I apologize for its length. I have tried to make it as short as possible.

If you can help me to find the mistake or point out opportunities to simplify or shorten the argument, I would appreciate it.

I have fixed the mistake pointed out by Misha. Here is the argument:

(1) $\pi(n) \le \left\lfloor\frac{4n}{15}\right\rfloor + 6$

$$\pi(n) \le \left\lfloor\frac{n+1}{30}\right\rfloor + \left\lfloor\frac{n+7}{30}\right\rfloor+ \left\lfloor\frac{n+11}{30}\right\rfloor + \left\lfloor\frac{n+13}{30}\right\rfloor + \left\lfloor\frac{n+17}{30}\right\rfloor + \left\lfloor\frac{n+19}{30}\right\rfloor + \left\lfloor\frac{n+23}{30}\right\rfloor+\left\lfloor\frac{n+29}{30}\right\rfloor + 2 \le \frac{n+1}{30} + \dots + \frac{n+29}{30} + 2 = \frac{4}{15}n + 6$$

(2) if $n > 30$, $n - \left\lceil\frac{4n}{15}\right\rceil-6 > \left\lceil\frac{4n}{15}\right\rceil + 6$

$\frac{7n}{15} > 14$ so $n > \frac{8n}{15}+14$ and $n - \left(\frac{4}{15}n+1\right) - 6 > \left(\frac{4n}{15}+1\right) + 6$

(3) if $n>10$, then $n > \sqrt[2\left\lfloor\frac{4n}{15}\right\rfloor+12]{\left(2\left\lfloor\frac{4n}{15}\right\rfloor+12\right)!}$

$\frac{176n^2}{225} + \frac{100n}{15} > 156$ so that $\frac{16n^2-60n}{15} + 24n > \frac{64n^2}{225} + \frac{96n}{15} + \frac{104n}{15} + 156$ and $n > \frac{\left(\frac{8n}{15}+12\right)\left(\frac{8n}{15}+13\right)}{4\left(\frac{4n-15}{15}\right)+24}$

$n > \frac{\left(2\left\lfloor\frac{4n}{15}\right\rfloor+12\right)\left(2\left\lfloor\frac{4n}{15}\right\rfloor+13\right)}{4\left\lfloor\frac{4n}{15}\right\rfloor+24} = \frac{1 + \dots + \left(2\left\lfloor\frac{4n}{15}\right\rfloor+12\right)}{2\left\lfloor\frac{4n}{15}\right\rfloor+12} > \sqrt[\left(2\left\lfloor\frac{4n}{15}\right\rfloor+12\right)]{\left(2\left\lfloor\frac{4n}{15}\right\rfloor+12\right)!}$

(4) Let $v_p(x)$ be the highest power of $p$ such that $p^{v_p(x)} \le x$

(5) $n^2 > \sqrt[\left(2\left\lfloor\frac{4n}{15}\right\rfloor+12\right)]{\prod\limits_{p \le n}p^{v_p(n^2)}\left(2\left\lfloor\frac{4n}{15}\right\rfloor+12\right)!}$

$(n^2)^{\left\lfloor\frac{4n}{15}\right\rfloor+6} > (n^2)^{\pi(n)} >\prod\limits_{p < n} p^{v_p(n^2)}$ so that $n > \sqrt[\left(2\left\lfloor\frac{4n}{15}\right\rfloor+12\right)]{\prod\limits_{p < n} p^{v_p(n^2)}}$ and with step(3), $n^2 > \sqrt[\left(2\left\lfloor\frac{4n}{15}\right\rfloor+12\right)]{\prod\limits_{p \le n}p^{v_p(n^2)}\left(2\left\lfloor\frac{4n}{15}\right\rfloor+12\right)!}$

(6) From step (2), for n > 30, we know that there are at least $\left(\left\lceil\frac{8n}{15}\right\rceil+12\right)$ integers in the sequence $n^2 + 1, \dots, n^2+n-1$

(7) Let $V = \prod\limits_{p < n} {p^{v_p(n^2)}}$

(8) Let $gpf(x)$ be the greatest prime factor of $x$.

(9) If $gpf(x) < n$ but $x \nmid V$, it follows that there exists $p^t$ where $p^t | x$ and $p < n$ and $p^t > n^2$.

(10) If $n^2 < x < \left(n^2+n\right)$ and $gpf(x) < n$ and $x \nmid V$ and $p^t > n^2$ and $p^t | x$, then it follows if $n^2 < w < \left(n^2 + n\right)$ where $w \ne x$, then if $p^s | w$, it follows that $p^s \le n^2$.

Assume that $p^s > n^2$, then we have a contradiction since $abs(w - x) < n$ and $p^s | abs(w - x)$ but $p^s > n$ which is impossible.

(11) From step (10), we can conclude that there are at most $\left\lfloor\frac{4n}{15}\right\rfloor + 6 > \pi(n)$ integers between $n^2$ and $\left(n^2 + n\right)$ which are divisible by a prime $p^v$ where $p^v > n^2$ and $p < n$

(12) So, between $n^2$ and $\left(n^2+n\right)$, there are at least $\left\lfloor\frac{4n}{15}\right\rfloor+6$ integers where none are divisible by $p^v$ where $p < n$ and $p^v > n^2$.

(13) Assume that for all $n^2 < x < (n^2+n)$, $x$ is not prime.

(14) Let $L=lcm(n^2+1, n^2+2, \dots, n^2+2\left\lfloor\frac{4n}{15}\right\rfloor + 12)$ be the least common multiple for the sequence $n^2 < x \le (n^2+2\left\lfloor\frac{4n}{15}\right\rfloor+12)$

(15) I claim that:

$$\frac{(n^2+2\left\lfloor\frac{4n}{15}\right\rfloor+12)!}{(n^2)!} \div L \le \left(2\left\lfloor\frac{4n}{15}\right\rfloor + 11\right)!$$

The argument for this can be found here.

(16) Let $U = \prod\limits_{p < n \text{ and }n^2 < p^w \le (n^2+2\left\lfloor\frac{4n}{15}\right\rfloor+12) } {p^w}$

(17) Since we are assuming that there are no primes between $n^2$ and $n^2 + n$ (step 13) and since all numbers $n^2 < x \le (n^2+2\left\lfloor\frac{4n}{15}\right\rfloor+12)$ that do not divide $V$ divide $U$, it follows that:

$$\frac{(n^2+2\left\lfloor\frac{4n}{15}\right\rfloor+12)!}{(n^2)!U} \div gcd(L,V) \le \left(2\left\lfloor\frac{4n}{15}\right\rfloor + 12\right)!$$

(18) Let $g_p(x,n)$ be the highest power of $p$ that divides $x+i$ where $0 < i < n$ and which divides $V$.

In other words, $g_p(x,n) = gcd(p^{v_p(n^2)},\frac{(x+n-1)!}{(x)!})$

(19) We can see that $gcd(L,V) = \prod\limits_{p < n}{p^{g_p(n^2,n)}} \le \prod\limits_{p < n}{p^{v_p(n^2)}}$

(20) So that we can conclude:

$$\frac{(n^2+2\left\lfloor\frac{4n}{15}\right\rfloor+12)!}{(n^2)!U} \le \prod\limits_{p < n}{p^{g_p(n^2,n)}}\left(2\left\lfloor\frac{4n}{15}\right\rfloor + 12\right)!$$

(21) But here we have a contradiction since:

$$\frac{(n^2+2\left\lfloor\frac{4n}{15}\right\rfloor+12)!}{(n^2)!U} > (n^2)^{2\left\lfloor\frac{4n}{15}\right\rfloor+12} > \prod\limits_{p \le n}p^{v_p(n^2)}\left(2\left\lfloor\frac{4n}{15}\right\rfloor+12\right)!$$

(22) For $2 \le n<31$, we can manually verify that there is a prime between $n$ and $n^2$

Edit: The argument as presented before was invalid.

Misha correctly identified the error. In reviewing the details, I realized that the error was not fatal.

I have updated the question with the corrections. A big thank you to Misha for identifying the error.

Edit 2: I realized that I had not accurately defined $g_p$.

I have updated the definition of $g_p$. Without the corrected definition, it was not clear that $gcd(L,V)= \prod\limits_{p<n} p^{g_p(n^2,n)}$ when we assume that there are no primes found in $n^2$ and $n^2+n$.

Edit 3: The argument is invalid. I am not accounting for the the primes between $n$ and $n^2$.

• Can you elaborate on the definition of $g_p$ function? – didgogns Mar 27 '17 at 12:43
• @didgogns, thanks for your question! I have updated the question and added an explanation in edit 2 above. – Larry Freeman Mar 27 '17 at 13:57
• I am having difficulty in understanding (17) but the statement "all numbers $n^2<x≤(n^2+2⌊4n/15⌋+12)$ that do not divide $V$ divide $U$" is not true. There might be numbers in that range that is divisible by prime $q$ where $n<q<n^2$. – didgogns Mar 27 '17 at 14:07
• That was the mistake! Thanks, @didgogns. The argument is invalid. – Larry Freeman Mar 28 '17 at 3:41

Claim (3) is false: the expression $$\sqrt[2\left\lfloor\frac{4n}{15}\right\rfloor+12]{\left(\left\lfloor\frac{12n}{15}\right\rfloor+18\right)!}$$ grows like $O(n^{3/2})$, so it is not smaller than $n$ for all $n>41$.
• Thanks very much for your observation. My argument is based on the arithmetic mean always being greater than the geometric mean. Does your argument imply that at some point $n$ my argument will fail for the arithmetic mean being smaller than $n$? Could you help me to understand which step in my argument is wrong for claim (3)? I wrote a java program that found $n$ was greater up to all numbers that I tested for the arithmetic mean. – Larry Freeman Mar 27 '17 at 5:56
• The inequality $\frac{a_1 + a_2 + \dots + a_k}{n} \ge \sqrt[n]{a_1 a_2 \dotsb a_k}$ does not follow from AM-GM if $k \ne n$; you seem to be applying it where $k \approx \frac32 n$, where this inequality is not true. For example, $\frac{4 + 4 + 4}{2} < \sqrt[2]{4\cdot4\cdot4}$. – Misha Lavrov Mar 27 '17 at 5:58