21
$\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$
13
  • 2
    $\begingroup$ This seems to me mre of a combinatorial problem..An application of pigeonhole principle maybe? $\endgroup$ Nov 28, 2017 at 15:26
  • 1
    $\begingroup$ @MariosGretsas I was thinking something along the lines of density of such numbers. $\endgroup$
    – Henry
    Nov 28, 2017 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, 2017 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$ Nov 28, 2017 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, 2017 at 10:51

2 Answers 2

15
$\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 $\ge 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
  • 2
    $\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, 2017 at 19:50
3
$\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$
3
  • $\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, 2017 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, 2017 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, 2017 at 19:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .