How many pieces to shrink a shape

The diameter of a shape is its greatest width: the largest distance between two of its points. A disc of radius one has diameter 2. Cut the disc into pieces, and the question is how many pieces it takes before every piece is strictly narrower than the whole.

Two are not enough. Cut along a diameter and each half still contains that diameter. Cut in any other way, with any wiggling boundary, and the answer is the same: one of the two pieces contains two opposite points of the rim, so it is still 2 wide. Three are enough. Three sectors of 120° each have a greatest width equal to the chord across the sector, $\sqrt3$, about 0.866 of the diameter.

Karol Borsuk asked in 1933 whether that pattern holds in general: can every bounded set in $d$ dimensions be split into $d + 1$ pieces, each of smaller diameter than the set? The question appeared in the same paper as the antipodal theorem that bears his name, and for a reason. The theorem is what shows that $d + 1$ is the least that could work. Borsuk’s question was whether it is also always enough, and the answer turned out to be one of the cleanest examples in mathematics of a pattern holding in every dimension anyone could picture and failing far beyond them.

Why two pieces of a disc fail #

The claim that every split of a disc into two pieces leaves one of them 2 wide is the antipodal theorem in its smallest form, and the argument is short enough to give whole.

Take the two pieces and look only at the rim. Each point of the rim lies in one piece or the other, and points on a boundary between them lie in both, since the pieces are closed. Suppose no piece contained a pair of opposite points. Then every point of the first piece would have its opposite in the second, and every point of the second its opposite in the first. Now take a point where the two pieces meet. It lies in both, so its opposite would have to lie in the second piece and in the first, and then the opposite point and its own opposite — the starting point — would be a pair inside one piece. The supposition fails.

The figure shows one such division, in which the rim is cut ten times and the arcs are given alternately to two sets. 68% of opposite pairs fall into one set, and the marked pair is the one farthest from any cut. A more careful division only makes the opposite pairs rarer; it cannot remove them. The same argument, run with the intermediate value theorem in place of the boundary point, is what halved two shapes with one line in the simplest of these theorems.

Pieces that are not closed can do better, and that is why the question is posed for diameter rather than for some cruder measure. A half-open split of the circle, with each point’s opposite always in the other set, exists. But the diameter of a set equals the diameter of its closure, so closing the pieces costs nothing, and once they are closed the argument applies.

The plane needs three and three suffice #

For every bounded set in the plane, three pieces of smaller diameter are enough; Borsuk proved that himself. More precisely, any plane set of diameter one can be split into three pieces of diameter at most $\sqrt3/2$, and the disc shows that this cannot be improved.

The proof is a geometric construction. A set of diameter one fits between two parallel lines one apart in every direction, and three such pairs of lines at 60° to one another enclose it in a hexagon. A theorem of Julius Pál from 1920 says the directions can be chosen so that the hexagon is regular, with opposite sides one apart. Three segments from the hexagon’s centre to the midpoints of alternate sides then cut it into three congruent pentagons, and each pentagon’s greatest width is $\sqrt3/2$. Whatever the set was, its three pieces inside the three pentagons are no wider than that.

Finite sets are where the question becomes combinatorial. Join two points of a finite set when they are at exactly the set’s diameter, and call the result the diameter graph. A piece has smaller diameter than the whole precisely when it contains no joined pair, so the number of pieces needed is the number of colours needed to colour the diameter graph — the same object the colours a circle forces studied for a different graph.

For a regular pentagon the diameter pairs are its five diagonals, which form a five-pointed star: a single cycle of odd length, which cannot be coloured with two colours, so the pentagon needs three pieces. A regular hexagon’s diameter pairs are its three long diagonals, which share no corners, and two colours do. A regular heptagon is like the pentagon, a seven-pointed star needing three. Nine points scattered at random usually have a single pair at the greatest distance, and two pieces suffice. In the plane the diameter graph of $n$ points has at most $n$ edges and never needs more than three colours, which is the finite form of Borsuk’s theorem.

The ball in space needs four #

In three dimensions the antipodal theorem says that if the sphere is covered by three closed sets, one of them contains a pair of opposite points. That is the case of the theorem that found two opposite points agreeing in temperature and pressure, turned into a statement about covers, and it means that a solid ball cut into three pieces leaves one of them a full diameter wide.

The figure divides a sphere into three sets by comparing three smooth random scores and giving each point to the largest. A search over a fine grid of points finds pairs of opposite points with the same winner, and marks the one where the winning score leads most clearly at both ends. The three sets were not designed to fail; no three sets can do otherwise.

Four pieces do succeed, and the natural way to cut is by a regular tetrahedron. Place one inside the ball with its corners on the sphere, and give each point of the sphere to the corner nearest it. The four regions are curved triangles, and cutting the ball along cones from the centre to their edges gives four solid pieces.

Each piece’s greatest width runs from one corner of its curved triangle to the middle of the opposite edge, and it measures 1.7761, against the ball’s 2. That number is $2\sqrt{(3 + \sqrt3)/6}$, and the computation behind the figure finds it by measuring every pair of points along the regions’ edges. It is about 0.888 of the diameter, a smaller saving than the disc’s 0.866.

Shapes as wide in every direction #

The ball is not the only shape in which every point has a partner at the full distance. A Reuleaux triangle — three circular arcs, each centred on the opposite corner — is as wide in every direction as it is in any one, and so is every shape of constant width. The longest fence of diameter one met these shapes as the polygons with the most perimeter: Barbier’s theorem gives every plane shape of constant width one the same perimeter, $\pi$, the disc’s.

They matter here because of a reduction that turns Borsuk’s question into a question about them alone. Every set of diameter one can be enlarged to a set of constant width one without increasing its diameter: keep adding points that are within one of everything already there, and what remains when nothing more can be added is as wide in every direction as the diameter. Pieces of the enlarged set that are narrower than one give pieces of the original that are narrower than one. So if every shape of constant width in $d$ dimensions can be cut into $d + 1$ narrower pieces, the conjecture is true there.

A Reuleaux triangle needs three pieces, like the disc, and three suffice, since it is a plane set. In three dimensions the constant-width bodies are far more varied, and the proof that four pieces always suffice has to handle all of them; that is part of why the three-dimensional case took two decades longer than the plane. The reduction also explains where a counterexample would have to look. A shape of constant width has a great many diameter pairs, and the question becomes whether those pairs can be arranged so densely that no small number of narrower pieces avoids them all.

Borsuk’s question in three dimensions, for every bounded set and not just the ball, was settled in the 1940s and 1950s: four pieces always suffice. By then the pattern had held in dimensions one, two and three, and every ball in every dimension needed exactly $d + 1$ pieces. The natural guess was that the ball is the hardest case, as it is for so many questions about width.

A finite set that needs more pieces #

The guess was refuted by Jeff Kahn and Gil Kalai in 1993, and the refutation used finite sets, so that it was a colouring problem from the start. The construction begins with sign patterns: strings of $n$ entries, each $+1$ or $-1$, where $n$ is four times a prime. Take those that begin with $+1$ and contain an even number of entries equal to $-1$. There are $2^{n-2}$ of them.

Each pattern $x$ is turned into a point: the table of all products $x_i x_j$, which is a point in a space of $n(n-1)/2$ dimensions once the diagonal, which is always 1, is ignored. The distance between the points for $x$ and $y$ depends only on how many entries the patterns share: it is greatest exactly when the patterns agree in half their places and disagree in the other half, which is to say when $x$ and $y$ are orthogonal. So the diameter graph of the point set joins two patterns precisely when they are orthogonal, and a piece of smaller diameter is a family of patterns no two of which are orthogonal.

At $n = 8$ the set is small enough to examine completely. There are 64 patterns, standing for 64 points in 28 dimensions, and each is orthogonal to 35 of the others. An exhaustive search finds that the largest family with no orthogonal pair has exactly 8 members, so the points need at least 8 pieces, and the figure shows a split into exactly 8. That is far from the 29 that Borsuk’s conjecture allows in 28 dimensions. The small case is consistent with the conjecture, and gives no warning.

The count that overtakes the dimension #

What makes the construction work is a theorem of Peter Frankl and Richard Wilson from 1981. For $n = 4p$ with $p$ prime, a family of these sign patterns with no orthogonal pair has at most

$$\sum_{i=0}^{p-1} \binom{n-1}{i}$$

members. At $n = 8$ that is $1 + 7 = 8$, exactly the size the exhaustive search found. Why orthogonality should be hard to avoid is clearer once the patterns are compared by counting disagreements. Two patterns of length $n$ that disagree in $k$ places have inner product $n - 2k$, so they are orthogonal exactly when they disagree in $n/2 = 2p$ places. Because every pattern has an even number of entries equal to $-1$, any two disagree in an even number of places, and a family with no orthogonal pair is a family in which a single even distance, $2p$, never occurs. Forbidding one distance out of about $2p$ possible ones sounds like a mild restriction. The theorem says it is drastic: the family shrinks from $2^{n-2}$ members to at most the number of subsets of fewer than $p$ things from $n - 1$, which is exponentially smaller. The proof works with the patterns as polynomials modulo $p$, and its point is that families avoiding orthogonality must be exponentially smaller than the whole set.

Dividing the number of patterns by the largest family size gives a lower bound on the pieces needed, and the figure sets it against the dimension plus one. At $n = 28$ the bound forces 169 pieces in 378 dimensions, well within the 379 allowed. At $n = 44$ it forces 1,650 pieces in 946 dimensions, against 947 allowed, and the conjecture is false. The forced number grows exponentially in $n$ and the allowed number only like $n^2$, so once the first overtakes the second it never falls back.

Kahn and Kalai’s original paper put the first counterexample in dimension 1,325, using $n = 52$, and showed the conjecture fails in every dimension from 2,015 on; the slightly sharper count drawn here, with $n = 44$, was published the following year and gives 946. Since then the dimension has fallen by other constructions, to 298 in 2003, to 65 in 2013, and to 64 in 2014, by Thomas Jenrich and Andries Brouwer. The conjecture is true in dimensions up to three and false from 64 up; between them, from four to 63, nobody knows. Not even dimension four is settled, and no one has a candidate shape there. A counterexample in low dimension would need a set whose diameter graph is dense enough to need six colours in four dimensions, and the known constructions all reach density by sheer size — many coordinates, many points, many pairs at the full distance. Whether the true threshold is near four or near sixty-four is open in both directions: a proof for dimension four would need tools beyond the reduction to constant width, and a counterexample would need a construction unlike any known.

What the antipodal theorem did and did not say #

The antipodal theorem’s contribution to Borsuk’s question is the lower bound, and it is exact: a ball in $d$ dimensions needs $d + 1$ pieces, because a cover of its bounding sphere by $d$ closed sets always puts two opposite points in one set. The same theorem has appeared in many other costumes — as many cuts as colours for a stolen necklace, several colours on every vertex for Kneser’s graphs, seven points split three ways for Tverberg’s partitions, and the halving lines of a scattered set of points — and in each the theorem forced something to exist.

Borsuk’s question asked it to do more: to identify the ball as the worst case. A ball is the shape whose every point has an opposite at full distance, so it is natural to think it holds the most diameter pairs and needs the most pieces. The Kahn–Kalai points show the opposite intuition is right in high dimensions. A ball’s diameter pairs are perfectly matched, each point with one opposite, while a cleverly chosen finite set can have each point at the full distance from many of the others — at length eight, from 35 of the other 63 — forming a diameter graph so dense that only small families avoid it. The topological bound sees only the matching. The combinatorial construction exploits the density.

The same tension appears in the problem of colouring the plane, where a graph of points at unit distance needs at least five colours and the best known upper bound is seven, and in the largest polygon of diameter one, where the regular shape wins for odd numbers of sides and loses for even ones. Diameter is a simple notion, and its extreme cases are not always the symmetric ones.

Small dimensions lie #

The conjecture held for a ball in every dimension, for every set in dimensions one to three, for every finite set anyone examined by hand, and for the sign-pattern points themselves at every length below 44. The 64 points at length eight need 8 pieces where 29 are allowed; at length 28 they need 169 where 379 are allowed. In every case where a person could look, the conjecture had room to spare.

What changed between length 28 and length 44 is not the geometry but the arithmetic: an exponential overtaking a square. Nothing about the small cases hints that the gap will close, and when it closes it closes for good. The number of pieces needed in the worst case is now known to grow at least exponentially in the square root of the dimension, where Borsuk guessed it grew by one with each dimension.

The ball still needs exactly $d + 1$ pieces in every dimension, and the antipodal theorem still proves it. That part of Borsuk’s 1933 paper stands. The part that fell was the guess that the ball, with its perfect symmetry and its sphere of opposite pairs, was the shape that made cutting hardest.