3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ What a great result ! Is it a consequence from Chebychev ? $\endgroup$ – Maman Feb 4 '17 at 16:52
  • $\begingroup$ I believe it is independent of Chebychev. I was attempting to improve on the proof by Paul Erdos which I referenced above. $\endgroup$ – Larry Freeman Feb 5 '17 at 4:12
  • $\begingroup$ Can you clarify what do you mean exactly by $R(p,w)$ and why $x+i\leq\prod_{p<w} R(p,w)$ in your proof? As it is right now, $R(p,w)$ is an exponent, and the product is a product of exponents... $\endgroup$ – Jose Brox Dec 28 '17 at 20:19
  • $\begingroup$ @Jose Brox, I read through my argument and you have identified a typo. It should read: Let $x > \prod\limits_{p<w}p^{R(p,w)}$ be an integer. I will update the argument (with a note). Thanks very much for noticing this! $\endgroup$ – Larry Freeman Dec 29 '17 at 6:38
  • 1
    $\begingroup$ I found another mistake in my definition for $R(p,w)$ so with the update, $\prod\limits_{p<w}p^{R(p,w)}$ is greater than $w$. $\endgroup$ – Larry Freeman Dec 29 '17 at 6:57
2
$\begingroup$

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)<n,$$ 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-j<k$, a contradiction with $p_i^{v_i},p_i^{v_j}>k$. 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.

$\endgroup$
  • 1
    $\begingroup$ @LarryFreeman Please, see the addendum at the end of my answer. $\endgroup$ – Jose Brox Dec 29 '17 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.