# Generalized Newton Identities

I learnt a lot of new words (Hall-Littlewood, 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 error-prone) 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_1-f_4$.

• What is $f_*$ ? The forgotten basis? – darij grinberg Dec 17 '17 at 18:30
• And what is $*$? – მამუკა ჯიბლაძე Dec 17 '17 at 19:39
• @darij grinberg: looks like it's a non standard notation for the monomial basis. So OP is asking to expand monomial to power sums. – hivert Dec 17 '17 at 22:46
• @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 change-of-basis matrix. Invert this change-of-basis matrix, and you get the coefficients of the monomial symmetric functions represented ... – darij grinberg Dec 17 '17 at 23:06
• ... as linear combinations of the other basis. In many specific cases, there are easier ways, but at least for the Hall-Littlewoods 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 power-sum basis, however, the change-of-basis matrices are triangular with respect to the refinement order on partitions; this simplifies life (it is easy to invert a triangular matrix). – 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.

• 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 :-) – Hauke Reddmann Dec 18 '17 at 8:28
• I'm surprised too ! I just found it googling after reading your question... – hivert Dec 18 '17 at 8:32