Plane graphs, special alternating links, and contact geometry

Abstract:

There is a beautiful theory of polytopes associated to bipartite plane graphs, due to Alexander Postnikov, Tamas Kalman, and others. Via a construction known as the median construction, this theory extends to knots and links — more specifically, minimal genus Seifert surfaces for special alternating links. The complements of these Seifert surfaces also have interesting geometry. The relationships between these objects provide many interesting connections between graphs, spanning trees, polytopes, knot and link polynomials, and even Floer homology. In recent work with Kalman we showed how these connections extend to contact geometry. I’ll try to explain something of these ideas.

Graphs are pretty important objects in mathematics, and in the world — what with every network of any kind being represented by one, from social connections, to road and rail systems, to chemical molecules, to abstract symmetries. They are a fundamental concept in understanding a lot about the world, from particle physics to sociology.

Knots are also pretty important. How can a loop of string get knotted in space? That’s a fairly basic question and you would think we might know the answer to it. But it turns out to be quite hard, and there is a whole field of mathematics devoted to understanding it. Lord Kelvin thought that atoms were knots in the ether. As it turns out, they are not, and there is no ether. Nonetheless the idea was an interesting one and it inspired mathematicians to investigate knots. Knot theory is now a major field of mathematics, part of the subject of topology. It turns out to be deeply connected to many other areas of science, because many things can be knotted: umbilical cords, polymers, quantum observables, DNA… and earphone cords. (Oh yes, earphone cords.) Indeed, knots arise crucially in some of the deepest questions about the nature of space and time, whether as Wilson loops in topological field theories, or as crucial examples in the theory of 3-dimensional spaces, or 3-manifolds, and as basic objects of quantum topology.

Being able to tell apart graphs and knots is, therefore, a pretty basic question. If you’re given two graphs, can you tell if they’re the same? Or if you’re given two knots, can you tell if they’re the same? This question is harder than it looks. For instance, the two graphs below look quite different, but they are the “same” (or, to use a technical term, isomorphic): each vertex in the first graph corresponds to a vertex in the second graph, in such a way that the connectedness of vertices is preserved.

Telling whether two graphs are the same, or isomorphic, is known as the graph isomorphism problem. It’s a hard problem; when you have very large graphs, it may take a long time to tell whether they are the same or not. As to precisely how hard it is, we don’t yet quite know.

Similarly, two knots, given as diagrams drawn on a page, it is difficult to tell if they are the “same” or not. Two knots are the “same”, or equivalent (or ambient isotopic), if there is a way to move one around in space to arrive at the other. For instance, all three knots shown below are equivalent: they are all, like the knot on the left, unknotted. This is pretty clear for the middle knot; for the knot on the right, have fun trying to see why!

Telling whether two knots are equivalent is also very hard. Indeed, it’s hard enough to tell if a given knot is knotted or knot — which is known as the unknot recognition or unknotting problem. We also don’t quite know precisely how hard it is.

The fact that we don’t know the answers to some of the most basic questions about graphs and knots is part of the reason why graph theory and knot theory are very active areas of current research!

However, there are some extremely clever methods that can be used to tell graphs and knots apart. Many such methods exist. Some are easier to understand than others; some are easier to implement than others; some tell more knots apart than others. I’m going to tell you about two particular methods, one for graphs, and one for knots. Both methods involve polynomials. Both methods are able to tell a lot of graphs/knots apart, but not all of them.

The idea is that, given a graph, you can apply a certain procedure to write down a polynomial. Even if the same graph is presented to you in a different way, you will still obtain the same polynomial. So if you have two graphs, and they give you different polynomials, then they must be different graphs!

Similarly, given a knot, you can apply another procedure to write down a polynomial. Even if the knot is drawn in a very different way (like the very different unknots above), you still obtain the same polynomial. So if you have two knots, and they give you different polynomials, then they must be different knots!

Bill Tutte and his polynomial

Bill Tutte was an interesting character: a second world war British cryptanalyst and mathematician, who helped crack the Lorenz cipher used by the Nazi high command, he also made major contributions to graph theory, and developed the field of matroid theory.

He also introduced a way to obtain a polynomial from a graph, which now bears his name: the Tutte polynomial.

Each graph \(G \) has a Tutte polynomial \(T_G \). It’s a polynomial in two variables, which we will call \(x\) and \(y\). So we will write the Tutte polynomial of \(G\) as \(T_G (x,y)\).

For instance, the graph \(G\) below, which forms a triangle, has Tutte polynomial given by \(T_G (x,y) = x^2 + x + y\).

So how do you calculate the Tutte polynomial? There are a few different ways. Probably the easiest is to use a technique where we simplify the graph step by step in the process. We successively collapse or remove edges in various ways, and as we do so, we make some algebra.

There are two operations we perform to simplify the graph. Each of these two operations “removes” an edge, but does so in a different way. They are called deletion and contraction. You can choose any edge of a graph, and delete it, or contract it, and you’ll end up with a simpler graph.

First, deletion. To delete an edge, you simply rub it out. Everything else stays as it was. The vertices are unchanged: there are still just as many vertices. There is just one fewer edge. So, for instance, the result of deleting an edge of the triangle graph above is shown below.

The graph obtained by deleting edge \(e\) from graph \(G\) is denoted \(G-e\).

Note that in the triangle case above, the triangle graph is connected, and after deleting an edge, the result is still connected. This isn’t always the case: it is possible that you have a connected graph, but after moving an edge \(e\), it becomes disconnected. In this case the edge \(e\) is called a bridge. (You can then think of it as a “bridge” between two separate “islands” of the graph; removing the edge, there is no bridge between the islands, so they become disconnected.)

Second, contraction. To contract an edge, you imagine shrinking it down, so that it’s shorter and shorter, until it has no length at all. The edge has vertices at its endpoints, and so these two vertices come together, and combine into a single vertex. So if edge \(e\) has vertices \(v_1, v_2\) at its endpoints, then after contracting \(e\), the vertices \(v_1, v_2\) are combined into a single vertex \(v\). Thus, if we contract an edge of the triangle graph, we obtain a result something like the graph shown below.

The graph obtained by contracting edge \(e\) from graph \(G\) is denoted \(G.e\).

Contracting an edge always produces a graph with 1 fewer edges. Each edge which previous ended at \(v_1\) or \(v_2\) now ends at \(v\). And contracting an edge usually produces a graph with 1 fewer vertices: the vertices \(v_1, v_2\) are collapsed into \(v\).

However, this is not always the case. If the edge \(e\) had both its endpoints at the same vertex, then the number of vertices does not decrease at all! The endpoints \(v_1\) and \(v_2\) of \(e\) are then the same point, i.e. \(v_1 = v_2\), and so they are already collapsed into the same vertex! In this case, the edge \(e\) is called a loop. Contracting a loop is the same as just deleting a loop.

So, that’s deletion and contraction. We can use deletion and contraction to calculate the Tutte polynomial using the following rules:

Let’s start with some really simple graphs.

If a graph \(G\) has no edges, then it’s just a collection of disconnected vertices. In this case the Tutte polynomial is given by \(T_G (x,y) = 1\).

If a graph has precisely one edge, then that it consists of a bunch of vertices, with precisely one edge \(e\) joining them. If \(e\) connects two distinct vertices, then it is a bridge, and \(T_G (x,y) = x\).

On the other hand, if \(G\) has precisely one edge \(e\) which connects a vertex to itself, then it is a loop, and \(T_G (x,y) = y\).

When you take a graph \(G\) and consider deleting an edge \(e\) to obtain \(G – e\), or contracting it to obtain \(G.e\), these three graphs \(G, G-e, G.e\) have Tutte polynomials which are closely related:

So in fact the Tutte polynomial you are looking for is just the sum of the Tutte polynomials of the two simpler graphs \(G-e\) and \(G.e\).
However! This rule only works if \(e\) is not a bridge or a loop. If \(e\) is a bridge or a loop, then we have two more rules to cover that situation.

When edge \(e\) is a bridge, then \(T_G (x,y) = x T_{G.e} (x,y)\).

When edge \(e\) is a loop, then \(T_G (x,y) = y T_{G-e} (x,y)\).

These may just look like a random set of rules. And indeed they are: I haven’t tried to explain them, where they come from, or given any motivation for them. And I’m afraid I’m not going to. Tutte was very clever to come up with these rules!

Nonetheless, using the above rules, we can calculate the Tutte polynomial of a graph.

Let’s do some examples. We’ll work out a few, starting with simpler graph and we’ll work our way up to calculating the Tutte polynomial of the triangle, which we’ll denote \(G\).

First, consider the graph \(A\) consisting of a single edge between two vertices.

This graph contains precisely one edge, which is a bridge, so \(T_A (x,y) = x\).

Second, consider the graph \(B\) consisting of a single loop on a single vertex. This graph also contains precisely one edge, but it’s a loop, so \(T_B (x,y) = y\).

Third, consider the graph \(C\) which is just like the graph \(A\), consisting of a single edge between two vertices, but with another disconnected vertex.

This graph also contains precisely one edge, which is also a bridge, so it actually has the same Tutte polynomial as \(A\)! So we have \(T_C (x,y) = x\).

Fourth, consider the graph \(D\) which consists of a loop and another edge as shown. A graph like this is sometimes called a lollipop.

Now let \(e\) be the loop. As it’s a loop, rule 4 applies. If we remove \(e\), then we just obtain the single edge graph \(A\) from before. That is, \(D-e=A\). Applying rule 4, then, we obtain \(T_D (x,y) = y T_{D-e} (x,y) = y T_A (x,y) = xy\).

Fifth, consider the graph \(E\) which consists of two edges joining three vertices. We saw this before when we deleted an edge from the triangle.

Pick one of the edges and call it \(e\). (It doesn’t matter which one — can you see why?) If we remove \(e\), the graph becomes disconnected, so \(e\) is a bridge. Consequently rule 3, for bridges, applies. Now contracting the edge \(e\) we obtain the lollipop graph \(E\). That is, \(E-e=C\). So, applying rule 3, we obtain \(T_E (x,y) = x T_{E-e} (x,y) = x T_C (x,y) = x^2 \).

Sixth, let’s consider the graph \(F\) consisting of two “parallel” edges between two vertices. We saw this graph before when we contracted an edge of the triangle.

Pick one of the edges and call it \(e\). (Again, it doesn’t matter which one.) This edge is neither a bridge nor a loop, so rule 2 applies. Removing \(e\) just gives the graph \(A\) with one vertex, which has Tutte polynomial \(x\). Contracting \(e\) gives a graph with a single vertex and a loop. Applying rule 4, this graph has Tutte polynomial \(y\). So, by rule 2, the Tutte polynomial of this graph \(F\) is given by \(\displaystyle T_F (x,y) = x + y \).

Finally, consider the triangle graph \(G\). Take an edge \(e\); it’s neither a bridge nor a loop, so rule 2 applies. Removing \(e\) results in the graph \(E\) from above, which has Tutte polynomial \(x^2\). Contracting \(e\) results in the graph \(F\) from above with two parallel edges; and we’ve seen it has Tutte polynomial \(x+y\). So, putting it all together, we obtain the Tutte polynomial of the triangle as

Having seen these examples, hopefully the process starts to make some sense.

However, as we mentioned before, we’ve given no motivation for why this works. And, it’s not even clear that it works at all! If you take a graph, you can delete and contract different edges in different orders and get all sorts of different polynomials along the way. It’s not at all clear that you’ll obtain the same result regardless of how you remove the edges.

Nonetheless, it is true, and was proved by Tutte, that no matter how you simplify the graph at each stage, you’ll obtain the same result. In other word, the Tutte polynomial of a graph is actually well defined.

H, O, M, F, L, Y, P and T

Tutte invented his polynomial in the 1940s — it was part of his PhD thesis. So the Tutte polynomial has been around for a long time. The knot polynomial that we’re going to consider, however, is considerably younger.

In the 1980s, there was a revolution in knot theory. The excellent mathematician Vaughan Jones in 1984 discovered a polynomial which can be associated to a knot. It has become known as the Jones polynomial. It was not the first polynomial that anyone had defined from a knot, but it sparked a great deal of interest in knots, and led to the resolution of many previously unknown questions in knot theory.

Once certain ideas are in the air, other ideas follow. Several mathematicians started trying to find improved versions of the Jones polynomial, and at least 8 mathematicians came up with similar ways to improve the Jones polynomial. In 1985, Jim Hoste, Adrian Ocneanu, Kenneth Millett, Peter J. Freyd, W. B. R. Lickorish, and David N. Yetter published a paper defining a new polynomial invariant. Making an acronym of their initials, it’s often called the HOMFLY polynomial. Two more mathematicians, Józef H. Przytycki and Pawe? Traczyk, did independent work on the subject, and so it’s often called the HOMFLY-PT polynomial.

Like the Tutte polynomial, the HOMFLY polynomial is a polynomial in two variables. (The Jones polynomial, however, is just in one variable.) It can also be written as a homogeneous polynomial in three variables. We’ll take the 3-variable homogeneous version.

Strictly speaking, to get a HOMFLY polynomial, your knot must be oriented: it must have a direction. This is usually represented by an arrow along the knot.

HOMFLY polynomials also exist for links — a link is just a knot with many loops invovled. So even if there are several loops knotted up, they still have a HOMFLY polynomial. (Each loop needs to be oriented though.)

So, if you’re given an oriented knot or link \(K\), it has a HOMFLY polynomial. We’ll denote it by \(P_K (x,y,z)\). So how do you compute it? By following some rules which successively simplify the knot.

If the knot \(K\) is the unknot, then \(P_K (x,y,z) = 1\).

If you take one of the crossings in the diagram and alter it in the various ways shown below — but leave the rest of the knot unchanged — then you obtain three links \(L^+, L^-, L^0\). Their HOMFLY polynomials are related by

\(\displaystyle x P_{L^+} (x,y,z) + y P_{L^-} (x,y,z) + z P_{L^0} (x,y,z) = 0\).

A relationship like this, between three knots or links which differ only at a single crossing, is called a skein relation.

If you can move the link \(L\) around in 3-dimensional space to another link \(L’\), then this doesn’t change the HOMFLY polynomial: $latex P_L (x,y,z) = P_{L’} (x,y,z).

If the oriented link \(L\) is split, i.e. separates into two disjoint (untangled) sub-links \(L_1, L_2\), then you can take the HOMFLY polynomials of the two pieces separately, and multiply them, with an extra factor:

What is a connect sum? It’s when two knots or links are joined together by a pair of strands, as shown below.

And there you go.

Again, it’s not at all clear where these rules come from, or that they will always give the same result. There might be many ways to change the crossings and simplify the knot, but H and O and M and F and L and Y and P and T showed that in fact you do always obtain the same result for the polynomial.

Let’s see how to do this in a couple of examples.

First of all, for the unknot \(U\), by rule 1, its HOMFLY polynomial is \(P_U (x,y,z) = 1\).

Second, let’s consider two linked unknots as shown below. This is known as the Hopf link. Let’s call it \(H\).

Let’s orient both the loops so that they are anticlockwise. Pick one of the crossings and consider the three possibilities obtained by replacing it according to the skein relation described above, \(H^+, H^-, H^0\). You should find that \(H^+\) corresponds to the crossing as it is shown, so \(H^+ = H\). Changing the crossing results in two unlinked rings, that is, \(H^- =\) two split unknots. By rule 4 above then, \(P_{H^-} (x,y,z) = \frac{-(x+y)}{z} P_U (x,y,z) P_U (x,y,z)\); and as each unknot has HOMFLY polynomial \(1\), we obtain \(P_{H^-} (x,y,z) = \frac{-(x+y)}{z}\). On the other hand, smoothing the crossing into \(H^0\) gives an unknot, so \(P_{H^0} (x,y,z) = P_{U} (x,y,z) = 1\).

Putting this together with the skein relation (rule 2), we obtain the equation

\(\displaystyle x P_{H^+} (x,y,z) + y P_{H^-} (x,y,z) + z P_{H^0} (x,y,z) = 0\),

which gives

\(\displaystyle x P_H (x,y,z) + y \frac{-(x+y)}{z} + z = 0\)

and hence the HOMFLY of the Hopf link is found to be

In 1988, Francois Jaeger showed that the Tutte and HOMFLY polynomials are closely related.

Given a graph \(G\) drawn in the plane, it has a Tutte polynomial \(T_G (x,y)\), as we’ve seen.

But from such a \(G\), Jaeger considered a way to build an oriented link \(D(G)\). And moreover, he showed that the HOMFLY polynomial of \(D(G)\) is closely related to the Tutte polynomial of \(G\). In other words, \(T_G (x,y)\) and \(P_{D(G)} (x,y,z)\) are closely related.

But first, let’s see how to build an link from a graph. It’s called the median construction. Here’s what you do. Starting from your graph \(G\), which is drawn in the plane, you do the following.

Thicken \(G\) up. You can then think of it as a disc around each vertex, together with a band along each edge.

Along each edge of \(G\), there is now a band. Take each band, and put a full right-handed twist in it. You’ve now got a surface which is twisted up in 3-dimensional space.

Take the boundary of this surface. It’s a link. And this link is precisely \(D(G)\). (As it turns out, there’s also a natural way to put a direction on \(D(G)\), i.e. make it an oriented link.)

It’s easier to understand with a picture. Below we have a graph \(G\), and the link \(D(G)\) obtained from it.

A graph (source: wikimedia) and the link (source: Jaeger) obtained via the median construction.

Jaeger was able to show that in general, the Tutte polynomial \(T_G (x,y)\) and the HOMFLY polynomial \(P_{D(G)} (x,y,z)\) are related by the equation

where \(V(G)\) denotes the number of vertices of \(G\), and \(E(G)\) denotes the number of edges of \(G\). Essentially, Jaeger showed that the process you can use to simplify the link \(D(G)\) to calculate the HOMFLY polynomial, corresponds in a precise way to the process you can use to simplify the graph \(G\) to calculate the Tutte polynomial.

In addition to this excellent correspondence — Tutte meeting HOMFLY — Jaeger was able to deduce some further consequences.

He showed that the four colour theorem is equivalent to a fact about HOMFLY polynomials: for every loopless connected plane graph \(G\), \(P_{D(G)} (3,1,2) \neq 0\).

Moreover, since colouring problems for plane graphs are known to be very hard, in terms of computational complexity — NP-hard — it follows that the computation of the HOMFLY polynomial is also NP hard.

Said another way: if you could find a way to compute the HOMFLY polynomial of a link in polynomial time, you would prove that \(P = NP\) and claim yourself a Millennium prize!

Abstract: This article is an exposition of a body of existing results, together with an announcement of recent results. We discuss a theory of polytopes associated to bipartite graphs and trinities, developed by Kálmán, Postnikov and others. This theory exhibits a variety of interesting duality and triality relations, and extends into knot theory, 3-manifold topology and Floer homology. In recent joint work with Kálmán, we extend this story into contact topology and contact invariants in sutured Floer homology.

Here we are, in the year 2017. With now 25 years of climate-change international agreements behind us, here we are still trying to build oil pipelines and coal mines.

It is sad. Sad for humanity.

It is no longer a question of reducing the speed at which we are approaching the cliff. It is now a question of counting the metres to the cliff, as it approaches so fast. It is no longer a question of reducing climate emissions to a reasonable level. It is now a question of counting the remaining tons which may be emitted, budgeting them carefully and switching off them with an emergency.

There are various different ways the budget can be calculated. The MCC Carbon Clock calculates that to limit increase in global average temperature to 2 degrees Celsius, the CO2 budget remaining is 734 gigatonnes, on a moderate (neither optimistic nor pessimistic) set of assumptions. At the current rate of emissions, that budget will be exhausted by 2035. That is time at which, continuing as we are now, scientific laws predict failure.

But there is a strong argument that a 2 degrees Celsius increase is too much. It means a vast range of climate impacts – for instance, at 2 degrees tropical coral reefs do not stand a chance. A limit of 1.5 degrees increase is an altogether better goal. Indeed, the Paris agreement aims to hold increase in global average temperature to 2 degrees Celsius, but “to pursue efforts” to limit the increase to 1.5 degrees Celsius. And the MCC Carbon Clock, under the same set of assumptions, calculates the remaining CO2 budget, to limit the increase to 1.5 degrees Celsius, as 41.3 gigatonnes. At the current rate, this budget will be exhausted in September 2018 — in just over a year’s time.

One year. Just one year.

Either way, it is a clear and present danger, urgent, all-absorbing, putting all other tumults to silence. All efforts must be to get off fossil fuels immediately, now, yesterday.

Yet where are we in Australia? We are about to build our biggest coal mine ever.

Adani, corrupt, lawbreaking Adani. They still want to build their Carmichael mine in the Galilee Basin in Queensland.

And Australian governments still fall over themselves to assist them. Approvals and re-approvals flow from the federal Liberal government. The Queensland Labor premier’s interventions have convinced Adani to go ahead. The total emissions of the Carmichael project — producing and burning the coal – will be 4.7 gigatonnes of CO2. That’s over 10% of the remaining budget for 1.5 degree increase. Just this one mine.

The project is itself barely financially viable. Adani says a special loan from the Northern Australian Infrastructure Facility (NAIF) is critical to their financing. Nonetheless contracts were announced in July. They say it will employ 10,000 people: the reality, as given by Adani’s own expert under oath, is closer to 1,500.

Like everything else in Australia, the mine would be built on Aboriginal land. The traditional owners, the Wangan and Jagalingou people, released a statement: Stop Adani destroying our land and culture.

If the Carmichael mine were to proceed it would tear the heart out of the land. The scale of this mine means it would have devastating impacts on our native title, ancestral lands and waters, our totemic plants and animals, and our environmental and cultural heritage. It would pollute and drain billions of litres of groundwater, and obliterate important springs systems. It would potentially wipe out threatened and endangered species. It would literally leave a huge black hole, monumental in proportions, where there were once our homelands. These effects are irreversible. Our land will be “disappeared”.

Just like the Keystone XL and Dakota Access pipelines in the US, which have seen such inspiring resistance, if the Adani Carmichael mine is built it will be game over for the climate.

It cannot go ahead. It must not.

Adani continues to acquire property along its proposed rail corridor, even as new accusations of fraud emerge against them. But largely they are currently playing a waiting game. The minister responsible for NAIF, Matt Canavan, stepped down over the citizenship farce; and his replacement is Barnaby Joyce. Until the High Court rules, and possibly byelections are held, it may wait.

On April 27, 2017, a hapless cow wandered off-course during a seasonal cattle drive in the Democratic Republic of the Congo, and ended up over the campfire of some Indigenous hunters. The traditional lands of these groups (Batwa and related groups) are routinely trampled by cattle, cut for old-growth timber, or grabbed for mineral resources including diamonds and coltan — generally illegally. As their wild game diminishes from these impacts, the Batwa have come to view cattle as fair game.

The cattle herders followed their cow’s tracks, and upon learning her fate, agreed to share the meat with the Batwa. But when they returned to their village, a local self-appointed “defense militia” was infuriated, returning to kill and mutilate eight of the Batwa.

The global economy’s demand for hard-to-obtain minerals and tropical timber, coupled with a long history of contempt and exploitation by neighboring tribes, have made these Batwa hunter-gatherers easy targets for land grabs and violence. Specifically targeted during a massive regional conflict to gain control over resources, in the early 2000s, an estimated 70,000 Batwa were tortured, killed and even cannibalized in northeastern Democratic Republic of the Congo (DRC), according to American University’s Inventory of Conflict and Environment Case Studies.

There is only one word for the attempted eradication of an entire group of people through the wholesale slaughter of men, women and children, whatever the reason. That word is genocide.

The conflict is now heating up again, this time in southeastern DRC. Since September 2016, volunteer investigators on the ground have been gathering names and numbers of Indigenous community members killed, injured, raped and displaced. These numbers, no doubt gross underestimates, show that well over 1,200 Batwa have been killed in the past 12 months — primarily in skirmishes with non-Indigenous neighboring communities intent on expanding their access to land and resources.

In one recent case, on July 4, 2017, a national online news source in DRC said that daylong clashes between Batwa and other ethnic groups were triggered after the Batwa killed two adversaries near the provincial capital of Kalemie. No casualty list was provided in the news article, but according to our sources, 189 Batwa people were killed that day, including men, women and children.

In the worst attack we have documented so far, on the night of January 13-14, 2017, there was a nighttime attack against the Batwa near a town called Moba. Six hundred Batwa people were slaughtered outright; at least 1,600 women and girls were brutally raped, and were being cared for using traditional medicines because there are no health centers. No pain-killers; no antibiotics; no urgently-needed surgeries; no forensic evidence; no psychological counseling. More than 40 of those women and girls had already died or were on the verge of death several days after the attack.

A desperately inadequate RFI news report on the event, translated from French, says, “On 13 January, clashes took place … 25 kilometers from the city of Moba. Four villages were partially or totally burned down and the population fled to Moba. In total, 24 people — four Bantus and twenty [Batwa] — lost their lives in one week.”

Is this destined to be an off-the-record genocide?

Knowledgeable sources on the ground say that neighboring tribes are intent on exterminating (yes, a dehumanizing term) the Indigenous people, and that the DRC government is determined to prevent word of this massacre from becoming known internationally. This is to be expected: President Joseph Kabila, who refuses to hold elections as required by DRC’s constitution, prefers to get rid of anything that stands in the way of enriching elites in his kleptocracy. Indigenous people’s traditional land rights are an impediment to uncontrolled resource extraction.

Less expected is the lack of forthright information by the UN’s peacekeeping force in DRC. The UN’s radio station in DRC routinely downplays these incidents, and fails to distinguish between deaths of Indigenous peoples and others. A July 11, 2017, article in IRIN, which reports on crises for the UN, left the dangerous misimpression that conflict and large-scale internal displacements of people in this region are instigated primarily by Indigenous Batwa militias. Without providing any objective breakdown of casualty statistics or detailed descriptions of incidents, the article presents, unchallenged, the anti-Batwa statements of individuals, primarily from the very tribal groups who are engaged in driving the Batwa off their lands.

This opacity is a major contributing factor to the ongoing crisis, providing cover for those looking to profit from the chaos. Local news sources fail to provide acceptable coverage, and international media are (rightly) afraid to send reporters in. The DRC government’s information cannot be trusted. UN investigators have been killed. Local journalists have been killed. Human rights advocates have been killed or barred from entering the country. International NGOs have sounded the alarm about conflicts and conflict minerals in the region, but only one organization has paid close attention to the genocide against the Indigenous Batwa. And on July 19, 2017, the UN announced plans to shut down five of its monitoring and peacekeeping bases in DRC, courtesy of the Trump administration’s refusal to meet US funding commitments.

There is, however, a way to obtain accurate and timely information on the situation: from the locals. My organization works with a network of local groups and individuals who are already on the ground and can tap into sources of information from the various ethnic communities and factions. Their cross-verified Field Reports provide one of the only current sources of insight into the devastation faced by the Batwa in eastern DRC.

With awareness comes the possibility of transformation. On January 16, 2017, just two days after the Moba massacre, delegates from organizations across the region convened along the shores of Lake Kivu to form a multi-ethnic coalition to defend the survival and rights of the Batwa people. With strong Batwa leadership, they developed a plan of action to monitor human rights violations and violent conflict, undertake legal interventions, launch a region-wide public awareness campaign on behalf of Indigenous rights, and implement genuine conflict resolution mechanisms (unlike the feeble government efforts led by Emmanuel Shadary, an internationally sanctioned human rights violator, which have failed to bring necessary issues and actors to the table).

We have a choice: we can either look away in horror, or we can take action to help stop the killing. If Congolese people of all ethnic backgrounds can join together to defend Indigenous rights, despite the horrendous civil and regional conflict of the past two decades, the least we in the international community can do is to back them up where we have influence. We need to educate ourselves and others, then support civil society efforts on the ground, demand that African Union and United Nations peacekeepers do their jobs, and block multinational resource extractive companies from providing financial incentives for genocide.

My colleagues in DRC end many of their communications with the exhortation, “Courage!” Let’s follow their lead.

In August 2017 I gave a talk on some of the mathematics of Maryam Mirzakhani, the great Iranian matheamtician, first female Fields Medallist. This was a Monash LunchMaths seminar.

The slides from my talk are available here (5.6 MB ppt).

I gave an outreach talk to secondary students at PLC about mathematics and mathematicians, talking about, among other things, topology, Maryam Mirzakhani, and billiards, in July 2017.

The slides from my talk are available here (8.5 MB pdf).

Today the Australian government announced a proposal to forcetech companies to provide government agencies with the contents of encrypted communications.

I don’t think any draft of proposed legislation exists yet — my understanding is that a bill will be introduced later in the year — but the most recent announcement today and the press conferences by Turnbull and Brandis essentially follow on from the G20 statement last week, which has a paragraph including such ideas.

Since there are no specifics, it’s hard to comment beyond generalities. But in general the whole proposal seems to me to be, to the extent it is not technically impossible or entirely misconceived, a threat to the privacy and safety of everyone.

The best thing to come out of the Turnbull’s press conference was that he said

The laws of mathematics are very commendable but the only laws that apply in Australia is the law of Australia.

I am very glad to see that Turnbull thinks mathematics is commendable. In this case, he should, for instance, take seriously the results of applying the laws of mathematics in climate models, which show just how dire the planetary climate situation is. He would be better advised to spend his precious days as Prime Minister bringing the laws of Australia into line with the laws of mathematics as applied to climate, than to try to fight the mathematics behind encryption by legislation.

I am afraid that, however commendable Turnbull thinks they are, the laws of mathematics simply cannot be avoided, whatever he thinks of them, and they cannot be legislated away. That’s the way the universe works.

You cannot legislate that messages sent by properly implemented end-to-end encryption be decrypted any more than you can legislate that pi is 3. Central results in cryptography show that properly implemented encryption schemes make decryption practically impossible. (This is putting aside potential futuristic technologies like quantum computers.)

So, in practice what this means is that the government wants to force tech companies to not implement end-to-end encryption properly, but to make some modification, whether by using a weakened implementation or malware or a backdoor of some sort, so that the government can access it. Such proposals by law enforcement and intelligence have a long and ignominious history going back to at least the 1990s and the Clipper Chip. Technical dificulties aside, the important point which has come out of all that history is that there is no way to make encryption subject to government-mandated decryption without making it vulnerable to other attacks as well. If encryption is weak enough that a conversation can be decrypted by someone other than the parties to the conversation, then it is weak enough to be decrypted by many others, hackers, other governments, and so on. If it is implemented through government-mandated malware, then anyone who gains access to that malware has similar power — and we have seen precisely this happen, for instance, with NSA malware and WannaCrypt attacks.

The government’s approach with the present proposal appears to be to transfer responsibility to tech companies. Rather than legislate government backdoors, they seem to want to legislate that the tech companies must do what they can to assist. They want to use the legal language of rendering “proportionate” and “reasonable” assistance. But breaking end-to-end encryption, or implementing backdoors, is not at all proportionate or reasonable. If a company makes such a change, then they no longer implement end-to-end encryption and the promises of privacy provided to their users are null and void. There is no proportionate way to break an algorithm which mathematically provides secure encryption. It is either secure, or it is not.

In recent years there has been a mass takeup of encrypted messaging by people around the world. End-to-end encryption has been implemented by many major technology companies. This is largely sparked by revelations of mass warrantless surveillance by the NSA, not only of individuals, but also of those very tech companies. People are right to be wary of their privacy.

The Australian authorities, I’m afraid, do not inspire a great deal of confidence. They have already been given draconian powers. Quite aside from other draconian laws which, for instance, criminalise government leaks and whistleblowing from within refugeedetention centres, metadata laws have come into effect. These metadata laws allow many government agencies, without any court warrant, to access the metadata of almost any Australian’s online activity. These agencies have been invested with great power, and yet even the mild protections for journalists have been violated, as we found out in April, when the Australian Federal Police admitted that a journalist’s data had been accessed. No charges were laid and no action was taken, so far as I’m aware, beyond the Federal Police holding a press conference. Given the approach the AFP takes to journalists — a class of people with special legal protections — one wonders what approach they take to ordinary citizens. How will they then treat whistleblowers, activists, and government critics?

Police and intelligence already have enormous powers of surveillance and monitoring. Terrorism, child pornography and sex trafficking are important issues, but these proposals are not the way to deal with them.