Load the input file :

<<modlifts.m

The reduction algorithm of Lemma 9

The series ((Subscript[H, (Subscript[a, 1]),(Subscript[a, 2]), . . .,(Subscript[a, s])])^((Subscript[γ, 1]),(Subscript[γ, 2]), . . .,(Subscript[γ, s])))(z) is entered as

H[{(Subscript[a, 1]),...,(Subscript[a, s])},{(Subscript[γ, 1]),...,(Subscript[γ, s])}]

Once one enters such a series, the reduction algorithm of Lemma 9 is instantly applied:

Expand[H[{1,2,1},{0,0,0}]]

Expand[H[{1,2,1},{4,0,-1}]]

Here, H[{(Subscript[a, 1]),...,(Subscript[a, s])}] is the series (Subscript[H, (Subscript[a, 1]),...,(Subscript[a, s])])(z) of the paper.

In order to expand powers of Φ(z), one can use PP[n], which expands (Φ^n)(z) in terms of the series (Subscript[H, (Subscript[a, 1]),...,(Subscript[a, s])])(z). For example, here is the first computation in Appendix A:

PP[5]

Catalan numbers

Derivation of (1.2) :

Cat64

Derivation of Theorem 14:

Cat4096

Free subgroup numbers for lifts of the inhomogeneous modular group

For the derivation of Theorem 20 for specific m, one has to enter FLIMG64[m] (m must be odd):

FLIMG64[3]

Subgroup numbers of the inhomogeneous modular group

For the derivation of Theorem 24, one has to enter IMG64:

IMG64

If one wants to determine the subgroup numbers of the inhomogeneous modular group modulo 4096, one has to enter IMG4096 (this takes a few minutes):

IMG4096

Subgroup numbers for the homogeneous modular group (Subscript[SL, 2])(Z)

The file sl2z.rek contains the recurrence described implicitly above (11.2) :

sl2zrec=<<sl2z.rek;

In order to see that this recurrence is indeed correct, we use Christoph Koutschan’s package HolonomicFunctions.m

<< HolonomicFunctions.m

HolonomicFunctions package by Christoph Koutschan, RISC-Linz, Version 1.5.1 (09.08.2011)
⟶ Type  ?HolonomicFunctions  for help

We have to show that the sum in equation (10.5) satisfies the recurrence sl2zrec. To do so, we apply creative telescoping as follows. First, we compute (multivariate) recurrence equations for the three inner sums individually.

annH1=First[CreativeTelescoping[Annihilator[(2k)!/i!(4/3)^i/(2k-3i)!,{S[n],S[k],S[i]}],S[i]-1,{S[n],S[k]}]];

annH2=First[CreativeTelescoping[Annihilator[(n-4k)!/i!/2^i/(n-4k-2i)!,{S[n],S[k],S[i]}],S[i]-1,{S[n],S[k]}]];

annH3=First[CreativeTelescoping[Annihilator[(n-4k)!/i!/3^i/(n-4k-3i)!,{S[n],S[k],S[i]}],S[i]-1,{S[n],S[k]}]];

Next, we combine these recurrence systems to a recurrence system for the summand of the outer sum in (10.5).

annH123=DFiniteTimes[annH2,annH3,annH1];

annSummand=DFiniteTimes[annH123,Annihilator[n!/k! 4^(-k)/(n-4k)!,{S[n],S[k]}]];

The next step is to compute a creative telescoping relation. We did so by first using the FGLM command to change the term order of the Gröbner basis in annSummand and then applied the FindCreativeTelescoping command to obtain a recurrence of order 30 along with a corresponding certificate. The main step of this calculation took about 30h. It need not be reproduced here because the correctness its result can be verified independently, by just checking that the certifying relation belongs to the annihilating ideal of the summand.

annLex=FGLM[annSummand,OreAlgebra[S[k],S[n]],Lexicographic]; (* costly *)

cert=<<sl2z.certificate;

OreReduce[cert[[1,1]]+(S[k]-1)**cert[[2,1,1]],annLex]

The output being 0 proves that cert[[1,1]] is a valid recurrence for the sum in (10.5). This recurrence is however different from sl2zrec. To prove, finally, that also sl2zrec is correct, we compute the greatest common right divisor gcrd of cert[[1,1]] and the operator corresponding to the recurrence sl2zrec. By checking that the sum in (10.5) satisfies gcrd for the first 30 terms (30 is the order of cert[[1,1]]), it follows that gcrd is a correct recurrence for the sum. Then, since sl2zrec is a left multiple of gcrd by construction, it follows that sl2zrec is a correct recurrence for the sum, too.

sl2zop=DFiniteTimesHyper[ToOrePolynomial[sl2zrec/.n->n+50,SUM[n]],n!];

gcrd=OreGroebnerBasis[{cert[[1,1]], sl2zop}];

h2[n_Integer]:=h2[n]=Sum[n!/2^m/m!/(n-2m)!,{m,0,n/2}];

h3[n_Integer]:=h3[n]=Sum[n!/3^m/m!/(n-3m)!,{m,0,n/3}];

h[n_Integer]:=h[n]=Sum[n!/r!/2^(2r)/(n-4r)!h2[n-4r]h3[n-4r]*Sum[(2r)!4^s/s!/3^s/(2r-3s)!,{s,0,2r/3}],{r,0,n/4}];

Table[#,{n,1,30}]&[ApplyOreOperator[gcrd[[1]],h[n]]]

The Riccati-type differential equation corresponding to sl2zrek, when reduced modulo 16, as given in (11.5), is encoded by DGl1:

Clear[S0,S1,S2,S3,S4];DGl1

If one attempts to apply the method from Section 4 for the modulus 8, then the algorithm fails :

SL2Z8a

Instead, for the derivation of Theorem 26, one has to work with the minimal polynomial for the modulus 16 given in Proposition 2:

SL2Z8

and then reduce the result modulo the minimal polynomial for the modulus 8 (here, R8 does reduction of coefficients modulo 8) :

Collect[Map[R8,Expand[X*PolynomialRemainder[%,(f[z]^4-2 f[z]^3+(2 z+3) f[z]^2+(2 z-2) f[z]-3 z^2+2 z),f[z]]],2]/.X->1,f[z]]

For producing the equations for the determination of the subgroup
numbers of (Subscript[SL, 2])(Z) modulo 16, which then can be "handed over" to
the procedure explained in Appendix D, one has to type SL2Z16:

SL2Z16

Subgroup numbers for the lift (Subscript[Γ, 3])(3)

The file ga3.rek contains the recurrence described implicitly above (12.1) :

ga3rec=<<ga3.rek;

The correctness proof for this recurrence proceeds by the same argument as the proof of sl2zrec in the previous section. We state the commands without further comments.

<<HolonomicFunctions.m (* unless already loaded before *)

HolonomicFunctions package by Christoph Koutschan, RISC-Linz, Version 1.5.1 (09.08.2011)
⟶ Type  ?HolonomicFunctions  for help

annH1=First[CreativeTelescoping[Annihilator[(3k)!/i!(3/2)^i/(3k-2i)!,{S[n],S[k],S[i]}],S[i]-1,{S[n],S[k]}]];

annH2=First[CreativeTelescoping[Annihilator[(n-9k)!/i!/2^i/(n-9k-2i)!,{S[n],S[k],S[i]}],S[i]-1,{S[n],S[k]}]];

annH3=First[CreativeTelescoping[Annihilator[(n-9k)!/i!/3^i/(n-9k-3i)!,{S[n],S[k],S[i]}],S[i]-1,{S[n],S[k]}]];

annH123=DFiniteTimes[annH2,annH3,annH1];

annSummand=DFiniteTimesHyper[annH123,n!/k! 9^(-k)/(n-9k)!];

annLex=FGLM[annSummand,OreAlgebra[S[k],S[n]],Lexicographic];(* costly *)

cert=<<ga3.certificate;

OreReduce[cert[[1,1]]+(S[k]-1)**cert[[2,1,1]],annLex]

ga3op=DFiniteTimesHyper[ToOrePolynomial[ga3rec/.n->n+60/.t[_]->0,SUM[n]],n!];

gcrd=<<ga3.gcrd; (* computation is costly; we just check that the precomputed basis is correct *)

OreReduce[cert[[1,1]],gcrd]

OreReduce[ga3op,gcrd]

H1[n_Integer,k_Integer]:=H1[n,k]=Sum[(3k)!/i!(3/2)^i/(3k-2i)!,{i,0,3/2 k}]

H2[n_Integer,k_Integer]:=H2[n,k]=Sum[(n-9k)!/i!/2^i/(n-9k-2i)!,{i,0,(n-9k)/2}]

H3[n_Integer,k_Integer]:=H3[n,k]=Sum[(n-9k)!/i!/3^i/(n-9k-3i)!,{i,0,(n-9k)/3}]

H[n_Integer]:=H[n]=Sum[n!/k! 9^(-k)/(n-9k)!H1[n,k]H2[n,k]H3[n,k],{k,0,n/9}];

Table[#,{n,1,42}]&[ApplyOreOperator[gcrd[[1]], H[n]]]

The  Riccati-type differential equation resulting from ga3rec, when reduced modulo 16, as given in (12.3), is encoded by DGl2:

Clear[S0,S1,S2,S3,S4,S5,S6,S7,S8,S9,S10,S11];DGl2

If one attempts to apply the method from Section 4 for the modulus 8, then the algorithm fails (this takes up to two hours) :

Ga338a

Instead, for the derivation of Theorem 30, one has to work with the minimal polynomial for the modulus 16 given in Proposition 2:

Ga338

and then reduce the result modulo the minimal polynomial for the modulus 8 (here, R8 does reduction of coefficients modulo 8) :

Collect[Map[R8,Expand[X*PolynomialRemainder[%,(f[z]^4-2 f[z]^3+(2 z+3) f[z]^2+(2 z-2) f[z]-3 z^2+2 z),f[z]]],2]/.X->1,f[z]]

For producing the equations for the determination of the subgroup
numbers of (Subscript[Ga, 3])(3) modulo 16, which then can be "handed over" to
the procedure explained in Appendix D, one has to type Ga3316:

Ga3316

Free subgroup numbers for lifts of Hecke groups

For the derivation of Theorem 35 for specific m, one has to enter Gam516[m] :

Gam516[1]

Subgroup numbers of the Hecke group H(5)

For the derivation of Theorem 24, one has to enter H516 :

H516