Pinned distance sets using effective dimension

I have just uploaded a paper on the Hausdorff dimension of pinned distance sets. For a given set , the distance set of E is

If , the pinned distance set of E with respect to x is

An important problem in geometric measure theory is to understand the size of and, more generally, . Falconer conjectured that, if , then . Even in the plane, this is still open (although there has been a recent surge in progress on this question).

In this post we focus on the planar case. Liu showed that, if

then for “most” (formally defined later) points in the plane,

.

Shortly thereafter, Shmerkin improved Liu’s result when is close to 1. Specifically, he showed that if the dimension of E is strictly greater than 1, then

for most points .

In this post, I will describe the main argument in my paper on pinned distance sets, where I proved the following.

Theorem 1: If is analytic and has Hausdorff dimension strictly greater than one, then

for all x outside a set of Hausdorff dimension at most one.

Update: It is possible to generalize this bound so that it depends on the Hausdorff dimension of . In particular, we can conclude that

The proof of this generalization is essentially the same as the proof of this post, with one or two technical additions. In this post I will sketch the proof of Theorem 1.

The proof of Theorem 1 uses effective dimension. The first part of the proof gives an effective, pointwise, analog of Theorem 1 (this is Theorem 2 below). The second uses a result by Orponen on radial projections and the point-to-set principle to reduce Theorem 1 to our pointwise result. We begin by explaining the proof of the main (effective) theorem.

Theorem 2: Suppose and satisfy the following conditions.

(C1)

(C2) for every .

(C3) for every .

(C4) for every .

The main technical result need in the proof of Theorem 2 is a bound on the complexity of projected points, which may be of independent interest. At the conclusion of the next section, we will discuss how this relates to Theorem 2.

1. Projection theorem

Recall that if is a unit vector in the plane, the projection of onto the line spanned by is

As described in a previous post, for every precision r,

whenever is random relative to , i.e.,

Unfortunately, for the application to Theorem 2, we don’t have enough control over e to ensure that e is random relative to x. However, we will have (the weaker condition) that e is random up to precision t, i.e.,

for all where

.

The main content of this section is to show that the techniques for projections developed by Lutz and Stull can be extended to give bounds in this case (at a cost of weakening the bound). Formally, we prove

Theorem 3: Suppose that , and for all . Then

The first step in the proof of Theorem 3 is the observation that our previous techniques almost immediately imply the following.

Lemma 4: Suppose r is sufficiently large, for all and

for all . Then

.

We won’t go into the proof of Lemma 4 in this post. The argument is nearly identical to the one described in this post. We can use Lemma 4 and an oracle reduction idea to show the following.

Lemma 5: Suppose r is sufficiently large, for all and

for all . Then

.

The point here is to use our oracle construction to get an oracle D so that

.

Then, relative to D, we are able to apply Lemma 4.

We introduce the following definitions. We say an interval [a, b] is yellow if

for all . We say that [a, b] is teal if

for all . Thus, Lemmas 4 and 5 show that we have tight bound for on yellow and teal intervals.

1.1 Partition construction

For every t and r, it is not difficult to show the existence of a partition P of so that

1. All intervals in P are either yellow or teal.
2. All intervals in P are of length at most t
3. The intervals in P have pairwise disjoint interiors and their union is .

We call a partition satisfying these conditions admissible. Given such a partition, using symmetry of information and Lemmas 4 and 5, we can sum the bounds on each interval in P. This gives the following bound.

.

Unfortunately, this partition is too naive to immediately imply Theorem 3. To complete the proof, we need to construct a partition which is slightly more optimized.

We say that an interval [a, b] is green if

1. , and
2. is both yellow and teal.

Note that, by Lemma 4, if [a, b] is green, then

.

Moreover,

.

Thus on green intervals, we maximize the difference

.

This motivates us to construct a partition of which contains many green intervals. In the paper, such a partition is formally constructed. However, for this post, I will elide this details, and skip to the conclusion of Theorem 3.

Proof of Theorem 3: First assume that there is an admissible partition P of [0, r] containing only yellow intervals. Then by the symmetry of information

,

and so by our previous bound, (1),

,

and the conclusion follows.

If no such partition exists then it is possible to show that there is an admissible partition P of [0, r] satisfying the following: The total length of green intervals in P is at least t, i.e.,

Again by the symmetry of information we can conclude that

where

is the total length of bad intervals (intervals which are yellow, but not green). Therefore, by (1) and (2), we see that

Combining (3), and the fact that ,

from which the conclusion follows.

1.2 Connection between projections and distances

The connection between projections and distances comes from the following fact.

Observation: Let , be points such that . Let

, .

Then

,

where . Moreover,

,

for all .

To see why this is useful, suppose that satisfy the hypothesis of the observation. Then it is not difficult to show that

If, in addition, we assume x is independent of y, this is equivalent to

Then, since , it is not hard to see that

.

Combining these facts, we deduce

Applying our projection result, Theorem 3, with respect to ,

and so we have

The point of (4) is that it gives strong lower bounds on the complexity of any point whose distance from is . We now describe how to use this in order to prove Theorem 2.

2. Proof of the pointwise analog of Thereom 1

We now turn to the pointwise analog of Theorem 1, which gives a lower bound on the effective dimension of , whenever satisfy certain conditions.

Theorem 2: Suppose and satisfy the following conditions.

(C1)

(C2) for every .

(C3) for every .

(C4) for every .

Then

.

In addition to the projection result (Section 1), Theorem 2 relies on the following the general bound, which holds at every precision

The proof of this is very similar to the argument for projections (and is in fact simpler). To keep this exposition short, we will not give a proof of this bound here.

The proof of Theorem 2 combines (5) with our projection result. We first choose precision t so that

Then, by our naive bound (5), we see that

.

Thus, by symmetry of information it suffices to show that

Let D be an oracle (as described previously) which reduces the complexity of y so that

for some small . Let

and . If s is greater than r/2, then we can use the argument of Lemma 4 to conclude that

Otherwise, if s is less than r/2, by the bound (4) given in Section 1.2,

Thus, in either case,

Therefore, relative to oracle D, if we are given

1. a approximation of y
2. a approximation of , and
3. x as an oracle

we can compute a approximation of y. Indeed, we simply enumerate all points z with distance such that . We have just seen that any such point must be within of y, and the claim follows. In the language of Kolmogorov complexity, this is written

By the properties of oracle D, condition (C3), and our choice of t, we can conclude

The conclusion follows since can be arbitrarily small.

3. Reduction to pointwise analog

To finish this post, we now describe how to use Theorem 2 to prove the main theorem of the paper, Theorem 1.

Theorem 1: If is analytic and has Hausdorff dimension strictly greater than one, then

We begin by noting (using well known facts of geometric measure theory) that it suffices to show Theorem 1 for the case when E is compact, and

for some s > 1. Let .

The main result used in the reduction is the following theorem of Orponen on radial projections. For any x, define

The pushforward measure of is the measure defined by

for any subset S of the unit circle. Orponen’s theorem implies the following.

Theorem: There is a Borel set B with Hausdorff dimension less than 1 such that, for all ,

is absolutely continuous with respect to

We can use this theorem in our reduction by combining it with recent results in algorithmic information theory. Specifically, let A be an oracle relative to which E is effectively compact and is lower semicomputable. Then it is possible to show that, for any x,

1. The set of directions e such that infinitely often is of measure zero.
2. The set of points y in E such that infinitely often is of measure zero.

Facts (1) and (2), combined with Orponen’s theorem, show that, for every x outside a set B of dimension at most one, there is some y in E so that (x,y) satisfies conditions (C1)-(C4) of Theorem 2, relative to oracle A.

We can conclude Theorem 1 by applying the point-to-set principle for this choice of A and using Theorem 2. Since is effectively compact relative to , it is not difficult to show that is effectively compact relative to , for every point . A theorem of Hitchcock shows that, for every ,

Thus, for every outside B, by taking any so that satisfy (C1)-(C4) relative to , and applying Theorem 2,

and the proof is complete