1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ I suspect the answer is C=13. (Still checking small cases.) For large k, you can use results like those of Nagura and extensions (there is a prime in (n, 6n/5) for n bigger than 24), and combinatorics for very small k. There is a region of k which aren't small but less than n/log n which makes this a challenge, if not an open problem. Gerhard "Will Try Jumping On It" Paseman, 2020.05.14. $\endgroup$ – Gerhard Paseman May 14 at 14:53
  • 1
    $\begingroup$ By hand, I get n=18 as an exception. I suspect there are for each k greater than 2 only finitely many exceptional n, and for k=2 the only exceptions involve n or n-1 being a power of two. What computations have you done regarding this? Gerhard "Wants To See More Motivation" Paseman, 2020.05.14. $\endgroup$ – Gerhard Paseman May 14 at 15:09
  • $\begingroup$ Actually, regarding my loss of knowledge concerning number theory, I hoped the result is a simple corollary of existing theory and therefore just asked. Thank you for your time and comments! $\endgroup$ – Daniel W. May 14 at 20:05
  • 1
    $\begingroup$ It turns out there are some simple arguments (Langevin especially) around Grimm's conjecture which don't give your result but bring you closer to it. I'm preparing an answer to make these more known. I'm also seeing if my recent work can apply to this question. Gerhard "Check Out 243490 And Sequel" Paseman, 2020.05.14. $\endgroup$ – Gerhard Paseman May 14 at 20:48
  • 1
    $\begingroup$ I think we can prove it by understanding, refining, and reworking Sylvester's original proof. If you are willing to give it a go, I can provide a strategy and we can try it out, if you are willing to do a lot of the work of checking. I invite you to email me using the address hiding on one of my user pages. Gerhard "Up For Combinatorial Number Theory" Paseman, 2020.05.25. $\endgroup$ – Gerhard Paseman May 25 at 23:32
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ For n less than 2q, we can still find a small bound on k. For the Nagura argument, it helps if k is less than 5; this should hold already for most practical applications of d and n. Gerhard "Leaving Small Computations To Reader" Paseman, 2020.06.01. $\endgroup$ – Gerhard Paseman Jun 1 at 18:24
  • 1
    $\begingroup$ Also, the observation is new to me because I have not scoured the literature. I (and Daniel) would appreciate any reference having something close to the bound observed above on WB. Gerhard "Going Back To Modesty Now" Paseman, 2020.06.01. $\endgroup$ – Gerhard Paseman Jun 1 at 18:36
  • 1
    $\begingroup$ By analyzing the product more carefully, I get 3k/2 is less than e, so k must be 1. This means we just have m in (n,2n) to worry about for n greater than n0. Further, for n less than n0 we can increase the denominator significantly to arrive at a smaller value of k. I think this will be an improvement on the Erdos paper. Gerhard "Is Still Working The Algebra" Paseman, 2020.06.01. $\endgroup$ – Gerhard Paseman Jun 1 at 22:30
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Now you invested quite some work into this. Thank you very much! It seems to be a hard problem. Do you think it helps to restrict $k \leq n-P$, where $P$ is the biggest prime number $\leq n$? Maybe this is a distance short enough to overcome the hard cases in the middle... $\endgroup$ – Daniel W. May 15 at 6:49
  • 1
    $\begingroup$ If gaps between primes are as small as expected (like (log n)^2), we might get away with modified Langevin. Grimm's conjecture implies your result for k greater than 3. It's possible that my current work may help with values of k that small in spite of the current lack of knowledge of prime gaps. Gerhard "Hasn't Made The Leap Yet" Paseman, 2020.05.15. $\endgroup$ – Gerhard Paseman May 15 at 13:45
  • 1
    $\begingroup$ One can extend both these arguments, but with less certainty and still not close enough to realizing the desired C. There is Harman-Baker-Pintz which allows your k to range from n^{0.525.} plus epsilon on up, and there is modified Langevin which holds for a given k and all n above lcm(1.. sqrt(k)), roughly. If you ask, I will post details. Gerhard "Mathematics Remodeled Almost To Order" Paseman, 2020.05.16. $\endgroup$ – Gerhard Paseman May 16 at 15:39
  • $\begingroup$ I already noticed that my original ring theoretical question is related in many ways to prime gaps. Maybe the problem is equivalent to some conjecture on prime gaps. What do you think? $\endgroup$ – Daniel W. May 17 at 11:21
  • 1
    $\begingroup$ Equivalence to something directly related to prime gaps will be a challenge. To wit, a counterexample of significant size would say something about a gap below n, and also below n/2, n/3, and so on. It might tie in with studies on smooth numbers though. Grimm's conjecture should imply yours, but there may be weaker ones still to which yours might be equivalent. I would like to see the ring theoretic version of your conjecture. Gerhard "If It's Ready For PrimeTime" Paseman, 2020.05.17. $\endgroup$ – Gerhard Paseman May 17 at 19:08

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.