fuglede.dk

31/3/2021, 15:19

Burau and the infinite parking garage

Today, we'll be taking a look at an 85 year old open problem in mathematics, and we will see how more recent ideas reduce the problem to installing a Python package and finding a collection of four integers which may or may not exist.

Background

This section can be skipped if you're not too worried about context and just want to get to the problem itself.

The problem we are interested in is the following: Is the Burau representation of the four-strand braid group faithful? That is, we're taking a look at certain map, called the Burau representation, which takes as input a braid on four strands, outputs a certain matrix for that braid, and what we're interested in is whether the trivial braid (consisting of four vertical strands) is the only one which maps to the identity matrix.

There are versions of this problem for groups of braids on any number of strands: The Burau representation for the 3-strand braid group is known to be faithful, whereas the representation for the \(n\)-strand is not faithful for \(n \geq 5\). The latter result was obtained through a reformulation of the problem due to Long and Paton, which turns the problem into finding a particular pair of curves in an infinite parking garage held up by \(n\) pillars, and can be used to find concrete examples of non-trivial braids whose Burau representation is the identity matrix. This is the construction we will be diving into below.

The Burau representation shows up in a number of related fields; it was among the first representations considered in the group theory of the braid groups, it shows up as one of the simplest examples in topological quantum field theory, and in particular in topological quantum computation, in which the braid describes the time evolution of a set of anyons, and it shows up in the more algebraic discipline of quantum group representation theory.

An infinite parking garage

Our setting is a parking garage with infinitely many circular floors in both directions; one floor for every integer. On each floor there are four pillars, and extending from each of the four pillars, there is a ramp that can be used to go up or down. The slope of each ramp is so that crossing the ramp while moving clockwise takes us down a floor.

We identify the pillars using compass directions and will be considering paths going from the northwest pillar on floor 0, facing south, to the northeast pillar, facing north, not necessarily on the same floor. In the picture below, we show such a path which descends 10 floors before reaching the northeast pillar.

The two bottom pillars are actually toll booths: When passing the line between them, we pay 1 unit of currency if crossing from the north, or get 1 back if passing from the south. Each floor has its own toll collectors. In the example above, we end up paying (or earning) the following:

Floor   0 toll is +1
Floor  -2 toll is +1
Floor  -4 toll is +1
Floor  -8 toll is -1
Floor -10 toll is -1

That is, starting from the northwest pillar, we immediately cross the toll line from the north, then descend two floors before we cross the toll line again, from the north as well, and so forth. In the image below, we indicate the sign of the toll next to the crossing.

We can now phrase the open question we are interested in:

Let us look at some examples that show the meaning of the final two constraints. In the example below, we first pay 1 to the floor 0 toll collector, then immediately get 1 back, so the total toll is 0 at floor 0 (and every other floor), and there are no self-intersections, but by wiggling the path up a bit, it no longer crosses the toll line, which is forbidden by point 3 above.

Similarly, in the example below, we first pay 1 to the floor 0 toll collector, then descend one floor and ascend shortly after, to get 1 back from the floor 0 collectors, so once again, the total toll is 0 on every floor. Moreover, in this case it is impossible to wiggle the path away from the toll line (in the projection, we can not wiggle through pillars), so point 3 is not violated, but point 2 is: even though the path never intersects itself in the infinite parking garage, the projection of the path does intersect itself (six times, actually).

For the rest of the discussion, we will be considering a particular set of paths constructed as follows: Choose four positive integers cap_west, cap_east, cup_west, and cup_east satisfying

cup_west + cup_east > cap_west + cap_east.

The terms "cup" and "cap" refer to the mathematical symbols for union and intersection, \(\cup\) and \(\cap\), respectively. We use each of these integers to define a collection of half-circles around each pillar. The path considered above follows this construction with cap_west = 2, cap_east = 1, cup_west = 3, and cup_east = 2.

Let cap_outer = cup_west + cup_east - (cap_west + cap_east + 1) and use this to define a collection of half-circles containing both north pillars at once. In the example above, cap_outer = 1.

Everything has been set up so it's possible to connect the north and south halves of the picture to create a path between the north pillars. Note that in some cases the path will have multiple connected components (try drawing cap_west = cap_east = 1, cup_west = cup_east = 3), but it is possible to place conditions on the four integers so this never happens; we won't bother here though.

A Python implementation

A Python package for calculating the total toll is available on PyPI, and whose source code is available on GitHub. It can be installed using pip:

pip install burau

In particular, we can calculate the total toll – also known as the Burau polynomial – of the path above:

>>> from burau.curve import calculate_polynomial
>>> calculate_polynomial(cap_west=2, cap_east=1, cup_west=3, cup_east=2)
(DictType[int64,int64]({0: 1, -2: 1, -4: 1, -8: -1, -10: -1}), True, 5)

We focus on the dictionary {0: 1, -2: 1, -4: 1, -8: -1, -10: -1}; the keys of the dictionary represent the floors, and the corresponding values are the tolls paid (or earned) at those floors. Note that this result exactly matches what we found previously.

In terms of this package, the open question now becomes the following:

At this point, there are several avenues for experimentation:

• One could simply systematically try all combinations of the four positive integers, ordered by, say, their sum. It is known that if a solution exists, the resulting path will have to cross at least 2000 toll lines, so such a search for an example solution seems unlikely to become fruitful.


• Directed search, such as A* search with heuristics like the width of the result dictionary (i.e. max(res.keys()) - min(res.keys())), or the sum of absolute values of its values (i.e. sum(map(abs, res.values()))), or a combination thereof, also has not yielded a solution, but at the same time quickly gives insight into what the space of possible results looks like.


• Another approach has been to try to identify which solutions arise once one allows the parking garage to repeat itself by saying, for instance, that ascending 17 floors gets you back to where you started (i.e. treating the resulting dictionary keys as identical if they are equal modulo 17).


• Chances are that no solution exists. Taking that as a starting point, one can try to use calculate_polynomial to find enough patterns in the results to rule out the existence of a solution.

The source code of the package, and the description of the paths above, closely follow Stephen Bigelow's approach to the same problem, and in particular, Bigelow has been helpful in explaining the approach leading to this blog post. The above is also the direct result of conversations with Jens Kristian Egsgaard, following earlier work of ours.

Comments

No comments yet.

Add a comment

To avoid too much spam, you'll have to log in to add a comment. You can do so below, or you can create a user, if you don't already have one. You can use your photo login here as well.