### Can a Computer Solve Lebesgue’s Universal Covering Problem?

#### Posted by John Baez

Here’s a problem I hope we can solve here. I think it will be fun. It involves computable analysis.

To state the problem precisely, recall that the **diameter** of a set of points $A$ in a metric space is

$diam(A)=\sup\{d(x,y) : x,y\in A\}$

Recall that two subsets of the Euclidean plane $\mathbb{R}^2$ are **isometric** if we can get one from the other by translation, rotation and/or reflection.

Finally, let’s define a **universal covering** to be a convex compact subset $K$ of the Euclidean plane such that any set $A \subseteq \mathbb{R}^2$ of diameter $1$ is isometric to a subset of $K$.

In 1914 Lebesgue posed the puzzle of finding the universal covering with the least area. Since then people have been using increasingly clever constructions to find universal coverings with smaller and smaller area.

My question is whether we need an unbounded amount of cleverness, or whether we could write a program to solve this puzzle.

There are actually a number of ways to make this question precise, but let me focus on the simplest. Let $\mathcal{U}$ be the set of all universal coverings. Can we write a program that computes this number to as much accuracy as desired:

$a=inf\{ area(K) : K \in \mathcal{U}\} \; ?$

More precisely, is this real number $a$ computable?

Right now all we know is that

$0.832 \le a \le 0.844115376859\dots$

though Philip Gibbs has a heuristic argument for a better lower bound:

$0.84408 \le a$

I recently wrote a letter to Greg Egan in which by the end I’d convinced myself that the answer is *yes*, the number $a$ is computable. Instead of taking the time to polish up this letter into a nice blog article, I’ll just copy it here with minimal changes. There are lots of things that need to be clarified, but I think it would be fun to do this by having a conversation here. By the end of the conversation, maybe we’ll have a theorem.

So:

Let $\mathcal{X}$ be the space of convex compact sets in the plane having area 1 and center of mass at the origin. There’s a function

$f : \mathcal{X} \to [0,\infty)$

sending each such set $K$ to the largest value of $D$ such that any subset of the plane with diameter $D$ is isometric to a subset of $K$. The Lebesgue covering problem is equivalent to finding the supremum of the function $f$. In particular, the number $a$ is computable iff the number

$s = sup \{f(K) :K \in \mathcal{X} \}$

is computable. I guess

$a = \frac{1}{s^2}$

or something like that.

We can put a metric on $\mathcal{X}$, namely the usual Hausdorff metric. I’m willing to guess that $f$ is continuous with respect to this metric.

In fact, don’t think we lose anything by restricting attention to sets in the plane that lie in a ball of radius 1000: there are sets in $\mathcal{X}$ without this property, but they’ll be long and skinny, so they won’t maximize $f$.

So, let’s redefine $\mathcal{X}$ to include this extra requirement: it only contains sets that lie in a ball of radius 1000. Then $\mathcal{X}$ will be compact! This follows from the Blaschke selection theorem.

So now

$f: \mathcal{X} \to [0, \infty)$

is a continuous function on a compact metric space. So it must be bounded and attain its supremum somewhere.

So far this is just a proof that the Lebesgue universal covering problem has a solution: *there exists a universal covering of minimal area*.

The next question is whether we can compute the maximum value of $f$.

There’s a general fact, I believe: we can compute the maximum value of any computable function on a computably compact space. I don’t have any books on computable analysis at hand, but someone must have proved a theorem like this. We can’t compute where the maximum *occurs*, but we can compute the maximum value.

So, the question is just whether $f$ is computable.

First, what does it mean for a function

$f : \mathcal{X} \to \mathbb{R}$

to be computable? There are some different choices of definition here, since there are different approaches to computable analysis. I guess my favorite is this. I will define what it means for

$f : X \to Y$

to be computable whenever $X$ and $Y$ are separable metric spaces equipped with a **computability structure** that is, a countable dense sequence of points whose distances to each other can be computed to arbitrary desired accuracy.

Suppose $x_i$ is the computability structure for $X$ and $y_j$ is the computability structure for $Y$. Then $f$ is **computable** if the set of triples $i, j, n$ for which

$d(f(x_i), y_j) < 1/n$

is recursively enumerable — that is, it can be listed by some computer program.

In our example, we will take the computability structure on $\mathbb{R}$ to be any computable enumeration of the rationals: any way of listing the rationals that you can do with a computer program. We take the computability structure $x_i$ of $\mathcal{X}$ to be any computable enumeration of the polygons whose vertices have rational coordinates.

The definition of computability may sound a bit complicated. The basic idea is roughly that if we can compute $f(x_i)$ as a function of $i$, to whatever accuracy we want, our function

$f : \mathcal{X} \to \mathbb{R}$

will be computable in the technical sense above.

Actually that’s not quite right, in general! If $f$ changes very rapidly in an unpredictable way, we might be able to compute it as accurately as we want for the points $x_i$ but still be in the dark about nearby points. But I think we’ll be okay if *two* properties hold:

• $f$ is **sequentially computable**: we can write a program that given $i$ and $n$ computes a rational number within $1/n$ of $f(x_i)$.

• $f$ is **computably uniformly continuous**: as a function of $n > 0$ we can compute $m > 0$ such that if

$d(x,y) < 1/m$

then

$|f(x) - f(y)| < 1/n$

If our function $f$ has both these properties, I believe it will be computable in the technical sense. Moreover it’s also computable in another intuitive sense.

Namely: to specify a point $x \in X$ in a computable way, you have to give me a program that for each $m > 0$ will give me an $i$ such that

$d(x_i, x) < 1/m$

Suppose you do this, and I want to compute $f(x)$ to accuracy $2/n$. First I compute $m$ such that

$d(x,y) < 1/m$

implies

$|f(x) - f(y)| < 1/n$

Then I compute $f(x_i)$ to an accuracy of $1/n$. Then by the above inequality I know $f(x)$ to within $2/n$.

Now, back to our example. I believe we can show that the function in our example is computably uniformly continuous: changing the shape of a set just a little won’t dramatically change the maximum diameter $D$ such that it contains an isometric copy of any set of diameter $D$. I bet we have something pretty simple, like

$d(x,y) < 1/n$

implies

$|f(x) - f(y)| < 1/n$

So the question boils down to whether $f$ is sequentially computable: can we compute $f(x_i)$ as a function of $i$, to any desired accuracy?

In short: *can we in principle write a program that, given a convex polygon with rational vertices, computes to any desired accuracy the largest value of $D$ such that any set of diameter $D$ can be moved, by rigid motion, until it fits inside this polygon?*

This sounds hard.

However, we probably don’t need to think about “any set of diameter $d$”. It’s probably enough to think about “any polygon of diameter $d$ with rational vertices”.

It still seems hard to tell if *all* these can be translated and rotated/reflected in a way that fits them inside our chosen polygon. A completely brute-force search using some discretized approximation should settle the question for any *one* such shape — at least “up to a specified error $\epsilon$”, which is not a problem here. But going through *all* such shapes seems hard.

Hmm, but maybe not! We can probably assume without loss of generality that these shapes are convex — and then they, too, are points in a computably compact metric space, again thanks to Blaschke’s selection theorem. So maybe I don’t need to check infinitely many such shapes can be translated, rotated or reflected to fit inside my chosen polygon. I can do it for finitely many: enough that any such shape is very close to the ones I’ve checked.

I probably should say what a ‘computably compact metric space’ is. There’s probably a standard definition of this, but I think for my purposes this will do: it’s a separable metric space $X$ with a computability structure such that we can write a program that given any $n > 0$ as input will list a finite set $i_1, \dots, i_k$ such that every $x \in X$ is distance at most $1/n$ from one of the points $x_{i_1}, \dots, x_{i_k}$.

I believe, but haven’t proved, that the space $\mathcal{X}$ is computably compact.

So, right now I feel that

$s = sup \{f(K) :K \in \mathcal{X} \}$

is likely to be computable, and thus

$a=inf\{ area(K) : K \in \mathcal{U}\}$

is computable. But this would be nice to prove.

## Re: Can a Computer Solve Lebesgue’s Universal Covering Problem?

I’m not sure that this is entirely on-topic, but I’ve been pondering ways to approach the construction of a universal covering systematically, and I came up with a method that I think is quite interesting … although alas it gives a pretty useless area of about 0.85.

Any set $S$ of constant width 1 touches each side of a regular hexagon of width 1 at precisely one point. Each point of contact determines the one on the opposite side as well, so there is only a 3-parameter space of contact points; call the parameters $\alpha, \beta, \gamma$. Naively, 3 of the points can lie anywhere on their sides of the hexagon, but there’s an additional constraint that no pair of points can be separated by a distance greater than 1, which turns out to confine any pair of the three parameters to a certain intersection of ellipses.

Now, the set $S$ must lie inside the intersection of the six disks of radius 1 centred on the contact points; if we call that intersection of disks $D(\alpha, \beta, \gamma)$, then the union of $D(\alpha, \beta, \gamma)$ over the entire parameter space will give a universal covering. I haven’t checked, but I think that’s probably the entire hexagon.

However, we can do a bit better than that quite easily: the 12-element symmetry group of the hexagon acts on the parameter space of 3-tuples $(\alpha, \beta, \gamma)$, and there’s a natural partition of the parameter space into fundamental domains of that action. So the union of $D(\alpha, \beta, \gamma)$ over a single fundamental domain should also be a universal covering, once you take into account the possibility of applying the symmetries of the hexagon to the set you want to cover, in order to bring the contact points into the fundamental domain.

And the resulting set (which could probably be described analytically quite easily, but so far I’ve only constructed numerically) has an area of about 0.85.

But there might be some clever way to improve it …