A while back I described a century-old geometry problem posed by the famous French mathematician Lebesgue, inventor of our modern theory of areas and volumes.
This problem is famously difficult. So I’m happy to report some progress:
• John Baez, Karine Bagdasaryan and Philip Gibbs, The Lebesgue universal covering problem, Journal of Computational Geometry 6 (2015), 288–299.
As far as the math goes, it’s just high-school geometry. But it’s carried to a fanatical level of intensity, which makes it pretty interesting.
Here’s the story:
A subset of the plane has diameter 1 if the distance between any two points in this set is ≤ 1. You know what a circle of diameter 1 looks like. But an equilateral triangle with edges of length 1 also has diameter 1:
After all, two points in this triangle are farthest apart when they’re at two corners.
Note that this triangle doesn’t fit inside a circle of diameter 1:
There are lots of sets of diameter 1, so it’s interesting to look for a set that can contain them all.
In 1914, the famous mathematician Henri Lebesgue sent a letter to a pal named Pál. And in this letter he challenged Pál to find the convex set with smallest possible area such that every set of diameter 1 fits inside.
More precisely, he defined a universal covering to be 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. And his challenge was 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 C1C2C3 and E1E2E3 here:
Our paper explains why you can remove these triangles, assuming the hexagon was a universal covering in the first place. 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. However, our paper redoes his calculation and shows that the second number is seriously wrong. The actual areas are 3.7507 · 10-11 and 8.4460 · 10-21. These regions are shown as XE2T here and T’C3V here:
But this picture is not in scale! In fact the smaller region, T’C3V, has length 3.7 · 10-7 and maximum width 1.4 · 10-14, tapering down to a very sharp point. That’s about a few atoms wide if you draw the whole hexagon on paper! And it’s about 30 million times longer than it is wide. This is the sort of thing you can only draw with the help of a computer.
Anyway, Hansen’s best 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, our new universal covering removes about a million times more area than Hansen’s larger region: a whopping 2.233 · 10-5. So, we get a universal covering with area
The key is to slightly rotate the dodecagon shown in the above pictures, and then use the ideas of Pál and Sprague.
There’s a lot of room between our number and the best lower bound on this problem, due to Brass and Sharifi:
So, one way or another, we can expect a lot of progress now that computers are being brought to bear.
Read our paper for the details! If you want to check our work, we’ll be glad to answer lots of detailed questions. We want to rotate the dodecagon by an amount that minimizes the area of the universal covering we get, so we use a program to compute the area for many choices of rotation angle:
• Philip Gibbs, Java program.
The program is not very long—please study it or write your own, in your own favorite language! The output is here:
• Philip Gibbs, Java program output.
and as explained at the end of our paper, the best rotation angle is about 1.3°.
Azimuth 
Reblogged this on Pathological Handwaving and commented:
John Baez, Karine Bagdasaryan, and Philip Gibbs improve the Lebesgue Universal Covering problem by over a million times (2.23 x 10^(-5)) to get a new area of 0.844137708426… !
They invite you to check their work and note it will be much easier if you are very good at programming!
On page 2, you write “best previous lower bound, due to Hansen”, but this seems to be an upper bound.
Yes, thanks! I’ll fix that.
Congratulations! As a bonus, if none of you hears strange noises in coming days that kinda puts the kibosh on certain paranormal theories (any ectoplasmic embodiment of Martin Gardner’s spirit would clamor for details). In the second-last sentence of the paper, should “We could obtain a larger area if σ were smaller,…” instead be “We could obtain a smaller area if σ were smaller,…”?
Arch1 wrote:
Yes! Whoops, thanks!
Brilliant stuff!
I reconstructed the geometry for your final cover in Mathematica, and I get the same results for area as a function of the angle σ as you do.
Using high-precision arithmetic (2000 digits working precision), I found a valid σ of:
1.294389444703601012°
giving an area for the cover of:
0.844115297128419059…
There are a couple of typos in the paper. In the second inequality on page 2, you give Sprague’s area as:
0.8441377708435
but I believe the correct value is:
0.844137708435
i.e. there’s a triple 7 in the paper where it should be just a double 7.
Also, when you quote your final bound on page 10, you go from:
0.8441153768593765
which I agree with, to:
0.844411538
where the double 4 has become a triple 4.
Wow, that’s amazing! You’re the first person outside the team to actually check our work.
Thanks for catching those stupid typos. Those are my fault, and it goes to show (yet again) that errors easily creep in when copying things by hand—a lesson I should have learned by now.
But thanks much more for redoing Philip’s calculation! That’s truly heroic! Could you mail me the Mathematica program? I guess you can send it to me as a “notebook”. I can put it on my website and include a link to it in the paper, saying you used it to check our work. That way a referee of the paper, or any other interested party, will have another way to check our work.
Thanks for giving me the Mathematica notebook and a printout that people can read without using the software:
• Greg Egan, Gibbs–Bagdasaryan–Baez reduction: Mathematica notebook.
• Greg Egan, Gibbs–Bagdasaryan–Baez reduction: Mathematica printout.
I’ve updated our paper to refer to these.
More mathematics papers should use the word whopping.
Sarcastically, like us?
(I’m not sure I’ll have the guts to include this when we submit the paper for publication.)
Our paper on this subject has now been published, including the word “whopping” in the abstract:
• John Baez, Karine Bagdasaryan and Philip Gibbs, The Lebesgue universal covering problem, Journal of Computational Geometry 16 (2015), 288-299.
The referees caught a number of mistakes, so if you ever got ahold of an earlier version of this paper, and if you care, please get the new one. The journal is open-access, so it’s free.
Some party pooper apparently tried to remove the “whopping” (but failed; it’s obvious where the word belongs, and once you imagine it there, it sticks:-)
Oh, whoops! I forgot I removed the word “whopping” when I submitted the paper — feeling a bit nervous I guess. If I’d been clever, I would have re-inserted it in the final version.
[…] Back in 2015, I reported some progress on this difficult problem in plane geometry. I’m happy to report some more. This week I met Philip at 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.
[…] “As far as the math goes, it’s just high-school geometry. But it’s carried to a fanatical level of intensity,” wrote Baez. […]