The complete generating function for Gessel walks is algebraic
Supplementary Material
This is a collection of files accompanying an article of
Alin Bostan
and
Manuel Kauers
containing a proof that the complete generating
function for Gessel walks is algebraic.
The article itself can be downloaded here:
[ps.gz]
[pdf]
Section 1
Section 2
 Maple Session [mpl]
 Coefficients of F(t,x) mod t^{101}
[mpl]
[mma]
 The minimal polynomial of F(t,x)
[mpl]
[mma]
Section 3.1

Coefficients of G(t,x,0) mod t^{1001}
[mpl]
[mma] (75Mb)
 Guessed differential operator for G(t,x,0)
[mpl]
[mma]
 The minimal polynomial of G(t,x,0)
[mpl]
[mma]

Coefficients of G(t,0,y) mod t^{1001}
[mpl]
[mma] (45Mb)
 Guessed differential operator for G(t,0,y)
[mpl]
[mma]
 The minimal polynomial of G(t,0,y)
[mpl]
[mma]

Coefficients of U(t,x) mod t^{1001}
[mpl]
[mma] (75Mb)
 The minimal polynomial of U(t,x)
[mpl]
[mma]

Coefficients of V(t,x) mod t^{1001}
[mpl]
[mma] (45Mb)
 The minimal polynomial of V(t,x)
[mpl]
[mma]
Section 3.2
 Details on existence of U_{cand}(t,x)
and V_{cand}(t,x)
[ps]
[pdf]
 Differential operators annihilating U_{cand}(t,x)
[mma]
 Recurrence operators annihilating the coefficients of
U_{cand}(t,x)
[mma]
 Transformation matrix for U_{cand}(t,x)
[mma]
 Witness operators for U_{cand}(t,x)
[mma]
 The polynomial Q(T,t,y) whose solution is the auxiliary
series f(t,y)
[mma]
 Differential operators annihilating f(t,x)
[mma]
 Recurrence operators annihilating the coefficients of
f(t,x)
[mma]
 First transformation matrix for f(t,x)
[mma]
 First set of witness operators for f(t,x)
[mma] (10Mb)
 Second transformation matrix for f(t,x)
[mma]
 Second set of witness operators for f(t,x)
[mma] (18Mb)
Section 3.3
 The minimal polynomial of
(1+x)G_{2}(t,x)  G(t;0,0)
and
x X(t,x)/tG_{1}(t,X(t,x))
[mpl]
[mma]
Section 3.4
 Radical expression for G(t,1,1)
[mpl]
[mma]
 Minimal polynomial of G(t,1,1)
[mpl]
[mma]
 Radical expression for G(t,1,0)
[mpl]
[mma]
 Minimal polynomial of G(t,1,0)
[mpl]
[mma]
 Radical expression for G(t,0,1)
[mpl]
[mma]
 Minimal polynomial of G(t,0,1)
[mpl]
[mma]
Appendix (by Mark van Hoeij)