Articles

Translation surfaces and friends

Recall that we earlier defined translation surfaces as maximal atlases of coordinate charts into the Euclidean plane \mathbb{R}^2, with finitely many cone singularities and where the transition maps between coordinate charts are translations in \mathbb{R}^2.

Recall that we were led to this notion starting from polygonal billiards, but not every translation surface, generally defined, comes from a rational polygonal billiard.

Enter Riemann surfaces and moduli spaces

A translation surface may also be thought of as a Riemann surface, together with an associated holomorphic 1-form—a continuous choice of specified direction (“up”) at every point; such a pair of structures canonically defines a (singular) flat structure on the surface, with a distinguished vertical direction.

To wit: we take the holomorphic 1-form \omega to be (locally) our dz. Since \omega is holomorphic, its zeroes are isolated: a zero of degree d corresponds exactly to a conical singularity with cone angle 2\pi(d+1). Where \omega is not zero, it is represented (locally) by dz, whence we obtain a complex coordinate z, which in turn specifies (locally) a Euclidean structure. Since dz is globally well-defined on our translation surface, the resulting flat structure is also well-defined, away from the conical singularities.

Conversely, given a flat structure with conical singularities P_1, \dots, P_n, and a specified direction, consider a fundamental polygon P_1P_2 \cdots P_n embedded (anywhere, but with orientation dictated by the specified direction) in the complex plane. The fundamental polygon inherits a natural complex coordinate z. This does not descend to the translation surface, but since the identification maps are all of the form z \mapsto z + \zeta where \zeta \in \mathbb{C} is a constant (for each identification map), the holomorphic 1-form dz does, and we obtain a holomorphic 1-form \omega on our translation surface. \omega is zero exactly at the conical singularities, with cone angle being related to degree as above.

The Riemann surface perspective emphasizes more clearly the presence of a moduli space of translation surfaces (on for a fixed genus g), which we presently define as a space of pairs (X, \omega), where X denotes a Riemann surface structure, and \omega a choice of holomorphic 1-form, modulo some natural equivalence relation. The 1-form specifies a distinguished direction—so there is a well-defined notion of “north” on the surface. Two such pairs (X_1, \omega_1) and (X_2, \omega_2) are considered equivalent if there is a conformal map from X_1 to X_2 which takes (specified) zeroes of \omega_1 to (specified) zeroes of \omega_2.

The moduli space is divided into distinct strata \mathcal{H}(d_1, \dots, d_m), consisting of forms with zeroes of degree d_1, \dots, d_m with d_1 + \dots + d_m = 2g-2. This last identity follows from the formula for the sum of degrees of zeroes of a holomorphic 1-form on a Riemann surface of genus g, and can be interpreted as a Gauss-Bonnet formula for the singular flat metric.

There is a \mathrm{SL}_2\mathbb{R} action on this moduli space (or, really, on each stratum) which is most easily described back in the framework of flat geometry: given any pair (X,\omega), build the corresponding flat polygon (with distinguished vertical direction.) Elements of \mathrm{SL}_2\mathbb{R} act (linearly) on these flat polygons, thought of as being embedded in the Euclidean plane, with (say) some vertex at the origin. This action preserves parallelisms between edges; and hence is (induces) an action on the corresponding flat surfaces.

fig15

(figure from the Zorich survey—the \mathrm{SL}(2,\mathbb{R}) action, depicted on the left, changes the affine structure but not the translation structure; the “cut-and-paste” on the right changes the translation structure, but not the affine structure.)

We can study the dynamics of this action, and this turns out to be surprisingly (or perhaps not surprisingly—or maybe that is only with the benefit of giant-assisted hindsight) rich …

(There were already hints of this in the last post, when we talked about “changing the translation structure while preserving the affine structure” and how Masur used this idea to prove his theorem on counting closed geodesics.)

Counting closed geodesics and saddle connections

As previously noted in the slightly more restricted context of rational polygonal billiards, directional flow on a flat surface is uniquely ergodic in almost every direction.

This is most transparently seen in the case of a torus: geodesics with rational slopes are closed, while those with irrational slopes are equidistributed. Geodesics on flat surfaces of higher genera exhibit certain similiarities: the closed geodesics also appear in parallel families, although in higher genera these do not fill the whole surface, but only flat cylinders with conical singularities on the boundary.

Related to closed geodesic are saddle connections, which are geodesic segments joining two conical singularities (which may coincide), with no conical points in their interior. On a flat torus there are no conical singularities, and so any closed loop can be tightened to a closed geodesic; on a more general flat surface, this tightening process can produce either a closed geodesic, or—if at some point in the process we hit one of the singularities on the surface, which, as one might imagine, is the more generic case—a union of saddle connections.

Masur and Eskin have found quadratic asymptotics, as a function of length, for the number of [cylindrical families of] closed geodesics—this was discussed more in the previous post—and the number of saddle connections. The constants which appear in these asymptotics are called the Siegel-Veech constants. There are also (somewhat surprising) quadratic asymptotics for multiple cylindrical families in the same parallel direction.

These results are interesting in their own right—on a [rational] billiard table, for instance, generalized diagonals (trajectories joining two of the corners, possibly after reflections) unfold to saddle connections and periodic trajectories unfold to closed regular geodesics—but are also useful for at least two other reasons:

One, degeneration of “configurations” of parallel saddle connections or closed geodesics leads us into cusped regions in the boundary of (strata in the) moduli space, and so a description of such configurations gives us a description of the cusps of our strata. Local considerations involving short / degenerating saddle connections also lead us to relations between and structural results about the strata, which can be described more carefully / analytically in the language of Abelian differentials.

Two, configurations of saddle connections and closed geodesics are also useful as invariants of \mathrm{SL}(2,\mathbb{R}) orbits—something that we will refer back to below.

Volume of moduli space

We remark that this last counting problem can be related to computations of volumes of the moduli space, via the observation that the Siegel-Veech constants can be obtained as a limit of the form \lim_{\epsilon \to 0} \frac{1}{\pi \epsilon^2} \frac{\mathrm{Vol}(\epsilon\mbox{-neighborhood of cusp }\mathcal{C})}{\mathrm{Vol} \mathcal{H}_1^\circ(d_1, \dots, d_n)} where \mathcal{C} is a specified configuration of saddle connections or closed geodesics.

Athreya-Eskin-Zorich used this idea to obtain explicit formulas (conjectured by Kontsevich based on experimental evidence) for the volumes of strata in genus 0, by counting generalized diagonals and periodic trajectories on right-angled billiards. In general, of course, the relation between the two problems can be exploited in both directions: results on volumes of strata can also be used to obtain results on the counts of saddle connections / closed geodesics.

There are a number of alternative strategies for finding these volumes; the following is so far the most general:

The general idea is to simply use asymptotics for counts of integer lattice points, where the lattice is defined in terms of cohomological period coordinates. We can count the number of such points in a sphere or hyperboloid (which is the unit sphere for an indefinite quadratic form of suitable signature) to estimate its volume, and take a derivative to estimate the volume of the boundary hypersurface.

Integer lattice points may be thought of, geometrically, as flat surfaces tiled by square flat tori, and combinatorial geometric methods may be used to count these: in the simplest cases we can count directly; slightly more generally we can consider the graph with conical points as vertices and horizontal saddle connections as edges, leading to the notions of ribbon graphs and separatrix diagrams.

In the most general case we turn, following an idea of Eskin-Okounkov, to representation theory: suppose there are N squares; label them, and consider the permutation \pi on [N] which sends j to the square \pi(j) which we get to by starting at j and moving left, up, right, and down in turn. For the generic square j, \pi fixes j, but near the conical points it acts non-trivially, and indeed it is a product of m cycles of lengths (d_1+1), \dots, (d_m+1).

It then suffices to count the number of permutations of N with such a property … except there is a nontrivial correction needed to pick out only those permutations which correspond to connected square-tiled surfaces. Eskin-Okounkov-Pandharipande pushed through this strategy to obtain explicit quantitative results, with a strong arithmetic flavor. These results may be made explicit, although there is considerable computational work involved; by comparison, other approaches such as the work of Athreya-Eskin-Zorich referred to above can produce simpler formulas in special cases.

Applications

We have described above and previously how translation surfaces are related to (rational) polygonal billiards, and how the former provide a powerful framework for the study of the latter. Here (and in a subsequent post) we present a number of other applications:

Electron transport

S. P. Novikov suggested the following as a mathematical formulation of electron transport in metals: consider a periodic surface \widetilde{M^2} \subset \mathbb{R}^3; an affine plane in \mathbb{R}^3 intersects this in some union of closed and unbounded intervals. Question: how does an unbounded component propagate in \mathbb{R}^3 (as we move the affine plane in some continuous fashion?)

After we quotient by the period lattice (taken to be \mathbb{Z}^3), we are looking at plane sections of the quotient surface M^2 \subset \mathbb{T}^3. Our original intersection can be viewed as level curves of a linear function f(x,y,z) = ax + by + cz restricted to \widetilde{M^2}, but this does not push down to the quotient; instead, we consider the codimension-one foliation of M^2 defined by the closed 1-form df = a\,dx + b\,dy + c\,dz.

Our question can then be reformulated as follows: what do lifts of leaves of this foliation on M^2 \subset \mathbb{T}^3 look like upstairs, in \widetilde{M^2} \subset \mathbb{R}^3?

Closed 1-forms on surfaces can be straightened to geodesic foliations in appropriate flat metrics iff any cycle formed from a union of closed paths following a sequence of saddle connections is homologically non-trivial. The surfaces and 1-forms obtained from Novikov’s problem can be modified (decomposed and surgered) to satisfy this criterion, and after these reductions we are left exactly in the world of flat structures with closed 1-forms on them, i.e. translation surfaces.

Invisibility

In a subsequent post we describe the illumination problem; a related problem concerns invisibility—more precisely: whether a body with mirror surfaces can be “invisible” from some direction/s, because light rays travelling in these direction/s are reflected in such a way that they continue along trajectories in the same direction/s; or whether a body can be similarly made invisible in certain driections through the strategic placement of mirrors around it. It is a conjecture of Plakhov the set of directions that are invisible for any fixed body has measure zero. This conjecture is closely connected with the (similar) Ivrii conjecture on the measure of the set of periodic billiard trajectories in a bounded domain: if Ivrii’s conjecture is true then, most probably, true also is the conjecture on invisible light rays.

Flat (but not very), and real affine …

There are at least two ways in which the notion of translation surfaces can be generalized: one is to consider flat structures with non-trivial linear holonomy, which “forces a generic geodesic to come back and to intersect itself again and again in different directions.” The other to consider real affine structures, which are maximal collections of charts on a closed surface where all of the transition maps are of the form f(z) = az+b where a > 0 (and is in particular real) and b \in \mathbb{C}.

These remain rather less well-studied and more mysterious, or, in other words / from another perspective, present potentially rich sources of interesting open problems …

References

Zorich’s survey covers a broad range of ideas, and contains many further references

Hubert-Masur-Schmidt-Zorich have a (slightly outdated) list of open problems on translation surfaces , from a conference at Luminy.

Standard
Articles

Groups and graphs (and computation)

Graphs in group theory

Given a group G, or more specifically a finite set S of generators for G, one can form the Cayley graph \mathrm{Cay}(G,S) by taking the vertex set to be the set of group elements, and adding an edge vw iff v = ws for some s \in S.

One can then attempt to study algebraic properties of the group by looking at properties of (one of) its Cayley graph(s). In the case of an infinite group G, one can show that any two Cayley graphs, i.e. the Cayley graphs associated to any two sets of generators, have the same coarse geometry (in the sense of quasi-isometry—see the post on geometric group theory), so that the coarse geometric properties of any Cayley graph can be considered to be intrinsic geometric properties of the group, rather than properties of any particular presentation thereof. Indeed, this is the key insight that drives geometric group theory.

One particularly striking example where such geometric methods seem to yield great insight with much less pain than directly algebraic ones is in the case of free groups and their automorphism groups, which may be thought of geometrically as fundamental groups of bouquets of circles. This is equivalent to the Cayley graph viewpoint: the Cayley graph is the universal cover of the bouquet of circles. Automorphisms of the free group then correspond to homotopy equivalences of the bouquet of circles, and arguments about the automorphism group can be conducted in terms of these homotopy equivalences, leading to such results as classifications and characterizations of these automorphisms analogous to the classification of mapping classes of surfaces.

The same arguments apply to finite groups, although in this case the graphs are finite, and so quasi-equivalent to trivial graphs (i.e. the graph with one vertex and no edges), and geometric group theory has nothing more to say. From this point of view, finite groups are, in a very precise sense, virtually trivial. I do wonder though: can the theory of finite graphs, itself a rather rich area of combinatorics, be fruitfully used to say / argue interesting things about finite groups?

Graphs also appear in group theory in the notion of graphs of groups which is fundamental to the Bass-Serre theory of groups acting on simplicial trees. Here the graph acts essentially as a book-keeping mechanism to record the structure of the group as built up from vertex and edge stabilisers; these graphs have also been described as “one-dimensional analogues of orbifolds”. Group actions on trees appear in a variety of settings, for fundamental reasons I do not yet fully understand, and so this notion takes on some importance.

Groups in graph theory

Conversely, group theory can play a role in elucidating the structure theory of graphs. For instance, group theory played a significant role in Laci Babai’s recent breakthrough on graph isomorphism. Very roughly speaking, Babai’s algorithm relies on the heuristic that any isomorphism between graphs has to preserve degree. Thus, given a highly irregular graph, a brute-force search could actually be (sufficiently) efficient, since the number of possible isomorphisms is small relative to the number of vertices.

The problem, then, is if we have highly regular graphs. One way around this is to consider an equitable partition; but one may not always have one of these either. However, Babai proved that the only obstacle to the existence of such a partition is the existence of a large Johnson graph, and then used subtle structural results, of an essentially algebraic nature, on Johnson groups and how they sit inside larger (finite) permutation groups to obtain, constructively, either an isomorphism, or a certificate of non-isomorphism (a provably empty automorphism group.)

In the language of Babai’s preprint: “We shall certify both the presence and the absence of local symmetry. … If we don’t find local symmetry, we infer global irregularity; if we do find local symmetry, we either build it up to global symmetry (find automorphisms) or use any obstacles to this attempt to infer local irregularity which we then synthesize to global irregularity. Building up symmetry means approximating the automorphism group from below; when we discover irregularity,we turn that into an effective upper bound on the automorphism group . When the lower and the upper bounds on the automorphism group meet, we have found the automorphism group and solved the isomorphism problem.”

Here the group theory plays a key role in introducing more rigidity / structure to an otherwise fairly flexible and fluid structure. The structural theory of finite groups is used in a fairly strong way: indeed, the proof relies on the classification of finite simple groups, although the strict logical dependence is only on one of its corollaries (Schreier’s statement that the outer automorphism group of a finite simple group is solvable.)

A concrete application to coding theory

Group theory and graph theory both come into play in e.g. the construction and study of codes from Cayley graphs and Schreier graphs: the algebraic structure introduced by the group-theoretic construction of these graphs is very helpful in proving key desired properties of these codes.

Standard
Questions, Reading Notes

Cryptosystems using free group automorphisms

Moldenhauer has proposed proposed cryptographic protocols which make use of \mathrm{Aut}(F_n). Here we describe them, for the fun of it, and because a potential closer analysis of their security suggests potentially interesting problems (or perhaps exercises—I don’t know enough / haven’t spent enough time to be able to judge) regarding automorphisms of free groups.

One-time pads of free group automorphisms

Choose a free group F_q, a key-space (\phi_n)_{n=1}^N consisting of some large number N (say, 2^{128}) of automorphisms of F_q, and a linear congruence generator h: \mathbb{Z}/N \to \mathbb{Z}/N with maximal period length.

To communicate securely, Alice and Bob privately agree on a free subgroup F_U with rank equal to the alphabet size, a (minimal Nielsen-reduced freely-reduced) free generating set U, and a starting seed for the linear congruence generator.

To securely send a message m = m_1 \cdots m_z, Alice generates an equally-long string of congruences k_1 \cdots k_z using h, and sends the ciphertext \phi_{k_1}(m_1) \cdots \phi_{k_z}(m_z) as an unreduced word in F_q, where we implicitly identify letters in the alphabet with corresponding generators of F_U from S. She also sends z.

To decrypt the ciphertext, Bob calculates k_1 \cdots k_z using h and then \phi_{k_r}(u) for all 1 \leq r \leq z and u \in U, and uses this to chunk the ciphertext into words corresponding to individual letters, which are then decrypted using the corresponding \phi_{k_r}^{-1}.

This effectively uses the ginormous size of \mathrm{Aut}(F_n) and its highly noncommutative nature (or, more precisely, the difficulty of guessing \phi_{k_1}, \dots, \phi_{k_z} given h and \phi_{k_1}(m_1) \cdots \phi_{k_z}(m_z), but not k_1) for cryptographic security, although the protocol itself (a one-time pad) is not terribly sophisticated.

Vague hyperbolic language aside, the security of this system really rests on how the automorphisms \phi_i are randomly chosen. Moldenhauer proposes a system which uses binary strings, of varying lengths (details unspecified here) and maps these to Whitehead automorphisms in some systematically random way.

Question: Is the proposed method of  generating the automorphisms secure, or is it vulnerable to heuristic or other attacks?

Public-key encryption with free group automorphisms

Moldenhauer also suggests a public-key protocol: here the public parameters consist of the free group F_q, a freely reduced word w \neq 1 in the free group, and an automorphism f: F \to F of infinite order.

Alice and Bob pick private keys a, b \in \mathbb{Z}_{>0}, and publish as their public keys f^a(w), f^b(w).

To securely send a message m to Bob, Alice computes the freely-reduced elements m \cdot f^a(f^b(w)) =: c and send this to Bob as the ciphertext.

Bob decrypts the message by computes c_1 \cdot (f^b(f^a(w)))^{-1} = m \cdot f^{a+b}(w) f^{-(b+a)}(c) = m.

Security here is based on the difficulty of determining how much cancellation happens. Presumably, though, not all of the plaintext is cancelled most of the time, so there will likely be some substantial chunk of plaintext just hanging out in front, which seems … not optimal.

Slightly more secure might be to have Alice send f^a(m), have Bob not immediately decrypt, but instead compute f^{b+a}(m) and send this back to Alice, and then have Alice compute f^{-a}(f^{b+a}(m)) = f^b(m). Now Bob decrypts the message by computing m =  f^{-b}(f^b(m)).

We can modify this further for use as a signature / authentication protocol: as a signature to Bob, Alice sends f^a(f^b(w)) = f^{a+b}(w) to Bob; Bob computes f^{-b}(f^{a+b}(w)) and verifies that this matches with Alice’s public key f^a(w).

The security of these modified protocols are based on the difficulty of efficiently of deducing and b or m, given only f and the images f^a(m), f^b(m) and f^{a+b}(m); i.e. the difficulty of the (analogue of the) discrete logarithm in generic infinite cyclic subgroups of the free group.

Questions: Do generic infinite-order automorphisms of the free group actually have good properties from the standpoint of these cryptographic applications? How much cancellation can we typically expect in freely reducing m \cdot f^{a+b}(w)? Moldenhauer’s arXiv preprint doesn’t appear to address these questions, although her thesis might.

Also: if Eve observes a lot of the Alice’s comunications secured using this last protocol, she will see a lot of pairs (x, f^a(x)), since f^{a+b}(m) = f^a(f^b(m)), and both f^{a+b}(m) and f^b(m) are exchanged in the protocol. How many of these would Eve need to collect before she can try to effectively reconstruct what f^a is? How much will the cancellation / free reduction created by concatenating signatures (or other material) to the end of messages alleviate this?

Standard
Articles

Weil-Petersson geometry (II)

Reformulations

Random geodesics and geodesic currents

Given two different hyperbolic metrics m and m’ on a closed topological surface, i.e. two different points in Teichmüller space, Thurston defined a quantity A(m, m') which can be interpreted as the length of a “random geodesic” in one metric measured in the other metric. A more precise definition involves intersection forms and Liouville measures and the transverse measure L_m to the geodesic flow, terms (some of) which are to be defined presently.

By the (rather computational) work of Wolpert, this metric turns out to be equivalent to the Weil-Petersson metric.

Bonahon reinterpreted this, yet again, in the language of geodesic currents. A geodesic current associated to a closed hyperbolic surface S is a measure on the set G(\tilde{S}) of unoriented geodesics of the universal cover \tilde{S} which is invariant under the natural action of \pi_1(S).

The space of geodesics G(\tilde{S}) embeds into the space of currents \mathscr{C}(S) as atomic measures, and this can be extended to an embedding of the measured laminations \mathscr{ML}(S) into \mathscr{C}(S). Indeed the image of the geodesics under scalar multiplication, i.e. \mathbb{R} \cdot G(\tilde{S}), is dense in \mathscr{C}(S).

Moreover, we can extend the geometric intersection number on closed geodesics to a continuous symmetric bilinear form i: \mathscr{C}(S) \times \mathscr{C}(S) \to \mathbb{R}^+.

What makes \mathscr{C}(S) an interesting object to consider is that there is also a natural embedding of Teichmüller space \mathcal{T}(S) \curvearrowright \mathscr{C}(S), which works by taking any point into the Liouville measure induced by the associated hyperbolic metric. This embedding is as nice as one might want it to be; in particular, its image can be characterized by analytic equations.

We can now use the intersection form to define a (path) metric on Teichmüller space, or rather on its image in the space of currents, relate this to Thurston’s metric, and then appeal to Wolpert’s result to find that this metric is in fact equivalent to the Weil-Petersson metric.

The thermodynamic formalism and the pressure metric

Yet another reinterpretation of—i.e. yet another way of defining a metric on Teichmüller space which turns out to be equivalent to—the Weil-Petersson metric involves the thermodynamic formalism from dynamics.

The thermodynamic formalism, for our purposes, is a machine from symbolic dynamics which produces analytically varying numerical invariants associated to families of (sufficiently nice) dynamical systems. In our case the dynamical system in question will be the geodesic flow on the unit tangent bundle of our closed hyperbolic surface, which may be represented as a finite-type shift using the Bowen-Series coding; we obtain our family of systems by considering Hölder reparametrizations of this flow.

From this system we obtain a space of \alpha-Hölder functions, which we view as reparametrizations of our geodesic flow, and thence a function C^{1+\alpha}(S^1) \to \mathbb{R}_{\geq 0}  the pressure function, which is equal to the log of the spectral radius of the transfer operator. Pressure-zero functions correspond to ergodic, flow-invariant equilibrium measures.

We may verify that pressure varies analytically, and so the second derivative of the pressure is well-defined, and is equal to the variance for a pressure-zero Hölder function. We may further check that the corresponding pressure metric defined by \|g\|^2_{\mathbf{P}} := \frac{\partial^2}{\partial t^2} \big|_{t=0} \mathbf{P}(f+tg) on the space of pressure-zero functions is positive-definite.

Working through this machinery, McMullen (building on the work of Bridgeman and Taylor, who extended the Weil-Petersson metric to quasifuchsian space) showed that the pressure metric may be expressed in terms of the Hessian of the Hausdorff dimension of the limit set, or of the pushforward measure on the boundary circle.

With more work, this Hausdroff dimension can also be related to the Weil-Petersson metric, and this can be used to show that the pressure metric on Teichmüller space is equivalent to the Weil-Petersson metric.

This pressure metric was subsequently extendedby Bridgeman, Canary, Labourie and Sambarino to more general higher Teichmüller spaces / spaces of Anosov representations. In that setting the technicalities are considerably more formidable—one has to produce a flow space to replace the geodesic flow on the unit tangent bundle, showing that the resulting pressure metric is well-defined and non-degenerate is much more work, etc.

Example here

[[ akan datang ]]

Applications

Wolpert’s expansions and estimates on curvature, together with the geometry of the boundary strata, can be used to produce an arithmetic Riemann-Roch formula for pointed stable curves, which yields e.g. the exact formula for the Selberg zeta function on the level-2 principal congruence subgroup \Gamma(2) < \mathrm{SL}_2\mathbb{R}. I don’t understand this at all well enough to comment further, but I’m going to speculate that the Weil-Petersson geometry plays the role which e.g. moduli space / stack arguments play in the Arakelov theory version.

A different (line of) application(s) appears in the groundbreaking work of Maryam Mirzakhani, who used a recursion formula for the Weil-Petersson volume of moduli space(s) to obtain asymptotic counts of simple closed geodesics on hyperbolic surfaces, establish relations to intersection theory on stable curves (including a new proof of the Witten-Kontsevich formula), applications to mathematical physics, and so on …

All of these results can also be used to study—going back to where it all began, in some sense—the properties of random Riemann surfaces of high genus.

Standard