September 25
Matt Frank,
independent scholar
What is the quantifier cost of eliminating Boolean connectives?
We show that every finite Boolean combination of polynomial equations and inequations over $\mathbb C$ is equivalent both to a $\forall\exists$ quantification of a single equation and to an $\exists\forall$ quantification of a single equation, in each case by an explicit construction using one quantifier of each type. Furthermore, neither a purely universal nor a purely existential prefix suffices, and different tradeoffs apply over $\mathbb R$ and $\mathbb Q$. In the language of complex exponentiation, we show that $\mathbb Q$ can be defined with $\exists$ and the conjunction of two exponential equations, but not by $\exists$ and a single such equation. We use these arguments to strengthen Boxall's special case of Zilber's quasiminimality conjecture. The constructions above also show that the full conjecture is equivalent to its subcase about quantified equations rather than quantified formulas.