 SumTools[Hypergeometric] - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Summation and Difference Equations : SumTools : Hypergeometric Subpackage : SumTools/Hypergeometric/RationalCanonicalForm

SumTools[Hypergeometric]

 RationalCanonicalForm
 construct four rational canonical forms of a rational function

 Calling Sequence RationalCanonicalForm(F, n) RationalCanonicalForm(F, n) RationalCanonicalForm(F, n) RationalCanonicalForm(F, n)

Parameters

 F - rational function of n n - variable

Description

 • Let F be a rational function of n over a field K of characteristic 0. The RationalCanonicalForm[i](F,n) calling sequence constructs the ith rational canonical forms for F, $i=\left\{1,2,3,4\right\}$.
 If the RationalCanonicalForm command is called without an index, the first rational canonical form is constructed.
 • The output is a sequence of 5 elements $z,r,s,u,v$, called $\mathrm{RNF}\left(F\right)$, where z is an element of K, and $r,s,u,v$ are monic polynomials over K such that:
 1 $F=\frac{zrE\left(\frac{u}{v}\right)v}{su}$.
 2 $\mathrm{gcd}\left(r,{E}^{k\left(s\right)}\right)=1$ for all integers k.
 3 $\mathrm{gcd}\left(r,u·E\left(v\right)\right)=1$, $\mathrm{gcd}\left(s,E\left(u\right)·v\right)=1$.
 Note: E is the automorphism of K(n) defined by $E\left(F\left(n\right)\right)=F\left(n+1\right)$.
 • The five-tuple $z,r,s,u,v$ that satisfies the three conditions is a strict rational normal form for F. The rational functions $\frac{zr}{s}$ and $\frac{u}{v}$ are called the kernel and the shell of an $\mathrm{RNF}\left(F\right)$, respectively.
 • Let $\mathrm{\phi }=\left(z,r,s,u,v\right)$ be any RNF of a rational function F. Then the degrees of the polynomials r and s are unique, and have minimal possible values in the sense that if $F\left(n\right)=\frac{p\left(n\right)E\left(G\left(n\right)\right)}{q\left(n\right)G\left(n\right)}$ where p, q are polynomials in n, and G is a rational function of n, then $\mathrm{degree}\left(r\right)\le \mathrm{degree}\left(p\right)$ and $\mathrm{degree}\left(s\right)\le \mathrm{degree}\left(q\right)$.
 If $i=1$ then $\mathrm{degree}\left(v\right)$ is minimal.
 If $i=2$ then $\mathrm{degree}\left(u\right)$ is minimal.
 If $i=3$ then $\mathrm{degree}\left(u\right)+\mathrm{degree}\left(v\right)$ is minimal, and under this condition, $\mathrm{degree}\left(v\right)$ is minimal.
 If $i=4$ then $\mathrm{degree}\left(u\right)+\mathrm{degree}\left(v\right)$ is minimal, and under this condition, $\mathrm{degree}\left(u\right)$ is minimal.

Examples

 > $\mathrm{with}\left(\mathrm{SumTools}\left[\mathrm{Hypergeometric}\right]\right):$
 > $\mathrm{\nu }≔n\left(n+2\right)\left(n-4+\mathrm{sqrt}\left(2\right)\right)\left(n-3+\mathrm{sqrt}\left(2\right)\right)\left(n+2+\mathrm{sqrt}\left(2\right)\right)\left(n+11+\mathrm{sqrt}\left(2\right)\right)$
 ${\mathrm{\nu }}{≔}{n}{}\left({n}{+}{2}\right){}\left({n}{-}{4}{+}\sqrt{{2}}\right){}\left({n}{-}{3}{+}\sqrt{{2}}\right){}\left({n}{+}{2}{+}\sqrt{{2}}\right){}\left({n}{+}{11}{+}\sqrt{{2}}\right)$ (1)
 > $\mathrm{de}≔\left(n-3\right){\left(n-2\right)}^{2}\left(n+6\right)\left(n+12\right)\left(n-1+\mathrm{sqrt}\left(2\right)\right)\left(n+1+\mathrm{sqrt}\left(2\right)\right)$
 ${\mathrm{de}}{≔}\left({n}{-}{3}\right){}{\left({n}{-}{2}\right)}^{{2}}{}\left({n}{+}{6}\right){}\left({n}{+}{12}\right){}\left({n}{-}{1}{+}\sqrt{{2}}\right){}\left({n}{+}{1}{+}\sqrt{{2}}\right)$ (2)
 > $F≔\frac{\mathrm{\nu }}{\mathrm{de}}$
 ${F}{≔}\frac{{n}{}\left({n}{+}{2}\right){}\left({n}{-}{4}{+}\sqrt{{2}}\right){}\left({n}{-}{3}{+}\sqrt{{2}}\right){}\left({n}{+}{2}{+}\sqrt{{2}}\right){}\left({n}{+}{11}{+}\sqrt{{2}}\right)}{\left({n}{-}{3}\right){}{\left({n}{-}{2}\right)}^{{2}}{}\left({n}{+}{6}\right){}\left({n}{+}{12}\right){}\left({n}{-}{1}{+}\sqrt{{2}}\right){}\left({n}{+}{1}{+}\sqrt{{2}}\right)}$ (3)
 > $\mathrm{z1},\mathrm{r1},\mathrm{s1},\mathrm{u1},\mathrm{v1}≔\mathrm{RationalCanonicalForm}\left[1\right]\left(F,n\right)$
 ${\mathrm{z1}}{,}{\mathrm{r1}}{,}{\mathrm{s1}}{,}{\mathrm{u1}}{,}{\mathrm{v1}}{≔}{1}{,}\left({n}{-}{4}{+}\sqrt{{2}}\right){}\left({n}{-}{3}{+}\sqrt{{2}}\right){,}\left({n}{-}{3}\right){}\left({n}{+}{6}\right){}\left({n}{+}{12}\right){,}{\left({n}{+}{1}{+}\sqrt{{2}}\right)}^{{2}}{}{\left({n}{-}{1}\right)}^{{2}}{}{\left({n}{-}{2}\right)}^{{2}}{}\left({n}{+}{1}\right){}{n}{}\left({n}{+}{10}{+}\sqrt{{2}}\right){}\left({n}{+}{9}{+}\sqrt{{2}}\right){}\left({n}{+}{8}{+}\sqrt{{2}}\right){}\left({n}{+}{7}{+}\sqrt{{2}}\right){}\left({n}{+}{6}{+}\sqrt{{2}}\right){}\left({n}{+}{5}{+}\sqrt{{2}}\right){}\left({n}{+}{4}{+}\sqrt{{2}}\right){}\left({n}{+}{3}{+}\sqrt{{2}}\right){}\left({n}{+}{2}{+}\sqrt{{2}}\right){}\left({n}{+}\sqrt{{2}}\right){}\left({n}{-}{1}{+}\sqrt{{2}}\right){,}{1}$ (4)
 > $\mathrm{z2},\mathrm{r2},\mathrm{s2},\mathrm{u2},\mathrm{v2}≔\mathrm{RationalCanonicalForm}\left[2\right]\left(F,n\right)$
 ${\mathrm{z2}}{,}{\mathrm{r2}}{,}{\mathrm{s2}}{,}{\mathrm{u2}}{,}{\mathrm{v2}}{≔}{1}{,}\left({n}{+}{2}{+}\sqrt{{2}}\right){}\left({n}{+}{11}{+}\sqrt{{2}}\right){,}\left({n}{-}{3}\right){}{\left({n}{-}{2}\right)}^{{2}}{,}{1}{,}{\left({n}{-}{2}{+}\sqrt{{2}}\right)}^{{2}}{}{\left({n}{-}{3}{+}\sqrt{{2}}\right)}^{{2}}{}{\left({n}{+}{5}\right)}^{{2}}{}{\left({n}{+}{4}\right)}^{{2}}{}{\left({n}{+}{3}\right)}^{{2}}{}{\left({n}{+}{2}\right)}^{{2}}{}\left({n}{+}\sqrt{{2}}\right){}\left({n}{-}{1}{+}\sqrt{{2}}\right){}\left({n}{-}{4}{+}\sqrt{{2}}\right){}\left({n}{+}{11}\right){}\left({n}{+}{10}\right){}\left({n}{+}{9}\right){}\left({n}{+}{8}\right){}\left({n}{+}{7}\right){}\left({n}{+}{6}\right){}\left({n}{+}{1}\right){}{n}$ (5)
 > $\mathrm{z3},\mathrm{r3},\mathrm{s3},\mathrm{u3},\mathrm{v3}≔\mathrm{RationalCanonicalForm}\left[3\right]\left(F,n\right)$
 ${\mathrm{z3}}{,}{\mathrm{r3}}{,}{\mathrm{s3}}{,}{\mathrm{u3}}{,}{\mathrm{v3}}{≔}{1}{,}\left({n}{-}{4}{+}\sqrt{{2}}\right){}\left({n}{+}{11}{+}\sqrt{{2}}\right){,}\left({n}{-}{3}\right){}\left({n}{+}{6}\right){}\left({n}{+}{12}\right){,}\left({n}{+}{1}{+}\sqrt{{2}}\right){}{\left({n}{-}{1}\right)}^{{2}}{}{\left({n}{-}{2}\right)}^{{2}}{}\left({n}{+}{1}\right){}{n}{,}\left({n}{-}{2}{+}\sqrt{{2}}\right){}\left({n}{-}{3}{+}\sqrt{{2}}\right)$ (6)
 > $\mathrm{z4},\mathrm{r4},\mathrm{s4},\mathrm{u4},\mathrm{v4}≔\mathrm{RationalCanonicalForm}\left[4\right]\left(F,n\right)$
 ${\mathrm{z4}}{,}{\mathrm{r4}}{,}{\mathrm{s4}}{,}{\mathrm{u4}}{,}{\mathrm{v4}}{≔}{1}{,}\left({n}{-}{4}{+}\sqrt{{2}}\right){}\left({n}{+}{11}{+}\sqrt{{2}}\right){,}\left({n}{-}{3}\right){}\left({n}{-}{2}\right){}\left({n}{+}{12}\right){,}\left({n}{-}{1}\right){}\left({n}{-}{2}\right){}\left({n}{+}{1}{+}\sqrt{{2}}\right){,}\left({n}{+}{5}\right){}\left({n}{+}{4}\right){}\left({n}{+}{3}\right){}\left({n}{+}{2}\right){}\left({n}{-}{2}{+}\sqrt{{2}}\right){}\left({n}{-}{3}{+}\sqrt{{2}}\right)$ (7)

Check the result from RationalCanonicalForm.

Condition 1 is satisfied.

 > $\mathrm{evalb}\left(F=\mathrm{normal}\left(\frac{\mathrm{z1}\left(\frac{\mathrm{r1}}{\mathrm{s1}}\right)\mathrm{subs}\left(n=n+1,\frac{\mathrm{u1}}{\mathrm{v1}}\right)}{\frac{\mathrm{u1}}{\mathrm{v1}}}\right)\right)$
 ${\mathrm{true}}$ (8)

Condition 2 is satisfied.

 > $\mathrm{LREtools}\left[\mathrm{dispersion}\right]\left(\mathrm{r1},\mathrm{s1},n\right),\mathrm{LREtools}\left[\mathrm{dispersion}\right]\left(\mathrm{s1},\mathrm{r1},n\right)$
 ${\mathrm{FAIL}}{,}{\mathrm{FAIL}}$ (9)

Condition 3 is satisfied.

 > $\mathrm{gcd}\left(\mathrm{r1},\mathrm{u1}\mathrm{subs}\left(n=n+1,\mathrm{v1}\right)\right),\mathrm{gcd}\left(\mathrm{s1},\mathrm{subs}\left(n=n+1,\mathrm{u1}\right)\mathrm{v1}\right)$
 ${1}{,}{1}$ (10)

Degrees of the kernel:

 > $\mathrm{degree}\left(\mathrm{r1},n\right),\mathrm{degree}\left(\mathrm{r2},n\right),\mathrm{degree}\left(\mathrm{r3},n\right),\mathrm{degree}\left(\mathrm{r4},n\right)$
 ${2}{,}{2}{,}{2}{,}{2}$ (11)
 > $\mathrm{degree}\left(\mathrm{s1},n\right),\mathrm{degree}\left(\mathrm{s2},n\right),\mathrm{degree}\left(\mathrm{s3},n\right),\mathrm{degree}\left(\mathrm{s4},n\right)$
 ${3}{,}{3}{,}{3}{,}{3}$ (12)

The degree of v1 is minimal.

 > $\mathrm{degree}\left(\mathrm{v1},n\right),\mathrm{degree}\left(\mathrm{v2},n\right),\mathrm{degree}\left(\mathrm{v3},n\right),\mathrm{degree}\left(\mathrm{v4},n\right)$
 ${0}{,}{23}{,}{2}{,}{6}$ (13)

The degree of u2 is minimal.

 > $\mathrm{degree}\left(\mathrm{u1},n\right),\mathrm{degree}\left(\mathrm{u2},n\right),\mathrm{degree}\left(\mathrm{u3},n\right),\mathrm{degree}\left(\mathrm{u4},n\right)$
 ${19}{,}{0}{,}{7}{,}{3}$ (14)

For $i=3,4$, the degree of the shell is minimal.

 > $\mathrm{degree}\left(\mathrm{u1},n\right)+\mathrm{degree}\left(\mathrm{v1},n\right),\mathrm{degree}\left(\mathrm{u2},n\right)+\mathrm{degree}\left(\mathrm{v2},n\right),\mathrm{degree}\left(\mathrm{u3},n\right)+\mathrm{degree}\left(\mathrm{v3},n\right),\mathrm{degree}\left(\mathrm{u4},n\right)+\mathrm{degree}\left(\mathrm{v4},n\right)$
 ${19}{,}{23}{,}{9}{,}{9}$ (15)

References

 Abramov, S.A.; Le, H.Q.; and Petkovsek, M. "Rational Canonical Forms and Efficient Representations of Hypergeometric Terms." Proc. ISSAC'2003, pp. 7-14. 2003.
 Abramov, S.A., and Petkovsek, M. "Canonical representations of hypergeometric terms." Proc. FPSAC'2001, pp. 1-10. 2001.