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.


Problem.
Suppose that a sequence $\{a_n\}_{(n\ge 1)}$ is a strict increasing sequence of positive integers such that $$\forall i,\phantom{;}j(i\neq j);\phantom{;}a_i \not\mid a_j$$ Prove that $a_{n+1}-a_{n}$ is unbounded.
I had tried various kinds of ways but I couldn't prove the problem; Instead of it, I proved the following result, which is weaker than the original problem;
Weaker result I proved.
Suppose that a sequence $\{a_n\}_{(n\ge 1)}$ is a strict increasing sequence of positive integers such that $$\forall i,\phantom{;}j(i\neq j);\phantom{;}\color{blue}{\gcd(a_i, a_j)=1}$$ Then $a_{n+1}-a_{n}$ is unbounded.
I used Chinese remainder theorem to prove this. (I'll post it if you want it.) I tried to apply similar method for the original problem, but I failed;

Do you have some ideas for the problem?

share|improve this question
add comment

1 Answer 1

up vote 18 down vote accepted
+500

Sequences of positive integers such that no element of the sequence is divisible by any other are called "primitive", and there has been a lot of work done figuring out how dense these sequences can be. An early result of Erdős is that all primitive sequences must have lower density $0$, which immediately implies that they must have arbitrarily large gaps. The proof is quite short and is given in "Note on sequences of integers no one of which is divisible by any other", J. London Math. Soc. 10 (1935), pp. 126-128. There is also a similar result in Felix Behrend, "On Sequences of Numbers not Divisible one by another", J. London Math. Soc. (1935) s1-10(1): 42-44 (paper is behind a pay wall.)

A later, more precise result by Erdős, Sárközy and Szemerédi ("On a theorem of Behrend", J. Australian Mathematical Society, 7 (1967), pp. 9-16) is that if $(a_1,a_2,\dots)$ is a primitive sequence, then $$ \sum_{a_i<x} \frac{1}{a_i}=o(\frac{\log x}{\sqrt{\log \log x}}), $$ and this is best possible in the sense that the fraction on the right-hand side cannot be divided by any $h(x)$ with $\lim_{x\to\infty} h(x)=\infty.$

share|improve this answer
add comment

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.