GCRD - Maple Help

LREtools

 MultiplyOperators
 multiply linear difference operators
 GCRD
 Greatest Common Right Divisor of linear difference operators
 LCLM
 Least Common Left Multiple of linear difference operators
 RightDivision
 divide two linear difference operators
 RecurrenceToOperator
 convert a recurrence relation to a difference operator
 OperatorToRecurrence
 convert a difference operator to a recurrence relation

 Calling Sequence MultiplyOperators(L1, L2, ...) GCRD(L1, L2, ...) LCLM(L1, L2, ...) RightDivision(L1, L2) RecurrenceToOperator(R, dvar) OperatorToRecurrence(L, dvar)

Parameters

 L1,L2, ... - linear difference operators R - recurrence dvar - dependent variable

Description

 • The shift operator (often denoted as $E$, $S$, or $\mathrm{\tau }$) acts on functions by adding +1 to the independent variable (often denoted as $n$ or $x$). If for example the shift operator is denoted with $E$, and the independent variable by $x$, then $E$ is the operator that sends an expression $u\left(x\right)$ to $u\left(x+1\right)$.
 • One can choose the name of the shift operator by assigning it to _Env_LRE_tau, and the name of the independent variable by assigning it to _Env_LRE_x. If these environment variables are assigned then they will be used to denote the shift operator and independent variable.
 • An operator $L$ in ${C\left(x\right)}_{E}$ 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)$. If the dependent variable dvar is for example $u\left(x\right)$, then the equation $L\left(u\left(x\right)\right)=0$ is the recurrence relation ${a}_{n}\left(x\right)u\left(x+n\right)$ + ... + ${a}_{0}\left(x\right)u\left(x\right)$ = 0. So a difference operator represents a linear homogeneous recurrence relation. Converting representations can be done with the RecurrenceToOperator and OperatorToRecurrence commands.
 • The product $L$ := $\mathrm{MultiplyOperators}\left(\mathrm{L1},\mathrm{L2}\right)$ corresponds to composition of linear difference operators. For example, if $E$ is the shift operator and $x$ is the independent variable, then $E$ will send any expression $u\left(x\right)$ to $u\left(x+1\right)$, while the operator $x$ sends $u\left(x\right)$ to $xu\left(x\right)$. The product $xE$ sends $u\left(x\right)$ to $x\left(E\left(u\left(x\right)\right)\right)$ = $x\left(u\left(x+1\right)\right)$ = $xu\left(x+1\right)$ while the product $xE$ sends $u\left(x\right)$ to $E\left(x\left(u\left(x\right)\right)\right)$ = $E\left(xu\left(x\right)\right)$ = $\left(x+1\right)u\left(x+1\right)$. So $xE$ acts the same as $\left(x+1\right)E$, which means that the operator $xE$ equals the operator $\left(x+1\right)E$.
 • If $L$ := $\mathrm{MultiplyOperators}\left(\mathrm{L1},\mathrm{L2}\right)$ and if $u\left(x\right)$ is a solution of $\mathrm{L2}$, in other words $\mathrm{L2}\left(u\left(x\right)\right)=0$, then $L\left(u\left(x\right)\right)$ = $\mathrm{L1}\left(\mathrm{L2}\left(u\left(x\right)\right)\right)$ = $\mathrm{L1}\left(0\right)$ = $0$. So right-factors of $L$ are important for solving $L$ because solutions of right-factors are also a solutions of $L$ (this is not true for left-factors, which is why GCLD/LCRM/LeftDivision are omitted here).
 • The assignment $L$ := $\mathrm{LCLM}\left(\mathrm{L1},\mathrm{L2}\right)$ computes the Least Common Left Multiple of operators $\mathrm{L1}$ and $\mathrm{L2}$, which means that $\mathrm{L1}$ and $\mathrm{L2}$ are right-factors of $L$, and $L$ is minimal with this property. Then the solution space of $L$ is the sum of the solution spaces of $\mathrm{L1}$ and $\mathrm{L2}$. The same functionality is provided by gfun[rec+rec]. Difference operators are also a special case of Ore operators.
 • The assignment $L$ := $\mathrm{GCRD}\left(\mathrm{L1},\mathrm{L2}\right)$ computes the Greatest Common Right Divisor of $\mathrm{L1}$ and $\mathrm{L2}$, which means that $L$ is a right-factor of both $\mathrm{L1}$ and $\mathrm{L2}$, and is maximal with this property. Then the solution space of $L$ is the intersection of the solution spaces of $\mathrm{L1}$ and $\mathrm{L2}$.
 • One may specify more than two operators in MultiplyOperators, GCRD, or LCLM. For instance, $L$ := $\mathrm{LCLM}\left(\mathrm{L1},\mathrm{L2},\mathrm{L3}\right)$ is the Least Common Left Multiple of $\mathrm{L1}$, $\mathrm{L2}$, $\mathrm{L3}$, so solutions of $L$ are sums of solutions of $\mathrm{L1}$, $\mathrm{L2}$, and $\mathrm{L3}$.
 • The assignment $Q,R$ := $\mathrm{RightDivision}\left(\mathrm{L1},\mathrm{L2}\right)$ right-divides $\mathrm{L1}$ by $\mathrm{L2}$. This means that $\mathrm{L1}=Q\mathrm{L2}+R$ where the order of $R$ is less than that of $\mathrm{L2}$. $R$ will be $0$ if and only if $\mathrm{L2}$ is a right-factor of $\mathrm{L1}$.

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)
 > $\mathrm{MultiplyOperators}\left(E,x\right)$
 $\left({x}{+}{1}\right){}{E}$ (2)
 > $\mathrm{L1}≔{E}^{2}-x$
 ${\mathrm{L1}}{≔}{{E}}^{{2}}{-}{x}$ (3)
 > $\mathrm{L2}≔{E}^{2}-E-x$
 ${\mathrm{L2}}{≔}{{E}}^{{2}}{-}{E}{-}{x}$ (4)
 > $L≔\mathrm{LCLM}\left(\mathrm{L1},\mathrm{L2}\right)$
 ${L}{≔}{{E}}^{{4}}{-}{{E}}^{{3}}{+}\left({-}{2}{}{x}{-}{3}\right){}{{E}}^{{2}}{+}\left({x}{+}{1}\right){}{E}{+}{{x}}^{{2}}{+}{x}$ (5)
 > $\mathrm{L3}≔\mathrm{MultiplyOperators}\left(E-x,\mathrm{L1}\right)$
 ${\mathrm{L3}}{≔}{{E}}^{{3}}{-}{x}{}{{E}}^{{2}}{+}\left({-}{x}{-}{1}\right){}{E}{+}{{x}}^{{2}}$ (6)
 > $\mathrm{GCRD}\left(L,\mathrm{L3}\right)$
 ${{E}}^{{2}}{-}{x}$ (7)
 > $Q,R≔\mathrm{RightDivision}\left(L,\mathrm{L3}\right)$
 ${Q}{,}{R}{≔}{E}{+}{x}{,}\left({{x}}^{{2}}{-}{x}{-}{1}\right){}{{E}}^{{2}}{-}{{x}}^{{3}}{+}{{x}}^{{2}}{+}{x}$ (8)

R is not zero so L3 is not a right-factor of L

 > $\mathrm{Lnew}≔\mathrm{MultiplyOperators}\left(Q,\mathrm{L3}\right)+R$
 ${\mathrm{Lnew}}{≔}{{E}}^{{4}}{-}{{E}}^{{3}}{+}\left({-}{{x}}^{{2}}{-}{x}{-}{2}\right){}{{E}}^{{2}}{+}\left({x}{+}{1}\right){}{E}{+}\left({{x}}^{{2}}{-}{x}{-}{1}\right){}{{E}}^{{2}}{+}{{x}}^{{2}}{+}{x}$ (9)
 > $\mathrm{expand}\left(L-\mathrm{Lnew}\right)$
 ${0}$ (10)
 > $\mathrm{Op}≔\mathrm{RecurrenceToOperator}\left(u\left(n+3\right)+2u\left(n+1\right)+5nu\left(n\right)=0,u\left(n\right)\right)$
 ${\mathrm{Op}}{≔}{{E}}^{{3}}{+}{2}{}{E}{+}{5}{}{x}$ (11)
 > $\mathrm{rec}≔\mathrm{OperatorToRecurrence}\left(\mathrm{Op},u\left(n\right)\right)$
 ${\mathrm{rec}}{≔}{u}{}\left({n}{+}{3}\right){+}{2}{}{u}{}\left({n}{+}{1}\right){+}{5}{}{n}{}{u}{}\left({n}\right){=}{0}$ (12)

Compatibility

 • The LREtools[MultiplyOperators], LREtools[GCRD], LREtools[LCLM], LREtools[RightDivision], LREtools[RecurrenceToOperator] and LREtools[OperatorToRecurrence] commands were introduced in Maple 2021.