# Still unclear why Hanson's proof that $\text{lcm}(1,…,n)<3^n$ is not sufficient to resolve Legendre's Conjecture.

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.