Ask Your Question

symbolic calculus on doubling points in elliptic curves

asked 2011-03-17 16:06:08 -0500

manenir gravatar image

updated 2011-03-17 20:07:35 -0500

Suppose I have a polynomial $f(x)$ and i need to compute $f(f(x))$

how do i do this ??

i also need to compute $f(f(f(x)))$ and so on, is there an easy way of doing this ?

Example: If $f(x)=x^2+nx$ then $f(f(x))=...=x^4 + 2n x^3+(n^2+n) x^2+ n x$ and the computations become difficult when trying to compute say $f(f(f(f(f(x)))))$

edit retag flag offensive close merge delete

3 answers

Sort by ยป oldest newest most voted

answered 2011-03-17 17:01:32 -0500

updated 2011-03-17 17:22:00 -0500

How are you defining f? This works for me:

sage: R = GF(2)['y']
sage: R.inject_variables()
Defining y
sage: f = y^2 + y + 1
sage: f(f(y))
y^4 + y + 1

Edit: if you want to do something like f(y) = y^2 + ny, then you need two variables, and you could make one a polynomial variable, one a symbolic variable. Make sure that the symbolic one comes after the polynomial one, alphabetically:

sage: var('m')
sage: R = QQ['a']
sage: R.inject_variables()
sage: f = a^2 + m*a
sage: f(f(a))
(a^2 + a*m)^2 + (a^2 + a*m)*m
sage: f(f(a)).expand()
a^4 + 2*a^3*m + a^2*m^2 + a^2*m + a*m^2


sage: f(f(f(f(f(a))))).expand()

works, but gives a very long expression.

(You need the polynomial generator to come alphabetically before the symbolic variable because f depends on two variables, and when you call f(3), for example, it chooses to substitute the 3 for the first of the variables. You want to substitute f(a) for a by default, so make sure a comes before m.)

edit flag offensive delete link more


manenir gravatar imagemanenir ( 2011-03-17 19:23:08 -0500 )edit

answered 2011-03-17 16:31:13 -0500

Felix Lawrence gravatar image

updated 2011-03-17 16:34:38 -0500

In the next version of sage (4.7) you will be able to use the functions self_compose and nest to do this. Use nest when you want to find $f(f(...f(x)...))$ for known $x$, and use self_compose when you want a function that has not been evaluated.

In the meantime you'll need to define them yourself:

def nest(f, n, x):
    """Return `f(f(...f(x)...))`, where the composition occurs n times."""
    for i in xrange(n):
        x = f(x)
    return x

def self_compose(f, n):
    """Return the function `f` composed with itself `n` times."""
    return lambda x: nest(f, n, x)

For usage examples and more documentation, see the patch that adds this functionality. There is one example which is very similar to yours:

    sage: def f(x): return x^2 + 1
    sage: x = var('x')
    sage: nest(f, 3, x)
    ((x^2 + 1)^2 + 1)^2 + 1
edit flag offensive delete link more


Cool to know about! How come I didn't know that?

kcrisman gravatar imagekcrisman ( 2011-03-17 17:31:04 -0500 )edit

probably because it was merged 9 hours ago ;-)

Felix Lawrence gravatar imageFelix Lawrence ( 2011-03-17 18:05:54 -0500 )edit

answered 2011-03-17 19:40:51 -0500

manenir gravatar image

updated 2011-03-17 19:44:01 -0500

Dear John, your help is greatly appreciated :) One further question : What i want to do is exactly what you have descibed at the end, but with an expression of the form $\frac{f(a)}{g(a)}$ where $f,g$ are polynomials in $a$ (and with coefficients in $Z[m])$ instead of just a polynomial $f(a)$. So when I define say $$f=\frac{(a^2-m^2)^2}{a^3-m}$$ what Sage notebook gives is

1/256a^13/(a^2 - 4m)^2 - 1/8a^11m/(a^2 - 4m)^2 + 7/4a^9m^2/(a^2 - 4m)^2 - 14a^7m^3/(a^2 - 4m)^2 + 70a^5m^4/(a^2 - 4m)^2 - 1/2a^7m/(a^2 - 4m)^2 - 224a^3m^5/(a^2 - 4m)^2 + 8a^5m^2/(a^2 - 4m)^2 + 448am^6/(a^2 - 4m)^2 - 48a^3m^3/(a^2 - 4m)^2 - 512m^7/((a^2 - 4m)^2a) + 128am^4/(a^2 - 4m)^2 + 256m^8/((a^2 - 4m)^2a^3) - 128m^5/((a^2 - 4m)^2a) + 16am^2/(a^2 - 4m)^2

That seems rather incomprehensible as it computes the final expression in disctinct fractions. Is there any way to format this in a nice latexed expression of the form ''polynomial over (other)polynomial'' where both polynomials will be factored ?

thanx !

edit flag offensive delete link more


You are right, this is a separate question. You may want to try f.expand() or f.[some other method that sounds plausible].

kcrisman gravatar imagekcrisman ( 2011-03-18 02:13:03 -0500 )edit

If you set g=f(f(a)), then you could use g.rational_expand() or g.rational_simplify(), or g.numerator().factor() and g.denominator().factor(). Basically, do g=f(f(a)), type "g." and hit the TAB key to see what all of the many options, and hope that something looks right.

John Palmieri gravatar imageJohn Palmieri ( 2011-03-18 04:51:30 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2011-03-17 16:06:08 -0500

Seen: 198 times

Last updated: Mar 17 '11