You are currently browsing the tag archive for the ‘integer programming’ tag.
I have just uploaded a paper to the arXiv, entitled “Scl, sails and surgery”. The paper discusses a connection between stable commutator length in free groups and the geometry of sails. This is an interesting example of what sometimes happens in geometry, where a complicated topological problem in low dimensions can be translated into a “simple” geometric problem in high dimensions. Other examples include the Veronese embedding in Algebraic geometry (i.e. the embedding of one projective space into another taking a point with homogeneous co-ordinates to the point whose homogeneous co-ordinates are the monomials of some fixed degree in the ), which lets one exhibit any projective variety as an intersection of a Veronese variety (whose geometry is understood very well) with a linear subspace.
In my paper, the fundamental problem is to compute stable commutator length in free groups, and more generally in free products of Abelian groups. Let’s focus on the case of a group where are free abelian of finite rank. A is just a wedge of tori of dimension equal to the ranks of . Let be a free homotopy class of -manifold in , which is homologically trivial. Formally, we can think of as a chain in , the vector space of group -boundaries, modulo homogenization; i.e. quotiented by the subspace spanned by chains of the form and . One wants to find the simplest surface mapping to that rationally bounds . I.e. we want to find a map such that factors through , and so that the boundary wraps homologically times around each loop of , in such a way as to infimize . This infimum, over all maps of all surfaces of all possible genus, is the stable commutator length of the chain . Computing this quantity for all such finite chains is tantamount to understanding the bounded cohomology of a free group in dimension .
Given such a surface , one can cut it up into simpler pieces, along the preimage of the basepoint . Since is a surface with boundary, these simpler pieces are surfaces with corners. In general, understanding how a surface can be assembled from an abstract collection of surfaces with corners is a hopeless task. When one tries to glue the pieces back together, one runs into trouble at the corners — how does one decide when a collection of surfaces “closes up” around a corner? The wrong decision leads to branch points; moreover, a decision made at one corner will propogate along an edge and lead to constraints on the choices one can make at other corners. This problem arises again and again in low-dimensional topology, and has several different (and not always equivalent) formulations and guises, including -
- Given an abstract branched surface and a weight on that surface, when is there an unbranched surface carried by the abstract branched surface and realizing the weight?
- Given a triangulation of a -manifold and a collection of normal surface types in each simplex satisfying the gluing constraints but *not* necessarily satisfying the quadrilateral condition (i.e. there might be more than one quadrilateral type per simplex), when is there an immersed unbranched normal surface in the manifold realizing the weight?
- Given an immersed curve in the plane, when is there an immersion from the disk to the plane whose boundary is the given curve?
- Given a polyhedral surface (arising e.g. in computer graphics), how can one choose smooth approximations of the polygonal faces that mesh smoothly at the vertices?
I think of all these problems as examples of what I like to call the holonomy problem, since all of them can be reduced, in one way or another, to studying representations of fundamental groups of punctured surfaces into finite groups. The fortunate “accident” in this case is that every corner arises by intersecting a cut with a boundary edge of . Consequently, one never wants to glue more than two pieces up at any corner, and the holonomy problem does not arise. Hence in principle, to understand the surface one just needs to understand the pieces of that can arise by cutting, and the ways in which they can be reassembled.
This is still not a complete solution of the problem, since infinitely many kinds of pieces can arise by cutting complicated surfaces . The -manifold decomposes into a collection of arcs in the tori and which we denote respectively, and the surface (hereafter abbreviated to ) has edges that alternate between elements of , and edges mapping to . Since is a torus, handles of mapping to can be compressed, reducing the complexity of , and thereby , so one need only consider planar surfaces .
Let denote the real vector space with basis the set of ordered pairs of elements of (not necessarily distinct), and the real vector space with basis the elements of . A surface determines a non-negative integral vector , by counting the number of times a given pair of edges appear in succession on one of the (oriented) boundary components of . The vector satisfies two linear constraints. First, there is a map defined on a basis vector by . The vector satisfies . Second, each element is a based loop in , and therefore corresponds to an element in the free abelian group . Define on a basis vector by (warning: the notation obscures the fact that and map to quite different vector spaces). Then ; moreover, a non-negative rational vector satisfying has a multiple of the form for some as above. Denote the subspace of consisting of non-negative vectors in the kernel of and by . This is a rational polyhedral cone — i.e. a cone with finitely many extremal rays, each spanned by a rational vector.
Although every integral is equal to for some , many different correspond to a given . Moreover, if we are allowed to consider formal weighted sums of surfaces, then even more possibilities. In order to compute stable commutator length, we must determine, for a given vector , an expression where the are positive real numbers, which minimizes . Here denotes orbifold Euler characteristic of a surface with corners; each corner contributes to . The reason one counts complexity using this modified definition is that the result is additive: . The contribution to from corners is a linear function on . Moreover, a component with can be covered by a surface of high genus and compressed (increasing ); so such a term can always be replaced by a formal sum for which . Thus the only nonlinear contribution to comes from the surfaces whose underlying topological surface is a disk.
Call a vector a disk vector if where is topologically a disk (with corners). It turns out that the set of disk vectors has the following simple form: it is equal to the union of the integer lattice points contained in certain of the open faces of (those satisfying a combinatorial criterion). Define the sail of to be equal to the boundary of the convex hull of the polyhedron (where here denotes Minkowski sum). The Klein function is the unique continuous function on , linear on rays, that is equal to exactly on the sail. Then over expressions satisfies where denotes norm. To calculate stable commutator length, one minimizes over contained in a certain rational polyhedron in .
Sails are considered elsewhere by several authors; usually, people take to be the set of all integer vectors except the vertex of the cone, and the sail is therefore the boundary of the convex hull of this (simpler) set. Klein introduced sails as a higher-dimensional generalization of continued fractions: if is a polyhedral cone in two dimensions (i.e. a sector in the plane, normalized so that one edge is the horizontal axis, say), the vertices of the sail are the continued fraction approximations of the boundary slope. Arnold has revived the study of such objects in recent years. They arise in many different interesting contexts, such as numerical analysis (especially diophantine approximation) and algebraic number theory. For example, let be a matrix with irreducible characteristic equation, and all eigenvalues real and positive. There is a basis for consisting of eigenvalues, spanning a convex cone . The cone — and therefore its sail — is invariant under ; moreover, there is a subgroup of consisting of matrices with the same set of eigenvectors; this observation follows from Dirichlet’s theorem on the units in a number field, and is due to Tsuchihashi. This abelian group acts freely on the sail with quotient a (topological) torus of dimension , together with a “canonical” cell decomposition. This connection between number theory and combinatorics is quite mysterious; for example, Arnold asks: which cell decompositions can arise? This is unknown even in the case .
The most interesting aspect of this correspondence, between stable commutator length and sails, is that it allows one to introduce parameters. An element in a free group can be expressed as a word in letters , e.g. , which is usually abbreviated with exponential notation, e.g. . Having introduced this notation, one can think of the exponents as parameters, and study stable commutator length in families of words, e.g. . Under the correspondence above, the parameters only affect the coefficients of the linear map , and therefore one obtains families of polyhedral cones whose extremal rays depend linearly on the exponent parameters. This lets one prove many facts about the stable commutator length spectrum in a free group, including:
Theorem: The image of a nonabelian free group of rank at least under scl in is precisely .
Theorem: For each , the image of the free group under scl contains a well-ordered sequence of values with ordinal type . The image of contains a well-ordered sequence of values with ordinal type .
One can also say things about the precise dependence of scl on parameters in particular families. More conjecturally, one would like to use this correspondence to say something about the statistical distribution of scl in free groups. Experimentally, this distribution appears to obey power laws, in the sense that a given (reduced) fraction appears in certain infinite families of elements with frequency proportional to for some power (which unfortunately depends in a rather opaque way on the family). Such power laws are reminiscent of Arnold tongues in dynamics, one of the best-known examples of phase locking of coupled nonlinear oscillators. Heuristically one expects such power laws to appear in the geometry of “random” sails — this is explained by the fact that the (affine) geometry of a sail depends only on its orbit, and the existence of invariant measures on a natural moduli space; see e.g. Kontsevich and Suhov. The simplest example concerns the (-dimensional) cone spanned by a random integral vector in . The orbit of such a vector depends only on the gcd of the two co-ordinates. As is easy to see, the probability distribution of the gcd of a random pair of integers obeys a power law: with probability . The rigorous justification of the power laws observed in the scl spectrum of free groups remains the focus of current research by myself and my students.