Lower Bounds for Symmetric Circuits for the Determinant^††thanks: Research funded by EPSRC grant EP/S03238X/1. A preliminary version of this paper appeared as [12]

Let $\text{{Sym}}_{A}$ and $\text{{Alt}}_{A}$ denote the symmetric group and alternating group on the set $A$. We write $\text{{Sym}}_{n}$ and $\text{{Alt}}_{n}$ to abbreviate $\text{{Sym}}_{[n]}$ and $\text{{Alt}}_{[n]}$, respectively. Let $\{\operatorname{id}\}$ denote the trivial group. For groups $G$ and $H$ we write $H\leq G$ to denote that $H$ is a subgroup of $G$. The sign of a permutation $\sigma\in\text{{Sym}}_{A}$ is defined so that if $\sigma$ is even $\text{sgn}(\sigma)=1$ and otherwise $\text{sgn}(\sigma)=-1$.

Let $G$ be a group acting on a set $X$. We denote this as a left action, i.e. $\sigma x$ for $\sigma\in G$, $x\in X$. The action extends in a natural way to powers of $X$. So, for $(x,y)\in X\times X$, $\sigma(x,y)=(\sigma x,\sigma y)$. It also extends to the powerset of $X$ and functions on $X$ as follows. The action of $G$ on $\mathcal{P}(X)$ is defined for $\sigma\in G$ and $S\in\mathcal{P}(X)$ by $\sigma S=\{\sigma x\mid x\in S\}$. For $Y$ any set, the action of $G$ on $Y^{X}$ is defined for $\sigma\in G$ and $f\in Y^{X}$ by $(\sigma f)(x)=f(\sigma x)$ for all $x\in X$. We refer to all of these as the natural action of $G$ on the relevant set.

A set $X$ with the action of group $G$ on it is called a $G$-set. We do not distinguish notationally between a $G$-set $X$ and the underlying set of elements. Thus, we can say that if $X$ is a $G$-set, the collection of functions $Y^{X}$ is also a $G$-set with the natural action.

Let $X=\prod_{i\in I}X_{i}$ and for each $i\in I$ let $G_{i}$ be a group acting on $X_{i}$. The action of the direct product $G:=\prod_{i\in I}G_{i}$ on $X$ is defined for $x=(x_{i})_{i\in I}\in X$ and $\sigma=(\sigma_{i})_{i\in I}\in G$ by $\sigma x=(\sigma_{i}x_{i})_{i\in I}$. If instead $X=\biguplus_{i\in I}X_{i}$ then the action of $G$ on $X$ is defined for $x\in X$ and $\sigma=(\sigma_{i})_{i\in I}\in G$ such that if $x\in X_{i}$ then $\sigma x=\sigma_{i}x$. Again, we refer to either of these as the natural action of $G$ on $X$.

Let $X$ be a $G$-set. Let $S\subseteq X$. Let $\text{{Stab}}_{G}(S):=\{\sigma\in G\mid\forall x\in S\,\,\sigma x=x\}$ denote the pointwise stabilizer of $S$. Let $\text{{SetStab}}_{G}(S):=\{\sigma\in G\mid\sigma(S)=S\}$ denote the setwise stabilizer of $S$. If $S=\{x\}$ is a singleton we omit set braces and write $\text{{Stab}}_{G}(x)$. Note that $\text{{SetStab}}_{G}(S)$ is the pointwise stabilizer of $\{S\}$ in the $G$-set $\mathcal{P}(X)$. For $x\in X$ let $\text{{Orb}}_{G}(x):=\{\sigma(x)\mid\sigma\in G\}$ denote the orbit of $x$. In all cases, we omit the subscript $G$ where it is clear from context.

Let $A$ and $B$ be finite non-empty sets. We identify matrices with rows indexed by $A$ and columns by $B$ and entries from some set $X$ with functions of the form $M:A\times B\rightarrow X$. So for $a\in A$, $b\in B$, $M_{ab}=M(a,b)$. We also denote $M$ by $(M_{ab})_{a\in A,b\in B}$, or just $(M_{ab})$ when the index sets are clear from context.

Let $R$ be a commutative ring and $M:A\times B\rightarrow R$ be a matrix with $|A|=|B|$. The permanent of $M$ over $R$ is $\text{perm}_{R}(M)=\sum_{\sigma\in\mathrm{Bij}(A,B)}\prod_{a\in A}M_{a\sigma(a)}$. Suppose $A=B$. The determinant of $M$ over $R$ is $\det_{R}(M)=\sum_{\sigma\in\text{{Sym}}_{A}}\text{sgn}(\sigma)\prod_{a\in A}M_{a\sigma(a)}$. The trace of $M$ over $R$ is $\operatorname{Tr}_{R}(M)=\sum_{a\in A}M_{aa}$. We omit reference to the ring when it is obvious from context. When $R$ is a field, we write $\text{{rk}}(M)$ to denote the rank of the matrix $M$.

We always use $\mathbb{F}$ to denote a field and $\text{char}(\mathbb{F})$ to denote the characteristic of $\mathbb{F}$. For any prime power $q$ we write $\mathbb{F}_{q}$ for the finite field of order $q$. We are often interested in polynomials and circuits defined over a set of variables $X$ with a natural matrix structure, i.e. $X=\{x_{ab}:a\in A,b\in B\}$. We identify $X$ with this matrix. We also identify any function of the form $f:X\rightarrow Y$ with the $A\times B$ matrix with entries in $Y$ defined by replacing each $x_{ab}$ with $f(x_{ab})$.

Given a graph $\Gamma=(V,E)$, the adjacency matrix $A_{\Gamma}$ of $\Gamma$ is the $V\times V$ $\{0,1\}$-matrix with $A_{\Gamma}(u,v)=1$ if, and only if, $\{u,v\}\in E$. If $\Gamma$ is bipartite, with bipartition $V=U\cup W$, then the biadjacency matrix $B_{\Gamma}$ of $\Gamma$ is the $U\times W$ $\{0,1\}$-matrix with $B_{\Gamma}(u,v)=1$ if, and only if, $\{u,v\}\in E$. For a set $U\subseteq V$ we write $\Gamma[U]$ to denote the subgraph induced by $U$.

A $k$-factor of a graph $\Gamma$ is a spanning $k$-regular subgraph. A perfect matching is a $1$-factor. It is well known that for a bipartite graph $\Gamma$, $\text{perm}(B_{\Gamma})$ over any field of characteristic zero counts the number of perfect matchings in $\Gamma$ [16] and for prime $p$, $\text{perm}_{\mathbb{F}}(B_{\Gamma})$ for a field $\mathbb{F}$ of characteristic $p$ counts the number of perfect matchings in $\Gamma$ modulo $p$. For bipartite $\Gamma$, $A_{\Gamma}$ is a block anti-diagonal matrix with two blocks corresponding to $B_{\Gamma}$ and $B_{\Gamma}^{T}$, and so $\text{perm}(A_{\Gamma})=\text{perm}(B_{\Gamma})^{2}$.

Let $\Gamma=(V,E)$ be a graph. For $S\subseteq V$ let $N^{+}(S):=\{v\in V\setminus S\mid\exists s\in S,\,\,(v,s)\in E\}$. We say $\Gamma$ is an $\alpha$-expander for $\alpha\in[0,1]$ if for every $S\subseteq V$ of size at most $|V|/2$ we have $|N^{+}(S)|\geq\alpha|S|$. For an introduction to expander graphs see [19]. A set $S$ of vertices in a graph $\Gamma$ is a balanced separator if no connected component of $\Gamma\setminus S$ contains more than half the vertices of $\Gamma$. It is easy to see that for any $\alpha$ there is a constant $\tau$ such that if $\Gamma$ is an $\alpha$-expander then $\Gamma$ has no balanced separator of size less than $\tau|V|$.

The tree width of a graph is a well-known graph parameter which can be characterized in terms of the cops and robbers game [25]. This game is played on a graph $\Gamma=(V,E)$, with one player controlling the single robber and another a team of $k$ cops. The cops and robbers both sit on nodes in the graph. At the start of a round the cops are sitting on nodes $X\subset V$ and the round begins with the cop player announcing he intends to move cops from $X^{\prime}\subseteq X$ to occupy the nodes $Y$. The robber player must respond with a path from the robbers current location that does not intersect $X\setminus X^{\prime}$. At the end of the round the cops and robber are moved to their new locations, and if any cop is on the same node as the robber the cops win. The characterization is as follows.

We give a general definition of a circuit that incorporates both Boolean and arithmetic circuits.

Let $C$ be circuit that is the labelling of a directed graph $(D,W)$, where $W\subset D\times D$ with values $K$. We call the elements of $D$ gates, and the elements of $W$ wires. We call the gates with in-degree $0$ input gates and gates with out-degree $0$ output gates. We call those input gates labelled by elements of $K$ constant gates. We call those gates that are not input gates internal gates. For $g,h\in D$ we say that $h$ is a child of $g$ if $(h,g)\in W$. We write $\text{child}(g)$ to denote the set of children of $g$. We write $C_{g}$ to denote the sub-circuit of $C$ rooted at $g$, i.e the sub-circuit induced by those gates with a directed path to $g$. Unless otherwise stated we always assume a circuit has exactly one output gate.

If $K$ is a field $\mathbb{F}$, and $\mathbb{B}$ is the set $\{+,\times\}$, we have an arithmetic circuit over $\mathbb{F}$. If $K=\{0,1\}$, and $\mathbb{B}$ is a collection of Boolean functions, we have a Boolean circuit over the basis $\mathbb{B}$. We define two bases here. The first is the standard basis $\mathbb{B}_{\text{std}}$ containing the functions $\land$, $\lor$, and $\neg$. The second is the threshold basis $\mathbb{B}_{t}$ which is the union of $\mathbb{B}_{\text{std}}$ and $\{t_{\geq k}:k\in\mathbb{N}\}$, where for each $k\in\mathbb{N}$, $t_{\geq k}$ is defined for a string $\vec{x}\in\{0,1\}^{*}$ so that $t_{\geq k}(\vec{x})=1$ if, and only if, the number of $1$s in $\vec{x}$ at least $k$. We call a circuit defined over this basis a threshold circuit. Another useful Boolean function is $t_{=k}$, which is defined by $t_{=k}(x)=t_{\leq k}(x)\land\neg t_{\leq k+1}(x)$. We do not explicitly include it in the basis as it is easily defined in $\mathbb{B}_{t}$.

In general, we require that a basis contain only functions that are invariant under all permutations of their inputs. That is, if $f\in\mathbb{B}$ is such that $f:K^{n}\rightarrow K$ for some $n\in\mathbb{N}$ then for all $\sigma\in\text{{Sym}}_{n}$ and $M\in K^{n}$ we have $f(M\circ\sigma)=f(M)$. We call such a function $f$ fully symmetric. The arithmetic functions $+$ and $\times$ and all of the Boolean functions in $\mathbb{B}_{t}$ and $\mathbb{B}_{\text{std}}$ are fully symmetric. Let $C$ be a circuit defined over such a basis with variables $X$ and values $K$. We evaluate $C$ for an assignment $M\in K^{X}$ by evaluating each gate labelled by some $x\in X$ to $M(x)$ and each gate labelled by some $k\in K$ to $k$, and then recursively evaluating each gate $g$ according to its corresponding basis element. That is $g$ gets the value obtained by applying the function labelling $g$ to the set of values of $\text{child}(g)$. We write $C[M](g)$ to denote the value of the gate $g$ and $C[M]$ to denote the value of the output gate. We say that $C$ computes the function $M\mapsto C[M]$.

It is conventional to consider an arithmetic circuit $C$ over $\mathbb{F}$ with variables $X$ to be computing a polynomial in $\mathbb{F}[X]$, rather than a function $\mathbb{F}^{X}\rightarrow\mathbb{F}$. This polynomial is defined via a similar recursive evaluation, except that now each gate labelled by a variable evaluates to the corresponding formal variable, and we treat addition and multiplication as ring operations in $\mathbb{F}[X]$. Each gate then evaluates to some polynomial in $\mathbb{F}[X]$. The polynomial computed by $C$ is the value of the output gate.

For more details on arithmetic circuits see [26] and for Boolean circuits see [27].

We are interested in functions of type $K^{X}\rightarrow K$ with some group $G$ acting on $X$, which then induces an action on $K^{X}$. We think of elements of $K^{X}$ as “generalized structures”, and define notions of homomorphism and isomorphism below. We first consider some examples. Note that whenever $H$ is a subgroup of $G$, then any $G$-symmetric function is also $H$-symmetric. In particular every function is $\{\operatorname{id}\}$-symmetric.

Let $G$ and $H$ be groups. A homomorphism from the $G$-set $X$ to $H$-set $Y$ is a pair of functions $(f,\phi)$ where $f:X\rightarrow Y$ is a function and $\phi:G\rightarrow H$ is a group homomorphism such that for each $x\in X$ and $\pi\in G$, $f(\pi x)=\phi(\pi)f(x)$. We say $(f,\phi)$ is an isomorphism if both $f$ and $\phi$ are bijective. We abuse terminology and refer to a bijection $f:X\rightarrow Y$ as an isomorphism if there exists $\phi:G\rightarrow H$ such that $(f,\phi)$ is an isomorphism.

Let $M:X\rightarrow K$ with $X$ a $G$-set and let $N:Y\rightarrow K$ with $Y$ an $H$-set. A homomorphism from $(M,G)$ to $(N,H)$ is a homomorphism $(f,\phi):(X,G)\rightarrow(Y,H)$ such that $N\circ f=M$. It is an isomorphism from $(M,G)$ to $(N,H)$ if both $f$ and $\phi$ are bijective. We omit mention of the groups and refer just to a homomorphisms or isomorphisms from $M$ to $N$ when the groups are clear from context (see Section 4.1.

Let $G$ be a group acting on $X$ and $F:K^{X}\rightarrow L$. We are usually interested in such functions up to isomorphism. Let $M:Y\rightarrow K$ and $H$ be a group acting on $Y$ such that $(X,G)$ and $(Y,H)$ are isomorphic. Then we abuse notation and sometimes write $F(M)$ to denote $F(M\circ f)$ for some isomorphism $f:X\rightarrow Y$.

We next define the notion of a symmetric circuit as it appears in [11]. These circuits take as input functions of the form $M:X\rightarrow K$, where $X$ is a $G$-set, and are symmetric in the sense that the computation itself, not just the value of the output, remains unchanged under the action of $G$. We first need to formalize what it means for a permutation in $G$ to act on the gates of a circuit, and for this we define the notion of a circuit automorphism extending a permutation.

We say that a circuit $C$ with variables $X$ is rigid if for every permutation $\sigma\in\text{{Sym}}(X)$ there is at most one automorphism of $C$ extending $\sigma$. The argument used to prove [10, Lemma 5.5] suffices to show that any symmetric circuit may be transformed into an equivalent rigid one in time polynomial in the size of the circuit. As such, when proving lower bounds we often assume the circuit is rigid without a loss of generality.

We are now ready to define the key notion of a symmetric circuit.

The following can be shown via a straightforward induction.

We now introduce our generalization of Hella’s bijection game. The generalization is in two directions. The first is that we allow the game to be played on arbitrary indexed functions, rather than just graphs or relational structures. The second is that Duplicator is restricted on which bijections it is allowed to play. Specifically, the bijection must be obtained from a fixed initial bijection by composition with a permutation from a fixed group. We recover the usual requirement in the bijection game by just taking this group to be the full symmetric group.

We begin by introducing the key notions of indexed set and function.

All of the structures discussed so far may be identified with indexed functions. For example, we can identify a (directed) graph $(V,E^{2})$ with the indexed function $(E:V^{2}\rightarrow\{0,1\},V,\text{{Sym}}_{V})$. Similarly, a bipartitioned graph $(V,U,E)$ can be identified with the indexed function $(E:U\times V\rightarrow\{0,1\},U\uplus V,\text{{Sym}}_{U}\times\text{{Sym}}_{V})$.

We now want to generalize the notion of isomorphism between structures to an equivalence notion on indexed functions, which is suitably restricted by the permutation group $G$. Suppose $A$ and $B$ are index sets and $f:A\rightarrow B$ is a bijection. For a group $G\leq\text{{Sym}}_{A}$, let $H\leq\text{{Sym}}_{B}$ be the group of permutations $\{f\pi f^{-1}\mid\pi\in G\}$. Let $\mathcal{M}=(M:X\rightarrow K,A,G)$ and $\mathcal{N}=(M:Y\rightarrow K,B,H)$ be a pair of indexed functions and $\hat{f}:X\rightarrow Y$ be a bijection which lifts the bijection $f$ in the sense that $\hat{f}(\pi x)=(f\pi f^{-1})\hat{f}(x)$ for all $\pi\in G$. We say that the indexed functions $\mathcal{M}$ and $\mathcal{N}$ are $(f,\hat{f})$-isomorophic, if there is a permutation $\pi\in H$ such that for all $x\in X$, $M(x)=N(\pi\hat{f}(x))$.

In particular, for a pair of directed graphs $(V_{1},E_{1})$ and $(V_{2},E_{2})$, if $f$ is any bijection between $V_{1}$ and $V_{2}$, and $\hat{f}$ is its natural lift to a bijection between $V_{1}^{2}$ and $V_{2}^{2}$ (i.e. $\hat{f}(u,v)=(f(u),f(v))$, then the pair of indexed functions $(E_{1}:V_{1}^{2}\rightarrow\{0,1\},V_{1},\text{{Sym}}_{V_{1}})$ and $(E_{2}:V_{2}^{2}\rightarrow\{0,1\},V_{2},\text{{Sym}}_{V_{2}})$ are $(f,\hat{f})$-isomorphic if, and only if, $(V_{1},E_{1})$ and $(V_{2},E_{2})$ are isomorphic in the usual sense. Similar statements hold for bipartitioned graphs and other relational structures. As a further example, we can identify $n\times n$ matrices over a field $\mathbb{F}$ with structured functions of the form $(M:[n]\times[n]\rightarrow\mathbb{F},[n]\uplus[n],G)$, for some group $G$. Unlike the case of structures considered above, there is not a canonical choice of $G$, and it depends on what invariants of the matrix we wish to take into account. For example, if $G=\text{{Sym}}_{n}$ then isomorphism corresponds to equivalence under simultaneous row and column permutations and if $G=\text{{Sym}}_{n}\times\text{{Sym}}_{n}$ then isomorphism corresponds to equivalence under separate row and column permutations.

Our notion of isomorphism is parameterized by a fixed bijection between the index sets $A$ and $B$ and its lift to the indexed sets $X$ and $Y$. To simplify notation, we often simply identify the sets $A$ and $B$, and the sets $X$ and $Y$, so that the base bijection can be taken to be the identity. This is akin to fixing the universe of any $n$ vertex graph to be the set $[n]$, so that isomorphisms can be identified with permutations of $[n]$.

In order to define the bijection game, we need a notion of partial isomorphism on the set of pebbled positions in an indexed function. In order to introduce this, we first define the notion of a lift.

Thus, $X_{S}$ is those elements of $X$ that are fixed by any permutation that fixes $S$ pointwise. The following is now an easy observation.

We define the notion of partial isomorphism specifically for two indexed functions over the same index set. It can easily be generalized to the case with distinct index sets with a fixed bijection between them.

It is easily seen that this gives the usual notion of partial isomorphism when the indexed functions are graphs or other relational structures. With this, we are ready to define the bijection game on indexed functions. The game is played by two players Spoiler and Duplicator on a pair of indexed functions, using a set of pebbles. During the course of the game, the pebbles are placed on elements of the indexing sets. Where it does not cause confusion, we do not distinguish notationally between the pebbles and the elements on which they are placed.

In the sequel, we abbreviate “$k$-pebble $G$-bijection game” to $(G,k)$-bijection game.

We recover the ordinary bijection game on graphs by taking $A=[n]$, $X=[n]^{2}$ and $G=\text{{Sym}}_{n}$. It is clear in this case that if $\mathcal{M}$ and $\mathcal{N}$ are isomorphic graphs, then Duplicator has a winning strategy by choosing a fixed isomorphism $\pi$ between them and playing it at every move. However, if $G\leq\text{{Sym}}_{A}$ is a more restricted group that does not contain an isomorphism between $\mathcal{M}$ and $\mathcal{N}$, a Duplicator winning strategy is not guaranteed even when $\mathcal{M}$ and $\mathcal{N}$ are isomorphic as graphs. This is just the case in the application in Section 5.

Lower bounds for symmetric circuits rely on the notion of a support. We define the notion formally below but it is worthwhile developing an intuition. If we have a $G$-symmetric circuit $C$ then the function computed by $C$ is invariant under permutations in $G$ on the input. This is not the case for individual gates $g$ in $C$ other than the output gate: applying a permutation $\pi\in G$ to the inputs of the circuit might yield a different function at $g$. But, by the symmetry condition, there is then another gate $\pi g$ which computes this other function. If the circuit is small, the orbit of $g$ is small and thus the stabilizer group of $g$ is large. That is, for many $\pi$ we have $g=\pi g$. What the support theorem tells us is that in this case, there is a small subset $S$ (which we call a support of $g$) of the permutation domain of $G$ such that the function computed at $g$ only depends on $S$. This is in the sense that permutations that only move elements of the permutation domain outside of $S$ do not change the function computed at $g$. This support theorem can be proved as long as the group $G$ is, in a sense, large enough. We now define the notion of a support formally and prove the relationship between support size and orbit size in Section 4.3.

We extend this notion to indexed sets, where the support is now a subset of the indices. A key example is the action of $\text{{Sym}}_{n}$ on the set $X=[n]\times[n]$ or on the collection of matrices $M:X\rightarrow\{0,1\}$.

Note that $S$ is a support of $x$ just in case $x$ is in the lift of $S$, in the sense of Definition 4.2.

Let $(X,A,G)$ be an indexed set. We write $\text{{max-orbit}}(X)$ to denote the maximum size of the orbit of $x$ over all $x\in X$. For $x\in X$ we write $\text{{min-supp}}(x)$ to denote the minimum size of a support of $x$ and $\text{{max-supp}}(X)$ to denote the maximum of $\text{{min-supp}}(x)$ over all $x\in X$.

We now specialise our discussion to circuits. Let $C$ be a rigid $G$-symmetric circuit with gate set $D$, where $G\leq\text{{Sym}}_{n}$ for some natural number $n$. Then $(D,[n],G)$ is an indexed set. In this way we can speak of the supports and orbits of a gate. We abuse notation slightly and write $\text{{max-orbit}}(C)$ and $\text{{max-supp}}(C)$ to denote $\text{{max-orbit}}(D)$ and $\text{{max-supp}}(D)$, respectively.

We are now ready to prove the first major theorem of this section. This links the number of pebbles in a bijection game with the size of the supports. Structures in which Duplicator has a $2k$-pebble winning strategy cannot be distinguished by symmetric circuits with supports limited to size $k$. The statement of the theorem and argument used generalize that in [7].