# Decompose polynomial by other irreducible polynomial

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 = 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

edit retag close merge delete

Sort by » oldest newest most voted

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

more

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.

more

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

( 2015-01-15 08:24:54 -0600 )edit

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

( 2015-01-15 08:32:06 -0600 )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.

( 2015-01-15 08:50:45 -0600 )edit