  The classical zero-one law for first-order logic on random graphs says that
for any first-order sentence $\phi$ in the theory of graphs, as n approaches
infinity, the probability that the random graph G(n, p) satisfies $\phi$
approaches either 0 or 1. It is well known that this law fails to hold for any
formalism that can express the parity quantifier: for certain properties, the
probability that G(n, p) satisfies the property need not converge, and for
others the limit may be strictly between 0 and 1. In this paper, we capture the
limiting behavior of properties definable in first order logic augmented with
the parity quantier, FO[parity], over G(n, p), thus eluding the above hurdles.
Specifically, we establish the following "modular convergence law": For every
FO[parity] sentence $\phi$, there are two rational numbers a_0, a_1, such that
for i in {0,1}, as n approaches infinity, the probability that the random graph
G(2n+i, p) satisfies $\phi$ approaches a_i. Our results also extend
appropriately to first order logic equipped with Mod-q quantiers for prime q.
Our approach is based on multivariate polynomials over finite fields, in
particular, on a new generalization of the Gowers norm. The proof generalizes
the original quantifier elimination approach to the zero-one law, and has
analogies with the Razborov-Smolensky method for lower bounds for AC0 with
parity gates.
