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.



The numerical procedure for finding the circle radius seems to be a mere binary search: shrink the circle if the polygon sides wrap around 2π and expand it otherwise.


Sure. The details that I didn't work out were working out the trigonometric formula for testing "if the polygon sides wrap around" and proving that it is appropriately monotonic so that it can be used in a binary search.


We had a similar run-in with Galois theory recently. In my newest arXiv preprint The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems (arXiv:1404.4020 with Jin-Yi Cai, Heng Guo), we also encountered an infinite sequence of polynomials and wanted to determine their Galois groups. Our ultimate goal was to show that the roots of these polynomials satisfy a condition that we call the lattice condition. Dick Lipton and Ken Regan had a blog post about our paper which discusses the lattice condition.

Our situation was easier than yours though because all of our polynomials are of the same degree, namely 5. However, we were still unable to prove that these polynomials are irreducible. Since we were able to show that these polynomials all have exactly one pair of nonreal complex conjugate roots, proving irreducibility implies the Galois groups are all the full symmetric group S_5. After we published our arXiv version, I asked MathOverflow how to prove irreducibility. I got a great answer from Noam Elkies, but its just a proof sketch that I still don't fully understand.

~ Tyson Williams


Also, I agree with your comment that Galois theory is not a completed subject. The methods to determine the Galois group of a polynomial seem ad hoc to me. Mathematicians probably want to characterize which polynomials have a particular Galois group (say, for Galois groups of polynomials with integer coefficients over Q) but my impression is that things are too complicated for any meaningful characterization to exist. As a computer scientist, I would be happy with a polynomial-time algorithm that computes the Galois group of a given polynomial. This also seems too difficult because of the vast number of possible Galois groups for large degree polynomials. To approach this lofty goal, I suggest parameterizing by a set \mathcal{G} of Galois groups. The problem defined by \mathcal{G} is to determine if the Galois group of a given polynomial is in \mathcal{G}. If \mathcal{G} contains Galois groups for polynomials at most degree 4, then this problem can be solved in polynomial time (see, for example, this excellent exposition by Keith Conrad). We can also efficiently decide the case when \mathcal{G} is the set of all transitive Galois groups since this is equivalent to the polynomial being irreducible.

~ Tyson Williams