power series composition inverse

[Matt Bainbridge]

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]

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]

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]

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]

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]

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]

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]

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