# Dimension of Pinned Distance Sets for Semi-Regular Sets

Jacob B. Fiedler  Department of Mathematics, University of Wisconsin, Madison,
Wisconsin 53715<EMAIL_ADDRESS>and  D. M. Stull  Department of
Mathematics, University of Chicago, Chicago, IL 60637<EMAIL_ADDRESS>
###### Abstract.

We prove that if $E\subseteq\mathbb{R}^{2}$ is analytic and $1<d<\dim_{H}(E)$,
there are “many” points $x\in E$ such that the Hausdorff dimension of the
pinned distance set $\Delta_{x}E$ is at least
$d\left(1-\frac{\left(D-1\right)\left(D-d\right)}{2D^{2}+\left(2-4d\right)D+d^{2}+d-2}\right)$,
where $D=\dim_{P}(E)$. In particular, we prove that
$\dim_{H}(\Delta_{x}E)\geq\frac{d(d-4)}{d-5}$ for these $x$, which gives the
best known lower bound for this problem when $d\in(1,5-\sqrt{15})$. We also
prove that there exists some $x\in E$ such that the packing dimension of
$\Delta_{x}E$ is at least $\frac{12-\sqrt{2}}{8\sqrt{2}}$. Moreover, whenever
the packing dimension of $E$ is sufficiently close to the Hausdorff dimension
of $E$, we show the pinned distance set $\Delta_{x}E$ has full Hausdorff
dimension for many points $x\in E$; in particular the condition is that
$D<\frac{(3+\sqrt{5})d-1-\sqrt{5}}{2}$.

We also consider the pinned distance problem between two sets
$X,Y\subseteq\mathbb{R}^{2}$, both of Hausdorff dimension greater than 1. We
show that if either $X$ or $Y$ has equal Hausdorff and packing dimensions, the
pinned distance $\Delta_{x}Y$ has full Hausdorff dimension for many points
$x\in X$.

The first author was supported in part by NSF DMS-2037851 and NSF DMS-2246906.
Both authors are grateful to the American Institute of Mathematics for hosting
the workshop Effective methods in measure and dimension, which was the genesis
of this collaboration.

##  1\. Introduction

Given some $E\subseteq\mathbb{R}^{n}$ of a particular size, a natural question
is whether one can bound the size of its distance set, defined as

$\Delta E=\\{|x-y|:x,y\in E\\}$

The continuous version of this question is the Falconer distance problem,
concerning the fractal dimension of $E$. Falconer conjectured that for Borel
sets $E$, whenever $\dim_{H}(E)>\frac{n}{2}$, then $\Delta E$ has positive
measure. In the plane, the best known bound is that $\dim_{H}(E)>\frac{5}{4}$
implies $\Delta E$ has positive measure and is due to Guth, Iosevich, Ou, and
Wang [5]. In higher dimensions, very recent work of Du, Ou, Ren, and Zhang
established the threshold that
$\dim_{H}(E)>\frac{n}{2}+\frac{1}{4}-\frac{1}{8n+4}$ implies $\Delta E$ has
positive measure [3][4][17].

In fact, these works each established a stronger result concerning _pinned_
distance sets. For $x\in\mathbb{R}^{n}$, we define

$\Delta_{x}E=\\{|x-y|:y\in E\\}.$

The aforementioned papers prove that under the respective assumptions, there
exists some $x\in E$ such that $\Delta_{x}E$ has positive measure. Note that
such a result for pinned distance sets immediately implies the corresponding
result for distance sets.

A closely related problem is to prove lower bounds on the Hausdorff or packing
dimension of $\Delta_{x}E$ for “many” $x\in E$, given $d=\dim_{H}(E)$.
Restricting consideration to $\mathbb{R}^{2}$ for the remainder of the paper,
we now discuss a few previous bounds of this type. For $d\in(1,\frac{5}{4})$,
Liu proved that $\dim_{H}(\Delta_{x}E)>\frac{4d}{3}-\frac{2}{3}$ in [9].
Shmerkin proved a better bound for $d$ not much greater than 1, namely that
$\dim_{H}(\Delta_{x}E)\geq\frac{2}{3}+\frac{1}{42}$ [19]. The second author
improved the best known bound for $d$ not much larger than 1, proving that
$\dim_{H}(\Delta_{x}E)\geq\frac{d}{4}+\frac{1}{2}$ [20].

Complementing the bounds cited in the previous paragraph, Du, Ou, Ren and
Zhang proved a bound for $d$ _less_ than the dimension threshold of Falconer’s
conjecture [3]. In $\mathbb{R}^{2}$, they showed $\sup_{x\in
E}\dim_{H}(\Delta_{x}E)\geq\frac{5d}{3}-1$. As for packing dimension, in [7],
Shmerkin and Keleti proved that

$\dim_{P}(\Delta_{x}E)\geq\frac{1}{4}\left(1+d+\sqrt{3d(2-d)}\right).$

Finally, we note that Shmerkin proved that for sets $E$ which are _regular_ in
the sense that $\dim_{H}(E)=\dim_{P}(E)$, so long as $\dim_{H}(E)>1$, then for
most $x$, the pinned distance set has full dimensions, i.e.,
$\dim_{H}(\Delta_{x}E)=1$ [18].111Observe that this regularity is weaker than
Alfors-David regularity, which Orponen considered in [15]. Throughout the
remainder of the paper, by regular, we mean the more general notion.

Our work makes a number of improvements to the pinned distance problem in the
plane. First, we are able to prove a dimensional lower bound which takes into
account the packing dimension of $E$.

######  Theorem 1.

Let $E\subseteq\mathbb{R}^{2}$ be analytic such that $1<d<\dim_{H}(E)$. Then
there is a subset $F\subseteq E$ of full dimension such that

$\dim_{H}(\Delta_{x}E)\geq
d\left(1-\frac{\left(D-1\right)\left(D-d\right)}{2D^{2}+\left(2-4d\right)D+d^{2}+d-2}\right),$

for all $x\in F$, where $D=\dim_{P}(E)$. In particular, $\dim_{H}(E\setminus
F)\leq d<\dim_{H}(E)$. Furthermore, if

$D<\frac{(3+\sqrt{5})d-1-\sqrt{5}}{2}$

Then $\dim_{H}(\Delta_{x}E)=1$.

Note that the second part of the theorem significantly generalizes Shmerkin’s
result for regular sets $E\subseteq\mathbb{R}^{2}$, in the sense that we show
that $E$ need not be fully regular to have most of its pinned distance sets be
full dimension. Instead, it only needs to have sufficiently close Hausdorff
and packing dimension, a form of “semi-regularity”. As a corollary of this
theorem, we obtain an improvement over the second author’s previous bound,
namely.

######  Corollary 2.

Let $E\subseteq\mathbb{R}^{2}$ be analytic such that $1<d<\dim_{H}(E)$. Then
there is a subset $F\subseteq E$ of full dimension such that

$\dim_{H}(\Delta_{x}E)\geq\frac{d(d-4)}{d-5}.$

for all $x\in F$.

Additionally, we can bound the dimension of the pinned distance sets in terms
of only the packing dimension, as below.

######  Corollary 3.

Let $E\subseteq\mathbb{R}^{2}$ be analytic such that $\dim_{H}(E)>1$. Then,
for all $x\in E$ outside a set of (Hausdorff) dimension one,

$\dim_{H}(\Delta_{x}E)\geq\frac{D+1}{2D},$

where $D=\dim_{P}(E)$.

This corollary turns out to be useful in establishing the following
improvement on Shmerkin and Keleti’s packing dimension bound.222More
precisely, we use its effective analog.

######  Theorem 4.

Let $E\subseteq\mathbb{R}^{2}$ be analytic such that $\dim_{H}(E)>1$. Then
there exists some $x\in E$ such that,

$\dim_{P}(\Delta_{x}E)\geq\frac{12-\sqrt{2}}{8\sqrt{(}2)}\approx 0.9356.$

However, our results are more general than the above. We are able to prove
essentially the same bounds in the case that our pinned points $x$ lie in some
set $X$ and we consider the set of distances from $x$ to some analytic set
$Y$. Theorem 1 is itself an immediate corollary of the following more general
theorem.

######  Theorem 5.

Let $Y\subseteq\mathbb{R}^{2}$ be analytic such that $1<d_{y}=\dim_{H}(Y)$ and
$D_{y}=\operatorname{Dim}_{p}(Y)$. Let $X\subseteq\mathbb{R}^{2}$ be such that
$1<d_{x}<\dim_{H}(X)$ and $D_{x}=\operatorname{Dim}_{p}(X)$. Then there is
some $F\subseteq X$ of full dimension such that

$\dim_{H}(\Delta_{x}E)\geq
d\left(1-\frac{\left(D-1\right)\left(D-d\right)}{2D^{2}+\left(2-4d\right)D+d^{2}+d-2}\right),$

for all $x\in F$, where $d=\min\\{d_{x},d_{y}\\}$ and
$D=\max\\{D_{x},D_{y}\\}$. In particular, $\dim_{H}(X\setminus F)\leq
d_{x}<\dim_{H}(X)$ Furthermore, if

$D<\frac{(3+\sqrt{5})d-1-\sqrt{5}}{2}$

Then $\dim_{H}(\Delta_{x}E)=1$.

The second portion of this theorem amounts to a semi-regularity condition on
both $X$ and $Y$. Our work also shows that we can achieve full dimension
pinned distance sets when all that we require of $X$ is $\dim_{H}(X)>1$, at
the cost of a somewhat more strict semi-regularity condition on $Y$.

######  Theorem 6.

Let $Y\subseteq\mathbb{R}^{2}$ be analytic with $\dim_{H}(Y)>1$ and
$\dim_{P}(Y)<2\dim_{H}(Y)-1$. Let $X\subseteq\mathbb{R}^{2}$ be any set such
that $\dim_{H}(X)>1$. Then for all $x\in X$ outside a set of (Hausdorff)
dimension one,

$\dim_{H}(\Delta_{x}Y)=1.$

Finally, we are able to show that regularity in just the pin set $X$ is good
enough to imply that typical pinned distance sets have dimension 1.

######  Theorem 7.

Let $Y\subseteq\mathbb{R}^{2}$ be analytic with $\dim_{H}(Y)>1$. Let
$X\subseteq\mathbb{R}^{2}$ be any set such that $\dim_{H}(X)=\dim_{P}(X)>1$.
Then there is a subset $F\subseteq X$ such that,

$\dim_{H}(\Delta_{x}Y)=1,$

for all $x\in F$. Moreover, $\dim_{H}(X\setminus F)<\dim_{H}(X)$.

Now, we outline the structure of the paper. This paper employs recently
developed “effective” methods in the study of dimension. These methods connect
Hausdorff and packing dimension to Kolmogorov complexity through point-to-set
principles, and thus open classical problems up to attack by tools from
computability theory. Section 2 covers the necessary preliminaries from
computability theory, as well as a few less introductory but crucial lemmas.

Section 3 deals with the proof of an effective projection theorem for points
$x$ which is primarily used to bound the growth of the complexity of $|x-y|$
in the next section. In order to obtain this projection theorem, we need to
perform a certain partitioning argument on the interval $[1,r]$ considering
the complexity function $K_{r}(x)$. Partitioning $[1,r]$ into smaller
intervals so that the complexity function has useful properties on each
interval, or even just certain intervals, is a recurring idea throughout this
paper.

Section 4 is the main thrust of the argument on the effective side. The idea
is to now partition $[1,r]$ so that $K_{r}(|x-y|)$ either grows at an optimal
rate of 1 or grows at an average rate at least equal to the average growth
rate of $K_{r}(y)$ on each interval. First, in section 4.2, we construct a
partition which only uses the first kind of interval; this does not require
the application of the projection theorem and will thus be essential in
proving Theorem 6.333Recall that Theorem 6 was more or less independent of the
dimension of $X$, so long as it is greater than 1. This is why we do not use
the projection theorem here, as it concerns the pin $x$ and its effective
dimension. Section 4.3 details the construction of a more general partition
that achieves better bounds using the projection theorem, and section 4.4 sums
over this partition to obtain the effective analog of Theorem 5. This
effective analog is a bound on the complexity of the distance at _every_
precision, and in section 4.5 we use it as a basis to obtain improved bounds
at certain well-chosen precisions; this yields the effective analog of Theorem
4.

Section 5 is where we perform the reductions to the classical results.
Essentially, we have to show that sets of the given dimensions always have
points $x$ and $y$ with the desired algorithmic properties, which then imply
the bounds of our effective theorems hold for certain distances. Performing
these reductions yields Theorem 4, Theorem 5, and Theorem 6.

Section 6, wherein the goal is to prove Theorem 7, is more self-contained. The
idea is that if the point $x$ is regular in the sense of having equal
effective Hausdorff and effective packing dimensions, we get an essentially
optimal effective projection theorem. This allows us to take intervals as long
as we want when partitioning $|x-y|$, which makes it straightforward to
establish the bound of 1. A complication when performing the reduction to the
classical result is that regular sets do not necessarily contain sufficiently
many regular points, so we need a variant of the projection theorem that holds
for $x$’s that are _almost_ regular. As a consequence, we cannot take
arbitrarily long intervals when partitioning $|x-y|$, but as
$\dim_{H}(Y)>d_{y}>1$, we do not need arbitrarily long intervals to get the
bound of 1. Thus, the reduction goes through.

######  Remark.

For readers who want a relatively straightforward demonstration of the main
ideas of this paper, we suggest considering starting with section 6. The case
of almost regular $x$, while it does not follow from the previous sections,
has a similar structure to sections 3-5 without as many of the complications.

##  2\. Preliminaries

###  2.1. Kolmogorov complexity and effective dimension

The _conditional Kolmogorov complexity_ of binary string
$\sigma\in\\{0,1\\}^{*}$ given a binary string $\tau\in\\{0,1\\}^{*}$ is the
length of the shortest program $\pi$ that will output $\sigma$ given $\tau$ as
input. Formally, the conditional Kolmogorov complexity of $\sigma$ given
$\tau$ is

$K(\sigma\mid\tau)=\min_{\pi\in\\{0,1\\}^{*}}\left\\{\ell(\pi):U(\pi,\tau)=\sigma\right\\}\,,$

where $U$ is a fixed universal prefix-free Turing machine and $\ell(\pi)$ is
the length of $\pi$. Any $\pi$ that achieves this minimum is said to _testify_
to, or be a _witness_ to, the value $K(\sigma\mid\tau)$. The _Kolmogorov
complexity_ of a binary string $\sigma$ is $K(\sigma)=K(\sigma\mid\lambda)$,
where $\lambda$ is the empty string. We can easily extend these definitions to
other finite data objects, e.g., vectors in $\mathbb{Q}^{n}$, via standard
binary encodings. See [8] for details.

The _Kolmogorov complexity_ of a point $x\in\mathbb{R}^{m}$ at _precision_
$r\in\mathbb{N}$ is the length of the shortest program $\pi$ that outputs a
_precision- $r$_ rational estimate for $x$. Formally, this is

$K_{r}(x)=\min\left\\{K(p)\,:\,p\in
B_{2^{-r}}(x)\cap\mathbb{Q}^{m}\right\\}\,,$

where $B_{\varepsilon}(x)$ denotes the open ball of radius $\varepsilon$
centered on $x$. Note that this implies that the Kolmogorov complexity of a
point is non-decreasing in precision. The _conditional Kolmogorov complexity_
of $x$ at precision $r$ given $y\in\mathbb{R}^{n}$ at precision
$s\in\mathbb{R}^{n}$ is

$K_{r,s}(x\mid y)=\max\big{\\{}\min\\{K_{r}(p\mid q)\,:\,p\in
B_{2^{-r}}(x)\cap\mathbb{Q}^{m}\\}\,:\,q\in
B_{2^{-s}}(y)\cap\mathbb{Q}^{n}\big{\\}}\,.$

When the precisions $r$ and $s$ are equal, we abbreviate $K_{r,r}(x\mid y)$ by
$K_{r}(x\mid y)$. As a matter of notational convenience, if we are given a
non-integral positive real as a precision parameter, we will always round up
to the next integer. Thus $K_{r}(x)$ denotes $K_{\lceil r\rceil}(x)$ whenever
$r\in(0,\infty)$.

A basic property, proven by Case and J. Lutz [1] shows that the growth rate of
the Kolmogorov complexity of a point is essentially bounded by the dimension
of the ambient space. Since this paper concerns $\mathbb{R}^{2}$, we will
frequently use this in the form that for any $\varepsilon>0$, for sufficiently
large $s$ we have that

$K_{r+s}(x)\leq K_{r}(x)+2s+\varepsilon s$

We may _relativize_ the definitions in this section to an arbitrary oracle set
$A\subseteq\mathbb{N}$. We will frequently consider the complexity of a point
$x\in\mathbb{R}^{n}$ _relative to a point_ $y\in\mathbb{R}^{m}$, i.e.,
relative to an oracle set $A_{y}$ that encodes the binary expansion of $y$ is
a standard way. We then write $K^{y}_{r}(x)$ for $K^{A_{y}}_{r}(x)$. Oracle
access to the _entire_ binary expansion of a point is no less useful than
conditional access to that binary expansion only up to a certain precision.
Thus, we note that, for every $x\in\mathbb{R}^{n}$ and $y\in\mathbb{R}^{m}$,

(1) $K_{s,r}(x\mid y)\geq K^{y}_{s}(x)-O(\log r)-O(\log s),$

for every $s,r\in\mathbb{N}$

One of the most useful properties of Kolmogorov complexity is that it obeys
the _symmetry of information_. That is, for every
$\sigma,\tau\in\\{0,1\\}^{*}$,

$K(\sigma,\tau)=K(\sigma)+K(\tau\mid\sigma,K(\sigma))+O(1)\,.$

We also have the more technical lemmas detailing versions of symmetry of
information that hold for Kolmogorov complexity in $\mathbb{R}^{n}$. Lemma 8
was proved in the second author’s work [13].

######  Lemma 8 ([13]).

For every $m,n\in\mathbb{N}$, $x\in\mathbb{R}^{m}$, $y\in\mathbb{R}^{n}$, and
$r,s\in\mathbb{N}$ with $r\geq s$,

  1. (i)

$\displaystyle|K_{r}(x\mid y)+K_{r}(y)-K_{r}(x,y)\big{|}\leq O(\log
r)+O(\log\log|y|)\,.$

  2. (ii)

$\displaystyle|K_{r,s}(x\mid x)+K_{s}(x)-K_{r}(x)|\leq O(\log
r)+O(\log\log|x|)\,.$

A consequence of Lemma 8, is the following.

######  Lemma 9 ([13]).

Let $m,n\in\mathbb{N}$, $x\in\mathbb{R}^{m}$, $z\in\mathbb{R}^{n}$,
$\varepsilon>0$ and $r\in\mathbb{N}$. If $K^{x}_{r}(z)\geq K_{r}(z)-O(\log
r)$, then the following hold for all $s\leq r$.

  1. (i)

$\displaystyle K^{x}_{s}(z)\geq K_{s}(z)-O(\log r)\,.$

  2. (ii)

$\displaystyle K_{s,r}(x\mid z)\geq K_{s}(x)-O(\log r)\,.$

J. Lutz [10] initiated the study of effective dimensions (also known as
_algorithmic dimensions_) by effectivizing Hausdorff dimension using betting
strategies called  _gales_ , which generalize martingales. Mayordomo showed
that effective Hausdorff dimension can be characterized using Kolmogorov
complexity [14]. In this paper, we use this characterization as a definition.
The _effective Hausdorff dimension_ of a point $x\in\mathbb{R}^{n}$ is

$\dim(x)=\liminf_{r\to\infty}\frac{K_{r}(x)}{r}\,.$

The _effective packing dimension_ of a point $x\in\mathbb{R}^{n}$ is

$\operatorname{Dim}(x)=\limsup_{r\to\infty}\frac{K_{r}(x)}{r}\,.$

We can relativize both definitions, so that the effective Hausdorff and
packing dimension with respect to an oracle $A\subseteq\mathbb{N}$ are

$\dim^{A}(x)=\liminf_{r\to\infty}\frac{K^{A}_{r}(x)}{r}$ and
$\operatorname{Dim}^{A}(x)=\limsup_{r\to\infty}\frac{K^{A}_{r}(x)}{r}$

###  2.2. The Point-to-Set Principle

The _point-to-set principle_ shows that the Hausdorff and packing dimension of
a set can be characterized by the effective Hausdorff and effecive packing
dimension of its individual points. Specifically, J. Lutz and N. Lutz [11]
showed the following for arbitrary subsets of $\mathbb{R}^{n}$.

######  Theorem 10 (Point-to-set principle [11]).

Let $n\in\mathbb{N}$ and $E\subseteq\mathbb{R}^{n}$. Then

$\operatorname{dim_{H}}(E)=\adjustlimits{\min}_{A\subseteq\mathbb{N}}{\sup}_{x\in
E}\dim^{A}(x).$
$\operatorname{dim_{P}}(E)=\adjustlimits{\min}_{A\subseteq\mathbb{N}}{\sup}_{x\in
E}\operatorname{Dim}^{A}(x).$

Stated as above, it is clear that Hausdorff and pacing dimension are in a
certain respect dual to each other. The only difference is a limit inferior
versus a limit superior for the individual points. This immediately implies
that the packing dimension of a set is no less than its Hausdorff application.

The general point-to-set principle is extremely useful, but for some
applications, we would like to either remove the oracle, or at least be able
to say something about which oracles achieve the minimum. The first point-to-
set principle for Hausdorff dimension, which holds for a restricted class of
sets, was implicitly proven by Hitchcock [6] and J. Lutz [10].

A set $E\subseteq\mathbb{R}^{n}$ is effectively compact relative to $A$ if the
set of finite open covers of $E$ by rational balls is computably enumerable
relative to $A$.444The balls are rational in the sense that the coordinates of
the centers and the radii are all rational numbers, which allows us to
identify each ball by a finite string. We will use the fact that every compact
set is effectively compact relative to some oracle.

######  Theorem 11 ([6, 10]).

Let $E\subseteq\mathbb{R}^{n}$ and $A\subseteq\mathbb{N}$ be such that $E$ is
effectively compact relative to $A$. Then

$\operatorname{dim_{H}}(E)=\sup\limits_{x\in E}\dim^{A}(x)\,.$

######  Remark.

We only state this restricted point-to-set principle for Hausdorff dimension
because it is known that it fails for packing dimension, see [2]. Informally,
this can be seen to occur because effective compactness and Hausdorff
dimension both deal with covers, whereas it is hard to convert the covers we
have from effective compactness into usable information about packings.

In order to apply Theorem 11 to the pinned distance sets, we need the
following fact of computable analysis.

######  Observation 12.

Let $E\subseteq\mathbb{R}^{2}$ be a compact set and let $A\subseteq\mathbb{N}$
be an oracle relative to which $E$ is effectively compact. Then, for every
$x\in\mathbb{R}^{2}$, $\Delta_{x}E$ is effectively compact relative to
$(x,A)$.

###  2.3. Helpful lemmas

In this section, we recall several lemmas which were introduced by Lutz and
Stull [13, 12] and which will be used throughout the paper. Note that these
lemmas each relativize with the addition of an oracle $A$. The first lemma
shows that the precision to which we can compute $e$ given $x,w$ such that
$p_{e}x=p_{e}w$ depends linearly on the distance of $x$ and $w$.

######  Lemma 13 ([13]).

Let $z\in\mathbb{R}^{2}$, $e\in S^{1}$, and $r\in\mathbb{N}$. Let
$w\in\mathbb{R}^{2}$ such that $p_{e}z=p_{e}w$ up to precision $r$.555This
lemma was originally proven without the “up to precision $r$” qualifier, but
we rephrase like this to match the form we will use the lemma in. The
generalization is essentially immediate, because in this case there will be
some sufficiently close point to $w$ with _exactly_ the same projection as
$z$, indistinguishable from $w$ at precision $r$. Then

$K_{r}(w)\geq K_{t}(z)+K_{r-t,r}(e\mid z)+O(\log r)\,,$

where $t:=-\log|z-w|$.

We will commonly need to lower the complexity of points at specified
positions. The following lemma shows that conditional complexity gives a
convenient way to do this.

######  Lemma 14 ([13]).

Let $z\in\mathbb{R}^{2}$, $\eta\in\mathbb{Q}_{+}$, and $r\in\mathbb{N}$. Then
there is an oracle $D=D(r,z,\eta)$ with the following properties.

  * (i)

For every $t\leq r$,

$K^{D}_{t}(z)=\min\\{\eta r,K_{t}(z)\\}+O(\log r)\,.$

  * (ii)

For every $m,t\in\mathbb{N}$ and $y\in\mathbb{R}^{m}$,

$K^{D}_{t,r}(y\mid z)=K_{t,r}(y\mid z)+O(\log r)\,,$

and

$K_{t}^{z,D}(y)=K_{t}^{z}(y)+O(\log r)\,.$

  * (iii)

If $B\subseteq\mathbb{N}$ satisfies $K^{B}_{r}(z)\geq K_{r}(z)-O(\log r)$,
then

$K_{r}^{B,D}(z)\geq K_{r}^{D}(z)-O(\log r)\,.$

  * (iv)

For every $t\in\mathbb{N}$, $u\in\mathbb{R}^{n},w\in\mathbb{R}^{m}$

$K_{r,t}(u\mid w)\leq K^{D}_{r,t}(u\mid w)+K_{r}(z)-\eta r+O(\log r)\,.$

In particular, this oracle $D$ encodes $\sigma$, the lexicographically first
time-minimizing witness to $K(z{\upharpoonright}r\mid z{\upharpoonright}s)$,
where $s=\max\\{t\leq r\,:\,K_{t-1}(z)\leq\eta r\\}$.

The final lemma in this section is a crucial tool at several points of the
argument. Under certain conditions, it lets us lower bound the complexity
growth of the $|x-y|$ by the complexity growth of $y$ on particular intervals.

######  Lemma 15.

Suppose that $x,y\in\mathbb{R}^{2}$, $t<r\in\mathbb{N}$, and
$\eta,\varepsilon\in\mathbb{Q}_{+}$ satisfy the following conditions.

  * (i)

$K_{r}(y)\leq\left(\eta+\frac{\varepsilon}{2}\right)r$.

  * (ii)

For every $w\in B_{2^{-t}}(y)$ such that $|x-y|=|x-w|$,

$K_{r}(w)\geq\eta r+\min\\{\varepsilon r,r-s-\varepsilon r\\}\,,$

where $s=-\log|y-w|\leq r$.

Then for every oracle set $A\subseteq\mathbb{N}$,

$K_{r,t}^{A,x}(y\mid y)\leq K^{A,x}_{r,t}(|x-y|\mid y)+3\varepsilon
r+K(\varepsilon,\eta)+O(\log r)\,.$

##  3\. Projection theorem

The main goal of this section is to prove the following projection theorem:

######  Theorem 16.

Let $x\in\mathbb{R}^{2}$, $e\in\mathcal{S}^{1}$,
$\varepsilon\in\mathbb{Q}^{+}$, $C\in\mathbb{N}$, $A\subseteq\mathbb{N}$, and
$t,r\in\mathbb{N}$. Suppose that $r$ is sufficiently large, and that the
following hold.

  1. (P1)

$1<d\leq\dim^{A}(x)\leq\operatorname{Dim}^{A}(x)\leq D$.

  2. (P2)

$t\geq\frac{d(2-D)}{2}r$.

  3. (P3)

$K^{x,A}_{s}(e)\geq s-C\log s$, for all $s\leq t$.

Then

$K^{A}_{r}(x\,|\,p_{e}x,e)\leq\max\\{\frac{D-1}{D}(dr-t)+K^{A}_{r}(x)-dr,K^{A}_{r}(x)-r\\}+\varepsilon
r.$

This projection has somewhat more restrictive hypotheses than the projection
theorem of [20]. Namely, depending on $D$, we may have a rather large lower
bound on $t$. However, in the next section when we will need to apply this
projection theorem, if $t$ is smaller than the above, it is easy to deduce the
desired result without reference to this theorem. We will begin by introducing
some definitions and tools from [20] which will be of use in proving the
modified projection theorem.

###  3.1. Projection preliminaries

We need to consider $K^{A}_{s}(x)$ as a function of $s$. For convenience, we
define $f:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ to be the piece-wise linear
function which agrees with $K^{A}_{s}(x)$ on the integers such that

$f(a)=f(\lfloor a\rfloor)+(a-\lfloor a\rfloor)(f(\lceil a\rceil)-f(\lfloor
a\rfloor))$,

for any non-integer $a$. Note that $f$ is non-decreasing since $K^{A}_{r}(x)$
is, and, for every $a<b\in\mathbb{N}$,

$f(b)-f(a)\leq 2(b-a)+O(\log\lceil b\rceil)$.

That is, the maximal growth rate of $f$ on large intervals is about 2.

There are several specials kinds of intervals on which we can bound the
complexity of projections.

  * •

An interval $[a,b]$ is called teal if $f(b)-f(c)\leq b-c$ for every $a\leq
c\leq b$.

  * •

An interval $[a,b]$ is called yellow if $f(c)-f(a)\geq c-a$ for every $a\leq
c\leq b$.

More concretely, these intervals are useful due to the following proposition,
which is Corollary 16 in [20]:

######  Proposition 17.

Let $A\subseteq\mathbb{N}$,
$x\in\mathbb{R}^{2},e\in\mathcal{S}^{1},\varepsilon\in\mathbb{Q}_{+}$,
$C\in\mathbb{N}$ and $t<r\in\mathbb{R}_{+}$. Suppose that $r$ is sufficiently
large and $K^{A,x}_{s}(e)\geq s-C\log r$, for all $s\leq r-t$. Then the
following hold.

  1. (1)

If $[t,r]$ is yellow,

$K^{A}_{r,r,r,t}(x\mid p_{e}x,e,x)\leq K^{A}_{r,t}(x\mid x)-(r-t)+\varepsilon
r.$

  2. (2)

If $[t,r]$ is teal,

$K^{A}_{r,r,r,t}(x\mid p_{e}x,e,x)\leq\varepsilon r.$

We denote the set of teal intervals by $T$ and the set of yellow intervals by
$Y$.

Supposing that a partition of $[1,r]$ consists of only yellow and teal
intervals, and has essentially a constant number of terms, we could repeatedly
apply symmetry of information to 17 and deduce a useful bound for
$K^{A}_{r}(x\,|\,p_{e}x,e)$. We make the notion of such an “admissible”
partition more precise: a partition
$\mathcal{P}=\\{[a_{i},a_{i+1}]\\}_{i=0}^{k}$ of closed intervals with
disjoint interiors is $(M,r,t)$-admissible if $[1,r]=\cup_{i}[a_{i},a_{i+1}]$,
and it satisfies the following conditions.

  * (A1)

$k\leq M$,

  * (A2)

$[a_{i},a_{i+1}]$ is either yellow or teal,

  * (A3)

$a_{i+1}\leq a_{i}+t$.

We can repeatedly apply the symmetry of information to write the complexity
$K^{A}_{r}(x\mid p_{e}x,e)$ as a sum of complexities over a partition of
$[1,r]$, allowing us to apply 17. This idea is encapsulated by the following
result in [20].

######  Lemma 18.

Suppose that $x\in\mathbb{R}^{2}$, $e\in\mathcal{S}^{1}$,
$\varepsilon\in\mathbb{Q}^{+}$, $C\in\mathbb{N}$, $t,r\in\mathbb{N}$ satisfy
(P1)-(P3). If $\mathcal{P}=\\{[a_{i},a_{i+1}]\\}_{i=0}^{k}$ is an
$(3C,r,t)$-admissible partition, and $r$ is sufficiently large, then

$\displaystyle K^{A}_{r}(x\mid p_{e}x,e)$ $\displaystyle\leq\varepsilon
r+\sum\limits_{i\in\textbf{Bad}}K^{A}_{a_{i+1},a_{i}}(x\mid
x)-(a_{i+1}-a_{i}),$

where

Bad $=\\{i\leq k\mid[a_{i},a_{i+1}]\notin T\\}$.

Note that admissible partitions of specified intervals always exist, as per
the following lemma:

######  Lemma 19.

Let $x\in\mathbb{R}^{2}$, $r,C\in\mathbb{N}$ and $\frac{r}{C}\leq t<r$. For
any $0\leq a<b\leq r$, there is an $(3C,r,t)$-admissible partition of $[a,b]$.

However, a partition merely being admissible isn’t enough to establish the
desired bounds. We can do better by consider the special intervals which are
both yellow and teal.

  * •

An interval $[a,b]$ green if it is yellow and teal and $b-a\leq t$.

Green intervals are often advantageous because they combine the best of yellow
intervals (complexity of $x$ grows superlinearly) and the best of teal
intervals (we can compute $x$ with few bits given its projection). We denote
the set of green intervals by $G$. We now introduce two more types of
intervals to formulate a few results pertaining to green intervals.

  * •

An interval $[a,b]$ is called red if $f$ is strictly increasing on $[a,b]$.

  * •

An interval $[a,b]$ is called blue if $f$ is constant on $[a,b]$.

In [20], a partition $\hat{\mathcal{P}}=\hat{\mathcal{P}}(x,r,t)$ of $[1,r]$
with the following properties is constructed:

  * •

The interiors of the elements of $\hat{\mathcal{P}}$ are disjoint.

  * •

Each interval is red, blue, or green.

  * •

If $[a,b]$ is red and $[b,c]$ is blue (not necessarily in
$\hat{\mathcal{P}}$), then $b$ is contained in the interior of a green
interval in $\hat{\mathcal{P}}$. Moreover, any $b$ that’s contained in _any_
green interval is contained in a green interval in $\hat{\mathcal{P}}$.

  * •

Suppose $I_{0},\ldots,I_{n+1}$ is a a red-green-blue sequence in
$\hat{\mathcal{P}}$ i.e. a sequence $I_{0},\ldots,I_{n+1}$ of consecutive
intervals in $\hat{\mathcal{P}}$ such that $I_{0}$ is red,
$I_{1},\ldots,I_{n}$ are green, and $I_{n+1}$ is blue. Then the total length
of $I_{1},\ldots,I_{n}$ is at least $t$.

Call a maximal collection of consecutive green intervals a green block. The
last property, that green blocks preceded by a red and succeeded by a blue
interval have length at least $t$, will be particularly important. Informally,
this property holds because if a green interval had length less than $t$ with
red on the left and blue on the right, it would always be possible to lengthen
the green by consuming some of the blue and red.

The final fact from [20] we need in this section is the following: if there is
no red-green-blue sequence in $\hat{\mathcal{P}}=\hat{\mathcal{P}}(x,r,t)$,
then there is an essentially all yellow admissible partition of $[1,r]$. More
specifically, in this case there is an admissible partition $\mathcal{P}$ such
that for some $c$ not depending on $r$, if $c\leq a_{i}<a_{i+1}$ and
$[a_{i},a_{i+1}]\in P$, then $[a_{i},a_{i+1}]$ is yellow. Intuitively, this is
because if a blue interval appears after a red interval, there has to be a
red-green-blue sequence somewhere in between. $\dim(x)>1$, so after a certain
point there has to be a red interval. Consequently, after a certain point,
there can only be red or green intervals, which we can convert into an all-
yellow partition of $[c,r]$.

######  Remark.

In fact, it is easy to convert a partition of any subinterval of $[1,r]$
consisting of only red and green intervals into an all-yellow $3C$-admissible
partition of the subinterval. Just observe that green intervals are yellow,
any subinterval of a red interval is yellow, and the union of adjacent yellow
intervals is yellow. Greedily combining the red and green intervals from the
left to the right and beginning a new yellow interval when the length of the
previous yellow is about to exceed $t$ accomplishes this.

With these definitions and tools, we can now prove the modified projection
theorem.

###  3.2. Proof of the projection theorem

######  Theorem 16.

Let $x\in\mathbb{R}^{2}$, $e\in\mathcal{S}^{1}$,
$\varepsilon\in\mathbb{Q}^{+}$, $C\in\mathbb{N}$, $A\subseteq\mathbb{N}$, and
$t,r\in\mathbb{N}$. Suppose that $r$ is sufficiently large, and that the
following hold.

  1. (P1)

$1<d\leq\dim(x)\leq\operatorname{Dim}(x)\leq D$.

  2. (P2)

$t\geq\frac{d(2-D)}{2}r$.

  3. (P3)

$K^{A,x}_{s}(e)\geq s-C\log s$, for all $s\leq t$.

Then

$K^{A}_{r}(x\,|\,p_{e}x,e)\leq\max\\{\frac{D-1}{D}(dr-t)+K^{A}_{r}(x)-dr,K^{A}_{r}(x)-r\\}+\varepsilon
r.$

###### Proof.

Let $x$ be as in the statement of the theorem, $r$ sufficiently large, and
$t\geq\frac{d(2-D)}{2}r$. Let $\hat{P}=\hat{P}(x,r,t)$ be a partition of
$[1,r]$ satisfying the properties described in the last section. Let $S$ be
the number of red-green-blue sequences in $\hat{P}$. Note that
$S<\frac{2}{d(2-D)}$, since the green block in each red-green-blue sequence is
at least length $t$, and these blocks have to be separated from each other by
some amount.

The case $S$ = 0: In this case, there are no red-green-blue sequences, so let
$\mathcal{P}$ be the all yellow $3C$-admissible partition guaranteed by last
fact of the previous section.

$\sum\limits_{I_{i}\in\mathcal{P}-Y}a_{i+1}-a_{i}\leq c,$

for some constant $c$, and so for sufficiently large $r$

(2) $B:=\sum\limits_{I_{i}\in\mathcal{P}\cap Y}a_{i+1}-a_{i}\geq
r-\frac{\varepsilon r}{2}.$

By symmetry of information, we can write

$\displaystyle K^{A}_{r}(x)$
$\displaystyle\geq\sum\limits_{I_{i}\in\mathcal{P}}K^{A}_{a_{i+1},a_{i}}(x\mid
x)-O(\log r)$ $\displaystyle\geq\sum\limits_{I_{i}\in\mathcal{P}\cap
Y}K^{A}_{a_{i+1},a_{i}}(x\mid x)-O(\log r)$
$\displaystyle\geq-\frac{\varepsilon
r}{4}+\sum\limits_{I_{i}\in\mathcal{P}\cap Y}K^{A}_{a_{i+1},a_{i}}(x\mid x)$

To apply Lemma 18 we note that, on green intervals, $K^{A}_{a,b}(x\mid
x)=b-a$. Therefore, we see that

[Lemma 18] $\displaystyle K^{A}_{r}(x)$ $\displaystyle\geq K^{A}_{r}(x\mid
p_{e}x,e)+B-\frac{\varepsilon r}{2}$ $\displaystyle\geq K^{A}_{r}(x\mid
p_{e},x,e)+r-\varepsilon r.$

Thus,

(3) $K^{A}_{r}(x\mid p_{e}x,e)\leq K^{A}_{r}(x)-r+\varepsilon r,$

and the conclusion follows.

The case $S$ = 1: Now, suppose there is exactly one red-green-blue sequence in
$\hat{\mathcal{P}}$. Then there is a precision $1<r_{1}<r-t$ and an $s\geq t$
such that $[r_{1},r_{1}+s]$ is green in $\hat{\mathcal{P}}$. Let
$\mathcal{P}_{1}$ be a $3C$-admissible partition of $[1,r_{1}]$, and
$\mathcal{P}_{2}$ be a $3C$-admissible partition of $[r_{1}+s,r]$, guaranteed
by Lemma 19. Since there is exactly one red-green-blue sequence in
$\hat{\mathcal{P}}$, $\mathcal{P}_{1}$ contains no red-green-blue sequences.
Therefore, using the same argument as in the previous case, $\mathcal{P}_{1}$
is essentially covered by yellow intervals and we conclude that

$\displaystyle K^{A}_{r_{1}}(x\mid p_{e}x,e)$ $\displaystyle\leq
K^{A}_{r_{1}}(x)-r_{1}+\frac{\varepsilon r_{1}}{4}$
$\displaystyle(D-1)r_{1}+\frac{\varepsilon r_{1}}{2}.$

Let $r_{2}\geq r_{1}+s$ be minimal precision such that $[r_{2},r]$ is the
union of yellow intervals666We allow $r_{2}$ to be equal to $r$, in the case
that $[r_{1}+s,r]$ is covered by teal intervals. Therefore we have

$\displaystyle K^{A}_{r}(x\mid p_{e}x,e)$ $\displaystyle\leq
K^{A}_{r_{1}}(x)-r_{1}+K^{A}_{r,r_{2}}(x\mid x)-(r-r_{2})+\varepsilon r$
$\displaystyle\leq\left(D-1\right)r_{1}+K^{A}_{r,r_{2}}(x\mid
x)-(r-r_{2})+\varepsilon r$
$\displaystyle\leq\left(D-1\right)r_{1}+\left(d-1\right)\left(r-r_{2}\right)+K^{A}_{r}(x)-dr+\varepsilon
r$ $\displaystyle\leq\left(D-1\right)B+K^{A}_{r}(x)-dr+\varepsilon r.$

If $B\leq\frac{dr-t}{D}$, the conclusion follows. So, we assume that
$B>\frac{dr-t}{D}$. Hence,

$\displaystyle K^{A}_{r}(x\mid p_{e}x,e)$ $\displaystyle\leq
K^{A}_{r}(x)-s-B+\varepsilon r$ $\displaystyle\leq
K^{A}_{r}(x)-t-B+\varepsilon r$
$\displaystyle<K^{A}_{r}(x)-t-\frac{dr-t}{D}+\varepsilon r$
$\displaystyle=K^{A}_{r}(x)-dr+\frac{D-1}{D}\left(dr-t\right)+\varepsilon r,$

and the conclusion follows.

The case $S\geq 2$: We now consider the case that there are at least two red-
green-blue sequence in $\hat{P}$. Let

(4) $L=\sum\limits_{I_{i}\in\mathcal{P}\cap G}a_{i+1}-a_{i}$

be the total length of the green intervals in $\mathcal{P}$. In this case we
have $L\geq 2t$. Let

(5) $B=\sum\limits_{i\in\textbf{Bad}}a_{i+1}-a_{i}$

be the total length of the bad (non-teal) intervals in $\mathcal{P}$.

We first prove that

(6) $K^{A}_{r}(x\mid p_{e}x,e)\leq\min\\{K^{A}_{r}(x)-B-2t,B\\}+\varepsilon
r.$

Since $x$ is an element of $\mathbb{R}^{2}$,

$K^{A}_{a_{i+1},a_{i}}(x\mid x)\leq 2(a_{i+1}-a_{i})+O(\log r).$

Therefore, by Lemma 18, with respect to $\varepsilon/4$,

(7) $K^{A}_{r}(x\mid p_{e}x,e)\leq\frac{\varepsilon r}{2}+B.$

By repeated applications of the symmetry of information,

$\displaystyle K^{A}_{r}(x)$ $\displaystyle\geq-\frac{\varepsilon
r}{2}+\sum\limits_{I_{i}\in\mathcal{P}\cap T}K^{A}_{a_{i+1},a_{i}}(x\mid
x)+\sum\limits_{i\in\textbf{Bad}}K^{A}_{a_{i+1},a_{i}}(x\mid x)$
$\displaystyle\geq-\frac{\varepsilon
r}{2}+\sum\limits_{I_{i}\in\mathcal{P}\cap G}K^{A}_{a_{i+1},a_{i}}(x\mid
x)+\sum\limits_{i\in\textbf{Bad}}K^{A}_{a_{i+1},a_{i}}(x\mid x)$
$\displaystyle=-\frac{\varepsilon
r}{2}+L+\sum\limits_{i\in\textbf{Bad}}K^{A}_{a_{i+1},a_{i}}(x\mid x)$ (8)
$\displaystyle\geq 2t+K^{A}_{r}(x\mid p_{e}x,e)+B-\varepsilon r$

Combining (7) and (8) proves inequality (6).

By inequality (6), if

$B\leq K^{A}_{r}(x)-dr+\frac{D-1}{D}(dr-t),$

we are done, so we assume otherwise. Applying (6) again and using our
assumption on $t$ implies that

$\displaystyle K^{A}_{r}(x\mid p_{e}x,e)$ $\displaystyle\leq
K^{A}_{r}(x)-2t-B+\varepsilon r$
$\displaystyle<\frac{d}{D}r-\frac{D+1}{D}t+\varepsilon r$
$\displaystyle\leq\frac{D-1}{D}(dr-t)+\varepsilon r$ $\displaystyle\leq
K^{A}_{r}(x)-dr+\frac{D-1}{D}\left(dr-t\right)+\varepsilon r,$

and the proof is complete. ∎

##  4\. Effective dimension of distances

In the previous section, we considered partitions of the interval $[1,r]$
depending on the complexity function of our pinned point $x$. In particular,
we were able to use these partitions to get a bound on the complexity of $x$
given $e$ and the projection of $x$ in the direction of $e$. Now, we need to
consider the complexity function of $y$ and relate this to the complexity of
$|x-y|$. Similar to before, we let $f:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$
be the piece-wise linear function which agrees with $K^{A}_{s}(y)$ on the
integers, and

$f(a)=f(\lfloor a\rfloor)+(a-\lfloor a\rfloor)(f(\lceil a\rceil)-f(\lfloor
a\rfloor))$,

for any non-integer $a$. Since

$K^{A}_{s}(y)\leq K^{A}_{s+1}(y)$

for every $s\in\mathbb{N}$, $f$ is non-decreasing and since
$y\in\mathbb{R}^{2}$, for every $a<b\in\mathbb{R}$,

$f(b)-f(a)\leq 2(b-a)+O(\log\lceil b\rceil)$.

As before, we make the following definitions: an interval $[a,b]$ is called
teal if $f(b)-f(c)\leq b-c$ for every $c\in[a,b]$. It is called yellow if
$f(c)-f(a)\geq c-a$, for every $c\in[a,b]$. We denote the set of teal
intervals by $T$ and the set of yellow intervals by $Y$.

For reference, here we list some conditions that our points $x$ and $y$ will
be assumed to satisfy throughout the remainder of this section. Let
$x,y\in\mathbb{R}^{2}$, $e=\frac{x-y}{|x-y|}$ and $A,B\subseteq\mathbb{N}$.
For this section, we let $d_{x}=\dim^{A}(x)$,
$D_{x}=\operatorname{Dim}^{A}(x)$, $d_{y}=\dim^{A}(y)$ and
$D_{y}=\operatorname{Dim}^{A}(y)$. We will assume that $x$ and $y$ satisfy the
following conditions.

  * (C1)

$d_{x},d_{y}>1$

  * (C2)

$K^{x,A}_{r}(e)=r-O(\log r)$ for all $r$.

  * (C3)

$K^{x,A,B}_{r}(y)\geq K^{A}_{r}(y)-O(\log r)$ for all sufficiently large $r$.

  * (C4)

$K^{A}_{r}(e\mid y)=r-o(r)$ for all $r$.

###  4.1. Complexity of distances on yellow and teal intervals

As compared to the corresponding part of [20], we’ll need to partition $[1,r]$
more carefully. However, similar to the proof of the projection theorem in the
previous section, there are a few tools from [20] that we can reuse.

######  Lemma 20.

Suppose that $A\subseteq\mathbb{N}$, $x,y\in\mathbb{R}^{2}$ and
$e=\frac{x-y}{|x-y|}$ satisfy (C1)-(C4) for every $r\in\mathbb{N}$. Then for
every $\varepsilon\in\mathbb{Q}_{+}$ and all sufficiently large
$r\in\mathbb{N}$, the following hold.

  1. (1)

If $[t,r]$ is yellow and $t\leq r\leq 2t$

$K^{A,x}_{r,r,t}(y\mid|x-y|,y)\leq K^{A}_{r,t}(y\mid y)-(r-t)+\varepsilon r.$

  2. (2)

If $[t,r]$ is teal, and $t\leq r\leq 2t$,

$K^{A,x}_{r,r,t}(y\mid|x-y|,y)\leq\varepsilon r.$

We say that a partition $\mathcal{P}=\\{[a_{i},a_{i+1}]\\}_{i=0}^{k}$ of
intervals with disjoint interiors is good if $[1,r]=\cup_{i}[a_{i},a_{i+1}]$
and it satisfies the following conditions.

  * (G1)

$[a_{i},a_{i+1}]$ is either yellow or teal,

  * (G2)

$a_{i+1}\leq 2a_{i}$, for every $i$ and

  * (G3)

$a_{i+2}>2a_{i}$ for every $i<k$.

Note that (G3) ensures that the errors do not pile up. Furthermore, observe
that (G2) is somewhat different than the admissibility condition in the
previous section. There, we had that an interval could not be longer than $t$:
essentially some fixed quantity, at least when partitioning. Now, the
requirement is that the intervals cannot be any more than ”doubling”, so the
best we can hope for in a partition is a logarithmic number terms. Indeed,
just as we had admissible partitions for every $[a,b]$, the following lemma
guarantees the existence of good partitions.

######  Lemma 21.

For every $y\in\mathbb{R}^{2}$ and every $r\in\mathbb{N}$, there is a good
partition of $[1,r]$.

The following lemma uses repeated applications of the symmetry of information
to write $K^{x}_{r}(y\mid|x-y|)$ as a sum of its complexity on the intervals
of a partition. The conclusion then follows via Lemma 20.

######  Lemma 22.

Let $A\subseteq\mathbb{N}$. Let $\mathcal{P}=\\{[a_{i},a_{i+1}]\\}_{i=0}^{k}$
be a good partition. Then

$\displaystyle K^{A,x}_{r}(y\mid|x-y|)$ $\displaystyle\leq\varepsilon
r+\sum\limits_{i\in\textbf{Bad}}K^{A}_{a_{i+1},a_{i}}(y\mid
y)-(a_{i+1}-a_{i}),$

where

Bad $=\\{i\leq k\mid[a_{i},a_{i+1}]\notin T\\}$.

So applying the previous lemma with $\frac{\varepsilon}{2}$, absorbing the log
term for sufficiently large $r$, and recalling condition (C3), we have that

(9) $K^{x,A}_{r}(|x-y|)\geq
K^{A}_{r}(y)-\sum\limits_{i\in\textbf{Bad}}K^{A}_{a_{i+1},a_{i}}(y\mid
y)-(a_{i+1}-a_{i})-\varepsilon r,$

Constructing a particular good partition to optimize this bound - either at
every precision or well-chosen precisions - will be crucial to proving a bound
on the effective Hausdorff and effective packing dimension of such points
(respectively) and will thus be a key goal of the remainder of this section.

###  4.2. Sufficient conditions for an all-yellow partition

We will describe a more general partition strategy in the next subsection, but
here we will introduce a related partition for a simpler scenario. In
particular, we will discuss situations where we can guarantee the existence of
a good partition consisting (essentially) of only yellow intervals which are
not more than doubling. To see why this is significant, observe that if we had
such a partition $\mathcal{P}$, equation 9, together with the observation that
the complexity of $y$ grows at an average rate of exactly 1 on yellow
intervals that are _also_ green, implies that for sufficiently large $r$

$\displaystyle K^{x,A}_{r}(|x-y|)$ $\displaystyle\geq
K^{A}_{r}(y)-\sum\limits_{i\in\mathcal{P}}K^{A}_{a_{i+1},a_{i}}(y\mid
y)-(a_{i+1}-a_{i})-\frac{\varepsilon}{2}r$ $\displaystyle\geq
K^{A}_{r}(y)-K^{A}_{r}(y)+r-\varepsilon r$ $\displaystyle=(1-\varepsilon)r$

Since we can take $\varepsilon$ to be as small as desired, this implies the
dimension of the distance is 1. We now state the necessary conditions and make
the above argument more rigorous.

######  Proposition 23.

Suppose that, in addition to conditions $(C1)-(C4)$, we also have that
$D_{y}<2d_{y}-1$. Then $\dim^{x,A}(|x-y|)=1$.

Intuitively, this extra requirement expresses that, if $y$ is semi-regular,
then we have the same conclusion as if $y$ is regular (in the sense of having
equal effective Hausdorff and effective packing dimension). As long as these
dimensions do not differ by too much, we can find an all-yellow partition. To
see why we have this bound specifically, consider the adversary complexity
function in Figure 1. We can only work with yellow intervals that are at most
doubling, so we want to choose $D_{y}$ and $d_{y}$ to guarantee that the
average growth rate of the complexity from $\frac{r}{2}$ to $r$ is at least 1.
Maximizing $K^{A}_{\frac{r}{2}}(y)$ and minimizing $K^{A}_{r}(y)$ allows us to
conclude the above when $D_{y}<2d_{y}-1$. Now, we prove the proposition.

  * Proof of Proposition 23.

Pick an $\varepsilon>0$ small enough that $d_{x}-\frac{\varepsilon}{4}>1$ and
$D_{y}+\frac{\varepsilon}{4}<2(d_{y}-\frac{\varepsilon}{4})-1$. For all $r$
sufficiently large, we have that
$(d_{y}-\frac{\varepsilon}{4})s<K^{A}_{s}(y)<(D_{y}+\frac{\varepsilon}{4})s$
whenever $s\geq\frac{\varepsilon}{4}r$. We now construct a partition of the
interval $[\frac{\varepsilon}{2}r,r]$.

Set $r_{0}=r$. Given $r_{i}$, first check if
$r_{i}\leq\frac{\varepsilon}{2}r$. If it is, let $i=n$ and we are done. If
not, we let $r_{i+1}$ be the largest value of $s$ such that
$K^{A}_{s}(y)=K^{A}_{\frac{r_{i}}{2}}(y)+(s-\frac{r_{i}}{2})$. Note that
$\frac{r_{i}}{2}>\frac{\varepsilon}{4}r$, so the inequalities at the start of
the proof hold in the interval we consider on this step. First, we show that
$r_{i+1}<r_{i}$. To see this, observe that

$K^{A}_{\frac{r_{i}}{2}}(y)+(s-\frac{r_{i}}{2})<s+(D_{y}+\frac{\varepsilon}{4}-\frac{1}{2})r_{i}$

On the other hand,

$K^{A}_{s}(y)>(d_{y}-\frac{\varepsilon}{4})s,$

so for an $s$ satisfying the above equation, we have

$s<\dfrac{\frac{D_{y}}{2}-\frac{1}{2}+\frac{\varepsilon}{8}}{d_{y}-1-\frac{\varepsilon}{4}}r_{i}<r_{i}.$

Here, the second inequality follows from our choice of $\varepsilon$. Now, we
define the partition $\mathcal{P}$ to be
$[1,r_{n}],[r_{n},r_{n-1}],...,[r_{1},r_{0}]$.

We now claim that each $[r_{i+1},r_{i}]$ is a yellow interval which is at most
doubling. If it were not yellow, we would have some
$s^{\prime}\in[r_{i+1},r_{i}]$ such that
$K^{A}_{s^{\prime}}(y)-K^{A}_{r_{i+1}}(y)<s^{\prime}-r_{i+1}$. This implies
that
$K^{A}_{s^{\prime}}(y)<K^{A}_{\frac{r_{i}}{2}}(y)+(s^{\prime}-\frac{r_{i}}{2})$.
However,
$K^{A}_{r_{i}}(y)>K^{A}_{\frac{r_{i}}{2}}(y)+(r_{i}-\frac{r_{i}}{2})$, so by
the intermediate value theorem, there is some
$s^{\prime\prime}\in(s^{\prime},r_{i})$ such that
$K^{A}_{s^{\prime\prime}}(y)=K^{A}_{\frac{r_{i}}{2}}(y)+(s^{\prime\prime}-\frac{r_{i}}{2})$,
contradicting that $r_{i+1}$ was the maximal such precision. Finally,
$[r_{i+1},r_{i}]$ is at most doubling because $r_{i+1}$ cannot be any less
than $\frac{r_{i}}{2}$, as
$K^{A}_{\frac{r_{i}}{2}}(y)=K^{A}_{\frac{r_{i}}{2}}(y)+(\frac{r_{i}}{2}-\frac{r_{i}}{2})$.
Thus we have a partition of $[1,r]$ where all but the first interval are
yellow.

$K^{A}_{s}(y)$$r$$r/2$$(d_{y}-\varepsilon/4)r$$(D_{y}+\varepsilon/4)r$$K^{A}_{s}(y)$$r=r_{0}$$r/2$$(d_{y}-\varepsilon/4)r$$(D_{y}+\varepsilon/4)r$$r_{1}$
Figure 1. On the left, the adversary complexity function that grows as quickly
as possible (given $D_{y}$) and then levels off. On the right, an
implementation of the procedure, generating a yellow interval $[r_{1},r]$ by
sending out a line of slope 1 from
$\left(\frac{r}{2},K^{A}_{\frac{r}{2}}(y)\right)$ and then finding the last
intersection of this line with $K^{A}_{s}(y)$.

We want to apply Lemma 22, so we make $\mathcal{P}$ into a good partition by
taking a good partition $\mathcal{P}_{[1,r_{n}]}$ of the first interval
$[1,r_{n}]$ and replacing it in $\mathcal{P}$ with $\mathcal{P}_{[1,r_{n}]}$.
As for the remaining intervals, the union of yellow intervals is still yellow,
so simply greedily combine them from the left to the right. Start a new yellow
interval each time adding the next $[r_{i+1},r_{i}]$ would make the current
yellow interval more than doubling. For ease of notation, continue to denote
this modification of $\mathcal{P}$ by $\mathcal{P}$. The conditions being
satisfied, we apply Lemma 22 relative to $A$ with $\frac{\varepsilon}{2}$ via
(9), obtaining:

$\displaystyle K^{x,A}_{r}(|x-y|)$ $\displaystyle\geq
K^{A}_{r}(y)-\frac{\varepsilon}{2}r\sum\limits_{i\in\mathcal{P}\setminus\mathcal{P}_{[1,r_{n}]}}K^{A}_{a_{i+1},a_{i}}(y\mid
y)-(a_{i+1}-a_{i})$ $\displaystyle\geq
K^{A}_{r}(y)-(K^{A}_{r}(y)-r+\frac{\varepsilon}{2}r)-\frac{\varepsilon}{2}r$
$\displaystyle=(1-\varepsilon)r$

Since we only needed $r$ to be sufficiently large,

$\dim^{x,A}(|x-y|)\geq 1-\varepsilon.$

and taking a sequence of $\varepsilon$ going to 0 gives the desired
conclusion.

###  4.3. Constructing a general partition

In this subsection, we describe a partitioning strategy that works outside of
the special case considered in Proposition 23. The key limitation of the
previous subsection was that we could only use intervals that were at most
doubling, which we now would like to enhance - at least for certain intervals
- using the projection theorem of section 3. The new partition will involve a
combination of yellow intervals and certain teal intervals, with the teal
intervals chosen so we can apply Theorem 16 to understand the complexity
growth of $|x-y|$ on them. To begin, fix a precision $r\in\mathbb{N}$. To keep
the expressions involved reasonably brief, we set

$d=\min\\{d_{x},d_{y}\\}$ and $D=\max\\{D_{x},D_{y}\\}$.777It would be
possible to obtain a somewhat better bound in Theorem 5 that more freely
involves $d_{x},d_{y},D_{x},$ and $D_{y}$ using the same approach of this
section, at the cost of significantly worse calculations.

Our goal is to give a lower bound on the complexity $K^{A,x}_{r}(|x-y|)$ at
precision $r$. We will first define a sequence $r=r_{0}>r_{1}>\ldots>r_{k}=1$
of precisions. We then prove a lower bound of the complexity
$K^{A}_{r_{i+1},r_{i}}(|x-y|\mid|x-y|)$ on each interval of the resulting
partition of $[1,r]$.

Constructing the partition $\mathcal{P}$: We define the sequence $\\{r_{i}\\}$
inductively. To begin, we set $r_{0}=r$. Having defined the sequence up to
$r_{i}$, we choose $r_{i+1}$ as follows. Let $a\leq r_{i}$ be the minimal real
such that $[a,r_{i}]$ can be written as the union of yellow intervals whose
lengths are at most doubling. If $a<r_{i}$, then we set $r_{i+1}=a$. In this
case, we will refer to $[r_{i+1},r_{i}]$ as a yellow interval of
$\mathcal{P}$.

Otherwise, let $t_{i}<r_{i}$ be the maximum of all reals such that

(10) $f(t)=f(r_{i})+\frac{D-1}{D}\left(dr_{i}-(d+1)t\right)-d(r_{i}-t).$

Let $t_{i}^{\prime}<r_{i}$ be the largest real such that
$f(r_{i})=f(t^{\prime}_{i})+r_{i}-t_{i}^{\prime}$. Note that such a
$t^{\prime}$ must exist. We then set

(11) $r_{i+1}=\max\\{t_{i},t_{i}^{\prime}\\}.$

Note that, in this case, $[r_{i+1},r_{i}]$ is teal. We therefore refer to
intervals of this case as teal intervals of $\mathcal{P}$.

We begin by observing that our partition is well defined.

######  Observation 24.

Suppose that $r_{i}\leq r$ and $r_{i}>C$, for some fixed constant $C$
depending only on $y$. Then there is at least one $t$ such that

$f(t)=f(r_{i})+\frac{D-1}{D}\left(dr_{i}-(d+1)t\right)-d(r_{i}-t).$

###### Proof.

We first note that $f(0)=O(1)$, and so

$\displaystyle f(r_{i})+\frac{D-1}{D}\left(dr_{i}-(d+1)t\right)-d(r_{i}-t)$
$\displaystyle=f(r_{i})+d\frac{D-1}{D}r_{i}-dr_{i}$
$\displaystyle=f(r_{i})-\frac{d}{D}r_{i}$ $\displaystyle>f(0).$

We also see that, at $t=r_{i}$,

$f(r_{i})+\frac{D-1}{D}\left(dr_{i}-(d+1)t\right)-d(r_{i}-t)<f(r_{i}),$

and so by the mean value theorem, the conclusion follows. ∎

We now show that a partition $\mathcal{P}$ does not contain too many
intervals. This will allow us to control the accumulation of error terms when
applying the symmetry of information.

######  Lemma 25.

If $[r_{i+1},r_{i}]\in\mathcal{P}$ is teal, then $r_{i+1}\leq\frac{r_{i}}{2}$.

###### Proof.

Suppose that $[r_{i+1},r_{i}]\in\mathcal{P}$ is teal. Then, by the
construction of $\mathcal{P}$, $[t,r_{i}]$ is not yellow, for any
$\frac{r_{i}}{2}\leq t<r_{i}$. This immediately implies that
$t^{\prime}_{i}<\frac{r_{i}}{2}$. Moreover, for any $t>\frac{r_{i}}{2}$, we
see that

$\displaystyle f(t)-f(r_{i})+\frac{d}{D}r_{i}-\frac{d+1-D}{D}t$
$\displaystyle\geq\frac{d+1}{D}t-\frac{D-d}{D}r_{i}$ $\displaystyle>0,$

implying that $t_{i}\leq\frac{r_{i}}{2}$, and the conclusion follows. ∎

$K^{A}_{s}(y)$$r=r_{0}$$d_{y}r$$D_{y}r$$r^{\prime}$$K^{A}_{s}(y)$$r=r_{0}$$d_{y}r$$D_{y}r$$r^{\prime}$$t^{\prime}=r_{1}$$t$
Figure 2. On the left, the adversary complexity function with $d_{y}=1.2$ and
$D_{y}=1.44$, equipped with an initial good partition of yellow intervals from
$1$ to $r^{\prime}$ and a teal interval $[r^{\prime},r]$. On the right,
generating an improved partition from the good partition. Note that the green
interval $[r_{1},r_{0}]$ is more than doubling. By combining it with a good
partition of $[1,r_{1}]$– which will clearly be all-yellow– we obtain an all
yellow partition of $[1,r]$. $1.44>2\cdot 1.2-1$, so this improves over the
previous subsection.

######  Lemma 26.

Let $\varepsilon>0$. Suppose that $r_{i+1}$ is sufficiently large and
$[r_{i+1},r_{i}]$ is a teal interval of the above partition. Then

$r_{i+1}\geq\frac{d(D-1)}{D^{2}+D-d-1}r_{i}-\varepsilon r_{i}.$

In particular,

$r_{i+1}\geq\frac{d(2-D)}{2+d(2-D)}r_{i}+1.$

###### Proof.

Assume that $r_{i+1}$ is large enough that, for all $s>r_{i+1}$,

$ds-\varepsilon^{\prime}s\leq K^{A}_{s}(y)\leq Ds+\varepsilon^{\prime}s$

for some $\varepsilon^{\prime}$ to be determined. By our choice of $r_{i+1}$,

(12) $K^{A}_{r_{i+1}}(y)\geq
K^{A}_{r_{i}}(y)-\frac{d}{D}r_{i}+\frac{1+d-D}{D}r_{i+1}-\varepsilon^{\prime}r_{i}.$

We then have

$\displaystyle Dr_{i+1}$ $\displaystyle\geq D_{y}r_{i+1}$ $\displaystyle\geq
K^{A}_{r_{i+1}}(y)-\varepsilon^{\prime}r_{i+1}$ $\displaystyle\geq
K^{A}_{r_{i}}(y)-\frac{d}{D}r_{i}+\frac{1+d-D-D\varepsilon^{\prime}}{D}r_{i+1}$
$\displaystyle\geq
dr_{i}-\varepsilon^{\prime}r_{i}-\frac{d}{D}r_{i}+\frac{1+d-D-D\varepsilon^{\prime}}{D}r_{i+1}$
$\displaystyle=\frac{d(D-1)-D\varepsilon^{\prime}}{D}r_{i}+\frac{1+d-D-D\varepsilon^{\prime}}{D}r_{i+1}.$

Rearranging and simplifying yields

(13)
$r_{i+1}\geq\frac{d(D-1)-D\varepsilon^{\prime}}{D^{2}+D-d-1-D\varepsilon^{\prime}}r_{i}.$

Given $\varepsilon>0$, choosing $\varepsilon^{\prime}$ sufficiently small
compared to these quantities gives the desired conclusion:

(14) $r_{i+1}\geq\frac{d(D-1)}{D^{2}+D-d-1}r_{i}-\varepsilon r_{i}.$

It is straightforward to verify that this implies that

$r_{i+1}\geq\frac{d(2-D)}{2+d(2-D)}r_{i}$

for sufficiently small $\varepsilon$. Indeed, using the above inequality, it
suffices to show that

$\frac{d(D-1)}{D^{2}+D-d-1}>\frac{d(2-D)}{2+d(2-D)},$

or, equivalently, $d(2-D)>D-D^{2}+1$.

By our assumption, $d>1$, and so the above inequality follows. Thus, for $r$
sufficiently large, we have

$r_{i+1}\geq\frac{d(2-D)}{2+d(2-D)}r_{i}+1.$

∎

######  Lemma 27.

Let $\varepsilon>0$. Suppose that $[r_{i+1},r_{i}]\in\mathcal{P}$ is a yellow
interval. Then,

$K^{A,x}_{r_{i},r_{i+1}}(|x-y|\mid|x-y|)\geq r_{i}-r_{i+1}-\varepsilon r_{i}.$

###### Proof.

By assumption, $[r_{i+1},r_{i}]$ is the union of of yellow intervals
$[a_{j+1},a_{j}]$ such that $a_{j}\leq 2a_{j+1}$. By a simple greedy strategy
we can construct a partition $P_{1}=\\{[b_{k+1},b_{k}]\\}$ of
$[r_{i+1},r_{i}]$ such that, for every $k$, $[b_{k+1},b_{k}]$ is yellow,
$b_{k}\leq 2b_{k+1}$ and $b_{k+2}>2b_{k}$. That is, $P_{1}$ is a good
partition of $[r_{i+1},r_{i}]$. The conclusion then follows from Lemma 22. ∎

######  Lemma 28.

Let $\varepsilon>0$ be given and suppose that $[r_{i+1},r_{i}]$ is teal and
$r_{i}$ is sufficiently large. Then

(15) $\frac{K^{A}_{r_{i},r_{i+1}}(y\mid
y)}{r_{i}-r_{i+1}}\geq\min\\{1,\frac{d(2D-d-1)}{D^{2}+D-Dd-1}-\varepsilon\\}$

###### Proof.

Recall that we chose $r_{i+1}$ to be

$r_{i+1}=\max\\{t,t^{\prime}\\}$,

where $t^{\prime}$ is the largest real such that $[t^{\prime},r_{i}]$ is
green, and $t$ is the largest real such that

$f(t)=f(r_{i})+\frac{D-1}{D}\left(dr_{i}-(d+1)t\right)-d(r_{i}-t).$

If $r_{i+1}=t^{\prime}$, then

$K^{A}_{r_{i+1}}(y)=K^{A}_{r_{i}}(y)-(r_{i}-r_{i+1}),$

and the conclusion holds trivially.

We now assume that $r_{i+1}=t$. Then, by the previous proposition,

(16) $r_{i+1}\geq\frac{d(D-1)}{D^{2}+D-d-1}r_{i}-\varepsilon r_{i}.$

We proceed via a tedious, but straightforward, calculation. Noting that our
interval is not green, we have from the definition of $r_{i+1}$ that

$K^{A}_{r_{i}}(y)-K^{A}_{r_{i+1}}(y)=-\frac{D-1}{D}\left(dr_{i}-(d+1)r_{i+1}\right)+d(r_{i}-r_{i+1}).$

Using this condition and the above bound on $r_{i+1}$ allows one to bound the
growth rate on such an interval. We omit the details since the algebra becomes
quite unpleasant. ∎

######  Observation 29.

When $D\leq\frac{(3+\sqrt{5})d-1-\sqrt{5}}{2}$,
$\frac{K^{A}_{r_{i},r_{i+1}}(y\mid y)}{r_{i}-r_{i+1}}=1$ whenever
$[r_{i+1},r_{i}]$ is teal.

The last goal of this subsection is to prove that these particular teals are
useful, namely, that we can lower bound the growth of the complexity of the
distance by the growth of the complexity of $y$ on them. We start by stating
the following lemma from [20]:

######  Lemma 30.

Let $x,y\in\mathbb{R}^{2}$ and $r\in\mathbb{N}$. Let $z\in\mathbb{R}^{2}$ such
that $|x-y|=|x-z|$. Then for every $A\subseteq\mathbb{N}$,

(17) $K^{A}_{r}(z)\geq K^{A}_{t}(y)+K^{A}_{r-t,r}(x\mid y)-K_{r-t}(x\mid
p_{e^{\prime}}x,e^{\prime})-O(\log r),$

where $e^{\prime}=\frac{y-z}{|y-z|}$ and $t=-\log|y-z|$.

Though it may appear somewhat cumbersome, the above lemma is a relatively
straightforward consequence of attempting to compute $x$ given access to $y$
up to a certain precision through the use of $z$ and $w$ – the midpoint
between $y$ and $z$ – which has the property that
$p_{e^{\prime}}x=p_{e^{\prime}}w$, which is a key connection between
projections and distances. In particular, note the term $K_{r-t}(x\mid
p_{e^{\prime}}x,e^{\prime})$ above; bounding this is where the projection
theorem will be useful. Now, we state the final lemma of this subsection.

######  Lemma 31.

Suppose that $[r_{i+1},r_{i}]\in\mathcal{P}$ is a teal interval. For any
$\varepsilon>0$, provided that $r_{i+1}$ is sufficiently large, we have

(18) $K^{A,x}_{r_{i},r_{i},r_{i+1}}(y\mid|x-y|,y)\leq\varepsilon r_{i}.$

Therefore, $K^{A,x}_{r_{i},r_{i+1}}(|x-y|\mid|x-y|)\geq
K^{A,x}_{r_{i},r_{i+1}}(y\mid y)-\varepsilon r_{i}$.

Notice that the conclusion of Lemma 15 is almost exactly the conclusion of
this lemma. Thus, we need to verify that its conditions are satisfied, which
is the content of this proof. Essentially, this entails proving a lower bound
on the complexity of points $z$ which are the same distance from $x$ as $y$
is.

###### Proof.

Let some small rational $\varepsilon>0$ be given, and assume $r_{i+1}$ is
sufficiently large. Let $\eta$ be the rational such that $\eta
r_{i}=K^{A}_{r_{i}}(y)-4\varepsilon$. Let $G=D(r,y,\eta)$ be the oracle of
Lemma 14 relative to $A$.

Our goal is to apply Lemma 15. It is routine to verify that condition (i) of
Lemma 15 holds. We must therefore verify condition (ii) That is, we need to
show that, for any $z\in B_{2^{-r_{i+1}}}(y)$ whose distance from $x$ is
$|x-y|$, either (i) $K^{A,G}_{r_{i}}(z)$ is greater than $\eta r_{i}$ or (ii)
$z$ is very close to $y$. Formally, we must show that, for any such $z$,

(19) $K_{r_{i}}^{A,G}(z)\geq\eta r_{i}+\min\\{\varepsilon
r_{i},r_{i}-s-\varepsilon r_{i}\\},$

where $s=-\log|y-z|$.

To that end, let $z\in B_{2^{-r_{i+1}}}(y)$ such that $|x-y|=|x-z|$. Let
$s=|y-z|$. We consider two cases. For the first, assume that
$s\geq\frac{r_{i}}{2}-\log r_{i}$. Then, as observed in [20], the projections
of $y$ and $z$ in the direction $e$ are almost exactly the same. Specifically,
$|p_{e}y-p_{e}z|<r_{i}^{2}2^{-r_{i}}$. Then, letting
$r_{i}^{\prime}=r_{i}-2\log r_{i}$, these projections are indistinguishable at
precision $r_{i}^{\prime}$. This enables us to apply Lemma 13 which, in
conjunction with property (C4) and the properties of our oracle $G$ imply that

(20) $K_{r_{i}}^{A,G}(z)\geq
K_{s}^{A,G}(y)+r_{i}-s-\frac{\varepsilon}{2}r_{i}-O(\log r_{i})$

Then, using the fact that $K_{s}^{A,G}(y)=\min\\{\eta
r_{i},K_{s}^{A}(y)+O(\log r_{i})$ and considering each of these cases
establishes (19) in the case that $s\geq\frac{r_{i}}{2}-\log r_{i}$.

This leaves the case that $s<\frac{r_{i}}{2}-\log r_{i}$. Note that this
immediately implies that $K^{A,G}_{s}(y)=K^{A}_{s}(y)-O(\log r_{i})$. Lemma
30, relative to $(A,G)$, implies that

(21) $K^{A,G}_{r_{i}}(z)\geq K^{A,G}_{s}(y)+K^{A,G}_{r_{i}-s,r_{i}}(x\mid
y)-K^{A,G}_{r_{i}-s}(x\mid p_{e^{\prime}}x,e^{\prime})-O(\log r).$

To bound the projection term, we need to apply Theorem 16 with respect to $x$,
$e^{\prime}$, $\varepsilon$, a constant $C$ (depending only on $x$ and $y$),
$t=s$, and $r=r_{i}-s$. We now check that the conditions are satisfied.

First, observe that $r_{i+1}-1<s<\frac{r_{i}}{2}-\log r_{i}$, since $z$ is
assumed to be within $2^{-r_{i+1}}$ of $y$. The second inequality implies that
we can take $r_{i}-s$ to be sufficiently large, since $r_{i}$ is taken to be
sufficiently large. From the first inequality and Lemma 26, we obtain that

(22) $s\geq\left(\frac{d(2-D)}{2+d(2-D)}r_{i}+1\right)-1.$

Hence,

(23) $s\geq\frac{d(2-D)}{2}(r_{i}-s)$

Thus conditions (P1) and (P2) are satisfied. As for condition (P3), from an
observation in [20], $e^{\prime}$ and $e$ are close enough to each other that,
using the fact that $e$ and its orthogonal complement are computable from each
other, we have for $s^{\prime}\leq s$

(24) $K^{A,x}_{s^{\prime}}(e^{\prime})=K^{A,x}_{s^{\prime}}(e)+O(\log
s^{\prime}).$

So, using condition (C2), we have

(25) $K^{A,x}_{s^{\prime}}(e^{\prime})\geq s^{\prime}-C\log s^{\prime}$

and thus we may apply Theorem 16.

Using Theorem 16 the properties of $G$, and our choice of $r_{i+1}$ yields

$\displaystyle K^{A,G}_{r_{i}}(z)$ $\displaystyle\geq
K^{A,G}_{s}(y)+K^{A,G}_{r_{i}-s,r_{i}}(x\mid y)-K^{A,G}_{r_{i}-s}(x\mid
p_{e^{\prime}}x,e^{\prime})-O(\log r)$ $\displaystyle\geq
K^{A}_{s}(y)+K^{A}_{r_{i}-s,r_{i}}(x\mid y)-K^{A,G}_{r_{i}-s}(x\mid
p_{e^{\prime}}x,e^{\prime})-O(\log r)$ $\displaystyle\geq
K^{A}_{s}(y)+K^{A}_{r_{i}-s}(x)-K^{A,G}_{r_{i}-s}(x\mid
p_{e^{\prime}}x,e^{\prime})-O(\log r)$ $\displaystyle\geq
K^{A}_{s}(y)+K^{A}_{r_{i}-s}(x)-K^{A}_{r_{i}-s}(x\mid
p_{e^{\prime}}x,e^{\prime})-O(\log r)$ $\displaystyle\geq
K^{A}_{s}(y)+K^{A}_{r_{i}-s}(x)-\varepsilon r_{i}-O(\log r)$
$\displaystyle-\max\\{K^{A}_{r_{i}-s}(x)-\frac{d}{D}r_{i}+\frac{d+1-D}{D}s,K^{A}_{r_{i}-s}(x)-(r_{i}-s)\\}$

Hence,

(26) $K^{A,G}_{r_{i}}(z)\geq
K^{A}_{s}(y)+\min\\{\frac{d}{D}r_{i}-\frac{d+1-D}{D}s,(r_{i}-s)\\}-\varepsilon
r_{i}-O(\log r)$

By our choice of $r_{i+1}$, (10), we see that

(27) $K^{A}_{s}(y)\geq K^{A}_{r_{i}}(y)-\frac{d}{D}r_{i}+\frac{d+1-D}{D}s.$

Combining (26) and (27) shows that

$\displaystyle K^{A,G}_{r_{i}}(z)$ $\displaystyle\geq
K^{A}_{s}(y)+\min\\{\frac{d}{D}r_{i}-\frac{d+1-D}{D}s,(r_{i}-s)\\}-\varepsilon
r_{i}-O(\log r)$ $\displaystyle\geq
K^{A}_{r_{i}}(y)-\frac{d}{D}r_{i}+\frac{d+1-D}{D}s$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;+\min\\{\frac{d}{D}r_{i}-\frac{d+1-D}{D}s,(r_{i}-s)\\}-\varepsilon
r_{i}-O(\log r)$

If $\frac{d}{D}r_{i}-\frac{d+1-D}{D}s\leq r_{i}-s$, then we have

$\displaystyle K^{A,G}_{r_{i}}(z)$ $\displaystyle\geq
K^{A}_{r_{i}}(y)-2\varepsilon r_{i}$ $\displaystyle\geq\eta r_{i}+\varepsilon
r_{i},$

and (19) holds. Otherwise, since $[r_{i+1},r_{i}]$ is teal,

$\displaystyle K^{A,G}_{r_{i}}(z)$ $\displaystyle\geq
K^{A}_{s}(y)+r_{i}-s-\varepsilon r_{i}-O(\log r)$ $\displaystyle\geq
K^{A}_{r_{i}}(y)-\varepsilon r_{i}-O(\log r)$ $\displaystyle\geq\eta
r_{i}+\varepsilon r_{i}$

and we can again establish (19).

Therefore, we are able to apply Lemma 15, which shows that

$\displaystyle K^{A,x}_{r_{i},r_{i+1}}(|x-y|\mid|x-y|)$ $\displaystyle\geq
K^{A,x}_{r_{i},r_{i+1}}(|x-y|\mid y)$ $\displaystyle\geq
K^{A,G,x}_{r_{i},r_{i+1}}(|x-y|\mid y)$ $\displaystyle\geq
K^{A,G,x}_{r_{i},r_{i+1}}(y\mid y)-3\varepsilon r+K(\varepsilon,\eta)-O(\log
r_{i})$ $\displaystyle\geq K^{A,x}_{r_{i},r_{i+1}}(y\mid y)-4\varepsilon r,$

and the proof is complete. ∎

###  4.4. Main theorem for effective Hausdorff dimension

In this section, we prove the point-wise analog of the main theorem of this
paper. That is, we prove the following.

######  Theorem 32.

Suppose that $x,y\in\mathbb{R}^{2}$, $e=\frac{y-x}{|y-x|}$, and
$A,B\subseteq\mathbb{N}$ satisfy the following.

  * (C1)

$d_{x},d_{y}>1$

  * (C2)

$K^{x,A}_{r}(e)=r-O(\log r)$ for all $r$.

  * (C3)

$K^{x,A,B}_{r}(y)\geq K^{A}_{r}(y)-O(\log r)$ for all sufficiently large $r$.

  * (C4)

$K^{A}_{r}(e\mid y)=r-o(r)$ for all $r$.

Then

$\dim^{x,A}(|x-y|)\geq
d\left(1-\frac{(D-1)(D-d)}{2(D^{2}+D-1)-2d(2D-1)}\right),$

where $d=\min\\{d_{x},d_{y}\\}$ and $D=\max\\{D_{x},D_{y}\\}$. Furthermore, if

$D\leq\frac{(3+\sqrt{5})d-1-\sqrt{5}}{2}$

Then $\dim^{x,A}(|x-y|)=1$.

In the last subsection we have a good bound on the complexity growth of the
distance on any teal interval, and the complexity growth on any yellow is 1.
Then, it would seem that the worst case scenario is that our partition is
(almost) all teal. But, this case is advantageous too, because if there is
very little yellow, then almost all the complexity growth for $y$ has to take
place on the teals, and Lemma 31 indicates we can transfer _all_ the growth of
$K_{s}^{A}(y)$ on teals to $K_{s}^{A}(|x-y|)$. So, the worst case scenario is
actually when there is an intermediate amount of yellow. Now, we formalize
this and prove the theorem.

###### Proof.

Let $\varepsilon>0$ be given and let $r$ be sufficiently large. Let
$\mathcal{P}=\\{[r_{i+1},r_{i}]\\}$ be the partition of $[1,r]$ defined in the
previous section. Let $L$ be the total length of the yellow intervals. Recall
that if $[r_{i+1},r_{i}]$ is yellow, then we have that

$K^{A,x}_{r_{i},r_{i+1}}(|x-y|\mid|x-y|)\geq r_{i}-r_{i+1}-\varepsilon r_{i}$

By the previous lemma, and repeated applications of the symmetry of
information, we have for sufficiently large $r$ that

$\displaystyle K^{A,x}_{r}(|x-y|)$ $\displaystyle=\sum\limits_{i\in
Y}K^{A,x}_{r_{i},r_{i+1}}(|x-y|\mid|x-y|)+\sum\limits_{i\in
Y^{C}}K^{A,x}_{r_{i},r_{i+1}}(|x-y|\mid|x-y|)$ $\displaystyle\geq
L-\frac{\varepsilon}{3}r+\sum\limits_{i\in
Y^{C}}K^{A,x}_{r_{i},r_{i+1}}(|x-y|\mid|x-y|)$ $\displaystyle\geq
L-\frac{2\varepsilon}{3}r+\sum\limits_{i\in
Y^{C}}K^{A,x}_{r_{i},r_{i+1}}(y\mid y)$ $\displaystyle\geq
L+\min\\{1,\frac{d(2D-d-1)}{D^{2}+D-Dd-1}\\}(r-L)-\varepsilon r.$

From Observation 29, we have 1 as the minimum when
$D\leq\frac{(3+\sqrt{5})d-1-\sqrt{5}}{2}$, so in this case
$K^{A,x}_{r}(|x-y|)\geq L+(r-L)-\varepsilon r=r-\varepsilon r$. Taking
$\varepsilon$ as small as desired and letting $r$ go to infinity completes the
proof. Now assume we are not in the above case and that $r$ is sufficiently
large given $\varepsilon$, and note the following bound which is advantageous
when there is not much yellow:

$\displaystyle d_{y}r$ $\displaystyle\leq
K^{A,x}_{r}(y)+\frac{\varepsilon}{3}$ $\displaystyle=\sum\limits_{i\in
Y}K^{A,x}_{r_{i},r_{i+1}}(y\mid y)+\sum\limits_{i\in
Y^{C}}K^{A,x}_{r_{i},r_{i+1}}(y\mid y)$ $\displaystyle\leq
2L+\frac{2\varepsilon}{3}+\sum\limits_{i\in
Y^{C}}K^{A,x}_{r_{i},r_{i+1}}(|x-y|)$
$\displaystyle=L+K^{A,x}_{r}(|x-y|)+\varepsilon r.$

Hence,

(28)
$K^{A,x}_{r}(|x-y|)\geq\max\\{L+\frac{d(2D-d-1)}{D^{2}+D-Dd-1}(r-L),dr-L\\}-\varepsilon
r.$

The first term is increasing in $L$ (since we are considering the case where
$\frac{d(2D-d-1)}{D^{2}+D-Dd-1}<1$), and the second term is decreasing in $L$,
so we can set them equal to find the minimum over all $L$, which yields

(29) $K^{x,A}_{r}(|x-y|)\geq
d\left(1-\frac{\left(D-1\right)\left(D-d\right)}{2D^{2}+\left(2-4d\right)D+d^{2}+d-2}\right)-\varepsilon
r.$

Since we can take $\varepsilon$ as small as desired and then let $r$ go to
infinity, this completes the proof.

∎

Now, we can consider a few special cases. First, note that when combined with
Proposition 23, for any choice of $d$, our lower bound on the dimension is
monotone decreasing in $D$. Thus, setting $D=2$ gives the following corollary:

######  Corollary 33.

When conditions (C1)-(C4) are satisfied,

(30) $\dim^{x,A}(|x-y|)\geq\frac{d(d-4)}{d-5}.$

Similarly, our lower bound is monotone increasing in $d$, so setting $d=1$
gives

######  Corollary 34.

When conditions (C1)-(C4) are satisfied,

(31) $\dim^{x,A}(|x-y|)\geq\frac{D+1}{2D}.$

Note that these are the effective analogs of Corollary 2 and Corollary 3 in
the introduction. The first of these corollaries is a helpful comparison point
to previous work on the pinned distance problem, and the second will be useful
in the next subsection.

###  4.5. Main theorem for effective packing dimension

We can use our work in the previous section to prove a new bound on the
packing dimension of pinned distance sets. The basic idea is that for
effective Hausdorff dimension, we had to prove a lower bound for
$K_{r}^{x,A}(|x-y|)$ at _every_ sufficiently large precision (since dim is
defined with a limit inferior), whereas for effective packing dimension, we
are free to _choose_ a sequence of advantageous precisions (since Dim is
defined with a limit superior). The idea is to consider “maximal” precisions
$r_{i}$ where $K^{A}_{r_{i}}(y)\approx Dr_{i}$. These maximal precisions have
to be contained in large yellow intervals, and prior to the large yellow
intervals, we can use the bound from Corollary 34, which holds at _every_
precision.

We call an interval $[a,b]$ an all yellow interval if there is a good
partition of $[a,b]$ consisting entirely yellow intervals whose lengths are at
most doubling.

######  Lemma 35.

Suppose that $\varepsilon>0$, $A,B\subseteq\mathbb{N}$ and
$x,y\in\mathbb{R}^{2}$ satisfy (C1)-(C4). In addition, assume that
$\operatorname{Dim}^{A}(x)\leq\operatorname{Dim}^{A}(y)$. Let $r$ be a
sufficiently large precision which is maximal in the sense that
$K^{A,x}_{r}(y)\geq D_{y}r-\varepsilon r$. Then

(32) $K^{A,B,x}_{r}(|x-y|)\geq\frac{D^{2}-D+2}{2D}r-\varepsilon r.$

Moreover, if $[r_{1},r_{2}]$ is an all yellow interval containing $r$, then

(33) $K^{A,B,x}_{r_{2}}(|x-y|)\geq r_{2}-\frac{3D-D^{2}-2}{2D}r-\varepsilon
r.$

###### Proof.

Let $r$ be sufficiently large such that

(34) $K^{A}_{r}(y)\geq Dr-\frac{\varepsilon}{2}r.$

Let $\mathcal{P}=\\{[r_{i+1},r_{i}]\\}$ be the partition of $[1,r]$ defined in
the previous section. Let $L$ be the total length of the yellow intervals in
$\mathcal{P}$. Using (28), we have that

(35) $K^{A,x}_{r}(|x-y|)\geq\max\\{L+\frac{2}{D+1}(r-L),Dr-L\\}-\varepsilon
r.$

We can therefore conclude that (32) holds.

Let $[r_{1},r_{2}]$ be an all yellow interval containing $r$. Then, by Lemma
20,

$\displaystyle r_{2}-r_{1}-\frac{\varepsilon r}{2}$ $\displaystyle\leq
K^{A,x}_{r_{2},r_{1}}(|x-y|\mid|x-y|)$ $\displaystyle\leq
K^{A,x}_{r_{2}}(|x-y|)-K^{A,x}_{r_{1}}(|x-y|)-O(\log r)$ $\displaystyle\leq
K^{A,x}_{r_{2}}(|x-y|)-\left(K^{A,x}_{r}(|x-y|)-(r-r_{1})\right)-O(\log r).$

Rearranging, and using (32), we see that for sufficiently large $r$

$\displaystyle K^{A,x}_{r_{2}}(|x-y|)$
$\displaystyle=K^{A,x}_{r}(|x-y|)-(r-r_{1})+r_{2}-r_{1}-\frac{\varepsilon}{2}r$
$\displaystyle\geq\frac{D^{2}-D+2}{2D}r-\varepsilon r+r_{2}-r$
$\displaystyle=r_{2}-\frac{3D-D^{2}-2}{2D}r-\varepsilon r,$

and the conclusion follows. ∎

######  Theorem 36.

Suppose that $x,y\in\mathbb{R}^{2}$, $e=\frac{y-x}{|y-x|}$, and
$A,B\subseteq\mathbb{N}$ satisfy
$\operatorname{Dim}^{A}(x)\leq\operatorname{Dim}^{A}(y)$ and the following.

  * (C1)

$d_{x},d_{y}>1$,

  * (C2)

$K^{x,A}_{r}(e)=r-O(\log r)$ for all $r$.

  * (C3)

$K^{x,A,B}_{r}(y)\geq K^{A}_{r}(y)-O(\log r)$ for all sufficiently large $r$.

  * (C4)

$K^{A}_{r}(e\mid y)=r-o(r)$ for all $r$.

Then $\operatorname{Dim}^{x,A,B}(|x-y|)\geq\frac{3D_{y}^{2}-D_{y}+6}{8D_{y}}$

######  Remark.

The extra requirement that
$\operatorname{Dim}^{A}(x)\leq\operatorname{Dim}^{A}(y)$ seems necessary to
obtain the largest lower bound with our methods. Previously in this section,
we assumed $D$ was the larger of $D_{x},D_{y}$, a safe assumption since a
larger $D_{x}$ gives a worse projection theorem and a larger $D_{y}$ gives a
worse adversary function when partitioning. For the packing bound, however, a
higher $D_{y}$ could actually improve the bound. Thus, if $D_{y}$ were
actually much smaller than $D$, this could make for a worse bound, which
necessitates the extra assumption.

###### Proof.

Let $\varepsilon>0$. Let $r$ be a sufficiently large precision which is
maximal in the sense that $K^{A}_{r}(y)\geq D_{y}r-\varepsilon r$. We also
assume that the function $f$ associated to $K^{A}_{s}(y)$ is increasing on
$[r-1,r]$. Note that there are infinitely many such $r$. We first assume that
there exists an all yellow interval $[r_{1},r_{2}]$ containing $r$ such that
$r_{2}\geq\frac{4}{3}r$. Then,

$K^{A,x}_{r_{2}}(|x-y|)\geq\frac{3D^{2}-D+6}{8D}r_{2}-\varepsilon r_{2},$

and the proof is complete.

We now assume that, no such all yellow interval exists. Let $[r_{1},r_{2}]$ be
an all yellow interval containing $r$ which is of maximal length. This implies
that there is an interval $[a,r_{2}]$ which is the union of green intervals,
whose lengths are at most doubling, such that $a\leq\frac{r_{2}}{2}$. Hence
$r\geq\frac{3}{2}a$. For convenience, we set $r^{\prime}=\frac{r_{2}}{2}$. Let
$\mathcal{P}=\\{[r_{i+1},r_{i}]\\}$ be the partition of $[1,r^{\prime}]$. Let
$L$ be the total length of the yellow intervals in $\mathcal{P}$. We first see
that

(36)
$K^{A,x}_{r^{\prime}}(|x-y|)\geq\max\\{L+\frac{2}{D+1}(r^{\prime}-L),K^{A}_{r^{\prime}}(y)-L\\}.$

Since $[a,r_{2}]$ is green, and $r\geq\frac{3}{2}r^{\prime}$,

$\displaystyle K^{A}_{r^{\prime}}(y)$ $\displaystyle\geq
K^{A}_{2r^{\prime}}(y)-r^{\prime}$ $\displaystyle\geq K^{A}_{r}(y)-r^{\prime}$
$\displaystyle=Dr-r^{\prime}$ $\displaystyle>\frac{3D-2}{2}r^{\prime}.$

We now show that

(37)
$K^{A,x}_{r^{\prime}}(|x-y|)\geq\frac{3D^{2}-5D+6}{4D}r^{\prime}-\varepsilon
r.$

If

(38) $K^{A}_{r^{\prime}}(y)-L\geq\frac{3D^{2}-5D+6}{4D}r^{\prime}-\varepsilon
r,$

then (37) holds immediately. Otherwise, using our lower bound on
$K^{A}_{r^{\prime}}(y)$, we see that

(39) $L\geq\frac{3D^{2}+D-6}{4D}r^{\prime}.$

Therefore,

$\displaystyle K^{A,x}_{r^{\prime}}(|x-y|)$ $\displaystyle\geq
L+\frac{2}{D+1}(r^{\prime}-L)-\varepsilon r$
$\displaystyle\geq\frac{3D^{2}-5D+6}{4D}r^{\prime}-\varepsilon r,$

and so (37) holds.

Since $[r_{1},r_{2}]$ is all yellow, by Lemma 20 we see that

$\displaystyle K^{x,A,B}_{2r^{\prime}}(|x-y|)$
$\displaystyle\geq\frac{3D^{2}-5D+6}{4D}r^{\prime}+r^{\prime}-\varepsilon r$
$\displaystyle=\frac{3D^{2}-D+6}{4D}r^{\prime}-\varepsilon r$
$\displaystyle\geq\frac{3D^{2}-D+6}{8D}2r^{\prime}-2\varepsilon r^{\prime},$

Noting we can take $\varepsilon$ as small as desired and then let $r$ go to
infinity completes the proof. ∎

##  5\. Dimensions of pinned distance sets

In this section, we reduce the effective Hausdorff and packing theorems to
their classical analogues. We prove Theorem 5 and then Theorem 6 in the first
subsection, then consider packing dimension. Throughout, we have
$x,y\in\mathbb{R}^{2}$, $e=\frac{x-y}{|x-y|}$ and $A,B\subseteq\mathbb{N}$.
For ease of reference, we list conditions $(C1)-(C4)$ here:

  * (C1)

$\dim^{A}(x)>d_{x},d_{y}>1$

  * (C2)

$K^{x,A}_{r}(e)=r-O(\log r)$ for all $r$.

  * (C3)

$K^{x,A,B}_{r}(y)\geq K^{A}_{r}(y)-O(\log r)$ for all sufficiently large $r$.

  * (C4)

$K^{A}_{r}(e\mid y)=r-o(r)$ for all $r$.

Note the modification of condition (C1), here we drop the convention that
$d_{x}=\dim^{A}(x)$. For the reduction, we will want $d_{x}$ to be strictly
less than $\dim_{H}(X)$, because we will remove an exceptional set of size
$d_{x}$. Thus, we want $\dim_{A}(x)>d_{x}$ so we can apply our effective
theorem uniformly.

###  5.1. Hausdorff dimension of pinned distance sets

A main tool we need to reduce the classical statements to their effective
counterparts is the following radial projection theorem of Orponen [16]:

######  Theorem 37.

Let $Y\subseteq\mathbb{R}^{2}$ be a Borel set with $s=dim_{H}(Y)>1$ such that
there is a measure $\mu\in\mathcal{M}(Y)$ such that there is a measure
satisfying $I_{d}(\mu)<\infty$ for all $1<d<s$. Then there is a Borel
$G\subseteq\mathbb{R}^{2}$ with $\dim_{H}(G)\leq 2-\dim_{H}(Y)$ such that, for
every $x\in\mathbb{R}^{2}\setminus\text{spt}(\mu)$,
$\mathcal{H}^{1}(\pi_{x}(Y))>0$. Moreover, the pushforward of $\mu$ under
$\pi_{x}$ is absolutely continuous with respect to $\mathcal{H}^{1}|_{S^{1}}$
for $x\notin G$.

With this theorem, we are able to prove the following.

######  Lemma 38.

Let $Y\subseteq\mathbb{R}^{2}$ be compact with $0<\mathcal{H}^{d}(Y)<\infty$
for some $d_{y}>1$, and let $d_{x}>1$ be given. Let
$\mu=\mathcal{H}^{s}|_{Y}$. Let $A\subseteq\mathbb{N}$ be an oracle such that
$A$ is a packing oracle for $Y$, $Y$ is computably compact relative to $A$ and
$\mu$ is computable relative to $A$. Then, there is a set $G$ of Hausdorff
dimension at most $d_{x}$ such that for all
$x\in\mathbb{R}^{2}-(\text{spt}(\mu)\cup G)$, and all $B\subseteq\mathbb{N}$,
there exists some $y\in Y$ such that the pair $x,y$ satisfy conditions
(C1)-(C4).

###### Proof.

Let $G$ be the set guaranteed by Orponen’s radial projection theorem with
respect to $Y$ and $\mu=\mathcal{H}^{s}|_{Y}$. Let
$x\in\mathbb{R}^{2}-(\text{spt}(\mu)\cup G)$ have effective Hausdorff
dimension relative to $A$ greater than $d_{x}$, and define $N=\\{e\in
S^{1}:(\exists^{\infty}r)K_{r}^{x,A}(e)<r-4\log(r)\\}$. As observed in the
second author’s previous paper, $\mathcal{H}^{1}|_{S^{1}}(N)=0$. Orponen’s
theorem guarantees the absolute continuity of $\pi_{x\\#}(\mu)$ with respect
to $\mathcal{H}^{1}|_{S^{1}}$ for $x$ outside the exceptional set $G$, where
$\pi_{x}(y)=\frac{y-x}{||y-x||}\in S^{1}$. Thus,
$\mathcal{H}^{s}|_{Y}(\pi^{-1}_{x}(N))=0$. Now, let

$M=\\{y\in Y:\dim^{A}(y)\geq s\text{ and }K_{r}^{x,A,B}(y)>K_{r}^{A}(y)-8\log
r\text{ for large enough }r\\}$

Again from [20], we have that $\mathcal{H}^{s}(M)=\mathcal{H}^{s}(Y)>0$ by
assumption.888This result actually deals with $M=\\{y\in Y:\dim^{A}(y)\geq
s\text{ and }K_{r}^{x,A}(y)>K_{r}^{A}(y)-8\log r\text{ for large enough
}r\\}$, but since the statement only involves $x$ as an oracle, the same proof
goes through with the oracle $x,B$. Thus, $M-\pi_{x}^{-1}(N)$ has dimension
$s$ and is in particular nonempty. Picking a $y$ in $M-\pi_{x}^{-1}(N)$, we
may check the conditions: $x$ satisfies (C1) by assumption, we group together
all $e$ not satisfying (C2) in the negligible set $N$, and $y$ satisfies its
part of (C1) and (C3) by the definition of $M$. As for (C4), Lemma 31 in [20]
shows that (C1)-(C3) imply (C4), so the proof of this lemma is complete. ∎

Now, we would like to drop the $\text{spt}(\mu)$ from the excluded set, which
we will do by proving the following lemma:

######  Lemma 39.

Let $Y\subseteq\mathbb{R}^{2}$ be a compact set such that
$0<\mathcal{H}^{s}(Y)<\infty$ for some $s>1$, let $A$ be any oracle relative
to which $Y$ is effectively compact, and let $d_{x}>1$ be given. Then there is
a set $G\subseteq\mathbb{R}^{2}$ of Hausdorff dimension at most $d_{x}$ such
that for every $x\in\mathbb{R}^{2}-G$, and every $B\subseteq\mathbb{N}$, there
is a $y\in Y$ such that the pair $x,y$ satisfies (C1)-(C4)

###### Proof.

Let $Y$ be as in the statement of the lemma, and write $Y=Y_{1}\cup Y_{2}$ for
disjoint compact $Y_{1}$, $Y_{2}$ such that $0<\mathcal{H}^{s}(Y_{1})<\infty$
and $0<\mathcal{H}^{s}(Y_{2})<\infty$. Let $\mu_{1},\mu_{2}$ be
$\mathcal{H}^{s}|_{Y_{1}},\mathcal{H}^{s}|_{Y_{2}}$ respectively. Suppose
$A_{1}$ and $A_{2}$ are effective compactness oracles for $Y_{1}$ and $Y_{2}$
respectively, $A_{3}$ is an effective compactness oracle for $Y$, and let
$\hat{\mu}_{i}$ encode $\mu_{i}(Q)$ for each ball $Q$ with rational center and
radius. Let $A$ be the join of $A_{1},A_{2},A_{3},\hat{\mu}_{1}$, and
$\hat{\mu}_{2}$. Then $A$ and $Y_{i}$ satisfy the hypotheses of the previous
lemma for each $i$.

Let $G_{1},G_{2}$ be the exceptional sets guaranteed by the lemma. Let
$G=G_{1}\cup G_{2}\cup\\{x\in\mathbb{R}^{2}:\dim^{A}(x)\leq d_{x}\\}$. If
$x\in\mathbb{R}^{2}\setminus G$, then by the previous lemma, there is some $y$
in either $Y_{1}$ or $Y_{2}$ satisfying conditions (C1)-(C4) (since $x$ can
only be in the support of at most _one_ of $\mu_{1},\mu_{2}$). ∎

Now we are in a position to prove our main theorem.

######  Theorem 5.

Let $Y\subseteq\mathbb{R}^{2}$ be analytic such that $1<d_{y}=\dim_{H}(Y)$ and
$D_{y}=\dim_{p}(Y)$. Let $X\subseteq\mathbb{R}^{2}$ be such that
$1<d_{x}<\dim_{H}(X)$ and $D_{x}=\operatorname{Dim}_{p}(X)$. Then there is
some $F\subseteq X$ of full dimension such that

$\dim_{H}(\Delta_{x}E)\geq
d\left(1-\frac{\left(D-1\right)\left(D-d\right)}{2D^{2}+\left(2-4d\right)D+d^{2}+d-2}\right),$

for all $x\in F$, where $d=\min\\{d_{x},d_{y}\\}$ and
$D=\max\\{D_{x},D_{y}\\}$. In particular, $\dim_{H}(X\setminus F)\leq
d_{x}<\dim_{H}(X)$ Furthermore, if

$D<\frac{(3+\sqrt{5})d-1-\sqrt{5}}{2}$

Then $\dim_{H}(\Delta_{x}E)=1$.

###### Proof.

Let $Y$ and $X$ be as above, and let $B$ be the trivial oracle.999We need the
oracle $B$ to make the _packing_ reduction go through; in the Hausdorff case,
it can be removed. $Y$ is analytic, thus for any $s<d_{y}=\dim_{H}(Y)$, there
is a compact $Y_{s}$ such that $0<\mathcal{H}^{s}(Y_{s})<\infty$. Let
$\\{s_{i}\\}_{i\in\mathbb{N}}=d_{y}-\frac{1}{i}$. Let $Y_{s_{i}}$ be a
sequence of such compact sets. The $Y_{s_{i}}$ are compact, so let
$A_{1},A_{2},...$ be oracles relative to which they are effectively compact.

Now, we use the general point-to-set principle. Let $A_{Y}$ and $A_{X}$ be
packing oracles for $Y$ and $X$ respectively, that is, oracles such that
$\dim_{P}(Y)=\sup_{y\in Y}\operatorname{Dim}^{A_{Y}}(y)$ and likewise for $X$.
Now, take the join of $A_{Y},A_{X},A_{1},A_{2},...$, and call this new oracle
$A$.

Note that this oracle retains all the desired properties of its constituents.
In particular, every $Y_{s_{i}}$ is effectively compact relative to $A$, for
all $y\in Y$ we have that $\operatorname{Dim}^{A}(y)\leq\dim_{P}(Y)=D_{y}$,
and for all $x\in X$ we have that
$\operatorname{Dim}^{A}(x)\leq\dim_{P}(X)=D_{x}$. Using $A$, we may apply the
previous lemma to each $Y_{s_{i}}$, giving a corresponding exceptional set
$G_{i}$. Observe that $\dim_{H}(X)>d_{x}\geq\dim_{H}(G_{i})$, so the set of
$x\in{X}$ for which there is some $y\in Y_{s_{i}}$ satisfying conditions
(C1)-(C4) is nonempty for each sufficiently large $i$ (large enough that
$s_{i}>1$). In fact, by the countable stability of Hausdorff dimension,
$\dim_{H}(X)>d_{x}\geq\dim_{H}(\bigcup_{i\in\mathbb{N}}G_{i})$. If we denote
this union by $G$, then for all $x\in X-B$, there is a $y\in Y$ such that
(C1)-(C4) hold with $A$ as the oracle.

We choose $A$ such that the desired packing dimension conditions hold relative
to $A$ for _any_ $x\in X$, $y\in Y_{s_{i}}\subseteq(Y)$, so along with
conditions (C1)-(C4), all the hypotheses of our effective theorem are
satisfied. Applying this theorem when
$D\geq\frac{(3+\sqrt{5})d-1-\sqrt{5}}{2}$, then, we obtain that

$\dim^{A,x}(|x-y|)\geq(d-\frac{1}{i})\left(1-\frac{\left(D-1\right)\left(D-(d-\frac{1}{i})\right)}{2D^{2}+\left(2-4(d-\frac{1}{i})\right)D+(d-\frac{1}{i})^{2}+(d-\frac{1}{i})-2}\right).$

By Observation 12, since $Y_{s_{i}}$ is effectively compact relative to $A$,
$\Delta_{x}Y_{s_{i}}$ is effectively compact relative to $(A,x)$. Finishing
the proof, by Theorem 11, we have that

$\displaystyle\dim_{H}(\Delta_{x}E)$
$\displaystyle\geq\dim_{H}(\Delta_{x}E_{s_{i}})$ $\displaystyle=\sup_{y\in
E_{s_{i}}}\dim^{A,x}(|x-y|)$
$\displaystyle\geq(d-\frac{1}{i})\left(1-\frac{\left(D-1\right)\left(D-(d-\frac{1}{i})\right)}{2D^{2}+\left(2-4(d-\frac{1}{i})\right)D+(d-\frac{1}{i})^{2}+(d-\frac{1}{i})-2}\right).$

Letting $i$ go to infinity completes the proof in this case. If we are in the
case that $D<\frac{(3+\sqrt{5})d-1-\sqrt{5}}{2}$, then for some $i$ large
enough, we have

$D<\frac{(3+\sqrt{5})(d-\frac{1}{i})-1-\sqrt{5}}{2}.$

Then, repeating the above argument with $i$ at least this large gives the
bound of 1 immediately and completes the proof.

∎

Assuming $E=X=Y$, we immediately have as a corollary that

######  Theorem 1.

Let $E\subseteq\mathbb{R}^{2}$ be analytic such that $1<d<\dim_{H}(E)$. Then
there is a subset $F\subseteq E$ of full dimension such that

$\dim_{H}(\Delta_{x}E)\geq
d\left(1-\frac{\left(D-1\right)\left(D-d\right)}{2D^{2}+\left(2-4d\right)D+d^{2}+d-2}\right),$

for all $x\in F$, where $D=\dim_{P}(E)$. In particular, $\dim_{H}(E\setminus
F)\leq d<\dim_{H}(E)$. Furthermore, if

$D<\frac{(3+\sqrt{5})d-1-\sqrt{5}}{2}$

Then $\dim_{H}(\Delta_{x}E)=1$.

In a similar manner, we prove the following theorem.

######  Theorem 6.

Let $Y\subseteq\mathbb{R}^{2}$ be analytic with $\dim_{H}(Y)>1$ and
$\dim_{P}(Y)<2\dim_{H}(Y)-1$. Let $X\subseteq\mathbb{R}^{2}$ be any set such
that $\dim_{H}(X)>1$. Then for all $x\in X$ outside a set of (Hausdorff)
dimension one,

$\dim_{H}(\Delta_{x}Y)=1$.

We can follow essentially the same argument as above, except now we only need
the dimension of $x$ to be greater than 1, at the cost of also requiring that
$\dim^{A}(y)$ and $\operatorname{Dim}^{A}(y)$ are close enough, as in the
hypothesis of Proposition 23.

###### Proof.

Let $Y$ and $X$ be as above, and again let $B$ be the trivial oracle. $Y$ is
analytic, thus for any $s<\dim_{H}(Y)$, there is a compact $Y_{s}$ such that
$0<\mathcal{H}^{s}(Y_{s})<\infty$. Let $s$ be such that
$\dim_{p}(Y)<2s-1<2\dim_{H}(Y)-1$, and let $A_{s}$ be an oracle relative to
which $Y_{s}$ is effectively compact. Let $A_{Y}$ be a packing oracle for $Y$.
Now, take the join of $A_{Y},A_{s}$, and call this new oracle $A$.

Now, apply Lemma 39 to $Y_{s}$ relative to $A$ with $d_{x}=1$. As above,
conditions (C1)-(C4) are satisfied with an exceptional set of dimension at
most 1. $Y_{s}\subseteq Y$, so for any $y\in Y_{s}$,
$\operatorname{Dim}^{A}(y)\leq\dim_{P}(Y)$. Hence,
$\operatorname{Dim}^{A}(y)<2\dim^{A}(y)-1$, and all the conditions for
Proposition 23 are satisfied, and we have as above that for $x$ not in our
exceptional set,

$\displaystyle\dim_{H}(\Delta_{x}Y)$
$\displaystyle\geq\dim_{H}(\Delta_{x}Y_{s})$ $\displaystyle=\sup_{y\in
Y_{s}}\dim^{A,x}(||x-y||)$ $\displaystyle=1$

∎

###  5.2. Packing dimension of pinned distance sets

######  Theorem 4.

Let $E\subseteq\mathbb{R}^{2}$ be analytic such that $\dim_{H}(E)>1$. Then,
for some $x\in E$,

$\dim_{P}(\Delta_{x}E)\geq\frac{12-\sqrt{2}}{8\sqrt{(}2)}\approx 0.9356.$

###### Proof.

Let $E\subseteq\mathbb{R}^{2}$ be analytic such that $d=\dim_{H}(E)>1$. Let
$D=\dim_{P}(E)$. Since $E$ is analytic, there is a compact subset $F\subseteq
E$ such that $0<\mathcal{H}^{s}(F)<\infty$, for $s=\frac{d+1}{2}$. Let
$\mu=\mathcal{H}^{s}_{|F}$. Let $A_{1}$ be an oracle relative to which $F$ is
effectively compact.

Let $A_{2}$ be a packing oracle for $F$, that is, $\dim_{P}(F)=\sup_{x\in
F}\operatorname{Dim}^{A_{2}}(x)$. Let $A$ be the join of $A_{1}$ and $A_{2}$.

Using Orponen’s radial projection theorem, we see that there is an exceptional
set $G_{1}$ such that the pushforward of $\mu$ under $\pi_{x}$ is absolutely
continuous with respect to $\mathcal{H}^{1}_{|S^{1}}$ for all $x\notin G_{1}$.
Let $G_{2}=\\{x\in F\mid\dim^{A}(x)<\frac{s+1}{2}\\}$ and $G=G_{1}\cup G_{2}$.
Since $\dim_{H}(G_{1})\leq 1$ and $\dim_{H}(G_{2})\leq\frac{s+1}{2}<s$ we see
that $\dim_{H}(G)<s$. We now choose $x\in F-G$ such that the set

$F^{\prime}=\\{y\in
F-G\mid\operatorname{Dim}^{A}(x)\leq\operatorname{Dim}^{A}(y)\\}$

has positive $\mu$ measure, which is possible since we can choose some $x$
that has minimal or nearly minimal effective packing dimension. Let $B$ be a
packing oracle for $\Delta_{x}E$. The proof of Lemma 38 shows that there is a
$y\in F^{\prime}$ such that the pair $x,y$ satisfies (C1)-(C4). Moreover,
$\operatorname{Dim}^{A}(x)\leq\operatorname{Dim}^{A}(y)$.

We may therefore apply Theorem 36, which shows that

$\operatorname{Dim}^{A,x,B}(|x-y|)\geq\frac{3D^{2}-D+6}{8D},$

where $D=\operatorname{Dim}^{A}(y)$. Since this is minimized when
$D=\sqrt{2}$, we conclude that

$\operatorname{Dim}^{A,x,B}(|x-y|)\geq\frac{12-\sqrt{2}}{8\sqrt{(}2)}.$

Our choice of $B$ and the point-to-set principle concludes the proof, since

$\displaystyle\dim_{P}(\Delta_{x}E)$ $\displaystyle\geq\sup_{y\in
E}\operatorname{Dim}^{B}(|x-y|)$ $\displaystyle\geq\sup_{y\in
E}\operatorname{Dim}^{x,A,B}(|x-y|)$
$\displaystyle\geq_{\frac{12-\sqrt{2}}{8\sqrt{(}2)}}.$

∎

##  6\. Regular pin sets give full dimension pinned distance sets

Now, we consider a case that is not covered by our previous theorems. Our work
thus far implies that if $Y$ is sufficiently regular and $\dim_{H}(X)>1$, then
$\dim_{H}(\Delta_{x}Y)=1$ for all $x$ in a full dimension subset of $X$.

More surprisingly, however, the above holds even if just the _pin_ set $X$ is
regular. In this case, we are able to deduce an essentially optimal effective
projection theorem for $x$ which allows us to utilize arbitrarily long green
intervals when partitioning $K^{A}_{r}(y)$. If we have access to these green
intervals, we will never be forced to use a strictly teal interval101010A non-
green teal interval, so one with a growth rate of strictly less than 1,
implying that our partition is all-yellow and that $\dim^{x,A}(|x-y|)=1$.

We would like to perform the reduction to the classical result by finding some
point $x$ that is regular, but there is a problem. Suppose $X$ is regular of
dimension greater than 1 and $\dim_{H}(Y)>1$. In general, we cannot assume $X$
contains regular points relative to a given oracle. For instance, consider the
set

$X=\\{x\in\mathbb{R}^{2}:\operatorname{Dim}(x)=1.2\text{ and }\dim(x)<1.2\\}$.

The packing and Hausdorff dimensions of $X$ will be 1.2, but, relative to any
oracle $A$, any point will have effective Hausdorff dimension strictly less
than 1.2, though it may have packing dimension _exactly_ 1.2. However, we can
overcome this obstacle, due to the fact that $\dim_{H}(Y)>1$. This fact
implies that there a bound on the length of any green interval.

We start by stating and proving an effective projection theorem that holds
when $x$ is sufficiently regular.

######  Proposition 40.

Let $A\subseteq\mathbb{N}$, $x\in\mathbb{R}^{2}$, $e\in\mathcal{S}^{1}$,
$\varepsilon\in\mathbb{Q}^{+}$, $C,C^{\prime}\in\mathbb{N}$, and
$t,r\in\mathbb{N}$. Suppose that $r$ is sufficiently large, and that the
following hold.

  1. (P1)

$1<d_{x}<\dim^{A}(x)$.

  2. (P2)

$t\geq\frac{r}{C}$.

  3. (P3)

$K^{x,A}_{s}(e)\geq s-C^{\prime}\log s$, for all $s\leq t$.

Then there exists some $\varepsilon_{x}$ depending only on $d_{x}$ and $C$
such that $\operatorname{Dim}^{A}(x)-d_{x}<\varepsilon_{x}$ implies that

$K^{A}_{r}(x\,|\,p_{e}x,e)\leq K^{A}_{r}(x)-r+\varepsilon r.$

The key of this result is that the $\varepsilon_{x}$ we need in the almost-
regularity condition does not depend on $\varepsilon$. The way we will apply
this theorem, $C$ is going to depend on $d_{y}$. So, given a lower bound for
the effective Hausdorff dimension of points $x$ and $y$, $\varepsilon_{x}>0$
expresses how close to regular $x$ needs to be in order to apply this theorem,
and that required closeness is _fixed_ given sets $X,Y$ when we perform the
reduction.

The idea of the proof is quite simple. When we partition in $x$, we were
allowed to use intervals up to length $t$. By picking $r$ large enough that
the complexity function lies very close to the line $d_{x}s$,111111How close
it needs to be to this line for the argument to go through depends on $C$, how
close we are allowed to assume it is depends on $\varepsilon_{x}$ since the
point is not exactly regular. Thus, we choose $\varepsilon_{x}$ based in part
on $C$. we can show that it is impossible for there to be any red-green-blue
sequences past some precision $\varepsilon r$, since this would imply the
existence of a green block of length at least $t$. Thus, $[1,r]$ is almost
entirely covered by red and green intervals, and we obtain an essentially all-
yellow partition of it. Formally,

###### Proof.

Let $x$ satisfying the conditions of the proposition for some
$\varepsilon_{x}$ be given. Let $C$, and $\varepsilon$ be given and choose
$\varepsilon^{\prime}$ depending on $\varepsilon_{x}$, $d_{x}$, and $C$ in a
manner which we will detail shortly. Now let $r$ be large enough that
$d_{x}s-\varepsilon^{\prime}s\leq K^{A}_{s}(x)\leq
d_{x}s+\varepsilon^{\prime}s$ for all $s\geq\sqrt{r}$. Note that we must have
$\varepsilon^{\prime}>\varepsilon_{x}$. Let $t\geq\frac{r}{C}$ be given, and
let $\hat{\mathcal{P}}=\hat{\mathcal{P}}(x,r,t)$ be the partition of $[1,r]$
by red, blue and green intervals considered in section 3.1. We will show that
if $\varepsilon_{x}$ is sufficiently small depending only on $C$ and $d_{x}$,
then the desired conclusion holds.

On one hand, any red-green-blue sequence has a green block of length at least
$t$; this was one of the key properties of this partition in section 3. On the
other hand, since the slope is $1$ on green intervals, if we have
$K^{A}_{r-t}(x)=(d_{x}+\varepsilon^{\prime})(r-t)$, (its maximum possible
value) and that $[r-t,r]$ is green, then

$\displaystyle K^{A}_{r}(x)$
$\displaystyle\leq(d_{x}+\varepsilon^{\prime})(r-t)+t$
$\displaystyle\leq(d_{x}+\varepsilon^{\prime})r-(d_{x}-1-\varepsilon^{\prime})\frac{r}{C}$

So, if $\varepsilon^{\prime}$ is small enough that

(40)
$-\frac{d_{x}}{C}+2\varepsilon^{\prime}-\frac{\varepsilon^{\prime}}{C}-\frac{1}{C}<0,$

we have a contradiction, since by assumption $K^{A}_{r}(x)\geq
d_{x}r-\varepsilon^{\prime}r$. If we attempted to place the left endpoint of a
green block of a red-green-blue sequence at any $\sqrt{r}\leq s\leq r$, we
would clearly have the same contradiction, in fact, the green interval would
be forced to be even shorter. Hence, there are no red-green-blue sequences
such that the green block is contained in $[\sqrt{r},r]$. Provided that
$\varepsilon_{x}$ satisfies equation (40), we can choose such an
$\varepsilon^{\prime}>\varepsilon_{x}$ also satisfying it.

Now, we want to determine when, given $\varepsilon$, the interval
$[\sqrt{r},\frac{\varepsilon}{2}r]$ is forced to intersect at least one red
interval. For convenience, let $\varepsilon^{\prime\prime}r=\sqrt{r}$. Then,
we will choose $r$ large enough to satisfy this condition and large enough
that $\varepsilon^{\prime}$ satisfies (40). Notice that
$[\varepsilon^{\prime\prime}r,\frac{\varepsilon}{2}r]$ intersecting some red
interval will imply there are no blue intervals in
$[\frac{\varepsilon}{2},r]$, or else we would have the green block of a red-
green-blue sequence contained in $[\varepsilon^{\prime\prime}r,r]$.
$[\varepsilon^{\prime\prime}r,\frac{\varepsilon}{2}r]$ must intersect a red
interval when the average growth rate of $K^{A}_{s}(x)$ on this interval is
strictly greater than 1. We can easily bound that growth rate as follows

(41)
$\dfrac{K^{A}_{\frac{\varepsilon}{2}r}(y)-K^{A}_{\varepsilon^{\prime\prime}r}(y)}{(\frac{\varepsilon}{2}-\varepsilon^{\prime\prime})r}\geq\dfrac{(d_{x}-\varepsilon^{\prime\prime})\frac{\varepsilon}{2}r-(d_{x}+\varepsilon^{\prime\prime})\varepsilon^{\prime\prime}r}{(\frac{\varepsilon}{2}-\varepsilon^{\prime\prime})r}.$

Since $d_{x}>1$, for any $\varepsilon>0$, there exists some
$\varepsilon^{\prime\prime}$ small enough that the right hand side is greater
than 1. Hence, for $r$ sufficiently large, $[\frac{\varepsilon}{2}r,r]$ is
covered entirely by red and green intervals.

Just as in the $S=0$ case of section 3.2, we cite the result that an interval
covered only by red and green intervals in $\hat{\mathcal{P}}$ can be covered
by an all-yellow $3C$-admissible partition. Summing over this partition using
Lemma 18 relative to $A$ with respect to $\frac{\varepsilon}{2}$ then yields

(42) $K^{A}_{r}(x\mid p_{e}x,e)\leq K^{A}_{r}(x)-r+\varepsilon r,$

which completes the proof. ∎

Equipped with this proposition, we define a new partition of $[1,r]$ for
$K^{A}_{s}(y)$. The key is that this partition will, after a certain small
precision, only use yellow intervals. Some of these yellow intervals will be
very long green intervals, and we will use the above proposition to prove an
analogue of Lemma 31 on them. Once we are able to sum over the intervals in
our partition, we are essentially done. We now define this partition
inductively.

Set $r_{0}=r$ and assume we have defined the sequence up to $r_{i}$. Take a
good partition of $[1,r_{i}]$. Let $a$ denote the minimal real such that
$[a,r_{i}]$ is the union of yellow intervals whose lengths are at most
doubling. If $a<r_{i}$ add all these yellow intervals to the partition, and
let $r_{i+1}=a$. Otherwise, let $r_{i+1}$ be the smallest precision such that
$[r_{i+1},r_{i}]$ is green, i.e., such that
$f(r_{i})=f(r_{i+1})+r_{i}-r_{i+1}$. Note that such an $r_{i+1}$ exists in
this case, since $r_{i}$ is the right endpoint of a teal interval. Greedily
combine intervals that have a less than doubling union, re-index the
intervals, and denote this partition by $\mathcal{P}$. It is easy to see that
$2r_{i+2}<r_{i}$. As a result, once we have established that we can use these
long green intervals in our sum, the conclusion of Lemma 22 follows
immediately.

Now, we prove a lower bound for $r_{i+1}$ on these green intervals (depending
on $d_{y}$) on when $r_{i}$ is sufficiently large.

######  Lemma 41.

Let $0<\varepsilon<\frac{d_{y}-1}{2}$ be given, and suppose $r_{i}$ is large
enough that for all $s>\frac{d_{y}-1}{8}r_{i}$, we have $d_{y}s-\varepsilon
s\leq K_{s}^{A}(y)\leq 2s+\varepsilon s$. Then

(43)
$r_{i+1}\geq\frac{d_{y}-1-\varepsilon}{3+\varepsilon}r_{i}\geq\frac{d_{y}-1}{8}r_{i}$

###### Proof.

The desired result is an immediate consequence of the fact that the line
$K^{A}_{r_{i}}(y)-(r_{i}-s)$ cannot intersect $K^{A}_{s}(y)$ for any
$s<\frac{d_{y}-1-\varepsilon}{3+\varepsilon}r_{i}$, hence, any green interval
with right endpoint $r_{i}$ has to have left endpoint larger than
$\frac{d_{y}-1-\varepsilon}{3+\varepsilon}r_{i}$. Now, assume $s$ is such that
$K^{A}_{r_{i}}(y)-(r_{i}-s)=K^{A}_{s}(y)$. The aforementioned fact is the
consequence of a simple calculation.

(44) $K^{A}_{r_{i}}(y)-(r_{i}-s)\geq d_{y}r_{i}-\varepsilon r_{i}-(r_{i}-s)$

whereas $K_{s}^{A}(y)\leq 2s+\varepsilon s$. Setting the bounds equal yields
$r_{i+1}\geq s\geq\frac{d_{y}-1-\varepsilon}{3+\varepsilon}r_{i}$ and thus
completes the proof. ∎

Now, we are able to state and prove the analogue of Lemma 31.

######  Lemma 42.

Suppose that $[r_{i+1},r_{i}]$ is a green interval in our constructed
partition. For any $\varepsilon>0$, provided that $r_{i+1}$ is sufficiently
large, we have

(45) $K^{A,x}_{r_{i},r_{i},r_{i+1}}(y\mid|x-y|,y)\leq\varepsilon r_{i}.$

Therefore, $K^{A,x}_{r_{i},r_{i+1}}(|x-y|\mid|x-y|)\geq
K^{A,x}_{r_{i},r_{i+1}}(y\mid y)-\varepsilon r_{i}$.

As before, the strategy is to use our projection theorem to verify that the
hypotheses of Lemma 15 hold, which immediately implies the desired bound.

###### Proof.

Let some small rational $\varepsilon>0$ be given, and assume $r_{i+1}$ is
sufficiently large. Let $\eta$ be the rational such that $\eta
r=K^{A}_{r}(y)-4\varepsilon$. Let $G=D(r,y,\eta)$ be the oracle of Lemma 14
relative to $A$. Let $z\in B_{2^{-r_{i+1}}}(y)$ and satisfying $|x-y|=|x-z|$
be given.

Letting $s=|y-z|$, we again have two cases. The $s\geq\frac{r_{i}}{2}-\log
r_{i}$ case is identical to the previous proof, so we assume
$s<\frac{r_{i}}{2}-\log r_{i}$. Lemma 29 applied relative to $(A,G)$ implies
that

(46) $K^{A,G}_{r}(z)\geq K^{A,G}_{s}(y)+K^{A,G}_{r_{i}-s,r_{i}}(x\mid
y)-K^{A,G}_{r_{i}-s}(x\mid p_{e^{\prime}}x,e^{\prime})-O(\log r).$

To bound the projection term, we need to apply Proposition 40 with respect to
$x$, $e^{\prime}$, $\frac{\varepsilon}{2}$, the constant $C$ such that
$\frac{1}{C}=\frac{d_{y}-1}{16}$, $t=s$, and $r=r_{i}-s$.

Again, we have that $r_{i+1}-1<s<\frac{r_{i}}{2}-\log r_{i}$, since $z$ is
assumed to be within $2^{-r_{i+1}}$ of $s$. Clearly, then, we can take
$r_{i}-s$ to be sufficiently large. By assumption, $1<d_{x}=D_{x}$, and by 41,
we have that

$\displaystyle s$ $\displaystyle\geq\frac{d_{y}-1}{8}r_{i}-1$
$\displaystyle\geq\frac{d_{y}-1}{8}(r_{i}-s)-1$
$\displaystyle\geq\frac{d_{y}-1}{16}(r_{i}-s)$
$\displaystyle=\frac{r_{i}-s}{C}$

Thus, we can examine sufficiently large precisions and conditions (P1) and
(P2) are satisfied. As before, (P3) is satisfied using (C2). After using some
of the properties of the oracle $G$ and taking $r_{i}-s$ to be sufficiently
large, we can apply the projection theorem relative to $A$, as below:

$\displaystyle K^{A,G}_{r_{i}}(z)$ $\displaystyle\geq
K^{A,G}_{s}(y)+K^{A,G}_{r_{i}-s,r_{i}}(x\mid y)-K^{A,G}_{r_{i}-s}(x\mid
p_{e^{\prime}}x,e^{\prime})-O(\log r)$ $\displaystyle\geq
K^{A,G}_{s}(y)+K^{A}_{r_{i}-s,r_{i}}(x\mid y)-K^{A,G}_{r_{i}-s}(x\mid
p_{e^{\prime}}x,e^{\prime})-O(\log r)$ $\displaystyle\geq
K^{A,G}_{s}(y)+K^{A}_{r_{i}-s}(x)-K^{A,G}_{r_{i}-s}(x\mid
p_{e^{\prime}}x,e^{\prime})-O(\log r)$ $\displaystyle\geq
K^{A,G}_{s}(y)+d_{x}(r_{i}-s)-\frac{\varepsilon}{2}r_{i}-K^{A}_{r_{i}-s}(x\mid
p_{e^{\prime}}x,e^{\prime})$ $\displaystyle\geq
K^{A,G}_{s}(y)+d_{x}(r_{i}-s)-d_{x}(r_{i}-s)+(r_{i}-s)-\varepsilon r_{i}$
$\displaystyle=K^{A,G}_{s}(y)+(r_{i}-s)-\varepsilon r_{i}$

Because of the choice of $\eta$, for small enough $\varepsilon$ we can
guarantee that $K^{A,G}_{s}(y)=K^{A}_{s}(y)-O(\log r_{i})$, since
$s<\frac{r_{i}}{2}$. Hence,

$K^{A,G}_{r_{i}}(z)\geq K^{A}_{s}(y)+(r_{i}-s)-2\varepsilon r_{i}.$

Finally, using the fact that these intervals are green, hence teal, we have

$\displaystyle K^{A,G}_{r_{i}}(z)$ $\displaystyle\geq
K^{A}_{s}(y)+(r_{i}-s)-2\varepsilon r_{i}$ $\displaystyle\geq
K^{A}_{r_{i}}(y)-(r_{i}-s)+(r_{i}-s)-2\varepsilon r_{i}$
$\displaystyle\geq(\eta+\varepsilon)r_{i}$

Thus, the conditions for Lemma 15 hold and we apply it, completing the proof.
∎

Now, we are able to prove the main effective theorem of this section. As
indicated, since we can now sum over our green intervals, we can begin with
the conclusion of Lemma 22.

######  Theorem 43.

There is some $\varepsilon_{x}$ sufficiently small depending only on $d_{x}$
and $d_{y}$ that, supposing $x,y\in\mathbb{R}^{2}$, $e=\frac{y-x}{|y-x|}$, and
$A,B\subseteq\mathbb{N}$ satisfy the following.

  * (C1)

$1<d_{y}<\dim^{A}(y),d_{x}<\dim^{A}(x)\leq\operatorname{Dim}^{A}(x)<D_{x}$.121212Our
condition (C1) is slightly different than before; this is just to make the
reduction easier. Specifically, it will be helpful if we now think of $d_{y}$
as a strict lower bound on the dimension of points $y$. Note that this change
will not complicate the application of Proposition 39, since we will use it on
a compact set with dimension greater than $d_{y}$.

  * (C2)

$K^{x,A}_{r}(e)=r-O(\log r)$ for all $r$.

  * (C3)

$K^{x,A,B}_{r}(y)\geq K^{A}_{r}(y)-O(\log r)$ for all sufficiently large $r$.

  * (C4)

$K^{A}_{r}(e\mid y)=r-o(r)$ for all $r$.

Then, $\operatorname{Dim}^{A}(x)-\dim^{A}(x)<\varepsilon_{x}$ implies

$\dim^{x,A}(|x-y|)=1$

###### Proof.

Let $\varepsilon>0$ be given. Let $r$ be large enough that applying Lemma 22
in the form of equation (9), we have

(47) $K^{A,x}_{r}(|x-y|)\geq
K^{A}_{r}(y)-\sum\limits_{i\in\textbf{Bad}}K^{A}_{a_{i+1},a_{i}}(y\mid
y)-(a_{i+1}-a_{i})-\frac{\varepsilon}{2}r.$

Recalling that the complexity grows at an average rate of exactly 1 on green
intervals, thus implies

(48) $\displaystyle K^{A,x}_{r}(|x-y|)$ $\displaystyle\geq
K^{A}_{r}(y)-\sum\limits_{i\in\mathcal{P}}K^{A}_{a_{i+1},a_{i}}(y\mid
y)-(a_{i+1}-a_{i})-\frac{\varepsilon}{2}r$ (49) $\displaystyle\geq
K^{A}_{r}(y)-K^{A}_{r}(y)+r-\varepsilon r$ (50)
$\displaystyle=(1-\varepsilon)r$

Taking $\varepsilon$ as small as desired then letting $r$ go to infinity
completes the proof. ∎

Finally, we state and prove the classical result.

######  Theorem 44.

Let $X\subseteq\mathbb{R}^{2}$ be such that $1<d_{x}<\dim_{H}(X)=\dim_{P}(X)$
and let $Y\subseteq\mathbb{R}^{2}$ be analytic and satisfy
$1<d_{y}<\dim_{H}(Y)$. Then there is some $F\subseteq X$ such that,

$\dim_{H}(\Delta_{x}Y)=1$

for all $x\in F$. Moreover, $\dim_{H}(X\setminus F)<\dim_{H}(X)$.

###### Proof.

Let $X$ and $Y$ be as above, and let $B$ be the trivial oracle. $Y$ is
analytic, thus for any $d_{y}<s<\dim_{H}(Y)$, there is a compact $Y_{s}$ such
that $0<\mathcal{H}^{s}(Y_{s})<\infty$. Fix some such $s$ and a corresponding
$Y_{s}$, and let $A_{s}$ be its effective compactness oracle.

Now, we use the general point-to-set principle. Let $A_{Y}$ and $A_{X}$ be
packing oracles for $Y$ and $X$ respectively. Now, take the join of
$A_{X},A_{Y}$, and $A_{s}$ and call this new oracle $A$.

Relative to $A$, we may apply Lemma 39 to $Y_{s}$, giving a corresponding
exceptional set $G$. Note that we choose $A$ such that the desired packing
dimension conditions hold relative to $A$ for _any_ $x\in X$. In light of this
fact and observing that $\dim_{H}(X)>d_{x}\geq\dim_{H}(G)$, the set of
$x\in{X}$ for which there is some $y\in Y_{s}$ satisfying conditions relative
to $A$ (C1)-(C4) is nonempty. Then for all $x\in X-G$, there is a $y\in Y_{s}$
such that (C1)-(C4) hold with $A$ as the oracle.

Now, further refine $X-G$ by removing all the points such that
$\operatorname{Dim}_{P}(X)-\dim^{A}(x)\geq\varepsilon_{x}$ for the
$\varepsilon_{x}$ in Theorem 43. Since $A$ is a packing oracle for $X$, this
implies that the remaining points satisfy
$\operatorname{Dim}^{A}(x)-\dim^{A}(x)<\varepsilon_{x}$ Letting $F$ denote
$X-\left(G\cup\\{x:\operatorname{Dim}_{P}(X)-\dim^{A}(x)\\}\right)$
immediately implies that all $x\in F$ satisfy the requirements of Theorem 43,
and furthermore that $\dim_{H}(X\setminus F)<\dim_{H}(X)$.

Finally, applying the effective theorem yields that $\dim^{A,x}(|x-y|)=1$ for
such a pair $x,y$. By Observation 12, since $Y_{s}$ is effectively compact
relative to $A$, $\Delta_{x}Y_{s}$ is effectively compact relative to $(A,x)$.
Finishing the proof, by theorem 11, we have that

$\displaystyle\dim_{H}(\Delta_{x}Y)$
$\displaystyle\geq\dim_{H}(\Delta_{x}Y_{s})$ $\displaystyle=\sup_{y\in
Y_{s}}\dim^{A,x}(|x-y|)$ $\displaystyle=1$

∎

## References

  * [1] Adam Case and Jack H. Lutz, _Mutual dimension_ , ACM Transactions on Computation Theory 7 (2015), no. 3, 12.
  * [2] Chris Conidis, _Effective packing dimension of $\pi_{0}^{1}$-classes_, Proceedings of the American Mathematical Society 136 (2008), no. 10, 3655–3662. MR 2415051
  * [3] Xiumin Du, Yumeng Ou, Kevin Ren, and Ruixiang Zhang, _New improvement to falconer distance set problem in higher dimensions_ , 2023.
  * [4] by same author, _Weighted refined decoupling estimates and application to falconer distance set problem_ , 2023.
  * [5] Larry Guth, Alex Iosevich, Yumeng Ou, and Hong Wang, _On Falconer’s distance set problem in the plane_ , Inventiones mathematicae 219 (2020).
  * [6] John M. Hitchcock, _Correspondence principles for effective dimensions_ , Theory of Computing Systems 38 (2005), no. 5, 559–571.
  * [7] Tamás Keleti and Pablo Shmerkin, _New bounds on the dimensions of planar distance sets_ , Geometric and Functional Analysis 29 (2019), no. 6, 1886–1948. MR 4034924
  * [8] Ming Li and Paul M.B. Vitányi, _An introduction to Kolmogorov complexity and its applications_ , third ed., Springer, 2008.
  * [9] Bochen Liu, _Hausdorff dimension of pinned distance sets and the L 2-method_, Proceedings of the American Mathematical Society 148 (2020), no. 1, 333–341.
  * [10] Jack H. Lutz, _Dimension in complexity classes_ , SIAM J. Comput. 32 (2003), no. 5, 1236–1259.
  * [11] Jack H. Lutz and Neil Lutz, _Algorithmic information, plane Kakeya sets, and conditional dimension_ , ACM Trans. Comput. Theory 10 (2018), no. 2, 7:1–7:22.
  * [12] Neil Lutz and D. M. Stull, _Projection theorems using effective dimension_ , 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), 2018.
  * [13] by same author, _Bounding the dimension of points on a line_ , Information and Computation 275 (2020), 104601.
  * [14] Elvira Mayordomo, _A Kolmogorov complexity characterization of constructive Hausdorff dimension_ , Inf. Process. Lett. 84 (2002), no. 1, 1–3.
  * [15] Tuomas Orponen, _On the distance sets of Ahlfors-David regular sets_ , Adv. Math. 307 (2017), 1029–1045. MR 3590535
  * [16] by same author, _On the dimension and smoothness of radial projections_ , Analysis & PDE 12 (2019), no. 5, 1273–1294. MR 3892404
  * [17] Kevin Ren, _Discretized radial projection in $\mathbb{R}^{d}$_, 2023.
  * [18] Pablo Shmerkin, _On the hausdorff dimension of pinned distance sets_ , Israel Journal of Mathematics 230 (2019), no. 2, 949–972.
  * [19] by same author, _Improved bounds for the dimensions of planar distance sets_ , Journal of Fractal Geometry 8 (2020), no. 1, 27–51.
  * [20] D. M. Stull, _Pinned distance sets using effective dimension_ , 2022.