I learnt a lot of new words (HallLittlewood, Jack and Macdonald polynomials) but unfortunately everything I dug up is written without a single example and I still don't know the answer to a very obvious generalization: Let $P$ be a partition. Example: $31$. The symmetric polynomial corresponding to $P$ would be $f_{31}=a^3*b+a^3*c+...$ (with any number of variables: if we work in the ring of symmetric functions, it doesn't matter anyway). Now Newton's identities cover $f_{1...1}$ vs. $f_n$. I'd like to have an explicit formula or at least algorithm (at the moment I do it by hand, which is tedious and errorprone) to express any $f_P$ in the basis functions (actually I need the power sums $f_n$, but since the standard Newton identities cover the conversion, a formulation via the elementary symmetric polynomials is fine, either). Example with power sums: $f_{31}=f_3*f_1f_4$.

$\begingroup$ What is $f_*$ ? The forgotten basis? $\endgroup$ – darij grinberg Dec 17 '17 at 18:30

$\begingroup$ And what is $*$? $\endgroup$ – მამუკა ჯიბლაძე Dec 17 '17 at 19:39

$\begingroup$ @darij grinberg: looks like it's a non standard notation for the monomial basis. So OP is asking to expand monomial to power sums. $\endgroup$ – hivert Dec 17 '17 at 22:46

$\begingroup$ @hivert: Hi, and sorry for the radio silence on ssreflect (too much to learn so far...)! Yeah, his example does look like monomial symmetric functions. So Hauke wants to know how a monomial symmetric function can be written as a linear combination of elements of another basis. Well, the one way that always works is: Writing the elements of the other basis as linear combinations of monomial symmetric functions, you get a changeofbasis matrix. Invert this changeofbasis matrix, and you get the coefficients of the monomial symmetric functions represented ... $\endgroup$ – darij grinberg Dec 17 '17 at 23:06

$\begingroup$ ... as linear combinations of the other basis. In many specific cases, there are easier ways, but at least for the HallLittlewoods there seems to be no particularly simple rule, or else I'd expect to see it in the corresponding piece of Sage sourcecode. I don't think the matrix will be triangular either. For the powersum basis, however, the changeofbasis matrices are triangular with respect to the refinement order on partitions; this simplifies life (it is easy to invert a triangular matrix). $\endgroup$ – darij grinberg Dec 17 '17 at 23:09
As far as I understand, what you call $f_P$ is usually called monomial symmetric function and is denoted $m_P$. So I interpret your question as asking for an algorithm converting monomial symmetric funtions to power sum symmetric functions. Such an algorithm seems to be described here:
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4656270/
Also there is one which was implemented in Symmetrica (which is the one used in Sagemath) more than twenty years ago. I don't think the algorithm was documented anywhere but as a comment in the code (the file is called tmp.c
) . The comment seems to indicate that they use a recursive divide and conquer method using the following recursion step:
$$ m_{a_1,a_2,...,a_n,a_{n+1},...a_{2n}} = m_{a_1,...,a_n} * m_{a_{n+1},..,a_{2n}}  \text{terms of length} <2n $$
You can compute the rest of the terms using this answer.
Anyway, unless you really need to say something about the algorithm, I would recommend using a computer algebra system which already has this algorithm implemented.

$\begingroup$ Yes, this is what I searched for. Best for me would be an implementation in MATHEMATICA, but I probably won't go past n=10 anyway. (Still, it surprises me somewhat that there is a 2015 article about an elementary problem solved about 300 years ago :) $\endgroup$ – Hauke Reddmann Dec 18 '17 at 8:28

$\begingroup$ I'm surprised too ! I just found it googling after reading your question... $\endgroup$ – hivert Dec 18 '17 at 8:32