ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 17 Jan 2015 17:30:02 -0600Decompose polynomial by other irreducible polynomialhttps://ask.sagemath.org/question/25530/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 solutionThu, 15 Jan 2015 06:54:09 -0600https://ask.sagemath.org/question/25530/decompose-polynomial-by-other-irreducible-polynomial/Answer by vdelecroix for <p>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)$$</p>
<p>Is there some fast(?) way to do it in Sage except by hand writing your own function?</p>
<p>UPD. I forget to add that $\deg a_i < \deg v$.</p>
<p>UPD2. Naive solution:</p>
<pre><code> degree = f.degree()//v.degree()
decomposition = [None] * (degree + 1)
for i in range(degree+1):
decomposition[i] = f%v
f //= v
return decomposition
</code></pre>
<p>But may be there is some native solution</p>
https://ask.sagemath.org/question/25530/decompose-polynomial-by-other-irreducible-polynomial/?answer=25548#post-id-25548Hello,
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
VincentSat, 17 Jan 2015 17:30:02 -0600https://ask.sagemath.org/question/25530/decompose-polynomial-by-other-irreducible-polynomial/?answer=25548#post-id-25548Answer by mmarco for <p>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)$$</p>
<p>Is there some fast(?) way to do it in Sage except by hand writing your own function?</p>
<p>UPD. I forget to add that $\deg a_i < \deg v$.</p>
<p>UPD2. Naive solution:</p>
<pre><code> degree = f.degree()//v.degree()
decomposition = [None] * (degree + 1)
for i in range(degree+1):
decomposition[i] = f%v
f //= v
return decomposition
</code></pre>
<p>But may be there is some native solution</p>
https://ask.sagemath.org/question/25530/decompose-polynomial-by-other-irreducible-polynomial/?answer=25531#post-id-25531What 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.Thu, 15 Jan 2015 07:16:36 -0600https://ask.sagemath.org/question/25530/decompose-polynomial-by-other-irreducible-polynomial/?answer=25531#post-id-25531Comment by mmarco for <p>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)$.</p>
<p>this can be done using elimination techniques:</p>
<pre><code>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
</code></pre>
<p>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.</p>
https://ask.sagemath.org/question/25530/decompose-polynomial-by-other-irreducible-polynomial/?comment=25534#post-id-25534Oh, 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.Thu, 15 Jan 2015 08:50:45 -0600https://ask.sagemath.org/question/25530/decompose-polynomial-by-other-irreducible-polynomial/?comment=25534#post-id-25534Comment by petRUShka for <p>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)$.</p>
<p>this can be done using elimination techniques:</p>
<pre><code>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
</code></pre>
<p>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.</p>
https://ask.sagemath.org/question/25530/decompose-polynomial-by-other-irreducible-polynomial/?comment=25533#post-id-25533Unfortunately this technique will not work with other examples :( For example where a_i should be something with degree more than 0.Thu, 15 Jan 2015 08:32:06 -0600https://ask.sagemath.org/question/25530/decompose-polynomial-by-other-irreducible-polynomial/?comment=25533#post-id-25533Comment by petRUShka for <p>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)$.</p>
<p>this can be done using elimination techniques:</p>
<pre><code>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
</code></pre>
<p>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.</p>
https://ask.sagemath.org/question/25530/decompose-polynomial-by-other-irreducible-polynomial/?comment=25532#post-id-25532Why it is impossible? If $f$ has lower degree than $v$ then $f$ = $a_0$, where $a_0$ = $f(x)$.Thu, 15 Jan 2015 08:24:54 -0600https://ask.sagemath.org/question/25530/decompose-polynomial-by-other-irreducible-polynomial/?comment=25532#post-id-25532