elementary number theory - Strengthening the Sylvester-Schur Theorem

The Sylvester-Schur Theorem states that if $x > k$, then in the set of integers: $x, x+1, x+2, \dots, x+k-1$, there is at least $1$ number containing a prime divisor greater than $k$.

It has always struck me that this theorem is significantly weaker than the actual reality, especially as $n$ gets larger.

As I was trying to check my intuition, I had the following thought:

• Let $k$ be any integer greater than $1$



• Let $p_n$ be the $n$th prime such that $p_n \le k < p_{n+1}$.


• If an integer $x$ is sufficiently large, then it follows that in the set of integers: $x, x+1, x+2, \dots, x+k-1$, there are at least $k-n$ numbers containing a prime divisor greater than $k$.

Here's my argument:

(1) Let $k > 1$ be an integer with $p_n \le k < p_{n+1}$ where $p_n$ is the $n$th prime.

(2) Let $x > 2p_n$ be an integer

(3) Let $0 \le t_1 < p_n$ be the smallest integer greater than $x$ such that $gpf(x+t_1) \le p_n$ where gpf() = greatest prime factor.

(4) It is clear that $x+t_1$ consists of at least one prime divisor $q$ where $q \le p_n$

(5) Let $t_1 < t_2 < p_n$ be the second smallest integer greater than $x$ such that $gpf(x+t_2) \le p_n$.

(6) Let $f = gcd(x + t_1,t_2 - t_1)$ where gcd() = greatest common divisor.

(7) Let $u = \frac{x+t_1}{f}, v = \frac{t_2-t_1}{f}$ so that $u > 2$ and $1 \le v < p_n$ and $gcd(u+v,x+t_1)=1$

(8) $x+t_2 = uf + vf = f(u+v)$ and since $u+v > 3$, there exists a prime $q$ that divides $u+v$ but does not divide $w+t_1$.

(9) Let $t_2 \le t_3 < p_n$ be the third smallest integer greater than $x$ such that $gpf(x+t_3) \le p_n$

(10) We can use the same arguments as steps (5) thru steps (8) to show that $x+t_3$ contains a prime divisor relatively prime to $x+t_1$ and relatively prime to $x+t_2$

• Let $f_1 = gcd(x+t_1,t_3-t_1), u_1 = \frac{x+t_1}{f_1}, v_1 = \frac{t_3-t_1}{f1}$


• Let $f_2 = gcd(x+t_2,t_3-t_2), u_2 = \frac{x+t_2}{f_2}, v_2 = \frac{t_3-t_2}{f_2}$


• $x+t_3 = f_1(u_1 + v_1) = f_2(u_2 + v_2)$ and $gcd(u_1 + v_1,x+t_1)=1, gcd(u_2 + v_2,x+t_2)=1$



• Let $h = gcd(f_1,f_2)$ so that $gcd(\frac{f_1}{h},\frac{f_2}{h})=1$


• Then, $\frac{f_1}{h}(u_1 + v_1) = \frac{f_2}{h}(u_2+v_2)$


• And: $\frac{u_1+v_1}{\frac{f_2}{h}} = \frac{u_2+v_2}{\frac{f_1}{h}}$

(11) We can repeat this argument until $x+t_n$ at which point there are no more primes less than or equal to $p_n$.

(12) We can thus use this same argument to show that all remaining integers in the sequence $x,x+1, x+2, \dots x+k-1$ have at least one prime divisor greater than $p_n$.

Of course, in order to make this argument, $x$ may well need to be greater than $(p_n) ^ n$ since I am assuming that at each point $\frac{u_i + v_i}{\frac{f_i}{h}} > p_n$.

• Is my reasoning sound?




• Is this a known property of large numbers?




• Is there a more precise formulation for smaller numbers? For example, my argument seems like it could be improved to argue that for $x > 2p_n$, there are at least $2$ numbers with a prime divisor greater than $p_n$.

---

Edit: I found a simpler argument (modified on 12/28/2017)

• Let $w > 1$ be an integer


• Let $p_n$ be the $n$th prime such that $p_n \le w < p_{n+1}$


• Let $R(p,w)$ be the largest integer $r$ such that $p$ is a prime and $p^r \le w$ but $p^{r+1} > w$


• Let $x > \prod\limits_{p < w} p^{R(p,w)}$ be an integer


• Let $i$ be an integer such that $0 \le i < w$

I claim that if $gpf(x+i) \le p_n$, then there exists $k,v$ such that $1 \le k \le n$ and $(p_k)^v \ge w$ and $(p_k)^v | x+i$

Assume no such $k,v$ exists. It follows that each $x+i \le \prod\limits_{p < w} R(p,w)$ which goes against assumption.

I also claim that there are at most $n$ instances where $gpf(x+1) \le p_n$.

Assume that there exists integers $v_2 > v_1$ and $i \ne j$ where $(p_k)^{v_1} | x+i$ and $(p_k)^{v_2} | x+j$.

Then there exists positive integers $a,b$ such that $a(p_k)^{v_1} = x+i$ and $b(p_k)^{v_2} = x+j$

Let $u = x+j - x - i = j - i = (p_k)^{v_1}(a - b(p_k)^{v_2 - v_1})$

We can assume $u$ is positive since if it were negative, we could set $u = x+i - x - j$ instead.

We can assume therefore that $a - b(p_k)^{v_2 - v_1} \ge 1$.

But now we have a contradiction since $w > j - i$ but $(p_k)^{v_1} \ge w$.

Answer

I think your second proof is correct. I'm going to rewrite it:

Theorem (Sylvester's theorem generalization):

Let $n,k\in\mathbb{N}$ with $n\geq$ lcm$(1,\ldots,k)$, and let $\pi(x):=\sum_{p\leq x} 1$ be the number of primes not greater than $x$. Then in the interval $[n,n+k]$ there are at least $k+1-\pi(k)$ integers $n_i$ with a prime factor $p_i>k$.

Proof: For $p$ prime let $\nu_p(k)$ be the $p$-adic valuation of $k$. Let gpf$(x)$ be the greatest prime factor of $x$ and $p_j$ be the $j$-th prime. Consider $0\leq i\leq k$.

Suppose that $i$ is such that gpf$(n+i)\leq p_{\pi(k)}$ ($p_{\pi(k)}$ is the greatest prime not greater than $k$). Then there exist a prime $p_i\leq p_{\pi(k)}$ and an exponent $v_i\in\mathbb{N}$ such that $p_i^{v_i}|n+i$ and $p_i^{v_i}>k$, as otherwise
$$n+i\leq\displaystyle\prod_{p\leq k}p^{v_p(k)}=\text{lcm}(1,\ldots,k)a contradiction.

Now pick $i\neq j\in\{0,\ldots,k\}$ such that gpf$(n+i)$, gpf$(n+j)\leq p_{\pi(k)}$ with $p_i=p_j$. Then $p_i^{v_i}|n+i$ and $p_i^{v_j}|n+j$, so $p_i^{\min\{v_i,v_j\}}|i-jk$. Therefore $p_i\neq p_j$.

Thus, to every integer $i$ such that gpf$(n+i)\leq p_{\pi(k)}$ there corresponds a different prime $p_i\leq p_{\pi(k)}$, so that there can be at most $\pi(k)$ integers of this form. Hence there are at least $k+1-\pi(k)$ numbers $n+i\in [n,n+k]$ such that gpf$(n+i)\geq p_{\pi(k)+1}>k$.

Corollary (Grimm's conjecture): If $n\geq$lcm$(1,\ldots,k)$, then for every integer $n_i\in[n,n+k]$ there is a different prime $p_i$ such that $p_i|n_i$ (i.e., Grimm's conjecture is true for this choice of $n$ and $k$).

Proof: If gpf$(n+i)\leq p_{\pi(k)}$, pick $p_i$ (we already know $p_i\neq p_j$ if $i\neq j$). Otherwise gpf$(n+i)>k$ and this factor cannot divide any other $n+j$ with $i\neq j\leq k$.

In fact, the two results are equivalent:

Lemma: Grimm's implies Sylvester's.

Proof: If there is a different prime $p_i|n_i$ for every $n_i\in[n,n+k]$, then as there are $\pi(k)$ primes below $k$, there must be at least $k+1-\pi(k)$ numbers $n_i$ such that $p_i>k$.

---

Now that I have put it like this, I realize that this theorem (and its proof!) are a particular case of Theorem 1 of M. Langevin, Plus grand facteur premier d'entiers en progression arithmétique, Séminaire Delange-Pisot-Poitou. Théorie des nombres (1976-1977), 18(1), 1-7. So this was known (although perhaps not very well known!).

Observe that Langevin manages to prove the result with the less restrictive condition that $n+i$ does not divide lcm$(1,\ldots,k)$ for any $i\in\{0,\ldots,k\}$. We can adapt your proof to get this condition: if gpf$(n+i)\leq p_{\pi(k)}$ and $n+i\not|$lcm$(1,\ldots,k)$ then there must be a prime $p_i\leq p_{\pi(k)}$ and an exponent $v_i\in\mathbb{N}$ such that $p_i^{v_i}|n+i$ and $p_i^{v_i}>k$. The proof then follows as before.