Hyperbolic maze

Some comments about this maze

This is a maze in the hyperbolic plane, displayed using the Poincaré disk or Beltrami-Klein model (see this video for explanations and illustrations about projections of the hyperbolic plane). The fundamental pattern used to construct the maze is the uniform tiling of the hyperbolic plane by regular quadrilaterals (“squares”?) with angles of 2π/5=72° at each vertex (less than the 90° of a Euclidean square because the hyperbolic plane is negatively curved); a circle has been drawn at the center of every square.

Use the up and down arrows to move up and down, left and right to rotate left and right, and insert and delete to move left and right without turning. (Note that since the hyperbolic plane has curvature, even if one moves without turning, one can return to one's starting point with a different orientation. So it would be meaningless to have a “compass” in the hyperbolic plane.)

Since the hyperbolic plane is infinite, the maze has been made “periodic”, in much the same way that the Euclidean plane can be made “periodic”, that is, transformed into a flat torus by quotienting by a lattice of periods, typically a square lattice in computer games, so that one “loops around” if one goes to far. Here something analogous has been done, by quotienting out by a discrete subgroup Γ, acting without fixed points, of the group PSL(2,ℝ) of orientation-preserving isometries of the hyperbolic plane which is contained in the group Δ of symmetries of the tiling (the (2,4,5) triangle group); here, Γ is a normal subgroup and the quotient (PSL(2,ℝ)∩Δ)/Γ is the projective special linear group PSL(2,89) on the finite field with 89 elements: since #PSL(2,89) = 352440, the period domain consists of 88110 cells (each cell has 4 orientation-preserving symmetries because it is a square), 176220 edges (each edge has 2 orientation-preserving symmetries) and 70488 vertices (each vertex has 5 orientation-preserving symmetries). If one prefers, the maze lives on a compact Riemann surface of genus 8812 (having 352440 symmetries), whose universal cover is the hyperbolic plane (and Γ is its fundamental group). Or on the Cayley graph of PSL(2,89) for two generators R (rotation around a cell) and T (translation to the next cell).

The number 89 was chosen because it is the smallest mod which the three polynomials X⁴+1, X⁴−(3/2)X²+(1/4) and X⁴+(1/2)X²−(1/4) split completely (they are the minimal polynomials of the coefficients of R and T as elements of PSL(2,ℝ)), making it possible to define R and T in PSL(2,F) without requiring any extension.

The maze generation is not particularly smart: the algorithm first carves a tree inside the graph and then randomly removes another 8.5% of walls (a completely heuristic value to make the maze more interesting). The distance to the starting point and “green point” (a point at maximal distance from the starting point) determines the color of the circles; the proposed goal is to first reach that target and then return to the starting point by using a path that is not homotopic (even with the walls removed) to the first path (in other words, by “looping” in the sense that it defines a non-trivial element of Γ).