Here's an algorithm that I use. Let's call $S$ the degree-$n$ shift operation, sending $\sum c_kz^k$ to $\sum c_{n+k}z^k$, in other words the quotient when you divide a power series by $z^n$. Step 0: divide $f$ by $Sf$, giving you a power series $f_1$ such that $Sf_1\equiv 1$ modulo $M$. Step $i$, for $i\ge0$: i > 0$: repeat. At each stage, you get a power series $f_i$ for which $Sf_i\equiv 1 $ modulo $M^i$. For a quicker variant of Step $i$ (for $i > 0$), instead multiply by $2-Sf_i$. It works because you've constructed a convergent infinite product.
|
2 | changed an inequality from weak to strong. | ||
|
|
||||
|
|
1 |
|
||
|
Here's an algorithm that I use. Let's call $S$ the degree-$n$ shift operation, sending $\sum c_kz^k$ to $\sum c_{n+k}z^k$, in other words the quotient when you divide a power series by $z^n$. Step 0: divide $f$ by $Sf$, giving you a power series $f_1$ such that $Sf_1\equiv 1$ modulo $M$. Step $i$, for $i\ge0$: repeat. At each stage, you get a power series $f_i$ for which $Sf_i\equiv 1 $ modulo $M^i$. For a quicker variant of Step $i$ (for $i > 0$), instead multiply by $2-Sf_i$. It works because you've constructed a convergent infinite product. |
||||
