2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Can you elaborate on the definition of $g_p$ function? $\endgroup$ – didgogns Mar 27 '17 at 12:43
  • $\begingroup$ @didgogns, thanks for your question! I have updated the question and added an explanation in edit 2 above. $\endgroup$ – Larry Freeman Mar 27 '17 at 13:57
  • $\begingroup$ 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$. $\endgroup$ – didgogns Mar 27 '17 at 14:07
  • 1
    $\begingroup$ That was the mistake! Thanks, @didgogns. The argument is invalid. $\endgroup$ – Larry Freeman Mar 28 '17 at 3:41
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Larry Freeman Mar 27 '17 at 5:56
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Misha Lavrov Mar 27 '17 at 5:58
  • $\begingroup$ I have fixed claim (3). I believe that claim 3 is now valid. If you still see a mistake, please let me know. :-) $\endgroup$ – Larry Freeman Mar 27 '17 at 7:20

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.