Izaak Meckler

Tighter representation theory lower bounds from stronger assumptions

Posted on December 29, 2016

Let me preface this post by saying that the things proved here are more easily proved by the simplest counting arguments. I think the proofs are still worthwhile, however, as they give indications of how complexity theoretic assumptions can be used to prove purely mathematical statements, and the way in which stronger assumptions allow you to prove stronger statements.

Last time, I talked about how complexity theoretic assumptions given you lower bounds on the dimensions of irreducible representations of the symmetric group. This time, I want to show how certain stronger cryptographic assumptions give better lower bounds on such dimensions.

Namely, we'll assume that one way functions exist. I.e., there is some polytime computable function \(f : 2^k \to 2^m\) such that for any non-uniform PPT algorithm \(A\), we have \[ \mathrm{Pr}_{x \sim U(2^k)} \left[ A(f(x)) \in f^{-1}(f(x)) \right ] < \frac{1}{|p(k)|} \] for every polynomial \(k\) and for large enough \(k\). What this says is that \(f\) cannot be inverted on a generic input, except with vanishingly small probability.

Now let's prove the following theorem under this assumption:

Theorem Fix a sequence of finite fields \(F_k\) with \(\log |F_k| = \mathrm{poly}(k)\) and operations computable in \(\mathrm{poly}(k)\) time.

Let \(d_k\) be the dimension of the minimal \(F_k\)-representation of \(S(2^k)\). Then for any polynomial \(q(k)\), for all sufficiently large \(k\) we have \(d_k > q(k)\)

Proof: Let \(S(2^k)\) be the symmetric group on binary strings of length \(k\) equipped with a generating set \(X_k\) corresponding to a collection > of universal gates.

Fix a polynomial \(q(k)\). Suppose to the contrary that for infinitely many \(k\) we have \(d_k \leq q(k)\). Let \(\rho_k\) be the corresponding representation.

Then for such \(k\), we can given a non-uniform polytime algorithm for deciding the word problem in \(S(2^k)\). The advice string is \(\rho_k(x_1), \rho_k(x_2), \dots\) where the \(x_i\) are the generators. There are \(\mathrm{poly}(k)\) many generators and \(d_k\) is bounded by the polynomial \(q\), so the total advice is \(\mathrm{poly}(k)\). Now, we can just solve the word problem by taking our word, replacing generators with the corresonding matrices, multiplying them together and checking if the result is the identity matrix. All this can be done in polynomial time.

The word problem for \(S(2^k)\) on our given generating set is NP-complete (this is somewhat imprecise, what I really mean is described in the last post). We note that inverting any one-way function can be done in polytime with an NP oracle. Since we non-uniformly solve NP hard problems on arbitrarily large input sizes, we can non-uniformly invert one-way functions infinitely often, (come to think of it, one has to do a bit more work, but it should work out). This contradicts our cryptographic assumption.

Examining the proof, we can actually get away with a significantly weaker assumption. Namely, that there is some NP-hard problem \(L\) such that for any \(\mathrm{P/poly}\) algorithm \(A\), there is some constant \(N\) such that for all \(k > N\), some \(x\) of length \(k\) has \(A(k) \neq L(k)\).

A more quantitative assumption

If we make a more quantitative assumption, such as the following non-uniform exponential time hypothesis:

There is a universal constant \(\delta\) such that any circuit for 3-SAT has size at least \(2^{\delta k}\).

Analyzing the circuit given in the above proof, using the fact that multiplying two \(d_k \times d_k\) matrices can be done in time \(d_k^3 \mathrm{poly}(k)\), we get the inequality \[ d_k^3 \mathrm{poly}(k) \geq 2^{\delta k} \] and thus for any \(\epsilon > 0\), \[ d_k \geq 2^{\frac{1}{3} (\delta - \epsilon) k} \] for large enough \(k\).

Sadly this is still far from the truth, which is that \(d_k = 2^k - 1\). Still, a purely complexity theoretic assumption lets us get pretty close.