Is this a valid proof for Sylvester-Schur Theorem for the case $n \ge 8$ and $x \ge 2n$

92 Views Asked by At

Below is my effort to provide an alternative argument for the Sylvester-Schur Theorem that is simpler than this one by Paul Erdős.

Please let me know if I made any mistakes or if any point is unclear.

The argument uses the following lemma:

Lemma: For integers $n \ge 13$ and $x \ge 2n$:

$${x \choose n} > \dfrac{x!}{[x - \pi(n)]!}$$

(1) For $n \ge 8$, it is straight forward to show that:

$$n > (\ln n)^2$$

Note: See here for details on $n > (\ln n)^2$

(2) For $n \ge 5$, it follows that $(2n-2)\ln n > 2.25506n$ so that:

$$2n\ln n - \left(\dfrac{n+2}{n+1}\right)\ln n - 1.25506n > (2n-2)\ln(n) - 1.25506n> 2.25506n - 1.25506n= n$$

(3) $2n\ln n - \left(\dfrac{n+2}{n+1}\right)\ln n - 1.25506n > (\ln n)^2$

(4) $(2n-1) - \dfrac{1.25506n}{\ln n} > \ln n + \dfrac{1}{n+1}$

(5) Multiplying $n+1$ to both sides $$(n+1)\left[(2n-1) - \dfrac{1.25506n}{\ln n}\right] > (n+1)\ln n + 1$$

(6) Multiplying $\ln n$ to both sides:

$$(n+1)[(n-1)\ln n - 1.25506n] > (\ln n)[(n+1)\ln n -n + 1]$$

(7) $n+1 > \left(\dfrac{\ln n}{(n-1)\ln n - 1.25506n}\right)\left[(n+1)\ln n - (n-1)\ln e \right]$

(8) $\sqrt[n - 1 - \frac{1.25506n}{\ln n}]{\left(2n - \dfrac{1.25506n}{\ln n}\right)\left(2n-1 - \dfrac{1.25506n}{\ln n}\right)\dots(n+1)} > (n+1) > \sqrt[n - 1 - \frac{1.25506n}{\ln n}]{\dfrac{n^{n+1}}{e^{n-1}}}$

(9) Since $n! \le \dfrac{n^{n+1}}{e^{n-1}}$, it follows that:

$$\sqrt[n - 1 - \frac{1.25506n}{\ln n}]{\left(2n - \dfrac{1.25506n}{\ln n}\right)\left(2n-1 - \dfrac{1.25506n}{\ln n}\right)\dots(n+1)} > (n+1) > \sqrt[n - 1 - \frac{1.25506n}{\ln n}]{n!}$$

Note: See Theorem here for the argument that $n! \le \dfrac{n^{n+1}}{e^{n-1}}$.

(10) Since $x \ge 2n$:

$$\left(x - \dfrac{1.25506n}{\ln n}\right)\left(x-1 - \dfrac{1.25506n}{\ln n}\right)\dots(x-n+1) \ge \left(2n - \dfrac{1.25506n}{\ln n}\right)\left(2n-1 - \dfrac{1.25506n}{\ln n}\right)\dots(n+1) > n!$$

(11) Since for $n > 1$, $\pi(n) < \dfrac{1.25506n}{\ln n}:$

$$(x-\pi(n))(x-1-\pi(n))\dots(n+1) > n!$$

Note: See 3.6, Theorem 2, Corollary 1,from Rosser & Schoenfeld, 1962

(12) $\dfrac{(x)(x-1)\dots(x-n+1)}{n!} > (x)(x-1)\dots(x-\pi(n)+1)$

(13) It follows that:

$${x \choose n} > \frac{x!}{[x - \pi(n)]!}$$

Theorem: For integers $n \ge 9, x \ge 2n$, there exists a prime $p > n$ such that $p | \dfrac{x!}{(x-n)!}$

(1) Let $x,n$ be integers such that $n \ge 9$ and $x \ge 2n$.

(2) Assume that there is no prime greater than $n$ that divides $\dfrac{x!}{(x-n)!}$

(3) Let $\text{lcm}(x-n+1, x-n+2, \dots, x)$ be their least common multiple.

(4) It can be shown that:

$$\text{lcm}(x-n+1, x-n+2, \dots, x) \ge {x \choose n}$$

Note: The argument for this can be found here

(5) From the assumption in (2), it follows that: $$\text{lcm}(x-n+1, x-n+2, \dots, x) < \dfrac{x!}{[x - \pi(n)]!}$$

Note: Where $\pi(n)$ is the prime counting function.

(6) But then, we have a contradiction since for $n \ge 13, x \ge 2n$, it follows from the lemma:

$${x \choose n} > \dfrac{x!}{[x - \pi(n)]!}$$

Feel free to let me know if any point is unclear or if there is a better way to make the same argument.


Edit: found 1 mistake in step(2).

This allows me to change the lower bound from $n\ge 9$ to $n \ge 8$, I believe that it has now been fixed.

Edit 2:

Step(8) does not follow from step(7). I will update the argument if I can. At this point, it is invalid.