  We specify the frontier of decidability for fragments of the first-order
theory of ordinal multiplication. We give a NEXPTIME lower bound for the
complexity of the existential fragment of $\langle \omega^{\omega^\lambda};
\times, \omega, \omega+1, \omega^2+1 \rangle$ for every ordinal $\lambda$.
Moreover, we prove (by reduction from Hilbert Tenth Problem) that the
$\exists^*\forall^{6}$-fragment of $\langle \omega^{\omega^\lambda}; \times
\rangle$ is undecidable for every ordinal $\lambda$.
