9
$\begingroup$

$\DeclareMathOperator\lcm{lcm}$We know that $\operatorname{lcm}(1,\dotsc,n)$ is approximately $e^n$ and we also know that $\gcd(2^a-1, 2^b-1)=2^{\gcd(a,b)}-1$.

I wonder if there exists an upper bound/lower bound/approximation for $\operatorname{lcm}(2^1-1, 2^2-1,\dotsc,2^n-1)$.

$\endgroup$
5
  • 2
    $\begingroup$ It's at least $2^n - 1$ and it's at most $\prod_{i=1}^n (2^i - 1) \le 2^{{n \choose 2}} - 1$. $\endgroup$ Apr 2, 2015 at 7:24
  • 6
    $\begingroup$ As $\operatorname{gcd}(2^p-1,2^q-1)=1$ if $p,q$ are distinct primes, it's at least the product of $2^p-1$ where $p$ ranges over the primes at most $n.$ I think this should give you an asymptotic lower bound of $2^{cn^2/\operatorname{log}(n)}$ where $c$ is any constant less than $\frac{1}{2}.$ $\endgroup$
    – dhy
    Apr 2, 2015 at 7:48
  • 5
    $\begingroup$ Kazimierz Szymiczek worked this out in a paper around 1970. Sorry I'm away from my office and can't give you a better reference. $\endgroup$ Apr 2, 2015 at 11:53
  • $\begingroup$ One can choose prime powers instead of primes in dhy's product and bump up the lower bound by more than 2^n for large n. $\endgroup$ Apr 2, 2015 at 16:27
  • $\begingroup$ I found the Szymiczek reference: On the distribution of prime factors of Mersenne numbers, Prace Mat. 13 (1969) 33–49, MR0252316 (40 #5537). Unfortunately, I don't seem to have the actual paper, nor can I find it online. $\endgroup$ Apr 9, 2015 at 2:53

2 Answers 2

18
$\begingroup$

Here my guess that seems to be confirmed by numerical computation.

Let $(u_n)_{n \geq 0}$ be a non-degenerate Lucas sequence of the first kind with a dominant positive real root $\alpha$. In other words, $u_0 = 0$, $u_1 = 1$, $u_{n+2} = a u_{n+1} + b u_n$ for each $n \geq 0$ for some relatively prime integers $a, b$; and the roots $\alpha, \beta$ of the characteristic polynomial $X^2 - aX - b$ are real and satisfy $\alpha > |\beta|$.

Can we find some asymptotic for $L_n := \text{lcm}\{u_k : k \leq n\}$ as $n \to \infty$?

Note that your case of $u_k = 2^k-1$ is given by $a = 3$, $b = -2$ (and hence $\alpha = 2$).

It holds the product formula $$u_n = \prod_{\substack{d \,\mid\, n \\ d > 1}} \Phi_d ,$$ where $$\Phi_d := \prod_{\zeta \text{ primitive $d$-th root of unity}} (\alpha - \zeta \beta)$$ is the homogeneous cyclotomic polynomial of $\alpha$ and $\beta$. Thus, clearly $L_n \mid \prod_{k \leq n} \Phi_k$. On the other hand, it is not true that the $\Phi_d$'s are pairwise coprime, however if $\gcd(\Phi_k, \Phi_h) > 1$ for some $k < h$, then $\gcd(\Phi_k, \Phi_h)$ is a prime number. Therefore, it seems quite possible that $L_n$ is not too smaller than $\prod_{k \leq n} \Phi_k$, so I guess $\log(L_n) \approx \sum_{k \leq n} \log(\Phi_k)$. Since $\alpha$ is dominant and $\Phi_k$ has degree $\varphi(k)$, it should be $\Phi_k \approx \alpha^{\varphi(k)}$. Finally, from the asymptotic formula $$\sum_{k \leq n} \varphi(k) = \frac{3}{\pi^2}n^2 + O(n)$$ my conjecture is that $$\log(L_n) \sim \frac{3\log\alpha}{\pi^2} \cdot n^2 ,$$ as $n \to \infty$.

P.S. My conjecture is true. The question was studied in much generality by S. Akiyama and F. Luca [1]. In particular, their Theorem 2 gives the guessed asymptotic for $L_n$, also with a good error term.

[1] S. Akiyama and F. Luca, On the least common multiple of Lucas subsequences, Acta Arith. 161 (2013), 327--349

$\endgroup$
5
$\begingroup$

The Szymiczek paper that I mentioned in comments some time ago is now available on the web. From Theorems 7 and 8 in the paper, we get $$\log{\rm lcm}(2^1-1,\dots,2^{[x]}-1)={3\log2\over\pi^2}x^2+O(x\log x)$$

$\endgroup$
1

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.