Abramov's_algorithm Knowpia

In mathematics, particularly in computer algebra, Abramov's algorithm computes all rational solutions of a linear recurrence equation with polynomial coefficients. The algorithm was published by Sergei A. Abramov in 1989.^[1]^[2]

Universal denominator edit

The main concept in Abramov's algorithm is a universal denominator. Let ${\textstyle \mathbb {K} }$ be a field of characteristic zero. The dispersion ${\textstyle \operatorname {dis} (p,q)}$ of two polynomials ${\textstyle p,q\in \mathbb {K} [n]}$ is defined as

\operatorname {dis} (p,q)=\max\{k\in \mathbb {N} \,:\,\deg(\gcd(p(n),q(n+k)))\geq 1\}\cup \{-1\},

where

{\textstyle \mathbb {N} }

denotes the set of non-negative integers. Therefore the dispersion is the maximum

{\textstyle k\in \mathbb {N} }

such that the polynomial

{\textstyle p}

and the

{\textstyle k}

-times shifted polynomial

q

have a common factor. It is

{\textstyle -1}

if such a

{\textstyle k}

does not exist. The dispersion can be computed as the largest non-negative integer root of the resultant

{\textstyle \operatorname {res} _{n}(p(n),q(n+k))\in \mathbb {K} [k]}

.^[3]^[4] Let

{\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}

be a recurrence equation of order

{\textstyle r}

with polynomial coefficients

p_{k}\in \mathbb {K} [n]

, polynomial right-hand side

{\textstyle f\in \mathbb {K} [n]}

and rational sequence solution

{\textstyle y(n)\in \mathbb {K} (n)}

. It is possible to write

{\textstyle y(n)=p(n)/q(n)}

for two relatively prime polynomials

{\textstyle p,q\in \mathbb {K} [n]}

. Let

{\textstyle D=\operatorname {dis} (p_{r}(n-r),p_{0}(n))}

and

u(n)=\gcd([p_{0}(n+D)]^{\underline {D+1}},[p_{r}(n-r)]^{\underline {D+1}})

where

{\textstyle [p(n)]^{\underline {k}}=p(n)p(n-1)\cdots p(n-k+1)}

denotes the falling factorial of a function. Then

{\textstyle q(n)}

divides

{\textstyle u(n)}

. So the polynomial

{\textstyle u(n)}

can be used as a denominator for all rational solutions

{\textstyle y(n)}

and hence it is called a universal denominator.^[5]

Algorithm edit

Let again ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$ be a recurrence equation with polynomial coefficients and ${\textstyle u(n)}$ a universal denominator. After substituting ${\textstyle y(n)=z(n)/u(n)}$ for an unknown polynomial ${\textstyle z(n)\in \mathbb {K} [n]}$ and setting ${\textstyle \ell (n)=\operatorname {lcm} (u(n),\dots ,u(n+r))}$ the recurrence equation is equivalent to

\sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n).

As the

{\textstyle u(n+k)}

cancel this is a linear recurrence equation with polynomial coefficients which can be solved for an unknown polynomial solution

{\textstyle z(n)}

. There are algorithms to find polynomial solutions. The solutions for

{\textstyle z(n)}

can then be used again to compute the rational solutions

{\textstyle y(n)=z(n)/u(n)}

. ^[2]

algorithm rational_solutions is
    input: Linear recurrence equation  ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n),p_{k},f\in \mathbb {K} [n],p_{0},p_{r}\neq 0}$ .
    output: The general rational solution  ${\textstyle y}$  if there are any solutions, otherwise false.

     ${\textstyle D=\operatorname {disp} (p_{r}(n-r),p_{0}(n))}$ 
     ${\textstyle u(n)=\gcd([p_{0}(n+D)]^{\underline {D+1}},[p_{r}(n-r)]^{\underline {D+1}})}$ 
     ${\textstyle \ell (n)=\operatorname {lcm} (u(n),\dots ,u(n+r))}$ 
    Solve  ${\textstyle \sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n)}$  for general polynomial solution  ${\textstyle z(n)}$ 
    if solution  ${\textstyle z(n)}$  exists then
        return general solution  ${\textstyle y(n)=z(n)/u(n)}$ 
    else
        return false
    end if

Example edit

The homogeneous recurrence equation of order ${\textstyle 1}$

(n-1)\,y(n)+(-n-1)\,y(n+1)=0

over

{\textstyle \mathbb {Q} }

has a rational solution. It can be computed by considering the dispersion

D=\operatorname {dis} (p_{1}(n-1),p_{0}(n))=\operatorname {disp} (-n,n-1)=1.

This yields the following universal denominator:

u(n)=\gcd([p_{0}(n+1)]^{\underline {2}},[p_{r}(n-1)]^{\underline {2}})=(n-1)n

and

\ell (n)=\operatorname {lcm} (u(n),u(n+1))=(n-1)n(n+1).

Multiplying the original recurrence equation with

{\textstyle \ell (n)}

and substituting

{\textstyle y(n)=z(n)/u(n)}

leads to

(n-1)(n+1)\,z(n)+(-n-1)(n-1)\,z(n+1)=0.

This equation has the polynomial solution

{\textstyle z(n)=c}

for an arbitrary constant

{\textstyle c\in \mathbb {Q} }

. Using

{\textstyle y(n)=z(n)/u(n)}

the general rational solution is

y(n)={\frac {c}{(n-1)n}}

for arbitrary

{\textstyle c\in \mathbb {Q} }

.

References edit

^ Abramov, Sergei A. (1989). "Rational solutions of linear differential and difference equations with polynomial coefficients". USSR Computational Mathematics and Mathematical Physics. 29 (6): 7–12. doi:10.1016/s0041-5553(89)80002-3. ISSN 0041-5553.
^ ^a ^b Abramov, Sergei A. (1995). "Rational solutions of linear difference and q -difference equations with polynomial coefficients". Proceedings of the 1995 international symposium on Symbolic and algebraic computation - ISSAC '95. pp. 285–289. doi:10.1145/220346.220383. ISBN 978-0897916998. S2CID 15424889.
^ Man, Yiu-Kwong; Wright, Francis J. (1994). "Fast polynomial dispersion computation and its application to indefinite summation". Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC '94. pp. 175–180. doi:10.1145/190347.190413. ISBN 978-0897916387. S2CID 2192728.
^ Gerhard, Jürgen (2005). Modular Algorithms in Symbolic Summation and Symbolic Integration. Lecture Notes in Computer Science. Vol. 3218. doi:10.1007/b104035. ISBN 978-3-540-24061-7. ISSN 0302-9743.
^ Chen, William Y. C.; Paule, Peter; Saad, Husam L. (2007). "Converging to Gosper's Algorithm". arXiv:0711.3386 [math.CA].

WikiProject Mathematics on Wikidata

[1] Abramov, Sergei A. (1989). "Rational solutions of linear differential and difference equations with polynomial coefficients". USSR Computational Mathematics and Mathematical Physics. 29 (6): 7–12. doi:10.1016/s0041-5553(89)80002-3. ISSN 0041-5553.

[Abramov_1995-2] Abramov, Sergei A. (1995). "Rational solutions of linear difference and q -difference equations with polynomial coefficients". Proceedings of the 1995 international symposium on Symbolic and algebraic computation - ISSAC '95. pp. 285–289. doi:10.1145/220346.220383. ISBN 978-0897916998. S2CID 15424889.

[3] Man, Yiu-Kwong; Wright, Francis J. (1994). "Fast polynomial dispersion computation and its application to indefinite summation". Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC '94. pp. 175–180. doi:10.1145/190347.190413. ISBN 978-0897916387. S2CID 2192728.

[4] Gerhard, Jürgen (2005). Modular Algorithms in Symbolic Summation and Symbolic Integration. Lecture Notes in Computer Science. Vol. 3218. doi:10.1007/b104035. ISBN 978-3-540-24061-7. ISSN 0302-9743.

[5] Chen, William Y. C.; Paule, Peter; Saad, Husam L. (2007). "Converging to Gosper's Algorithm". arXiv:0711.3386 [math.CA].

[1]

[2]

[3]

[4]

[5]

Summary

Universal denominator edit

Algorithm edit

Example edit

References edit