Find asymptotics of $x(n)$, if $n = x^{x!}$

Question

Find the asymptotic for $x(n)$, if $n = x^{x!}$.

I've tried

1) to take a logarithm:

$x! \log{x} = \log{n}$.

2) to find $n'(x)$, using gamma-function for factorial

$\Gamma(z) = \int_0^\infty t^{z-1}e^{-t}dt$

I'm here now:

$\frac{1}{n}n'(x) = \Gamma'(x+1)\log{x} + \Gamma(x) $

$n'(x) = x^{x!}(\Gamma'(x+1)\log{x} + \Gamma(x)) $

What should I do next? Should I use another way of solving this problem? I'm new to this theme, I will be grateful for any help.

Answer 1

We'll follow the approach suggested by alex.jordan. By taking logs again we get the equation

$$ \log x! + \log\log x = \log\log n. $$

The $\log x!$ term is the dominant term on the left-hand side so it will be the main source of information about $x$. It's clear that $x \to \infty$ as $n \to \infty$, and by rearranging we note that

$$ \log x! = \log\log n - \log\log x < \log\log n $$

for $x$ large enough. Now

$$ \log x! = x\log x + O(x) > \frac{1}{2} x\log x $$

for $x$ large enough, so

$$ x \log x < 2 \log\log n $$

for $x$ large enough. Taking the Lambert $W$ function of both sides yields

$$ \log x < W(2\log\log n) $$

since $W(x\log x) = \log x$, whence

$$ x < e^{W(2\log\log n)} = \frac{2\log\log n}{W(2\log\log n)} = O\left(\frac{\log\log n}{\log\log\log n}\right). $$

To obtain the last bound we used the fact that

$$ W(z) = \log z + O(\log\log z) $$

as derived in this answer. We'll now bootstrap this crude estimate into the previous estimates to obtain a sharper one. The approximation $\log x! = x\log x + O(x)$ becomes

$$ \log x! = x\log x + O\left(\frac{\log\log n}{\log\log\log n}\right), $$

which allows us to rewrite the equation

$$ \log x! = \log\log n - \log\log x $$

as

$$ x\log x + O\left(\frac{\log\log n}{\log\log\log n}\right) = \log\log n + O(\log\log\log\log n). $$

or just

$$ x\log x = \log\log n + O\left(\frac{\log\log n}{\log\log\log n}\right). $$

We then have

$$ \begin{align} x &= \frac{\log\log n + O\left(\frac{\log\log n}{\log\log\log n}\right)}{W\left[\log\log n + O\left(\frac{\log\log n}{\log\log\log n}\right)\right]} \\ &= \frac{\log\log n + O\left(\frac{\log\log n}{\log\log\log n}\right)}{\log\left[\log\log n + O\left(\frac{\log\log n}{\log\log\log n}\right)\right] + O(\log\log\log\log n)} \\ &= \frac{\log\log n + O\left(\frac{\log\log n}{\log\log\log n}\right)}{\log\log\log n + \log\left[1+O\left(\frac{1}{\log\log\log n}\right)\right] + O(\log\log\log\log n)} \\ &= \frac{\log\log n + O\left(\frac{\log\log n}{\log\log\log n}\right)}{\log\log\log n + O(\log\log\log\log n)} \\ &= \frac{\frac{\log\log n}{\log\log\log n} + O\left(\frac{\log\log n}{(\log\log\log n)^2}\right)}{1 + O\left(\frac{\log\log\log\log n}{\log\log\log n}\right)} \\ &= \left[\frac{\log\log n}{\log\log\log n} + O\left(\frac{\log\log n}{(\log\log\log n)^2}\right)\right]\left[1+O\left(\frac{\log\log\log\log n}{\log\log\log n}\right)\right] \\ &= \frac{\log\log n}{\log\log\log n} + O\left(\frac{(\log\log n)(\log\log\log\log n)}{(\log\log\log n)^2}\right). \end{align} $$

This last part was pretty brutal but at least we wound up with a rigorous error bound. In summary,

$$ x = \frac{\log\log n}{\log\log\log n} + O\left(\frac{(\log\log n)(\log\log\log\log n)}{(\log\log\log n)^2}\right) $$ as $n \to \infty$.

If we desired, we could bootstrap again with this estimate. Before doing so, let us introduce the notation

$$ \begin{align} &\log\log n = L_2(n), \\ &\log\log\log n = L_3(n), \\ &\log\log\log\log n = L_4(n), \end{align} $$

so that the last estimate can be written

$$ x = \frac{L_2(n)}{L_3(n)} + O\left(\frac{L_2(n)L_4(n)}{L_3(n)^2}\right). $$

We then find that

$$ \begin{align} \log x! &= x \log x - x + O(\log x) \\ &= x \log x - \frac{L_2(n)}{L_3(n)} + O\left(\frac{L_2(n)L_4(n)}{L_3(n)^2}\right), \end{align} $$

so that $\log x! = \log\log n - \log\log x$ becomes

$$ x\log x = L_2(n) - \frac{L_2(n)}{L_3(n)} + O\left(\frac{L_2(n)L_4(n)}{L_3(n)^2}\right), $$

yielding

$$ x = \frac{L_2(n) - \frac{L_2(n)}{L_3(n)} + O\left(\frac{L_2(n)L_4(n)}{L_3(n)^2}\right)}{W\left[L_2(n) - \frac{L_2(n)}{L_3(n)} + O\left(\frac{L_2(n)L_4(n)}{L_3(n)^2}\right)\right]}. $$

We can then use $W(z) = \log z - L_2(z) + O\left(\frac{L_2(z)}{\log z}\right)$, which also follows from this other answer, to obtain the final result of

$$ x = \frac{L_2(n)}{L_3(n)} + \frac{L_2(n)(1-L_4(n))}{L_3(n)^2} + O\left(\frac{L_2(n)L_4(n)}{L_3(n)^3}\right). $$ as $n \to \infty$.

Answer 2

This matches Antonio Vargas's first answer, but the derivation is a bit shorter. $$ \begin{align} n&=x^{x!}\\[6pt] \log(n) &=x!\log(x)\\ \log(\log(n)) &=\log(\log(x))+x\log(x)-x+\frac12\log(2\pi x)\\ &=x\log(x)\left(1-\frac1{\log(x)}+\frac1{2x}+\frac{\log(\log(x))}{x\log(x)}+\frac12\frac{\log(2\pi)}{x\log(x)}\right)\\ \log(\log(\log(n))) &=\log(x)+\log(\log(x))-\frac1{\log(x)}+O\left(\frac1{\log(x)^2}\right)\\ &=\log(x)\left(1+\frac{\log(\log(x))}{\log(x)}-\frac1{\log(x)^2}+O\left(\frac1{\log(x)^3}\right)\right)\\ \frac{\log(\log(n))}{\log(\log(\log(n)))} &=x\left(1-\frac{\log(\log(x))}{\log(x)}-\frac1{\log(x)}+O\left(\frac{\log(\log(x))}{\log(x)}\right)^2\right) \end{align} $$ Therefore, since $\log(x)\sim\log(\log(\log(n)))$, we get $$ x=\frac{\log(\log(n))}{\log(\log(\log(n)))}\left(1+O\left(\frac{\log(\log(\log(\log(n))))}{\log(\log(\log(n)))}\right)\right) $$ Note that to get $\frac{\log(\log(\log(\log(n))))}{\log(\log(\log(n)))}\sim\frac1{10}$, we need $\log(\log(\log(n)))\sim36$; that is, $n$ needs to be huge.