How to find asymptotics?

430 Views Asked by At

The function $\Phi:(0,\infty) \mapsto \mathbb{R}$ is defined as follows. We put $\Phi(x):=1$ if $x \ge 1$. Let the function $\Phi$ satisfy $$\Phi(x)=\int_0^x \Phi\left(\frac t {1-t}\right) \frac {dt} t $$ if $x <1.$ What is the asymptotics of $\Phi(x)$ as $x\downarrow 0$?

1

There are 1 best solutions below

9
On BEST ANSWER

This is the Dickman function (references: 1, 2). Asymptotic analysis is usually done in terms of the function $\rho(u)$ defined by $\rho(u) = \Phi(1/u)$. Xuan (equation 1.6) gives the estimate $$\rho(u) = \exp \left( -u \log u - u \log \log u +u - \frac{u \log \log u}{\log u} +O\left( \frac{u}{\log u} \right) \right).$$ Xuan cites papers of Hua and de Bruijn, neither of which I have easy access to. Wikipedia states without citation that $\rho(n) < 1/n!$ is easy to prove.

I also remember a good discussion of this in Volume 2 of the Art of Computer Programming, by Donald Knuth.