Geodesic
Algorithmically distinguishing irreducible characters of the symmetric group
Timothy Y. Chow1 ; Jennifer Paulhus2
1Center of Communication Research
2Grinnell College
The electronic journal of combinatorics, Tome 28 (2021) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Suppose that $\chi_\lambda$ and $\chi_\mu$ are distinct irreducible characters of the symmetric group $S_n$. We give an algorithm that, in time polynomial in $n$, constructs $\pi\in S_n$ such that $\chi_\lambda(\pi)$ is provably different from $\chi_\mu(\pi)$. In fact, we show a little more. Suppose $f = \chi_\lambda$ for some irreducible character $\chi_\lambda$ of $S_n$, but we do not know $\lambda$, and we are given only oracle access to $f$. We give an algorithm that determines $\lambda$, 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 $\lambda$.
DOI : 10.37236/9753
Classification : 20C30, 05E10
Mots-clés : symmetric group, character, Murnaghan-Nakayama rule

Timothy Y. Chow  1   ; Jennifer Paulhus  2

1 Center of Communication Research
2 Grinnell College 
@article{10_37236_9753,
     author = {Timothy Y. Chow and Jennifer Paulhus},
     title = {Algorithmically distinguishing irreducible characters of the symmetric group},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {2},
     doi = {10.37236/9753},
     zbl = {1473.20022},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9753/}
}
TY  - JOUR
AU  - Timothy Y. Chow
AU  - Jennifer Paulhus
TI  - Algorithmically distinguishing irreducible characters of the symmetric group
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9753/
DO  - 10.37236/9753
ID  - 10_37236_9753
ER  - 
%0 Journal Article
%A Timothy Y. Chow
%A Jennifer Paulhus
%T Algorithmically distinguishing irreducible characters of the symmetric group
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/9753/
%R 10.37236/9753
%F 10_37236_9753
Timothy Y. Chow; Jennifer Paulhus. Algorithmically distinguishing irreducible characters of the symmetric group. The electronic journal of combinatorics, Tome 28 (2021) no. 2. doi: 10.37236/9753

Cité par Sources :