= Solution
Let $L=\log\log N$, $h=L^{-1/2}$, and let $F_N$ be the <cumulative distribution function> of $(\omega-L)/\sqrt L$. Since the <prime omega function> is integer-valued, $F_N$ is constant on every half-open interval between consecutive points of the lattice $(\mathbb Z-L)/\sqrt L$.
Choose $k=\lfloor L\rfloor$ and put $\alpha=(k-L)/\sqrt L$, $\beta=(k+1-L)/\sqrt L$. Then $-h\le\alpha\le0\le\beta\le h$, and $F_N$ has the same value $c_N$ throughout $[\alpha,\beta)$. The <standard normal distribution function> $\Phi$ is continuous, so the definition of the <Kolmogorov distance> gives
$$
E(N)\ge|c_N-\Phi(\alpha)|,\qquad E(N)\ge|c_N-\Phi(\beta)|,
$$
where the second inequality follows by taking a limit from below at $\beta$. The <triangle inequality> therefore yields
$$
2E(N)\ge\Phi(\beta)-\Phi(\alpha)=\int_\alpha^\beta\frac{e^{-t^2/2}}{\sqrt{2\pi}}\,dt\ge\frac{h e^{-h^2/2}}{\sqrt{2\pi}}.
$$
Thus \b[the integer lattice forces the lower bound]:
$$
\boxed{E(N)\ge\frac{e^{-1/(2\log\log N)}}{2\sqrt{2\pi\log\log N}}\gg\frac1{\sqrt{\log\log N}}.}
$$
This <lattice obstruction to normal approximation> does not require a quantitative <Erdős-Kac theorem>; it follows directly from discreteness and the positive <standard normal density> near zero.
Back to article page
