3
$\begingroup$

Let $g(x,c)$ be a uniformly random integer in the range $(x,x+c)$ and $LCM[x_1,x_2...x_i]$ the lowest common multiple of the integers $x_i$.

A) Does the limit of (the asymptotics of $LCM[g(3^1,c),g(3^2,c),...,g(3^x,c)]$ as $x→∞$) as $c→∞$ exist?

B) How to find the limit of A) if it exists ?

C) Given any strictly increasing unbounded function $f(n)>O(n)$, how to find the asymptotics of $LCM[g(f(1)),g(f(2))...g(f(x))]$ as $x→∞$, and then as $c→∞$?

Alternatively, is there any reference that seeks an answer to above questions? Which tools can be used to solve the above?

$\endgroup$
3
  • 3
    $\begingroup$ Which one of the formulations do you want, $g(x)$ in the range $(0.99 x, 1.01 x)$, or $g$ in the range $(x-1000,x+1000)$? I suspect they are different. And do you really want this for all $f$, or do you have an $f$ you care about? There are some challenging questions here, but I am turned off from thinking about them because (1) There are several different questions, and it is hard to know which one to focus on and (2) your language sounds like you copied this out of a textbook, without motivation or background. $\endgroup$ Oct 10, 2011 at 18:39
  • 2
    $\begingroup$ Also posted with bounty on Math Stack Exchange: math.stackexchange.com/questions/69828/asymptotics-of-lcm $\endgroup$ Oct 10, 2011 at 19:45
  • $\begingroup$ @David Thanks I have incorporated your suggestions. $\endgroup$
    – hakuna
    Oct 13, 2011 at 18:29

1 Answer 1

1
$\begingroup$

There are some basic results about LCM that you can use. Here's one: for any increasing sequence of positive integers $a_1 \lt \ldots \lt a_n$, one has $a_n \leq LCM(a_1 , \ldots, a_n) \leq a_1 \times \ldots \times a_n$ . So if $a_n$ increases quickly enough, the difference between the logs of the upper and lower bounds will be small compared to the log of the LCM, so the logarithm of the logarithm of the LCM may have a computable limit.

There may be a statistical difference between using $x$ and using $g(x,c)$, but I am having a hard time seeing it for general $x$. Letting $b_n = LCM(a_1, \ldots, a_n), a_{n+1}$ will have to be pretty special in order for $b_n$ not to be coprime to any number between $a_n$ and $a_n + c$ inclusive even when c is smaller than $\log(b_n)$; even then, most such numbers will have a small factor in common with $b_n$, so you might as well replace $g(a_{n+1},c)$ by a number coprime to $b_n$ that looks like a small multiple or factor of $a_{n+1}/log(b_n)$.

Given that the limiting probability of two positive integers being coprime is $6/\pi^2$, I would suspect that $b_n$ will "look like" a small multiple of the product of perhaps 2/3 of the members of the increasing sequence in the case that the increase in a_n is exponential or near exponential. If your sequence increases slowly, the LCM will most likely increase in a fashion similar to the factorial or primorial function.

If you provide some motivation, I may be able to give some definite answers toward the motivating problem.

Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2011.10.13

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.