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 because $n$ is at most the order. 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$(($\frac{1}{x}$)), 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$.

$\mathrm{with}\left(\mathrm{LREtools}\right)\&colon;$

$L≔E^2-x$

$L≔E^2-x$

$\mathrm{ge}≔\mathrm{GeneralizedExponents}\left(L\&comma;x\&comma;E\right)$

$\mathrm{ge}≔\left\{\left[\mathrm{T1}\left(1+\frac{N}{x}\right)\&comma;{\mathrm{T1}}^2=x\&comma;N=\left[-\frac{1}{4}\right]\right]\right\}$

$e≔\mathrm{ge}\left[1\right]$

$e≔\left[\mathrm{T1}\left(1+\frac{N}{x}\right)\&comma;{\mathrm{T1}}^2=x\&comma;N=\left[-\frac{1}{4}\right]\right]$

$\mathrm{\_Env\_LRE\_x}≔x$

$\mathrm{\_Env\_LRE\_x}≔x$

$\mathrm{\_Env\_LRE\_tau}≔E$

$\mathrm{\_Env\_LRE\_tau}≔E$

$\mathrm{GeneralizedExponents}\left(L\right)$

$\left\{\left[\mathrm{T1}\left(1+\frac{N}{x}\right)\&comma;{\mathrm{T1}}^2=x\&comma;N=\left[-\frac{1}{4}\right]\right]\right\}$

$\mathrm{L2}≔\mathrm{LCLM}\left(L\&comma;E^2-x-1\&comma;E^4+E^3+2E^{2}x+x^2\right)$

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

$\mathrm{GeneralizedExponents}\left(\mathrm{L2}\right)$

$\left\{\left[\mathrm{T1}\left(1+\frac{N}{x}\right)\&comma;{\mathrm{T1}}^2=x\&comma;N=\left[-\frac{1}{4}\&comma;\frac{1}{4}\right]\right]\&comma;\left[\mathrm{T1}\left(1+\mathrm{T2}\right)\left(1+\mathrm{T3}\right)\left(1+\mathrm{T4}\right)\left(1+\frac{N}{x}\right)\&comma;{\mathrm{T1}}^2=-x\&comma;{\mathrm{T2}}^2=-\frac{1}{4\mathrm{T1}}\&comma;\mathrm{T3}=-\frac{1}{4\mathrm{T1}}\&comma;\mathrm{T4}=-\frac{31}{128x\mathrm{T2}}\&comma;N=\left[-\frac{43}{64}\right]\right]\right\}$

$\mathrm{GeneralizedExponents}\left(E^2-x-1\right)$

$\left\{\left[\mathrm{T1}\left(1+\frac{N}{x}\right)\&comma;{\mathrm{T1}}^2=x\&comma;N=\left[\frac{1}{4}\right]\right]\right\}$

$\mathrm{GeneralizedExponents}\left(E^4+E^3+2E^{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)\&comma;{\mathrm{T1}}^2=-x\&comma;{\mathrm{T2}}^2=-\frac{1}{4\mathrm{T1}}\&comma;\mathrm{T3}=-\frac{1}{4\mathrm{T1}}\&comma;\mathrm{T4}=-\frac{31}{128x\mathrm{T2}}\&comma;N=\left[-\frac{43}{64}\right]\right]\right\}$

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

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

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