GeneralizedExponents - Maple Help

LREtools

 GeneralizedExponents
 compute the generalized exponents of a difference operator

 Calling Sequence GeneralizedExponents(L, K) GeneralizedExponents(L, x, tau, K)

Parameters

 L - linear difference operator x - name for the independent variable tau - name for the shift operator K - (optional) set of algebraic extensions

Description

 • If $E$ is the shift operator, then a difference operator $L$ = ${a}_{d}{E}^{d}$ + ... + ${a}_{0}$ represents a recurrence relation ${a}_{d}\left(x\right)u\left(x+d\right)$ + ... + ${a}_{0}\left(x\right)u\left(x\right)$ = 0. A generalized exponent of $L$ is an algebraic expression that encodes the asymptotic behavior (as $x$ -> $\mathrm{\infty }$) of a solution of $L$. A precise definition is found in section 4 in the reference below, but a description in terms of examples is given here.
 • A non-zero solution $u$ of $L$ corresponds to a first-order right-hand factor $E-r$ of $L$ where $r$ = $\frac{E\left(u\right)}{u}$ = $\frac{u\left(x+1\right)}{u\left(x\right)}$. If $r$ is a rational function then $u$ is called a hypergeometric solution but that is not assumed here.
 • The asymptotic behavior of $u$ as $x$ -> $\mathrm{\infty }$ is determined by the asymptotic behavior of $r$ as $x$ -> $\mathrm{\infty }$, which in turn can be represented with a series expansion at $x=\mathrm{\infty }$. Ignoring logarithmic terms, this expansion takes the form $r$ = $c{x}^{v}$ (1 + ${c}_{1}{x}^{-\frac{1}{n}}$ + ${c}_{2}{x}^{-\frac{2}{n}}$ + ...) for some constants $c$, ${c}_{1}$, ${c}_{2}$, ..., a rational number v, and positive integer $n$.
 • The only terms ${c}_{i}{x}^{-\frac{i}{n}}$ in this sum with a significant contribution to the asymptotic behavior of $u$ are terms with $\frac{i}{n}\le 1$. Discarding terms with $1<\frac{i}{n}$ and logarithmic terms, what remains is the generalized exponent $e$ := $c{x}^{v}$ (1 + ${c}_{1}{x}^{-\frac{1}{n}}$ + ${c}_{2}{x}^{-\frac{2}{n}}$ + ... $\frac{{c}_{n}}{x}$) for a solution $u$.
 • For example, if $u$ is a polynomial solution of degree $N$, then $u$  = constant  (${x}^{N}$ + less dominant terms). Then $\frac{E\left(u\right)}{u}$ = 1 + $\frac{N}{x}$ + less dominant terms, and so $e=1+\frac{N}{x}$ is the generalized exponent of $u$.
 • If $u={c}^{x}$ then $\frac{E\left(u\right)}{u}=c$, so in this case the generalized exponent of $u$ is $c$. If $u=\mathrm{\Gamma }\left(x\right)$ then $\frac{E\left(u\right)}{u}=x$ and so $e=x$ in this example.
 • Multiplying solutions corresponds to multiplying generalized exponents (and deleting terms ${c}_{i}{x}^{-\frac{i}{n}}$ with $1<\frac{i}{n}$). So if $u={c}^{x}{x}^{N}{\mathrm{\Gamma }\left(x\right)}^{v}$ is a solution of $L$, then $e=c{x}^{v}\left(1+\frac{N}{x}\right)$ is a generalized exponent of $L$. This is used in LREtools[hypergeomsols] to narrow the search.
 • Fractional powers of $x$ can only appear if $L$ has order > 1, in which case the order will be at most $n$. The GeneralizedExponents command will represent $e$ in the form $\mathrm{T1}\left(1+\mathrm{T2}\right)$  ...  $\left(1+\mathrm{Tk}\right)\left(1+\frac{N}{x}\right)$ where $\mathrm{T1}=c{x}^{v}$ for some constant $c$ and rational number $v$. Each $\mathrm{T2}$, $\mathrm{T3}$, ... is of the form ${c}_{i}{x}^{-\frac{i}{n}}$ for some constant ${c}_{i}$ and rational number 0 < $\frac{i}{n}$ < 1, and will be given implicitly in the form of an equation. In the output, each $e$ is presented as a list, in which each variable is $\mathrm{T1}$, $\mathrm{T2}$, ... is defined in terms of prior variables. The notation $N$ = list means that $N$ runs through all elements of that list, which may contain duplicates because generalized exponents have multiplicities.
 • Counting with multiplicities, the number of generalized exponents will be equal to the order of $L$, however, the algorithm will only give one $e$ in every conjugacy class over $C\left(\frac{1}{x}\right)$, where $C$ is the smallest field of constants that contains the coefficients of $L$ as well as the extensions in the optional argument $K$.
 • The generalized exponents of any right-factor $R$ of $L$ form a subset of the generalized exponents of $L$. This is used to compute right-factors efficiently, and makes it possible to quickly compute degree-bounds for right-factors of $L$.

Examples

 > $\mathrm{with}\left(\mathrm{LREtools}\right):$
 > $L≔{E}^{2}-x$
 ${L}{≔}{{E}}^{{2}}{-}{x}$ (1)
 > $\mathrm{ge}≔\mathrm{GeneralizedExponents}\left(L,x,E\right)$
 ${\mathrm{ge}}{≔}\left\{\left[{\mathrm{T1}}{}\left({1}{+}\frac{{N}}{{x}}\right){,}{{\mathrm{T1}}}^{{2}}{=}{x}{,}{N}{=}\left[{-}\frac{{1}}{{4}}\right]\right]\right\}$ (2)
 > $e≔\mathrm{ge}\left[1\right]$
 ${e}{≔}\left[{\mathrm{T1}}{}\left({1}{+}\frac{{N}}{{x}}\right){,}{{\mathrm{T1}}}^{{2}}{=}{x}{,}{N}{=}\left[{-}\frac{{1}}{{4}}\right]\right]$ (3)

The optional argument K was omitted, so the field of constants is Q here. The equation T1^2 = x has two solutions, and so although the output lists only one e, it represents T1  (1 - (1/4)/x) for both T1 = x^(1/2) and for T1 = -x^(1/2). Counted this way, the number of generalized exponents matches the order of the input.

The names for the independent variable and the shift operator may be omitted from the input when they have been assigned to _Env_LRE_x and _Env_LRE_tau:

 > $\mathrm{_Env_LRE_x}≔x$
 ${\mathrm{_Env_LRE_x}}{≔}{x}$ (4)
 > $\mathrm{_Env_LRE_tau}≔E$
 ${\mathrm{_Env_LRE_tau}}{≔}{E}$ (5)
 > $\mathrm{GeneralizedExponents}\left(L\right)$
 $\left\{\left[{\mathrm{T1}}{}\left({1}{+}\frac{{N}}{{x}}\right){,}{{\mathrm{T1}}}^{{2}}{=}{x}{,}{N}{=}\left[{-}\frac{{1}}{{4}}\right]\right]\right\}$ (6)

Any operator with L as right-factor will have L's generalized exponents (for left factors, this holds for terms other than the N/x term). This helps to detect factors efficiently.

 > $\mathrm{L2}≔\mathrm{LCLM}\left(L,{E}^{2}-x-1,{E}^{4}+{E}^{3}+2{E}^{2}x+{x}^{2}\right)$
 ${\mathrm{L2}}{≔}\left({256}{}{{x}}^{{6}}{+}{2784}{}{{x}}^{{5}}{+}{11505}{}{{x}}^{{4}}{+}{22536}{}{{x}}^{{3}}{+}{20923}{}{{x}}^{{2}}{+}{7496}{}{x}{+}{122}\right){}{{E}}^{{8}}{+}\left({256}{}{{x}}^{{6}}{+}{2912}{}{{x}}^{{5}}{+}{12713}{}{{x}}^{{4}}{+}{26588}{}{{x}}^{{3}}{+}{27269}{}{{x}}^{{2}}{+}{12484}{}{x}{+}{1766}\right){}{{E}}^{{7}}{+}\left({-}{768}{}{{x}}^{{6}}{-}{9280}{}{{x}}^{{5}}{-}{42905}{}{{x}}^{{4}}{-}{95556}{}{{x}}^{{3}}{-}{106161}{}{{x}}^{{2}}{-}{54352}{}{x}{-}{9266}\right){}{{E}}^{{6}}{+}\left({-}{512}{}{{x}}^{{7}}{-}{8256}{}{{x}}^{{6}}{-}{53482}{}{{x}}^{{5}}{-}{178405}{}{{x}}^{{4}}{-}{326480}{}{{x}}^{{3}}{-}{323499}{}{{x}}^{{2}}{-}{159312}{}{x}{-}{29766}\right){}{{E}}^{{5}}{+}\left({-}{512}{}{{x}}^{{8}}{-}{8896}{}{{x}}^{{7}}{-}{62434}{}{{x}}^{{6}}{-}{226115}{}{{x}}^{{5}}{-}{443306}{}{{x}}^{{4}}{-}{433839}{}{{x}}^{{3}}{-}{121064}{}{{x}}^{{2}}{+}{99674}{}{x}{+}{57908}\right){}{{E}}^{{4}}{+}\left({256}{}{{x}}^{{8}}{+}{4960}{}{{x}}^{{7}}{+}{40505}{}{{x}}^{{6}}{+}{181387}{}{{x}}^{{5}}{+}{485301}{}{{x}}^{{4}}{+}{791893}{}{{x}}^{{3}}{+}{768780}{}{{x}}^{{2}}{+}{407034}{}{x}{+}{90552}\right){}{{E}}^{{3}}{+}\left({-}{256}{}{{x}}^{{8}}{-}{4800}{}{{x}}^{{7}}{-}{37619}{}{{x}}^{{6}}{-}{160764}{}{{x}}^{{5}}{-}{408389}{}{{x}}^{{4}}{-}{627288}{}{{x}}^{{3}}{-}{562190}{}{{x}}^{{2}}{-}{263264}{}{x}{-}{47544}\right){}{{E}}^{{2}}{+}\left({-}{128}{}{{x}}^{{8}}{-}{2232}{}{{x}}^{{7}}{-}{16612}{}{{x}}^{{6}}{-}{68782}{}{{x}}^{{5}}{-}{172684}{}{{x}}^{{4}}{-}{268054}{}{{x}}^{{3}}{-}{250364}{}{{x}}^{{2}}{-}{128464}{}{x}{-}{27744}\right){}{E}{+}{256}{}{{x}}^{{10}}{+}{5088}{}{{x}}^{{9}}{+}{42737}{}{{x}}^{{8}}{+}{197951}{}{{x}}^{{7}}{+}{552319}{}{{x}}^{{6}}{+}{949181}{}{{x}}^{{5}}{+}{979382}{}{{x}}^{{4}}{+}{553718}{}{{x}}^{{3}}{+}{131244}{}{{x}}^{{2}}$ (7)
 > $\mathrm{GeneralizedExponents}\left(\mathrm{L2}\right)$
 $\left\{\left[{\mathrm{T1}}{}\left({1}{+}\frac{{N}}{{x}}\right){,}{{\mathrm{T1}}}^{{2}}{=}{x}{,}{N}{=}\left[{-}\frac{{1}}{{4}}{,}\frac{{1}}{{4}}\right]\right]{,}\left[{\mathrm{T1}}{}\left({1}{+}{\mathrm{T2}}\right){}\left({1}{+}{\mathrm{T3}}\right){}\left({1}{+}{\mathrm{T4}}\right){}\left({1}{+}\frac{{N}}{{x}}\right){,}{{\mathrm{T1}}}^{{2}}{=}{-}{x}{,}{{\mathrm{T2}}}^{{2}}{=}{-}\frac{{1}}{{4}{}{\mathrm{T1}}}{,}{\mathrm{T3}}{=}{-}\frac{{1}}{{4}{}{\mathrm{T1}}}{,}{\mathrm{T4}}{=}{-}\frac{{31}}{{128}{}{x}{}{\mathrm{T2}}}{,}{N}{=}\left[{-}\frac{{43}}{{64}}\right]\right]\right\}$ (8)

This contains the generalized exponents of each right-factor of L2, see

 > $\mathrm{GeneralizedExponents}\left({E}^{2}-x-1\right)$
 $\left\{\left[{\mathrm{T1}}{}\left({1}{+}\frac{{N}}{{x}}\right){,}{{\mathrm{T1}}}^{{2}}{=}{x}{,}{N}{=}\left[\frac{{1}}{{4}}\right]\right]\right\}$ (9)

and

 > $\mathrm{GeneralizedExponents}\left({E}^{4}+{E}^{3}+2{E}^{2}x+{x}^{2}\right)$
 $\left\{\left[{\mathrm{T1}}{}\left({1}{+}{\mathrm{T2}}\right){}\left({1}{+}{\mathrm{T3}}\right){}\left({1}{+}{\mathrm{T4}}\right){}\left({1}{+}\frac{{N}}{{x}}\right){,}{{\mathrm{T1}}}^{{2}}{=}{-}{x}{,}{{\mathrm{T2}}}^{{2}}{=}{-}\frac{{1}}{{4}{}{\mathrm{T1}}}{,}{\mathrm{T3}}{=}{-}\frac{{1}}{{4}{}{\mathrm{T1}}}{,}{\mathrm{T4}}{=}{-}\frac{{31}}{{128}{}{x}{}{\mathrm{T2}}}{,}{N}{=}\left[{-}\frac{{43}}{{64}}\right]\right]\right\}$ (10)

References

 Y. Cha, M. van Hoeij, G. Levy.  "Solving Recurrence Relations using Local Invariants." ISSAC'2010 Proceedings.

Compatibility

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