Symmetric Formulas for Products of Permutations

We study the formula complexity of the word problem ${\mathsf{W}\mathsf{o}\mathsf{r}\mathsf{d}}_{S_n,k}:\{0,1{\}}^{k{n}^2}\to \{0,1\}$: given $n$-by-$n$ permutation matrices $M_1,\dots ,M_k$, compute the $(1,1)$-entry of the matrix product $M_1\cdots M_k$. An important feature of this function is that it is invariant under action of $S_n^{k-1}$ given by $$({\pi }_1,\dots ,{\pi }_{k-1})(M_1,\dots ,M_k)=(M_1{\pi }_1^{-1},{\pi }_1{M}_2{\pi }_2^{-1},\dots ,{\pi }_{k-2}{M}_{k-1}{\pi }_{k-1}^{-1},{\pi }_{k-1}{M}_k)\mathrm{.}$$ This symmetry is also exhibited in the smallest known unbounded fan-in $\{\mathsf{A}\mathsf{N}\mathsf{D},\mathsf{O}\mathsf{R},\mathsf{N}\mathsf{O}\mathsf{T}\}$-formulas for ${\mathsf{W}\mathsf{o}\mathsf{r}\mathsf{d}}_{S_n,k}$, which have size $n^{O(\log k)}$. In this paper we prove a matching $n^{\mathrm{\Omega }(\log k)}$ lower bound for $S_n^{k-1}$-invariant formulas computing ${\mathsf{W}\mathsf{o}\mathsf{r}\mathsf{d}}_{S_n,k}$. This result is motivated by the fact that a similar lower bound for unrestricted (non-invariant) formulas would separate complexity classes ${\mathsf{N}\mathsf{C}}^1$ and $\mathsf{L}\mathsf{o}\mathsf{g}\mathsf{s}\mathsf{p}\mathsf{a}\mathsf{c}\mathsf{e}$. Our more general main theorem gives a nearly tight $n^{d(k^{1\mathrm{/}d}-1)}$ lower bound on the $G^{k-1}$-invariant depth-$d$ $\{\mathsf{M}\mathsf{A}\mathsf{J},\mathsf{A}\mathsf{N}\mathsf{D},\mathsf{O}\mathsf{R},\mathsf{N}\mathsf{O}\mathsf{T}\}$-formula size of ${\mathsf{W}\mathsf{o}\mathsf{r}\mathsf{d}}_{G,k}$ for any finite simple group $G$ whose minimum permutation representation has degree~$n$. We also give nearly tight lower bounds on the $G^{k-1}$-invariant depth-$d$ $\{\mathsf{A}\mathsf{N}\mathsf{D},\mathsf{O}\mathsf{R},\mathsf{N}\mathsf{O}\mathsf{T}\}$-formula size in the case where $G$ is an abelian group.