Is Lebesgue's "universal covering" problem still open?

Question

The following problem has been attributed to Lebesgue. Let "set" denote any subset of the Euclidean plane. What is the greatest lower bound of the diameter of any set which contains a subset congruent to every set of diameter 1? There are a number of interesting geometric problems of this type. Is it possible that some of them may be difficult to solve because the solution is a real irrational number which (when expressed in decimal form) is not even recursive-and so cannot be approximated in the usual way?

Answer 1

The question is still open. There are at least two versions. The most popular asks for the minimal-area convex subset of the plane such that every set with diameter 1 can be translated, rotated and/or reflected to fit inside it. Here is the best lower bound I know:

• Peter Brass and Mehrbod Sharifi, A lower bound for Lebesgue's universal cover problem, Int. Jour. Comp. Geom. & Appl. 15 (2005), 537--544.

Their lower bound is 0.832, obtained through a rigorous computer-aided search for the convex set with the smallest area that contains a circle, equilateral triangle and pentagon of diameter 1.

The best upper bound I'm 100% sure of is 0.8441153, proved here:

• John Baez, Karine Bagdasaryan and Philip Gibbs, The Lebesgue universal covering problem, Jour. Comp. Geom. 16 (2015), 288-299; arXiv:1502.01251 .

Our paper also reviews the history of this problem, which is rather interesting.

In 1920, Pál noted that a regular hexagon of area circumscribed around the unit circle does the job. This has area

$$ \sqrt{3}/2 \approx 0.86602540 $$

But in the same paper, he showed you could safely cut off two corners of this hexagon, defined by fitting a dodecagon circumscribed around the unit circle inside the hexagon. This brought the upper bound down to

$$ 2 - 2/\sqrt{3} \approx 0.84529946 $$

He guessed this solution was optimal.

In 1936, Sprague sliced tiny pieces of Pal's proposed solution and bring the upper bound down to

$$ \sim 0.84413770 $$

        
        _{(Image from Hansen's paper, added by J.O'Rourke.)}

The big hexagon above is Pál's original solution. He then inscribed a regular dodecagon inside this, and showed that you can remove two of the resulting corners, say $B_1B_2B$ and $F_1F_2F,$ and get a smaller universal covering. But Sprague noticed that near $D$ you can also remove the part outside the circle with radius 1 centered at $B_1$, as well as the part outside the circle with radius 1 centered at $F_2.$

In 1975, Hansen showed you could slice off very tiny corners off Sprague's solution, each of which reduces the area by $6 \cdot 10^{-18}$.

In a later paper, Hansen did better:

• H. Hansen, Small universal covers for sets of unit diameter, Geometriae Dedicata 42 (1992), 205--213.

He again sliced two corners off Sprague's solution, but now one reduces the area by a whopping $4 \cdot 10^{-11}$, while the other, he claimed, reduces the area by $6 \cdot 10^{-18}$.

One author, in a parody of the usual optimistic prophecies of accelerating progress, commented that

...progress on this question, which has been painfully slow in the past, may be even more painfully slow in the future.

In 1980, Duff considered nonconvex subsets of the plane with least area such that every set with diameter one can be rotated and translated to fit inside it. He found one with area

$$ \sim 0.84413570 $$

which is smaller than the best known convex solution:

• G. F. D. Duff, A smaller universal cover for sets of unit diameter, C. R. Math. Acad. Sci. 2 (1980), 37--42.

In 2015, Philip Gibbs, Karine Bagdasaryan and I wrote a paper on this topic, mentioned above. We found a new smaller universal cover, and noticed that Hansen had made a mistake in his 1992 paper.

Hansen claimed to have removed pieces of area $4\cdot 10^{-11}$ and $6 \cdot 10^{-18}$ from Sprague's universal cover, but the actual areas removed were $3.7507 \cdot 10^{-11}$ and $8.4460 \cdot 10^{-21}$. So, Hansen's universal covering has area

$$ \sim 0.844137708416 $$

Our new, smaller universal covering had area

$$ \sim 0.8441153 $$

This is about $2.2 \cdot 10^{-5}$ smaller than Hansen's.

To calculate the area of our universal cover Philip used a Java program, which is available online. Greg Egan checked our work using high-precision calculations in Mathematica, which are also available online. See the references in our paper for these programs and also a Java applet that Gibbs created to visualize Hansen's universal covering. It's fun to look at the smallest sliver Hansen removed, because it's 30 million times longer that it is wide!

More recently Philip Gibbs wrote a paper claiming to have an even smaller universal covering, with area

$$ \sim 0.8440935944 $$

• Philip Gibbs, An upper bound for Lebesgue’s universal covering problem, 22 January 2018.

Gibbs is a master at this line of work, but I must admit I haven't checked all the details, so it would be good for some people to carefully check them.

I've written a slightly more detailed account of the Lebesgue universal covering problem with some pictures here:

• J. Baez, Lebesgue's universal covering problem (part 1), Azimuth, 8 December 2013.

• J. Baez, Lebesgue's universal covering problem (part 2), Azimuth, 3 February 2015.

• J. Baez, Lebesgue's universal covering problem (part 3), Azimuth, 7 October 2018.

If anyone knows of further progress on this puzzle, please let me know!

Answer 2

The problem has been studied for various groups $G$ of isometries of $\mathbb R^n$. A set $K\subset \mathbb R^n$ is called $G$-universal cover iff every set of diameter 1 is contained in $gK$ for some $g\in G$.

V. Makeev proved that the mean width of a $T_n$-universal cover is greater or equal to $\sqrt{2n/(2n+1)}$, where $T_n$ is the group of translations of $\mathbb R^n$. For $n=2$ the estimate is sharp; the perimeter of a $T_2$-universal cover $\geq 2\pi/\sqrt{3}$ (link).

M. Kovalev obtained a rather explicit description of all minimal $D_2$-universal covers, where $D_2$ is the group of all isometries of $\mathbb R^2$.

Theorem. Every minimal universal $D_2$-cover $K$ is star-shaped. There is a polar coordinate system (with the centre in $K$) such that $$\partial K=\{(\phi,\rho(\phi)):\ 0 < \phi\leq 2\pi\},$$ where $\rho=\rho(\phi)$ is Lipschitz and for any $\phi\in[0,2\pi]$ $$c^2\leq \rho(\phi) \leq 1 - c^2,\qquad c=1-1/\sqrt{3}.$$

Answer 3

It's Lebesgue Minimal Problem. It's still open, though there are some bounds to the area of such set, for example there are lower bound for area $S\ge \frac{\pi}{8}+\frac{\sqrt{3}}{4}$

it's not hard to show that such set must have diameter larger or equal to $\frac{\sqrt{3}}{3}+\frac{1}{2}=1.077350...$

Our set must have a subsets congruent to the equilateral triangle with side 1(ABC) and to the circle with radius 0.5(with center O). If I - the incenter of triangle ABC, and $O \in BIC$, then consider point D which lies on the radius perpendicular to BC. Then $AD \ge AI+OD=1.077...$.

Answer 4

As other answers have pointed out there are different versions and generalizations of Lebesgue's Universal Covering Problem. His original question from 1914 in a letter to Pál has been quoted as

"What is the smallest area of a convex set in the plane that contains a congruent copy of every planar set of unit diameter?" (see "Research Problems in Discrete Geometry" Brass, Moser, Pach.)

Variations of the question ask for the minimum diameter or perimeter. Sometimes the convexity condition is relaxed but an advantage of the convex case is that the existance of a universal cover with minimum area is then ensured by the Blaschke selection theorem. Congruence allows reflections as well as translations and rotations but in some statements of the problem reflections are not allowed. The universal covers found by Pál and improved by Sprague do not require reflections. The best known convex universal cover by Hansen from 1992 does require reflections. Hansen's area is 0.844137708435197570894066994 and Duff gave a smaller non-convex cover of 0.84413570 (see other answers for references)

However, it is possible to improve on these upper bounds as follows: Start with a regular hexagon circumscribed round a circle of diameter one. As Pál showed this is a universal cover. Pál considered the eight sided shape formed by removing two corners from this hexagon using cuts made with two lines tangent to the circle in such a way that the new edges are sides of a regular dodecagon inscribed in the hexagon. Now consider a more general case where the two cuts are still tangent to the circle and still at an angle of 60 degrees to each other but at a small angle $\sigma$ to the edges of a dodecahedron. The remaining shape is still a universal cover.

To see this consider the six triangles at the corners of the hexagon each outisde a line tangent to the circle and at the same slant angle away from the edge of a regualar dodecagon. In the diagram these are labelled A,B,C,D,E and F. Any shape of diameter one can be fitted inside the hexagon. The least distance between opposite triangles such as A and D is one, so the shape cannot be in the interior of both triangles. This is true for each of the three pairs of opposite triangles so the shape can only be inside the interior of at most three of these triangles. Each of the possible cases can be checked to see that the shape can then be rotated through some multiple of sixty degrees around the centre so that it is still inside the hexagon but not inside the triangles E and C. Therefore the hexagon with these two triangles removed is a universal cover.

This cover can be reduced further by generalising the argument used by Sprague. First observe that any shape of diameter one can be contained inside a curve of constant width one (such as a cirle of unit diameter, or a Reuleaux polygon) so to prove that a set of points is a universal cover it suffices to show that it can cover a set congruent to every curve of constant width one. When such a curve is fitted inside the hexagon it will touch each of the six sides of the hexagon at a unique point. On the side running from D to C it must be to the left of the point P on the corner of the removed triangle C. This means that all points near A outside an arc of radius one centred on P can be removed. Similarly the curve must touch the edge of the hexagon from E to D somewhere right of N, the corner of the triangle E that has been removed. So all points outside an arc of radius one centred on N can also be removed. The remaining cover then has a vertex at X where these two arcs meet. This reduces the cover but not enough to make it smaller for any non-zero value of $\sigma$ than Sprague's universal cover which is the case $\sigma=0$.

One more piece can be removed if we use the freedom to reflect shapes. The axis of reflection to use is the line from the midpoint M of the side of the hexagon from E to D, to the midpoint of the opposite side. A shape fitted into the hexagon with the corners E and C removed can be reflected about this axis provided it also does not enter the triangles F' and D' which are the reflections of C and E about the axis. When this is the case we will choose to reflect the shape if it touches the side from E to D at a point nearer to E than D. Remember that it touches the opposite side at the opposite point which is therefore also reflected to be nearer the corner of the hexagon at B than the one at A. If we draw an arc centred on M of radius one it cuts off a larger region near A and no shape that can be reflected can be beyond this line. The point where this meets the arc centred on P is marked W.

This means that the only shapes that can have points outside that arc are ones that cannot be reflected. This means they must enter some point inside the regions F' or D' If they have a point in D' then they cannot have a point in A' which is the triangle whose points are at a distance of more than one from all points in D'. Draw one more arc centred on Q at the corner of the triangle C' which is the reflection of the region F. All points in C' are at a distance of one or more than one from points in F' so the arc will touch the region F' but not enter it. This arc will meet the arc centred on M at a point Z and the arc centred on N at a point Y. Now consider the fate of points inside the region XYZW bounded by the four arcs. It is a general property of curves of constant width one that if two points are inside the curve then all points on an arc of radius one through the two points are also inside the curve. Suppose then that a shape fitted inside the hexagon had a point in XYZW and also in F' We could then join those two points with an arc but between the two points it would be outside the arc centered on Q and would therefore go outside the hexagon. This is in contradiction with the premise so we conclude that no shape fitted in the hexagon can have a point in both XYZW and F'. It can also be verified that for angles $\sigma$ less than 9 degrees the region XYZW is inside the triangle A'. Therefore shapes with a point insode XYZW do not have points in F' or D' and can be reflected. However, we have already determined that such shapes will not have points in this region. This proves that the region XYZW can be removed from the universal cover.

It turns out that this is now sufficient to construct a universal cover smaller than the ones of Hansen and Duff. Even if we restrict ourselves to the convex case and remove only the part of this region that leaves a convex shape, the area of the universal cover for an angle $\sigma = 0.4$ degrees can be computed to be 0.8441177

There are other small pieces that can be removed from this cover to reduce it further.

This of course does not solve Lebesgue's Universal Covering Problem which is hard because of the complexity of the problem (not because the numbers involved are irrational as asked in the question) However I can break the problem down with three conjectures

1st conjecture: The minimal convex cover for any subset of curves of width one will always fit inside a hexagon circumscribed around a circle such that opposite sides are parallel. It can be shown that such a shape is a universal cover but only computational evidence supports the truth of this conjecture.

2nd conjecture: For any such hexagon there is a minimal convex cover. The conjecture is that the minimum area for such a cover is found for the case of the regular hexagon. Again computation supports this conjecture.

3rd conjecture: For a regular hexagon the minimum cover within the hexagon for any subset of curves of width one fits inside the shape formed by removing two corners by two lines tangent to the inscribed circle and at an angle of 60 degrees to each other (as above)

If all of these three conjectures are true then the problem of finding the minimal convex cover reduces to finding the minimal cover inside a shape of this form. The conjectures may be hard to prove but if are true then the final problem may be tractable using methods similar to the above proof.

Answer 5

Philip Gibbs wrote:

the area of the universal cover for an angle $\sigma=0.4$ degrees can be computed to be $0.8441177$.

I believe Philip later noticed an error in this area computation. He also later noticed that there's a constraint that $\sigma$ needs to obey, which is not obeyed by this choice: the best choice of $\sigma$ is about

$$ \sigma = 1.294389444703601012^\circ $$

and the area of the universal covering this gives is about

$$ 0.844115297128419059\dots .$$

We wrote a paper on this together with Karine Bagdasaryan, and Greg Egan did some high-precision calculations that give the above numbers. Our paper explains the details:

• John C. Baez, Karine Bagdasaryan and Philip Gibbs, The Lebesgue universal covering problem.

Abstract: In 1914 Lebesgue defined a "universal covering" to be a convex subset of the plane that contains an isometric copy of any subset of diameter 1. His challenge of finding a universal covering with the least possible area has been addressed by various mathematicians: Pal, Sprague and Hansen have each created a smaller universal covering by removing regions from those known before. However, Hansen's last reduction was microsopic: he claimed to remove an area of $6 \cdot 10^{−18}$, but we show that he actually removed an area of just $8 \cdot 10^{-21}$. In the following, with the help of Greg Egan, we find a new, smaller universal covering with area less than $0.8441153$. This reduces the area of the previous best universal covering by a whopping $2.2 \cdot 10^{−5}$.