Ask Your Question
0

Decompose polynomial by other irreducible polynomial

asked 10 years ago

petRUShka gravatar image

updated 10 years ago

Suppose I have irreducible polynomial v(x) over Q (or arbitrary field). I want to decompose any other f(x)Q[x] by powers of v. Like this f(x)=an(x)(v(x))n++a1(x)v(x)+a0(x)

Is there some fast(?) way to do it in Sage except by hand writing your own function?

UPD. I forget to add that degai<degv.

UPD2. Naive solution:

  degree = f.degree()//v.degree()                                                                                                                                          
  decomposition = [None] * (degree + 1)
  for i in range(degree+1):                                                                                                              
    decomposition[i] = f%v                                                                                                             
    f //= v                                                                                                                       
  return decomposition

But may be there is some native solution

Preview: (hide)

2 Answers

Sort by » oldest newest most voted
2

answered 10 years ago

vdelecroix gravatar image

Hello,

Do you really need v to be irreducible in order to do that? Your algorithm looks fine but you can do cleaner using the method quo_rem which returns at once both the quotient and the remainder.

sage: x = polygen(ZZ, 'x')
sage: f = x^6 + 3*x^3 - x^2 + 1
sage: v = x^2 + 1
sage: decomposition = []
sage: q = f
sage: while q:
....:    q,r = q.quo_rem(v)
....:    decomposition.append(r)

And then you can check that you get back the initial polynomial:

sage: sum(a * v^i  for i,a in enumerate(decomposition))
x^6 + 3*x^3 - x^2 + 1

Vincent

Preview: (hide)
link
0

answered 10 years ago

mmarco gravatar image

What you want to do is not always possible (for instance, if f has lower degree than v). But when there exists an answer, what you want is just an inverse image of the polynomial f by the map that sends x to v(x).

this can be done using elimination techniques:

sage: R.<x,t> = QQ[]
sage: v = x^2 + x + 1
sage: f = x^4 + 2*x^3 + 6*x^2 + 5*x + 2
sage: I = R.ideal([t - v, f])
sage: L = I.elimination_ideal(x)
sage: L
Ideal (t^2 + 3*t - 2) of Multivariate Polynomial Ring in x, t over Rational Field
sage: L.gen(0)(t=v) == f
True

In this case there was a solution. When there is not, you will get some polynomial whose image is a multiple of what you wanted.

Preview: (hide)
link

Comments

Why it is impossible? If f has lower degree than v then f = a0, where a0 = f(x).

petRUShka gravatar imagepetRUShka ( 10 years ago )

Unfortunately this technique will not work with other examples :( For example where a_i should be something with degree more than 0.

petRUShka gravatar imagepetRUShka ( 10 years ago )

Oh, sorry, i understood that you meant the ai to be constants.

So what you want are basically the remainders of the division of f by v, v2, v3 and so on.

mmarco gravatar imagemmarco ( 10 years ago )

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 10 years ago

Seen: 491 times

Last updated: Jan 18 '15