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
The main concept in Abramov's algorithm is a universal denominator. Let
be a field of characteristic zero. The dispersion
of two polynomials
is defined as
![{\displaystyle \operatorname {dis} (p,q)=\max\{k\in \mathbb {N} \,:\,\deg(\gcd(p(n),q(n+k)))\geq 1\}\cup \{-1\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac39a7fe185688a05e3f44e63cc235436749277d)
where
![{\textstyle \mathbb {N} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/a2d54af08511d5aa5601af546c787c263505d621)
denotes the set of non-negative integers. Therefore the dispersion is the maximum
![{\textstyle k\in \mathbb {N} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/b359d27f09d61f7e77a0bae3c5d8b5e4227ec85f)
such that the polynomial
![{\textstyle p}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad87bd7009e2a5c52bd0fb5a9bda9d8c1c23a79b)
and the
![{\textstyle k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d5595fc0c47452f8fc2aa6e29c3611f047714b0)
-times shifted polynomial
![{\displaystyle q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/06809d64fa7c817ffc7e323f85997f783dbdf71d)
have a common factor. It is
![{\textstyle -1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e03d0251b380d21d87eb1cd07628008e254050c3)
if such a
![{\textstyle k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d5595fc0c47452f8fc2aa6e29c3611f047714b0)
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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/320e230996024a30e89c8e9f727bdc95cfc287b8)
.
[3][4] Let
![{\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ec2e21026868642f83c9b8e946f9eab0d3f7cba)
be a recurrence equation of order
![{\textstyle r}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2dfb06630b52c9e18fcc0a4688da10774206729)
with polynomial coefficients
![{\displaystyle p_{k}\in \mathbb {K} [n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99a01d50ae357ea8203df5b2f6cc55dc93819501)
, polynomial right-hand side
![{\textstyle f\in \mathbb {K} [n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1630da272da3f2909cddd06710cb3f885ef1cd25)
and rational sequence solution
![{\textstyle y(n)\in \mathbb {K} (n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/09743763a28e6100aa268e73bc0765772470440e)
. It is possible to write
![{\textstyle y(n)=p(n)/q(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff7ef6a052034a35fbbd9eab323f8fc6f2600ef3)
for two relatively prime polynomials
![{\textstyle p,q\in \mathbb {K} [n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/36bcc87d3123b013a99b2fa730743a44a6a60db8)
. Let
![{\textstyle D=\operatorname {dis} (p_{r}(n-r),p_{0}(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05b365b3f827c6aa41ac0db613cf9b293bf83bd2)
and
![{\displaystyle u(n)=\gcd([p_{0}(n+D)]^{\underline {D+1}},[p_{r}(n-r)]^{\underline {D+1}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23b6a2e862fdeab2c12ec82af1bb0e9f9f7d68de)
where
![{\textstyle [p(n)]^{\underline {k}}=p(n)p(n-1)\cdots p(n-k+1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6aa8c3540431b8056a7e751814de7c71a0054bc2)
denotes the
falling factorial of a function. Then
![{\textstyle q(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/696017a9b696b80d6c4df68fb2226532bd37bffd)
divides
![{\textstyle u(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e8f0958673f39b2b7c757ae24ec59948fd8723e)
. So the polynomial
![{\textstyle u(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e8f0958673f39b2b7c757ae24ec59948fd8723e)
can be used as a denominator for all rational solutions
![{\textstyle y(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd92c672ca7c544a538590e34b15e7346a853acf)
and hence it is called a universal denominator.
[5] Algorithm
Let again
be a recurrence equation with polynomial coefficients and
a universal denominator. After substituting
for an unknown polynomial
and setting
the recurrence equation is equivalent to
![{\displaystyle \sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/80d62ca3baafb8755724944d27471df896b4016e)
As the
![{\textstyle u(n+k)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b53add14d4827ecde981da40eb50dd55ff74cf6)
cancel this is a linear recurrence equation with polynomial coefficients which can be solved for an unknown polynomial solution
![{\textstyle z(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac83ed6935b034f76f783f23a817b00ab56f493a)
. There are
algorithms to find polynomial solutions. The solutions for
![{\textstyle z(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac83ed6935b034f76f783f23a817b00ab56f493a)
can then be used again to compute the rational solutions
![{\textstyle y(n)=z(n)/u(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/514c8b21a8c9029508b340979086f26d11c560a3)
.
[2] algorithm rational_solutions is
input: Linear recurrence equation
.
output: The general rational solution
if there are any solutions, otherwise false.
Solve
for general polynomial solution
if solution
exists then
return general solution
else
return false
end if
Example
The homogeneous recurrence equation of order ![{\textstyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6706df9ed9f240d1a94545fb4e522bda168fe8fd)
![{\displaystyle (n-1)\,y(n)+(-n-1)\,y(n+1)=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5430f1e182acc251977c562eb4e64a1871a339f6)
over
![{\textstyle \mathbb {Q} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/d381b6fc0b446b7f503e2af3a5d73e4e1da6600f)
has a rational solution. It can be computed by considering the dispersion
![{\displaystyle D=\operatorname {dis} (p_{1}(n-1),p_{0}(n))=\operatorname {disp} (-n,n-1)=1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84107aa9dc4302faf1edcf82fcb898816773c73c)
This yields the following universal denominator:
![{\displaystyle u(n)=\gcd([p_{0}(n+1)]^{\underline {2}},[p_{r}(n-1)]^{\underline {2}})=(n-1)n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a788d308c3a83d2d6916118a30edf810258ea45f)
and
![{\displaystyle \ell (n)=\operatorname {lcm} (u(n),u(n+1))=(n-1)n(n+1).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a341e64f5b7f134332b4a6f820b634068b9c4c51)
Multiplying the original recurrence equation with
![{\textstyle \ell (n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/98a80c29d06338aeb0dd32f6ccfb6f5c93d4efed)
and substituting
![{\textstyle y(n)=z(n)/u(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/514c8b21a8c9029508b340979086f26d11c560a3)
leads to
![{\displaystyle (n-1)(n+1)\,z(n)+(-n-1)(n-1)\,z(n+1)=0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/137211bc1b23b33ccc55e40b3c343e1916405217)
This equation has the polynomial solution
![{\textstyle z(n)=c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a01ac0626c5c9f92089aa0d6ea2e5094f4a283e)
for an arbitrary constant
![{\textstyle c\in \mathbb {Q} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/1594121e1a51be5f5df51e073b0e2ee1a76c29aa)
. Using
![{\textstyle y(n)=z(n)/u(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/514c8b21a8c9029508b340979086f26d11c560a3)
the general rational solution is
![{\displaystyle y(n)={\frac {c}{(n-1)n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13988dc8d9531e75b94327bd07833da7a163f6e7)
for arbitrary
![{\textstyle c\in \mathbb {Q} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/1594121e1a51be5f5df51e073b0e2ee1a76c29aa)
.
References
- ^ 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 |