Lebesgue’s Universal Covering Problem (Part 2)

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, Lebesgue’s universal covering problem.

But we’d like you to check our work! It will help if you’re good at programming. As far as the math goes, it’s just high-school geometry… carried to a fanatical level of intensity.

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

0.86602540…

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

0.84529946…

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

0.8441377708435…

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.

Philip Gibbs has created a Java applet illustrating Hansen’s universal cover. I urge you to take a look! You can zoom in and see the regions he removed:

• Philip Gibbs, Lebesgue’s universal covering problem.

I find that my laptop, a Windows machine, makes it hard to view Java applets because they’re a security risk. I promise this one is safe! To be able to view it, I had to go to the “Search programs and files” window, find the “Configure Java” program, go to “Security”, and add

http://gcsealgebra.uk/lebesgue/hansen

to the “Exception Site List”. It’s easy once you know what to do.

And it’s worth it, because only the ability to zoom lets you get a sense of the puny slivers that Hansen removed! One is the region XE2T here, and the other is T’C3V:

You can use this picture to help you find these regions in Philip Gibbs’ applet. 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

0.844137708416…

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

0.844115376859…

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:

0.832

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°.

13 Responses to Lebesgue’s Universal Covering Problem (Part 2)

  1. Emi says:

    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!

  2. Dan Schmidt says:

    On page 2, you write “best previous lower bound, due to Hansen”, but this seems to be an upper bound.

  3. arch1 says:

    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,…”?

    • John Baez says:

      Arch1 wrote:

      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,…”?

      Yes! Whoops, thanks!

  4. Greg Egan says:

    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.

    • John Baez says:

      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.

    • John Baez says:

      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.

  5. Blake Stacey says:

    More mathematics papers should use the word whopping.

  6. John Baez says:

    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.

  7. arch1 says:

    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:-)

    • John Baez says:

      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.

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s