Erdős Problem #240

Erdős Problem 240: an infinite prime set with separated smooth numbers

1) Statement and scope

Is there an infinite set of primes $P$ such that successive integers composed only of primes in $P$ have gaps tending to infinity? We reconstruct Tijdeman's inductive argument, obtaining the stronger bound $b-a>\sqrt a$ for every two such integers $a<b$. A consequence of Baker's theorem on logarithms is the explicit deep input.

2) The external logarithmic estimate

The consequence needed here is as follows. Fix a finite prime set $P_0$. There exists $C=C(P_0)$ such that, for any new prime $q>\max P_0$, if \[ a=q^\alpha\prod_{p\in P_0}p^{u_p},\qquad b=q^\beta\prod_{p\in P_0}p^{v_p},\qquad \alpha\ne\beta,\qquad 0<b-a\leq\sqrt a, \] then $a,b\leq q^C$. In particular $\alpha,\beta\leq C$ and $u_p,v_p\leq C\log q/\log p$. This is the estimate derived from Baker's theorem in the proof of Tijdeman's Theorem 7, with its parameter $\theta=1/2$ and with the constant enlarged if necessary. Its crucial uniformity is that $C$ is independent of $q$. We use this estimate as an external theorem, not as an unproved elementary assertion.

3) Extending a finite prime set

Assume all $P_0$-smooth pairs $a<b$ satisfy $b-a>\sqrt a$. Let $q\in[T/2,T]$ be a candidate new prime. If a bad pair in $P_0\cup\{q\}$ has $\alpha=\beta$, division by $q^\alpha$ gives a pair $a',b'$ from the old semigroup, and \[ b-a=q^\alpha(b'-a')> q^\alpha\sqrt{a'}\geq\sqrt a, \] a contradiction. Thus every bad pair has $\alpha\ne\beta$. By the external estimate, the number of possible exponent tuples is $O_{P_0}((\log T)^{2|P_0|})$.

Fix one such tuple and write $b/a=cq^d$, with $d\ne0$ fixed. At least one of $a,b$ is divisible by $q$, so $b\geq q\geq T/2$. Since $b\leq a+\sqrt a\leq2a$, we have $a\geq T/4$. Consequently \[ 0<\log c+d\log q=\log(b/a)\leq2T^{-1/2}. \] The allowed values of $\log q$ lie in an interval of length at most $2T^{-1/2}/|d|$. Restricted to $q\in[T/2,T]$, this gives an interval of $q$ values of length $O(\sqrt T)$. There are therefore $O(\sqrt T)$ integers, hence at most that many primes, excluded by this tuple.

The total number of bad primes is \[ O_{P_0}\left(\sqrt T(\log T)^{2|P_0|}\right) =o(T/\log T). \] The standard prime-counting estimate $\#\{q\text{ prime}:T/2\leq q\leq T\}\gg T/\log T$ shows that some prime remains when $T$ is sufficiently large. Taking also $T/2>\max P_0$ extends the prime set and preserves the required separation.

4) Passing to an infinite set

Start with $P_0=\{3\}$. Distinct powers $a<b$ of three satisfy $b-a\geq2a>\sqrt a$. Repeated extension gives a strictly increasing infinite sequence of primes. Any two integers in the resulting semigroup use only finitely many selected primes, so their separation inequality already holds at some finite stage. Listing the semigroup as $a_1<a_2<\cdots$, we obtain $a_{i+1}-a_i>\sqrt{a_i}\to\infty$.

5) Sources and scope

Sources: https://www.erdosproblems.com/240; R. Tijdeman, On integers with many small prime factors, Compositio Math. 26 $1973$, 319--330, especially Theorem 7, https://www.numdam.org/item/CM_1973__26_3_319_0.pdf. This reconstructs the known argument from its stated Baker estimate and a standard dyadic prime-counting lower bound. Those external inputs are not reproved, and no novelty is claimed.

6) Completion estimate

COMPLETION: 100%