Positivity of the Symmetric Group Characters is as Hard as the Polynomial Time Hierarchy

NEW

Problem: Reconstructed statement: let COMPUTECHARBINARY be the integer-valued function which, on input two partitions $\lambda,\mu\vdash n$ written as binary lists of parts, outputs the irreducible symmetric-group character value $\chi^\lambda(\mu)$, where $\mu$ denotes cycle type. The conjecture asserts that this function is GapP-complete under exact polynomial-time many-one reductions: for every $f\in\mathrm{GapP}$ there is a polynomial-time map $R$ with

This is the natural reading of Ikenmeyer–Pak–Panova, §5.3; their v2 labels it Conjecture 5.2 rather than 5.3.2. Exact many-one is stronger than metric/Turing reduction, so proving this resolves the stated conjecture.

Result: The conjecture is true.

Key known gadget from Ikenmeyer–Pak–Panova, Prop. 4.5: for every pair of nonnegative integer sequences $c,d$ with

one can compute in polynomial time partitions $\lambda,\alpha$ such that

where $P(a,b)$ is the number of ordered set partitions of items of sizes $a$ into bins of sizes $b$.

First, membership in GapP follows from Frobenius/Jacobi–Trudi:

For each $\sigma$, $P(\mu,\lambda+\sigma-\mathrm{id})\in\#P$: guess the bin of each part of $\mu$ and verify binary sums. Splitting the sum by the sign of $\sigma$ gives a difference of two $\#P$ functions.

For hardness, use the standard parsimonious $\#P$-completeness of $\#3\mathrm{DM}$. Thus the gap problem

is GapP-complete. Pad $E,E'$ by forced edges so both lie in $[k]^3$, with the same $k\ge 6$, without changing their numbers of perfect matchings.

Let $m=|E|+|E'|$, choose $L=m+k+10$, and encode each edge $e=(i,j,\ell)$ by a high-base code $H(e)$ with ones in the three vertex coordinates. Let $U$ be the code with ones in all $3k$ vertex coordinates. Choose a modulus $M$ larger than all possible low-order residue sums.

Create weights $W$:

plus two selector weights $kL$ and $k+1$, and one huge filler weight in a new high coordinate. Put

A residue check gives:

and there are no subsets summing to $K-1,K+3,K+4,K+5$. Indeed, any subset summing near $K$ must have high code $U$, hence exactly $k$ selected edge-items. If it uses the first selector, the low residue equals $K$ only when all $k$ edges come from $E$; if it uses the second selector, the low residue equals $K+1$ only when all $k$ edges come from $E'$. The choice $L>k+5$ excludes the nearby unwanted residues.

Now set

Then $|c|=S+12$ and $|d|=S+6$, so $|c|=|d|+6$. Also all entries are positive.

In $P(c,(2,4,d))$, the bins of sizes $2$ and $4$ are forced to contain the items $2$ and $4$. The remaining small items are $1,5$. The bin of size $K+5$ can only use the small item $5$, because the alternatives would require subset sums $K+4,K-1,K+5$, which do not occur. Hence

Similarly, in $P(c,(1,5,d))$, the first two bins force items $1,5$, leaving $2,4$. The bin $K+5$ can only use the small item $4$, giving subset sum $K+1$; the other alternatives require $K+3,K-1,K+5$, impossible. Thus

By the character gadget,

Therefore the GapP-complete function $G$ exact-many-one reduces to COMPUTECHARBINARY. Together with membership, COMPUTECHARBINARY is GapP-complete under many-one reductions.

Verification audit: the reduction outputs valid binary-encoded partitions; all numerical parameters have polynomial bitlength; padding of $3\mathrm{DM}$ instances is count-preserving; the proof gives exact equality, not merely sign preservation or Turing reduction. Thus it proves the reconstructed conjecture as stated.

Citation: Uses Ikenmeyer–Pak–Panova, “Positivity of the symmetric group characters is as hard as the polynomial time hierarchy,” IMRN 2024 / arXiv:2207.05423, especially Prop. 4.5 and §5.3. Uses the standard parsimonious $\#P$-completeness of $\#3\mathrm{DM}$, as recalled in their §3.2.