[Axiom-math] Decomposition of rationnal fractions

[Nicolas FRANCOIS]

Hi.

Is there any way to obtain the decomposition in simple elements (don't
know exactly how to say this in english) of a fraction of the form :

1
-------------------
(1-X)(1-X^2)(1-X^5)

(to obtain its formal series equivalent \sum a_nX^n, a_n being the
number of ways to pay n€ using 1, 2 and 5€ corners (no, there
is no such thing as a 5€ corner, but there's a 5€ banknote !)).

I'd like to obtain the C-decomposition, what do I have to do ?

More precisely : is there a way to force the use of an extension of
Q(X), by adding roots like exp(2*I*PI/5) or sqrt(2) ?

\bye

PS : clearly I'm not very good at using Axiom documentation !

[Raymond Rogers]

I don't know about a specialized solution (outside of Taylor series),
but as I recall making change and counting such is the first example in:
http://www.msri.org/communications/vmath/special_productions/production1/index_html
Sturmfel's excellent elementary introduction to Grobner Bases; which
Axiom does have support for.

Ray

Post by Nicolas FRANCOIS
Hi.
Is there any way to obtain the decomposition in simple elements (don't
1
-------------------
(1-X)(1-X^2)(1-X^5)
(to obtain its formal series equivalent \sum a_nX^n, a_n being the
number of ways to pay n€ using 1, 2 and 5€ corners (no, there
is no such thing as a 5€ corner, but there's a 5€ banknote !)).
I'd like to obtain the C-decomposition, what do I have to do ?
More precisely : is there a way to force the use of an extension of
Q(X), by adding roots like exp(2*I*PI/5) or sqrt(2) ?
\bye
PS : clearly I'm not very good at using Axiom documentation !

[Martin Rubey]

Post by Nicolas FRANCOIS
Hi.
Is there any way to obtain the decomposition in simple elements (don't
1
-------------------
(1-X)(1-X^2)(1-X^5)
(to obtain its formal series equivalent \sum a_nX^n, a_n being the
number of ways to pay n€ using 1, 2 and 5€ corners (no, there
is no such thing as a 5€ corner, but there's a 5€ banknote !)).
I'd like to obtain the C-decomposition, what do I have to do ?
More precisely : is there a way to force the use of an extension of
Q(X), by adding roots like exp(2*I*PI/5) or sqrt(2) ?
\bye
PS : clearly I'm not very good at using Axiom documentation !

Is the following close to what you have in mind? (two problems: you
need to know the extension in advance, and I don't see a way to factor
over extensions of degree higher than one right now. Possibly Waldek
knows.)


(1) -> SAEs5 := SAE(FRAC INT,UP(s5,FRAC INT),s5^2-5)

(1)
SimpleAlgebraicExtension(Fraction(Integer),UnivariatePolynomial(s5,Fra
ction(Integer)),s5^2+-5)
Type: Type
(2) -> p:UP(x,SAEs5) :=(x^5-1)*(x^2-1)*(x-1)

8 7 6 5 3 2
(2) x - x - x + x - x + x + x - 1
Type:
UnivariatePolynomial(x,SimpleAlgebraicExtension(Fraction(Integer),UnivariatePolynomial(s5,Fraction(Integer)),s5^2+-5))
(3) -> factor p

3 2 1 1 2 1 1
(3) (x - 1) (x + 1)(x + (- - s5 + -)x + 1)(x + (- s5 + -)x + 1)
2 2 2 2
Type:
Factored(UnivariatePolynomial(x,SimpleAlgebraicExtension(Fraction(Integer),UnivariatePolynomial(s5,Fraction(Integer)),s5^2+-5)))
(4) -> partialFraction(1/p, x)

(4)
13 2 9 27 1 1 1 1 1
-- x - -- x + -- - (- -- s5 - --)x + -- s5 - --
40 10 40 8 50 10 50 10
----------------- - ----- + ----------------------------
3 x + 1 2 1 1
(x - 1) x + (- - s5 + -)x + 1
2 2
+
1 1 1 1
(-- s5 - --)x - -- s5 - --
50 10 50 10
--------------------------
2 1 1
x + (- s5 + -)x + 1
2 2
Type:
PartialFraction(UnivariatePolynomial(x,Fraction(Polynomial(SimpleAlgebraicExtension(Fraction(Integer),UnivariatePolynomial(s5,Fraction(Integer)),s5^2+-5)))))


Apart from that: Gröbner bases are in Axiom (FriCAS, OpenAxiom), and a
rather good implementation, too.

Martin

[Nicolas FRANCOIS]

Le Fri, 14 May 2010 08:52:33 +0200,

Post by Martin Rubey
Is the following close to what you have in mind? (two problems: you
need to know the extension in advance, and I don't see a way to factor
over extensions of degree higher than one right now. Possibly Waldek
knows.)
(1) -> SAEs5 := SAE(FRAC INT,UP(s5,FRAC INT),s5^2-5)
(1)
SimpleAlgebraicExtension(Fraction(Integer),UnivariatePolynomial(s5,Fra
ction(Integer)),s5^2+-5)
Type: Type
(2) -> p:UP(x,SAEs5) :=(x^5-1)*(x^2-1)*(x-1)
8 7 6 5 3 2
(2) x - x - x + x - x + x + x - 1
UnivariatePolynomial(x,SimpleAlgebraicExtension(Fraction(Integer),UnivariatePolynomial(s5,Fraction(Integer)),s5^2+-5))
(3) -> factor p
3 2 1 1 2 1 1
(3) (x - 1) (x + 1)(x + (- - s5 + -)x + 1)(x + (- s5 + -)x + 1)
2 2 2 2
Factored(UnivariatePolynomial(x,SimpleAlgebraicExtension(Fraction(Integer),UnivariatePolynomial(s5,Fraction(Integer)),s5^2+-5)))
(4) -> partialFraction(1/p, x)
(4)
13 2 9 27 1 1 1 1 1
-- x - -- x + -- - (- -- s5 - --)x + -- s5 - --
40 10 40 8 50 10 50 10
----------------- - ----- + ----------------------------
3 x + 1 2 1 1
(x - 1) x + (- - s5 + -)x + 1
2 2
+
1 1 1 1
(-- s5 - --)x - -- s5 - --
50 10 50 10
--------------------------
2 1 1
x + (- s5 + -)x + 1
2 2
PartialFraction(UnivariatePolynomial(x,Fraction(Polynomial(SimpleAlgebraicExtension(Fraction(Integer),UnivariatePolynomial(s5,Fraction(Integer)),s5^2+-5)))))

Yeah, definitely closer ! I'll have to investigate all this. Thanks.

\bye