As seen in this comment on Polymath and explicated further in Fernando de Oliveira Filho’s thesis, section 4.4.

I actually spent much of today thinking about this so let me try to explain it in a down-to-earth way, because it involved me thinking about Bessel functions for the first time ever, surely a life event worthy of recording.

So here’s what we’re going to do. As I mentioned last week, you can express this problem as follows: suppose you have a map h: R^2 -> V, for some normed vector space V, which is a *unit-distance embedding*; that is, if |x-x’|_{R^2} = 1, then |h(x)-h(x’)|_V = 1. (We don’t ask that h is an isometry, only that it preserves the distance-1 set.)

Then let t be the radius of the smallest hypersphere in V containing h(R^2).

Then any graph embeddable in R^2 with all edges of length 1 is sent to a unit-distance graph in V contained in the hyperplane of radius t; this turns out to be equivalent to saying the Lovasz number of G (ok, really I mean the Lovasz number of the complement of G) is at most 1/(1-2t). So we want to show that t is bounded below 1, is the point. Or rather: we can *find *a V and a map from R^2 to V to make this the case.

So here’s one! Let V be the space of L^2 functions on R^2 with the usual inner product. Choose a square-integrable function F on R^2 — in fact let’s normalize to make F^2 integrate to 1 — and for each a in R^2 we let h(a) be the function F(x-a).

We want the distance between F(x-a) and F(x-b) to be the same for every pair of points at distance 1 from each other; the easiest way to arrange that is to insist that F(x) be a radially symmetric function F(x) = f(|x|); then it’s easy to see that the distance between F(x-a) and F(x-b) in V is a function G(a-b) which depends only on |a-b|. We write

so that the squared distance between F(x) and F(x-r) is

.

In particular, if two points in R^2 are at distance 1, the squared distance between their images in V is 2(1-g(1)). Note also that g(0) is the square integral of F, which is 1.

What kind of hypersphere encloses all the points F(x-a) in V? We can just go ahead and take the “center” of our hypersphere to be 0; since |F| = 1, every point in h(R^2) lies in (indeed, lies *on*) the sphere of radius 1 around the origin.

Hey but remember: we want to study a *unit-distance* embedding of R^2 in V. Right now, h sends unit distances to the distance 2(1-g(1)), whatever that is. We can fix that by scaling h by the square root of that number. So now h sends unit distances to unit distances, and its image is enclosed in a hypersphere of radius

2(1-g(1))^{-1}

The more negative g(1) is, the smaller this sphere is, which means the more we can “fold” R^2 into a small space. Remember, the relationship between hypersphere number and Lovasz theta is

and plugging in the above bound for the hypersphere number, we find that the Lovasz theta number of R^2, and thus the Lovasz theta number of any unit-distance graph in R^2, is at most

1-1/g(1).

So the only question is — what is g(1)?

Well, that depends on what g is.

Which depends on what F is.

Which depends on what f is.

And of course we get to *choose* what f is, in order to make g(1) as negative as possible.

How do we do this? Well, here’s the trick. The function G is not arbitrary; if it were, we could make g(1) whatever we wanted. It’s not hard to see that G is what’s called a *positive definite* function on R^2. And moreover, if G is positive definite, there exists some f giving rise to it. (Roughly speaking, this is the fact that a positive definite symmetric matrix has a square root.) So we ask: if G is a positive definite (radially symmetric) function on R^2, and g(0) = 1, how small can g(1) be?

And now there’s an old theorem of (Wisconsin’s own!) Isaac Schoenberg which helpfully classifies the positive definite functions on R^2; they are precisely the functions G(x) = g(|x|) where g is a mixture of scalings of the Bessel function $J_0$:

for some everywhere nonnegative A(u). (Actually it’s more correct to say that A is a distribution and we are integrating J_0(ur) against a non-decreasing measure.)

So g(1) can be no smaller than the minimum value of J_0 on [0,infty], and in fact can be exactly that small if you let A become narrowly supported around the minimum argument. This is basically just taking g to be a rescaled version of J_0 which achieves its minimum at 1. That minimum value is about -0.4, and so the Lovasz theta for any unit-distance subgraph on the plane is bounded above by a number that’s about 1 + 1/0.4 = 3.5.

**To sum up:** I give you a set of points in the plane, I connect every pair that’s at distance 1, and I ask how you can embed that graph in a small hypersphere keeping all the distances 1. And *you* say: “Oh, I know what to do, just assign to each point a the radially symmetrized Bessel function J_0(|x-a|) on R^2, the embedding of your graph in the finite-dimensional space of functions spanned by those Bessel translates will do the trick!”

That is cool!

*Remark: *Oliveira’s thesis does this for Euclidean space of every dimension (it gets more complicated.) And I think (using analysis I haven’t really tried to understand) he doesn’t just give an upper bound for the Lovasz number of the plane as I do in this post, he really computes that number on the nose.

*Update:* DeCorte, Oliveira, and Vallentin just posted a relevant paper on the arXiv this morning!

### Like this:

Like Loading...