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{}{}{0ex}{}{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).

$\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$

$L≔E^3-3E^2+3E-1$

$L≔E^3-3E^2+3E-1$

$\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-2x-{\mathrm{\_Z}}_1-{\mathrm{\_Z}}_2-1\,''a\; family\; of\; dimension''\,2\,''with\; equations''\,\varnothing \right]\right\}$

$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+3x+3\right)E^2+\left(x^2+c\right)\left({\left(x+1\right)}^2+c\right)$

$\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\}$

$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-2x\left(x^2+3x+146\right)E^2+\left(x-2\right)x\left(x+1\right)\left(x+2\right)$

$\mathrm{RightFactors}\left(L\,2\right)$

$\left\{\left(x-1\right)\left(2x-1\right)\left(x^6-3x^5+37x^4-69x^3+277x^2-243x+315\right)x{E}^2-\left(x-2\right)\left(2x+3\right)\left(x+2\right)\left(x+1\right)\left(x^6+9x^5+67x^4+267x^3+751x^2+1173x+945\right)\right\}$

$L≔\mathrm{LCLM}\left(E^4-Ex+1\,E^5+E^3-x\right)$

$L≔\left(x^6+10x^5+32x^4+24x^3-47x^2-66x-31\right)E^9+\left(-6x^4-41x^3-101x^2-104x-9\right)E^8+\left(x^6+10x^5+27x^4-17x^3-136x^2-142x-92\right)E^7+\left(-x^7-15x^6-82x^5-196x^4-178x^3-2x^2+92x+134\right)E^6+\left(x^6+16x^5+92x^4+231x^3+243x^2+20x-138\right)E^5+\left(-2x^7-29x^6-154x^5-342x^4-186x^3+353x^2+491x+267\right)E^4+\left(x^6+22x^5+156x^4+496x^3+739x^2+417x-50\right)E^3+\left(5x^5+51x^4+171x^3+254x^2+213x+122\right)E^2+\left(x^8+16x^7+97x^6+272x^5+327x^4+38x^3-295x^2-339x-143\right)E-x^7-16x^6-97x^5-272x^4-332x^3-96x^2+77x$

$\mathrm{RightFactors}\left(L\,'\mathrm{Heuristic}'\right)$

$\left\{E^5+E^3-x\right\}$

$\mathrm{RightFactors}\left(L\,'\mathrm{DegreeBounds}'\right)$

$\left[-\mathrm{\infty }\,-\mathrm{\infty }\,-\mathrm{\infty }\,1\,1\,2\,-\mathrm{\infty }\,-\mathrm{\infty }\,8\right]$

$\mathrm{RightFactors}\left(L\,'\mathrm{LCLM}'\right)$

$\left\{E^4-xE+1\,E^5+E^3-x\right\}$

$\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-xE+1\right\},\left\{E^5+E^3-x\right\},\varnothing ,\varnothing ,\varnothing$

$L≔\mathrm{MultiplyOperators}\left(L\,E-x\right)$

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

$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-xE+x^2\right\}$

$\mathrm{add}\left(\mathrm{degree}\left(i\,E\right)\,i=S\right)$

$11$

$\mathrm{degree}\left(L\,E\right)$

$10$

$L≔E^4+1$

$L≔E^4+1$

$\mathrm{RightFactors}\left(L\,2\right)$

$\varnothing$

$\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\}$

$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)+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$

$\mathrm{RightFactors}\left(R\,2\right)$

$\left\{nu\left(n+2\right)-n\left(n+2\right)u\left(n+1\right)+\left(-n-2\right)u\left(n\right)=0\right\}$

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).

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

For more information on Maple 2021 changes, see Updates in Maple 2021.