Queen Dido and the carpenter's rule

The story goes that Dido, a refugee from her home city of Tyre, took refuge in north Africa where king Iarbas granted her and her followers a small amount of land: the amount that she could surround by an oxhide. Cleverly, she cut the hide into a cord, which she arranged in a circle around a hill to maximize the area it would surround, and in so doing founded the city of Carthage. But what if Dido had been granted a carpenter's rule instead of an oxhide? Mathematically, the problem is: given a polygon in the plane, formed by rigid line segments connected to each other by flexible hinges at the vertices, adjust the angles of the polygon to surround the maximum area possible. What is the shape of the optimal solution?

The answer turns out to be a convex and cyclic polygon, meaning that the endpoints of the line segments all lie on a single circle. It doesn't matter how the lengths of the segments in the polygon are permuted; you always get the same circle and the same area regardless of the permutation. But which circle? How to compute its radius? I think this problem is not hard to solve with an iterative numerical procedure that converges to the optimal circle radius (although I haven't worked out the details). It's also possible to set up a system of polynomial equations that has the optimal circle radius as a root. But it turns out not to be possible to write down an algebraic expression (even one involving fractional powers) for the solution. In algebraic terms, the desired radius might generate an extension of the rationals that has an unsolvable Galois group. (The reference I have for this is Varfolomeev, V.V.: Galois groups of the Heron–Sabitov polynomials for inscribed pentagons. Mat. Sb. 195 (2004) 3–16 Translation in Sb. Math. 195: 149–162, 2004.)

My new arxiv preprint with the long title "The Galois Complexity of Graph Drawing: Why Numerical Solutions are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings" (arXiv:1408.1422, with Bannister, Devanny, and Goodrich, to appear at GD) similarly uses Galois theory to prove the non-existence of an exact algebraic formula for many important problems in the geometric representation of graphs. These include force-directed graph drawing methods (i.e. pretend your edges are springs pulling together vertices that have repulsive electrical charges on them and see what happens), spectral graph drawing methods (construct a matrix from your graph, find its eigenvectors, and use the top few as coordinates), multidimensional scaling (pretend your graph distances are Euclidean distances, transform the distance matrix to a matrix that in the Euclidean case would be the dot products of coordinate vectors, and use matrix factorization to find the corresponding Euclidean coordinates), and the construction of circle packings that represent planar graphs.

Of course, algebraic formulas with fractional powers (also known as nested radicals) aren't the only thing one could use to describe the solutions to these problems with an exact formula. For instance, there's a way to use elliptic functions to solve fifth-degree polynomials, even the ones that have no solution in nested radicals. But we also show that, even if you have a black box for solving fifth-degree polynomials (or polynomials of any bounded degree), and you could use that black box iteratively on the numbers produced in earlier iterations, you still wouldn't be able to solve most of these problems. (For technical reasons this part of our results doesn't work for MDS.)

What effect does any of this have on practical graph drawing? Essentially none. These problems are all solved in practice efficiently and quickly with numerical methods that converge quickly to the correct answer (except in the force-directed case, where they only converge to a local minimum, but that's usually considered good enough). The point is less to try to change practice and more to understand why approximate numerical methods are the preferred choice for these problems when exact algebraic methods work well for many other algorithmic problems in geometry and when these problems can be formulated algebraically.

This project also taught me that Galois theory is far from a completed subject. For instance, suppose you want a sequence of polynomials, one for each degree, whose Galois groups are as nasty as they could be (the symmetric groups of order equal to the degree). Some sequences like this are known, for instance certain families of trinomials. But now, suppose you already have a sequence of polynomials, one for each degree, and you suspect their Galois groups are the symmetric groups. How to prove this? All the tools we could find for this sort of problem work by computing the Galois group of individual polynomials, one at a time, so we don't know how to compute Galois groups of infinite sequences of polynomials (even when we're pretty sure what those groups are). This is relevant for the new preprint because it shows nonexistence of two kinds of formulas: ones with fractional powers (of arbitrarily high degree) and ones with black boxes for roots (of bounded degree). What we really want to show is that the problems we consider lead to unsolvable Galois groups of arbitrarily high order. If we could do that, it would imply the nonexistence of formulas that are allowed to include both fractional powers (of unbounded degree) and black boxes for roots (of bounded degree). But we're prevented from doing that by our inability to compute Galois groups of infinite sequences of polynomials.

---

Comments: