ore_algebra.examples.ssw

Small-step walks

Examples from the paper “Hypergeometric expressions for generating functions of walks with small steps in the quarter plane” by Alin Bostan, Frédéric Chyzak, Mark van Hoeij, Manuel Kauers and Lucien Pech (European Journal of Combinatorics, 2017; arXiv:1606.02982 [math.CO]; <http://specfun.inria.fr/chyzak/ssw/index.html>).

For the rational functions rat[1], …, rat[19], the task consists in computing a telescoper wrt Du and Dv. Interesting settings are when x and y are both set to 1 or one of them is set to 0 and the other is left symbolic. For example:

sage: from ore_algebra import OreAlgebra
sage: A.<Du,Dv,Dt> = OreAlgebra(ZZ['u','v','t'].fraction_field(), 'Du', 'Dv', 'Dt')

sage: from ore_algebra.examples import ssw
sage: q = A.base_ring()(ssw.rat[1](x=1,y=1))
sage: ct1 = A.ideal([q*D - D(q) for D in Du,Dv,Dt]).ct(Dv)[0]
sage: ct2 = ct1[0].parent().ideal(ct1).ct(Du)[0]
sage: ct2
[(16*t^4 - t^2)*Dt^3 + (128*t^3 + 8*t^2 - 6*t)*Dt^2 + (224*t^2 + 28*t - 6)*Dt + 64*t + 12]
sage: ct2 == [ssw.dop[1,1,1]]
True

After obtaining the telescopers, we can use them to compute connection matrices that encode information on the asymptotics of the corresponding lattice walks:

sage: mat = ssw.dop[5,1,1].numerical_transition_matrix([0, 1/3+i/10, 1/3]) # (1.8 s)
sage: (mat*vector([0, 0, 1, 3, 7]))[0] # long time
[...] + [0.50000...]*I

sage: ssw.dop[1, 0, 0].numerical_transition_matrix([0, 1/4])
[ [-206.5126691369...] + [...]*I            [16.000000000000...] + [...]*I  [1.20938909474579...] + [...]*I]
[ [1489.126691369...] + [...]*I             [-128.00000000000...] + [...]*I [3.9061090525420...] + [...]*I]
[[1925.57548817...] + [-1536.00000000...]*I [768.000000000...] + [...]*I    [-124.21690469554...] + [128.000000000000...]*I]

TESTS:

sage: for i in [2, 5, 12, 18]: # long time (1 min 40 s)
....:     for xx, yy in [(0, 1), (1, 0)]:
....:         ssw.test_ct(i, xx, yy)

sage: for i in [1..19]: # not tested (9 min 31 s)
....:     for xx in [0, 1]:
....:         for yy in [0, 1]:
....:             ssw.test_ct(i, xx, yy)

Plus an example provided by Bruno Salvy, also related to small-step walks:

sage: ssw.aux_dop.numerical_solution(ssw.aux_ini, [0,1]) # TODO: double-check result
[10.662510694...]

Functions

test_ct(i, xx, yy[, infolevel])