# 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 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