Using complexity theory to prove things in representation theory

Posted on December 11, 2016

The other day, Evan Shapiro and I figured something interesting out about how complexity theoretic assumptions can help to prove asymptotic statements about the representation theory of symmetric groups! At a high level, we proved that $S_{2^k}$ can't have very small faithful representations over any finite field (given a certain complexity-theoretic assumption). It's a very crude lower bound and the minimal size of a faithful representation of the symmetric group is already known, which makes this proof a bit of a nuclear fly-swatter.

But! I think the proof is interesting because it involves basically nothing about representation theory and just uses a complexity theoretic argument. It's really weird! To me this seems like a fact about geometry of Euclidean space but you can prove it just with complexity theory in a super hands off way. (The argument itself feels a bit like using a cardinality argument to establish that not all reals are computable or something.) Also, the proof generalizes to broader classes of groups to conclude something about their rep theory apparently out of nothing.

Specifically, we proved the following:

Theorem: Fix a sequence of finite fields $F_k$ whose elements can be represented in $\mathrm{poly}(k)$ space and where operations can be done in time $\mathrm{poly}(k)$.

Let $(G_1, S_1), (G_2, S_2), \dots$ be a sequence of groups equipped with generating sets with $|S_k| = \mathrm{poly}(k)$ such that the language $L := \left\{ (1^k, w) : k \in \mathbb{N}, w \text{ a word in the } S_k,\, w =_{G_k} 1 \right\}$ is coNP-hard. Suppose further that each $(G_k, S_k)$ includes into $(G_{k+1}, S_{k+1})$. Let $d_k$ be the dimension of the minimal faithful $F_k$-representation of $G_k$.

Then if $\mathrm{coNP} \not\subset \mathrm{P/poly}$, $d_k$ is not bounded by any polynomial in $k$.

Here's a proof: Suppose $d_k$ is bounded by some polynomial in $k$. Then we can give a $\mathrm{P/poly}$ algorithm for the problem $L$ as follows: Specifically, for the inputs of length $n$, our advice string will be the $d_n$-dimensional faithful representation of $G_n$, encoded as a list of $d_n$-dimensional matrices, one matrix $S_i$ for each generator $s_i$.

Now say our input is $(1^k, w)$. We have $k \leq n$, so $(G_k, S_k)$ includes into $(G_n, S_n)$. Thus we may decide if $w =_{G_k} 1$ by checking if $w =_{G_n} 1$. This we do by applying our representation to $w$. I.e., $w = s_{i_1} \dots s_{i_r}$, so we compute the matrix $W = S_{i_1} \dots S_{i_r}$ which we can do in time, say $d_n^4$. Then, since the representation is faithful, $W$ is the identity matrix iff $w = 1$, so we can just check if $W = I$, which is done in $d_n^2$ time. In total the runtime of our algorithm is roughly $d_n^4 + d_n^2$, which is polynomial in $n$ since by assumption $d_n$ is.

This contradicts the assumption that $\mathrm{NP}$ is not contained in $\mathrm{P / poly}$, so $d_k$ is not bounded by any polynomial in $k$.

You can strengthen this a little bit in a few ways, but I won't talk about that here. To conclude that the dimension of the smallest faithful rep of $S_{2^k}$ isn't bounded by a polynomial in $k$, we can notice that reversible circuits are basically words in a particular generating set of $S_{2^k}$. Namely, the generating set consisting of

• apply CNOT on the first two bits
• apply a Toffoli gate on the first 3 bits
• swap the $i^{\text{th}}$ bit and the $j^{\text{th}}$ bit

The corresponding language $L$ essentially consists of the reversible circuits which compute the identity map. Deciding whether a reversible circuit is the identity is coNP hard, so the word problem $L$ is too and our theorem applies. The conclusion that $S_{2^k}$ doesn't always have small representations then follows.

I think this result is interesting because it shows how complexity theoretic information can be used as a very general tool for proving things about finitely representable mathematical objects. Certain things have to get very complicated or else they could be used to give efficient algorithms for hard problems! This is also interesting because it says that if we had a more exact complexity theory (which talked about specific polynomials or at least leading terms rather than just P, etc) then we could get even more specific information about the representation theory of such groups.

I think it gives an indication as to why separations in complexity theory are so hard to prove: You need to rule out all algorithms, ones that may based on properties of arbitrary mathematical objects, which could plausibly involved in algorithms given the ubiquity of coding problems in seemingly unrelated objects. So, separating classes ends up proving properties of lots of different objects.

A big thanks to Mario Sanchez, German Stefanich, and especially Nic Brody and Patrick Lutz for thinking about related stuff with me. Thanks also to Brandon Rayhaun for pointing out this is a total nuclear flyswatter.