Infinitely many $k$ such that $[a_k,a_{k+1}]>ck^2$

Question

Let $a_n\in \mathbf{N}$ be an infinite sequence such that $\forall i\neq j, a_i\neq a_j$.

I have the following theorem:

For $0<c<\frac{3}{2}$, there are infinitely many $k$ for which $[a_k,a_{k+1}]>ck$, where $[\cdots]$ denotes least common multiple.

Idea of proof: By contradiction. Suppose there is an $M$ such that for all $k>M$, $[a_k,a_{k+1}]\leq ck$.

On the one hand,

$\displaystyle \sum_{k=1}^{n}\frac{1}{[a_k,a_{k+1}]}\geq \sum_{k=M+1}^{n}\frac{1}{[a_k,a_{k+1}]}\geq \sum_{k=M+1}^{n}\frac{1}{ck}$

On the other hand,

$\displaystyle \frac{1}{[a_k,a_{k+1}]}$

$\displaystyle =\frac{(a_k,a_{k+1})}{a_ka_{k+1}}$

$\displaystyle =(a_k,a_{k+1})\frac{1}{a_k+a_{k+1}}(\frac{1}{a_k}+\frac{1}{a_{k+1}})$

$\displaystyle =\frac{1}{\frac{a_k}{(a_k,a_{k+1})}+\frac{a_{k+1}}{(a_k,a_{k+1})}}(\frac{1}{a_k}+\frac{1}{a_{k+1}})$

$\displaystyle \leq \frac{1}{3}(\frac{1}{a_k}+\frac{1}{a_{k+1}})$

$\displaystyle \sum_{k=1}^{n}\frac{1}{[a_k,a_{k+1}]}\leq \frac{1}{3}\sum_{k=1}^{n}(\frac{1}{a_k}+\frac{1}{a_{k+1}})\leq \frac{2}{3}\sum_{k=1}^{n}\frac{1}{k}$

And I make the following conjecture:

$\exists c>0$, there are infinitely many $k$ for which $[a_k,a_{k+1}]>ck^2$.

But I cannot prove or disprove it.

Answer 1

In fact there are sequences $\{a_k\}$ of pairwise distinct positive integers such that $[a_k, a_{k+1}] \ll k^{1+\epsilon}$ for all $\epsilon > 0$.

We first exhibit a sequence with $[a_k, a_{k+1}] \ll k^{3/2} \log^3 k$ for all $k>1$, which already disproves the conjecture that $[a_k, a_{k+1}] \gg k^2$ infinitely often. The sequence will consist of all numbers of the form $p_m p_n$ with $m$ odd and $n$ even, listed in the following order: $$ \begin{array}{cccccccc} 17\cdot 3 & \rightarrow & 17\cdot 7 & \rightarrow & 17\cdot 13 & \rightarrow & 17\cdot 19 & \cr \uparrow & & & & & & \downarrow & \cr 11\cdot 3 & \leftarrow & 11\cdot 7 & \leftarrow & 11\cdot 13 & & 11\cdot 19 & \cr & & & & \uparrow & & \downarrow & \cr 5\cdot 3 & \rightarrow & 5\cdot 7 & & 5\cdot 13 & & 5\cdot 19 & \cr \uparrow & & \downarrow & & \uparrow & & \downarrow & \cr 2\cdot 3 & & 2\cdot 7 & \rightarrow & 2\cdot 13 & & 2\cdot 19 & \rightarrow \end{array} $$ Then each $a_k$ is $p_m p_n$ with $m,n \ll \sqrt k$, so $p_m, p_n \ll \sqrt k \log k$; and each $[a_k,a_{k+1}]$ is the product of three such primes, so $\ll k^{3/2} \log^3 k$, as claimed.

Likewise, for each $M>1$ we can use products of $M$ primes to obtain a sequence $\{a_k\}$ of pairwise distinct positive integers such that $[a_k, a_{k+1}] \ll k^{(M+1)/M} \log^M k \ll k^{1+\epsilon}$ for all $\epsilon > 1/M$. Finally, by concatenating ever-longer initial segments of the sequences for $M=2$, $M=3$, $M=4$, etc. we construct a sequence $\{a_k\}$ of pairwise distinct positive integers such that $[a_k, a_{k+1}] \ll k^{1+\epsilon}$ for all $\epsilon > 0$.

Answer 2

In this paper
P. Erdős, R. Freud, and N. Hegyvári, Arithmetical properties of permutations of integers, Acta Mathematica Hungarica 41:1-2 (1983), pp 169-176. http://renyi.mta.hu/~p_erdos/1983-02.pdf the authors show that for permutations of {1,2,...,n} the answer is $\Theta(n^2/\log n)$.

See https://oeis.org/A064764 .

Also for infinite permutations they give an example where ${\rm lcm}(a_i, a_{i+1}) < i \exp (c \sqrt{\log i} \log\log i)$ for all $i$.

And I see that Chen, Y.-G.; Ji, C.-S. The permutation of integers with small least common multiple of two subsequent terms. Acta Math. Hungar. 132 (2011), no. 4, 307–309 has improved on this still further, to $i \exp (c' \sqrt{\log i\log\log i})$.

Answer 3

Here is a counterexample for the exponent 2. But I think it should be wrong also for some smaller exponents.

We construct $(a_k)$ by blocks. The $n$th block consists of all the numbers of the form $(2n-1)2^t$, where $t$ is an integer satisfying $0\leq t\leq 10+\log_2 n$. The values of $t$ inside the block are ordered as $0,2,3,\dots,t_{\max},1$. The first $N$ blocks thus occupy $$ \sum_{i=1}^N \log_2 i+O(N)=N\log_2N+O(N) $$ terms of the sequence.

Now,

(1) if $a_k$ and $a_{k+1}$ belong to the $n$th block, then $k\geq (n-1)\log_2(n-1)+O(n)=n\log_2n+O(n)$, while $[a_k,a_{k+1}]=\max(a_k,a_{k+1})<2^{11}n^2=o(k^2)$. Otherwise,

(2) $a_k$ belongs to the $n$th block and $a_{k+1}$ belongs to the $(n+1)$th one, then $[a_k,a_{k+1}]=2(4n^2-1)=o(k^2)$ again, as required.

If we look for a counterexample for a smaller exponent, case (1) can easily be improved by changing the range of $t$ (at the beginning) by $0\leq t\leq 10+\alpha\log_2 k$ for a fixed $\alpha\in(0,1)$. Thus the crucial point is to make something with (2); I would assume that some rearranging of the blocks may work (perhaps, one may apply a similar procedure for the block numbers?).