I have recently been asking a lot of questions regarding the Gamma Function and a well-known upper bound of the prime counting function. I really appreciate everyone's assistance in helping me to better reason with the Gamma Function.
I wanted to also check if my approach to proving the Sylvester-Schur Theorem makes sense. I have long found Paul Erdős's classic paper on the theorem especially difficult to follow and wondered if an approach based on the properties of the Gamma Function and the inequality from Rosser and Schoenfeld would also work.
Is the following a valid approach to proving the Sylvester-Schur Theorem?
Sylvester-Schur Theorem: For integers: $x > 1, k \ge 2x$, there exists a prime $p > x$ that divides ${{k}\choose{x}}$.
Here is the argument:
(1) For $x \ge 631$, the following inequality holds:
$$\frac{\Gamma\left(2x+1-\frac{1.255506x}{\ln x}\right)}{\Gamma(x+1)\Gamma(x+1)} > 1$$
- The value at $631$ can be checked $\approx 1.0018$
- This function is increasing at $x \ge 631$ [See here, or graph]
Note: I am still not 100% clear on the analysis that it is increasing. Integrand gave an answer which was very helpful (see above).
(2) Assume that Sylvester-Schur is false. That there exists an integer $k$ such that no prime $p > x$ divides ${{k} \choose {x}}$
(3) Then, the following is true where lcm$(a,b,c,\dots)$ is the least common multiple of $a, b, c, \dots$:
$$\text{lcm}(k-x+1, k-x+2, \dots, k) < \frac{k!}{[k-\pi(x)]!}$$
Note: This analysis stems from 2 observations
- If $t$ is the maximum power of a prime $p$ that divides $k-x+c$, then $p^t \le k-x+c$
- If $p^t > x$, then $p^t$ can only divide one element in $k-x+1, k-x+2, \dots, k$ (otherwise, $p^t | (k-x+a) - (k-x+b) = a - b < x$)
(4) From properties of Least Common Multiples and Binomial Coefficients (see here), it can be shown that:
$$\text{lcm}(k-x+1, k-x+2, \dots, k) \ge {k \choose x}$$
(5) But then:
$$\frac{k!}{[k-\pi(x)]!} \ge {k \choose x}$$
Which, when using the Rosser and Schoenfeld upper bound for $\pi(x)$, leads to:
$${k \choose x}<\frac{k!}{[k-\pi(x)]!} < \frac{\Gamma(k+1)}{\Gamma\left(k + 1 - \frac{1.25506x}{\ln x}\right)} <\frac{k!}{[k - \left\lfloor\frac{1.25506x}{\ln x}\right\rfloor]!}$$
(6) But this contradicts step(1) since:
$$\frac{\Gamma\left(k+1-\frac{1.255506x}{\ln x}\right)}{\Gamma(x+1)\Gamma(x+1)} \ge \frac{\Gamma\left(2x+1-\frac{1.255506x}{\ln x}\right)}{\Gamma(x+1)\Gamma(x+1)} > 1$$
- After multiplying $\dfrac{\Gamma(k+1)}{\Gamma\left(k + 1 - \frac{1.25506x}{\ln x}\right)} $ to both sides:
$$\frac{\Gamma(k+1)}{\Gamma\left(k + 1 - \frac{1.25506x}{\ln x}\right)} < \frac{\Gamma(k+1)}{\Gamma(x+1)\Gamma(x+1)} = {k \choose x}$$
Please let me know if there is any problem with any step in this argument or whether there is a simpler way to make the same argument.
Yes I now that I understand step 3 I'd say its a valid proof.
EDITED IN LATER:
If you don't mind I write down here an alternative proof of the inequality in step 3 to help myself understand how it uses the assumption of step 2.
Let $A$ be the set of $x$ numbers $\{k - x + 1, k - x + 2, \ldots, k\}$ and let $P = \{p_1, \ldots, p_n\}$ be the set of distinct primes dividing at least one element of $A$. Finally let numbers $t_1, \ldots, t_n$ defined by the requirement that $p_i^{t_i}$ is the highest power of $p_i$ dividing an element of $A$.
By the fundamental theorem of arithmetic we have that $\gcd(A) = \prod_{i=1}^n p_i^{t_i}$. Moreover for every $p_i \in P$ there is at least one $a \in A$ such that $p_i^{t_i} | a$. Now you state that in the special case that $p_i^{t_i} > x$ this $a$ is unique, but I don't see how that is helpful since we don't have much control over the size of the $p_i^{t_i}$. However that is no problem.
For every $p_i \in P$ I just pick (by some arbitrary process) an element $\phi(p_i) \in A$ such that $p_i^{t_i}|\phi(p_i)$.
Now we have this map $\phi$ from the $n$-element set $P$ to the $x$-element set $A$ that is well defined (though not necessarily injective) and we denote by $B \subset A$ its image: $B = \phi(P)$. We write $m$ for the number of elements in $B$, so $m \leq \min(n, x)$.
Now since the elements of $P$ are distinct, the fundamental theorem of arithmetic tells us that whenever we have that $\phi(p_i) = \phi(p_j)$ we have that $(p_i^{t_i}p_j^{t_j})|\phi(p_i)$.
It follows that:
$$\left(\prod_{i=1}^n p_i^{t_i} \right) | \left( \prod_{b \in B} b \right)$$
On the left hand side we have $\gcd(A)$. On the right hand side we have a product of $m$ distinct elements of $A$ (namely: the $m$ distinct elements of $B$). It follows that the right hand side, and hence the left hand side as well, are smaller than or equal to the largest product of $m$ distinct elements from $A$, which are of course the elements $k - m + 1, \ldots, k$. In other words we find:
$$\gcd(A) \leq k!/(k - m)!$$
This is very close to the inequality in step (3), all we need to show in order to find that that inequality holds as well, is $m \leq \pi(x)$. And since $m \leq n$ for that it suffices to show that $n \leq \pi(x)$ and for that of course it suffices to show that each $p_i \leq x$, so that's what we are going to do.
CLAIM: Under assumption of step 2, every prime $p$ dividing an element of $A$ satisfies $p \leq x$.
Proof by contradiction: assume that $p > x$ and $p|a$ for some $a \in A$. It follows trivially that $p|\prod A$. Moreover since $p$ is prime and $p > x$ we have by Euclid's lemma that $p$ does not divide $x!$. It follows (again by the fundamental theorem of arithmetic) that $p$ divides $(\prod A) / x!$ $=$ $\binom{k}{x}$.
We already used the assumption $p > x$ once in the proof but now we'll use it again: $p > x$ and $p|\binom{k}{x}$ together contradict step (2). The claim in bold (and hence inequality of step 3) follow.