Compositional inverse of a power series

2

If \$f(x) = x + \sum_{i>1} a_ix^i\$ and \$g(x)=x+\sum_{i>1}b_ix^i\$ then there is a composite power series \$f(g(x))\$ also of this form. Given a power series \$f\$ the goal is to find a compositional inverse \$f^{-1}\$ so that \$f(f^{-1}(x))=x\$.

One approach to this is recursive: start with a guess \$g_1(x)=x\$ for the inverse. Suppose that \$f(g_{n-1}(x))=x+c_{n}x^n + O(x^{n+1})\$. Then set \$g_n(x)=g_{n-1}(x)-c_nx^n\$. Then \$f^{-1}=\lim_{n\to\infty}g_n\$. (The sequence \$g_n\$ is convergent in the power series norm so this limit is well defined.)

A second approach is to use the Lagrange inversion formula, which says that \$f^{-1}(x)=\sum b_ix^i\$ where

\$\displaystyle \qquad \qquad \qquad \qquad \qquad \qquad\,\,\,\,\,\,\, b_i=\frac{1}{n!}\frac{d^{n-1}}{dw^{n-1}}\left(\frac{w}{f(w)}\right)^n\$.

Task

Input: A list of integers \$[a_2, a_3,..., a_n]\$

Output: A list of integers \$[b_2,\ldots, b_n]\$ such that if

\$\displaystyle \qquad \qquad \qquad \qquad \qquad \qquad f(x)=x+\sum_{i=2}^n a_ix^i\$

and

\$\displaystyle \qquad \qquad \qquad \qquad \qquad \qquad g(x)=x+\sum_{i=2}^n b_ix^i\$

then

\$\displaystyle \qquad \qquad \qquad \qquad \qquad \,\,\,\,f(g(x))=x+O(x^{n+1})\$

You may alternatively accept input in whatever other format is most convenient. If you wish to accept an input list padded like \$[0, 1, a_2,\ldots,a_n]\$ or like \$[1,a_2,\ldots, a_n]\$ that is acceptable. If you wish to pad the output in either of these ways that is acceptable too.

Scoring

This is code golf so shortest answer in bytes wins.

Test cases

[0, 0, 0, 0, 0] => [0, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1] => [-1, 1, -1, 1, -1, 1, -1, 1, -1, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] => [-1, 0, 2, -2, -5, 14, 5, -72, 68, 
  278]
[2, 3, 4, 5, 6, 7, 8, 9, 10] => [-2, 5, -14, 42, -132, 429, -1430, 4862, -16796, 58797]
[1, 4, 9, 16, 25, 36] => [-1, -2, 6, 16, -67, -164]
[0, 0, 2, -4, 2, 3] => [0, 0, -2, 4, -2, 13]
[1, 2, -5, 1, 4, -5] => [-1, 0, 10, -47, 87, 333]
[2, 1, 0, 4, -3, -1] => [-2, 7, -30, 139, -669, 3285]

Hood

Posted 2020-01-11T20:54:30.647

Reputation: 1 437

Question was closed 2020-01-11T21:41:45.987

No answers