Inverting formal power series wrt. composition

A formal power series $f \in R[[X]]$ is said to be invertible wrt. composition, iff there exists $g \in R[[X]]$ s.t. $f \circ g = g \circ f = X$ holds.

It is easy to see, that for such $f = \sum_{n=0}^\infty f_n X^n$ necessarily $f_0 = 0$ and $f_1 \in R^\times$ holds. I am looking for a proof, that this condition is also sufficient. Is there an elegant proof which avoids using an explicit formula for the coefficients of compositions $f \circ g$?

• How is composition defined on a ring of formal power series? – Tobias Kildetoft Mar 18 '13 at 23:03
• In fact it is not defined on the whole ring, some conditions are needed (such as constant term is zero). – Martin Brandenburg Mar 18 '13 at 23:08
• $f \circ g$ is defined as $\sum_{n=0}^\infty f_n g^n$ which converges wrt. the $(X)$-adic topology, providing that $g(0) = 0$. Otherwise composition is not defined, so $f_0 = 0$ is a necessary condition not only for being invertible, but also for a well defined composition from left and right. – Dune Mar 18 '13 at 23:16
• If anybody is listening: the last comment seems to miss a point in formal power series. My reading is that a generating function/process for "Formal Power Series" means that the process converges for each coefficiant not for the sum! If I am wrong I would appreciate being corrected. – rrogers Mar 9 '17 at 16:26

You can use Hensel's lemma in the following variant:

Hensel's lemma: Let $$A$$ be an integral domain which is complete w.r.t. an ideal $$I$$. Suppose we are given $$F \in A[[Y]]$$ and $$a \in I$$ such that $$F(a) \equiv 0 \bmod I^s$$ for some $$s \geq 1$$, and $$F'(a) \in A^\times$$. Then there exists a unique $$b \in I$$ such that $$F(b) = 0$$ and $$b \equiv a \bmod I^s$$.

Given $$f(X) = f_1X + \ldots \in R[[X]]$$ with $$f_1 \in R^\times$$ (the dots mean terms of higher order), take $$A = R[[X]]$$, $$F(Y) = f(Y)-X \in R[[X]][[Y]]$$, $$a = f_1^{-1}X$$ and $$s = 2$$ in the lemma. We have $$F(f_1^{-1}X) = f_1(f_1^{-1}X) + \ldots - X \equiv 0 \mod {X^2},$$ $$F'(f_1^{-1}X) = f_1 + \ldots \in R[[X]]^\times,$$ so Hensel's lemma gives a unique $$g \in R[[X]]$$ such that $$f(g(X)) = X$$ and $$g(X) = f_1^{-1}X +\ldots$$. The same argument with $$g$$ instead of $$f$$ gives a unique $$h(X) = f_1X + \ldots \in R[[X]]$$ such that $$g(h(X)) = X$$. Now $$f(X) = f(g(h(X))) = h(X),$$ so $$h=f$$ and thus $$f(g(X)) = g(f(X)) = X$$.

Edit 11/2018: I think you can prove the lemma as follows. Replacing $$F(Y)$$ with $$F(Y+a)F'(a)^{-1}$$ we can assume $$a = 0$$ and $$F'(0) = 1$$. Then we put $$x_0 = 0$$ and $$x_{n+1} := x_n - F(x_n)$$. Then $$x_n \equiv 0 \bmod I^s$$ for all $$n \geq 0$$ by induction. We claim: $$x_{n+1} \equiv x_n \bmod I^{n+s} \quad \text{for all n \geq 0}.$$ The case $$n=0$$ is clear. Assume $$x_n \equiv x_{n-1} \bmod I^{n+s-1}$$ for the induction. We can write $$F(Y) - F(Z) = (Y-Z)(1+YG(Y,Z)+ZH(Y,Z))$$ for certain $$G, H \in A[[Y,Z]]$$. We find $$F(x_n) - F(x_{n-1}) \equiv x_n - x_{n-1} \bmod I^{n+s},$$ hence $$x_n - F(x_n) \equiv x_{n-1} - F(x_{n-1}) \bmod I^{n+s}$$, or also $$x_{n+1} \equiv x_n \bmod I^{n+s}$$. The claim shows that $$(x_n)$$ is a Cauchy sequence. By completeness, it converges to some $$b \in I^s$$. It satisfies $$b = b-F(b)$$, hence $$F(b) = 0$$. For uniqueness, assume $$F(b) = F(c) = 0$$ with $$b,c \in I^s$$. We find $$0 = (b-c)(1+bG(b,c)+cH(b,c)),$$ which implies $$b = c$$ since $$1+I \subseteq A^\times$$. It seems that the assumption of $$A$$ to be integral is not necessary.

• That's really elegant, but it puts off the proof effort to this variant of Hensel's lemma, which is unknown to me yet. I would be really happy, if you could also provide a (preferably online) source for a proof of it. – Dune Mar 19 '13 at 8:28
• It is really necessary for $A$ being integral? – Dune Mar 19 '13 at 12:14
• Actually, I couldn't find a reference for that variant of Hensel's lemma. However, lemma 10.5 here (people.ds.cam.ac.uk/eb525/ec-notes.pdf) comes very close and I think the proof generalizes to the variant given above. Alternatively, look at lemma 11.6. This is exactly the statement you want to prove, and the proof actually goes along the lines of Hensel's lemma, by constructing successive approximations of the inverse power series. Integrality of $A$ is only needed for the uniqueness in Hensel's lemma, but since we didn't use that, it can probably be dropped. – marlu Mar 19 '13 at 14:14
• @marlu: Your link is dead. I'm quite interested in the proof of that version of Hensel's lemma; I can't imagine any way in which integrality could be used. On the other hand, I suspect you want $A$ to be hausdorff, not just complete, or else how would $f'(a)$ be defined? – darij grinberg Nov 27 at 1:03
• I edited my answer to include a proof sketch. You are right, I think integrality is not needed. I also indeed want $A$ to be Hausdorff, that is included in the definition of "complete" that I used – marlu Nov 29 at 1:07

I'm going to basically copy a proof given by Cartan.

It is sufficient for there to exist a unique $g$ that $f(0) = 0$ and $f'(0) \ne 0$, as you have said. We also know that $f_1g_1$ must equal $1$.

We want $f\circ g(X) = X$, So we try to find the conditions for which the coefficient of $X^n$ in $f\circ g$ is $0$. We know that this is equal to the coefficient of $X^n$ in $$f_1g+f_2g^2+\cdots + f_ng^n\tag{1}$$ So we have a condition $$f_1g_n + P_n(f_2,\dots,f_n,g_1,\dots,g_{n-1})= 0\tag{2}$$ Where $P_n$ is a polynomial that may be calculated from $(1)$. Because $f_1 \ne 0$, $f_1g_1 = 1$ determines $g_1$. We then take $(2)$ with $n = 2$ to find $g_2$, and by induction we can find all $g_n$.

We therefore have the existence and uniqueness of such an inverse compositional series.

We can also show that $f$ is the only series for which $g$ is an inverse. Construct $f'$ as we constructed $g$ such that $f'(0) = 0$ and $g\circ f' = X$. We have that $$f' = X\circ f' =f\circ g \circ f' = f\circ X = f$$

This doesn't explicitly construct the coefficients, but proves that they may be constructed, which is a little more elegant.

• Thank you for this great answer! I wish I could accept both answers, but since this is not possible and since I find the application of Hensel's lemma slightly more elegant, I chose the other. – Dune Mar 19 '13 at 18:41