A model-theoretic characterization of constant-depth arithmetic circuits

We study the class ${\mathrm{\#}\text{AC}}^0$ of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fan-in addition and multiplication gates. No model-theoretic characterization for arithmetic circuit classes is known so far. Inspired by Immerman's characterization of the Boolean circuit class ${\text{AC}}^0$, we remedy this situation and develop such a characterization of ${\mathrm{\#}\text{AC}}^0$. Our characterization can be interpreted as follows: Functions in ${\mathrm{\#}\text{AC}}^0$ are exactly those functions counting winning strategies in first-order model checking games. A consequence of our results is a new model-theoretic characterization of ${\text{TC}}^0$, the class of languages accepted by constant-depth polynomial-size majority circuits.