Bounds for several-disk packings of hyperbolic surfaces
Jason DeBlois




Department of Mathematics, University of Pittsburghjdeblois@pitt.edu

  For any given k∈ℕ, this paper gives upper bounds on the radius of a packing of a complete hyperbolic surface of finite area by k equal-radius disks in terms of the surface's topology.  We show that these bounds are sharp in some cases and not sharp in others.

Bounds for several-disk packings of hyperbolic surfaces
    Jason DeBlois
    18 november 2016
=======================================================



By a packing of a metric space we will mean a collection of disjoint open metric balls.  This paper considers packings of a fixed radius on finite-area hyperbolic (i.e. constant curvature -1) surfaces, and our methods are primarily those of low-dimensional topology and hyperbolic geometry.  But before describing the main results in detail I would like to situate them in the context of the broader question below, so I will first list some of its other instances, survey what is known toward their answers, and draw analogies with the setting of this paper:

  For a fixed k∈ℕ and topological manifold M that admits a complete constant-curvature metric of finite volume, what is the supremal density of packings of M by k balls of equal radius, taken over all such metrics with fixed curvature? (Here the density of a packing is the ratio of the sum of the balls' volumes to that of M.)

The botanist P.L. Tammes posed a positive-curvature case of Question <ref> which is now known as Tammes' problem, where M = 𝕊^2 with its (rigid) round metric, in 1930.  Answers (i.e. sharp density bounds) are currently known for k≤ 14 and k=24 after work of many authors, with the k=14 case only appearing in 2015 <cit.> (the problem's history is surveyed in 1.2 there).  

In the Euclidean setting, the case of Question <ref> with M an n-dimensional torus is equivalent to the famous lattice sphere packing problem, see eg. <cit.>, when k=1.  When k>1 it is the periodic packing problem; and finding the supremum over all k is equivalent to the sphere packing problem, which is solved only in dimensions 2, 3 <cit.> and, very recently, 8 <cit.> and 24 <cit.>.  The lattice sphere packing problem is solved in all additional dimensions up to 8, see <cit.>.

The hyperbolic case is also well studied.  Here a key tool, known in low-dimensional topology as “Böröczky's theorem", asserts that any packing of ℍ^n by balls of radius r has local density bounded above by the density in an equilateral n-simplex with sidelength 2r of its intersection with balls centered at its vertices <cit.>.  Rogers proved the analogous result for Euclidean packings earlier <cit.>.  We note that in the hyperbolic setting the bound depends on r as well as n.

Böröczky's theorem yields bounds towards an answer to Question <ref> for an arbitrary k∈ℕ and complete hyperbolic manifold M, since a packing of M has a packing of ℍ^n as its preimage under the universal cover ℍ^n→ M.  Analogously, Rogers' result yields bounds toward the lattice sphere packing problem, which until recently were still the best known in some dimensions (see <cit.>).  This basic observation is particularly useful in low dimensions: for instance Rogers' lattice sphere packing bound is sharp only in dimension 2 (where it is usually attributed to Gauss).  In the three-dimensional hyperbolic setting, where Böröczky's Theorem was actually proved earlier by Böröczky–Florian <cit.>, its “r=∞” (i.e. horoball packing) case yields sharp lower bounds on the volumes of cusped hyperbolic 3-orbifolds <cit.> and 3-manifolds <cit.>, for example.

In dimension two, C. Bavard observed that Böröczky's theorem implies answers to the k=1 case of Question <ref> for every closed hyperbolic surface F <cit.>; that is, it yields sharp bounds on the maximal radius of a ball embedded in such a surface.  The same argument yields bounds towards Question <ref> for arbitrary k and hyperbolic surfaces F, as we will observe in Section <ref>.  This was already shown for closed genus-two surfaces when k=2, by Kojima–Miyamoto <cit.>.

For a non-compact surface F of finite area, it is no longer true that a maximal-density packing of F pulls back to a packing of ℍ^2 with maximal local density: the cusps of F yield “empty horocycles", large vacant regions in the preimage packing.  In <cit.> I introduced a new technique for proving two-dimensional packing theorems and used it to settle the k=1 case of Question <ref> for arbitrary complete, orientable hyperbolic surfaces of finite area.  M. Gendulphe has since released a preprint which resolves the non-orientable k=1 cases by another method <cit.>.  But the restriction to orientable surfaces in <cit.> is not necessary, as I show in Section <ref> below.  The first main result here records density bounds for arbitrary k∈ℕ and complete, finite-area hyperbolic surfaces (orientable or not) which follow from the packing theorems of <cit.>.

In fact we bound the radius of packings.  But this is equivalent to bounding their density, since the area of a hyperbolic disk is determined by its radius, and by the Gauss–Bonnet theorem the area of a complete, finite-area hyperbolic surface is determined by its topological type.


plain
*VorBoundPropProposition <ref>


Above, a horocyclic ideal triangle is the convex hull in ℍ^2 of three points, two of which lie on a horocycle C with the third at the ideal point of C.  We prove Proposition <ref> in Section <ref>.

To my knowledge, the bounds of Proposition <ref> are the best in the literature for every k, χ and n.  They coincide with those from Böröczky's Theorem in the closed (n=0) case but are otherwise stronger, see Proposition <ref>.  But as we show below, they are not sharp in general; indeed, it is easy to see that they are not attained in general.  For a closed surface F with Euler characteristic χ attaining the bound of r_χ,0^k, the equilateral triangles that decompose F all have equal vertex angles, since they have equal side lengths.  It follows that its triangulation must be regular; that is, each vertex must see the same number of triangles.  This imposes the condition that k divide 6χ, since the number of such triangles is 2(k-χ) by a simple computation.

In this sense Proposition <ref> is akin to L. Fejes Tóth's general bound toward Tammes' problem <cit.>, which is attained only for k=3, 4, 6, and 12: those for which S^2 has a regular triangulation with k vertices. (The last three are realized by the boundaries of a tetrahedron, octahedron, and icosahedron, respectively).  When the bound is attained in the non-compact (n>0) case, one correspondingly expects both equilateral and horocyclic ideal triangle vertices to be “evenly distributed”.  Lemma <ref> formulates this precisely, and shows that it imposes the conditions that k divide both 6χ and n.  The second main result of this paper shows that the bound is attained when these conditions hold.


*attained theoremTheorem <ref>


The non-trivial part of the proof is the purely topological Proposition <ref>, which constructs closed surfaces of Euler characteristic χ+n, triangulated with k+n vertices of which n have valence one, when k divides both 6χ and n.  (The valence-one vertices correspond to cusps of F.)  Previous work of Edmonds–Ewing–Kulkarni <cit.> covers the n=0 cases of Proposition <ref> but its techniques, which exploit the existence of certain branched coverings in this setting, do not naturally extend to the n>0 cases.  The proof here is independent of <cit.>, even for n=0.

I could not prove in the n>0 case that the bound r_χ,n^k is attained only if k divides both 6χ and n.  But I do show in Lemma <ref> that for a given χ<0 and n>0, it is attained only at finitely many k.  Section <ref> goes on to establish:


*not attained theoremTheorem <ref>


This follows immediately from Lemma <ref> and the main result Proposition <ref> of Section <ref>, which asserts for each χ and n that the function on the entire moduli space of all (orientable or non-orientable) hyperbolic surfaces with Euler characteristic χ and n cusps which measures the maximal k-disk packing radius does attain a maximum.  (This is not obvious because the function in question is not proper, see <cit.> in the case k=1.) Key to the proof of Proposition <ref> is Lemma <ref>, which asserts that the thick part of a surface with a short geodesic can be inflated while increasing the length of the geodesic.  Proposition <ref> and its proof were suggested by a referee for <cit.>, and sketched by Gendulphe <cit.>, in the case k=1.  

I'll end this introduction with a couple of further questions.  First, recall from the discussion above that Lemma <ref> is is likely not best possible.  It would be interesting to know whether the bound of Theorem <ref> is attained in any cases beyond those covered by Theorem <ref>.

  For χ< 0 and n> 0, does there exist any k not dividing both n and 6χ for which a complete hyperbolic surface of finite area with n cusps and Euler characteristic χ admits a packing by k disks that each have radius r_χ,n^k?

For any example not covered by Theorem <ref>, some observations from the proof of Lemma <ref> can be used to show that α(r_χ,n^k) and β(r_χ,n^k) must satisfy an additional algebraic dependence beyond what is prescribed in Theorem <ref>.  While this seems unlikely, it is not clear (to me at least) that it does not ever occur.  In a follow-up paper I will consider the case of two disks on the three-punctured sphere, showing that at least in this simplest possible case it does not.

It would also be interesting to know whether k-disk packing radius has local but non-global maximizers.  We phrase the question below in the language introduced above Proposition <ref>.

  For which smooth surfaces Σ and k∈ℕ does the function _k from Definition <ref> have a local maximum on 𝔗(Σ) that is not a global maximum?  In particular, can this occur if k divides both 6χ and n, where χ is the Euler characteristic of Σ and n its number of cusps?

Gendulphe answered this “no” for k=1 <cit.>, extending my result on the orientable case <cit.>.



 §.§ Acknowledgements
  Thanks to Dave Futer for a keen observation, and for pointing me to <cit.>, and to Ian Biringer for a helpful conversation.  Thanks also to the anonymous referee for a careful reading and helpful comments.




§ DECOMPOSITIONS OF ORIENTABLE AND NON-ORIENTABLE SURFACES


The bound of <cit.>, which Proposition <ref> generalizes, is proved using the centered dual complex plus as defined in Proposition 5.9 of <cit.>.  This is a decomposition of a finite-area hyperbolic surface F that is canonically determined by a finite subset of F.  In this section we will first recap the construction of the centered dual plus, and show that <cit.> carries through to the non-orientable case without revision.  Then we will prove Proposition <ref>.

Let F be a complete, finite-area hyperbolic surface, ⊂ F a finite set, and πℍ^2→ F a locally isometric universal cover.  We will assume here that F is non-orientable, since the orientable case is covered by previous work, and let F_0 be the orientable double cover of F and _0 be the preimage of  in F_0.  Note that π factors through a locally isometric universal cover pℍ^2→ F_0, so in fact =p^-1(_0).
This set is invariant under the isometric actions of π_1 F and π_1 F_0 by covering transformations.

Theorem 5.1 of <cit.>, which is a rephrasing of <cit.> for surfaces, asserts the existence of a π_1 F_0-invariant Delaunay tessellation of p^-1(_0) characterized by the following empty circumcircles condition:

For each circle or horocycle S of ℍ^2 that intersects  and bounds a disk or horoball B with B∩ = S∩, the closed convex hull of S∩ in ℍ^2 is a Delaunay cell. Each Delaunay cell has this form.

Since this characterization is in purely geometric terms it implies that the Delaunay tessellation is invariant under every isometry that leaves  invariant.  In particular, it is π_1 F-invariant.  In fact the entire <cit.> extends to the non-orientable case; one needs only additionally observe that the parabolic fixed point sets of π_1 F and π_1 F_0 are identical. We will now run through the remaining results of Sections 5.1 and 5.2 of <cit.>, which build to Proposition 5.9 there, and comment on their extensions to the non-orientable case.  

Corollary 5.2 of <cit.> makes three assertions about properties of the Delaunay tessellation's image in the quotient surface, which all extend directly to the non-orientable case.  The first, on finiteness of the number of π_1 F_0-orbits of Delaunay cells, implies the same for π_1 F-orbits.  The original proof (in <cit.>) of the the second, on interiors of compact cells embedding, applies directly.  In our setting, the third assertion is that for each non-compact Delaunay cell C_u, which is invariant under some parabolic subgroup Γ_u of π_1 F_0, p|_𝑖𝑛𝑡 C_u factors through an embedding of 𝑖𝑛𝑡 C_u/Γ_u to a cusp of F_0.  Here we have:

  The stabilizer of C_u in π_1 F is also Γ_u; each cusp of F_0 projects homeomorphically to F; and π|_𝑖𝑛𝑡 C_u factors through an embedding of 𝑖𝑛𝑡 C_u/Γ_u to a cusp of F.

  The stabilizer of C_u in the full group of isometries of ℍ^2 is the stabilizer of the ideal point u of the horocycle S in which it is inscribed.  Using the upper half-plane model and translating u to ∞, standard results on the classification of isometries (see eg. <cit.>) imply that this group is the semidirect product

    {([ 1 x; 0 1 ]) :  x∈ℝ}⋊{z↦ -z̅}

with the index-two translation subgroup preserving orientation.  One sees directly from the classification that every orientation-reversing element here reflects about a geodesic.  Since π_1 F acts freely on ℍ^2, every element that stabilizes C_u preserves orientation.  But π_1 F_0 consists precisely of those elements of π_1 F that preserve orientation.  The lemma's first assertion follows directly, and the latter two follow from that one.

The main result of Section 5.1 of <cit.>, Corollary 5.6, still holds if its orientability hypothesis is dropped.  This implies for us that the centered dual complex of S is π_1 F-invariant and its two-cells project to F homeomorphically on their interiors.  The centered dual complex is constructed in <cit.>; in particular see Definition 2.26 there, and it is the object to which the main packing results Theorems 3.31 and 4.16 of <cit.> apply.

The proof of <cit.> given there in fact applies without revision in the non-orientable case.  To this end we note that the Voronoi tessellation of  and its geometric dual (see <cit.> and the exposition above it) are by their construction invariant under every isometry preserving .  And the proofs of Lemmas 5.4 and 5.5, and Corollary 5.6, do not use the hypothesis that elements of π_1 F preserve orientation, only that they act isometrically and are fixed point-free. 

Section 5.2 of <cit.> builds to the description of the centered dual complex plus in Proposition 5.9, its final result.  The issue here is that if F has cusps then the underlying space of the centered dual decomposition is not necessarily all of ℍ^2, but rather the union of all geometric dual cells (which are precisely the compact cells of the Delaunay tessellation, by <cit.>) with possibly some horocyclic ideal triangles.  But Lemma 5.8 of <cit.> shows that each non-compact Delaunay cell C_u intersects this underlying space in a sub-union of the collection of horocyclic ideal triangles obtained by joining each of its vertices to its ideal point u by a geodesic ray.  So the centered dual plus is obtained by simply adding two-cells (and their edges and ideal vertices) to the centered dual, one for each horocyclic ideal triangle  obtained from each C_u as above that does not already lie in a centered dual two-cell.

The proof of <cit.> again extends without revision to the non-orientable  setting, and provides the final necessary ingredient for:

  Proposition 5.9 of <cit.> still holds if F is not assumed oriented.

Having established this, we turn to the first main result.



 The first part of this proof closely tracks that of Theorem 5.11 in <cit.>.  Given a complete, finite-area hyperbolic surface F of Euler characteristic χ with n cusps, equipped with an equal-radius packing by k disks of radius r, we let  be the set of disk centers.  Fixing a locally isometric universal cover πℍ^2→ F, let = π^-1() and, applying Proposition <ref>, enumerate a complete set of representatives for the π_1 F-orbits of cells of the centered dual complex plus as {C_1,,C_m}.  By the Gauss–Bonnet theorem the C_i satisfy:

    Area(C_1) +  + Area(C_m) = -2πχ

Take C_i non-compact if and only if i≤ m_0 for some fixed m_0≤ m, and for each i≤ m let n_i be the number of edges of C_i.  Each compact edge of the decomposition has length at least d = 2r, since it has disjoint open subsegments of length 2r around each of its vertices.  For i≤ m_0 we therefore have the key area inequality obtained from <cit.> and some calculus:

    Area(C_i) ≥ D_0(∞,d,∞) + (n_i-3)D_0(d,d,d),

with equality holding if and only if n_i=3 and the compact side length is d.  Here D_0(∞,d,∞) is the area of a horocyclic ideal triangle with compact side length d, and D_0(d,d,d) is the area of an equilateral hyperbolic triangle with all side lengths d.

For m_0 < i ≤ m, again as described in the proof of Theorem 5.11 of <cit.>, Theorem 3.31 there and some calculus give

    Area(C_i) ≥ (n_i-2) D_0(d,d,d),

with equality if and only if n_i=3 and all side lengths are d.  We therefore have:
    -2πχ   ≥ m_0 · D_0(∞,d,∞) + (∑_i=1^m (n_i-2) - m_0)· D_0(d,d,d) 
       ≥ n · D_0(∞,d,∞) + (∑_i=1^m n_i - 2m - n) · D_0(d,d,d) 
        = n· (π-2β(r)) + (2e-2m - n)· (π-3α(r))

In moving from the first to the second line above, we have used the fact that m_0≥ n and D_0(∞,d,∞) > D_0(d,d,d) (again see the proof of <cit.>) to trade m_0-n instances of D_0(∞,d,∞) down for the same number of D_0(d,d,d).  In moving from the second to the third we have rewritten ∑_i=1^m n_i as 2e, where e is the total number of edges, and used the angle deficit formula for areas of hyperbolic triangles (recall from above that d=2r).

We will now apply an Euler characteristic identity satisfied by the closed surface F̅ obtained from F by compactifying each cusp with a unique marked point.  By Proposition <ref> the C_i project to faces of a cell decomposition of F̅.  This satisfies v-e+f = χ(F̅), where v, e and f are the total number of vertices, edges, and faces, respectively.  For us this translates to

    n+k - e + m = χ+n,

since χ(F̅) = χ+n.  Here there are n+k vertices of the centered dual plus decomposition of F̅: k that are disk centers, and n that are marked points.  As above we have called the number of edges e, and the number of faces is m.  Now substituting 2k-2χ for 2e-2m on the final line of (<ref>), after simplifying we obtain

    (6 - 6χ+3n/k)α(r) + 2n/kβ(r) ≥ 2π

Since α and β are decreasing functions of r we obtain that r≤ r_χ,n^k.  

As we noted above the inequalities (<ref>), equality holds on the first line if and only if n_i=3 for each i, i.e. each C_i is a triangle, and all compact sides have length d=2r.  This implies in particular that the compact centered dual two-cells (the C_i for i>m_0) are all Delaunay two-cells, and the non-compact cells are obtained by dividing horocyclic Delaunay cells of  into horocyclic ideal triangles by rays from vertices.  As we noted below (<ref>), equality holds on the second line if and only if m_0 = n; that is, each cusp corresponds to a unique horocyclic ideal triangle.  Thus when r = r^k_χ,n, F decomposes into equilateral and n horocyclic ideal triangles with all compact sidelengths equal to 2r_χ,n^k.

In this case, one finds by inspecting the definition of the centered dual plus that every compact centered dual two-cell is a Delaunay triangle, and every non-compact cell is obtained from a Delaunay monogon by subdividing it by a single arc from its vertex out its cusp.  To prove the Proposition it thus only remains to show that a surface  of Euler characteristic χ and n cusps which decomposes into equilateral triangles and n horocyclic ideal triangles, all with compact sidelength 2r_χ,n^k, with k vertices, admits a packing by k disks of radius r_χ,n^k centered at the vertices.

This follows the line of argument from Examples 5.13 and 5.14 of <cit.>.  Lemma 5.12 there implies in particular that an open metric disk of radius r_χ,n^k centered at a vertex v of an equilateral triangle T in ℍ^2 with all sidelengths 2r_χ,n^k intersects T in a full sector with angle measure equal to the interior angle of T at v.  It is not hard to show that the same holds for a disk centered at a finite vertex of a horocyclic ideal triangle.  In both cases it is clear moreover that disks of radius r centered at distinct (finite) vertices of such triangles do not intersect.  Therefore for a surface decomposed into a collection of equilateral and horocyclic ideal triangles with all compact sidelengths 2r_χ,n^k, a collection of disjoint embedded open disks of radius r_χ,n^k centered at the vertices of the decomposition is assembled from disk sectors in each triangle around each of its vertices.





§ COMPARING BOUNDS


In this section we give brief accounts of two arguments that give alternative bounds on the k-disk packing radius: a naive bound r_A^k and a bound from Böröczky's Theorem <cit.> that turns out to simply be r_χ,0^k.  These arguments are not original, in particular the latter can essentially be found in <cit.> and <cit.>.  We will then compare the bounds in Proposition <ref>.

[The naive bound]  If k disks of radius r are packed in a complete finite-area surface F then the sum of their areas is no more than that of F.  The area of a hyperbolic disk of radius r is 2π(cosh r - 1) (see eg. <cit.>), and the Gauss–Bonnet theorem implies that the area of a complete, finite-area hyperbolic surface F with Euler characteristic χ is -2πχ.  Therefore 2π(cosh r -1)· k ≤ -2πχ, whence r ≤ r_A^k defined by

    cosh(r_A^k) = 1-χ/k



[Böröczky's bound]  Suppose again that k disks of radius r are packed in a complete, finite-area surface F.  Fix a locally isometric universal cover πℍ^2→ F and consider the the preimage of the disks packed on F, which is a packing of ℍ^2 by disks of radius r.  Each disk D in the preimage determines a Voronoi 2-cell V (see eg. Section 1 of <cit.>), and for α as in Theorem <ref> Böröczky's theorem asserts the following bound on the density of D in V:

    Area(D)/Area(V)≤3α(r)(cosh r -1)/π-3α(r)  ⇒    2π(π/3α(r) - 1)≤Area(V)

We obtain the right-hand inequality above upon substituting for Area(D) and simplifying.

The packing of ℍ^2 by the preimage of the disks on F is invariant under the action of π_1 F by covering transformations, so this is also true of its Voronoi tessellation.  Moreover since there is a one-to-one correspondence between disks and Voronoi 2-cells, a full set {D_1,,D_k} of disk orbit representatives determines a full set {V_1,,V_k} of Voronoi cell orbit representatives.  Their areas thus sum to that of F.  If F has Euler characteristic χ then summing the right-hand inequalities above and applying the Gauss–Bonnet theorem yields

    2π(π/3α(r) - 1)· k ≤ -2πχ  ⇒  π≤(1-χ/k)3α(r)

From the formula α(r) = 2sin^-1(1/(2cosh r)), we see that α decreases with r.  Comparing with the equation defining r_χ,n^k in Theorem <ref>, we thus find that this inequality implies r≤ r_χ,0^k.

The relationship between the bounds r_A^k, r_χ,0^k and r_χ,n^k is perhaps not immediately clear from their formulas in all cases.  The result below clarifies this.

  For any fixed χ<0 and n≥ 0, and k∈ℕ, r_χ,n^k ≤ r_χ,0^k < r_A^k.  The inequality r_χ,n^k≤ r_χ,0^k is strict if and only if n>0.

  We first compare r_χ,0^k with r_χ,n^k when n>0.  We will apply Corollary 5.15 of <cit.>, which asserts for any r>0 that 2β(r) < 3α(r).  Slightly rewriting the equation defining r_χ,n^k gives:

    2π = (6-6χ/k)α(r_χ,n^k) + n/k(2β(r_χ,n^k)-3α(r_χ,n^k)) < (6-6χ/k)α(r_χ,n^k)

Since α decreases with r, and r_χ,0^k is defined by setting the right side of the inequality above equal to 2π, it follows that r_χ,n^k < r_χ,0^k.

We now show that r_χ,0^k < r_A^k for each χ and k.  Recall that α(r) = 2sin^-1(1/(2cosh r)).  The inverse sine function is concave up on (0,1) and takes the value 0 at 0 and π/6 at 1/2, so α(r_χ,0^k) < π/(3cosh r_χ,0^k).  Plugging back into the definition of r_χ,0^k, and comparing with that of r_A^k, yields the desired inequality.




§ SOME EXAMPLES SHOWING SHARPNESS


In this section we'll prove Theorem <ref>, which asserts that the bound r_χ,n^k of Proposition <ref> is attained under certain divisibility hypotheses.  We begin with a simple counting lemma recording the  combinatorial condition that motivates these hypotheses.

  Suppose F is a complete, orientable hyperbolic surface of finite area with Euler characteristic χ<0 and n≥ 0 cusps that decomposes into a collection of compact and horocyclic ideal triangles that intersect pairwise (if at all) only at vertices or along entire edges, such that there are k vertices and exactly n horocyclic ideal triangles.  

If there exist fixed i and j such that each vertex of the decomposition of F is the meeting point of exactly i compact and j horocyclic ideal triangle vertices, then k divides both n and 6χ, and

    i = 6-6χ+3n/k     j = 2n/k.


  The closed surface F̅ obtained from F by compactifying each cusp with a single point has Euler characteristic χ+n, and the given decomposition determines a triangulation of F̅ with k+n vertices, where each horocyclic ideal triangle has been compactified by the addition of a single vertex at its ideal point.  Since F has n cusps and n horocyclic ideal triangles, each horocyclic ideal triangle encloses a cusp, its non-compact edges are identified in F, and the quotient of these edges has one endpoint at the added vertex (which has valence one).

Noting that the numbers e, of edges, and f, of faces of the triangulation of F̅ satisfy 2e = 3f, computing its Euler characteristic gives:
    v-e+f = k+n - f/2 = χ+n

Therefore F has a total of 2(k-χ) triangles, of which 2(k-χ)-n are compact.  Since each compact triangle has three vertices and each horocyclic ideal triangle has two, even distribution of vertices determines the counts i and j above.  These imply in particular that k must divide both 2n and 6χ+3n.  But we note that in fact k must divide n, since the two vertices of each horocyclic ideal triangle are identified in F, and therefore k must also divide 6χ.

A condition equivalent to the hypothesis of Lemma <ref> on a topological surface in fact ensures the existence of a hyperbolic structure satisfying the conclusion of Theorem <ref>.

 For χ<0 and n≥ 0, suppose S is a closed surface with Euler characteristic χ+n and n marked points that is triangulated with k+n vertices, including the marked points, with the following properties:
  
  * Each marked point is contained in exactly one triangle, which we also call .
  
  * There exist fixed i,j≥ 0 such that exactly i non-marked and j marked triangle vertices meet at each of the remaining k vertices.
Then there is a complete hyperbolic surface F of finite area that decomposes into a collection of equilateral and exactly n horocyclic ideal triangles intersecting pairwise only at vertices or along entire edges, if at all; and there is a homeomorphism f S-𝒫→ F, where 𝒫 is the set of marked points, taking non-marked triangles to equilateral triangles and each marked triangle, less its marked vertex, to a horocyclic ideal triangle. 

F is unique with this property up to isometry. That is, for any complete hyperbolic surface F' and homeomorphism f' S-𝒫→ F' satisfying the conclusion above, there is an isometry ϕ F'→ F such that f is properly isotopic, preserving triangles, to ϕ∘ f'. Also, F has a packing by k disks of radius r_χ,n^k, each centered at the image of a non-marked vertex of S.

Here a triangulation of a surface, possibly with boundary, is simply a homeomorphism to the quotient space of a finite disjoint union of triangles by homeomorphically pairing certain edges.  If the surface has boundary then not all edges must be paired.

In this section we will also prove existence of the triangulations required in Proposition <ref>.

  For any χ< 0 and n≥ 0, and any k∈ℕ that divides both 6χ and n, there is a closed non-orientable surface with Euler characteristic χ+n and n marked points that is triangulated with k+n vertices, including the marked points, with the following properties:
  
  * Each marked point is contained in exactly one triangle, which we also call .
  
  * Exactly i non-marked and j marked triangle vertices meet at each of the remaining k vertices, where i and j are given by (<ref>).
If χ+n is even then there is also an orientable surface of Euler characteristic χ+n with n marked points and such a triangulation.

The main result of this section follows directly from combining Proposition <ref> with <ref>.





 §.§ Geometric surfaces from triangulations
 We now proceed to prove the Propositions above. This subsection gives a standard argument to prove Proposition <ref>.

 Let S be a closed topological surface with a collection 𝒫 of n marked points, triangulated with k+n vertices satisfying the Proposition's hypotheses. Applying the Euler characteristic argument from the proof of Lemma <ref> with S in the role of F̅ there gives that there are 2(k-χ)-n non-marked triangles, and hence that i and j are given by (<ref>). By definition, S is a quotient space of a disjoint union of triangles by pairing edges homeomorphically. We will produce our hyperbolic surface F by taking a disjoint union of equilateral and horocyclic ideal triangles in ℍ^2 corresponding to the triangles of S and pairing their edges to match.

Number the non-marked triangles of the disjoint union giving rise to S from 1 to m, where m = 2(k- χ)-n.  Let T_1,,T_m be a collection of disjoint equilateral triangles in ℍ^2 with side lengths 2r_χ,n^k, and for 1≤ s≤ m fix a homeomorphism from T_s to the non-marked triangle numbered s. Number the marked triangles giving rise to S from 1 to n, let H_1,,H_n be disjoint horocyclic ideal triangles each with compact side length 2r_χ,n^k, and for each t fix a homeomorphism from H_t to the complement, in the t^th marked triangle, of its marked vertex.

We now form a triangulated complex F as a quotient space of (  T_s)⊔( H_t) by identifying edges of the T_s and H_t in pairs. For each s and t such that the images of T_s and T_t (or T_s and H_t, or H_s and T_t) share an edge, identify the corresponding edges of the geometric triangles by an isometry, choosing the one that is isotopic to the homeomorphism that pairs their images in the edge-pairing of marked and non-marked triangles that has quotient S.  Also isometrically identify the two non-compact edges of each H_t.  Since S is closed, and each of its marked vertices lies in a single triangle (hence also a single edge), this pairs off all edges of the T_s and H_t in F. And our choices of edge-pairings ensure that the homeomorphism from (  T_s)⊔( H_t) to the corresponding collection of triangles for S (less n vertices) can be adjusted by an isotopy to induce a homeomorphism F→ S-𝒫. Its inverse is the map f from the Proposition's statement. 

A standard argument now shows that F is a hyperbolic surface by describing a family of chart maps to ℍ^2 with isometric transition functions.  This argument is essentially that of, say, <cit.>, so we will only give a bare sketch of ideas.  The quotient map (  T_s)∪( H_t)→ F has a well-defined inverse on the interior of each triangle, and this yields charts for points that lie outside the triangulation's one-skeleton.  For a point p in the interior of an edge of intersection between the images of, say, T_s and T_s, there is a chart that maps p to its preimage p̃ in T_i.  It sends the intersection of a neighborhood of p with the image of T_s into an isometric translate of T_t that intersects T_s along the edge containing p̃.

Similarly, for each vertex p of the triangulation, a chart around p is given by choosing a preimage p̃ of p in some triangle whose image contains p, then isometrically translating all other triangles whose images contain p so that they have a vertex at p̃.  The idea is to choose these isometries so that each translate intersects the translate of the triangle before it (as their images are encountered, proceeding around the boundary of a small neighborhood U of p in F) in an edge containing p̃.  It is key that by the definition of r_χ,n^k in Proposition <ref> we have

    (6-6χ+3n/k)α(r_χ,n^k) + 2n/kβ(r_χ,n^k) = 2π.

And since p lies in 6-6χ+3n/k equilateral triangle vertices and 2n/k horocyclic ideal triangle vertices by hypothesis, upon proceeding all the way around the boundary of U we find that the union of isometric translates entirely encloses a neighborhood of p̃ in ℍ^2 that is isometric to U.

For each horocyclic ideal triangle H_t, the isometry that identifies the two non-compact edges of H_t is a parabolic fixing its ideal point u.  This implies that each cross-section of H_t by a horocycle with ideal point u has its endpoints identified, so Theorem 11.1.4 of <cit.> implies that F is complete. Proposition <ref> now implies that F has a packing by k disks of radius r_χ,n^k centered at the vertices of the triangulation of F.  

Any two equilateral triangles in ℍ^2 with the same side length are isometric, and the full combinatorial symmetry group of any equilateral triangle is realized by isometries (these facts are standard). Analogously, two horocyclic ideal triangles with the same compact side length are isometric (this is easy to prove bare hands, or cf. <cit.>), and every one has a reflection exchanging its two vertices in ℍ^2. It follows that if f' S-𝒫→ F' has the same properties as F then an isometry ϕ F'→ F can be defined triangle-by-triangle so that f and ϕ∘ f' take each vertex, edge, and triangle of S to identical corresponding objects in F, and that their restrictions to any edge are properly isotopic through maps to an edge of F. Adjusting ϕ∘ f' further on each triangle yields a proper isotopy to f.




 §.§ Constructing triangulated surfaces
  In this subsection we construct surfaces with prescribed triangulations to prove Proposition <ref>. We will treat the orientable and non-orientable cases separately, and it will be useful at times to think in terms of genus rather than Euler characteristic.  Here the genus of an orientable (or, respectively, non-orientable) closed surface is the number of summands in a decomposition as a connected sum of tori (resp. projective planes).  We declare the genus of a compact surface with boundary to be that of the closed surface obtained by adjoining a disk to each boundary component.  We now recall the fundamental relationship between the genus, number of boundary components, and Euler characteristic:
    χ(F_𝑜𝑟) = 2 - 2g_𝑜𝑟 - b       χ(F_𝑛𝑜𝑛) = 2 - g_𝑛𝑜𝑛 - b

On the left side above, F_𝑜𝑟 is a compact, orientable surface of genus g_𝑜𝑟≥ 0, and on the right, F_𝑛𝑜𝑛 is non-orientable of genus g_𝑛𝑜𝑛≥ 1, with b≥ 0 boundary components in each case.

In proving Proposition <ref>, we will find it convenient to track the “triangle valence" of vertices.

  We take the triangle valence of a vertex v of a triangulated surface to be the number of triangle vertices identified at v.

Since the link of a vertex v in a closed triangulated surface is a circle, the triangle valence of v coincides with its valence as usually defined: the number of edge endpoints at v.  However for a vertex on the boundary of a triangulated surface with boundary, the triangle valence is one less than the valence.  It is convenient to track triangle valence since it is additive under the operation of identifying surfaces with boundary along their boundaries.

The proof is a bit lengthy and technical, though completely elementary, so before embarking on it we give an overview.  We build every triangulated surface by identifying boundary components in pairs from a fixed collection of “building blocks” constructed in a sequence of Examples.  Each building block is a compact surface with boundary which is triangulated with all non-marked vertices on the boundary, an equal number of vertices per boundary component, and all (non-marked) vertices of equal valence. To give an idea of what we will construct, we have collected data on our orientable building blocks without marked vertices in Table <ref>.



In the Table, columns correspond to the triangulated building blocks Σ_g,b (of orientable genus g with b boundary components), rows to the number of vertices per boundary component, and table entries to the triangle valence of each vertex.  And the number in parentheses directly below each Σ_g,b refers to the Example where it is triangulated.

We use these building blocks in Lemma <ref> to prove the orientable closed (i.e. without marked vertices) case of Proposition <ref>. We then proceed to the non-orientable closed case, in Lemma <ref>, after adding a few non-orientable building blocks to the mix in Examples <ref> and <ref>. Each Lemma's proof has several cases, featuring different combinations of building blocks, determined by certain divisibility conditions on the total number of vertices k.

As we remarked in the introduction, the closed case of Proposition <ref> is the p=3 case of the main theorem of Edmonds–Ewing–Kulkarni <cit.>, which is proved by a different method involving branched covers.  The advantage of our proof is that each closed surface constructed in Lemmas <ref> and <ref> has a collection of disjoint simple closed curves, coming from the building blocks' boundaries, which are unions of edges and whose union contains every vertex. This allows us to extend to the case of n>0 marked vertices (a case not covered in <cit.>) by “unzipping” each edge in each such curve and inserting a copy of a final building block constructed in Example <ref>, homeomorphic to a disk, with marked vertices in its interior. We handle this case below that Example, completing the proof of Proposition <ref>.

  It is a simple exercise to show that an annulus Σ_0,2 can be triangulated with one, two, or three vertices on each boundary component, and each such triangulation can be arranged so that each vertex has triangle valence three.  We will also use three- and six-holed spheres Σ_0,3 and Σ_0,6 triangulated with two vertices per boundary component, and a four-holed sphere Σ_0,4 with three vertices per boundary component.  The three- and four-holed spheres are pictured in Figure <ref> on the left and in the middle, respectively.  Inspection of each reveals that each vertex has triangle valence four.

The right side of Figure <ref> shows a triangulated dodecagon, two copies of which are identified along alternating edges to produce a triangulated copy of Σ_0,6.  Precisely, for each even i we identify the edge e_i in one copy homeomorphically with e_i+6 in the other so that for each i, v_i = e_i∩ e_i+1 in the first copy is identified with v_i+6 in the other.  Note that for each i ≅0 modulo four, the vertex v_i is contained in 4 triangle vertices of the dodecagon, whereas v_i is in 3, 1, or 2 vertices for i≅1, 2, or 3, respectively.  Thus in the quotient six-holed sphere Σ_0,6, each vertex has triangle valence 5.  Each boundary component is the union of two copies of e_i along their endpoints for some odd i and so contains two vertex quotients, of v_i-1 and v_i.



  Here we will triangulate the orientable genus-g surface Σ_g,1 with one boundary component, for g≥ 1.  In fact we describe triangulations with one, two, and three vertices, all on the boundary and all with the same valence.

The standard construction of the closed, orientable genus-g surface takes a 4g-gon P_4g with edges labeled e_0,,e_4g-1 in counterclockwise order, and identifies e_i to e_i+2 via an orientation-reversing homeomorphism for each i<4g congruent to 0 or 1 modulo 4.  (Here the e_i inherit their orientation from the counterclockwise orientation on ∂ P_4g.)  We produce Σ_g,1 by identifying the first 4g edges of a (4g+1)-gon P_4g+1 in the same way, and making no nontrivial identifications on points in the interior of the final edge.  Any triangulation of P_4g+1 projects to a one-vertex triangulation of Σ_g,1 with its single vertex v on ∂Σ_g,1.  Such a triangulation has 4g-1 triangles, so v has triangle valence 12g-3.  The case g=1 is pictured on the left in Figure <ref>.





We may construct two- or three-vertex triangulations of Σ_g,1, each with all vertices on the boundary, by inserting one or two vertices, respectively, in the interior of the non-identified edge e_4g of P_4g+1.  If one vertex is inserted then we begin by joining it to each vertex e_i-1∩ e_i for 1≤ i ≤ 4g-1.  If two are inserted then the nearer one to e_0∩ e_4g is joined to e_i-1∩ e_i for 1≤ i ≤ 2g, and the other one is joined to e_i-1∩ e_i for 2g≤ i ≤ 4g-1.  See the middle and right side of Figure <ref> for the case g=1.  Note that in the resulting triangulations of Σ_g,1, the inserted vertices have lower valence than the quotient vertex v of those of P_4g+1.  

We can even out the valence by flipping edges.  An edge e that is the intersection of distinct triangles T and T' of a triangulated surface is flipped by replacing it with the other diagonal of the quadrilateral T∪ T'.  This yields a new triangulation in which each endpoint of e has its (triangle) valence reduced by by one, and each vertex opposite e has it increased by one.  In Σ_g,1, triangulated as prescribed in the paragraph above, the projection of each e_i begins and ends at v, and each vertex opposite e_i is an inserted vertex.  So flipping e_i reduces the valence of v and increases the valence of the inserted vertex, each by 2

In the the two-vertex triangulation of Σ_g,1 described above, the inserted vertex has triangle valence 4g.  Since there are a total of 4g triangles there are 12g triangle vertices total.  So after flipping e_i for g distinct i, each vertex of A_4g has triangle valence 6g.  In the three-vertex triangulation, each inserted vertex has triangle valence 2g+1, and there are 3(4g+1) triangle vertices total.  So after flipping all 2g distinct e_i, all vertices have triangle valence 4g+1.



 For each g≥ 1 we now triangulate the two-holed orientable surface Σ_g,2 of genus g with two boundary components.  Each triangulation will have all vertices on the boundary, each boundary component will have the same number of vertices (either one, two, or three) and each vertex will have the same valence.  We construct Σ_g,2 by identifying all but two of the edges of a 4n-gon P_4n in pairs, where n = g+1.

Label the edges of P_4n as e_0,,e_4n-1 in counterclockwise order, and for each k≠ 0,2n identify e_k with its diametrically opposite edge e_k+2n by an orientation-reversing homeomorphism.  The edge orientations in question here are inherited from the boundary orientation on ∂ P_4n.  So the initial vertex v_1 = e_0∩ e_1 of e_1 is identified with the terminal vertex v_2n+2 of e_2n+1.  Since v_2n+2 is the initial vertex of e_2n+2 it is also identified with the terminal vertex v_3 of e_2 and so on, so that in the end all vertices v_i for odd i<2n are identified with all vertices v_j for even j > 2n.  In particular the endpoints v_0 = v_4n and v_1 of e_0 are identified in the quotient.

Similarly, for all even i with 0<i≤ 2n, the vertices v_i are identified together with the vertices v_j for all odd j > 2n; and in particular the endpoints of e_2n are identified in the quotient.  The quotient Σ_g,2 by these identifications is thus a surface with two boundary components, one from e_0 and one from e_2n, each containing one of the two equivalence classes of vertices of P_4n.  Note that the 180-degree rotation of P_4n preserves the identifications and so induces an automorphism ρ of Σ_g,2 that exchanges its two boundary components and the vertex quotients they contain.







We may triangulate P_4n using arcs joining v_0 to v_j for 2n+1≤ j < 4n-1, v_2n to v_i for 1 ≤ i < 2n-1, and v_1 to v_2n+1.  The cases g=1 and g=2 (so P_8 and P_12, respectively) of this construction are pictured on the top line of Figure <ref>.  The resulting triangulations of Σ_g,2 are ρ-invariant, since for example ρ takes v_1 to v_2n+1, so the two vertices of Σ_g,2 have the same valence.  A triangulation of P_4n has 4n-2 triangles, so this is the number f of faces of the triangulation of Σ_g,2.  There are two vertices, and the number e of edges satisfies 2e-2 = 3f (note that the edges e_0 and e_2n belong to only one triangle each), so e = 3/2f+1. Therefore Σ_g,2 has Euler characteristic 2-2n.  Since it has two boundary components its genus is g as asserted.

We may re-triangulate Σ_g,2 with an additional one or two vertices per boundary component.  We first describe how to add one vertex, yielding a total of two vertices per boundary component.  We begin by adding vertices w_0 and w_2n to P_4n in the edges e_0 and e_2n, respectively.  Then triangulate the resulting (4n+2)-gon by joining w_0 to w_2n and each v_j for 2n < j ≤ 4n-1, and joining w_2n to each v_i for 1 ≤ i < 2n.  This is illustrated on the middle line of Figure <ref>.  The resulting triangulation of Σ_g,2 is ρ-invariant, so the two quotient vertices of the v_i have identical valence, as do the projections of w_0 and w_2n.

However it is plain to see that w_0 has triangle valence 2n+1: it is one vertex of each of the 2n triangles in the upper half of P_4n, and one of a unique triangle in the lower half.  But since there are 4n triangles there are 12n triangle endpoints, so the two quotient vertices of the v_i must each have triangle valence 4n-1.  As in Example <ref>, we even out the valence by flipping some of the e_i.  For each i between 1 and 2n-1, one of the triangles in Σ_g,2 containing e_i has w_0 as its opposite vertex, and the other has w_2n in this role.  If we flip e_i we thus increases the triangle valence of each of w_0 and w_2n by one, and since e_i has one endpoint at each quotient vertex of the v_i, it decreases each of their triangle valences by one.  Thus after flipping e_1 through e_n-1, all vertices of the new triangulation of Σ_g,2  have triangle valence 3n.

To re-triangulate Σ_g,2 with three vertices per boundary component, we begin by placing vertices u_0 and w_0 in the interior of e_0, in that order, and u_2n and w_2n in e_2n so that the 180-degree rotation of P_4n exchanges u_0 with u_2n and w_0 with w_2n.  Using line segments join w_0 to each of v_2,,v_n; join u_2n to each of v_n+1,,v_2n-1; join w_2n to each of v_2n+2,,v_3n; and join u_0 to each of v_3n+1,,v_4n-1.  Note that the collection of such line segments is rotation-invariant.  It divides P_4n into triangles and a single region with vertices u_0, w_0, v_n, v_n+1, u_2n, w_2n, u_3n and u_3n+1.  Triangulate this region by joining u_0 to w_2n and v_3n, w_0 to w_2n and u_2n, and v_n to u_2n.

The resulting triangulation of P_4n is still rotation-invariant, and moreover each of u_0 and w_0 has triangle valence n+2.  There are a total of 4n+2 triangles, with a total of 12n+6 vertices.  So flipping e_i for all i between 0 and 2n except n yields a triangulation of Σ_g,2 in which each vertex has triangle valence 2n+1 = 2g+3.


  In the special case g=1, the construction of Example <ref> yields a one-holed torus Σ_1,1 triangulated with one, two, or three vertices per boundary component such that each vertex has triangle valence 9, 6 or 5, respectively.  We may construct a b-holed torus Σ_1,b as a b-fold cover of Σ_1,1, where each boundary component projects homeomorphically to that of Σ_1,1.  One easily constructs such a cover by, say, joining a disk to Σ_1,1 along its boundary, taking a b-fold cover of the resulting torus, removing the preimage of the disk's interior and lifting a triangulation of Σ_1,1.  The triangle valence of vertices remains the same.

We now have enough building blocks to handle the orientable closed case of Proposition <ref>.

  For any g≥ 2 and any k∈ℕ that divides 12(g-1), the closed, orientable surface of genus g has a triangulation with k vertices, all of equal valence.

  For the case k=1 we observe that any triangulation of the 4g-gon P_4g descends to a one-vertex triangulation of the genus-g surface under the “standard construction” mentioned in Example <ref>.  So we assume below that k>1.   

By an Euler characteristic calculation, a k-vertex triangulation of the genus-g surface  has 4(g-1) + 2k triangles.  If the vertices have equal valence then each has valence 12(g-1)/k + 6.  Note that the number of vertices and their valence determines the genus, so below it is enough to exhibit k-vertex triangulations of closed, connected surfaces with vertices of the correct valence.  We break the proof into sub-cases depending on some congruence conditions satisfied by k.
  
  Case 1: 2 and 3 do not divide k  In this case k has no common factor with 12, so k divides g-1.  For g_0 = (g-1)/k, we claim that the desired surface is obtained by joining one copy of the one-holed genus-g_0 surface Σ_g_0,1 of Example <ref> to each of the k boundary components of Σ_1,k, where all building blocks are triangulated with one vertex per boundary component, so that vertices are identified.  
  
This follows from the fact that the vertex on Σ_g_0,1 has triangle valence 12g_0-3 and each vertex of Σ_1,k has triangle valence 9; that triangle valence adds upon joining boundary components; and that triangle valence coincides with valence for vertices of triangulated closed surfaces.  So each vertex of the resulting closed surface has valence:
  
    (12g_0-3)+9 = 12(g-1)/k + 6

  
  Case 2: 2 divides k, 3 and 4 do not  Now k/2 has no common factor with 12 and hence divides g-1.  So we use k/2 copies of Σ_g_0,2 from Example <ref>, where g_0 = 2(g-1)/k, each triangulated with one vertex on each boundary component.  We arrange them in a ring with a copy of the annulus Σ_0,2 placed between each pair of subsequent copies.  Each vertex of the resulting closed surface has valence:
  
    (6g_0+3)+3 = 12(g-1)/k + 6

  
  Case 3: 4 divides k, 3 does not  In this case we use k/4 copies of Σ_g_0,2, where g_0 = 4(g-1)/k, each triangulated with two vertices on each boundary component.  As in the previous case we arrange them in a ring interspersed with copies of Σ_0,2, so after joining boundaries each vertex has valence (3g_0+3) + 3 = 12(g-1)/k + 6.
  
  Case 4: 3 divides k, 2 does not  We take g_0 = 3(g-1)/k∈ℕ and join k/3 copies of Σ_g_0,1, each triangulated with 3 vertices per boundary component, to  Σ_1,k/3 with the corresponding triangulation to produce a closed triangulated surface.  Its vertices each have valence (4g_0+1)+5 = 12(g-1)/k + 6.
  
  Case 5: 6 divides k, 4 does not  We take g_0 = 6(g-1)/k∈ℕ and arrange k/6 copies of Σ_g_0,2, each triangulated with three vertices per boundary component, in a ring interspersed with copies of Σ_0,2.  The resulting closed, triangulated surface has vertices of valence (2g_0+3)+3 = 12(g-1)/k + 6.
  
  Case 6: 12 divides k  If 12(g-1)/k is even then we let g_0 = 12(g-1)/(2k), so that
  
    2g_0+3 = 12(g-1)/k + 3

As in the previous case we join k/6 copies of Σ_g_0,2, triangulated with three vertices per boundary component, in a ring interspersed with copies of Σ_0,2.  If 12(g-1)/k is odd then we let g_0 = (12(g-1)/k-1)/2, so that
  
    2g_0+3 = 12(g-1)/k + 2

We build the surface in this case from k/6 copies of Σ_g_0,2, triangulated with three vertices per boundary component, and k/12 copies of Σ_0,4, each triangulated as in Figure <ref>. (If g_0 = 0, as it may be, then Σ_g_0,2 is the annulus of Example <ref>.) Given any bijection from the set of boundary components of of the Σ_g_0,2 to those of the Σ_0,4, homeomorphically identifying each boundary component of a Σ_g_0,2 with its image taking vertices to vertices produces a closed, triangulated surface. We must choose the bijection to make the resulting surface connected, an easy exercise equivalent to constructing a connected four-valent graph with k/12 vertices (treating the Σ_0,4 as vertices and the Σ_g_0,2 as edges).

Each case above constructs a closed, connected surface triangulated with k vertices, each of valence 12(g-1)/k + 6.  These quantities determine the number of edges and faces of the triangulation and show that the surface constructed has Euler characteristic 2-2g, hence genus g.


We now prove the same result in the non-orientable case.  Recall below that the genus of a non-orientable surface is the maximal number of ℝP^2-summands in a connected sum decomposition.  We begin by adding some non-orientable building blocks to the mix.

  In Example <ref> the edge identifications between the two copies of the dodecagon comprising Σ_0,6 preserve orientation, so these copies inherit opposite orientations from any orientation on Σ_0,6.  Therefore the involution that exchanges the two dodecagons while rotating Σ_0,6 by 180-degrees reverses orientation.  Since it is also triangulation-preserving and fixed point-free, its quotient is a three-holed ℝP^2, triangulated with two vertices per boundary component where again each vertex has triangle valence 5.


  For any g≥ 2 and a 2g-gon with edges oriented counterclockwise and subsequently labeled e_0,,e_2g-1, identifying e_i with e_i+1 by an orientation-preserving homeomorphism for each even i<2n yields a non-orientable surface of genus g.  Any triangulation of the 2g-gon projects to a one-vertex triangulation of this surface with 2g-2 triangles.  For g≥ 1 a one-vertex triangulation of a one-holed genus-g nonorientable surface Υ_g,1 is produced by analogously by identifying all edges but one of a 2g+1-gon.  This triangulation thus has 2g-1 triangles, so the vertex has triangle valence 6g-3.

We produce two- or three-vertex triangulations with vertices of constant valence analogously to the orientable case of Example <ref>.  These triangulations have 2g and 2g+1 triangles, respectively, so each vertex has triangle valence 3g or 2g+1.



  For any g≥ 3 and any k∈ℕ that divides 6(g-2), the closed, nonorientable genus-g surface has a triangulation with k vertices, all of equal valence.

  The k=1 case is given at the beginning of Example <ref> above.  For the case k>1, as in the proof of Lemma <ref> we consider several sub-cases.
  
  Case 1: 2 and 3 do not divide k  For g_0 = (g-2)/k we glue one copy of Υ_g_0,1, triangulated with one vertex per boundary component, to each boundary component of Σ_1,k, triangulated to match.  The resulting closed surface has each vertex of valence (6g_0 -3)+9 = 6(g-2)/k + 6.

  Case 2: 2 divides k, 3 does not  For g_0 = 2(g-2)/k, join k/2 copies of Υ_g_0,1 to boundary components of Σ_1,k/2, all triangulated with two vertices per boundary component.  In the resulting surface each vertex has valence 3g_0+6=6(g-2)/k + 6.

  Case 3: 3 divides k, 2 does not  For g_0 = 3(g-2)/k, join k/3 copies of Υ_g_0,1 to boundary components of Σ_1,k/3, all triangulated with three vertices per boundary component.  In the resulting surface each vertex has valence (2g_0+1) + 5=6(g-2)/k + 6.

  Case 4: 6 divides k If 6(g-2)/k is even then take g_0 = 6(g-2)/(2k) and join k/3 copies of Υ_g_0,1 to boundary components of Σ_1,k/3, all triangulated with three vertices per boundary component.  In the resulting surface each vertex has valence (2g_0+1)+5 = 6(g-2)/k+6.  If 6(g-2)/k is odd and congruent to 0 modulo three, take g_0=6(g-2)/(3k) and join k/2 copies of Υ_g_0,1 to boundary components of Σ_1,k/2, all triangulated with two vertices per boundary component.  In the resulting surface each vertex has valence 3g_0 + 6 = 6(g-2)/k+6.

If 6(g-2)/k is odd and congruent to 1 modulo three, take g_0 = (6(g-2)/k+2)/3 and take g_1 = g_0-1.  We join k/6 copies of Σ_0,3, triangulated with two vertices per boundary component as in Figure <ref>, to k/6 copies of each of Υ_g_0,1 and the two-holed orientable building block Σ_g_1,2, triangulated to match, as follows: arrange the copies of Σ_g_1,2 in a ring and join boundary components of each pair of subsequent copies to two boundary components of a fixed copy of Σ_0,3.  This leaves one free boundary component on each copy of Σ_0,3, which we cap off with a copy of Υ_g_0,1.  The result is a connected, closed triangulated surface with k vertices, each of valence 3g_0+4 = 3(g_1+1)+4 = 6(g-2)/k+6.

If 6(g-2)/k is odd and congruent to 2 modulo three then we perform the same construction as in the previous case, except that we take g_0 = [6(g-2)/k+1]/3 and replace each copy of Σ_0,3 with a copy of the three-holed ℝP^2 from Example <ref>.  The resulting closed, triangulated surface now has k vertices that each have valence 3g_0+5 = 3(g_1+1) + 5 = 6(g-2)/k+6.
As in the proof of Lemma <ref>, the fact that each non-orientable surface constructed above has k vertices, each of valence 6(g-2)/k+6, implies that it has genus g.

[Triangulated complexes with ideal vertices] Here we will produce a triangulated complex X_l homeomorphic to a disk for each l∈ℕ, with l+1 vertices of which l lie in the interior and each have triangle valence one.  We call these vertices “marked”.   The remaining vertex lies on the boundary of X_l.  The triangulation of X_l is comprised of 2l-1 triangles in two classes: “marked” triangles H_1,,H_l, which each have one marked vertex, and “non-marked” triangles E_1,,E_l-1.










We begin by identifying a subset of the edges of the E_i in pairs so that their union is homeomorphic to a disk, for instance according to the scheme indicated in Figure <ref>, so that (for l>2) E_1 has exactly two free edges and each E_i has at least one.  An Euler characteristic calculation shows that a total of 2l-4 edges of the E_i are identified, so the boundary of ⋃ E_i is a union of l+1 free edges.  For each free edge e of ⋃ E_i except one belonging to E_1, we join one of the H_i to ⋃ E_i by identifying the edge opposite its marked vertex to e via a homeomorphism.  We then finish by identifying the two edges of each H_i that contain its marked vertex to each other by a boundary orientation-reversing homeomorphism.

In the resulting quotient X_l, the interior of each H_i forms an open neighborhood of its marked vertex, and its edge opposite the marked vertex descends to a loop based at the non-marked vertex quotient.  There is therefore a unique non-marked vertex quotient, with triangle valence 5l-3, where 3l-3 vertices of non-marked triangles are identified together with 2l non-marked vertices of marked triangles.

Let Y_l be the complex obtained by joining a non-marked triangle E_0 to X_l along its sole free edge (of E_1).  Then Y_l is still homeomorphic to a disk with l non-marked vertices in its interior, but its boundary is a union of two edges: the free edges of E_0.  The non-marked vertex quotient of X_l has triangle valence 5l-1 in Y_l, with 3l-1 non-marked triangle vertices identified there, since it picks up an extra two from E_0.  The other non-marked vertex quotient in Y_l is the single vertex shared by the two free edges of E_0, which therefore has triangle valence one in Y_l.

  We will begin by re-stating the Proposition separately in the orientable and non-orientable cases.  In the non-orientable case it asserts that for g≥ 1 and n≥ 0 such that 2-g-n<0, and any k∈ℕ that divides both 6(2-g) and n, there is a closed non-orientable surface of genus g with n marked points which is triangulated with k+n vertices with the following two properties: each marked point is a valence-one vertex; and calling the triangle containing it marked, each remaining vertex is a quotient of 2n/k marked and

    6 + 6(g-2) + 3n/k
 
non-marked triangle vertices.  Here we recall from the Proposition that the surface is required to have Euler characteristic χ+n, so from the non-orientable case of (<ref>) with b=0 we have χ+n = 2-g.  Thus χ = 2 - g -n < 0, and k divides both 6(2-g) and n if and only if it divides both 6χ and n.

The Proposition's orientable case asserts that for g, n≥ 0 such that 2-2g-n<0, and any k dividing both 12(g-1) and n, that there is a closed, orientable surface of genus g with n marked points which is triangulated in analogous fashion to the non-orientable case except that each non-marked vertex is contained in

    6 + 12(g-1)+3n/k

non-marked triangle vertices.  The valence computations here and in the non-orientable case are obtained by substituting 2-g-n and 2-2g-n, respectively, for χ in the formula 6-(6χ+3n)/k in the Proposition's original statement.

From these restatements it is clear that Lemmas <ref> and <ref> address the n=0 cases, so we assume below that n>0.  We first consider the orientable case, beginning with the subcase k=1.  For g≥ 1 join a copy of the one-holed building block Σ_g,1 of Example <ref>, triangulated with one vertex, to a copy of X_n along their boundaries.  The non-marked vertex is then a quotient of 
  
    (12g-3) + (3n-3) = 12(g-1) + 3n  + 6
 
non-marked triangle vertices, and 2n marked triangle vertices.  In the case g=0 (so with n≥ 3), for natural numbers i and j such that i+j=n we join a copy of X_i to a copy of X_j along their boundaries.  The result is homeomorphic to a triangulated sphere with n marked vertices, where the non-marked vertex is a quotient of (3i-3) + (3j-3) = 3n -6 non-marked triangle vertices.

Now take k≥2, and suppose g≥ 2.  Lemma <ref> supplies a closed, oriented, surface S_0 of genus g with no marked points and a k-vertex triangulation, where each vertex has valence 12(g-1)/k+6.  By its construction, S_0 is endowed with a collection of disjoint simple closed curves, each a union of one, two, or three edges, that separate it into a union of building blocks.  Orient each such curve on S_0, and for an edge e contained in such a curve let e inherit its orientation.  Then cut out the interior of e; that is, take the path-completion of S_0-e.  The resulting space has a single boundary component which is a union of two edges, and S_0 is recovered by identifying them.

Construct S by removing the interior of each such edge e, orienting the two new edges to match that of e, and joining each new edge to one of a copy of Y_l in orientation-preserving fashion, where l = n/k and the edges of Y_l are oriented pointing away from the free vertex of E_0.  Each vertex of S_0 is the initial vertex of one oriented edge, and the terminal vertex of one oriented edge.  It therefore picks up one additional non-marked triangle vertex from one copy of Y_l and 3l-1 from another, as well as 2l marked triangle vertices.  This vertex thus has the required valence in S.

For the orientable case g = 1 and k ≥ 2 we join one copy of X_l to each boundary component of Σ_1,k, triangulated as in Example <ref> with one vertex per boundary component, where l=n/k.  Then each non-marked vertex is contained in 9+3l-3 = 3n/k + 6 non-marked triangle vertices and 2n/k vertices from marked triangles.

We finally come to the orientable case g=0 and k≥ 2.  Since k must divide 12(g-1) = -12 it can be only 2, 3, 4, 6 or 12.  For the case k=2, noting that n is thus even, we join one copy of X_n/2 to each boundary component of the annulus Σ_0,2, triangulated with one vertex per boundary component.  For k=3 we produce a sphere S_0 by doubling a triangle across its boundary, orient the cycle of triangle edges, and perform the construction described above to yield S, using three copies of Y_n/3.  For k=6 and k=12 we begin with Σ_0,2 or Σ_0,4, respectively, each triangulated with three vertices per boundary component as in Example <ref>; construct S_0 by capping off each boundary component with a single triangle; and proceed similarly.

For the case k=4 we first construct a space Z_l, l∈ℕ, as follows: join two copies of Y_l along a single edge of E_0 in each so that the free vertex of E_0 in one is identified to the non-trivial, non-marked vertex quotient in the other.  Then Z_l is homeomorphic to a disk with two vertices on its boundary, each a quotient of 3l non-marked triangle vertices and 2l non-marked vertices of marked triangles, and 2l marked vertices in its interior.  Returning to the k=4 subcase, we attach one copy of Z_n/4 to each boundary component of the annulus Σ_0,2, triangulated with two vertices per boundary component.  This yields a sphere with four non-marked vertices, each a quotient of 3n/4+3 non-marked triangle vertices as required.  The valence requirements are also easily checked in the other orientable subcases with g=0 and k≥ 2.

The non-orientable subcase k=1 is analogous to the corresponding orientable subcase, with the orientable building block Σ_g,1 replaced by Υ_g,1 from Example <ref>.  (There is no analog of the g=0 sub-subcase here.)  And the non-orientable subcase k≥ 2, g≥ 3 is analogous to the orientable subcase k≥ 2, g≥ 2, with the surface S_0 provided here by Lemma <ref> instead of <ref>.

The non-orientable subcase k≥ 2, g=2 is analogous to the orientable subcase k≥ 2, g=1, but with the k-holed torus Σ_1,k replaced by a k-holed Klein bottle (the non-orientable genus-two surface) triangulated with one vertex per boundary component.  Its construction is analogous to that of Σ_1,k in Example <ref>: fill the hole of the triangulated one-holed Klein bottle Υ_2,1, take a k-fold cyclic cover, and remove the preimage of the interior of the added disk.  In all cases so far the valence criteria are straightforward to check.

We finally come to the subcase k≥ 2 and g=1.  As in the corresponding orientable subcase (g=0), we note that possible values of k are tightly restricted by the requirement that k divides 6(g-2) = -6: it must be either 2, 3, or 6.  For k=2 or 3 we note that the construction of Example <ref> supplies Υ_1,1, a one-holed ℝP^2 triangulated with one, two or three vertices on its boundary.  In each case each vertex is contained in three non-marked triangle vertices.  For k=2 we attach a copy of Z_n/2 to Υ_1,1, triangulated with two vertices, along their boundaries.  For k=3 we triangulate Υ_1,1 with three vertices, cap off its boundary with a triangle to produce a surface S_0, and produce S by suturing in three copies of Y_n/3 as above.  For k=6 we cap off the boundary components of the three-holed ℝP^2 from Example <ref>, triangulated with two vertices per boundary component, with three copies of Z_n/3 as defined above.





§ GENERIC NON-SHARPNESS



In this section we prove Theorem <ref>, that the bound r_χ,n^k of Proposition <ref> is “generically” not sharp.  We begin by observing that r_χ,n^k is generically not attained.

  For any χ<0 and k∈ℕ that does not divide 6χ, there is no closed hyperbolic surface with Euler characteristic χ and a packing by k disks of radius r_χ,0^k.  For any fixed χ< 0 and n>0, there are only finitely many k∈ℕ for which a complete, finite-area hyperbolic surface with Euler characteristic χ and n cusps exists which admits a packing by k disks of radius r_χ,n^k.

  We first consider the closed (n=0) case.  The main observation here is that by the equation from Proposition <ref> defining r_χ,n^k, α(r_χ,0^k) is an integer submultiple of 2π if and only if k divides 6χ.  By the Proposition, any closed surface that admits a radius-r_χ,0^k disk packing is triangulated by a collection of equilateral triangles that all have vertex angle α(r_χ,n^k).  The total angle around any vertex v of the triangulation is thus i·α(r_χ,n^k), where i is the number of triangle vertices identified at v.  But since v is a point of a hyperbolic surface this angle is 2π, whence k must divide 6χ.

Let us now fix χ<0 and n>0, and recall from Proposition <ref> that r_χ,n^k>0 is determined by the equation f_k(r_χ,n^k) = 2π, where for α(r) = 2sin^-1(1/2cosh r) and β(r) = sin^-1(1/cosh r),

    f_k(r) = (6-6χ+3n/k)α(r) + 2n/kβ(r) = (6 - 6χ+n/k)α(r) + 2n/k(β(r) - α(r)).

Rewriting f_k as on the right above makes it clear that for any fixed r>0 and k∈ℕ, f_k+1(r) < f_k(r).  For since the inverse sine is concave up on (0,1) we have β(r) > α(r) for any r, and inspecting the equations of (<ref>) shows in all cases that -6χ-n > 0.  Moreover, these equations show in all cases that -6χ-3n≥ -3 in all cases, so f_k decreases with r since both α and β do.

We now claim that α(r_χ,n^k) strictly increases to π/3 and β(r_χ,n^k) to π/2 as k→∞.  For each k, by the above we have f_k+1(r_χ,n^k) < f_k(r_χ,n^k) = 2π, so since each f_k decreases with r it follows that r_χ,n^k+1 < r_χ,n^k.  Thus in turn α(r_χ,n^k+1)>α(r_χ,n^k) and similarly for β.  Note that for each r, f_k(r) → 6α(r) as k→∞.  The limit is a decreasing function of r that takes the value 2π at r=0.  Since the sequence {r_χ,n^k}_k∈ℕ is decreasing and bounded below by 0, it converges to its infimum ℓ.  If ℓ were greater than 0 then for large enough k we would have f_k(r_χ,n^k) < f_k(ℓ) < 2π, a contradiction.  Thus r_χ,n^k→ 0 as k→∞, and the claim follows by a simple computation.

Now let us recall the geometric meaning of α and β: α(r) is the angle at any vertex of an equilateral triangle with side length 2r, and β(r) is the angle of a horocyclic triangle with compact side of length 2r, at either endpoint of this side.  By Proposition <ref>, if there is a complete hyperbolic surface F of finite area with Euler characteristic χ and n cusps and a packing by k disks of radius r_χ,n^k then F decomposes into equilateral triangles and exactly n horocyclic ideal triangles, all with compact sidelength 2r_χ,n^k.

For such a surface F, since F has n cusps and there are n horocyclic ideal triangles, each horocyclic ideal triangle has its edges identified in F to form a monogon encircling a cusp.  At most n disk centers can be at the vertex of such a monogon, so for k > n there is a disk center which is only at the vertex of equilateral triangles.  The angles around this vertex must sum to 2π, so α(r_χ,n^k) must equal 2π/i for some i∈ℕ.  But for k large enough we have 2π/7 < α(r_χ,n^k) < π/3, and this is impossible.


We will spend the rest of the section showing that among finite-area complete hyperbolic surfaces with any fixed topology, the maximal k-disk packing radius does attain a maximum.  To make this more precise requires some notation.  Below for a smooth surface Σ of hyperbolic type — that is, which is diffeomorphic to a complete, finite-area hyperbolic surface — let 𝔗(Σ) be the Teichmüller space of Σ.  This is the set of pairs (F,ϕ) up to equivalence, where F is a complete, finite-area hyperbolic surface and ϕΣ→ F is a diffeomorphism (called a marking), and (F',ϕ') is equivalent to (F,ϕ) if there is an isometry f F→ F' such that f∘ϕ is homotopic to ϕ'.  We take the usual topology on 𝔗(Σ), which we will discuss further in Lemma <ref> below.

 For a surface Σ of hyperbolic type and k∈ℕ, define _k𝔗(Σ)→ (0,∞) by taking _k(F,ϕ) to be the maximal radius of an equal-radius packing of F by k disks.  Refer by the same name to the induced function on the moduli space 𝔐(Σ) of Σ.

The moduli space 𝔐(Σ) is the quotient of 𝔗(Σ) by the action of the mapping class group, or, equivalently, the collection of complete, finite-area hyperbolic surfaces homeomorphic to Σ, taken up to isometry, endowed with the quotient topology from 𝔗(Σ).  Since the value of _k on (F,ϕ) depends only on F, it induces a well-defined function on 𝔐(Σ).  We are aiming for:

  For any surface Σ of hyperbolic type, and any k∈ℕ, _k attains a maximum on 𝔐(Σ).

Assuming the Proposition, we immediately obtain this section's main result:



This is because for fixed χ and n there are at most two n-punctured surfaces of hyperbolic type with Euler characteristic χ: one orientable and one non-orientable.  By Lemma <ref>, for all but finitely many k the maximum of _k on each of their moduli spaces (which exists by the Proposition) is less than r_χ,n^k.

To prove the Proposition we need some preliminary observations on _k, some basic facts about the topology of moduli space, and some non-trivial machinery due originally to Thurston.

 For any surface Σ of hyperbolic type, and any k∈ℕ there exist c_k>0 and ϵ_k>0 such that _k(F)≥ c_k for every F∈𝔐(Σ), and any packing of F by k disks of radius _k(F) is contained in the ϵ_k-thick part of F.  For each such F, there is a packing of F by k disks of radius _k(F).

  There is a universal lower bound of  sinh^-1(2/√(3)) on the maximal injectivity radius of a hyperbolic surface.   (This was shown by Yamada <cit.>.)  The value of _k on any hyperbolic surface F is therefore at least the maximum radius c_k of k disks embedded without overlapping in a single disk of radius sinh^-1(2/√(3)).  This proves the lemma's first assertion.

For a maximal-radius packing of F by k disks, the center of each disk is thus contained in the c_k-thick part F_[c_k,∞) of F, the set of x∈ F such that the injectivity radius of F at x is at least c_k.  The second assertion follows immediately from the (surely standard) fact below:

  For any r less than the two-dimensional Margulis constant, and any hyperbolic surface F, the r-neighborhood in F of F_[r,∞) is contained in F_[r',∞), where r' = sinh^-1(1/2(1-e^-2r)).

 We will use the following hyperbolic trigonometric fact: for a quadrilateral with base of length δ and two  sides of length h, each meeting the base at right-angles, the lengths δ of the base, h of the sides it meets, and ℓ of the remaining side are related by

    sinh(ℓ/2) = cosh hsinh(δ/2).

Now fix x∈∂ F_[r,∞) and let U be the component of the ϵ-thin part of F that contains x, where ϵ is the two-dimensional Margulis constant.  Suppose first that U is an annulus, and let h be the distance from x to the core geodesic γ of U.  If γ has length δ then applying (<ref>) in the universal cover we find that there is a closed geodesic arc of length ℓ (as defined there) based at x and freely homotopic (as a closed loop) to δ.  It thus follows that cosh h = sinh r/sinh(δ/2).  Let us now assume that δ≤ 2sinh^-1(sinh r/cosh r), so that h ≥ r.  For a point y at distance h-r from δ, the geodesic arc based at y in the free homotopy class of δ has length ℓ' given by

    sinh(ℓ'/2) = cosh(h-r)sinh(δ/2) = sinh r(cosh r - √(sinh^2 r - sinh^2(δ/2)))

(using the “angle addition” formula for hyperbolic cosine.)  As a function of δ, ℓ' is increasing, and its infimum at δ = 0 satisfies sinh(ℓ'/2) = sinh r(cosh r - sinh r) = 1/2(1-e^-2r).  Therefore the injectivity radius at y is at least r' defined in the claim.  Note also that at δ = 2sinh^-1(sinh r/cosh r) we have ℓ' = δ as expected.  So when h≤ r, i.e. when U is contained in the r-neighborhood of F_[r,∞), the injectivity radius at every point of U is at least δ/2 > r'.

Another hyperbolic trigonometric calculation shows that if U is a cusp component of the ϵ-thin part of F then for y at distance r from x along the geodesic ray from x out the cusp, the shortest geodesic arc based at y has length ℓ' satisfying the same formula as above.  Hence in this case as well, the injectivity radius is at least r' = ℓ'/2 at every point of U in the r-neighborhood of F_[r,∞).

For the Lemma's final assertion we note that _k(F) is the supremum of the function on F^k which records the maximal radius of a packing by equal-radius disks centered at x_1,,x_k for any (x_1,,x_k)∈ F^k.  (If x_i = x_j for some j≠ i then we take its value to be 0.)  This function is clearly continuous on F^k.  By the Lemma's first assertion it attains a value of c_k, so it approaches its supremum on the compact subset (F_[c_k,∞))^k of F^k.

 For any surface Σ of hyperbolic type, and any k∈ℕ, _k is continuous on 𝔗(Σ), therefore also on 𝔐(Σ).

  We will take the topology on 𝔗(Σ) to be that of approximate isometries as in <cit.>, with a basis consisting of K-neighborhoods of (F,ϕ)∈𝔗(Σ) for K∈(1,∞).  Such a neighborhood consists of those (F',ϕ')∈𝔗(Σ) for which there exists a K-bilipschitz diffeomorphism Φ F→ F' with Φ∘ϕ homotopic to ϕ'.  (This is equivalent to the “algebraic topology” of <cit.>, which is in turn equivalent to that induced by the Teichmüller metric, cf. <cit.>. In particular Mumford's compactness criterion holds for the induced topology on 𝔐(Σ), see <cit.>.)

It is obvious that _k is continuous with this topology.  For given a geodesic arc γ of length ℓ on F and a K-bilipschitz diffeomorphism Φ F→ F', the geodesic arc in the based homotopy class of Φ∘γ has length between ℓ/K and Kℓ.  Now for a packing of F by k disks of radius _k(F) there are finitely many geodesic arcs of length ℓ≐ 2_k(F) joining the disk centers, and every other arc based in this set has length at least some ℓ_0>ℓ.  Choosing K near enough to 1 that ℓ_0/K >Kℓ we find for every (F',ϕ') in the K-neighborhood of (F,ϕ) that _k(F)/K ≤_k(F') ≤ K_k(F). 

The main ingredient in the proof of Proposition <ref> is Lemma <ref> below.  It was suggested by a referee for <cit.>, who sketched the proof I give here.

  Let Σ be a surface of hyperbolic type, and fix r_1 > r_0 >0, both less than the two-dimensional Margulis constant.  For any essential simple closed curve 𝔠 on Σ, and any S∈𝔗(Σ) such that the geodesic representative γ of  has length less than 2r_0 in S, there exists S_0∈𝔗(Σ) where the geodesic representative γ_0 of  has length between 2r_0 and 2r_1, and a path-Lipschitz map (one which does not increase the length of paths) from S_0-γ_0 onto a region in S containing the complement of the component of the r_1-thin part containing γ.

  The construction uses the strip deformations described by Thurston <cit.>.  We will appeal to a follow-up by Papadopolous–Théret <cit.> for details and a key geometric assertion.  Below we take  to have geodesic length less than 2r_0 in S. We will assume first that  is non-separating.  The separating case raises a few complications that we will deal with after finishing this case.

To begin the strip deformation construction, cut S open along the geodesic representative γ of  to produce a surface with two geodesic boundary components γ_1 and γ_2.  Then adjoin a funnel to this surface along each γ_i to produce its Nielsen extension S.  Now fix a properly embedded geodesic arc α in the cut-open surface that meets each of γ_1 and γ_2 perpendicularly at an endpoint.  One can obtain such an arc α starting with a simple closed curve a in S that intersects γ once: if a∩γ = {x} then regarding a as a closed path in S based at x, any lift ã to the universal cover has its endpoints on distinct components γ̃_1 and γ̃_2 of the preimage of γ; this lift is then homotopic through arcs with endpoints on γ̃_1 and γ̃_2 to their common perpendicular α̃, which projects to α.

In S, α determines a bi-infinite geodesic α̂ with one end running out each funnel. We now cut S open along α̂ and glue in an “ϵ-strip” B (terminology as in <cit.>), which is isometric to the region in ℍ^2 between two ultraparallel geodesics whose common perpendicular (the core of B) has length ϵ, by an isometry from ∂ B to the two copies of α̂ in the cut-open S.  This isometry should take the endpoints of the core of B to the midpoints of the copies of α in the two copies of α̂.  Let us call the resulting surface S_0.  There is a quotient map fS_0→S taking B to α̂, which is the identity outside B and on B collapses arcs equidistant from the core.  By <cit.>, f is 1-Lipschitz.  (In <cit.>, applying f is called “peeling an ϵ-strip”, and the respective roles of S_0 and S here are played by X̂ and Ŷ_B there.)

For i=1,2, let γ̂_i be the geodesic in S_0 that is freely homotopic to f^-1(γ_i), which is the union of the open geodesic arc γ_i-α with an equidistant arc from the core of B.  By gluing the endpoints of the core of B to the midpoints of the copies of α we ensured that the γ̂_i have equal length, which depends on ϵ (we will expand on this assertion below).  We now remove the funnels that the γ̂_i bound in S_0, then isometrically identify the resulting boundary components yielding a finite-area surface S_0 (the choice of isometry is not important here).

Let γ_0 be the quotient of the γ̂_i in S_0.  The marking Σ→ S induces one from Σ to S_0 that takes  to a simple closed curve with geodesic representative γ_0.  The restriction of f also induces a map from S_0-γ_0 to a region in S.  This is because the γ̂_i lie inside the preimage f^-1(S-γ), where S-γ refers to the closure (S-γ)∪γ_1∪γ_2 of S-γ inside its Nielsen extension.  This in turn follows from the fact that the nearest-point retraction from S_0 to f^-1(S-γ), which is modeled on B∩(S_0-f^-1(S-γ)) by the orthogonal projection to a component of an equidistant locus to the core of B and on the rest of S_0-f^-1(S-γ) by the retraction of a funnel to its boundary, is distance-reducing.

Since f does not increase the length of paths, the same holds true for the induced map S_0-γ_0 → S.  Let us call U the component of the r_1-thin part of S containing γ.  We will show that ϵ can be chosen so that the γ̂_i, and hence also γ_0, have length at least 2r_0 and less than 2r_1.  Since f is Lipschitz, and the f(γ̂_i) are freely homotopic in S to γ, it will follow that their images lie in U and thus that the image of S_0-γ_0 contains S-U.

It seems intuitively clear that the length of the γ̂_i increases continuously and without bound with ϵ, and that it limits to the length of γ as ϵ→ 0.  If this is so then it is certainly possible to choose ϵ so that the γ̂_i, hence also their quotient in S_0, have length strictly between 2r_0 and 2r_1.  We will thus spend a few lines describing the hyperbolic trigonometric calculations to justify the assertions above on the length of the γ̂_i, completing the proof of the non-separating case.

For i = 1,2, γ̂_i is freely homotopic in S_0 to the broken geodesic that is the union of the open geodesic arc γ_i - α with the geodesic arc contained in the ϵ-strip B that joins its endpoints.  Dropping perpendiculars to γ̂_i from the midpoints of these two arcs divides the region in S_0 between γ̂_i and the broken geodesic into the union of two copies of a pentagon  with four right angles.  Let x be the length of the base of , half the length of γ̂_i.  The sides opposite the base have lengths δ/2 and z, where δ and 2z are the respective lengths of γ, and the arc in B joining the endpoints of γ-α.  See Figure <ref>.



The side of length z is also a side of a quadrilateral ⊂ B with its other sides in the core of B (with length ϵ/2), the core's perpendicular bisector, and a copy of α (with length h).  This quadrilateral has three right angles, and trigonometric formulas for such quadrilaterals (see <cit.>) describe z and the non-right angle θ in terms of ϵ/2 and h:
    sinh z = cosh h sinh (ϵ/2)       sinθ  = cosh(ϵ/2)/cosh z

The non-right angle of  has measure π/2+θ, so from trigonometric laws for pentagons with four right angles <cit.>, we now obtain:

    cosh x  = cosh hsinh(ϵ/2)sinh(δ/2) + cosh(ϵ/2)cosh(δ/2)

Recall that x is half the length of the γ̂_i.  And indeed we find that x increases with ϵ, continuously and without bound, and it limits to δ/2 (half the length of γ) as ϵ→ 0.

Now suppose  is separating.  In this case we choose geodesic arcs α_1 and α_2, each properly embedded in the surface obtained by cutting S along the geodesic representative γ of  and meeting the boundary  perpendicularly, one in each component. These may again be obtained from a simple closed curve a⊂ S, this time one which intersects γ twice, such that no isotopy of a reduces the number of intersections. Lifting the arcs a_1 and a_2 of a on either side of γ to the universal cover, separately homotoping each to a common perpendicular between lifts of γ, then pushing back down to S and cutting along γ yields the α_i.

After cutting S along γ, we take γ_i to be the geodesic boundary of the component containing α_i, for i=1,2.  After constructing S as before, we cut it open along both α̂_1 and α̂_2 then, for each i=1,2, attach an ϵ_i-strip B_i along the boundary of the component containing γ_i.  In the resulting disconnected surface S_0, for each i let γ̂_i be the geodesic in the free homotopy class of the union of the two arcs of γ_i-α_i with the two arcs in B_i joining the endpoints of these arcs that are on the same side of its core.

We now customize ϵ_1 so that γ_1 has length greater than 2r_0 but less than 2r_1, then customize ϵ_2 so that γ_2 has the same length as γ_1.  Then as in the previous case we can cut off the funnels that the γ̂_i bound in S_0 and glue the resulting boundary components isometrically to produce a surface S_0 with a 1-Lipschitz map to f^-1(K), for K as before.  Again what remains is to verify that the length of each γ̂_i increases continuously and without bound with ϵ_i, and that it approaches the length δ of γ as ϵ_i→ 0.

The extra complication in this case arises from the fact alluded to above, that each α_i intersects γ twice.  And we cannot guarantee that the points of intersection are evenly spaced along γ.  So for each i the funnel of S_0 bounded by γ̂_i, which contains the broken geodesic f^-1(γ_i), has only one reflective symmetry.  Its fixed locus is the disjoint union of the perpendicular bisectors of the two components of γ_i-α_i, which divide the region between γ̂_i and f^-1(γ_i) into two isometric hexagons with four right angles.  One such hexagon ℋ is pictured in Figure <ref>.



One side of ℋ has length x, half the length of γ̂_i as in the previous case.  The side opposite this one has length 2z, for z as in (<ref>).  (Here we are suppressing the dependence on i for convenience, but note that α_1 and α_2 may have different lengths, so “z” refers to different lengths in the cases i=1 and 2.)  The angle at each endpoint of the side with length z is π/2+θ, where again θ is given by (<ref>) (with the same caveat as for z).  The sides meeting this one are contained in γ_i-α_i, and calling their lengths a and b, we have that a+b = δ/2 is half the length of γ.

When ϵ is small, the geodesics containing the sides of lengths a and b meet at a point p in B.  Their sub-arcs that join p to the endpoints of the side of length 2z form an isosceles triangle with two angles of π/2-θ.  Applying some hyperbolic trigonometric laws and simplifying gives that the angle ψ at p and the length y of the two equal-length sides respectively satisfy:
    cosψ = 2sinh^2 hsinh^2(ϵ/2) - 1       cosh y = cosh(ϵ/2)/√(1 - sinh^2 h sinh^2(ϵ/2))

From these formulas we find in particular that this case holds when sinh(ϵ/2) < 1/sinh h.  From the same law for pentagons as in the non-separating case we now obtain:
    cosh x     = sinh(y+a)sinh(y+b) - cosh(y+a)cosh(y+b)cosψ
        = 1/2[(1-cosψ)cosh(2y+a+b) - (1+cosψ)cosh(a-b) ]

The second line above is obtained by applying the equation sinh xsinh y = 1/2(cosh(x+y) - cosh(x-y)) and its analog for hyperbolic cosine.  Applying hyperbolic trigonometric identities and substituting from (<ref>), after some work we may rewrite the right side above as:

    coshϵcosh (a+b) + sinhϵcosh hsinh(a+b) + sinh^2 hsinh^2(ϵ/2)(cosh(a+b) - cosh(a-b))

This makes it clear that x increases continuously with ϵ, and that x→ a+b as ϵ→ 0.  Recalling that x is half the length of γ̂_i and a+b = δ/2 half that of γ_i, we have all but one of the desired properties of γ̂_i.  But there is a “phase transition” at ϵ=2sinh^-1(1/sinh h).  Note that as ϵ approaches this from below, from (<ref>) we have
    sinh z → h       sinθ→cosh h/√(cosh^2 h + sinh^2 h)

From Proposition <ref> we now recall that the angle β at a finite vertex of a horocyclic ideal triangle and half the length r of its compact side satisfy sinβ = 1/cosh r.  One easily verifies that the limit values of cosh z and of sin(π/2-θ) = cosθ are reciprocal, so geometrically, what is happening as ϵ→2sinh^-1(1/sinh h) is that p is sliding away from the core of B along its perpendicular bisector, reaching an ideal point at ϵ = 2sinh^-1(1/sinh h).

For ϵ>2sinh^-1(1/sinh h) we therefore expect the geodesics containing a and b to have ultraparallel intersection with B.  Their common perpendicular is then one side of a quadrilateral in B with opposite side of length 2z. If d is the length of this common perpendicular and y the length of the two remaining sides, from standard hyperbolic trigonometric formulas <cit.> we have:
    cosh d = 2sinh^2 hsinh^2(ϵ/2)-1       cosh y = sinh z/sinh(d/2) = cosh hsinh(ϵ/2)/√(sinh^2 hsinh^2(ϵ/2)-1)

We now apply the hyperbolic law of cosines for right-angled hexagons <cit.>, yielding:
    cosh x     = sinh(y+a)sinh(y+b) cosh d-cosh(y+a)cosh(y+b) 
        = 1/2[cosh (2y+a+b)(cosh d - 1) - cosh(a-b)(cosh d+1)]

Manipulating this formula along the lines of the previous case now establishes that x increases continuously and without bound with ϵ, and comparing the resulting formula with the previous one shows that its limits coincide as ϵ approaches 2sinh^-1(1/sinh h) from above and below.  The lemma follows.


  Fix k∈ℕ and a surface Σ of hyperbolic type, and let r_1 = min{ϵ_0/2,ϵ_k} and r_0 = r_1/2, where ϵ_0 is the two-dimensional Margulis constant and ϵ_k is as in Lemma <ref>.  For any S∈𝔗(Σ) with a geodesic of length less than 2r_0, we claim that there exists S'∈𝔗(Σ) with all geodesics of length at least 2r_0 and _k(S')≥_k(S).

Let _1,,_n be the curves in Σ whose geodesic representatives have length less than 2r_0 in S, and let U be the component of the r_1-thin part of S containing the geodesic representative γ_1 of _1.  Lemma <ref> supplies some S_1'∈𝔗(Σ), with a path-Lipschitz map f from S'_1-γ_1' to a region in S containing S-U, where the geodesic representative γ_1' of _1 in S_1' has length between 2r_0 and 2r_1.  A packing of S by k disks of radius _k(S) is entirely contained in S-U by Lemma <ref> and our choice of r_1.  Therefore if x_1,,x_k are the disk centers in S, points x_1',,x_k' of S_1' mapping to the x_i under f are the centers of a packing of S_1' by disks of the same radius, since f does not increase the length of any based geodesic arc.

We note that for a point x∈ S-U where the injectivity radius is at least r_0, the injectivity radius is also at least r_0 at any x'∈ S_1' mapping to U: every geodesic arc based at x' that intersects γ_1' has length greater than the Margulis constant, and the length of every other arc is decreased by f.  It follows that only _2,,_n may have geodesic length less than 2r_0 in S_1'.  Iterating now yields the claim.

Now for a sequence (S_i) of surfaces in 𝔐(Σ) on which _k approaches its supremum, we use the claim to produce a sequence (S_i'), with _k(S_i') ≥_k(S_i) for each i, such that S_i' has systole length at least 2r_0 for each i.  This sequence has a convergent subsequence in 𝔐(Σ), by Mumford's compactness criterion <cit.>, and since _k is continuous on 𝔐(Σ) it attains its maximum at the limit.

plain


