Source code for flatsurf.geometry.fundamental_group

# ****************************************************************************
#  This file is part of sage-flatsurf.
#
#       Copyright (C) 2013-2019 Vincent Delecroix
#                     2013-2019 W. Patrick Hooper
#
#  sage-flatsurf is free software: you can redistribute it and/or modify
#  it under the terms of the GNU General Public License as published by
#  the Free Software Foundation, either version 2 of the License, or
#  (at your option) any later version.
#
#  sage-flatsurf is distributed in the hope that it will be useful,
#  but WITHOUT ANY WARRANTY; without even the implied warranty of
#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#  GNU General Public License for more details.
#
#  You should have received a copy of the GNU General Public License
#  along with sage-flatsurf. If not, see <https://www.gnu.org/licenses/>.
# ****************************************************************************

from sage.misc.cachefunc import cached_method

from sage.structure.element import parent

from sage.categories.groups import Groups
from sage.groups.group import Group
from sage.structure.element import MultiplicativeGroupElement
from sage.structure.unique_representation import UniqueRepresentation


[docs] def intersection(i0, j0, i1, j1): r""" Intersection inside a polygon. In case of equality we consider that i0 < i1 < j1 < j0 INPUT: - ``i0``, ``j0`` -- start and end of the first curve - ``i1``, ``j1`` -- start and end of the second curve TESTS:: sage: from flatsurf.geometry.fundamental_group import intersection sage: intersection(3,0,3,2) 1 sage: intersection(0,1,1,2) 1 sage: intersection(0,2,3,1) -1 sage: intersection(0,3,3,2) 0 sage: intersection(1,1,1,1) 0 sage: intersection(3,2,3,2) 0 sage: intersection(3,2,0,3) 0 sage: intersection(0,3,0,3) 0 sage: intersection(0,2,0,2) 0 """ if i0 <= j0: # that is i0 < j0 or i0 == j0 return (i0 <= i1 <= j0) - (i0 <= j1 <= j0) else: return (j0 < j1 < i0) - (j0 < i1 < i0)
[docs] class Path(MultiplicativeGroupElement): # activating the following somehow break the discovery of the Python _mul_ # method below... # __slots__ = ['_polys', '_edges', '_edges_rev'] def __init__(self, parent, polys, edge, edge_rev, check=True, reduced=False): self._polys = tuple(polys) self._edges = tuple(edge) self._edges_rev = tuple(edge_rev) MultiplicativeGroupElement.__init__(self, parent) if not reduced: self._reduce() if check: self._check() def _reduce(self): r""" Remove """ pass def _poly_cross_dict(self): d = {p: [] for p in self.parent()._s.labels()} d[self._polys[0]].append((self._edges_rev[-1], self._edges[0])) for i in range(1, len(self._polys) - 1): p = self._polys[i] e0 = self._edges_rev[i - 1] e1 = self._edges[i] d[p].append((e0, e1)) return d def __hash__(self): return hash((self._polys, self._edges)) def __eq__(self, other): r""" TESTS:: sage: from flatsurf import translation_surfaces sage: t = translation_surfaces.square_torus() sage: F = t.fundamental_group() sage: a,b = F.gens() sage: a == b False sage: a*b == b*a False sage: a*b == a*b True """ return ( parent(self) is parent(other) and self._polys == other._polys and self._edges == other._edges ) def __ne__(self, other): r""" TESTS:: sage: from flatsurf import translation_surfaces sage: t = translation_surfaces.square_torus() sage: F = t.fundamental_group() sage: a,b = F.gens() sage: a != b True sage: a*b != b*a True sage: a*b != a*b False """ return ( parent(self) is not parent(other) or self._polys != other._polys or self._edges != other._edges ) def _check(self): if not (len(self._polys) - 1 == len(self._edges) == len(self._edges_rev)): raise ValueError( "polys = {}\nedges = {}\nedges_rev={}".format( self._polys, self._edges, self._edges_rev ) ) assert self._polys[0] == self.parent()._b == self._polys[-1]
[docs] def is_one(self): return not self._edges
def _repr_(self): return "".join( "{} --{}-- ".format(p, e) for p, e in zip(self._polys, self._edges) ) + "{}".format(self._polys[-1]) def _mul_(self, other): r""" TESTS:: sage: from flatsurf import translation_surfaces sage: t = translation_surfaces.square_torus() sage: a,b = t.fundamental_group().gens() sage: a*b 0 --0-- 0 --1-- 0 """ sp = self._polys[:] se = self._edges[:] se_r = self._edges_rev[:] op = other._polys[:] oe = other._edges[:] oe_r = other._edges_rev[:] if sp[-1] != op[0]: return None i = 0 while i < len(se) and i < len(oe) and se[-i - 1] == oe_r[i]: i += 1 P = self.parent() return P.element_class( P, sp[: len(sp) - i] + op[i + 1 :], se[: len(se) - i] + oe[i:], se_r[: len(se_r) - i] + oe_r[i:], ) def __invert__(self): r""" TESTS:: sage: from flatsurf import translation_surfaces sage: o = translation_surfaces.octagon_and_squares() sage: F = o.fundamental_group() sage: a1,a2,a3,a4,a5,a6 = F.gens() sage: (a1 * a2 * ~a2 * ~a1).is_one() True sage: (a1 * ~a2 * a2 * a1) == a1 * a1 True """ P = self.parent() return P.element_class( P, self._polys[::-1], self._edges_rev[::-1], self._edges[::-1] )
[docs] def intersection(self, other): r""" The intersection number of this element with ``other``. EXAMPLES:: sage: from flatsurf import translation_surfaces sage: t = translation_surfaces.square_torus() sage: a,b = t.fundamental_group().gens() sage: a.intersection(b) 1 sage: b.intersection(a) -1 This is an Abelian invariant:: sage: x1 = a*b*b*~a*~a*b*b*a*~b*~b sage: x2 = a*b*a*b sage: x3 = ~b*~b*a sage: (x1*x2).intersection(x3) == x1.intersection(x3) + x2.intersection(x3) True sage: (x2*x1*~x2).intersection(x2*x3*~x2) == x1.intersection(x3) True A little bit more involved example:: sage: S = SymmetricGroup(4) sage: r = S('(1,2)(3,4)') sage: u = S('(2,3)') sage: o = translation_surfaces.origami(r,u) sage: F = o.fundamental_group() sage: x = F([1,2,2,3]) sage: x.intersection(x) 0 sage: a = F.gens() sage: m = matrix(ZZ, 5, lambda i,j: a[i].intersection(a[j])) sage: m [ 0 1 0 0 0] [-1 0 -1 0 0] [ 0 1 0 1 0] [ 0 0 -1 0 -1] [ 0 0 0 1 0] A slightly more involved example:: sage: S = SymmetricGroup(8) sage: r = S('(1,2,3,4,5,6,7,8)') sage: u = S('(1,8,5,4)(2,3)(6,7)') sage: o = translation_surfaces.origami(r,u) sage: a = o.fundamental_group().gens() sage: m = matrix(ZZ, 9, lambda i,j: a[i].intersection(a[j])) sage: m [ 0 -1 1 -1 1 -1 -1 -1 1] [ 1 0 1 0 0 -1 -1 -1 1] [-1 -1 0 0 0 0 0 0 0] [ 1 0 0 0 -1 0 0 0 0] [-1 0 0 1 0 0 0 0 0] [ 1 1 0 0 0 0 0 0 0] [ 1 1 0 0 0 0 0 1 -1] [ 1 1 0 0 0 0 -1 0 -1] [-1 -1 0 0 0 0 1 1 0] """ si = self._poly_cross_dict() oi = other._poly_cross_dict() n = 0 for p in self.parent()._s.labels(): for e0, e1 in si[p]: for f0, f1 in oi[p]: n += intersection(e0, e1, f0, f1) return n
[docs] class FundamentalGroup(UniqueRepresentation, Group): r""" The fundamental group of a punctured surface EXAMPLES:: sage: from flatsurf import translation_surfaces sage: t = translation_surfaces.square_torus() sage: TestSuite(t.fundamental_group()).run() """ Element = Path def __init__(self, surface, base): if not surface.is_finite_type(): raise ValueError("the method only work for finite surfaces") self._s = surface self._b = base Group.__init__(self, category=Groups().Infinite()) def _element_constructor_(self, *args): r""" TESTS:: sage: from flatsurf import translation_surfaces sage: S = SymmetricGroup(4) sage: r = S('(1,2)(3,4)') sage: u = S('(2,3)') sage: o = translation_surfaces.origami(r,u) sage: F = o.fundamental_group() sage: F([1,1]) 1 --1-- 2 --1-- 1 sage: F([1,2,2,3]) 1 --1-- 2 --2-- 3 --2-- 2 --3-- 1 sage: F([1,2,3]) Traceback (most recent call last): ... AssertionError """ if len(args) == 1 and isinstance(args[0], (tuple, list)): args = args[0] s = self._s p = [self._b] e = [] er = [] for i in args: i = int(i) % len(s.polygon(p[-1]).vertices()) q, j = s.opposite_edge(p[-1], i) p.append(q) e.append(i) er.append(j) return self.element_class(self, p, e, er) def _repr_(self): return "Fundamental group of {} based at polygon {}".format(self._s, self._b)
[docs] @cached_method def one(self): return self.element_class(self, [self._b], [], [])
[docs] @cached_method def gens(self): r""" Return a generating set EXAMPLES:: sage: from flatsurf import translation_surfaces sage: S = SymmetricGroup(8) sage: r = S('(1,2,3,4,5,6,7,8)') sage: u = S('(1,8,5,4)(2,3)(6,7)') sage: o = translation_surfaces.origami(r,u) sage: len(o.fundamental_group().gens()) 9 """ p = self._b s = self._s tree = {} # a tree whose root is base_label basis = [] tree[p] = (None, None, None) wait = [] # list of edges of the dual graph, ie p1 -- (e1,e2) --> p2 for e in range(len(s.polygon(p).vertices())): pp, ee = s.opposite_edge(p, e) wait.append((pp, ee, p, e)) while wait: p1, e1, p2, e2 = wait.pop() assert p2 in tree if p1 in tree: # new cycle? if (p1, e1) > (p2, e2): continue polys = [p1] edges = [] edges_rev = [] p1, e, e_back = tree[p1] while p1 is not None: edges.append(e_back) edges_rev.append(e) polys.append(p1) p1, e, e_back = tree[p1] polys.reverse() edges.reverse() edges_rev.reverse() polys.append(p2) edges.append(e1) edges_rev.append(e2) p2, e, e_back = tree[p2] while p2 is not None: edges.append(e) edges_rev.append(e_back) polys.append(p2) p2, e, e_back = tree[p2] basis.append((polys, edges, edges_rev)) else: # new branch tree[p1] = (p2, e1, e2) for e in range(len(s.polygon(p1).vertices())): if e != e1: pp, ee = s.opposite_edge(p1, e) wait.append((pp, ee, p1, e)) basis.sort() return tuple([self.element_class(self, p, e, er) for p, e, er in basis])