15
$\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$ Commented 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
    Commented 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$ Commented 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$ Commented 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$ Commented Apr 9, 2015 at 2:53

3 Answers 3

25
$\begingroup$

Here is my guess, which 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$
16
$\begingroup$

The Szymiczek paper (On the distribution of prime factors of Mersenne numbers, Commentationes Mathematicae 13 (1969), pp. 33–49, doi 10.14708/cm.v13i1.5654) 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
7
$\begingroup$

Using inclusion-exclusion, we can give the following explicit formula:

$$\mathrm{lcm}(2^1-1,2^2-1,\dots,2^n-1) = \prod_{k=1}^n (2^k-1)^{M(\lfloor n/k\rfloor)},$$ where $M(\cdot)$ is Mertens function.

Ignoring "$-1$" in the factors, the last expression can be approximated by $$2^{\sum_{k=1}^n kM(\lfloor n/k\rfloor)} = 2^{\Phi(n)} \approx 2^{\frac3{\pi^2}n^2},$$ giving the same estimate as in the other answers, where $\Phi(\cdot)$ is the totient summatory function. Perhaps, this approximation can be made rigorous, but I'll leave it here just as an idea.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .