This is a documentation of the package DalgSeq, a subpackage of our package NLDE.
This is not only the difference anologue of our work on D-algebraic functions. There are commands like CCfiniteToSimpleRatrec that makes no use of Gröbner bases to compute rational recursion for $C^2$-finite sequences. As usual, the purpose of our implementation is not only to support the theoretical approach, but also to serve as a basis for the investigation of more effective algorithms.
This package is based on the research detailed in the paper "Computing with D-algebraic Sequences", by the author of the package. A revised and complete version of this paper will be available on arXiv in a couple of weeks.
The source file of the package can be found here. For help in using Jupyter with Maple follow the link Maple-kernel-for-Jupyter. Those interested in trying the computations of this file in a Maple session (or worksheet) can download the file DalgSeq-Commands-and-Examples.mw on the GitHub repository.
In this notebook, we concentrate on the most practical commands of the subpackage DalgSeq.
In order to be able to use NLDE, one can just put the file NLDE.mla in the same directory with the notebook or the Maple worksheet.
We start by setting the (current) working directory as a directory for libraries.
restart
libname:=currentdir(),libname:
with(NLDE:-DalgSeq, OrderDegreeRec, unaryDalgSeq, arithmeticDalgSeq, CCfiniteToDalg, CCfiniteToSimpleRatrec, HoloToSimpleRatrec, DalgGuess)
Let us consider an algebraic difference equation satisfied by Bernoulli numbers.
ADE_Bernoulli:=5*s(n+3)*s(n)-6*s(n+2)*s(n+1)+s(n+1)*s(n)=0
Calling sequence: OrderDegreeRec(ADE,s(n))
ADE: An algebraic difference equation in the dependent variable s(n) (and the independent variable n).
s(n): s and n are variable names.
Description: Returns a list $[r,d]$, where $r$ and $d$ are the order and the (total) degree of ADE, respectively.
OrderDegreeRec(ADE_Bernoulli,s(n))
OrderDegreeRec(s(n)^2+s(n)-s(n+6)^3=0,s(n))
Calling sequence: unaryDalgSeq(ADE,s(n),z=r(s(n),s(n+1),...s(n+k-1))),options)
ADE: An autonomous algebraic difference equation in the dependent variable s(n), where n is the independent variable.
s(n): s and n are variable names.
z=r(s(n),s(n+1),...,s(n+r-1)): r is a rational function in s(n), s(n+1),...,s(n+k-1), where k represents the order. z is the variable name for the dependent variable in the output. Not all shifts of order less than the k are required to appear in the rational function.
Description: Computes a least-order algebraic differential equation that $r(s(n),s(n+1),\ldots,s(n+k-1))$ satisfies for large enough integers $n$, where $s(n)$ is a D-algebraic solution of the input ADE.
unaryDalgSeq(ADE_Bernoulli,s(n),z=s(n)+s(n+1))
Note that the Bernoulli sequence is not a D-algebraic solution of ADE_Bernoulli. The above equation is satisfied by sequences whose terms are sum of two consecutive terms of D-algebraic zeros of ADE_Bernoulli.
unaryDalgSeq(ADE_Bernoulli,s(n),z=s(n)/(s(n)+1))
Calling sequence: arithmeticDalgSeq([ADE1,...,ADEN],[s1(n),...,sN(n)],z=r(s1,...,sN))
[ADE1,...,ADEN]: A list of algebraic difference equations in the dependent variables s1(n),...,sN(n) given in the same order.
s1(n),...,sN(n): s1,...,sN, and n are variable names.
z=r(s1,...,sN): r is a rational function in s1,...,sN, and z is the variable name for the dependent variable in the output.
Description: Computes an algebraic difference equation (mostly of least order) that $r(s_1(n),\ldots,s_N(n))$ satisfies for large enough integers $n$, where $s_1(n),\ldots,s_N(n)$ are D-algebraic solutions of ADE1,...,ADEN, respectively.
ADE_Fibonacci:=F(n+2)=F(n)+F(n+1)
ADE_sum:=arithmeticDalgSeq([ADE_Bernoulli,ADE_Fibonacci],[s(n),F(n)],u=s+F)
OrderDegreeRec(ADE_sum,u(n))
ADE_A000301:=u(n+2)-u(n+1)*u(n)=0
ADE_A007018:=v(n+1)-v(n)^2-v(n)=0
These ADEs define interesting sequences from the Online Encyclopedia of Integer Sequences (OEIS). They are identified on there by A000301 and A007018.
ADE_ratio:=arithmeticDalgSeq([ADE_A000301,ADE_A007018],[u(n),v(n)],s=u/v)
OrderDegreeRec(ADE_ratio,s(n))
ADE_prod:=arithmeticDalgSeq([ADE_A000301,ADE_Fibonacci],[u(n),F(n)],s=u*F)
OrderDegreeRec(ADE_prod,s(n))
HugeADE:=arithmeticDalgSeq([ADE_A000301,ADE_Fibonacci],[u(n),F(n)],s=u+F^2):
kilobytes used=102263, alloc=28144, time=205.98
OrderDegreeRec(HugeADE,s(n))
This huge output is one of the reasons why the minimal order ADE might not always be the best choice.
Calling sequence: CCfiniteToDalg(CCeq,s(n),[CDE1,...,CDEN],[C1(n),...,CN(n)])
CCeq: A linear difference equation in the dependent variable s(n) with C-finite term coefficients, among which C1,...,CN linearly appear.
s(n): s and n are variable names.
[CDE1,...,CDEN]: A list of C-finite equations in the dependent variables C1(n),...,CN(n) given in the same order.
C1(n),...,CN(n): C1,...,CN, and n are variable names.
Description: Computes a least-order algebraic difference equation that has the same solutions as CCeq. Note, however, that the scope of the algorithm goes beyond the conversion of $C^2$-finite equation into ADE. In fact, CCeq can be a linear difference equation with $C^2$-finite terms coefficients. We refers to this algorithm as the slow algorithm as it depends on elimination with Gröbner bases. The next command is a much more faster implementation...
CDE1:=c(n+2)=2*c(n+1)+3*c(n)
CDE2:=F(n+2)=F(n)+F(n+1): #Fibonacci
CCfiniteToDalg(c*s(n)+F*s(n+1)=0,s(n),[CDE1,CDE2],[c(n),F(n)])
kilobytes used=135651, alloc=27120, time=333.72
CCfiniteToDalg(u*s(n) + 2*s(n + 1) + v*s(n + 2) = 0, s(n),[u(n + 2) - u(n) = 0, v(n + 2) - v(n) = 0], [u(n), v(n)])
kilobytes used=167554, alloc=27120, time=481.50
Calling sequence: CCfiniteToSimpleRatrec(CCeq,s(n),[CDE1,...,CDEN],[C1(n),...,CN(n)])
CCeq: A linear difference equation in the dependent variable s(n) with C-finite term coefficients, among which C1(n),...,CN(n) linearly appear. Notice that these coefficients appear with index variable unlike the syntax of CCfiniteToDalg.
s(n): s and n are variable names.
[CDE1,...,CDEN]: A list of C-finite equations in the dependent variables C1(n),...,CN(n) given in the same order.
C1(n),...,CN(n): C1,...,CN, and n are variable names.
Description: Computes the least-order rational recursion that has the same solutions as CCeq. The algorithm here is the fast algorithmic approach. It finds the same results with CCfiniteToDalg within a second.
We recompute the equations obtained with CCfiniteToDalg.
CCfiniteToSimpleRatrec(c(n)*s(n)+F(n)*s(n+1)=0,s(n),[CDE1,CDE2],[c(n),F(n)])
CCfiniteToSimpleRatrec(u(n)*s(n) + 2*s(n + 1) + v(n)*s(n + 2) = 0, s(n),[u(n + 2) - u(n) = 0, v(n + 2) - v(n) = 0], [u(n), v(n)])
Calling sequence: HoloToSimpleRatrec(HDE,s(n))
HDE: A linear difference equation in the dependent variable s(n), with polynomial coefficient in the index variable n.
s(n): s and n are variable names.
Description: Computes the least-order rational recursion satisfied by most holonomic sequence solutions of HDE. The algorithm is based on linear algebra. This can be seen as a special case of the conversion of $C^2$-finite equations into rational recursions, since holonomic sequences are $C^2$-finite. However, our journey with D-algebraic sequences started here...
A rational recursion for $n!$:
HoloToSimpleRatrec(s(n+1)=(n+1)*s(n),s(n))
A rational recursion for $n!^3$
HoloToSimpleRatrec(s(n+1)=(n+1)^3*s(n),s(n))
HDE:=s(n+3)=n*s(n)+(n+1)*s(n+1)+(n+2)*s(n+2)
Another $``Somos-like''$ sequence!
HoloToSimpleRatrec(HDE,s(n))
Calling sequence: DalgGuess(L,options)
L: A list of some first terms of an unknown sequence.
options: of the form keyword = value.
revars=s(n): s and n are variable names. To specify desired variable names in the output ADE. The default name is a(n).
degADE: the bound for the degree of the ADE sought. The default value is 2.
startfromord: the starting order for the ADE search.
Description: Search for an algebraic difference equation satisfied by the sequence that generates the term in the list L.
OEIS: A031213, Periods of sum of 10th powers of digits iterated until the sequence becomes periodic.
Sometimes, the outputs are not well displayed with the arbitrary Maple constants $_Cj, j$ integers. As we know the output from the Maple worksheet, we evaluate some of these constants to get one of the possible algebraic difference equations sought.
L:=[1, 1, 17, 123, 17, 17, 123, 123, 123, 123, 1, 17, 123, 17, 123, 123, 123, 81, 81, 123, 17, 123, 123, 123, 123, 123, 123, 123, 123, 123, 123, 17, 123, 123, 123, 123, 123, 81, 17, 123, 17, 123, 123, 123, 123, 123, 7, 123, 123, 123, 17, 123, 123, 123, 123]
DalgGuess(L,degADE=3)
kilobytes used=217385, alloc=27120, time=511.80
eval(Out[31],[_C=1,seq(cat(_C,j)=0,j=0..17)])
OEIS: A031215, Even-indexed primes.
L := [seq(ithprime(2*j), j = 1 .. 55)]
DalgGuess(L, degADE = 8)
kilobytes used=281313, alloc=27120, time=516.66
factor(eval(Out[34],[_C=9971490500799098857,_C0=0]))
Other interesting commands include: PartialSumDalgSeq, PartialProdDalgSeq, radicalDalgSeq for partial sums, partial products, and taking radicals as the names suggest.