Ask Your Question

Decompose polynomial by other irreducible polynomial

asked 2015-01-15 13:54:09 +0200

petRUShka gravatar image

updated 2015-01-15 16:15:58 +0200

Suppose I have irreducible polynomial $v(x)$ over $\mathbb Q$ (or arbitrary field). I want to decompose any other $f(x) \in \mathbb Q[x]$ by powers of $v$. Like this $$f(x)=a_n(x)(v(x))^n + \dots + a_1(x)v(x) + a_0(x)$$

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

UPD. I forget to add that $\deg a_i < \deg v$.

UPD2. Naive solution:

  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

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted

answered 2015-01-18 00:30:02 +0200

vdelecroix gravatar image


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


edit flag offensive delete link more

answered 2015-01-15 14:16:36 +0200

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

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.

edit flag offensive delete link more


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

petRUShka gravatar imagepetRUShka ( 2015-01-15 15:24:54 +0200 )edit

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 ( 2015-01-15 15:32:06 +0200 )edit

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

So what you want are basically the remainders of the division of $f$ by $v$, $v^2$, $v^3$ and so on.

mmarco gravatar imagemmarco ( 2015-01-15 15:50:45 +0200 )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

1 follower


Asked: 2015-01-15 13:54:09 +0200

Seen: 308 times

Last updated: Jan 18 '15