Until recently, gerrymandered districts tended to stick out, identifiable by their contorted tendrils. This is no longer the case. “With modern technology, you can gerrymander pretty effectively without making your shapes very weird,” said Beth Malmskog, a mathematician at Colorado College. This makes it that much harder to figure out whether a map has been unfairly manipulated.

Without the telltale sign of an obviously misshapen district to go by, mathematicians have been developing increasingly powerful statistical methods for finding gerrymanders. These work by comparing a map to an ensemble of thousands or millions of possible maps. If the map results in noticeably more seats for Democrats or Republicans than would be expected from an average map, this is a sign that something fishy might have taken place.

But making such ensembles is trickier than it sounds, because it isn’t feasible to consider all possible maps — there are simply too many combinations for any supercomputer to count. A number of recent mathematical advances suggest ways to navigate this impossibly large space of possible simulations, giving mathematicians a reliable way to tell fair from unfair.

Like so many things related to redistricting, their work is ending up in court. In the last five years, simulations have been accepted as evidence in redistricting court cases in Missouri, North Carolina, Ohio and Michigan. And they are the central objects of debate in Allen v. Milligan, a crucial case pending before the Supreme Court in which Black voters accuse the state of Alabama of drawing its Congressional district map to disadvantage them. In this case, as in many others, simulations are being enlisted by both the plaintiffs and the defendants to plead their case. The Court is expected to issue a decision in June or July.

But, as one of the plaintiffs’ lawyers told Justice Samuel Alito in oral arguments in October, “the simulations actually generate more questions than they answer.”

Combinatorial Explosion

To understand the mathematical difficulty in generating an ensemble, start by thinking of unrealistically simple maps. Imagine, for example, a 4-by-4 grid. There are 117 different ways to subdivide these 16 squares into four contiguous districts with four squares per district. From there, the possibilities grow very quickly in what’s known as a combinatorial explosion. A 6-by-6 grid with six contiguous districts of six squares each has 451,206 possibilities. A 9-by-9 grid with nine districts of nine squares each? Over 700 trillion options. For a 10-by-10 grid, with 100 squares, nobody knows how many possible 10-district configurations there are.

Of course, a typical state has many more than 100 different jurisdictions that can be grouped together into districts.  Analysts often build possible districts out of voting precincts. North Carolina has over 2,500 precincts, for example, while Pennsylvania has 9,159. Official districting plans are generally based on even more granular census blocks: Alabama has 185,976 such blocks.

Every state has different rules for drawing districts, but in general, they must be contiguous and “compact,” preserve traditional geographic and political boundaries, be very close to equal in population, and avoid breaking apart so-called communities of interest. The Voting Rights Act also requires that districts be drawn in a way that ensures that voters of all racial groups get an equal chance to “elect representatives of their choice.” Reconciling all these requirements is mathematically challenging. The more requirements there are on redistricting, Malmskog said, “the more complicated the mathematical problem becomes.”

For the last 20 years, the dominant technique for generating lots of possible maps has been a technique called “random seed and grow.” This works much the way it sounds. Say you want to combine thousands of individual voting precincts into, say, 10 congressional districts, each of which must include about 760,000 people. You start by randomly choosing a precinct to “seed” a particular district. You then add adjacent precincts to this seed until you get close to 760,000 people in the district. Then you repeat the process — start with another precinct to seed another district — until you come up with the rest of your districts.

With some relatively simple tweaks to make sure the districts are compact, it’s possible to use this method to make lots of reasonable-looking maps. But because of the combinatorial explosion in the number of possible maps, even millions of maps made by the random-seed-and-grow technique account for only a tiny fraction of all possible maps. And there is no mathematical evidence that this fraction is representative of the set of valid maps as a whole, which means using it as a basis of comparison can lead to misleading conclusions.

That’s why, in the middle of the past decade, researchers including Kosuke Imai, a professor of government and statistics at Harvard University, and Jonathan Mattingly, a professor of mathematics and statistics at Duke University, began applying a technique called Markov chain Monte Carlo, or MCMC, to make maps.

MCMC works by first transforming the existing district map into a graph — a mathematical structure consisting of nodes, or points, connected by lines, or edges. Each precinct becomes a node; if precincts share a border in real life, they are joined by an edge in the graph. Early MCMC methods, like the “flip-based” method described by Imai and colleagues in a 2014 paper, worked by swapping precincts between bordering districts in a mathematically specific way.

By thinking of their map as a graph, researchers can use a tool from graph theory called the Perron-Frobenius theorem to show that, if the algorithm is allowed to run for long enough — an interval that mathematicians call the mixing time — it will properly sample from the distribution of all possible valid maps. This is an improvement, but it is still usually impossible to rigorously prove exactly how long the mixing time is. Mattingly said the question of how best to “prove to everyone that we did a good job sampling” remains unresolved. So mathematicians are working on tweaks to MCMC to better establish bounds on the mixing time — and to reach it more quickly.