  Automatic structures are structures whose universe and relations can be
represented as regular languages. It follows from the standard closure
properties of regular languages that the first-order theory of an automatic
structure is decidable. While existential quantifiers can be eliminated in
linear time by application of a homomorphism, universal quantifiers are
commonly eliminated via the identity $\forall{x}. \Phi \equiv \neg (\exists{x}.
\neg \Phi)$. If $\Phi$ is represented in the standard way as an NFA, a priori
this approach results in a doubly exponential blow-up. However, the recent
literature has shown that there are classes of automatic structures for which
universal quantifiers can be eliminated by different means without this blow-up
by treating them as first-class citizens and not resorting to double
complementation. While existing lower bounds for some classes of automatic
structures show that a singly exponential blow-up is unavoidable when
eliminating a universal quantifier, it is not known whether there may be better
approaches that avoid the na\"ive doubly exponential blow-up, perhaps at least
in restricted settings.
  In this paper, we answer this question negatively and show that there is a
family of NFA representing automatic relations for which the minimal NFA
recognising the language after eliminating a single universal quantifier is
doubly exponential, and deciding whether this language is empty is
\expspace-complete.
  The techniques underlying our \expspace lower bound further enable us to
establish new lower bounds for some fragments of B\"uchi arithmetic with a
fixed number of quantifier alternations.
