Subspace-Invariant AC${}^0$ Formulas

We consider the action of a linear subspace $U$ of $\{0,1{\}}^n$ on the set of AC${}^0$ formulas with inputs labeled by literals in the set ${X_1,\overline X_1,\dots,X_n,\overline X_n}$,whereanelement$u \in U$ acts on formulas by transposing the $i$th pair of literals for all $i\in [n]$ such that $u_i=1$. A formula is {\em $U$-invariant} if it is fixed by this action. For example, there is a well-known recursive construction of depth $d+1$ formulas of size $O(n\cdot 2^{d{n}^{1\mathrm{/}d}})$ computing the $n$-variable PARITY function; these formulas are easily seen to be $P$-invariant where $P$ is the subspace of even-weight elements of $\{0,1{\}}^n$. In this paper we establish a nearly matching $2^{d(n^{1\mathrm{/}d}-1)}$ lower bound on the $P$-invariant depth $d+1$ formula size of PARITY. Quantitatively this improves the best known $\mathrm{\Omega }(2^{\frac{1}{84}d(n^{1\mathrm{/}d}-1)})$ lower bound for {\em unrestricted} depth $d+1$ formulas, while avoiding the use of the switching lemma. More generally, for any linear subspaces $U\subset V$, we show that if a Boolean function is $U$-invariant and non-constant over $V$, then its $U$-invariant depth $d+1$ formula size is at least $2^{d(m^{1\mathrm{/}d}-1)}$ where $m$ is the minimum Hamming weight of a vector in $U^{\mathrm{\perp }}\setminus V^{\mathrm{\perp }}$.