For any prime $p$, is there $C$ such that if $x\ge C$, then all but one integer among $x+1, x+2, \dots, x+p$ has Greatest Prime Factor $> p$

Question

I apologize if this is a naive question about greatest prime factors (gpf). I was thinking about the sequence of integers where $\mathrm{gpf}(x) \le p$ where $p$ is any prime.

Clearly, as $x$ increases, the distance $d$ between an integer where $\mathrm{gpf}(x) \le p$ and $\mathrm{gpf}(x+d) \le p$ increases at a seemingly every increasing rate.

For all primes $p$, does there exist an integer $C$ where if $x \ge C$, then there is at most one integer in the sequence $x+1, x+2, \dots, x+p$ has $\mathrm{gpf}(x) \le p$

For example, if $p=2$, $C = 2$ since for any $x \ge 2$, either $x$ or $x+1, \mathrm{gpf}(x) > 2$

Answer 1

This is a summary of Gerhard Paseman's comment.

Suppose that $A$ and $B$ are two numbers with $A-B = c$ small such that $A$ and $B$ are only divisible by prime numbers less than or equal to $p$. Then one can write

$$A = a x^3, \qquad B = b y^3,$$

where all the prime factors of $a$ and $b$ are less than or equal to $p$, and all the exponents of each prime number is at most $2$ (the higher factors get absorbed into the cube). Note that if $p$ is the $n$th prime number, then there are $3^n$ possible values of $a$ and $b$. The answer to your problem will be positive provided that one can show that each of the ($3^{2n}$) equations

$$a x^3 - b y^3 = c$$

Has only finitely many solutions. Yet a theorem of Thue (1908) guarantees that if $f(x,y)$ is irreducible of degree $\ge 3$, then $f(x,y) = c$ has only finitely many integral solutions.

This leaves the reducible cases corresponding to the ratio $[a:b]$ being a perfect cube. Yet these are trivial; after absorbing the coefficients and multiplying through, one is left with an equation

$$X^3 - Y^3 = C$$

to solve in integers $X$ and $Y$. Yet this also has finitely many solutions for a trivial reason - the consecutive cubes become further apart.

Thue's results are actually effective, one can also prove this result by various other means, like Baker's method.

This problem is actually the baby case of the $S$-unit equation. In particular, it ultimately boils down to solving the equation

$$A + B = C$$

where $A$, $B$, and $C$ have a fixed set of prime factors dividing $S$ (Take $S$ to be the product of primes less than or equal to the maximum of $p$ and the range corresponding to $c$ in the Thue equations above). In other words, one is looking for a solution in units to the equation $A+B=C$ in the ring $\mathbf{Z}[1/S]$. The methods above can be generalized to applied to similar problems where $\mathbf{Z}[1/S]$ is replaced by the $S$-units in a number field, and one can even increase the number of terms (providing that one is careful only considers primitive solutions, ruling out trivialities like $A-A+B-B=0$.)

Answer 2

I heard a great answer to this question based on the Thue equation.

I investigated the Thue equation and there was one point that was not clear to me. It seems to me that there are an infinite number of values that $a$ and $b$ can take. If there are an infinite number of combinations of finite solutions, then there is an infinite number of solutions. Right?

So, if I understand it, the Thue equation alone doesn't seem to work. I apologize if I am misunderstanding the classical result there.

Here's an argument that seems to work as far as I understand:

(1) For any prime $p$, there is a finite number of combinations of primes that are less than $p$.

(2) For any of these combinations there exists an integer $x$ such that if a combination is greater than $x$, then at least one of the primes that make up the combination are of a degree greater than $2$.

(3) Let $c$ be either the highest of the values $x$ from step (2) or $4p^{4}(3\prod_{p} p^{\frac{1}{2}})^3$ depending on which is higher.

(4) There is a finite number of ways that we can pair these different combinations so that we have an equation of the form $ax^3 - by^3 = c$ where $c < p$.

(5) If $a \ne b$ and $gcd(x,y)=1$, then using a result from Siegel, there is at most $1$ solution (see Theorem A in the link below).

http://matwbn.icm.edu.pl/ksiazki/aa/aa75/aa7538.pdf

(6) if $a = b$ and $a = c$, then using a result from Michael Bennett, there is at most $1$ solution. Here's the reference:

M. A. Bennett, Rational approximation to algebraic numbers of small height : the Diophantine equation $|ax^n-by^n|=1$}, J. Reine Angew. Math. 535 (2001), 1-49

http://www.math.ubc.ca/~bennett/B-Crelle2.pdf

(7) if $a = b$ and $a < c$, then the equation has a form such as:

$x^3 - y^3 = \frac{c}{a}$

This is a Thue Equation and we can conclude that there is a finite number of solutions.

(8) if $a \ne b$ and $gcd(x,y) > 1$, then it means that both combinations consist of the same prime so we have an equation of the form:

$x^m - x^n = c$

Then, as I understand it, we have a Thue equation so we can again assume that there is a finite number solutions.

I believe that covers all the possible cases.

Since, there are only a finite number of solutions, it follows that there exists an integer $c$ which is greater than all of these solutions and for all $x \ge c$, we have at most $1$ integer in the sequence where $gpc(x+i) \le p$.

Apologies for the length of this argument. I'm sure a professional mathematician such as user 631 would be able to state the argument more elegantly. :-)

Answer 3

I don't know how far Larry went in pursuing this problem, but this touches on a topic I've spent some time on, ie. Lehmer's method.

Let $S_j$ be the maximum $S$ for which the pair {$S, S+j$} is $p$-smooth, and let $S_m$ be the maximum of $\{S_1, S_2 \ldots S_p\}$. Also let k = $\pi(p)$, ie. the number of primes $\leq p$.

It follows then that the minimal $C$ for which the desired property holds is $C = S_m$.

Determining each $S_j$ is not so straight-forward, apart from the cases $j=1, 2$, which are a direct application of Lehmer's method, which provides for the enumeration of all smooth pairs of the form $\{S, S+1\}$, $\{S, S+2\}$, by solving roughly $2^k$ standard Pell equations, ie. $x^2 - Dy^2 = 1$, for $D$ ranging over all combinations of the $k$ primes $\leq p$. Both sets of pairs can be obtained with a single pass.

For $3 \leq j \leq p$, however, things are not so simple. Lehmer did not address these cases, and perhaps we can understand why. We can in fact extend Lehmer's method to identify smooth pairs $\{S, S+j\}$, but this requires solving $x^2 - Dy^2 = j^2$, again for all $2^k$ values of $D$.

The good news is that these equations can be solved from the $x^2 - Dy^2 = 1$ solutions, so that the number of continued fractions we have to compute is still the same. See John Robertson's article on the LMM method (Lagrange-Matthews-Mollin) at JPR_Pell.

Note that there can be multiple solution classes for any $j$.

The bad news is that Lehmer's main achievement, by which he is able to reduce the number of Pell equations from $3^k$ to $2^k$, is not applicable for $j \geq 3$. For $j = 1, 2$ he showed that any smooth pair that does not turn up as a fundamental solution $(x_1, y_1)$ will be found at some $(x_m, y_m)$ with $m \leq (p+1)/2$. This is because the $y_n$ values form a Lucas sequence, and so $y_1$ divides all $y_n$. Thus, if $y_1$ isn't smooth, neither will be any other $y_n$. And if $y_1$ is smooth, we only need check a limited number of $y_n$.

Sadly, the multiple solutions in any class of solutions to $x^2 - Dy^2 = N$, $(N=j^2)$, do not have these Lucasian properties. So we don't know how many $(x_n, y_n)$ to look at, and we can't assume that $y_1$ not being smooth means that $y_2$ isn't either.

We could of course revert to the original Störmer method, where we solve for $D$ being all possible combinations of the $k$ primes to the power $\{ 0, 1, 2 \}$, thus requiring roughly $3^k$ equations to be solved. That's very slow, but guarantees that smooth pairs occur only as fundamental solutions.

Alternately, it might well be that $S_1 > S_j$ always, in which case we would avoid all of these complications, solving only the standard equations $x^2 - Dy^2 = 1$. I have not yet done any investigation of this question, but I remember that generally $S_2 < S_1$, so this property can't be ruled out.

Finally, I would like to know if Larry looked into the method described above involving $X^3 - Y^3 = C$, and if so, how it works.