14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $[m,n]$ = least common multiple of $m$ and $n$? $\endgroup$ – Noam D. Elkies Jan 19 '16 at 3:06
  • 1
    $\begingroup$ I have a similar feeling, but it is not that lcm of consecutive members is greater than O(k^2) for infinitely many k. I think a reasonable conjecture is that the lcm is greater than k^2 (or (k^2/2) to be safer) for infinitely many k. Greater than O(k^2) means bigger than dk^2 eventually for any d, and that is too strong. Gerhard "Don't Mess Around With O()" Paseman, 2016.01.18. $\endgroup$ – Gerhard Paseman Jan 19 '16 at 3:26
  • 1
    $\begingroup$ The conjecture looks ok. I still think you should change the title to match. I am also ok with being blamed for guessing that c=1/2 works. Gerhard "Or You Take The Credit" Paseman, 2016.01.18 $\endgroup$ – Gerhard Paseman Jan 19 '16 at 4:00
  • 2
    $\begingroup$ The original theorem stems from artofproblemsolving.com/community/c6h1062614p4605801. (I can't post comments.) $\endgroup$ – mssmath Jan 19 '16 at 4:20
  • 1
    $\begingroup$ The original problem also works for $c < 2^{1/3}$ (see the aops forum thread in one of the answers). $\endgroup$ – Mayank Pandey Jan 19 '16 at 8:42
17
$\begingroup$

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$.

$\endgroup$
11
$\begingroup$

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})$.

$\endgroup$
9
$\begingroup$

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?).

$\endgroup$

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.