Simulating Sparse Hamiltonians: help understanding query complexity bounds

Question

tl;dr: How can I show that $e^k/k^k$ is less than $\epsilon^2/2$ when $k=\Omega\left(\frac{\log(1/\epsilon)}{\log \log(1/\epsilon)}\right)$, where $k,\epsilon\in \mathbb{R}$ and > 0?

Context: Berry et al. show a $d$-sparse Hamiltonian can be approximately simulated for time $t$ with precision $\epsilon$ using $O\left(\frac{\log(\tau/\epsilon)}{\log \log(\tau/\epsilon )}\right)$ queries to an oracle, where $\tau=d^2\|H\|_{\max}t$ (1). The authors prove a related query complexity in Appendix 2, Lemma 3.5 which hinges on the argument $e^k/k^k$ is less than $\epsilon^2/2$ when $k=\Omega\left(\frac{\log(1/\epsilon)}{\log \log(1/\epsilon)}\right)$, where $k,\epsilon\in \mathbb{R}$ and > 0. I am not sure how to show this is the case and would greatly appreciate any insight!

arXiv:1312.1414 [quant-ph]

Answer 1

Here's the argument essentially given in Robin Kothari's thesis (p. 29 in particular).

From Stirling's approximation, we have $e^k/k^k \sim 1/k!$, or equivalently, $\log(k!) \sim k\log k - k$. Set $k = c\left(\frac{\log(1/\epsilon)}{\log\log(1/\epsilon)}\right)$ for some constant $c$. Then

\begin{align*} k\log k -k &= c\left(\frac{\log(1/\epsilon)}{\log\log(1/\epsilon)}\right) \left[\log\left(c\left(\frac{\log(1/\epsilon)}{\log\log(1/\epsilon)}\right)\right) - 1 \right]\\ &= c\left(\frac{\log(1/\epsilon)}{\log\log(1/\epsilon)}\right) \left( \log c + \log\log(1/\epsilon) - \log\log\log(1/\epsilon) - 1 \right)\\ &= \frac{c(\log c - 1)\log(1/\epsilon)}{\log\log(1/\epsilon)} + c\log(1/\epsilon) - \frac{c\log(1/\epsilon) \log\log\log(1/\epsilon)}{\log\log(1/\epsilon)}, \end{align*} which is asymptotically dominated by the $c\log(1/\epsilon)$ term. Thus $\log(k!) \sim c\log(1/\epsilon)$, and in particular we can choose $c$ large enough such that $\log(k!) \geq 2\log(\sqrt{2}/\epsilon)$. This implies that $1/k! \leq \epsilon^2/2$.