1

As I can see $$\prod_{i=2}^n log{(i)} = log(2) \cdot log(3) \cdot log(4)...log(p) \cdot log(p+1) ... log(n)= O(k^n)$$ when $$ log(p) = k$$ Am I right? Is there any better Big-$O$ for it?

ChaosPredictor
  • 303
  • 3
  • 12

2 Answers2

3

\begin{align*}\log\left(\prod_{i=2}^{n}\log(i)\right)&=\sum_{i=2}^{n}\log\log(i)\\\text{(Jensen's Inequality)}&\leq (n-1)\log\left(\frac{1}{n-1}\sum_{k=2}^{n}\log(i)\right)\\\text{(again)}&\leq(n-1)\log\log\left(\frac{1}{n-1}\sum_{k=2}^{n}i\right)\\&=(n-1)\log\log\left(\frac{n+2}{2}\right) \end{align*}

This gives $\prod_{i=2}^{n}\log(i)\leq \left(\log\left(\frac{n+2}{2}\right)\right)^{n-1}.$

RideTheWavelet
  • 3,543
  • What is a good estimation for $\frac{\log 2}{\log n}\frac{\log 3}{\log n}\cdots\frac{\log(n-1)}{\log n}$ in the $n\rightarrow\infty$ limit? – Zhuoran He Nov 18 '17 at 21:16
  • @ZhuoranHe You're absolutely right. My ultimate bound is right, but the argument I gave was wrong, so I've fixed that. I'm not sure what a good estimate is for that product, but it would give a better estimate for the constant (rather than my $4/3,$ which is a guess that was numerically checked). – RideTheWavelet Nov 18 '17 at 21:27
  • The limit of that product when $n\rightarrow\infty$ is $0$, which means $\log 2\cdots\log n$ is much smaller than $(\log n)^{n-1}$. But it's difficult to get the error within a nonzero constant factor. I tried using integration but got the logarithmic integral function: http://mathworld.wolfram.com/LogarithmicIntegral.html – Zhuoran He Nov 18 '17 at 21:30
  • It looks like some of the inequalities are quite weak, then, but we might have guessed this, since the equality case for Jensen's is that all of the terms in the sum are equal (which is quite far from being true here, and gets worse as $n$ grows). – RideTheWavelet Nov 18 '17 at 21:53
  • why I can say that $log(i) \le log(n)$ for any i from 2 to n. That lead the the same answer, isn't? – ChaosPredictor Nov 18 '17 at 21:56
  • @ChaosPredictor, it's like saying $O(n^2)$ is also $O(n^3)$, but not giving the strictest upper bound. But to get $\Theta(f(n))$ for the product is not easy in this case. You can check if my answer helps. – Zhuoran He Nov 18 '17 at 22:01
  • @ChaosPredictor is right. We don't need any complicated argument, just do the obvious bound $\log(i)\leq \log(n)$ for all $i$ and get $\prod_{i}\log(i)\leq \log(n)^{n-1}.$ The constant going to zero is then an artifact of $\log(n)^{-1}$ doing the same. – RideTheWavelet Nov 18 '17 at 22:37
  • 1
    I've improved the result, so at the very least, it's no longer trivial. – RideTheWavelet Nov 18 '17 at 23:37
1

Here's my estimation for the product in the $n\rightarrow\infty$ limit. Take the log is the first step. Then

$$\log\left(\prod_{i=2}^n\log i\right)=\sum_{i=2}^n\log\log i.$$

Then using the concavity of $\,\log\log x$, we know (assuming natural log)

$$\sum_{i=2}^n\log\log i\geq\left.\int_{\frac{3}{2}}^{n+\frac{1}{2}}\log\log x\,dx=x\log\log x\,\right|_{\frac{3}{2}}^{n+\frac{1}{2}}-\int_{\frac{3}{2}}^{n+\frac{1}{2}}\frac{dx}{\log x}.$$

The second part gives the logarithmic integral, whose full asymptotic expansion can be found on wikipedia. The error can be estimated to be a constant, because the leading-order error is given by the difference of areas of two "triangles" (approximately) in $[i-\frac{1}{2},i+\frac{1}{2}]$ summed over $i$, i.e.,

$$\sum_{i=2}^\infty\frac{1}{2}|(\log\log x)''|_{x=i}\left(\frac{1}{2}\right)^2\times 2=\frac{1}{4}\sum_{i=2}^\infty\frac{\log i+1}{i^2\log^2i}<\infty$$

is convergent. This means the integral estimator is off by a constant at most. But the logarithmic integral is not an elementary function.

Zhuoran He
  • 3,039