OEIS/Holonomic Project

This project tries to define as many existing OEIS sequences as possible by holonomic recurrences.

Whereas the usual linear recurrence has constant coefficients, a holonomic recurrence has coefficients that are polynomials in n (the sequence index). Holonomic recurrences can be derived from linear differential equations, and are applicable to a wide class of series - see Wikipedia: Holonomic function.

Example

A000957 Fine's sequence (or Fine numbers): 
  number of relations of valence >= 1 on an n-set; 
  also number of ordered rooted trees with n edges having root of even degree.
0, 1, 0, 1, 2, 6, 18, 57, 186, 622, 2120, 7338, 25724, 91144, 325878, ...
G.f.: (1-sqrt(1-4*x))/(3-sqrt(1-4*x))
D-finite with recurrence: 2*n*a(n) +(12-7*n)*a(n-1) +2*(3-2*n)*a(n-2)=0. - R. J. Mathar

Types of recurrences

There is a hierarchy of sequence types which are included in this project, with increasing complexity and computational effort:

• constant
• periodic
  • finite (followed by infinitely many zeroes), polynomials
  • continued fractions of sqrt(n)
• recurrent with constant coefficients (cf. OEIS Index entries for linear recurrences with constant coefficients)
  • defined by a rational generating function (fraction of two polynomials in x), among them sequences for Coexter groups and (lattice) coordination sequences
• holonomic recurrent (D-finite, hypergeometric functions, algebraic equations)

Initial terms

For all types the recurrence frequently starts only after some initial terms which do not participate in the recurrence equation.

Exponential generating function

The project also handles e.g.f.s, in which case the terms are multiplied by n! during the generation.of the sequence.

Embedding in jOEIS

jOEIS is a project which aims to implement all OEIS sequences in Java. Currently (Feb. 2021) there are more than 104,000 sequences implemented. They are compiled in a single jar file, and any sequence can be called repeatedly in a uniform way to produce the next terms.

In jOEIS there is a series of basic Java classes which generate sequences of the holonomic type. They can all be found under https://github.com/archmageirvine/joeis/tree/master/src/irvine/oeis:

BlockMultAddSequence
ContinuedFractionOfSqrtSequence
CoordinationSequence
CoxeterSequence
FiniteSequence
GeneratingFunctionSequence
HolonomicRecurrence
LatticeCoordinationSequence
LinearRecurrence
PaddingSequence
PeriodicSequence
PrependSequence

Currently the following numbers of sequences are covered by the holonomic project:

    36 block
  2911 conti
   946 coord
  2251 coxet
  4601 finit
  8520 gener
  5902 holon
   340 latti
 20035 linea
   336 paddi
  1202 perio
   700 prepe
------------
 47780 total

Program for holonomic recurrences

Recurrences are attractive because it is rather simple to implement them in any programming language. A CAS may have special functions for them (e.g. LinearRecurrence and RecurrenceTable in Mathematica). The algorithm is straightforward, at it needs only fixed space even in the holonomic case. In jOEIS, HolonomicRecurrence.java uses a ring buffer of size k for the recurrence variables a(n), a(n-1), ... a(n-k+1), and a second array where the powers of the index n are maintained. The length of this array corresponds with the degree if the equation (the highest power of n. The program is not too big, and could be rewritten in other languages, for example Python.

Parameterization

The program uses these parameters:

• recurrence equation
• initial terms
• index of the first term to be returned (OEIS offset1)

Equation

Given that the recurrence equation is written in the form of an annihilator:

p[0]*1 + p[1]*a[n-k+1] + p[2]*a[n-k+2] + ... + p[k-1]*a[n-k+k-1] + p[k]*a[n] = 0

then the corresponding parameter is represented by the array

[p[0], p[1], p[2], ... p[k]]

where each polynomial p[i] is represented by an array [c0, c1, c2 ... cm] that defines the exponents of n. The initial example equation

2*n*a(n) +(12-7*n)*a(n-1) +2*(3-2*n)*a(n-2)=0

is represented by:

[[0],[6,-4],[12,-7],[2]]

Constant term

The first polynomial allows for a constant term, but normally the homogenous form is used with p[0] = [0].

Index shifting

Usually the last recurrence variable is a(n), but it is also possible to shift the recurrence index, for example to have

 2*a(n) - 2*a(n+1) - a(n+2) = 0

Such a shifting is specified by an additional parameter dist which is 0 by default. The example would get dist=2. In the future, all equations will be recomputed such that the constant term as well as the shift become always zero.

Initial terms

For an order (number of variables - 1) k a recurrence normally needs k initial terms to be computable. With the current implementation it is possible

• that there are more initial terms, in which case the recurrence only applies to the last k terms,
• that there are fewer initial terms, in which case a suitable number of zeroes is implied before the first term.

Black startable sequences

As a special possibility a recurrence can be started "out of nothing", that is the initial terms can be omitted altogether. The implementation then implies a leading sequence term one, and a suitable number of zeroes before. We call this property black startable (an expression used for power stations), and there is a surprising number of sequences that have it.

Database table

The main result of the project is a database table with suitable parameter sets for the OEIS sequences that are covered. The table has the following column that correspond with the parameters of the program HolonomicRecurrence:

• A-number of the sequence
• offset
• array of coefficient polynomials for constant, a(n-k), a(n-k+1) ... a(n-1), a(n)
• initial terms
• optional shift for n
• derived attributes (constant, periodic, linear recurrence, hypergeometric, d-finite etc.)