Back in 2015, I reported some progress on this difficult problem in plane geometry. I’m happy to report some more.

First, remember the story. A subset of the plane has **diameter 1** if the distance between any two points in this set is ≤ 1. A **universal covering** is a convex subset of the plane that can cover a translated, reflected and/or rotated version of every subset of the plane with diameter 1. In 1914, the famous mathematician Henri Lebesgue sent a letter to a fellow named Pál, challenging him to find the universal covering with the least area.

Pál worked on this problem, and 6 years later he published a paper on it. He found a very nice universal covering: a regular hexagon in which one can inscribe a circle of diameter 1. This has area

But he also found a universal covering with less area, by removing two triangles from this hexagon—for example, the triangles C_{1}C_{2}C_{3} and E_{1}E_{2}E_{3} here:

The resulting universal covering has area

In 1936, Sprague went on to prove that more area could be removed from another corner of Pál’s original hexagon, giving a universal covering of area

In 1992, Hansen took these reductions even further by removing two more pieces from Pál’s hexagon. Each piece is a thin sliver bounded by two straight lines and an arc. The first piece is tiny. The second is downright microscopic!

Hansen claimed the areas of these regions were 4 · 10^{-11} and 6 · 10^{-18}. This turned out to be wrong. The actual areas are 3.7507 · 10^{-11} and 8.4460 · 10^{-21}. The resulting universal covering had an area of

This tiny improvement over Sprague’s work led Klee and Wagon to write:

it does seem safe to guess that progress on [this problem], which has been painfully slow in the past, may be even more painfully slow in the future.

However, in 2015 Philip Gibbs found a way to remove about a million times more area than Hansen’s larger region: a whopping 2.233 · 10^{-5}. This gave a universal covering with area

Karine Bagdasaryan and I helped Gibbs write up a rigorous proof of this result, and we published it here:

• John Baez, Karine Bagdasaryan and Philip Gibbs,The Lebesgue universal

covering problem, *Journal of Computational Geometry* **6** (2015), 288–299.

Greg Egan played an instrumental role as well, catching various computational errors.

At the time Philip was sure he could remove even more area, at the expense of a more complicated proof. Since the proof was already quite complicated, we decided to stick with what we had.

But this week I met Philip at The philosophy and physics of Noether’s theorems, a wonderful workshop in London which deserves a full blog article of its own. It turns out that he has gone further: he claims to have found a vastly better universal covering, with area

This is an improvement of 2.178245 × 10^{-5} over our earlier work—roughly equal to our improvement over Hansen.

You can read his argument here:

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

I say ‘claims’ not because I doubt his result—he’s clearly a master at this kind of mathematics!—but because I haven’t checked it and it’s easy to make mistakes, for example mistakes in computing the areas of the shapes removed.

It seems we are closing in on the final result; however, Philip Gibbs believes there is still room for improvement, so I expect it will take at least a decade or two to solve this problem… unless, of course, some mathematicians start working on it full-time, which could speed things up considerably.

Suppose someone found an optimal universal covering — does anyone have a plausible scheme for proving it optimal?

People know how to get upper bounds using arguments like those constructed by the people listed in this post. People know how to get lower bounds by showing that any shape that contains all shapes of certain kinds must have at least some area. In theory these arguments could meet! In practice, they seem to be creeping closer and closer, but with a gap much bigger than the latest improvements.

The current upper bound, if Philip’s new paper is correct, is

This is roughly 0.00002 less than the previous upper bound.

On the other hand, the best known lower bound I know is due to Brass and Sharifi in 2005. They got a lower bound of

This is 0.0049 higher than the previous lower bound.

I think people haven’t put as much work into lower bounds, so I think the

mainreason for the gap is that the lower bounds aren’t big enough… not that the upper bounds are too big, though Philip is sure someone could bring them down with further work.I seem to recall proving by a rather abstract argument that the actual constant we’re closing in on

iseffectively computable. (I never wrote up this proof in full detail.) But the argument did not give a practical algorithm. So, the challenge is just getting a practical way to compute it.The most interesting thing about the Lebesgue universal covering problem, in my opinion, is that it’s an example of a

typeof geometry problem that’s easy to state but hard to solve, because we currently have no sophisticated tools for solving it.Setting a good lower bound is certainly much harder for this problem. One way to proceed is to make some assumption. For example, assume that the best cover is contained in a regular hexagon of unit width. Then any curve of constant width (or orbiform) can only fit in finitely many ways, so the problem becomes more tractable. If you can solve that, then you only have to prove the assumption to finish the job. Try proving that the best cover can be contained within a strip of unit width, then in a parallelogram, … Both parts of this approach are still too hard. Something more is needed.

For the laymen in the audience, what’s the motivation,

i.e., what’s the canonical example of a set of diameter 1 that is not covered by a circle of diameter 1?I don't know what's canonical, but the first example that I thought of is an equilateral triangle whose sides all have length 1.

Oops, I thought of that but confused the circle’s diameter with its radius.

Right, the equilateral triangle is the most obvious set of diameter 1 that doesn’t fit in the circle of diameter 1. From Part 1:

Part 1 then goes on to describe the effect of also considering a regular pentagon, which is the next really important shape.

Read the earlier articles in this series: Part 1, Part 2.

Thanks for bringing this back to life. It is worth adding links to the two posts where we discussed this on n-cat cafe.

https://golem.ph.utexas.edu/category/2015/02/lebesgues_universal_covering_p.html

https://golem.ph.utexas.edu/category/2015/02/computability_for_lebesgues_un.html

Warming to this theme there is the classical Kakeya needle problem. A plane set K is called a Kakeya set if a unit segment, usually referred to as the needle, can be continuously turned around in K so as to return to its original position with its ends reversed. The problem posed by Kakeya was to find a Kakeya set of minimum area. He apparently thought that the answer was the deltoid (three-cusped hypocycloid) with area . Besicovitch surprised everybody by showing that actually there exist Kakeya sets of arbitrarily small area. In fact it can be proved that given , there exists a simply connected Kakeya set of area less than contained in a circle of radius 1. F Cunningham, The American Mathematical Monthly, Vol. 78, No. 2 (Feb., 1971), pp. 114-129 contains the details. There is a good exposition in Steven Krantz’s “A Panorama of Harmonic Analysis” (pages 148-170) where he discusses the method of “sprouting” which looks a lot like what is going on with this problem in terms of technique. Just adding this in for those who may not be aware of it and who want to find out more about it.

Yes, you are right to put this in the same class of problem. See this nice Greg Egan animation from G+ https://plus.google.com/113086553300459368002/posts/Ab1LKAxpdDC

As usual Greg Egan has been here before! Very nice.

Since G+ is scheduled to disappear in 10 months, I’ll copy Greg’s post here:

It seems that in the first article, you’re searching for a convex subset of the plane that covers any shape of diameter 1 if you allow reflections, but here you seem to allow only translations and rotations. Why did you change the goal this way? Is there a reason to think that the two problems are the same or are not the same?

I think you got it backwards: I didn’t mention reflections in Part 1, but this article here says:

But you raise a very important point! I believe the two problems are not the same: if you allow yourself to reflect your sets of diameter 1, you can fit them in a convex set with smaller area. In the paper Gibbs wrote with Bagdasaryan and me, we really needed to allow reflections to obtain the shape we did. I believe Gibbs’ new paper also uses reflections.

I have tried to edit all 3 articles so they only mention the version that allows reflections, since that’s what we really consider. But both problems are interesting.

It’s also interesting to consider the version that doesn’t demand convexity. I discussed this alternative in Part 1.

It’s also interesting to look at the case where only translations are allowed.