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
- All intervals in P are either yellow or teal.
- All intervals in P are of length at most t
- 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
, and
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
- a
approximation of y
- a
approximation of
, and
- 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,
- The set of directions e such that
infinitely often is of measure zero.
- 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