Strengthening Sylvester's theorem

Question

I am working on a problem in commutative ring theory, that deals with $p$-adic valuations. This leads to a number theoretical question that I want to explain in the following.

Let $n \in \mathbb{N}$ and $k$ an integer $\leq n/2$. Then, by the well-known result of Sylvester, there is an integer in $\{n, n-1,..., n-k+1\}$ that has a prime factor $>k$.

There is a very practical survey by Shorey and Tijdeman on generalizations of this theorem. For instance, it is known that the maximal distance of two positive integers having a prime factor $>k$ is $\leq \Big(\frac{1}{2} + o(1)\Big)\frac{k}{\log(k)}$. In particular, for large enough $k$ this difference is less than $\pi(k) < k$.

There are some similar results, but none of them helped me with my actual question, although they point in the direction of a positive answer to it:

Question: Can one explicitely give a constant $C$ with the following property?: For each positive integer $n \geq C$ that is not a prime power and for each integer $k$ with $1<k\leq n/2$, there are two different $a,b \in \{n,n-1,...,n-k+1\}$ having a prime factor $>k$.

Thank you in advance for any help!

Answer 1

With motivation from the original poster, a key idea from Sylvester, and technical inspiration from Iosif Pinelis, I contribute an observation that helps toward an answer.

I use m instead of n and n instead of k. I start with the inequality that p! is strictly less than 3^p for p less than 7, and less than (p/2)^p for all larger integers p. We will set p =$\pi$(n).

Consider the product of integers in (m,m+n], and write it as W(n!)B, where W are all the prime factors (with multiplicity) at most n dividing (m+n)!/(m!n!), leaving B as the product of the remaining prime factors which are all larger than n, and B=1 if there are no such large prime factors.

Sylvester's observation is that W is at most (m+n-p+1)...(m+n). If B=1 the interval (m,m+n] has all numbers being n-smooth. The extended observation (which I think is new and hopefully orignal) is that WB is at most (m+n-p-d+1)...(m+n) if there are at most d many numbers in (m,m+n] which are not n-smooth. We fix d and observe that the original problem relates to d=1 in what follows.

Under supposition that there are not d+1 many non smooth numbers in (m,m+n], we now have (n!) Is at least (m+1)...(m+n-p-d). Write m as kn + i for positive integer k and non negative integer i (choose i less than n for less confusion). We now have (p+d)! Is at least (and for large enough n strictly greater than) k^(n-p-d).

So if (m,m+n] has at most d numbers which are not n-smooth, then we use the inequality above to note that when p+d is greater than 6, k is strictly less than ((p+d)/2)^((p+d)/(n-(p+d))). To save on plus signs, write q=p+d.

By the above, when q is at most 6 and n is at least 2q, then k is at most 2. (I leave the case n smaller than 12 and arbitrary d to the reader.) As n grows, q(1+ log (q/2)) will be less than n (because d is fixed), and one can use current literature or supercomputers to compute for which n this holds, in which case k is strictly less than e.

So given d, one can compute n0 without much challenge to find that (m,m+n] has d+1 non smooth numbers for n greater than n0 and for m at least as large as 3n.

To handle the remaining case for small d (d less than 6), use Nagura or similar as outlined in the other answer of mine to find d+1 non smooth integers in the interval for when m is in [n,3n). This should hold for m at least 150, giving C is less than 150.

Gerhard "Would James Joseph Be Approving?" Paseman, 2020.06.01.

Answer 2

At Who first proved the generalization of Bertrand's postulate to (2n,3n) and (3n,4n)? are references to work establishing the existence of more than one prime in intervals that aren't too short, including work of Nagura. You can use many of these in a way similar to how I am about to show, which reveals that the main problem is for k small (but not too small).

We will pick n sufficiently large, and try to find a C using this. Pick a real x, say x is between n and n+1, and use Nagura's result to find a prime in (5x/6, x) whenever x is bigger than 30. So when k is bigger than n/6, we are already half way to our goal.

Now scale down by a factor of 2. When x is bigger than 60, there is a different prime in (5x/12, x/2), giving a number 2p which is less than n/6 below n, and has a factor larger than n/3. So for k bigger than n/6 and n at least 60, we have achieved our goal of finding two distinct numbers with prime factors bigger than k. For numbers n less than 60, one finds that primes and twice primes are close together so that this holds for k at least n/6 and n smaller than 60 and bigger than 36.

However, we need not stop there. We can scale down by 3,4,5 and larger to find numbers in (5x/6,x) which are three times a prime (or four times, or five or larger), getting at least five distinct numbers close to n .

In general, if you have a parameter $C_k$ so that for every $x \gt C_k$ there is a prime in $(x - x/k, x)$, you can then exhibit $k$ many distinct numbers below $n$ and greater than $n - n/k$ for $n \gt kC_k$ with prime factors greater than $n/k$. This gives more than you need for large values of your $k$ (different from the $k$ in $C_k$).

There is an argument from Langevin that goes like this: pick an arithmetic progression of $k$ terms, each term coprime to the common difference $d$. Define a map from each term to that prime $p$ such that the largest prime power which is a factor of that term is a power of $p$. Much of the time, this map is injective, so each term gets a different prime divisor. When it is not, then two terms are both divisible by a power of the same prime, say $p^e$. Since the terms are coprime to the difference, $p^e$ is less than $k$. Since $p^e$ is the largest prime power of one of the terms, that term must be no larger than lcm(1...p^e), so the term is less than lcm(1..k). So if n is large enough, k terms around n have large enough prime divisors, especially when $k \gt 4$. Unfortunately the lower bound grows with $k$.

It may be possible to push the lower bound (indeed, I have unpublished work which takes it down to about sqrt(lcm...)), but your condition is weaker. It may be possible to modify the term to largest prime power map to exhibit a logarithmic if not constant lower bound.

Gerhard "And Then There's Jumping Primes" Paseman, 2020.05.14.