I was recent reading through Paul Erdos's classic elementary proof of Sylvester-Schur. It occurred me that there is a simple argument that when $x$ is sufficiently large and if $p_i$ represents the $i$th prime such that $p_i \le n < p_{i+1}$, then there are least $n - i$ numbers in the sequence $x, x+1, \dots, x+n-1$ with prime divisors greater than $n$.

Have there been any well known result that goes beyond Sylvester-Schur in terms of the count of numbers with a prime divisor greater than $n$ in the integer sequence $x, x+1, \dots, x+n-1$? For example, trivially, $x > (n-1)!$ will have this property of at least $n - i$ numbers in the sequence $x,x+1,\dots,x+n-1$ with a prime divisor greater than $n$.


Edit: Here is the argument that I spoke of. Please let me know if anything is not clear.

  • Let $R(p,n)$ be the power of $p$ such that $p^{R(p,n)} \le n < p^{R(p,n)+1}$

  • Let $x > \prod\limits_{p < n}p^{R(p,n)}$ where $p$ is each prime less than $n$.

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

  • Let $t_k$ be any integer $x \le x+t_k < x+n$ and $gpf(x+t_k) \le p_i$ where gpf = greatest prime factor.

Claim 1: There exists a prime $q \le p_i$ such that $q^v \ge n$ and $q^v | x + t_k$

This follows directly from $x > \prod\limits_{p < n}p^{R(p,n)}$. If this were not true, then $x$ must necessarily be less than or equal to $\prod\limits_{p < n}p^{R(p,n)}$

Claim 2: There are at most $i$ such instances of $t_k$

Since there are only $i$ distinct primes less than or equal to $n$, it follows that if there are more than $i$ instances, then at least two must involve the same prime.

Assume that there exists $k_1 < k_2$ such that:

$0 < k_2 - k_1 < n$

$q^{v_1} | (x + k_1)$ and $q^{v_1} \ge n$ and $gpf(x+k_1) \le p_i$.

$q^{v_2} | (x + k_2)$ and $q^{v_2} \ge n$ and $gpf(x+k_2) \le p_i$

There exists integers $a_1 >0, a_2 > 0$ where:

$a_1(q^{v_1}) = x+k_1$ and $a_2(q^{v_2}) = x+k_2$

if $v_1 < v_2$, then:

$x+k_2 - x + k_1 = q^{v_1}[a_2(q^{v_2 - v_1}) - a_1]$

Now, $q^{v_1} \ge n$ and $[a_2(q^{v_2 - v_1}) - a 1] \ge 1$ which is impossible since $x + k_2 - x + k_1 < n$

if $v_1 > v_2$, then:

$x+k_2 - x + k_1 = q^{v_2}[a_2 - a_1(q^{v1-v2})]$ and the same argument applies.

  • I would be interested in seeing this argument. While I think it is true for most intervals of n integers there are p_i -i integers minimum with divisors larger than n, I think there is no simple argument. This is because we do not understand well enough how smooth numbers are distributed . For n=5, there is only one number in [8,12], not 2, with a prime divisor greater than 5. For related work check ArXiv for work of Najman e.g. arxiv.org/abs/1108.3710. Gerhard "Understanding Smoothness Can Be Rough" Paseman, 2017.02.16. – Gerhard Paseman Feb 16 '17 at 18:43
  • Sure. I will post it this evening. If this is not a common result, then I am sure that there is a flaw in my reasoning. – Larry Freeman Feb 16 '17 at 18:47
  • Even if it is flawed, I am still interested in the idea. I look forward to your posting it or putting it in a comment here. It may be possible to salvage it. Gerhard "Or Use It Somewhere Else" Paseman, 2017.02.16. – Gerhard Paseman Feb 16 '17 at 18:50
  • I'm glad to post it and learn my mistake. :-) – Larry Freeman Feb 16 '17 at 18:51
  • 1
    Claim 2 is more simply proved. If there are two integers less than n apart both divisible by a power of a prime q, their difference is divisible by a power of q less than n. This means one of them is divisible by a power less than n. While this puts a large lower bound on x, it is a nice proof. Well done! Gerhard "Now Searching For Smaller X" Paseman, 2017.02.16. – Gerhard Paseman Feb 16 '17 at 23:24
up vote 6 down vote accepted

I like Larry Freeman's proof so much, I am going to rephrase it, first by weakening it.

Claim (Freeman): Given integer $n$ greater than 1, and given $x$ greater than $n!$, there are at most $\pi(n)$ many $n$-smooth integers in the interval $[x+1,x+n]$.

Indeed, his proof is an injection from the subset of $[x+1,x+n]$ which have largest prime factor at most $n$ into the set of primes in $[1,n]$.

Proof sketch: for each smooth number, pick the largest prime power factor of that number, and map the number to that prime. If two numbers map to the same prime, their difference is divisible by a prime power less than $n$. But then (as Larry points out), one of these smooth numbers must be less than $n!$, as it is then a divisor of $n!$. End of proof sketch.

The sketch above also works with Larry's version where $x$ is allowed to be as small as the least common multiple of the first $n$ numbers. I imagine this is folklore, and appears somewhere in the literature on smooth numbers. I would like to see a reference to this result, as well as improvements.

Fixing $n$, the $n$-smooth numbers get increasingly sparse, and the expected count of these numbers in a small interval decays, probably exponentially. Besides a result of Stormer on consecutive smooth numbers, I am not aware of a result like Larry's that is phrased in a combinatorial fashion. I hope others can show us such references. Even data showing the decay for small values of n would be welcome.

Edit 2017.02.17 GRP

'Prime factors of arithmetic progressions and binomial coefficients' is the title of a paper by Shorey and Tijdeman which has an argument similar to the above. This paper has some answers to the question as well as an extensive bibliography.

End Edit 2017.02.17 GRP

EDIT 2018.01.27 GRP

Many thanks to Jose Brox who in helping with figuring out how primes jump found the following paper:

MICHEL LANGEVIN Plus grand facteur premier d’entiers en progression arithmétique

Séminaire Delange-Pisot-Poitou. Théorie des nombres, tome 18, no 1 (1976-1977), exp. no 3, p. 1-7

in which a nice extension is proved. The interval of n numbers can be an arithmetic progression of n terms with common difference coprime to all terms, with the restriction that all terms are positive and none divide lcm[1..n], and the same map will be injective. The proof is almost the same as above.

Being annoyed at having to leave out divisors of lcm[1..n], I found an argument which allows one to include one divisor, at the possible cost of altering the map at that divisor. It is a lot of work for small gain, but it uses a weak combinatorial estimate on the number of certain perfect powers in an interval, so I am pleased with it. I can for large n bring the forbidden divisors down by a factor of square root of n, and hope to improve this further, using just combinatorial arguments.

END EDIT 2018.02.27 GRP

Gerhard "Too Long For A Comment" Paseman, 2017.02.16.

  • This map might be a Grimm map. If so, I am willing to call it a Grimm-Freeman-Paseman map. Gerhard "Is That Too Many M's?" Paseman, 2017.02.16. – Gerhard Paseman Feb 17 '17 at 1:34

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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