Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

February 4, 2015

Lebesgue’s Universal Covering Problem

Posted by John Baez

Lebesgue’s universal covering problem is famously difficult, and a century old. 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\le 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

32=0.86602540 \frac{\sqrt{3}}{2} = 0.86602540 \dots

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

223=0.84529946 2 - \frac{2}{\sqrt{3}} = 0.84529946 \dots

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 0.8441377708435 \dots

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 410 114 \cdot 10^{-11} and 610 186 \cdot 10^{-18}. However, our paper redoes his calculation and shows that the second number is seriously wrong. The actual areas are 3.750710 113.7507 \cdot 10^{-11} and 8.446010 218.4460 \cdot 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.710 73.7 \cdot 10^{-7} and maximum width 1.410 141.4 \cdot 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 0.844137708416 \dots

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.23310 52.233 \cdot 10^{-5}. So, we get a universal covering with area

0.844115376859 0.844115376859 \dots

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 0.832

So, one way or another, we can expect a lot of progress now that computers are being brought to bear. Philip Gibbs has a heuristic computer calculation pointing toward a value of

0.84408 0.84408

so perhaps that’s what we should shoot for.

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 1.3^\circ.

Posted at February 4, 2015 1:23 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2801

13 Comments & 0 Trackbacks

Re: Lebesgue’s Universal Covering Problem

Congratulations! What got you into this?

Posted by: Tom Leinster on February 4, 2015 2:34 AM | Permalink | Reply to this

Re: Lebesgue’s Universal Covering Problem

I forget how I found out about this problem, but I blogged about it in December 2013 and Philip Gibbs got interested enough to tackle it with the help of a computer. He posted an article about it on the viXra:

full of new ideas. I decided it would be good to take a portion of his work and write proofs at a level of rigor suitable for publication in a good journal. Karine Bagdasaryan is an undergraduate math major at U. C. Riverside who wanted to do a project on geometry. So, we all teamed up and wrote this paper together!

Posted by: John Baez on February 4, 2015 4:26 AM | Permalink | Reply to this

Re: Lebesgue’s Universal Covering Problem

Thanks. I thought when I read your post that I’d seen you write about his problem before; it must have been that Azimuth post.

It sounds like a great undergrad project. And this is the first time I’ve seen a viXra paper cited in a respectable context!

Posted by: Tom Leinster on February 4, 2015 12:26 PM | Permalink | Reply to this

Re: Lebesgue’s Universal Covering Problem

It’s striking how elementary your proof is! That would seem to suggest that the large body of existing knowledge about convex geometry isn’t much use here.

The Lebesgue problem reminds me of a couple of other things: on the one hand, the Kakeya problem, and on the other, the Hadwiger containment theorem.

That’s not the same as the Hadwiger theorem (about valuations on convex sets) that I’ve mentioned many times here before. What Hadwiger’s containment theorem says is the following. Let KK and LL be compact convex subsets of the plane, with nonempty interiors. Suppose that

area(K)+area(L)perimeter(K)perimeter(L)>12π. \frac{area(K) + area(L)}{perimeter(K)\cdot perimeter(L)} \gt \frac{1}{2\pi}.

Then either there exists a Euclidean motion of the plane that moves KK into the interior of LL, or vice versa.

(The significance of the constant 1/2π1/2\pi: it’s what the left-hand side is equal to if KK and LL are equal-sized disks.)

This doesn’t seem very closely related to the Lebesgue problem, but it’s a nice theorem anyway. I learned it from Klain and Rota’s little book Introduction to Geometric Probability.

One more stray thought. In Taking categories seriously, Lawvere argues that the radius of a metric space is a more functorial quantity than the diameter. Here the radius of a bounded space XX is defined to be

inf{r:XB(a,r)forsomeaX}. inf \{r : X \subseteq B(a, r) \,\,for\,\,some\,\, a \in X\}.

Perhaps Lawvere would argue that Lebesgue should have asked: what is the least possible area of a convex planar set containing an isometric copy of every planar set of radius 1\leq 1?

Posted by: Tom Leinster on February 4, 2015 5:29 PM | Permalink | Reply to this

Re: Lebesgue’s Universal Covering Problem

I’m pretty sure the answer to that “should have asked” question is a unit disc.

Posted by: Jesse C. McKeown on February 4, 2015 6:26 PM | Permalink | Reply to this

Re: Lebesgue’s Universal Covering Problem

Ha! Thanks. I should have thought before posting.

While I obviously regret suggesting that Bill would have argued something so transparently idiotic, this little episode probably supports his point. Radius is such a functorial quantity that the answer to the Lebesgue-type question becomes trivial. Diameter, on the other hand, makes the Lebesgue question highly nontrivial.

Posted by: Tom Leinster on February 4, 2015 6:54 PM | Permalink | Reply to this

Re: Lebesgue’s Universal Covering Problem

Tom wrote:

I should have thought before posting.

Maybe not. It would have denied us several pleasures, Schadenfreude being just the basest.

It’s certainly interesting to think about how ‘radius’ differs from ‘diameter’. Sometimes you have to go against the tao of mathematics to come up with an easy-to-state but hard-to-solve problem. For example, it’s obviously going against the grain to ask if every large enough even number is the sum of two primes, since primes are for multiplying: you’d have to be perverse to try to build up numbers as sums of primes.

It’s fun when these problems reveal a ‘hidden tao’, like Fermat’s Last Theorem, which sounds like a silly thing to wonder about at first, but turns out to be a front for the Modularity Theorem (which is deeply connected to interesting things, though also somehow against the grain).

At the other extreme, some conjectures that go against the tao of mathematics could be ‘true, but for no good reason’ and thus unprovable. Conway has argued that problems related to the Collatz Conjecture may be examples.

In the case of the Lebesgue universal covering problem, which is not a yes-or-no conjecture, it could be instead that approaching the greatest lower bound leads to ever more work and nothing really elegant.

Hmm: I suppose we should ask if the greatest lower bound on areas of universal coverings is computable.

Philip Gibbs has found a nice way to estimate it, which unfortunately is not rigorous. He estimates it at 0.844080.84408. If so, our proof that it’s 0.844115376859\le 0.844115376859 \dots is not doing so bad.

Posted by: John Baez on February 4, 2015 10:03 PM | Permalink | Reply to this

Re: Lebesgue’s Universal Covering Problem

the tao of mathematics … primes are for multiplying: you’d have to be perverse to try to build up numbers as sums of primes.

I seem to remember Terry Tao making some joke about the existence of geometric progressions in the primes. Perhaps he was announcing a proof that he could construct arbitrarily short ones.

Posted by: Tom Leinster on February 5, 2015 9:13 PM | Permalink | Reply to this

Re: Lebesgue’s Universal Covering Problem

The Lebesgue problem reminds me of things like the Busemann–Petty problem. A common theme is that means of measurement with different dimensionalities (diameter v. area, or nn-dimensional volume v. (n1)(n-1)-dimensional volume of cross-sections) tend not to be very closely related to each other.

Posted by: Mark Meckes on February 5, 2015 8:47 PM | Permalink | Reply to this

Re: Lebesgue’s Universal Covering Problem

Tom wrote:

What got you into this?

I should add something rather obvious: this kind of problem, hard but not clearly connected to big general ideas, is exactly the opposite of the kind of math I used to advocate. It has nothing to do with nn-categories, nothing to do with figuring out the laws of the universe, and it requires lots of hard work instead of easy ‘following the tao’. So it may seem weird that I got involved in this problem.

I’m definitely not foresaking my philosophy that a lot of the best math comes from cutting along the grain instead of against it, and following elegant abstractions wherever they naturally lead instead of trying to crack hard problems with brute force.

However, I find that if you stick too tightly to any philosophy, you run the risk of overdeveloping certain mental muscles and underdeveloping others, and also just not having as much fun as you otherwise could. I think we’ve all sometime had the fantasy of tackling a famous old problem… so why not try, once?

And in this case, success was vastly more likely than usual, since Philip Gibbs had done most of the hard work, and Karine and I mainly needed to fill small holes in the argument and make everything nice.

Posted by: John Baez on February 4, 2015 10:23 PM | Permalink | Reply to this

Re: Lebesgue’s Universal Covering Problem

exactly the opposite of the kind of math I used to advocate.

Yes, that was more or less what was behind my question. I know that Baez gets involved in all sorts of things, but this one did surprise me slightly.

Just in case I’m giving off any negative vibes, I don’t even slightly disapprove! On the contrary, I’m impressed.

Posted by: Tom Leinster on February 5, 2015 5:54 PM | Permalink | Reply to this

Re: Lebesgue’s Universal Covering Problem

Good news! We’ve gotten some extra confirmation of our results… and also of my poor typing abilities. Greg Egan wrote:

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.

He gave me the Mathematica notebook where he did these calculations, 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 updated our paper to refer to these and thank Greg.

Posted by: John Baez on February 8, 2015 10:59 PM | Permalink | Reply to this

Re: Lebesgue’s Universal Covering Problem

Our paper on this subject has now been published:

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

Posted by: John Baez on September 23, 2015 6:26 PM | Permalink | Reply to this

Post a New Comment