Seven points split three ways

Three points, however many there are proved Radon’s theorem in the plane: any four points can be split into two groups whose convex hulls meet — either one point lies inside the triangle of the other three, or the four points pair off into two crossing segments. It named the next step as a debt. Replace two groups by $r$ groups, and ask how many points are needed before a split into $r$ groups with a common point is guaranteed. The answer is $(r - 1)(d + 1) + 1$ in $d$ dimensions, which in the plane is 4 for two groups, 7 for three and 10 for four. Helge Tverberg proved it in 1966.

The theorem belongs beside the earlier Borsuk–Ulam arguments because of how its strongest version is proved. One line that halves them both and as many cuts as colours used the Borsuk–Ulam theorem — a continuous map from a sphere to a space of lower dimension sends some pair of opposite points to the same place — to prove that something must exist. Tverberg’s theorem has a version in which the straight lines of the hulls are allowed to bend, and that version is proved by a theorem of exactly the Borsuk–Ulam kind, with the symmetry of swapping two opposite points replaced by the symmetry of rotating $r$ things. It works when $r$ is a prime or a power of one. It fails, as was discovered only in 2015, for every other $r$.

Seven points, three groups #

The first figure is one instance of the theorem. Seven points chosen at random in a square are split into three groups — here two pairs and a triple — and the convex hull of each group, the smallest convex region containing it, is drawn: two segments and a triangle. All three contain the ringed point, where the two segments cross inside the triangle.

Finding such a split is a search. Seven points can be divided into three non-empty groups in 301 ways, and for each the question is whether the three hulls have a point in common. In the plane that can be decided exactly by testing a short list of candidates: if three convex sets share a point, they share a corner of their common part, and every such corner is either one of the input points or a crossing of two hull edges from different groups. So the search computes each split’s hulls, lists the input points and the crossings of their edges, and checks each candidate against all three hulls. For the seven points in the figure, four of the 301 splits work.

The number 301 is itself a small count worth seeing. Each of the seven points can be given one of three labels in $3^7 = 2{,}187$ ways; removing the labellings that leave some label unused, by inclusion and exclusion, leaves $2{,}187 - 3 \cdot 2^7 + 3 = 1{,}806$; and since the three groups are not named, each split has been counted $3! = 6$ times, which leaves 301. For ten points in four groups the same reckoning gives 34,105, and the numbers grow so fast that exhaustive search, easy here, becomes hopeless within a few more points or groups.

Six points need a coincidence #

The number seven is exact, and the next figure shows why one fewer is not enough.

Six points split into three non-empty groups have only two shapes available: three pairs, whose hulls are three segments, or a triple, a pair and a single point, whose hulls are a triangle, a segment and a point. Three segments share a point only if three lines pass through one point; a single point lies in a segment only if it is exactly on the line. Both are coincidences, and points in general position — no three on a line, no three lines through a point — never produce them. Of six hundred random six-point sets, not one can be split. The right-hand panel builds the coincidence on purpose, three segments through a common point, and the split exists.

That is the content of the formula $(r - 1)(d + 1) + 1$. It is the number of points at which a split into $r$ groups with a common point stops needing luck. A common point of $r$ hulls in $d$ dimensions must satisfy $d$ equations for each of the $r - 1$ hulls after the first, and the groups’ points provide the freedom to satisfy them; below the threshold the count of freedoms falls short, and only special arrangements succeed. At the threshold the freedom is always enough, which is the theorem.

Every working split of one set #

The theorem guarantees one split. The seven points of the first figure have four, drawn side by side, and they are variations on one arrangement: the same central crossing, with the points shuffled among the groups in the ways that keep it inside every hull. Gerard Sierksma conjectured in 1979 that the number of such splits is always at least $((r - 1)!)^d$ for points in general position — for three groups in the plane, $(2!)^2 = 4$ — and, as the next figure shows, most random arrangements attain it exactly.

Four, over and over #

The conjecture can be tested on random sets, and the next figure tests it on three hundred.

Every one of the three hundred sets has at least four working splits, and 203 of them have exactly four — the conjectured minimum is not merely respected but met by most random arrangements. The largest count is seven. A typical set with exactly four looks like the one in the earlier figure: a single central crossing that the four splits share, with the remaining points distributed among the groups in the few ways that keep the crossing inside every hull. A sample cannot prove the conjecture even here, and the general case — any number of groups, any dimension — is open, and checking it is harder than it looks, because the number of splits grows enormously and the conjectured minimum grows with it.

For four groups the threshold is ten points, and the number of ways to split ten points into four non-empty groups is 34,105. The four random sets drawn have 46, 46, 44 and 40 working splits, all above Sierksma’s $(3!)^2 = 36$. The search that decides it is the same as before, run on four hulls at a time, and it finishes in well under a second; but the counts that would test the conjecture in higher dimensions or with more groups come from splitting tens or hundreds of points, where exhaustive search is out of reach.

A point deep inside every group #

A Tverberg point is more than a curiosity of convex geometry; it is a kind of median. If a point lies in the hulls of $r$ disjoint groups, then every half-plane containing that point contains at least one point of each group — a half-plane that missed a whole group would have to miss that group’s hull, and the hull contains the point. So every half-plane through a Tverberg point of an $r$-way split contains at least $r$ of the original points. Such a point is said to have depth at least $r$, and for seven points split three ways the common point has depth three: no line through it has fewer than three of the seven on either side.

That is the centerpoint theorem of three points, however many there are in a stronger form. A centerpoint of $n$ points in the plane is one of depth at least $n/3$; Tverberg’s theorem with $r$ about $n/3$ produces one directly, as the common point of a split into that many groups. Statisticians use the deepest such point as a two-dimensional median, a centre that a few wild points cannot drag away, and the existence of deep points in every dimension rests on exactly this theorem.

The theorem’s own proof is algebra #

Tverberg’s original proof was a careful argument about moving points continuously and watching the splits change. The proof most often given now is due to Karanbir Sarkaria in 1992 and is linear algebra from beginning to end. It lifts the $d$-dimensional points into a space of dimension $(r - 1)(d + 1)$ using vectors that encode which group each point might join, and observes that a common point of $r$ hulls in the original space is the same thing as the origin lying in a hull of the lifted points chosen one per original point. That second statement is the colourful version of Carathéodory’s theorem, Imre Bárány’s 1982 strengthening of the fact that a point inside a hull lies inside the hull of a few of its points.

So the straight-line theorem needs no topology at all, and the threshold is an algebraic fact: the colourful argument needs one colour class more than the dimension of the lifted space, and below the threshold there are not enough points to supply it. Topology enters only when the lines are allowed to bend, because then there is no linear structure to lift, and what remains is the symmetry of the configuration — which is where Borsuk–Ulam arguments live, and why the bent theorem depends on arithmetic properties of $r$ that the straight one never notices.

Bending the lines #

The convex hull of a group of points is the union of the simplices — points, segments, triangles — spanned by its members. Tverberg’s theorem therefore says something about a straight-line map: lay out a simplex with $(r - 1)(d + 1) + 1$ corners abstractly, send its corners to the given points of $d$-dimensional space and extend linearly, and some $r$ faces of the simplex with no corners in common are sent to sets that meet.

The topological Tverberg conjecture, proposed by Bárány in 1976, asks whether the same holds for every continuous map, not only straight-line ones: if the faces are allowed to bend and stretch as they are carried into space, must $r$ disjoint faces still meet? For $r = 2$ that is the topological Radon theorem, proved by Ervin Bajmóczy and Imre Bárány in 1979 directly from the Borsuk–Ulam theorem. The proof deserves to be stated, because it is the whole method.

Suppose the map had no two disjoint faces meeting. Consider the pairs of points, one on each of two disjoint faces, together with the difference of their images. Swapping the two points is a symmetry of order two, and it changes the sign of the difference. The space of such pairs can be shown to behave like a sphere for the purposes of the argument, and the difference is a map from it to $d$-dimensional space that respects the swap and never vanishes — which is exactly what a theorem of Borsuk–Ulam type forbids, for the same reason that two opposite points that agree twice must exist on any sphere of the right dimension. So two disjoint faces must meet.

Primes, and the powers of primes #

For $r$ groups the swap is replaced by the cyclic rotation of $r$ points, one on each of $r$ disjoint faces, and the argument needs a version of Borsuk–Ulam for that symmetry. Imre Bárány, Senya Shlosman and András Szűcs proved it in 1981 when $r$ is prime, where the rotation acts with no fixed points on anything that matters, and Murad Özaydin extended it in 1987 to powers of primes. For those $r$ the topological Tverberg theorem holds in every dimension.

For $r = 6$, $10$, $12$ and every other number that is not a prime power, the method gives nothing: a group of order six acting on a sphere does not obstruct maps the way a prime-order rotation does, and Özaydin showed that the obstruction the method relies on really vanishes. Whether the conjecture was nevertheless true for those $r$ stayed open for nearly thirty years. In 2014 Isaac Mabillard and Uli Wagner developed a way to remove intersections from maps of simplices in high dimensions, and in 2015 Florian Frick combined it with an earlier reduction to produce counterexamples: for every $r$ that is not a prime power there are continuous maps, in sufficiently high dimension, with no $r$ disjoint faces meeting. The straight-line theorem is true for every $r$; its bent version is true exactly when the symmetry behind the proof can do its work.

That is a striking pattern among these results. Every earlier one used a Borsuk–Ulam argument to prove that something exists, and in each case the existence was true for the simple reason the symmetry provided. Here the symmetry provides a proof for prime powers only, and the theorem turns out to need that symmetry: where the argument fails, the statement fails too.

The same symmetry, colouring graphs #

The argument that proves the topological Tverberg theorem for primes is the argument behind two earlier results of the same kind. The colours a circle forces proved Kneser’s conjecture with a Borsuk–Ulam argument on the sphere, and several colours on every vertex extended the counting with more colours per vertex. In each case a configuration is given a symmetry — the swap of antipodes, or the rotation of $r$ objects — and a map that respects the symmetry is shown to be impossible unless the desired structure exists. A combinatorial form of the same theorem, opposite labels that have to meet, replaces continuity by a labelling of a triangulated square, and it is the version a computer can check.

There is also a colourful Tverberg theorem, conjectured by Bárány and David Larman in 1992: colour the points with $d + 1$ colours, $r$ points of each, and ask for a split into $r$ groups each containing one point of every colour, with a common point. Rade Živaljević and Siniša Vrećica proved a weaker form with more points of each colour using the symmetry method, and Pavle Blagojević, Benjamin Matschke and Günter Ziegler proved the exact form in 2009 — when $r + 1$ is a prime. The same dependence on primes appears there, for the same reason, and the colourful conjecture for other $r$ is open.

What the searches do not show #

The searches decide Tverberg splits of particular point sets exactly, up to the tolerance used for points lying on hull edges, which matters only for constructed coincidences like the right-hand panel of the six-point figure. The random sets are in general position with probability one, and the counts are the true counts for those sets.

What a search cannot touch is the topological version, which is about continuous maps rather than point sets: a computer can test straight-line maps by the thousand and learn nothing about bent ones. And Frick’s counterexamples live in high dimensions — the first ones needed dimensions above three times the number of groups — so no picture in the plane can show a failure of the bent theorem. In the plane, and in three dimensions, whether the topological Tverberg statement holds for six groups is not known.

Still open: the count, and the low dimensions #

Sierksma’s conjecture, that the number of Tverberg splits is at least $((r - 1)!)^d$, is open in general. Lower bounds of the right shape are known when $r$ is a prime, through the same symmetry arguments, but they fall short of $((r - 1)!)^d$ by a large factor, and the conjecture itself has been proved only in a few small cases.

The topological Tverberg conjecture is now known to fail for non-prime-powers in high dimensions, and the threshold has been pushed down since 2015, but the smallest dimension in which it fails for a given $r$ is not known. For $r = 6$ the known counterexamples are in dimensions far above three, and whether a continuous map of a simplex into the plane, or into three-dimensional space, can avoid six disjoint faces meeting remains open — as does the question of whether the plane, where every curve separates and much of topology is easier, behaves like the prime-power case for every $r$.