Multilinear-NC1 ≠ multilinear-NC2

An arithmetic circuit or formula is multilinear if the polynomial computed at each of its wires is multilinear. We give an explicit example for a polynomial f(x₁,..., x_n), with coefficients in {0,1}, such that over any field: (1) f can be computed by a polynomial-size multilinear circuit of depth O(log² n). (2) Any multilinear formula for f is of size n^{Ω(log n)}. This gives a super-polynomial gap between multilinear circuit and formula size, and separates multilinear NC₁ circuits from multilinear NC₂ circuits.