19
$\begingroup$

An infinite sequence of increasing positive integers is given with bounded first differences.

Prove that there are elements $a$ and $b$ in the sequence such that $\dfrac{a}{b}$ is a positive integer.

I think maybe computing the Natural Density of the sequence would lead to some contradiction. But don't know if it exists.

Any help will be appreciated.
Thanks.

$\endgroup$
  • 2
    $\begingroup$ This seems to me mre of a combinatorial problem..An application of pigeonhole principle maybe? $\endgroup$ – Marios Gretsas Nov 28 '17 at 15:26
  • 1
    $\begingroup$ @MariosGretsas I was thinking something along the lines of density of such numbers. $\endgroup$ – Henry Nov 28 '17 at 16:27
  • 2
    $\begingroup$ @Henry That approach will definitely work: it is a famous result of Erdős that if $\{a_n\}$ is an increasing sequence of positive integers which don't divide one another, then $\sum_n 1/(a_n \log a_n)$ converges (in fact, is bounded). This certainly can't happen if $\{a_n\}$ has positive lower density. $\endgroup$ – Erick Wong Nov 28 '17 at 18:39
  • 1
    $\begingroup$ What is the source of the problem? The context may give an indication as to which tools are needed. $\endgroup$ – punctured dusk Nov 28 '17 at 21:15
  • 2
    $\begingroup$ @MariosGretsas One subtlety here is that the result does depend crucially on the sequence extending to infinity. The finite sequence $\{n+1,n+2,\ldots,2n\}$ has very bounded gaps and very high density ($\tfrac12$), but doesn't contain any dividing pairs. This suggests there has to be some aspect of any proof that uses some global consideration. $\endgroup$ – Erick Wong Nov 29 '17 at 10:51
12
$\begingroup$

Here is a 1935 paper of a relatively young Erdős proving in a few lines that a sequence of positive integers which don't divide one another must have lower density zero, as a consequence of the fact that $\sum_n 1/(a_n \log a_n)$ is bounded by an absolute constant. In particular, a sequence with gaps bounded by $d$ has lower density at least $1/d$, so this proves the claim, but perhaps there is a more direct argument. The bounded gap requirement does handily eliminate any possibility of a Besicovitch-type construction (which yields a positive upper density, but introduces gaps which grow very rapidly in length).

$\endgroup$
  • 1
    $\begingroup$ (+1) Thanks for the reference! I'll keep this question open and perhaps add a bounty since I think there might be more approaches. $\endgroup$ – Henry Nov 28 '17 at 19:50
2
$\begingroup$

I have doubts about the effeciency of this proof attempt, but it is just an extension of @MooS 's answer that is based upon the fact that increasing prime gaps are diverging to infinity, and they are!:

The proof in the paper claims that for an arbitrary large $n$ there is a sequence $n!,n!+2,n!+3,n!+4....n!+n=n!,2(n!/2+1),3(n!/3+1)...$ of composite numbers intermediating the largest prime $p_0$ before $n$ and the nearest $p_1$ after $n!+n$ which converges respectively of larger $n$.

On this ground you should remark that picking up consecutive primes iterately will force us into a pitfall! what is it ? it's like a cul-de-sac after consecutive leaps over prime gaps it should exist some infinitely divergent one when you have to choose a composite number as forced to be bound to some limit of differences.

What if a range of primes are skipped ? The following numbers should be mutually indivisible written in the form of skipped prime numbers. $p_0^ip_1^j...$ in the forthcoming must have decreasing prime weights, which means descending sets of {i,j..} thus they wouldn't divide their previous. Which immediately indicates that picking up a composite $p_0^ip_1^jp_2^k$ for example must consequently lead to a following $p_0^{i'}p_1^{j'}p_2^{k'}\prod_l p_l^l$ where $i+j+k>i'+j'+k'$.

Let's denote a prime quotient: a ratio between two composite mutually indivisible numbers chosen consequently. The prime quotient between the two previous composites is $\frac{p_0^{i'}p_1^{j'}p_2^{k'}\prod_l p_l^l}{p_0^ip_1^jp_2^k}$ their values are continuously increasing. The only steady sequence that guarantees a smallest prime quotient is $p_jp_{j+1}$ the prime quotient is ultimately small which equals $\frac{p_{j+2}}{p_j}$, consequently the gap between them $p_{j+1}(p_{j+2}-p_{j})$ is divergent.

I was planning to check my claims with an exhaustive sweepment program but there is already a handful here by which one can ensure that increasing n-prime gaps are also divergent.

$\endgroup$
  • $\begingroup$ This argument is nearly incomprehensible. What does "it's like a cul-de-sac after consecutive leaps over prime gaps it should exist some infinitely divergent one when you have to choose a composite number as forced to be bound to some limit of differences" even refer to? What's the context? What's wrong with choosing a composite number? The sequence need not even contain a single prime. The link about $n$-prime gaps is also of only mild relevance since the sequence need not be chosen greedily. $\endgroup$ – Erick Wong Dec 2 '17 at 17:52
  • $\begingroup$ @ErickWong a composite number in a sense of a product between an already chosen number with an arbitrary composite/prime number. a cul-de-sac is a situation when you are limited to not extend your choice more than a definite bound $n$, which force us to opt for a composite number = a divisible number by a previous one. $\endgroup$ – Abr001am Dec 2 '17 at 18:35
  • $\begingroup$ @ErickWong I just think of it as an attempt, it doesn't prove anything since there dosn't exist any mathematical notation to define where a deadlock can occur, even with a steady sequence of chosen numbers, prime gaps are random, unexpected, I don't think that anyone can maybe even bind a cul-de-sac situation to a range of inequalities, Only i conjectured that this situation must happen at some point because prime gaps doesn't converge! $\endgroup$ – Abr001am Dec 2 '17 at 19:45

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.