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.