Algorithmically distinguishing irreducible characters of the symmetric group

2020/05/29 by Chow, Timothy Y., Paulhus, Jennifer
#05E10 (Primary) 20C30 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #Representation Theory (math.RT)

paper · doi:10.48550/arxiv.2006.00035

Abstract

Suppose that χ_λ and χ_μ are distinct irreducible characters of the symmetric group S_n. We give an algorithm that, in time polynomial in n, constructs π∈ S_n such that χ_λ(π) is provably different from χ_μ(π). In fact, we show a little more. Suppose f=χ_λ for some irreducible character χ_λ of S_n, but we do not know λ, and we are given only oracle access to f. We give an algorithm that determines λ, using a number of queries to f that is polynomial in n. Each query can be computed in time polynomial in n by someone who knows λ.

Related

• On the irreducible character degrees of symmetric groups and their multiplicities
• Irreducible characters of the generalized symmetric group
• Irreducible Symmetric Group Characters of Rectangular Shape
• A recursion formula for the irreducible characters of the symmetric group
• A conjectured combinatorial interpretation of the normalized irreducible character values of the symmetric group