
\begin{problem}
The equation $x = y^y$ comes up fairly often.  Frustratingly, there is
no closed form expression for $y$ in terms of $x$.  However, we can at
least describe $y$'s rate of growth in terms of $x$:
%
\[
y = \Theta\left(\frac{\ln x}{\ln \ln x}\right)
\]
%
This is good enough for many problems.  Show that $y = \Omega(\ln x /
\ln \ln x)$ by proving that if $x = y^y$, then $y \geq \ln x / \ln \ln
x$ for all sufficiently large $x$.

\bigskip

\noindent \textbf{Hints.}  This problem requires ninja-level ability
with logarithms, which is a crucial skill for battling the hairy
expressions that come up in the analysis of complex systems.  Remember
the basic rules:
%
\begin{align}
\ln AB & = \ln A + \ln B \label{eq:product}\\
\ln A/B & = \ln A - \ln B \label{eq:quotient}\\
\ln A^B & = B \ln A \label{eq:exponent}
\end{align}
%
One more tip: when you encounter a nasty expression of the form $u^v$,
try rewriting it with the identity:
%
\begin{equation}
u^v = e^{v \ln u} \label{eq:star}
\end{equation}
%
This puts all the mess in one place, the exponent, which allows terms
to be combined and cancelled more effectively.
\end{problem}

\solution{
Note that:
%
\begin{align*}
\left(\frac{\ln x}{\ln \ln x}\right)^{\ln x / \ln ln x}
	& = e^{\displaystyle (\ln x / \ln \ln x) \cdot 
               \ln(\ln x / \ln \ln x)} & \text{by~\eqref{eq:star}} \\
	& = e^{\displaystyle (\ln x / \ln \ln x) \cdot
               (\ln \ln x - \ln \ln \ln x)} & \text{by~\eqref{eq:quotient}} \\
	& = e^{\displaystyle (\ln x) \cdot (1 - \ln \ln \ln x / \ln \ln x)} & \text{algebra} \\
        & < e^{\displaystyle \ln x} & \text{$\ln \ln \ln x < \ln \ln x$ for all large $x$} \\
        & = x & \text{definition of $\ln x$}
\end{align*}
%
Thus if $y^y = x$, then $y$ must be greater than $\ln x / \ln \ln x$
for all sufficiently large $x$.  This implies that $y = \Omega(\ln x /
\ln \ln x$).}
