So, about three weeks ago a fast ($\mathcal{O}(n\log^2(n))$) algorithm for composition and compositional inverse of formal power series has been discovered by [user:noshi91,2024-04-08], [here](https://noshi91.hatenablog.com/entry/2024/03/16/224034) is the original blog (in Japanese). Previous best algorithm was $\mathcal{O}((n\log n)^{3/2})$. I hope someone more competent than myself will make an in-deapth blog about this later, I'll link it here as soon as I see it. For now I'll give a "quick" retelling of the algorithm.↵
↵
Bostan-Mori algorithm↵
==================↵
(Summary of section 2.1 of [this](https://arxiv.org/pdf/2008.08822.pdf) article).↵
↵
We want to compute $[x^N]\frac{P(x)}{Q(x)}$. To do that we will use an observation that for any polynomial $Q(x)$ the polynomial $Q(x)Q(-x)$ is even, so it is equal so $V(x^2)$ for some $V$. Also let $U(x)=P(x)Q(-x), U(x)=U_e(x^2)+xU_o(x^2)$.↵
↵
↵
$$[x^N]\dfrac{P(x)}{Q(x)}=[x^N]\dfrac{P(x)Q(-x)}{Q(x)Q(-x)}=[x^N]\dfrac{U_e(x^2)+xU_o(x^2)}{V(x^2)}=[x^N]\left( \dfrac{U_e}{V}(x^2)+x\dfrac{U_o}{V}(x^2) \right)$$↵
↵
So if $N$ is even $[x^N]\dfrac{P(x)}{Q(x)} = [x^{\frac{N}{2}}]\dfrac{U_e(x)}{V(x)}$ and if $N$ is odd $[x^N]\dfrac{P(x)}{Q(x)}=[x^{\frac{N-1}{2}}]\dfrac{U_o(x)}{V(x)}$. Note that $deg(V)=deg(Q)$ and $deg(U_i) \approx \dfrac{deg(P)+deg(Q)}{2}$, so if initially $deg(P) \leqslant n$ and $deg(Q) \leqslant n$, those inequalities still hold after we make $P=U_i, Q=V, N = \left[\frac{N}{2} \right]$. So each step can be made in $2$ multiplications of polynomials of degree $\leqslant n$ and there are $\log(N)$ steps untill we have $N=0$ and the task is trivial, so the algorithm works in $\mathcal{O}(n\log n \log N)$.↵
↵
Application to bivariate polynomials↵
------------------↵
It turns out that this algorithm works great with some bivariate polynomials as well.↵
↵
Now we want to find $[x^k]\frac{P(x, y)}{Q(x, y)}$ where $deg_y(P), deg_y(Q) \leqslant 1$. Note that we don't need any coeffitients with $[x^{>k}]$ in $P$ and $Q$, so we can assume $deg_x(P), deg_x(Q) \leqslant k$. Now if we make one step of Bostan-Mori algorithm we will double limits on degrees of $P$ and $Q$ in respect to $y$ and halve $k$, so after we take $P$ and $Q$ modulo $x^{k+1}$ again, we'll halve their degrees in respect to $x$. So the product of degrees in respect to $x$ and $y$ stays the same and we'll be able to find $U$ and $V$ on each step in $\mathcal{O}(k\log k)$ and solve the problem in $\mathcal{O}(k\log^2(k))$ total time.↵
↵
↵
Compositional inverse↵
==================↵
From the "Coefficient of fixed $x^k$ in $f(x)^i$ " example of Lagrange inversion theoremoffrom [this](https://codeforces.me/blog/entry/77551) blog by [user:zscoder,2024-04-08] we know a connection between $[x^k]\dfrac{1}{1-yf(x)}$ and $\left(\dfrac{x}{f^{(-1)}(x)}\right)^k \mod x^k$, where $f^{(-1)}(f(x))=x$. Specifically, ↵
↵
$$[y^i]\left([x^k]\dfrac{1}{1-yf(x)} \right) = \dfrac{i}{k}[x^{k-i}] \left(\left(\dfrac{x}{f^{(-1)}(x)}\right)^k \right)$$↵
↵
so we can find either one from the other in linear time. We can now find the first value with Bostan-Mori algorithm in $\mathcal{O}(k\log^2(k))$, and getting $f^{(-1)}$ from the second value is easy (take $ln$, multiply by $-\frac{1}{k}$, take $exp$, multiply by $x$), we can now find $f^{(-1)} \mod x^k$ in $\mathcal{O}(k\log^2(k))$ time.↵
↵
↵
Composition↵
==================↵
Finding $H(F(x)) \mod x^n$ is a linear transformation of vector of coefficients of $H$. If we transpose this transformation we'll get some linear transformation of $n$-dimansional vector $\overline{c}$ into a $deg(H)+1$-dimansional one. If $C(x)$ is the polynomial whose coeffitients correspond to coordinates of $\overline{c}$, then the transposed transformation is finding $[x^{n-1}]\dfrac{rev(C(x))}{1-yF(x)} \mod y^{deg(H)+1}$, where $rev(C(x))$ is $x^{n-1}C(\frac{1}{x})$ or just reversed $C$. This can be found in $\mathcal{O}(n\log^2(n))$ with Bostan-Mori algorithm, so by [Tellegen's principle](https://specfun.inria.fr/bostan/publications/BoLeSc03.pdf) the original problem of polynomial composition can be solved in $\mathcal{O}(n\log^2(n))$ with the same constant factor as well.
↵
Bostan-Mori algorithm↵
==================↵
(Summary of section 2.1 of [this](https://arxiv.org/pdf/2008.08822.pdf) article).↵
↵
We want to compute $[x^N]\frac{P(x)}{Q(x)}$. To do that we will use an observation that for any polynomial $Q(x)$ the polynomial $Q(x)Q(-x)$ is even, so it is equal so $V(x^2)$ for some $V$. Also let $U(x)=P(x)Q(-x), U(x)=U_e(x^2)+xU_o(x^2)$.↵
↵
↵
$$[x^N]\dfrac{P(x)}{Q(x)}=[x^N]\dfrac{P(x)Q(-x)}{Q(x)Q(-x)}=[x^N]\dfrac{U_e(x^2)+xU_o(x^2)}{V(x^2)}=[x^N]\left( \dfrac{U_e}{V}(x^2)+x\dfrac{U_o}{V}(x^2) \right)$$↵
↵
So if $N$ is even $[x^N]\dfrac{P(x)}{Q(x)} = [x^{\frac{N}{2}}]\dfrac{U_e(x)}{V(x)}$ and if $N$ is odd $[x^N]\dfrac{P(x)}{Q(x)}=[x^{\frac{N-1}{2}}]\dfrac{U_o(x)}{V(x)}$. Note that $deg(V)=deg(Q)$ and $deg(U_i) \approx \dfrac{deg(P)+deg(Q)}{2}$, so if initially $deg(P) \leqslant n$ and $deg(Q) \leqslant n$, those inequalities still hold after we make $P=U_i, Q=V, N = \left[\frac{N}{2} \right]$. So each step can be made in $2$ multiplications of polynomials of degree $\leqslant n$ and there are $\log(N)$ steps untill we have $N=0$ and the task is trivial, so the algorithm works in $\mathcal{O}(n\log n \log N)$.↵
↵
Application to bivariate polynomials↵
------------------↵
It turns out that this algorithm works great with some bivariate polynomials as well.↵
↵
Now we want to find $[x^k]\frac{P(x, y)}{Q(x, y)}$ where $deg_y(P), deg_y(Q) \leqslant 1$. Note that we don't need any coeffitients with $[x^{>k}]$ in $P$ and $Q$, so we can assume $deg_x(P), deg_x(Q) \leqslant k$. Now if we make one step of Bostan-Mori algorithm we will double limits on degrees of $P$ and $Q$ in respect to $y$ and halve $k$, so after we take $P$ and $Q$ modulo $x^{k+1}$ again, we'll halve their degrees in respect to $x$. So the product of degrees in respect to $x$ and $y$ stays the same and we'll be able to find $U$ and $V$ on each step in $\mathcal{O}(k\log k)$ and solve the problem in $\mathcal{O}(k\log^2(k))$ total time.↵
↵
↵
Compositional inverse↵
==================↵
From the "Coefficient of fixed $x^k$ in $f(x)^i$ " example of Lagrange inversion theorem
↵
$$[y^i]\left([x^k]\dfrac{1}{1-yf(x)} \right) = \dfrac{i}{k}[x^{k-i}] \left(\left(\dfrac{x}{f^{(-1)}(x)}\right)^k \right)$$↵
↵
so we can find either one from the other in linear time. We can now find the first value with Bostan-Mori algorithm in $\mathcal{O}(k\log^2(k))$, and getting $f^{(-1)}$ from the second value is easy (take $ln$, multiply by $-\frac{1}{k}$, take $exp$, multiply by $x$), we can now find $f^{(-1)} \mod x^k$ in $\mathcal{O}(k\log^2(k))$ time.↵
↵
↵
Composition↵
==================↵
Finding $H(F(x)) \mod x^n$ is a linear transformation of vector of coefficients of $H$. If we transpose this transformation we'll get some linear transformation of $n$-dimansional vector $\overline{c}$ into a $deg(H)+1$-dimansional one. If $C(x)$ is the polynomial whose coeffitients correspond to coordinates of $\overline{c}$, then the transposed transformation is finding $[x^{n-1}]\dfrac{rev(C(x))}{1-yF(x)} \mod y^{deg(H)+1}$, where $rev(C(x))$ is $x^{n-1}C(\frac{1}{x})$ or just reversed $C$. This can be found in $\mathcal{O}(n\log^2(n))$ with Bostan-Mori algorithm, so by [Tellegen's principle](https://specfun.inria.fr/bostan/publications/BoLeSc03.pdf) the original problem of polynomial composition can be solved in $\mathcal{O}(n\log^2(n))$ with the same constant factor as well.
