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

We prove that deciding the vanishing of the character of the symmetric group is $\textsf{C}_= \textsf{P}$-complete. We use this hardness result to prove that the absolute value and also the square of the character are not contained in $\textsf{#P}$, unless the polynomial hierarchy collapses to the s...

Full description

Saved in:
Bibliographic Details
Published in:International mathematics research notices 2024-05, Vol.2024 (10), p.8442-8458
Main Authors: Ikenmeyer, Christian, Pak, Igor, Panova, Greta
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We prove that deciding the vanishing of the character of the symmetric group is $\textsf{C}_= \textsf{P}$-complete. We use this hardness result to prove that the absolute value and also the square of the character are not contained in $\textsf{#P}$, unless the polynomial hierarchy collapses to the second level. This rules out the existence of any (unsigned) combinatorial description for the square of the characters. As a byproduct of our proof, we conclude that deciding positivity of the character is $\textsf{PP}$-complete under many-one reductions, and hence $\textsf{PH}$-hard under Turing reductions.
ISSN:1073-7928
1687-0247
DOI:10.1093/imrn/rnad273