QRationalCanonicalForm - Maple Help

QDifferenceEquations

 QRationalCanonicalForm
 construct four q-rational canonical forms of a rational function

 Calling Sequence QRationalCanonicalForm[1](F, q, n) QRationalCanonicalForm[2](F, q, n) QRationalCanonicalForm[3](F, q, n) QRationalCanonicalForm[4](F, q, n)

Parameters

 F - rational function of n q - name used as the parameter q, usually q n - variable

Description

 • Let F be a rational function of n over a field K of characteristic 0, q is a nonzero element of K which is not a root of unity. The QRationalCanonicalForm[i](F,q,n) command constructs the $i$th rational canonical form for F, $i=\left\{1,2,3,4\right\}$.
 If QRationalCanonicalForm is called without an index, the first q-rational canonical form is constructed.
 • The output is a sequence of 5 elements $z,r,s,u,v$, called $\mathrm{qRNF}\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{z\left(\frac{r}{s}\right)Q\left(\frac{u}{v}\right)}{\left(\frac{u}{v}\right)}$, $\mathrm{gcd}\left(u,v\right)=1$.
 2 $\mathrm{gcd}\left(r,{Q}^{k\left(s\right)}\right)$ for all integers $k$.
 3 $u\left(0\right)\ne 0$, $v\left(0\right)\ne 0$.
 4 $\mathrm{gcd}\left(r,Q·E\left(v\right)\right)=1$, $\mathrm{gcd}\left(s,Q\left(u\right)·v\right)=1$.
 Note: Q is the automorphism of K(n) defined by $Q\left(F\left(n\right)\right)=F\left(qn\right)$.
 • The five-tuple $z,r,s,u,v$ that satisfies the four conditions is a strict q-rational normal form for F. The rational function $\frac{zr}{s}$ and $\frac{u}{v}$ are called the kernel and the shell of the $\mathrm{qRNF}\left(F\right)$, respectively.
 • Let $\mathrm{\phi }=\left(z,r,s,u,v\right)$ be any qRNF 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)Q\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)$.
 • Additionally, 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{QDifferenceEquations}\right):$
 > $\mathrm{\nu }≔\left(n+{q}^{2}\right){q}^{11}\left(n+1\right)\left(n+{q}^{5}-{q}^{3}\right)\left(n+{q}^{4}-{q}^{2}\right)\left({q}^{3}n+{q}^{2}-1\right)\left({q}^{12}n+{q}^{2}-1\right):$
 > $\mathrm{de}≔\left(n+{q}^{5}\right){\left(n+{q}^{4}\right)}^{2}{q}^{11}\left({q}^{4}n+1\right)\left(n+{q}^{2}-1\right)\left({q}^{2}n+{q}^{2}-1\right):$
 > $F≔\frac{\mathrm{\nu }}{\mathrm{de}}$
 ${F}{≔}\frac{\left({{q}}^{{2}}{+}{n}\right){}\left({n}{+}{1}\right){}\left({{q}}^{{5}}{-}{{q}}^{{3}}{+}{n}\right){}\left({{q}}^{{4}}{-}{{q}}^{{2}}{+}{n}\right){}\left({{q}}^{{3}}{}{n}{+}{{q}}^{{2}}{-}{1}\right){}\left({{q}}^{{12}}{}{n}{+}{{q}}^{{2}}{-}{1}\right)}{\left({{q}}^{{5}}{+}{n}\right){}{\left({{q}}^{{4}}{+}{n}\right)}^{{2}}{}\left({{q}}^{{4}}{}{n}{+}{1}\right){}\left({{q}}^{{2}}{+}{n}{-}{1}\right){}\left({{q}}^{{2}}{}{n}{+}{{q}}^{{2}}{-}{1}\right)}$ (1)
 > $\mathrm{z1},\mathrm{r1},\mathrm{s1},\mathrm{u1},\mathrm{v1}≔\mathrm{QRationalCanonicalForm}\left[1\right]\left(F,q,n\right)$
 ${\mathrm{z1}}{,}{\mathrm{r1}}{,}{\mathrm{s1}}{,}{\mathrm{u1}}{,}{\mathrm{v1}}{≔}\frac{{1}}{{{q}}^{{10}}}{,}\left({{q}}^{{5}}{-}{{q}}^{{3}}{+}{n}\right){}\left({{q}}^{{4}}{-}{{q}}^{{2}}{+}{n}\right){,}\left({{q}}^{{5}}{+}{n}\right){}\left({n}{+}\frac{{1}}{{{q}}^{{4}}}\right){,}{\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{{q}}^{{2}}}\right)}^{{2}}{}{\left({{q}}^{{3}}{+}{n}\right)}^{{2}}{}{\left({{q}}^{{4}}{+}{n}\right)}^{{2}}{}\left({q}{+}{n}\right){}\left({{q}}^{{2}}{+}{n}\right){}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{{q}}^{{11}}}\right){}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{{q}}^{{10}}}\right){}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{{q}}^{{9}}}\right){}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{{q}}^{{8}}}\right){}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{{q}}^{{7}}}\right){}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{{q}}^{{6}}}\right){}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{{q}}^{{5}}}\right){}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{{q}}^{{4}}}\right){}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{{q}}^{{3}}}\right){}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{q}}\right){}\left({{q}}^{{2}}{+}{n}{-}{1}\right){,}{1}$ (2)
 > $\mathrm{z2},\mathrm{r2},\mathrm{s2},\mathrm{u2},\mathrm{v2}≔\mathrm{QRationalCanonicalForm}\left[2\right]\left(F,q,n\right)$
 ${\mathrm{z2}}{,}{\mathrm{r2}}{,}{\mathrm{s2}}{,}{\mathrm{u2}}{,}{\mathrm{v2}}{≔}{{q}}^{{18}}{,}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{{q}}^{{3}}}\right){}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{{q}}^{{12}}}\right){,}\left({{q}}^{{4}}{+}{n}\right){}\left({{q}}^{{5}}{+}{n}\right){,}\left({{q}}^{{3}}{+}{n}\right){}\left({{q}}^{{4}}{+}{n}\right){,}{\left({{q}}^{{3}}{+}{n}{-}{q}\right)}^{{2}}{}{\left({{q}}^{{4}}{-}{{q}}^{{2}}{+}{n}\right)}^{{2}}{}\left({n}{+}\frac{{1}}{{{q}}^{{3}}}\right){}\left({n}{+}\frac{{1}}{{{q}}^{{2}}}\right){}\left({n}{+}\frac{{1}}{{q}}\right){}\left({n}{+}{1}\right){}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{q}}\right){}\left({{q}}^{{2}}{+}{n}{-}{1}\right){}\left({{q}}^{{5}}{-}{{q}}^{{3}}{+}{n}\right)$ (3)
 > $\mathrm{z3},\mathrm{r3},\mathrm{s3},\mathrm{u3},\mathrm{v3}≔\mathrm{QRationalCanonicalForm}\left[3\right]\left(F,q,n\right)$
 ${\mathrm{z3}}{,}{\mathrm{r3}}{,}{\mathrm{s3}}{,}{\mathrm{u3}}{,}{\mathrm{v3}}{≔}{{q}}^{{4}}{,}\left({{q}}^{{5}}{-}{{q}}^{{3}}{+}{n}\right){}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{{q}}^{{12}}}\right){,}\left({{q}}^{{5}}{+}{n}\right){}\left({n}{+}\frac{{1}}{{{q}}^{{4}}}\right){,}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{{q}}^{{2}}}\right){}{\left({{q}}^{{3}}{+}{n}\right)}^{{2}}{}{\left({{q}}^{{4}}{+}{n}\right)}^{{2}}{}\left({q}{+}{n}\right){}\left({{q}}^{{2}}{+}{n}\right){,}\left({{q}}^{{3}}{+}{n}{-}{q}\right){}\left({{q}}^{{4}}{-}{{q}}^{{2}}{+}{n}\right)$ (4)
 > $\mathrm{z4},\mathrm{r4},\mathrm{s4},\mathrm{u4},\mathrm{v4}≔\mathrm{QRationalCanonicalForm}\left[4\right]\left(F,q,n\right)$
 ${\mathrm{z4}}{,}{\mathrm{r4}}{,}{\mathrm{s4}}{,}{\mathrm{u4}}{,}{\mathrm{v4}}{≔}{{q}}^{{12}}{,}\left({{q}}^{{5}}{-}{{q}}^{{3}}{+}{n}\right){}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{{q}}^{{12}}}\right){,}\left({{q}}^{{4}}{+}{n}\right){}\left({{q}}^{{5}}{+}{n}\right){,}\left({n}{+}\frac{{{q}}^{{2}}{-}{1}}{{{q}}^{{2}}}\right){}\left({{q}}^{{3}}{+}{n}\right){}\left({{q}}^{{4}}{+}{n}\right){,}\left({{q}}^{{3}}{+}{n}{-}{q}\right){}\left({{q}}^{{4}}{-}{{q}}^{{2}}{+}{n}\right){}\left({n}{+}\frac{{1}}{{{q}}^{{3}}}\right){}\left({n}{+}\frac{{1}}{{{q}}^{{2}}}\right){}\left({n}{+}\frac{{1}}{{q}}\right){}\left({n}{+}{1}\right)$ (5)

Check the result from QRationalCanonicalForm[2].

Condition 1 is satisfied.

 > $\mathrm{normal}\left(F-\frac{\mathrm{z2}\left(\frac{\mathrm{r2}}{\mathrm{s2}}\right)\mathrm{subs}\left(n=qn,\frac{\mathrm{u2}}{\mathrm{v2}}\right)}{\frac{\mathrm{u2}}{\mathrm{v2}}}\right),\mathrm{gcdex}\left(\mathrm{u2},\mathrm{v2},n\right)$
 ${0}{,}{1}$ (6)

Condition 2 is satisfied.

 > $\mathrm{QDispersion}\left(\mathrm{r2},\mathrm{s2},q,n\right),\mathrm{QDispersion}\left(\mathrm{s2},\mathrm{r2},q,n\right)$
 ${\mathrm{FAIL}}{,}{\mathrm{FAIL}}$ (7)

Condition 3 is satisfied.

 > $\mathrm{eval}\left(\mathrm{u2},n=0\right)\ne 0,\mathrm{normal}\left(\mathrm{eval}\left(\mathrm{v2},n=0\right)\right)\ne 0$
 ${{q}}^{{7}}{\ne }{0}{,}{\left({{q}}^{{2}}{-}{1}\right)}^{{7}}{}{{q}}^{{2}}{\ne }{0}$ (8)

Condition 4 is satisfied.

 > $\mathrm{gcdex}\left(\mathrm{r2},\mathrm{u2}\mathrm{subs}\left(n=qn,\mathrm{v2}\right),n\right),\mathrm{gcdex}\left(\mathrm{s2},\mathrm{subs}\left(n=qn,\mathrm{u2}\right)\mathrm{v2},n\right)$
 ${1}{,}{1}$ (9)

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}$ (10)
 > $\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)$
 ${2}{,}{2}{,}{2}{,}{2}$ (11)

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}{,}{11}{,}{2}{,}{6}$ (12)

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}{,}{2}{,}{7}{,}{3}$ (13)

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}{,}{13}{,}{9}{,}{9}$ (14)

References

 Abramov, S.A.; Le, H.Q.; and Petkovsek, M. "Efficient Representations of (q-)Hypergeometric Terms and the Assignment Problem." Submitted.
 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.