Walks obeying two-step rules on the square lattice: full, half and quarter planes

Here is some code associated with the paper on two-step paths in the square lattice, preprint here https://arxiv.org/abs/2010.06955.

• computing_the_models.ipynb is an interactive Jupyter Notebook using the Sage engine. It computes all the connected and aperiodic models in the full, half and quarter planes, and applies the relevant symmetries to determine all the non-isomorphic models. Its ultimate output is the three files full_plane_models.txt, half_plane_models.txt, and quarter_plane_models.txt, which are also included in this repository.

• group_order.py is a Sage script (you will need to have sage in your PATH) which attempts to compute the order of the symmetry group of the function B. It takes three mandatory arguments:

  • T, the 16-digit bitstring for the matrix, read one row at a time
  • D, one of E, N, W or S
  • nmax, a positive integer corresponding to the maximum order of the group to try

  So a sample usage would be

  ./group_order.py 1001110001100011 E 10
  

  The output will be a single integer (at most nmax) corresponding to the order of the symmetry group. If no group of order nmax or less was found, the output is 0.

• group_time.py does the same as group_order.py, but uses a different criterion to terminate. It also takes three mandatory arguments:

  • T, the 16-digit bitstring for the matrix
  • D, one of E, N, W or S
  • tmax, a positive integer corresponding to the number of seconds to allow for substitution and factorisation of the two group generators.

  So a sample usage would be

  ./group_time.py 1001110001100011 E 5
  

  The output is the same as group_order.py. The files group_4.txt, group_6.txt, group_8.txt, group_10.txt, group_12.txt, and group_0.txt in this repository were obtained using group_time.py with tmax set to 5 (each value of D produces the same results). These files together contain all the 6909 'interesting' quarter plane models.

• counting.cpp is C++ code (much faster than Python or Sage) for generating series. It uses the GNU Multiple Precision (GMP) libraries, and needs to be compiled with the -lgmp -lgmpxx flags. After compiling, it takes six mandatory arguments:

  • T, the 16-digit bitstring for the matrix
  • nmax, a positive integer corresponding to the maximum length of paths to count
  • allfile (xfile, yfile, ofile), the filename for the series output counting walks ending anywhere (on the x-axis, y-axis, and at the origin). So a sample usage would be

  ./a.out 1001110001100011 500 allfile xfile yfile ofile
  

  Each of the four output files will be a list of the series coefficients, one per line, starting at length 0.

• seriestest.py is a Sage script using the Ore Algebra package, available here https://github.com/mkauers/ore_algebra. It takes series (as generated by counting.cpp, or indeed any other series) and attempts to determine if the corresponding generating function is algebraic and/or differentially finite. It takes a single argument, simply the filename of the file containing the series.

  The output will be either 0 (no differential equation found), 1 (a differential equation was found but no algebraic equation found) or 2 (an algebraic equation was found). The files algebraic_500.txt, dfinite_500.txt, and nondfinite_500.txt were obtained using seriestest.py with 500 terms each (for walks ending anywhere). Again, these files together contain all the 6909 quarter plane models. Note that 500 terms is certainly going to be insufficient in some cases - there will be models in nondfinite_500.txt which are actually D-finite but require more than 500 terms to find a differential equation, and probably models in dfinite_500.txt which are actually algebraic.

References

• The Sage Developers, SageMath, the Sage Mathematics Software System (version 9.1), https://www.sagemath.org.
• M. Kauers, M. Jaroschek, and F. Johansson, Ore polynomials in Sage, in Computer Algebra and Polynomials: Applications of Algebra and Number Theory. Berlin: Springer, 2015, pp. 105–125.
  • https://github.com/mkauers/ore_algebra (software version 0.5)