# Simulating Sparse Hamiltonians: help understanding query complexity bounds

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]

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$$.