RightFactors - Maple Help

LREtools

 RightFactors
 factor linear difference operators

 Calling Sequence RightFactors(L, d, K)

Parameters

 L - linear difference operator, or a recurrence relation d - a positive integer, DegreeBounds, Heuristic, or LCLM K - (optional) a set with field extensions

Description

 • For the syntax of difference operators, and their relation to recurrence relations, see LREtools[MultiplyOperators]. The names of the shift operator and independent variable are selected by assigning them to _Env_LRE_tau and _Env_LRE_x.
 • If $E$ is the shift operator and $x$ is the independent variable, then a difference operator is an element of ${C\left(x\right)}_{E}$, and can be written as $L$ = ${a}_{n}\left(x\right){E}^{n}$ + ... + ${a}_{0}\left(x\right)$ for rational functions ${a}_{i}\left(x\right)$ in $C\left(x\right)$. Multiplication in this non-commutative ring corresponds to composition of difference operators. If ${a}_{0}\left(x\right)$ and ${a}_{n}\left(x\right)$ are both non-zero, then the order of $L$ is $n$.
 • The optional argument K has the same role as in factor. If omitted, RightFactors assumes that the field of constants $C$ is the smallest field for which $L$ is in ${C\left(x\right)}_{\mathrm{\tau }}$. In most applications $C$ is the field of rational numbers. If a set K is specified, then C will be extended with the algebraic expressions in K.
 • If d is a positive integer, then RightFactors(L, d, K) returns the set of all right-factors of order d of L in ${C\left(x\right)}_{E}$. This is not equivalent to factoring in ${C}_{x,E}$ because operators that are reducible in ${C\left(x\right)}_{E}$ are often irreducible in ${C}_{x,E}$. Right factors of order $d=1$ are equivalent to hypergeometric solutions. If R is a right-factor of L, then the corresponding left-factor can then be obtained with RightDivision.
 • Denominators of right-factors will be cleared so they are written as elements of ${C}_{x,E}$ (the corresponding left-factors will be in ${C\left(x\right)}_{E}$). The degree of a right-factor R with respect to x is often higher than the degree of the input L. This makes it non-trivial to find right-factors or to bound their degrees. If the second argument is DegreeBounds then instead of computing right-factors, the command returns a list $\left[{b}_{1},{b}_{2},\mathrm{...}\right]$, where ${b}_{d}$ is an upper bound for the degree of any order-d right-factor. Such bounds are needed to obtain a recurrence relation of provably minimal order (see MinimalRecurrence). If ${b}_{d}=-\mathrm{\infty }$ then there are no right-factors of order d (however, the degree bounds need not be sharp, so if ${b}_{d}$ is not $-\mathrm{\infty }$, it does not imply that L has a right-factor of order d).
 • There can be infinitely many right-factors of order d, in which case the output will have members of the form $\left[R,"a family of dimension",f,"with equations",\mathrm{eq}\right]$, with R of the form ${R}_{0}$ + ${\mathrm{_Z}}_{1}{R}_{1}$ + ... + ${\mathrm{_Z}}_{m}{R}_{m}$ for some ${R}_{i}$ in ${C}_{x,E}$. This R will be a right-factor of L if and only if one substitutes values for ${\mathrm{_Z}}_{1}$, ..., ${\mathrm{_Z}}_{m}$ that satisfy the equations $\mathrm{eq}$. These equations are Plücker relations (they are quadratic equations), and have an f-dimensional solution space. The set eq will be empty if d is 1 or n-1 (in which case f equals the number of variables ${\mathrm{_Z}}_{i}$).
 • If the second argument is Heuristic, then a heuristic algorithm will be used. It can be much faster when $\left(\genfrac{}{}{0}{}{n-1}{d-1}\right)$ is large, but it need not find every factor.
 • If the second argument is LCLM, then the output will be a finite set $S$ = {${L}_{1}$,${L}_{2}$,...}, such that $L=\mathrm{LCLM}\left({L}_{1},{L}_{2},\mathrm{...}\right)$, and every element of $S$ is not an LCLM of lower order operators. If ${L}_{i}$ is an element of the output $S$, then ${L}_{i}$ need not be irreducible, but it will have only one irreducible left-factor (that is equivalent to ${L}_{i}$ not being an LCLM of lower order operators). Every solution of $L$ can be written as a sum of solutions of ${L}_{1}$, ${L}_{2}$, ... . (see SumDecompose).

Examples

 > $\mathrm{with}\left(\mathrm{LREtools}\right):$
 > $\mathrm{_Env_LRE_tau}≔E;$$\mathrm{_Env_LRE_x}≔x$
 ${\mathrm{_Env_LRE_tau}}{≔}{E}$
 ${\mathrm{_Env_LRE_x}}{≔}{x}$ (1)
 > $L≔{E}^{3}-3{E}^{2}+3E-1$
 ${L}{≔}{{E}}^{{3}}{-}{3}{}{{E}}^{{2}}{+}{3}{}{E}{-}{1}$ (2)

L has a right-factor E - E(u)/(u) for every non-zero solution u = u0+u1x+u2x^2. So the first order right-factors be parametrized by 3 homogeneous parameters (u0:u1:u2), or with 0, 1, and 2 inhomogeneous parameters:

 > $\mathrm{RightFactors}\left(L,1\right)$
 $\left\{{E}{-}{1}{,}\left[\left({x}{+}{{\mathrm{_Z}}}_{{1}}\right){}{E}{-}{x}{-}{{\mathrm{_Z}}}_{{1}}{-}{1}{,}{"a family of dimension"}{,}{1}{,}{"with equations"}{,}{\varnothing }\right]{,}\left[\left({{x}}^{{2}}{+}{{\mathrm{_Z}}}_{{2}}{}{x}{+}{{\mathrm{_Z}}}_{{1}}\right){}{E}{-}{{x}}^{{2}}{-}{{\mathrm{_Z}}}_{{2}}{}{x}{-}{2}{}{x}{-}{{\mathrm{_Z}}}_{{1}}{-}{{\mathrm{_Z}}}_{{2}}{-}{1}{,}{"a family of dimension"}{,}{2}{,}{"with equations"}{,}{\varnothing }\right]\right\}$ (3)
 > $L≔{E}^{4}-2\left({x}^{2}+c+3x+3\right){E}^{2}+\left({x}^{2}+c\right)\left({\left(x+1\right)}^{2}+c\right)$
 ${L}{≔}{{E}}^{{4}}{-}{2}{}\left({{x}}^{{2}}{+}{c}{+}{3}{}{x}{+}{3}\right){}{{E}}^{{2}}{+}\left({{x}}^{{2}}{+}{c}\right){}\left({\left({x}{+}{1}\right)}^{{2}}{+}{c}\right)$ (4)

Here the input contains a parameter c, so the field of constants is Q(c) in this example.

 > $\mathrm{RightFactors}\left(L,2\right)$
 $\left\{{{E}}^{{2}}{-}{E}{-}{{x}}^{{2}}{-}{c}{,}{{E}}^{{2}}{+}{E}{-}{{x}}^{{2}}{-}{c}{,}\left[\left({x}{+}{{\mathrm{_Z}}}_{{1}}\right){}{{E}}^{{2}}{+}{{\mathrm{_Z}}}_{{2}}{}{E}{-}\left({{x}}^{{2}}{+}{c}\right){}\left({x}{+}{{\mathrm{_Z}}}_{{1}}{+}{1}\right){,}{"a family of dimension"}{,}{1}{,}{"with equations"}{,}\left\{{{\mathrm{_Z}}}_{{1}}^{{2}}{-}{{\mathrm{_Z}}}_{{2}}^{{2}}{+}{c}\right\}\right]\right\}$ (5)
 > $L≔\left(x+1\right)\left(x+2\right){E}^{4}-2x\left({x}^{2}+3x+146\right){E}^{2}+\left(x-2\right)x\left(x+1\right)\left(x+2\right)$
 ${L}{≔}\left({x}{+}{1}\right){}\left({x}{+}{2}\right){}{{E}}^{{4}}{-}{2}{}{x}{}\left({{x}}^{{2}}{+}{3}{}{x}{+}{146}\right){}{{E}}^{{2}}{+}\left({x}{-}{2}\right){}{x}{}\left({x}{+}{1}\right){}\left({x}{+}{2}\right)$ (6)
 > $\mathrm{RightFactors}\left(L,2\right)$
 $\left\{\left({x}{-}{1}\right){}\left({2}{}{x}{-}{1}\right){}\left({{x}}^{{6}}{-}{3}{}{{x}}^{{5}}{+}{37}{}{{x}}^{{4}}{-}{69}{}{{x}}^{{3}}{+}{277}{}{{x}}^{{2}}{-}{243}{}{x}{+}{315}\right){}{x}{}{{E}}^{{2}}{-}\left({x}{-}{2}\right){}\left({2}{}{x}{+}{3}\right){}\left({x}{+}{2}\right){}\left({x}{+}{1}\right){}\left({{x}}^{{6}}{+}{9}{}{{x}}^{{5}}{+}{67}{}{{x}}^{{4}}{+}{267}{}{{x}}^{{3}}{+}{751}{}{{x}}^{{2}}{+}{1173}{}{x}{+}{945}\right)\right\}$ (7)
 > $L≔\mathrm{LCLM}\left({E}^{4}-Ex+1,{E}^{5}+{E}^{3}-x\right)$
 ${L}{≔}\left({{x}}^{{6}}{+}{10}{}{{x}}^{{5}}{+}{32}{}{{x}}^{{4}}{+}{24}{}{{x}}^{{3}}{-}{47}{}{{x}}^{{2}}{-}{66}{}{x}{-}{31}\right){}{{E}}^{{9}}{+}\left({-}{6}{}{{x}}^{{4}}{-}{41}{}{{x}}^{{3}}{-}{101}{}{{x}}^{{2}}{-}{104}{}{x}{-}{9}\right){}{{E}}^{{8}}{+}\left({{x}}^{{6}}{+}{10}{}{{x}}^{{5}}{+}{27}{}{{x}}^{{4}}{-}{17}{}{{x}}^{{3}}{-}{136}{}{{x}}^{{2}}{-}{142}{}{x}{-}{92}\right){}{{E}}^{{7}}{+}\left({-}{{x}}^{{7}}{-}{15}{}{{x}}^{{6}}{-}{82}{}{{x}}^{{5}}{-}{196}{}{{x}}^{{4}}{-}{178}{}{{x}}^{{3}}{-}{2}{}{{x}}^{{2}}{+}{92}{}{x}{+}{134}\right){}{{E}}^{{6}}{+}\left({{x}}^{{6}}{+}{16}{}{{x}}^{{5}}{+}{92}{}{{x}}^{{4}}{+}{231}{}{{x}}^{{3}}{+}{243}{}{{x}}^{{2}}{+}{20}{}{x}{-}{138}\right){}{{E}}^{{5}}{+}\left({-}{2}{}{{x}}^{{7}}{-}{29}{}{{x}}^{{6}}{-}{154}{}{{x}}^{{5}}{-}{342}{}{{x}}^{{4}}{-}{186}{}{{x}}^{{3}}{+}{353}{}{{x}}^{{2}}{+}{491}{}{x}{+}{267}\right){}{{E}}^{{4}}{+}\left({{x}}^{{6}}{+}{22}{}{{x}}^{{5}}{+}{156}{}{{x}}^{{4}}{+}{496}{}{{x}}^{{3}}{+}{739}{}{{x}}^{{2}}{+}{417}{}{x}{-}{50}\right){}{{E}}^{{3}}{+}\left({5}{}{{x}}^{{5}}{+}{51}{}{{x}}^{{4}}{+}{171}{}{{x}}^{{3}}{+}{254}{}{{x}}^{{2}}{+}{213}{}{x}{+}{122}\right){}{{E}}^{{2}}{+}\left({{x}}^{{8}}{+}{16}{}{{x}}^{{7}}{+}{97}{}{{x}}^{{6}}{+}{272}{}{{x}}^{{5}}{+}{327}{}{{x}}^{{4}}{+}{38}{}{{x}}^{{3}}{-}{295}{}{{x}}^{{2}}{-}{339}{}{x}{-}{143}\right){}{E}{-}{{x}}^{{7}}{-}{16}{}{{x}}^{{6}}{-}{97}{}{{x}}^{{5}}{-}{272}{}{{x}}^{{4}}{-}{332}{}{{x}}^{{3}}{-}{96}{}{{x}}^{{2}}{+}{77}{}{x}$ (8)
 > $\mathrm{RightFactors}\left(L,'\mathrm{Heuristic}'\right)$
 $\left\{{{E}}^{{5}}{+}{{E}}^{{3}}{-}{x}\right\}$ (9)
 > $\mathrm{RightFactors}\left(L,'\mathrm{DegreeBounds}'\right)$
 $\left[{-}{\mathrm{\infty }}{,}{-}{\mathrm{\infty }}{,}{-}{\mathrm{\infty }}{,}{1}{,}{1}{,}{2}{,}{-}{\mathrm{\infty }}{,}{-}{\mathrm{\infty }}{,}{8}\right]$ (10)

The DegreeBounds show that there can be no right-factors of orders 1, 2, 3, 7 or 8.

 > $\mathrm{RightFactors}\left(L,'\mathrm{LCLM}'\right)$
 $\left\{{{E}}^{{4}}{-}{x}{}{E}{+}{1}{,}{{E}}^{{5}}{+}{{E}}^{{3}}{-}{x}\right\}$ (11)

The degree-bound for d=4 and d=5 was sharp, but not the degree bound for d=6 since there is no right-factor of that order:

 > $\mathrm{seq}\left(\mathrm{RightFactors}\left(L,d\right),d=1..\mathrm{degree}\left(L,E\right)-1\right)$
 ${\varnothing }{,}{\varnothing }{,}{\varnothing }{,}\left\{{{E}}^{{4}}{-}{x}{}{E}{+}{1}\right\}{,}\left\{{{E}}^{{5}}{+}{{E}}^{{3}}{-}{x}\right\}{,}{\varnothing }{,}{\varnothing }{,}{\varnothing }$ (12)
 > $L≔\mathrm{MultiplyOperators}\left(L,E-x\right)$
 ${L}{≔}\left({{x}}^{{6}}{+}{10}{}{{x}}^{{5}}{+}{32}{}{{x}}^{{4}}{+}{24}{}{{x}}^{{3}}{-}{47}{}{{x}}^{{2}}{-}{66}{}{x}{-}{31}\right){}{{E}}^{{10}}{+}\left({-}{{x}}^{{7}}{-}{19}{}{{x}}^{{6}}{-}{122}{}{{x}}^{{5}}{-}{318}{}{{x}}^{{4}}{-}{210}{}{{x}}^{{3}}{+}{388}{}{{x}}^{{2}}{+}{521}{}{x}{+}{270}\right){}{{E}}^{{9}}{+}\left({{x}}^{{6}}{+}{16}{}{{x}}^{{5}}{+}{116}{}{{x}}^{{4}}{+}{412}{}{{x}}^{{3}}{+}{776}{}{{x}}^{{2}}{+}{699}{}{x}{-}{20}\right){}{{E}}^{{8}}{+}\left({-}{2}{}{{x}}^{{7}}{-}{32}{}{{x}}^{{6}}{-}{179}{}{{x}}^{{5}}{-}{368}{}{{x}}^{{4}}{+}{77}{}{{x}}^{{3}}{+}{1092}{}{{x}}^{{2}}{+}{1178}{}{x}{+}{778}\right){}{{E}}^{{7}}{+}\left({{x}}^{{8}}{+}{21}{}{{x}}^{{7}}{+}{173}{}{{x}}^{{6}}{+}{704}{}{{x}}^{{5}}{+}{1446}{}{{x}}^{{4}}{+}{1301}{}{{x}}^{{3}}{+}{163}{}{{x}}^{{2}}{-}{666}{}{x}{-}{942}\right){}{{E}}^{{6}}{+}\left({-}{3}{}{{x}}^{{7}}{-}{50}{}{{x}}^{{6}}{-}{326}{}{{x}}^{{5}}{-}{1033}{}{{x}}^{{4}}{-}{1584}{}{{x}}^{{3}}{-}{882}{}{{x}}^{{2}}{+}{529}{}{x}{+}{957}\right){}{{E}}^{{5}}{+}\left({2}{}{{x}}^{{8}}{+}{37}{}{{x}}^{{7}}{+}{271}{}{{x}}^{{6}}{+}{980}{}{{x}}^{{5}}{+}{1710}{}{{x}}^{{4}}{+}{887}{}{{x}}^{{3}}{-}{1164}{}{{x}}^{{2}}{-}{1814}{}{x}{-}{1118}\right){}{{E}}^{{4}}{+}\left({-}{{x}}^{{7}}{-}{25}{}{{x}}^{{6}}{-}{217}{}{{x}}^{{5}}{-}{913}{}{{x}}^{{4}}{-}{2056}{}{{x}}^{{3}}{-}{2380}{}{{x}}^{{2}}{-}{988}{}{x}{+}{272}\right){}{{E}}^{{3}}{+}\left({{x}}^{{8}}{+}{16}{}{{x}}^{{7}}{+}{92}{}{{x}}^{{6}}{+}{211}{}{{x}}^{{5}}{+}{54}{}{{x}}^{{4}}{-}{558}{}{{x}}^{{3}}{-}{1016}{}{{x}}^{{2}}{-}{887}{}{x}{-}{387}\right){}{{E}}^{{2}}{+}\left({-}{{x}}^{{9}}{-}{17}{}{{x}}^{{8}}{-}{114}{}{{x}}^{{7}}{-}{385}{}{{x}}^{{6}}{-}{696}{}{{x}}^{{5}}{-}{637}{}{{x}}^{{4}}{-}{75}{}{{x}}^{{3}}{+}{538}{}{{x}}^{{2}}{+}{559}{}{x}{+}{143}\right){}{E}{+}{{x}}^{{2}}{}\left({{x}}^{{6}}{+}{16}{}{{x}}^{{5}}{+}{97}{}{{x}}^{{4}}{+}{272}{}{{x}}^{{3}}{+}{332}{}{{x}}^{{2}}{+}{96}{}{x}{-}{77}\right)$ (13)
 > $S≔\mathrm{RightFactors}\left(L,'\mathrm{LCLM}'\right)$
 ${S}{≔}\left\{{{E}}^{{5}}{+}\left({-}{x}{-}{4}\right){}{{E}}^{{4}}{-}{x}{}{{E}}^{{2}}{+}\left({{x}}^{{2}}{+}{x}{+}{1}\right){}{E}{-}{x}{,}{{E}}^{{6}}{+}\left({-}{x}{-}{5}\right){}{{E}}^{{5}}{+}{{E}}^{{4}}{+}\left({-}{x}{-}{3}\right){}{{E}}^{{3}}{-}{x}{}{E}{+}{{x}}^{{2}}\right\}$ (14)
 > $\mathrm{add}\left(\mathrm{degree}\left(i,E\right),i=S\right)$
 ${11}$ (15)
 > $\mathrm{degree}\left(L,E\right)$
 ${10}$ (16)
 > $L≔{E}^{4}+1$
 ${L}{≔}{{E}}^{{4}}{+}{1}$ (17)
 > $\mathrm{RightFactors}\left(L,2\right)$
 ${\varnothing }$ (18)
 > $\mathrm{RightFactors}\left(L,2,\left\{\mathrm{sqrt}\left(2\right)\right\}\right)$
 $\left\{{{E}}^{{2}}{-}\sqrt{{2}}{}{E}{+}{1}{,}{{E}}^{{2}}{+}\sqrt{{2}}{}{E}{+}{1}\right\}$ (19)

This next recurrence is listed at oeis.org/A000179:

 > $R≔u\left(n\right)+nu\left(n+1\right)-2u\left(n+2\right)-\left(n+4\right)u\left(n+3\right)+u\left(n+4\right)=0$
 ${R}{≔}{u}{}\left({n}\right){+}{n}{}{u}{}\left({n}{+}{1}\right){-}{2}{}{u}{}\left({n}{+}{2}\right){-}\left({n}{+}{4}\right){}{u}{}\left({n}{+}{3}\right){+}{u}{}\left({n}{+}{4}\right){=}{0}$ (20)
 > $\mathrm{RightFactors}\left(R,2\right)$
 $\left\{{n}{}{u}{}\left({n}{+}{2}\right){-}{n}{}\left({n}{+}{2}\right){}{u}{}\left({n}{+}{1}\right){+}\left({-}{n}{-}{2}\right){}{u}{}\left({n}\right){=}{0}\right\}$ (21)

Any solution of this right-factor is also a solution of R, which helps to find closed form solutions of R.

References

 M. Bronstein. "Factorization and hypergeometric solutions of linear recurrence systems." (Ideas due to Manual Bronstein, presented at the conference in memory of Manuel Bronstein). URL www.math.fsu.edu/~hoeij/slides/bronstein/slides.pdf (2006).
 M. van Hoeij. "Factoring Linear Recurrence Operators." URL www.math.fsu.edu/~hoeij/2019/slides.pdf
 Y. Zhou and M. van Hoeij. "Fast Algorithm for Factoring Difference operators", ACM Communications in Computer Algebra. Vol. 53, No. 3 (2019).

Compatibility

 • The LREtools[RightFactors] command was introduced in Maple 2021.