Decomposition of rationnal fractions

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Decomposition of rationnal fractions

Nicolas FRANCOIS-2
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 !

--

Nicolas FRANCOIS                      |  /\
http://nicolas.francois.free.fr       | |__|
                                      X--/\\
We are the Micro$oft.        _\_V
Resistance is futile.    
You will be assimilated.         darthvader penguin

_______________________________________________
Axiom-math mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/axiom-math
Reply | Threaded
Open this post in threaded view
|

Re: Decomposition of rationnal fractions

Raymond Rogers-3
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

Nicolas FRANCOIS wrote:

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


_______________________________________________
Axiom-math mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/axiom-math
Reply | Threaded
Open this post in threaded view
|

Re: Decomposition of rationnal fractions

Martin Rubey-3
In reply to this post by Nicolas FRANCOIS-2
Nicolas FRANCOIS <[hidden email]> writes:

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

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

_______________________________________________
Axiom-math mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/axiom-math
Reply | Threaded
Open this post in threaded view
|

Re: Decomposition of rationnal fractions

Nicolas FRANCOIS-2
Le Fri, 14 May 2010 08:52:33 +0200,
Martin Rubey <[hidden email]> a écrit :

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

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

\bye

--

Nicolas FRANCOIS                      |  /\
http://nicolas.francois.free.fr       | |__|
                                      X--/\\
We are the Micro$oft.        _\_V
Resistance is futile.    
You will be assimilated.         darthvader penguin

_______________________________________________
Axiom-math mailing list
[hidden email]
http://lists.nongnu.org/mailman/listinfo/axiom-math