power series composition inverse

290 views
Skip to first unread message

Matt Bainbridge

unread,
Dec 7, 2009, 11:18:19 AM12/7/09
to sage-support
Hi there,

Does anyone know if Sage has a function for computing the composition
inverse of a power series (not the reciprocal)?

--Matt

P.S. Just started using sage and finding it very useful. Thanks for
developing it.

William Stein

unread,
Dec 7, 2009, 1:43:43 PM12/7/09
to sage-support
2009/12/7 Matt Bainbridge <bainbri...@gmail.com>:
> Hi there,
>
> Does anyone know if Sage has a function for computing the composition
> inverse of a power series (not the reciprocal)?

Yep, we have that:

sage: R.<x> = QQ[[]]
sage: f = 1/(1-x) - 1; f
x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12
+ x^13 + x^14 + x^15 + x^16 + x^17 + x^18 + x^19 + O(x^20)
sage: g = f.reversion(); g
x - x^2 + x^3 - x^4 + x^5 - x^6 + x^7 - x^8 + x^9 - x^10 + x^11 - x^12
+ x^13 - x^14 + x^15 - x^16 + x^17 - x^18 + x^19 + O(x^20)
sage: f(g)
x + O(x^20)



> --Matt
>
> P.S. Just started using sage and finding it very useful.  Thanks for
> developing it.
>
> --
> To post to this group, send email to sage-s...@googlegroups.com
> To unsubscribe from this group, send email to sage-support...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-support
> URL: http://www.sagemath.org



--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org

Matt Bainbridge

unread,
Dec 7, 2009, 2:04:23 PM12/7/09
to sage-support
Thanks, William!

I guess so far it only works over Q?

--Matt



On Dec 7, 7:43 pm, William Stein <wst...@gmail.com> wrote:
> 2009/12/7 Matt Bainbridge <bainbridge.m...@gmail.com>:
>
> > Hi there,
>
> > Does anyone know if Sage has a function for computing the composition
> > inverse of a power series (not the reciprocal)?
>
> Yep, we have that:
>
> sage: R.<x> = QQ[[]]
> sage: f = 1/(1-x) - 1; f
> x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12
> + x^13 + x^14 + x^15 + x^16 + x^17 + x^18 + x^19 + O(x^20)
> sage: g = f.reversion(); g
> x - x^2 + x^3 - x^4 + x^5 - x^6 + x^7 - x^8 + x^9 - x^10 + x^11 - x^12
> + x^13 - x^14 + x^15 - x^16 + x^17 - x^18 + x^19 + O(x^20)
> sage: f(g)
> x + O(x^20)
>
> > --Matt
>
> > P.S. Just started using sage and finding it very useful.  Thanks for
> > developing it.
>
> > --
> > To post to this group, send email to sage-s...@googlegroups.com
> > To unsubscribe from this group, send email to sage-support...@googlegroups.com
> > For more options, visit this group athttp://groups.google.com/group/sage-support

William Stein

unread,
Dec 9, 2009, 10:35:59 AM12/9/09
to sage-support
On Mon, Dec 7, 2009 at 11:04 AM, Matt Bainbridge
<bainbri...@gmail.com> wrote:
> Thanks, William!
>
> I guess so far it only works over Q?
>
> --Matt
>

It calls off to PARI, so it probably works (or can trivially be made
to work) over any base that PARI supports. In case it isn't
implemented in general in sage, it would be nice if somebody were to
add that.

William

Martin Rubey

unread,
Dec 9, 2009, 11:15:33 AM12/9/09
to sage-s...@googlegroups.com
William Stein <wst...@gmail.com> writes:

> On Mon, Dec 7, 2009 at 11:04 AM, Matt Bainbridge
> <bainbri...@gmail.com> wrote:
>> Thanks, William!
>>
>> I guess so far it only works over Q?
>>
>> --Matt
>>
>
> It calls off to PARI, so it probably works (or can trivially be made
> to work) over any base that PARI supports.

In case it doesn't and you really really need it, and there is no other way to do it, you could call
the fricas implementation for lazy power series. Eg: (WARNING: ASCII art follows)

sage: X=fricas('monomial(1,1)$UnivariateTaylorSeries(SquareMatrix(2, PrimeField 7), x, 0)')
sage: X
x
sage: s = 4*(fricas.recip(1-2*X)-1)
sage: s

+2 0+ 2 +4 0+ 3 4 +2 0+ 5 +4 0+ 6 7 +2 0+ 8 +4 0+ 9 10 11
x + | |x + | |x + x + | |x + | |x + x + | |x + | |x + x + O(x )
+0 2+ +0 4+ +0 2+ +0 4+ +0 2+ +0 4+
sage: t = fricas.revert(s)
sage: t

+5 0+ 2 +4 0+ 3 4 +2 0+ 5 +3 0+ 6 7 +5 0+ 8 +4 0+ 9 10 11
x + | |x + | |x - x + | |x + | |x + x + | |x + | |x - x + O(x )
+0 5+ +0 4+ +0 2+ +0 3+ +0 5+ +0 4+
sage: fricas.elt(t,s)

11
x + O(x )
sage: fricas.coefficient(t, 100)

+6 0+
| |
+0 6+


(Unfortunately, the sage wrapper is not very polished... The computations should be pretty fast
though.)

Martin

Matt Bainbridge

unread,
Dec 9, 2009, 1:50:56 PM12/9/09
to sage-support
Its easy enough to code this in sage. This seems to work over any
field:


def ps_inverse(f):
if f.prec() is infinity:
raise ValueError, "series must have finite precision for
reversion"
if f.valuation() != 1:
raise ValueError, "series must have valuation one for
reversion"
t = parent(f).gen()
a = 1/f.coefficients()[0]
g = a*t
for i in range(2, f.prec()):
g -= ps_coefficient((f + O(t^(i+1)))(g),i)*a*t^i
g += O(t^f.prec())
return g

def ps_coefficient(f,i):
if i >= f.prec():
raise ValueError, "that coefficient is undefined"
else:
return f.padded_list(f.prec())[i]

William Stein

unread,
Dec 9, 2009, 3:20:29 PM12/9/09
to sage-s...@googlegroups.com
On Wed, Dec 9, 2009 at 10:50 AM, Matt Bainbridge
<bainbri...@gmail.com> wrote:
> Its easy enough to code this in sage.  This seems to work over any
> field:

Thanks. This is now http://trac.sagemath.org/sage_trac/ticket/7644

>
>
> def ps_inverse(f):
>    if f.prec() is infinity:
>        raise ValueError, "series must have finite precision for
> reversion"
>    if f.valuation() != 1:
>        raise ValueError, "series must have valuation one for
> reversion"
>    t = parent(f).gen()
>    a = 1/f.coefficients()[0]
>    g = a*t
>    for i in range(2, f.prec()):
>        g -=  ps_coefficient((f + O(t^(i+1)))(g),i)*a*t^i
>    g += O(t^f.prec())
>    return g
>
> def ps_coefficient(f,i):
>    if i >= f.prec():
>        raise ValueError, "that coefficient is undefined"
>    else:
>        return f.padded_list(f.prec())[i]
>
> --
> To post to this group, send email to sage-s...@googlegroups.com
> To unsubscribe from this group, send email to sage-support...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-support

Niles

unread,
Dec 25, 2009, 9:58:42 AM12/25/09
to sage-support
Some code for Lagrange inversion has been posted on the "generic power
series reversion" trac ticket: http://trac.sagemath.org/sage_trac/ticket/7644

The code doesn't quite run, since it references some other function
(ps_coefficient); here's an updated version which uses only built-in
functions:

def ps_inverse_Lagrange(f):


if f.valuation() != 1:
raise ValueError, "series must have valuation one for
reversion"
if f.prec() is infinity:
raise ValueError, "series must have finite precision for
reversion"

t = parent(f).gen()
h = t/f
k = 1
g = 0
for i in range(1, f.prec()):
k *= h
g += (1/i)*k.padded_list(i)[i - 1]*t^i


g += O(t^f.prec())
return g


On Dec 9, 3:20 pm, William Stein <wst...@gmail.com> wrote:
> On Wed, Dec 9, 2009 at 10:50 AM, Matt Bainbridge
>

> > For more options, visit this group athttp://groups.google.com/group/sage-support

Reply all
Reply to author
Forward
0 new messages