Flat surfaces in Sage

Introduction

What is a flat surface ? What are we doing here ?

A flat surface can be seen either

• as a union of polygons glued along pairs of parallel sides,
• as a flat metric with trivial SO(2) holonomy on a compact surface,
• as a Riemann surface together with a nonzero Abelian (or quadratic) differential,
• as a non zero tangent vector to the Teichmüller space,
• ...

This page is an organization wiki for the implementation of various algorithms related to flat surfaces and more generally geometry/combinatorics/dynamics of surfaces (mapping class group, train tracks, pseudo-Anosov dynamics, ...). If you have a special request do not hesitate to edit wishes.

Quick links

• dynamics: the wider project sage-dynamics (look at it in particular for installation)

• dynamics/examples: examples of code that uses the algorithms developed here

• Flat surfaces wiki: a wiki dedicated to flat surfaces

Global organization

Architecture

We need to review the architecture of flat surfaces repository to fit with the general framework for dynamics. In is now as follows and should be quickly changed

• sage.combinat.flat_surfaces (various generic objects)
• sage.combinat.flat_surfaces.iet (interval exchange transformations)
• sage.combinat.flat_surfaces.origamis (origamis/square-tiled surfaces)
• sage.geometry.hyperbolic_geometry (hyperbolic spaces)
• sage.groups.surface_gps (abstract surface groups)

What should be a Sage flat surface ?

We aim to allow different implementation for flat surfaces and full compatibility between them. Here is a draft of what we expect.

Different representations/implementations for flat surfaces

• (convex) polygonal surface
  • rectangulated surface
    • suspension of iet (and li) (almost in Sage)
    • Thurston-Veech construction
  • triangulated surface
    • Delaunay surface (?)
• algebraic curve with Abelian or quadratic differential
• coverings (make it relative)... need to implement homomorphism between translation surfaces
  • square-tiled surfaces/origamis (torus coverings) (almost in Sage)
  • pillow-case covers (almost in Sage)
  • hyperelliptic curves (specifying a double cover of the sphere)
• unfoldings of rational billiards

Needed generic methods

• switch between representations (the one to which everybody can be converted is triangulated flat surface)
• compute fundamental group, relative homology, and homology (as well as functors between them)
• maps between flat surfaces (and functors to fundamental groups and homologies)
• action of SL(2,R) and isomorphisms (and functors)
• Siegel-Veech constants and volumes
• Lyapunov exponents

Roadmap / Concrete tasks

We need to rebase some of the code and create new one. Here is what do we want to be done.

Wishes

Write here what you need for your research work (no precision on implementations is needed).

• volume of strata and Siegel Veech constants
• sum of Lyapunov exponents in various context

Interval exchange transformations

• rebase reduced permutations to be systematically on the alphabet 0, ..., n (we can think about an optional possibility of allowing an alphabet, but it should be optional)
• make Rauzy diagrams lazy (we do NOT want to compute all permutations at initialization)
  • provide generators for standard permutations in each Rauzy diagrams
  • add the formula for the cardinality
  • ...

• stratum <-> Rauzy diagrams: we should provide a uniform framework for the correspondance between various Rauzy diagrams and strata of Abelian/quadratic differential

• interval exchange transformations are not fast enough to do any simulation
  • computation of the language and the measure of the clopens (i.e. decompose T^n)
  • quantitative recurrence (how to deal with approximations here)
  • ...

Permutation in pure C

We really need fast permutation objects for various reason (and other group theoretical stuff). The most convenient would be to use GAP which is completely written in C and has a lot of capabilities to deal with permutations. Moreover, the implementation of permutation in GAP is as we expect: starting at 0 and not 1

**  Mathematically a permutation is a bijective mapping  of a finite set onto
**  itself.  In \GAP\ this subset must always be of the form [ 1, 2, .., N ],
**  where N is at most $2^16$.
**
**  Internally a permutation  is viewed as a mapping  of [ 0,  1,  .., N-1 ],
**  because in C indexing of  arrays is done with the origin  0 instead of 1.
**  A permutation is represented by a bag of type 'T_PERM' of the form
**
**      +-------+-------+-------+-------+- - - -+-------+-------+
**      | image | image | image | image |       | image | image |
**      | of  0 | of  1 | of  2 | of  3 |       | of N-2| of N-1|
**      +-------+-------+-------+-------+- - - -+-------+-------+
**
**  The entries of the bag are of type  'UInt2'  (defined in 'system.h' as an
**  at least 16 bit   wide unsigned integer  type).   The first entry is  the
**  image of 0, the second is the image of 1, and so  on.  Thus, the entry at
**  C index <i> is the image of <i>, if we view the permutation as mapping of
**  [ 0, 1, 2, .., N-1 ] as described above.

• We also need other kind of objects
  • - permutations (standard operations) - tuple of permutations up to conjugacy - constellations (prod_n d_i = 1) - generalized constellations of genus g (prod_g [a_i,b_i] prod_n d_i = 1)

• back and forth between C interface <-> gap (W. Stein started to write a libgap... look at it)

Separatrix diagrams / Cylinder diagrams

• quadratic differentials (*current dev. by S. Lelièvre*)
• compute homology from cylinder diagrams (as well as the part generated from
  • the circumference of the cylinders)
• allows partial saddle connection configurations (see Eskin, Masur, Zorich 2003)

Origami

• sparse implementation of permutations (just store what happens at the cone points of the separatrix diagram, i.e. integer coordinates).
• consider a special class for hyperelliptic origami which are invariant under inversions (or a special attribute)
• (faster) C implementation for orbit and C data structure for x and y, in which case the return type of SLedges could be origamis and not tuples (dependent of permutations in C).
• affine group as an extension of the Veech group
• field of definition of origamis (Swinnerton-Dyer, ...)

• primitivity <=> compute the lattice generated by the set of holonomy of saddle connections.

Surface groups and mapping class group

They are needed from two points of view: the group of the surface itself and the flat surface's stabilizer under the action of SL(2,R) or PSL(2,R). There must be some software for dealing with surface groups. We need to look at

• kbmag: Knuth-Bendix in monoids and automatic groups, implemented by Derek Holt

Surface group and covers

To deal with coverings we need some stuff about constellations (of genus g and degree d) which are (ordered) tuples of permutations (\alpha_i, \beta_i)_{i \in \{1, ldots, g\}} and (\delta_i)_{i \in \{1, \ldots, k\}} in the symmetric group S_d such that

• the group generated by them is transitive (not fully needed) <=> connectivity of the cover

• they verify the surface relation: \prod_i [\alpha_i, \beta_i] \prod_i \delta_i = 1

A constellation has to be thought "up to conjugacy". For any tuple of permutations, one can compute a normal form for it in polynomial time. Most of the time, one would like to choose the conjugacy classes of the \delta_i and fix the degree of the cover. There exists explicit formula for counting involving Frobenius formula but is there any fast generation method ?

• A Grothendieck dessin d'enfants is a genus 0 degree 3 constellation
• a pillow case cover is a genus 0 degree 4 constellation
• an origami is a genus 1 degree 1 constellation

Mapping class group

Is there any library somewhere to work with the mapping class group?

Hyperbolic geometry

This part is roughly implemented in trac #9439

• the three 2D models: hyperbolic plane, hyperbolic disc and the hyperboloïd
• points, geodesics and polygonal domains
• tessellations (covering of HH by finite area convex polygonal domains)
• Fuchsian groups, their fundamental domains and their associated tessellations

The Experimental geometry lab (University of Maryland) published a lot of Mathematica packages/worksheets to deal with Kleinian and Fuchsian groups, hyperbolic tessellations, etc.

Port of other programs

• Joshua Bowman's program on iso-Delaunay tessellations (written in Java)
• Finish porting Anton Zorich's programs on interval exchange transformations and linear involutions (written in Mathematica)
• Anton Zorich's program for computing approximations of various Lyapunov exponents (written in C and Mathematica)
• Alex Eskin's program for analyzing saddle connection directions in a surface (written in C++)