Let \(S_n\) be the symmetric group on \(n\) objects. \(S_n\) has the following properties:

• Every faithful (i.e., injective) representation of \(S_n\) has dimension \(n - 1\).
• If we think of \(S_{2^k}\) as the group of reversible circuits (with generators given by a universal set of gates), the word problem (suitably interpreted) of \(S_{2^k}\) is \(\mathrm{coNP}\) complete.

Taken together, these two facts give a sort of lower bound on a certain kind of read-once program for computing a \(\mathrm{coNP}\) hard problem. Can read-many programs be somehow transformed into representations of the symmetric group in such a way that a small program yields a small dimensional representation? If so, the non-existence of small-dimensional representations would prove that no small program can exist for the word problem of \(S_{2^k}\), thus proving a lower bound for \(\mathrm{coNP}\).