Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A long time ago I solved the following theorem

Let $p_1,p_2,\ldots,p_k$ be distinct primes. Let $\{a_i\}^\infty_{i=1}$ be the increasing sequence of positive integers whose prime factorization contains only these primes (not necesarily all). Show that $\forall c>0\exists n\in \mathbb{N}:a_{n+1}-a_n>c$

Solution. Let $m$ be an integer such that $p^m_i>c$ for all $i=1,2,\ldots,k$. Let $a_n=(a_1a_2\ldots a_k)^m$. As $a_{n+1}>a_n$, there exist a prime $p_j$ such that $p_j^m|a_{n+1}$. Then $p^m|a_{n+1}-a_n$ from which $a_{n+1}-a_n>c$.

Then a friend told me that this stronger version is also true.

Let $p_1,p_2,\ldots,p_k$ be distinct primes. Let $\{a_i\}^\infty_{i=1}$ be the increasing sequence of positive integers whose prime factorization contains only these primes (not necesarily all). Show that $\forall c>0\exists n_c\in \mathbb{N}:n>n_c\implies a_{n+1}- a_n>c$

I've tried to solve it but I couldn't. I'm 90% sure that the stronger version is also true. I'm interested in elementary solutions but a complex one is also welcome.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

This is a result of Thue. For much stronger information, see the 1973 paper "On integers with many small prime factors" (Tijdeman, Compositio Mathematica).

share|improve this answer

This is not quite an answer but possibly a push in the right direction. I remembered the following beautiful idea to show that the reciprocal sum of $a_i$ must be finite:

Recall by Euler's product formula that $\prod_{i=1}^\infty \left(1-\frac{1}{q_i}\right)^{-1}=1+1/2+1/3+\ldots=\infty$ where $q_i$ is the $i'th$ prime. Notice that for your problem you have just $p_1,\ldots,p_k$. Then,

$S:=\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)^{-1}$ is the sum of the reciprocals of all numbers whose factors are $p_1,\ldots,p_k$. Notice that unlike the full Euler product, $S<\infty$. Then

$\sum_{i=1}^\infty \frac{1}{a_i}\leq \prod_{i=1}^k\left(1-\frac{1}{p_i}\right)^{-1} <\infty$

Hence the sum of reciprocals of $a_i$ converges. So by the ratio test, we must have that $\lim_{n\rightarrow\infty} \frac{a_{n}}{a_{n+1}}\leq 1$. In fact this result is inherently obvious since $a_n\leq a_{n+1}$ in the first place but, the point is thinking about it in terms of a sum may be useful.

Now, suppose there exists $c\geq 1$ with $a_{n+1}-a_n>c$ for all $n$. Then, rearranging this and using the fact that $a_n$ is strictly increasing gives

$1>\frac{a_n}{a_{n+1}}>1-\frac{c}{a_{n+1}}$

The problem is that we would like to conclude with a contradiction that $\lim_{n\rightarrow\infty} \frac{a_n}{a_{n+1}}>1$ but, we actually get $\lim_{n\rightarrow\infty} \frac{a_n}{a_{n+1}}=1$ and the equality at 1 gives us an indeterminate result from the ratio test. Perhaps someone more clever than me can show that $\lim_{n\rightarrow\infty} a_{n}/a_{n+1}<1$ which would imply the stronger result by taking the limit along a subsequence $n_i$ for which $a_{n_{i+1}}-a_{n_i}> c$. My initial hope was to try and show the sum must diverge if the limit is 1.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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