3
$\begingroup$

This is my second question on this topic. In my first question, mathlove quickly found the mistake.

Correcting for the previous mistake, there is still a mistake in my analysis but I can't find it. It will probably be obvious to everyone else.

I would greatly appreciate it if someone could help me find the mistake. Thanks.

Here is the reasoning:

(1) Let $x \ge 37$ be an integer so that $\pi(x) < \frac{x}{3}$ where $\pi(x)$ is the prime counting function.

Argument for this if needed can be found in Lemma 2 here.

(2) Let $P = \dfrac{(x^2+x)!}{\left(\frac{x^2+x}{2}\right)!}$

(3) Assume no prime $x^2 < p < (x^2+x)$ exists.

(4) $P = \left(\frac{x^2+x}{2}\right)!{{x^2+x}\choose{\frac{x^2+x}{2}}} > \left(\frac{x^2+x}{2}\right)!\left(\dfrac{4^{(x^2+x)/2}}{\frac{x^2+2}{2}}\right)$

  • $\dfrac{4^4}{4} = 64 <  {8 \choose 4} = \dfrac{8!}{(4!)(8-4)!} = 70$

  • Assume that it is true up to $n-1 \ge 4$

  • ${2n \choose n} = 2\left(\dfrac{2n-1}{n}\right){{2(n-1)} \choose {n-1}} >2\left(\dfrac{2n-1}{n}\right)\left(\dfrac{4^{n-1}}{n-1}\right)  > \dfrac{4^n}{n}$

(5) For $x \ge 8, \left(\frac{x^2+x}{2}\right)! > 4^{x^2}$

  • $\dfrac{8^2+8}{2}! = 36! > 3.71 \times 10^{41} > 3.41 \times 10^{38} > 4^{64}$

  • Assume it is true up to some $x \ge 8$ where $\left(\frac{x^2+x}{2}\right)! > 4^{x^2}$

  • $\left(\frac{(x+1)^2+(x+1)}{2}\right)! = \left(\frac{x^2+3x+2}{2}\right)\dots\left(\frac{x^2+x+2}{2}\right){{x^2+x}\choose{2}} > 16^{\frac{2x+2}{2}}4^{x^2} = 4^{2x+2}4^{x^2} > 4^{x^2 + 2x + 1} = 4^{(x+1)^2}$

(6) Let $v_p(n)$ be the highest power of $p$ that divides $n$.

(7) If $p > x$, then $v_p(P) = 1$ since using Legendre's Formula:

$$v_p(P) = \sum\limits_{i \ge 1}\left\lfloor\dfrac{x^2+x}{p^i}\right\rfloor - \left\lfloor\dfrac{\frac{x^2+x}{2}}{p^i}\right\rfloor$$

Clearly, if $p > x$, then $p^2 > (x+1)^2 > (x+1)x = x^2+x$

(8) For the upper bound, consider where $a>0$ is an integer and $p$ is a prime:

$$P = \left(\prod\limits_{p^a \le \frac{x^2+x}{2}\text{ and }p^a|P} p\right)\left(\prod\limits_{p \le x\text{ and } \frac{x^2+x}{2} < p^a \le (x^2+x)\text{ and } p^a|P}p\right)\left(\prod\limits_{x < p < x^2\text{ and } p | P} p\right)$$

(9) Using Hanson's proof about the least common multiple of $(1,2,3,\dots,n) < 3^n$, it follows:

$$\left(\prod\limits_{p^a \le \frac{x^2+x}{2}\text{ and }p^a|P} p\right) < 3^{\frac{x^2+x}{2}}$$

(10) It is well known that $n\# < 4^n$ where:

  • $n\#$ is the primorial, that is, $n = \prod\limits_{p \le n} p$ where $p$ is prime.

since:

  • For $n=3$ and $n=4$, this is true since $4\# = 3\# = 6 < 4^3 = 64$

  • Assume it is true for some $n-1 \ge 4$

  • We can assume that $n$ is odd since if $n$ is even $n\# = (n-1)\# < 4^{n-1}$ by assumption.

  • There exists $m$ such that $n = 2m-1$ and we note that:

  • $\dfrac{(2m-1)\#}{m\#} \le {{2m-1} \choose {m}} < \dfrac{1}{2}\left({{2m-1}\choose {m-1}}+{{2m-1}\choose{m}}\right) < \dfrac{1}{2}(1+1)^{2m-1} = 2^{2m-2}$

  • $n\# = (2m-1)\# = (m\#)\left(\dfrac{(2m-1)\#}{m\#}\right) < \left(2^{2m}\right)\left(2^{2m-2}\right) = 2^{4m-2} < 4^{2m-1} = 4^n$

(11) From step(10) and step(7), it follows:

$$\left(\prod\limits_{x < p < x^2\text{ and } p | P} p\right) < 4^{x^2}$$

(12) $\left(\prod\limits_{p \le x\text{ and } \frac{x^2+x}{2} < p^a \le (x^2+x)\text{ and } p^a|P}p\right) < 4^{x/3}$ since:

  • If $\frac{x^2+x}{2} < p^a \le (x^2+x)$, then $(x^2+x) < 2p^a \le p^{a+1}$

  • So, $\left(\prod\limits_{p \le x\text{ and } \frac{x^2+x}{2} < p^a \le (x^2+x)\text{ and } p^a|P}p\right) < 4^{\pi(x)} < 4^{x/3}$

(13) Combining steps (4),(5),(8) to (12), leads to the following inequality:

$$\left(3^{\frac{x^2+x}{2}}\right)\left(4^{x/3}\right)\left(4^{x^2}\right) > \left(\frac{4^{(x^2+x)/2}}{\frac{x^2+x}{2}}\right)\left(\frac{x^2+x}{2}\right)!$$

which factors to:

$$\left(\dfrac{x^2+x}{2}\right)\left(\left(\sqrt{3}\right)^{x+1}\right)^x\left(\sqrt[3]{4}\right)^x > \left(2^{x+1}\right)^x$$

refactoring a bit more:

$$\left(\dfrac{x^2+x}{2}\right)^{1/(x^2+x)}\left(4\right)^{1/(3x+3)} > \frac{2}{\sqrt{3}}$$

which is clearly not true for $x≥6$.

The argument is clearly too simple for such a tough problem. I look forward to finding out which assumption is wrong.

Here is the Wikipedia article on Legendre's Conjecture.


Edit: I figured out the mistake.

Step(9) is wrong. Because this is no longer a binomial coefficient, the power of a prime can exceed $\log_p(x^2+x)$ and so the product can exceed $\text{lcm}(1,2,\dots,\frac{x^2+x}{2})$.

I feel a lot better.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.