Problem 6

Problem

Let $a_1,a_2,\ldots$ be an infinite sequence of positive integers greater than $1$. For every positive integer $n$, let $a_{n+1}$ be the smallest positive integer greater than $a_n$ such that

Prove that there exist positive integers $T$ and $L$ such that

for every positive integer $n$.

Solution

We use zero-based indexing in this proof, writing the sequence as $a_0,a_1,\ldots$.

Call a positive integer $x$ globally compatible if it has a nontrivial common divisor with every term of the sequence:

Every two sequence terms have gcd greater than $1$, so every $a_i$ is globally compatible. The sequence is strictly increasing; in fact, $a_n\ge a_0+n$, so it is unbounded. Moreover, the greedy rule implies that $a_{n+1}$ is the least globally compatible integer greater than $a_n$: a globally compatible candidate automatically satisfies all the finitely many gcd conditions appearing in the original definition.

It follows that the sequence lists, in increasing order, all globally compatible integers at least $a_0$. Indeed, for any such $x$, look at the first sequence term not smaller than $x$; greedy minimality forces equality.

A period for global compatibility

A globally compatible integer $m$ is called minimal if it is squarefree and no proper positive divisor of $m$ is globally compatible. Every positive globally compatible $x$ is divisible by such an $m$: first replace $x$ by the product of its distinct prime factors, which remains globally compatible, and then choose a smallest globally compatible divisor.

For each positive integer $c\le a_0$, choose an index $w(c)$ for which $a_{w(c)}$ is coprime to $c$ whenever such an index exists; use $w(c)=0$ otherwise. Let $Q$ be the finite set of all primes dividing the resulting terms $a_{w(c)}$, and define

Then $L>0$. We claim that every minimal globally compatible integer divides $L$.

Fix a prime $q\mid m$, where $m$ is minimal. We prove by descent that there is another minimal globally compatible $m'$, still divisible by $q$, such that

Start with the current minimal number $r=m$. If $r/q\le a_0$, the descent is finished. Otherwise put $d=r/q>a_0$. Since $d$ is a proper positive divisor of the minimal number $r$, it is not globally compatible. Look at the first sequence term $a_{j+1}$ that is at least $d$, so $a_j<d$. If $d$ had nontrivial gcd with every $a_i$ for $i\le j$, it would be eligible at step $j$, and greedy minimality would give $a_{j+1}\le d$. Hence $a_{j+1}=d$, making $d$ a sequence term and therefore globally compatible, a contradiction. Thus some $a_i<d$ is coprime to $d$.

Choose a minimal globally compatible divisor $m_1$ of $a_i$. Then

Moreover $q\mid m_1$. Otherwise the prime $q$ is coprime to $m_1$, and $d$ is also coprime to $m_1$ because $m_1\mid a_i$. Hence $r=qd$ would be coprime to $m_1$. This is impossible: here $r>a_0$, so the globally compatible number $r$ occurs as a sequence term, while global compatibility of $m_1$ says that $m_1$ is noncoprime to every sequence term, including $r$. Replace $r$ by the strictly smaller minimal number $m_1$ and repeat. The positive integer $r$ strictly decreases, so the process terminates and proves the descent claim.

For the resulting $m'$, put $c=m'/q\le a_0$. The proper divisor $c$ is not globally compatible, so its chosen witness $a_{w(c)}$ is coprime to $c$. But $m'=qc$ is globally compatible and therefore is not coprime to $a_{w(c)}$. Hence $q\mid a_{w(c)}$, so $q\in Q$. Since the original $m$ is squarefree, all its prime factors occur in $Q$, and therefore $m\mid L$.

Now let $x>0$. If $G(x)$, choose a minimal globally compatible divisor $m\mid x$. Since $m\mid L$, we get $m\mid x+L$, hence $G(x+L)$. Conversely, if $G(x+L)$, choose a minimal globally compatible $m\mid x+L$. Again $m\mid L$, so $m\mid x$, and therefore $G(x)$. Thus we have the periodicity relation $(1)$:

Translating the greedy enumeration

Since $G(a_0)$, relation $(1)$ gives $G(a_0+L)$. Because the sequence enumerates all globally compatible integers from $a_0$ onward, there is an index $T$ such that

As $L>0$ and the sequence is strictly increasing, $T>0$.

We prove by induction on $n$ that

The case $n=0$ is the definition of $T$. Suppose the identity holds at $n$. The number $a_{n+1}$ is the least globally compatible integer greater than $a_n$, so periodicity makes $a_{n+1}+L$ globally compatible and greater than $a_n+L$. Conversely, if a globally compatible integer $y$ is greater than $a_n+L$, then $y-L>a_n>0$, and $(1)$ shows that $y-L$ is globally compatible. Thus $a_{n+1}\le y-L$, proving that $a_{n+1}+L$ is the least globally compatible integer greater than $a_n+L=a_{n+T}$. The greedy definition identifies this least integer with $a_{n+T+1}$. Hence

completing the induction. Therefore there exist positive integers $T,L$ such that