# Bounds on the dimension of lineal extensions

Ryan E. G. Bushling  Department of Mathematics
University of Washington, Box 354350
Seattle, WA 98195-4350<EMAIL_ADDRESS>and  Jacob B. Fiedler  Department of
Mathematics
University of Wisconsin, 480 Lincoln Drive
Madison, WI 53706-1325<EMAIL_ADDRESS>
###### Abstract.

Let $E\subseteq\mathbb{R}^{n}$ be a union of line segments and
$F\subseteq\mathbb{R}^{n}$ the set obtained from $E$ by extending each line
segment in $E$ to a full line. Keleti’s line segment extension conjecture
posits that the Hausdorff dimension of $F$ should equal that of $E$. Working
in $\mathbb{R}^{2}$, we use effective methods to prove a strong packing
dimension variant of this conjecture, from which the generalized Kakeya
conjecture for packing dimension immediately follows. This is followed by
several doubling estimates in higher dimensions and connections to related
problems.

###### Key words and phrases:

Algorithmic complexity, Kakeya conjecture

###### 2020 Mathematics Subject Classification:

Primary: 03D32, 28A80; Secondary: 68Q30

The second author was supported in part by NSF DMS-2037851 and NSF
DMS-2246906.

##  1\. Introduction and main results

Let $E=\bigcup\mathcal{I}$, where $\mathcal{I}$ is a family of line segments
in $\mathbb{R}^{n}$, $n\geq 2$. Throughout, $\mathcal{I}$ is assumed to be
maximal in the sense that, if $I$ is a line segment and
$I\subseteq\bigcup\mathcal{I}$, then $I\in\mathcal{I}$—a hypothesis that
results in no loss of generality in what follows. Denoting by
$\mathcal{A}(n,1)$ the affine Grassmannian of lines in $\mathbb{R}^{n}$, we
define the lineal extension of $\bm{E}$ to be the set $\mathrm{\mathbf{L}}(E)$
formed from $E$ by extending each $I\in\mathcal{I}$ to the unique line
$\ell_{I}\subset\mathbb{R}^{n}$ containing $I$:

$\mathrm{\mathbf{L}}(E)\ :=\ \bigcup_{I\in\mathcal{I}}\ell_{I}\ =\
\bigcup\big{\\{}\ell\in\mathcal{A}(n,1)\\!:E\cap\ell\text{ contains a line
segment}\big{\\}}.$

With this setup, Keleti [10] proposed the following conjecture. Let
$\operatorname{\dim_{\mathrm{H}}}$ denote Hausdorff dimension.

###### Conjecture 1 (Line segment extension conjecture).

Let $E\subseteq\mathbb{R}^{n}$ be a union of line segments and
$\mathrm{\mathbf{L}}(E)$ its lineal extension. Then
$\operatorname{\dim_{\mathrm{H}}}\mathrm{\mathbf{L}}(E)=\operatorname{\dim_{\mathrm{H}}}E$.

Conjecture 1 is open in dimensions $n\geq 3$ but is known for $n=2$.

###### Theorem 1.1 (Keleti [10]).

If $E\subseteq\mathbb{R}^{2}$ is a union of line segments, then
$\operatorname{\dim_{\mathrm{H}}}\mathrm{\mathbf{L}}(E)=\operatorname{\dim_{\mathrm{H}}}E$.

This article concerns variants and extensions of this problem, emphasizing the
planar case.

###  1.1. Line segment extension in $\bm{\mathbb{R}^{2}}$

We begin by introducing some notation. Let $\operatorname{\dim_{\mathrm{P}}}$
denote packing dimension.

###### Definition 1.1.

For $s\in(0,1]$ and $E\subseteq\mathbb{R}^{n}$ a union of subsets of lines
with (packing or Hausdorff) dimension at least $s$, let

$\displaystyle L_{s}^{\rm H}(E)$
$\displaystyle:=\bigcup\big{\\{}\ell\in\mathcal{A}(n,1)\\!:\operatorname{\dim_{\mathrm{H}}}(\ell\cap
E)\geq s\big{\\}}$ and $\displaystyle L_{s}^{\rm P}(E)$
$\displaystyle:=\bigcup\big{\\{}\ell\in\mathcal{A}(n,1)\\!:\operatorname{\dim_{\mathrm{P}}}(\ell\cap
E)\geq s\big{\\}}$

be, respectively, the $\bm{s}$-Hausdorff extension and $\bm{s}$-packing
extension of $\bm{E}$.111Alternatively, in the above definitions, we could
drop the requirement that $E$ be the union of certain subsets of lines and
instead write $L_{s}^{\rm
H}(E):=\bigcup\big{\\{}\ell\in\mathcal{A}(n,1)\\!:\operatorname{\dim_{\mathrm{H}}}(E\cap\ell)\geq
s\big{\\}}\cup E$, and likewise for packing dimension. One could partition $E$
into (1) the set of points covered by lines intersecting $E$ in sets of
Hausdorff dimension at least $s$ and (2) the remainder of $E$; calling the
first of these $E_{\text{lines}}$, it is easy to see that $L_{s}^{\rm
H}(E)$=$L_{s}^{\rm H}(E_{\text{lines}})\cup E$. The same holds for packing
dimension. Morally speaking, then, the actual definitions we use encompasses
all of the interesting features of the problem. In the extreme case $s=0$ we
let

$L_{0}(E):=\bigcup\big{\\{}\ell\in\mathcal{A}(n,1)\\!:\\#(\ell\cap E)\geq
2\big{\\}},$

which we call the two-point extension of $\bm{E}$.

Our first result—a generalization of Theorem 1.1—pertains to the lineal
extension of Furstenberg sets.

###### Proposition 1.2.

Let $s\in[0,1]$ and let $E\subseteq\mathbb{R}^{2}$ be a union of (at least)
$s$-Hausdorff-dimensional subsets of lines. Then
$\operatorname{\dim_{\mathrm{H}}}(L_{s}^{\rm
H}(E))\leq\operatorname{\dim_{\mathrm{H}}}E+2-2s$. In particular, if $E$ is a
union of line segments and $\mathrm{\mathbf{L}}(E)$ is its lineal extension,
then
$\operatorname{\dim_{\mathrm{H}}}\mathrm{\mathbf{L}}(E)=\operatorname{\dim_{\mathrm{H}}}E$.

Keleti’s proof of Theorem 1.1 combines Marstrand’s slicing theorem and the
“Fubini inequality” for Hausdorff measures in a simple and elegant argument,
whereas we prove Proposition 1.2 by effective methods that, in particular,
hinges on a result [15] of N. Lutz and Stull (Theorem 3.3 below). We remark
here that this is in fact implied by the Furstenberg set bound [16] of Molter
and Rela; cf. §2 below.

One motivation for Proposition 1.2 is that the proof is morally similar to
(but much simpler than) that of our main result.

###### Theorem 1.3.

If $E\subseteq\mathbb{R}^{2}$ is a union of $1$-Hausdorff-dimensional subsets
of lines, then $\operatorname{\dim_{\mathrm{P}}}(L_{1}^{\rm
H}(E))=\operatorname{\dim_{\mathrm{P}}}E$. In particular, if $E$ is a union of
line segments and $\mathrm{\mathbf{L}}(E)$ is its lineal extension, then
$\operatorname{\dim_{\mathrm{P}}}\mathrm{\mathbf{L}}(E)=\operatorname{\dim_{\mathrm{P}}}E$.

This theorem follows from a different effective analogue that cannot be proved
directly from the aforementioned Lutz–Stull result. The bulk of the proof in
§4 is establishing this analogue, which involves a sort of multiscale
application of the ideas underlying [15].

A strong “generalized Kakeya conjecture” for packing dimension (see §2.1)
follows readily from the final step of the proof of Theorem 1.3. Let
$\mathbb{P}^{n-1}:=\mathbb{S}^{n-1}/\\{\pm 1\\}$ be the set of directions of
lines in $\mathbb{R}^{n}$.

###### Corollary 1.4.

Let $E\subseteq\mathbb{R}^{2}$ and let $D\subseteq\mathbb{P}^{1}$ be the set
of directions of lines intersecting $E$ in a set of Hausdorff dimension $1$.
If $D\neq\varnothing$, then

$\operatorname{\dim_{\mathrm{P}}}D+1\leq\operatorname{\dim_{\mathrm{P}}}E.$
(1)

###  1.2. Line segment extension in $\bm{\mathbb{R}^{n}}$ and elementary
Besicovitch set estimates

Partial results in higher dimensions, including some (non-)doubling bounds on
the dimension of lineal extensions, follow from more rudimentary “two-part
code” arguments in the spirit of [1] Theorem 1.2.

###### Proposition 1.5.

If $E\subseteq\mathbb{R}^{n}$ is a union of line segments, then

$\operatorname{\dim_{\mathrm{H}}}\mathrm{\mathbf{L}}(E)\leq\operatorname{\dim_{\mathrm{H}}}E+\operatorname{\dim_{\mathrm{P}}}E-1\quad\text{and}\quad\operatorname{\dim_{\mathrm{P}}}\mathrm{\mathbf{L}}(E)\leq
2\operatorname{\dim_{\mathrm{P}}}E-1.$ (2)

Such results are connected to the Kakeya conjecture via the following theorem.
Call a subset of $\mathbb{R}^{n}$ (not necessarily Borel) a Besicovitch set if
it contains a unit line segment in every direction.

###### Theorem 1.6 (Keleti [10]).

  1. a.

If the line segment extension conjecture holds in $\mathbb{R}^{n}$ for some
$n\geq 2$, then every Besicovitch set in $\mathbb{R}^{n}$ has Hausdorff
dimension at least $n-1$.

  2. b.

If the line segment extension conjecture holds in $\mathbb{R}^{n}$ for all
$n\geq 2$, then, for every $n\geq 2$, every Besicovitch set in
$\mathbb{R}^{n}$ has packing dimension $n$.

While Theorem 1.6 assumes the full strength of Conjecture 1, with a small
modification of the final step in Keleti’s proof—to which the reader is
referred—one obtains the following generalization.

###### Lemma 1.7.

Suppose there is a function $g\\!:[0,n]^{2}\to[0,n]$ such that the following
holds:

> If $E$ is a union of line segments in $\mathbb{R}^{n}$, then
> $g(\operatorname{\dim_{\mathrm{H}}}E,\operatorname{\dim_{\mathrm{P}}}E)\geq\operatorname{\dim_{\mathrm{H}}}\mathrm{\mathbf{L}}(E)$.

Then
$g(\operatorname{\dim_{\mathrm{H}}}K,\operatorname{\dim_{\mathrm{P}}}K)\geq
n-1$ for every Besicovitch set $K\subseteq\mathbb{R}^{n}$.

As an immediate consequence of this lemma and Proposition 1.5, we obtain an
elementary estimate on the dimension of Besicovitch sets in $\mathbb{R}^{n}$.
(See also §2 for implications for the generalized Kakeya conjecture.)

###### Corollary 1.8.

If $K\subseteq\mathbb{R}^{n}$ is a Besicovitch set, then

$\operatorname{\dim_{\mathrm{H}}}K+\operatorname{\dim_{\mathrm{P}}}K\geq n.$

This is of course far from state-of-the-art, but the implication of Kakeya
inequalities from line segment extension inequalities has something of a
practical importance that we describe below.

##  2\. Background on the line segment extension conjecture and its relatives

###  2.1. History and context

Keleti [10] introduced the line segment extension problem as a natural follow-
up to the constructions of Nikodym [17] and Larman [12] showing that a union
of closed line segments in $\mathbb{R}^{n}$ can have positive Lebesgue measure
even when the union of the corresponding open line segments is Lebesgue-null.

In this same vein, Falconer and Mattila [5] introduced a “hyperplane extension
problem,” which they treated as a slicing problem with a dual projection
problem that is amenable to a Marstrand-type exceptional set estimate. The
planar case of their Theorem 3.2 weakens the hypothesis in Theorem 1.1 that
$E$ contains many line segments to the hypothesis that it contains many
positive-measure subsets of lines, which Proposition 1.2 further weakens to
$s$-dimensional subsets of lines (possibly of $\mathcal{H}^{s}$-measure $0$).
Another consequence of [5] is an equation for the dimension of a family of
hyperplanes in terms of that of its union. Héra, Keleti, and Máthé [8] pursued
this direction in arbitrary dimension and codimension, bounding the dimension
of families $\Lambda\subseteq\mathcal{A}(n,k)$ from above in terms of the
dimension of any set giving large slices to $\bigcup\Lambda$.

Redirecting attention back to the connection between the line segment
extension problem and the Kakeya problem, Keleti and Máthé [11] showed that
Theorem 1.6 has a strong converse.

###### Theorem 2.1 (Keleti–Máthé [11]).

If the Kakeya conjecture is true in $\mathbb{R}^{n}$, then the line segment
extension conjecture is true in $\mathbb{R}^{n}$.

This they established as a corollary to the equivalence of the Kakeya
conjecture with the generalized Kakeya conjecture.

###### Conjecture 2 (Generalized Kakeya conjecture).

Let $E\subseteq\mathbb{R}^{n}$ and let $D\subseteq\mathbb{P}^{n-1}$ be the set
of directions in which $E$ contains a line segment. If $D\neq\varnothing$,
then

$\operatorname{\dim_{\mathrm{H}}}D+1\leq\operatorname{\dim_{\mathrm{H}}}E.$

In particular, this conjecture is true in $\mathbb{R}^{2}$ but open in all
higher dimensions. Unlike Conjecture 2, the generalized Kakeya conjecture for
packing dimension does not seem to readily imply the packing dimension
analogue of Conjecture 1. On the Hausdorff side this implication follows from
Marstrand’s slicing theorem, of which the packing dimension analogue is
considerably weaker (cf. [4]). In fact, without additional hypotheses,
replacing Hausdorff dimension with packing dimension in the proof of
Conjecture 1 from Conjecture 2 only gives the trivial lower bound
$\operatorname{\dim_{\mathrm{P}}}E\geq 1$. It is furthermore not obvious to us
that the argument used to establish the equivalence between Kakeya and
generalized Kakeya in [11] easily adapts to packing dimension, and for these
reasons it seems surprising that both Theorem 1.3 and Corollary 1.4 fall out
of a single proof.

On a different note, it should also be remarked here that the implication in
Theorem 2.1 is not quantitative, in the sense that absolute lower bounds on
the size of Besicovitch sets (or of unions of line segments more generally) do
not translate into progress toward the line segment extension conjecture. This
stands in contrast to Lemma 1.7, according to which partial results on the
line segment conjecture do make headway on the Kakeya problem. In fact, the
equivalence between the Kakeya and generalized Kakeya conjectures proved in
[11] is also quantitative:

###### Theorem 2.2 (Keleti–Máthé [11]).

Let $E\subseteq\mathbb{R}^{n}$ and let $\varnothing\neq
D\subseteq\mathbb{P}^{n-1}$ be the set of directions in which $E$ contains a
line segment. Then there exists a compact Besicovitch set
$K\subset\mathbb{R}^{n}$ with

$\operatorname{\dim_{\mathrm{H}}}K\leq
n-1+\operatorname{\dim_{\mathrm{H}}}E-\operatorname{\dim_{\mathrm{H}}}D.$

Our method gives such inequalities of generalized Kakeya type for packing and
mixed Hausdorff-packing dimensions directly, without reference to a general
result analogous to Theorem 2.2; see the remarks following the proof of
Proposition 1.5 in §5.

###  2.2. Proposition 1.2 and the Furstenberg set conjecture

We take a moment to expound on the relationship between Proposition 1.2 and
the Furstenberg set conjecture. Call a set $E\subseteq\mathbb{R}^{2}$ an
$\bm{(s,t)}$-Furstenberg set if there exists a $t$-Hausdorff-dimensional set
$\Lambda\subseteq\mathcal{A}(2,1)$ such that

$E=\bigcup_{\ell\in\Lambda}(E\cap\ell),\qquad\text{where}\qquad\operatorname{\dim_{\mathrm{H}}}(E\cap\ell)\geq
s\hskip 7.11317pt\forall\hskip 0.83298pt\ell\in\Lambda.$

A special case of the aforementioned [5] Theorem 3.2 gives
$\operatorname{\dim_{\mathrm{H}}}L_{s}^{\rm H}(E)=t$, which in conjunction
with Proposition 1.2 entails

$t\leq\operatorname{\dim_{\mathrm{H}}}E+2-2s,\qquad\text{i.e.,}\qquad
2s+t-2\leq\operatorname{\dim_{\mathrm{H}}}E.$

When $E$ is Borel, this is essentially a consequence of the Furstenberg set
bound of Molter and Rela [16], and running the argument in reverse in turn
yields Proposition 1.2 for Borel sets from the Furstenberg set estimate.222The
authors thank Tamás Keleti and Josh Zahl for sharing this observation.

More recently, Ren and Wang fully resolved the Furstenberg set conjecture in
the plane.

###### Theorem 2.3 (Ren–Wang [21]).

If $E\subseteq\mathbb{R}^{2}$ is a Borel $(s,t)$-Furstenberg set, then

$\operatorname{\dim_{\mathrm{H}}}E\geq\min\left\\{s+t,\frac{3s+t}{2},s+1\right\\}.$

A corollary, then, is a sharpening of Proposition 1.2 for Borel sets.

###### Corollary 2.4.

Let $s\in[0,1]$ and let $E\subseteq\mathbb{R}^{2}$ be a union of (at least)
$s$-dimensional subsets of lines. If $E$ is Borel, then

$\operatorname{\dim_{\mathrm{H}}}(L_{s}^{\rm
H}(E))\leq\max\big{\\{}\operatorname{\dim_{\mathrm{H}}}E+1-s,\,2\operatorname{\dim_{\mathrm{H}}}E+1-3s,\,2-s\big{\\}}.$

The maximum here is attained according to the numerical relationship between
$\operatorname{\dim_{\mathrm{H}}}(L_{s}^{\rm H}(E))$ and $s$, and in fact the
final step in the proof of Proposition 1.2 shows that

$\operatorname{\dim_{\mathrm{H}}}(L_{s}^{\rm
H}(E))\leq\operatorname{\dim_{\mathrm{H}}}E+1-s\qquad\text{when}\qquad
s\geq\operatorname{\dim_{\mathrm{H}}}(L_{s}^{\rm H}(E)),$

recovering the corresponding case of Corollary 2.4.

Regardless of its comparative strength in view of other Furstenberg set
bounds, one reason for including Proposition 1.2 is that the setup for its
proof mirrors that of Theorem 1.3.

##  3\. Preliminaries on effective methods

###  3.1. Basic definitions

The main goal of this section is to collect in one place several tools which
we use repeatedly in the remainder of the paper, especially for the benefit of
readers less familiar with Kolmogorov complexity. We operate in the
algorithmic framework laid out in [14], which we briefly recall here to
establish terminology and notation. Let $\\{0,1\\}^{*}$ be the collection of
all finite strings over $\\{0,1\\}$, including the empty string $\emptyset$.
Fixing some prefix-free universal oracle Turing machine $U$, we define for
each pair $\sigma,\tau\in\\{0,1\\}^{*}$ the Kolmogorov complexity of
$\bm{\sigma}$ given $\bm{\tau}$ to be the minimal length of a program that,
when given to $U$ as an input with side information $\tau$, returns $\sigma$
as the output:

$K(\sigma\hskip 0.83298pt|\hskip
0.83298pt\tau):=\min\big{\\{}|\pi|\in\mathbb{N}\\!:\pi\in\\{0,1\\}^{*},\,U(\pi,\tau)=\sigma\big{\\}}.$

When $\tau=\emptyset$, we write $K(\sigma):=K(\sigma\hskip 0.83298pt|\hskip
0.83298pt\emptyset)$ and simply call this quantity the Kolmogorov complexity
of $\bm{\sigma}$.

Identifying the family of all rational vectors with $\\{0,1\\}^{*}$ via some
effective encoding $\bigcup_{n\in\mathbb{N}}\mathbb{Q}^{n}$
$\hookrightarrow\\{0,1\\}^{*}$, we may extend these definitions from strings
to real vectors as follows. Let $x\in\mathbb{R}^{n}$, $y\in\mathbb{R}^{m}$,
and $r,s\in\mathbb{N}$. We call

$K_{r}(x)\,:=\min_{p\in B(x,2^{-r})\cap\mathbb{Q}^{n}}K(p)$

the Kolmogorov complexity of $\bm{x}$ to precision $\bm{r}$ and

$K_{r,s}(x\hskip 0.83298pt|\hskip 0.83298pty)\,:=\max_{q\in
B(y,2^{-s})\cap\mathbb{Q}^{m}}\left(\min_{p\in
B(x,2^{-r})\cap\mathbb{Q}^{n}}K(p\hskip 0.83298pt|\hskip 0.83298ptq)\right)$

the Kolmogorov complexity of $\bm{x}$ to precision $\bm{r}$ given $\bm{y}$ to
precision $\bm{s}$. When $s=r$ we simply write $K_{r}(x\hskip 0.83298pt|\hskip
0.83298pty):=K_{r,r}(x\hskip 0.83298pt|\hskip 0.83298pty)$, and when $y=x$ we
write $K_{r,s}(x\hskip 0.83298pt|\hskip 0.83298ptx):=K_{r,s}(x)$.

The “universality” of $U$ refers to the fact that, for every prefix-free
oracle Turing machine $M$, there exists a program $\pi_{M}\in\\{0,1\\}^{*}$
such that

$U(\pi_{M},\sigma)=M(\sigma)\qquad\forall\hskip
0.83298pt\sigma\in\\{0,1\\}^{*}.$

The length of the shortest such $\pi_{M}$ is called the machine constant of
$M$. When it is more awkward to work with $U(\pi_{M},\,\cdot\,)$ than it is to
work with $M$ directly, we opt for the latter and then add the machine
constant to the length of the shortest $\sigma$ such that $M(\sigma)=\tau$
when computing the Kolmogorov complexity of $\tau$.

By allowing a machine access to an oracle $A\subseteq\\{0,1\\}^{*}$, we can
relativize the above definitions to $A$, in which case we embellish the
symbols $U$, $K$, and $M$ with a superscript $A$. An oracle represents extra
information that an oracle Turing machine is allowed to use in computations.
Access to an oracle can never make a computation meaningfully harder, as a
machine can always “ignore” the oracle if its information is irrelevant. In
particular, if $A$ and $B$ are oracles, then

$K_{r}^{A,B}(x)\leq K_{r}^{A}(x)+O(\log r)$

for all $x\in\mathbb{R}^{n}$.

Using some standard encoding, we can consider points in $\mathbb{R}^{n}$ as
oracles. Intuitively, conditional access to a point up to a certain precision
should be no more useful than oracle access to all of the information in that
point, and this is made precise by the inequality

$K_{r}^{A,x}(y)\leq K_{r}^{A}(y\hskip 0.83298pt|\hskip 0.83298ptx)+O(\log r).$

###  3.2. Some useful results

One key property of Kolmogorov complexity is symmetry of information. The
following quantitative form will see repeated use in this paper.

###### Lemma 3.1 (Symmetry of information [15]).

For all $A\subseteq\\{0,1\\}^{*}$, $x\in\mathbb{R}^{n}$, $y\in\mathbb{R}^{m}$,
and $r,s\in\mathbb{N}$ with $r\geq s$:

  1. a.

$\big{|}K_{r}^{A}(x\hskip 0.83298pt|\hskip
0.83298pty)+K_{r}^{A}(y)-K_{r}^{A}(x,y)\big{|}\leq O(\log
r)+O(\log\log\|y\|)$.

  2. b.

$\big{|}K_{r,s}^{A}(x)+K_{s}^{A}(x)-K_{r}^{A}(x)\big{|}\leq O(\log
r)+O(\log\log\|x\|)$.

In practice, the norms of the points we work with are fixed and independent of
the level of precision, so we frequently use these facts in the (relativized)
forms

$K_{r}^{A}(x,y)\approx K_{r}^{A}(x\hskip 0.83298pt|\hskip
0.83298pty)+K_{r}^{A}(y)\quad\text{and}\quad K_{r}^{A}(y)\approx
K_{r,s}^{A}(y)+K_{s}^{A}(y),$

where both equalities hold up to a logarithmic term in $r$. The latter of
these is particularly useful as a tool to bound the complexity of $y$ at a
given precision: its repeated use allows us to partition the interval $[1,r]$
into smaller intervals on which the complexity function of $y$ may have more
desirable properties.

We add to this another result for understanding how complexity varies with
precision. Case and J. Lutz [2] showed that, for any
$A\subseteq\\{0,1\\}^{*}$, $r,s\in\mathbb{N}$, and $x\in\mathbb{R}^{n}$,

$K_{r}^{A}(x)\leq K_{r+s}^{A}(x)\leq K_{r}^{A}(x)+ns+O(\log(s+r)).$

This bound captures two essential features of the Kolmogorov complexity of
points: it is non-decreasing, and its growth rate is essentially bounded by
$n$ on sufficiently long intervals.

Ultimately, we study the Kolmogorov complexity of points in
$x\in\mathbb{R}^{n}$ to bound their asymptotic information density. Given an
oracle $A\subseteq\\{0,1\\}^{*}$, we call

$\dim^{A}(x):=\liminf_{r\to\infty}\frac{K_{r}^{A}(x)}{r}\quad\text{and}\quad\operatorname{Dim}^{A}(x):=\limsup_{r\to\infty}\frac{K_{r}^{A}(x)}{r}$

the effective Hausdorff dimension and the effective packing dimension of
$\bm{x}$ relative to $\bm{A}$, respectively. The utility of effective
dimensions in geometric measure theory stems from the following theorem of J.
Lutz and N. Lutz.

###### Theorem 3.2 (Point-to-set principle [14]).

For every set $E\subseteq\mathbb{R}^{n}$,

$\operatorname{\dim_{\mathrm{H}}}E\,=\min_{A\subseteq\\{0,1\\}^{*}}\sup_{x\in
E}\dim^{A}(x)\quad\text{ and
}\quad\operatorname{\dim_{\mathrm{P}}}E\,=\min_{A\subseteq\\{0,1\\}^{*}}\sup_{x\in
E}\operatorname{Dim}^{A}(x).$

We frequently use the following immediate consequence of this theorem: given
some $E\subseteq\mathbb{R}^{n}$, for any oracle $A$ and $\varepsilon>0$, there
exists some $x\in E$ such that
$\dim^{A}(x)>\operatorname{\dim_{\mathrm{H}}}E-\varepsilon$, and likewise for
packing dimension.

Turning our attention to the effective dimension of points on lines, we note
the following observation of N. Lutz and Stull: for any
$A\subseteq\\{0,1\\}^{*}$ and any $x,a,b\in\mathbb{R}$,

$K_{r}^{A}(x,ax+b)\leq K_{r}^{A}(x,a,b)+O_{x,a,b}(\log r).$ (3)

This is because, for every large enough precision $r$, a Turing machine given
$x,a,b$ at precision $r$ can perform a very accurate calculation of $ax+b$ at
precision $r$. A main theme of [15] is how close this upper bound is to being
a lower bound for the points on a line, the answer to which is expressed in
the following theorem.

###### Theorem 3.3 (N. Lutz–Stull [15]).

For all $a,b,x\in\mathbb{R}$ and $A\subseteq\\{0,1\\}^{*}$,

$\dim^{A}(x\hskip 0.83298pt|\hskip
0.83298pta,b)+\min\big{\\{}\dim^{A}(a,b),\dim^{a,b}(x)\big{\\}}\leq\dim^{A}(x,ax+b).$

This is the key ingredient in our proof of Proposition 1.2. However, as the
effective packing dimension analogue of this statement is false,333The authors
appreciate Stull informing us of this in private communication. the proof of
Theorem 1.3 will require a different strategy.

##  4\. Line segment extension in the plane

###  4.1. The Hausdorff dimension bound for $\bm{s}$-Hausdorff extensions

We begin this section by using Theorem 3.3 of [15] to prove a bound on the
Hausdorff dimension of line segment extensions in the plane. This proof takes
Lutz and Stull’s result as a black box and illustrates the connection between
effective and classical theorems in this setting, which we will need to prove
Theorem 1.3.

###### Proposition 1.2, Restated.

Let $s\in[0,1]$ and let $E\subseteq\mathbb{R}^{2}$ be a union of (at least)
$s$-Hausdorff-dimensional subsets of lines. Then
$\operatorname{\dim_{\mathrm{H}}}(L_{s}^{\rm
H}(E))\leq\operatorname{\dim_{\mathrm{H}}}E+2-2s$. In particular, if $E$ is a
union of line segments and $\mathrm{\mathbf{L}}(E)$ is its lineal extension,
then
$\operatorname{\dim_{\mathrm{H}}}\mathrm{\mathbf{L}}(E)=\operatorname{\dim_{\mathrm{H}}}E$.

Proof. Write

$E=\bigcup_{\ell\in\Lambda}E_{\ell},$

where $\Lambda\subseteq\mathcal{A}(2,1)$ is the family of lines $\ell$ such
that $\operatorname{\dim_{\mathrm{H}}}E_{\ell}\geq s$ and $E_{\ell}:=\ell\cap
E$. By the point-to-set principle,

$\operatorname{\dim_{\mathrm{H}}}E=\min_{A\subseteq\\{0,1\\}^{*}}\sup_{z\in
E}\dim^{A}(z)=\min_{A\subseteq\\{0,1\\}^{*}}\sup_{\ell\in\Lambda}\hskip
0.83298pt\sup_{z\in E_{\ell}}\dim^{A}(z)$

and

$\operatorname{\dim_{\mathrm{H}}}L_{s}^{\rm
H}(E)=\min_{A\subseteq\\{0,1\\}^{*}}\sup_{z\in L_{s}^{\rm
H}(E)}\dim^{A}(z)=\min_{A\subseteq\\{0,1\\}^{*}}\sup_{\ell\in\Lambda}\hskip
0.83298pt\sup_{z\in\ell}\dim^{A}(z).$

Comparing the right-hand sides of these equations, we see it suffices to show
that

$\sup_{z\in\ell}\dim^{A}(z)\leq\sup_{z\in E_{\ell}}\dim^{A}(z)+2-2s$ (4)

for every oracle $A\subseteq\\{0,1\\}^{*}$ and every line $\ell\in\Lambda$.
Taking such an $A$ and $\ell$, we interchange the $x$\- and $y$-coordinates if
necessary so that $\ell$ is not vertical and we let $(a,b)$ be the slope-
intercept pair of $\ell$. As was observed in the previous section, for each
$x\in\mathbb{R}$ and each precision $r$,

$K_{r}^{A}(x,ax+b)\leq K_{r}^{A}(x,a,b)+o(r)\leq r+K_{r}^{A}(a,b)+o(r).$

Hence $\dim^{A}(x,ax+b)\leq\min\,\\{1+\dim^{A}(a,b),2\\}$ and, consequently,

$\sup\limits_{z\in\ell}\dim^{A}(z)\leq\min\,\\{1+\dim^{A}(a,b),2\\}.$ (5)

Now, let $S$ be the projection of $E_{\ell}$ onto the $x$-axis. Then
$\operatorname{\dim_{\mathrm{H}}}(S)\geq s$, so by the point-to-set principle,
for every $\varepsilon>0$, there exists $x_{\varepsilon}\in S$ such that
$\dim^{A,a,b}(x_{\varepsilon})\geq s-\varepsilon$. Applying Theorem 3.3, we
have

$\displaystyle\dim^{A}(x_{\varepsilon},ax_{\varepsilon}+b)$
$\displaystyle\geq\dim^{A}(x_{\varepsilon}\hskip 0.83298pt|\hskip
0.83298pta,b)+\min\,\\{\dim^{A}(a,b),\dim^{a,b}(x_{\varepsilon})\\}$
$\displaystyle\geq\dim^{A,a,b}(x_{\varepsilon})+\min\,\\{\dim^{A}(a,b),\dim^{A,a,b}(x_{\varepsilon})\\}$
$\displaystyle\geq s-\varepsilon+\min\,\\{\dim^{A}(a,b),s-\varepsilon\\}.$

Letting $\varepsilon$ go to zero gives

$\sup_{z\in E_{\ell}}\dim^{A}(z)\geq\min\,\\{s+\dim^{A}(a,b),2s\\}.$ (6)

The difference in the minima is largest when $\dim^{A}(a,b)\geq 1$, which
gives the desired bound. $\square$

###  4.2. The packing dimension bound for $\bm{1}$-Hausdorff extensions

Now we turn our attention to the packing dimension version of the line segment
extension problem. The key issue is that we do not have an analogue of Lutz
and Stull’s bound for effective packing dimension. In fact, the statement
obtained by replacing effective Hausdorff dimension with effective packing
dimension in Theorem 3.3 is simply not true.

Essentially, the inequality fails because a high packing dimension for the
pair $(a,b)$ can be the result of $K_{r}^{A}(a,b)$ growing relatively slowly
in $r$ up to some level of precision, and then significantly more quickly up
to a higher level of precision. At a key technical step in the proof, the
complexity function of $(a,b)$ needs to have certain properties, which can be
guaranteed by reducing its complexity up to precision $r$ via an oracle $D$.
This “wastes” complexity growth of $(x,a,b)$ that we would like to transfer to
$(x,ax+b)$, but since effective Hausdorff dimension only reflects a lower
bound on the asymptotic complexity growth, $D$ does not reduce the complexity
of $(x,ax+b)$ unacceptably in comparison to the effective Hausdorff dimension
of $(a,b)$. Effective packing dimension, however, reflects an upper bound on
asymptotic complexity growth, which dashes any hope for the analogous packing
inequality. We will proceed without proving an explicit lower bound on the
packing dimension of arbitrary points on a line, but will still show that for
$x$ of essentially maximal complexity at certain precisions, $(x,ax+b)$ also
has essentially maximal complexity. This will imply (a somewhat stronger
version of) the line segment extension conjecture for packing dimension in the
plane.

###### Theorem 1.3, Restated.

If $E\subseteq\mathbb{R}^{2}$ is a union of $1$-Hausdorff-dimensional subsets
of lines, then $\operatorname{\dim_{\mathrm{P}}}(L_{1}^{\rm
H}(E))=\operatorname{\dim_{\mathrm{P}}}E$. In particular, if $E$ is a union of
line segments and $\mathrm{\mathbf{L}}(E)$ is its lineal extension, then
$\operatorname{\dim_{\mathrm{P}}}\mathrm{\mathbf{L}}(E)=\operatorname{\dim_{\mathrm{P}}}E$.

The proof will proceed in four main steps. We need to establish a variant of
Theorem 3.3 that bounds the complexity growth of $(x,ax+b)$ on certain
intervals of precision, as opposed to the entirety of $[1,r]$. We will need to
consider two kinds of intervals, first teal intervals and then yellow
intervals, named as in [22]. The third step is the construction of a certain
partition of $[1,r]$ into yellow and teal intervals. Finally, we prove that
for partitions of this form and certain choices of $x$, the lower bound
arising from the partition essentially matches an upper bound at all
sufficiently large precisions.

Before we begin, we will need several lemmas, including the following slight
modification of Lemma 3.1 in [15].

###### Lemma 4.1.

Suppose $x,a,b\in\mathbb{R}$, $B\subseteq\\{0,1\\}^{*}$, $r,t\in\mathbb{N}$,
$\delta\in\mathbb{R}^{+}$, and $\varepsilon,\eta\in\mathbb{Q}^{+}$ satisfy
$r>\log(2|a|+|x|+5)+1$, $t<r$, and the following:

  1. (1)

$K_{r,t}^{B}(a,b)\leq(\eta+\varepsilon)(r-t)$.

  2. (2)

For every $(u,v)\in B\big{(}(a,b),2^{-t}\big{)}$ such that $ux+v=ax+b$,

$K_{r,t}^{B}(u,v)\geq(\eta-\varepsilon)(r-t)+\delta(r-s)$

where $s=-\log|(a,b)-(u,v)|\in(t,r]$.

Then

$K_{r,t}^{B}(x,ax+b)\geq
K_{r,t}^{B}(x,a,b)-\frac{4\varepsilon}{\delta}(r-t)-K^{B}(\varepsilon)-K^{B}(\eta)-O(\log
r).$

We note that the implicit constant may depend on $x,a,$ and $b$, but these
will be fixed in each application. The alteration as compared to [15] is the
introduction of the precision $t$, which enables us to apply this lemma not
only on intervals $[1,r]$ but to the elements of a partition. This kind of
lemma is often referred to as an “enumeration” lemma, as its proof depends on
enumerating many short strings to find one that gives an output with the
desired properties; enumeration lemmas are key technical elements of many
proofs using effective methods because they give us conditions under which a
desired lower bound holds. In the proof of our main theorem, showing that the
two conditions are satisfied is a significant element in proving the desired
bounds on yellow and teal intervals. We prove the lemma for completeness.

Proof. Let $x$, $a$, $b$, $B$, $r$, $t$, $\delta$, $\varepsilon$, and $\eta$
be as above. We first prove that it suffices to show that

$K_{r,t}^{B}(x,u,v\hskip 0.83298pt|\hskip 0.83298ptx,a,b)\leq
K_{r,t}^{B}(x,ax+b\hskip 0.83298pt|\hskip
0.83298pta,b,x)+K^{B}(\eta)+K^{B}(\varepsilon)+O(\log r).$ (7)

whenever $(u,v)$ satisfies $K_{r,t}^{B}(u,v)\leq(\eta+\varepsilon)(r-t)$ and
condition (2) of the lemma. The second condition gives that $(u,v)$ is
distance not more than $2^{-t}$ from $(a,b)$, so

$K_{r,t}^{B}(x,u,v\hskip 0.83298pt|\hskip 0.83298ptx,a,b)=K_{r,t}^{B}(x,u,v).$

Because $(x,a,b)$ contains at least as much information as $(x,ax+b)$ at
precision $t$, we also have that

$K_{r,t}^{B}(x,ax+b\hskip 0.83298pt|\hskip 0.83298pta,b,x)\leq
K_{r,t}^{B}(x,ax+b)+O(\log r).$

Applying these two facts to (7) yields

$K_{r,t}^{B}(x,u,v)\leq
K_{r,t}^{B}(x,ax+b)+K^{B}(\eta)+K^{B}(\varepsilon)+O(\log r).$ (8)

We see that $(x,a,b)$ and $(x,u,v)$ differ in two coordinates and completely
agree up to precision $t$, so by the definition of $s$,

$K_{r,t}^{B}(x,u,v)\geq K_{r,t}^{B}(x,a,b)-2(r-s)-O(\log r).$ (9)

Our extra condition on $(u,v)$ and the second condition of the lemma
immediately imply

$(\eta+\varepsilon)(r-t)\geq
K_{r,t}^{B}(u,v)\geq(\eta-\varepsilon)(r-t)+\delta(r-s),\qquad\text{so}\qquad\frac{2\varepsilon}{\delta}(r-t)\geq(r-s).$

This in conjunction with (9) entails

$K_{r,t}^{B}(x,u,v)\geq
K_{r,t}^{B}(x,a,b)-\frac{4\varepsilon}{\delta}(r-t)-O(\log r),$

and combining this with (8) gives the desired bound.

We now direct our attention to proving (7). Let $M$ be an oracle Turing
machine that does the following given access to $B$ and inputs
$(w_{1},w_{2},w_{3})\in\mathbb{Q}^{3}$,
$\pi=\pi_{1}\pi_{2}\pi_{3}\pi_{4}\pi_{5}\in\\{0,1\\}^{*}$ such that

$U^{B}(\pi_{2})=s_{1}\in\mathbb{N},\quad
U^{B}(\pi_{3})=s_{2}\in\mathbb{N},\quad
U^{B}(\pi_{4})=\zeta\in\mathbb{Q},\quad U^{B}(\pi_{5})=\iota\in\mathbb{Q}.$

First, $M^{B}$ computes $U^{B}(\pi_{1},(w_{1},w_{2},w_{3}))=(q_{1},q_{2})$.
For every program $\sigma\in\\{0,1\\}^{*}$ with length less than or equal to
$(\zeta+\iota)(s_{2}-s_{1})$, it simulates
$U^{B}(\sigma,(w_{2},w_{3}))=(p_{1},p_{2})$ in parallel. If one of the
simulations halts with $(p_{1},p_{2})\in
B\big{(}(w_{2},w_{3}),2^{-s_{1}}\big{)}$ such that
$|p_{1}q_{1}+p_{2}-q_{2}|<2^{-s_{2}}(|p_{1}|+|q_{1}|+3)$, then $M$ halts with
output $(q_{1},p_{1},p_{2})$. Let $c_{M}$ be a constant for this machine.

Now let $\pi_{1}$, $\pi_{2}$, $\pi_{3}$, $\pi_{4}$, and $\pi_{5}$ testify to

$K_{r,t}^{B}(x,ax+b\hskip 0.83298pt|\hskip 0.83298ptx,a,b),\quad
K^{B}(t),\quad K^{B}(r),\quad K^{B}(\eta),\quad\text{and}\quad
K^{B}(\varepsilon),$

respectively, and let $w_{1},w_{2},w_{3}$ be the $K$-minimizing rationals at
precision $t$ for $x,a,b$. Then $U^{B}(\pi_{1},(w_{1},w_{2},w_{3}))$ gives
$(x,ax+b)$ to precision $r$. By our hypothesis that
$K_{r,t}^{B}(a,b)\leq(\eta+\varepsilon)(r-t)$, there is a string $\sigma$ of
length at most $(\eta+\varepsilon)(r-t)$ such that
$U^{B}(\sigma,(w_{2},w_{3}))$ gives $(a,b)$ to precision $r$. Thus,
$M(\pi,(w_{1},w_{2},w_{3}))$ halts by the same geometric argument as in [15],
and the output $(q_{1},p_{1},p_{2})$ lies in
$B\big{(}(x,u,v),2^{\gamma+1-r}\big{)}$ for some $\gamma$ depending only on
$|x|$ and $|a|$. Absorbing $\gamma$ into the error term gives

$\displaystyle K_{r,t}^{B}(x,u,v\hskip 0.83298pt|\hskip
0.83298ptx,a,b)\leq|\pi|+c_{M}+O(\log r)$ $\displaystyle\qquad\leq
K_{r,t}^{B}(x,ax+b\hskip 0.83298pt|\hskip
0.83298ptx,a,b)+K^{B}(t)+K^{B}(r)+K^{B}(\eta)+K^{B}(\varepsilon)+O(\log r)$
$\displaystyle\qquad\leq K_{r,t}^{B}(x,ax+b\hskip 0.83298pt|\hskip
0.83298ptx,a,b)+K^{B}(\eta)+K^{B}(\varepsilon)+O(\log r).$

Finally observe that the string $\sigma$ which computes $(u,v)$ given access
to its first $t$ bits has length, by assumption, no greater than
$(\eta+\varepsilon)(r-t)$. Hence
$K_{r,t}^{B}(u,v)\leq(\eta+\varepsilon)(r-t)$, which in conjunction with the
above inequality completes the proof. $\square$

We also make use of Lemmas 3.2 and 3.3 from [15], stated in the form we will
need.444Lemmas 3.2 and 3.3 are used in a relativized form in [15], so we state
them in this way. The third and fourth properties in Lemma 4.3, which appear
in the proof of [15] Lemma 3.3, can also be found in [22].

###### Lemma 4.2.

Let $x,a,b\in\mathbb{R}$. For all $(u,v)\in B\big{(}(a,b),2^{-t}\big{)}$ such
that $ux+v=ax+b$ and for all $r\geq s:=-\log|(a,b)-(u,v)|$,

$K_{r}^{A}(u,v)\geq K_{s}^{A}(a,b)+K^{A}_{r-s,r}(x\hskip 0.83298pt|\hskip
0.83298pta,b)-O(\log r).$

###### Lemma 4.3.

Let $A\subseteq\\{0,1\\}^{*}$, $r\in\mathbb{N}$, $z\in\mathbb{R}^{n}$, and
$\gamma\in\mathbb{Q}^{+}$. There is an oracle $D=D(A,n,r,z,\gamma)$ satisfying
the following:

  1. (1)

For every natural number $t\leq r$,

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

  2. (2)

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

$K^{A,D}_{t,r}(y\hskip 0.83298pt|\hskip 0.83298ptz)=K^{A}_{t,r}(y\hskip
0.83298pt|\hskip 0.83298ptz)+O(\log r)\quad\text{and}\quad
K^{A,D,z}_{t}(y)=K^{A,z}_{t}(y)+O(\log r).$

  3. (3)

If $B\subseteq\\{0,1\\}^{*}$ satisfies $K^{A,B}_{r}(z)\geq K_{r}^{A}(z)-O(\log
r)$

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

  4. (4)

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

$K_{r}^{A}(u\hskip 0.83298pt|\hskip 0.83298ptw)\leq K_{r}^{A,D}(u\hskip
0.83298pt|\hskip 0.83298ptw)+K_{r}^{A}(z)-\gamma r.$

Lemma 4.2 is the key geometric observation of Lutz and Stull, and it
formalizes the statement that lines passing through the same point are either
almost parallel (in which case they contain much of the same information), or
they are transverse enough their approximations together determine the
$x$-coordinate of the intersection to a high precision.

Lemma 4.3 is common in effective arguments. Although it is lengthy to state,
the idea is rather simple: if you want to lower the complexity of a point $z$
at some precision $r$, look back to find a precision $s<r$ at which the
complexity of $z$ is what you want it to be at precision $r$. Then, let $D$
encode all of the new information in $z$ from $s$ to $r$. Property 1 says this
oracle accomplishes the goal of lowering the complexity. By contrast, the
remaining properties tell us that $D$ is not too helpful, that is, $D$ does
not undesirably lower the complexity of other objects. Specifically $D$ is not
any more helpful in any calculation than knowing $z$ up to precision $r$
(Property 2), it does not magically become more useful when combined with
other unhelpful oracles for $z$ (Property 3), and it does not reduce the
complexity of any object more than it reduces the complexity of $z$ at
precision $r$ (Property 4).

Proof of Theorem 1.3. By the same application of the point-to-set principle
used in Proposition 1.2, it suffices to show that for any planar line $\ell$
with slope-intercept pair $(a,b)$ and for any oracle
$A\subseteq\\{0,1\\}^{*}$, if $\dim^{A,a,b}(x_{\varepsilon})\geq
1-\frac{\varepsilon}{2}$ for a collection of $x_{\varepsilon}$, then

$\lim_{\varepsilon\to
0}\operatorname{Dim}^{A}(x_{\varepsilon},ax_{\varepsilon}+b)=\sup_{z\in\ell}\operatorname{Dim}^{A}(z).$
(10)

With this aim in mind, let $a,b\in\mathbb{R}$ and $A\subseteq\\{0,1\\}^{*}$ be
given. Although $K_{s}^{A}(a,b)$ is a function defined on the natural numbers,
for the purposes of our partitioning argument it is simpler to extend to all
reals $\geq 1$ by linear interpolation. For ease of notation, we continue to
use $K_{s}^{A}(a,b)$ to denote this extended function. Let
$\varepsilon\in(0,1)\cap\mathbb{Q}$ and assume $x\in\mathbb{R}$ is such that
$\dim^{A,a,b}(x)\geq 1-\frac{\varepsilon}{2}$. In the following, we will
always assume $r$ is large enough that for $s>\log r$, $(1-\varepsilon)s\leq
K^{A,a,b}_{s}(x)\leq(1+\varepsilon)s$.

Lower bound on teal intervals: Call an interval $[t,r]$ of precisions teal if

$K_{s}^{A}(a,b)\geq K_{r}^{A}(a,b)-(r-s)\qquad\forall\hskip
0.83298pts\in[t,r].$

We want to prove a lower bound on the complexity growth of $(x,ax+b)$ on such
intervals by applying Lemma 4.1. If possible,555If the average growth of
$K_{r,t}^{A}(a,b)$ is smaller than, say, $2\sqrt{\varepsilon}$, just set
$\eta=0$. We’ll get the trivial bound of $0$ for the growth on this interval
with _this_ choice of $\varepsilon$, but in practice, we will pick up any
actual growth as we pass through with smaller and smaller $\varepsilon$. pick
$\eta$ to be an element of the finite set
$\\{\frac{i}{2^{m}}\\!:m=2-\lceil\log\varepsilon\rceil\text{ and }0\leq i\leq
2^{m}\\}$ such that

$\frac{K_{r,t}^{A}(a,b)}{r-t}-2\sqrt{\varepsilon}<\eta<\frac{K_{r,t}^{A}(a,b)}{r-t}-\sqrt{\varepsilon}.$

Using Lemma 4.3, let
$D=D(A,2,r,(a,b),K^{A}_{t}(a,b)+\lfloor\eta(r-t)\rfloor)$. In particular,
observe that $D$ lowers the complexity of $K_{r}^{A}(a,b)$ by at most
$2\sqrt{\varepsilon}(r-t)+O(\log r)$. Thus, with this choice of $\eta$, it is
immediate that relative to $(A,D)$ and for sufficiently large $r$, the first
condition of Lemma 4.1 is satisfied.

Now we show the second is also satisfied. For $(u,v)\in B_{2^{-t}}(a,b)$, by
symmetry of information, Lemma 4.2, and the second property of $D$, we have

$\displaystyle K_{r,t}^{A,D}(u,v)$ $\displaystyle\geq
K_{r}^{A,D}(u,v)-K_{t}^{A,D}(u,v)-O(\log r)$ $\displaystyle\geq
K_{s}^{A,D}(a,b)+K_{r-s,r}^{A,D}(x\hskip 0.83298pt|\hskip
0.83298pta,b)-K_{t}^{A,D}(u,v)-O(\log r)$
$\displaystyle=K_{s}^{A,D}(a,b)+K_{r-s,r}^{A,D}(x\hskip 0.83298pt|\hskip
0.83298pta,b)-K_{t}^{A,D}(a,b)-O(\log r)$ $\displaystyle\geq
K_{s,t}^{A,D}(a,b)+K_{r-s,r}^{A,D}(x\hskip 0.83298pt|\hskip
0.83298pta,b)-O(\log r)$ $\displaystyle\geq
K_{s,t}^{A,D}(a,b)+K_{r-s,r}^{A}(x\hskip 0.83298pt|\hskip 0.83298pta,b)-O(\log
r)$ $\displaystyle\geq K_{s,t}^{A,D}(a,b)+K_{r-s}^{A,a,b}(x)-O(\log r).$

Because of how we choose $D$, our teal condition $K_{s}^{A}(a,b)\geq
K_{r}^{A}(a,b)-(r-s)$ implies a slightly stronger teal condition for
$K_{s}^{A,D}(a,b)$. Up to a log term, $D$ lowers the complexity of
$K_{r}^{A,D}(a,b)$ by at least $\sqrt{\varepsilon}(r-t)$. Hence, instead of
drawing a line of slope 1 intersecting the complexity function at $r$ (the
teal condition), we can draw a line of slope $(1-\sqrt{\varepsilon})$ and
$K_{s}^{A,D}(a,b)$ will still be above it on $[t,r]$. More concretely,
$K_{s}^{A,D}(a,b)\geq K^{A,D}_{r}(a,b)-(1-\sqrt{\varepsilon}(r-s)-O(\log r)$,
since, up to a log term, $D$ reduces the complexity of $(a,b)$ (relative to
$A$) more at precision $r$ than any precision $s<r$. By two applications of
symmetry of information, this in turn implies $K_{s,t}^{A,D}(a,b)\geq
K_{r,t}^{A,D}(a,b)-(1-\sqrt{\varepsilon})(r-s)-O(\log r)$. Hence,

$K_{r,t}^{A,D}(u,v)\geq
K_{r,t}^{A,D}(a,b)-(1-\sqrt{\varepsilon})(r-s)+K_{r-s}^{A,a,b}(x)-O(\log r).$

Now by our assumption on $x$, either $r-s\leq\log(r)$ or
$K^{A,a,b}_{r-s}(x)\geq(1-\varepsilon)(r-s)$ holds. In both cases, we have

$\displaystyle K_{r,t}^{A,D}(u,v)$ $\displaystyle\geq
K_{r,t}^{A,D}(a,b)-(1-\sqrt{\varepsilon})(r-s)+(1-\varepsilon)(r-s)-O(\log r)$
$\displaystyle=K_{r,t}^{A,D}(a,b)-(\varepsilon-\sqrt{\varepsilon})(r-s)-O(\log
r)$ $\displaystyle\geq\eta(r-t)-(\varepsilon-\sqrt{\varepsilon})(r-s)-O(\log
r)$
$\displaystyle=(\eta-\varepsilon+\varepsilon)(r-t)-(\varepsilon-\sqrt{\varepsilon})(r-s)-O(\log
r)$
$\displaystyle\geq(\eta-\varepsilon)(r-t)-(\varepsilon-\varepsilon-\sqrt{\varepsilon})(r-s)-O(\log
r)$ $\displaystyle\geq(\eta-\varepsilon)(r-t)+\sqrt{\varepsilon}(r-s)-O(\log
r).$

Thus, for sufficiently large $r$, we have

$K_{r,t}^{A,D}(u,v)\geq(\eta-\varepsilon)(r-t)+\frac{\sqrt{\varepsilon}}{2}(r-s).$

This is precisely the second condition of Lemma 4.1 with
$\delta=\frac{\sqrt{\varepsilon}}{2}$. Both conditions of Lemma 4.1 are
satisfied, hence applying it without any additional oracle, we obtain

$K_{r,t}^{A,D}(x,ax+b)\geq
K_{r,t}^{A,D}(x,a,b)-8\sqrt{\varepsilon}(r-t)-K(\varepsilon)-K(\eta)-O(\log
r).$ (11)

In practice, we will keep the same choice of $\varepsilon$ throughout a
partitioning argument even as $r$ goes to infinity, and we chose $\eta$ from a
fixed set that depends only on $\varepsilon$. Thus, we can treat the
complexity of these terms as constant in $r$. Furthermore, removing an oracle
can only increase complexity, up to a log term, so

$K_{r,t}^{A}(x,ax+b)\geq K_{r,t}^{A,D}(x,a,b)-8\sqrt{\varepsilon}(r-t)-O(\log
r).$ (12)

Now, applying symmetry of information and the properties of $D$ to
$K_{r,t}^{A,D}(x,a,b)$, we obtain

$\displaystyle K_{r,t}^{A,D}(x,a,b)$ $\displaystyle\geq
K_{r}^{A,D}(x,a,b)-K_{t}^{A,D}(x,a,b)-O(\log r)$ $\displaystyle\geq
K_{r}^{A,D}(x\hskip 0.83298pt|\hskip
0.83298pta,b)+K_{r}^{A,D}(a,b)-K_{t}^{A,D}(x\hskip 0.83298pt|\hskip
0.83298pta,b)-K_{t}^{A,D}(a,b)-O(\log r)$ $\displaystyle\geq
K_{r}^{A,D,a,b}(x)+K_{r}^{A,D}(a,b)-K_{t}^{A,D,a,b}(x)-K_{t}^{A,D}(a,b)-O(\log
r)$ $\displaystyle\geq
K_{r}^{A,a,b}(x)+K_{r}^{A,D}(a,b)-K_{t}^{A,a,b}(x)-K_{t}^{A,D}(a,b)-O(\log r)$
$\displaystyle\geq K_{r}^{A,a,b}(x)+K_{r,t}^{A,D}(a,b)-K_{t}^{A,a,b}(x)-O(\log
r).$

Recalling the definition of $D$, we have

$K_{r,t}^{A,D}(x,a,b)\geq
K_{r}^{A,a,b}(x)-K_{t}^{A,a,b}(x)+K_{r,t}^{A}(a,b)-2\sqrt{\varepsilon}(r-t)-O(\log
r).$

Finally, we need a lower bound on the growth
$K_{r}^{A,a,b}(x)-K_{t}^{A,a,b}(x)$. If $t<\log r$, then
$K_{r}^{A,a,b}(x)-K_{t}^{A,a,b}(x)\geq(1-\varepsilon)r-O(\log r)$, which is
better than the bound we get below. Otherwise, recall the upper bound
$K_{t}^{A,a,b}(x)\leq(1+\varepsilon)t$. If $t$ is too close to $r$, we cannot
usefully combine this upper bound with the lower bound
$K_{t}^{A,a,b}(x)\geq(1-\varepsilon)t$. But, in this case, the interval
$[t,r]$ will be too short to affect the sum of elements in the partition very
much. So, we assume $t<(1-\sqrt{\varepsilon})r$. Then

$\displaystyle\dfrac{K_{r}^{A,a,b}(x)-K_{t}^{A,a,b}(x)}{r-t}$
$\displaystyle\geq\dfrac{(1-\varepsilon)r-(1+\varepsilon)t}{r-t}$
$\displaystyle\geq\dfrac{(1-\varepsilon)r-(1+\varepsilon)(1-\sqrt{\varepsilon})r}{r-(1-\sqrt{\varepsilon})r}$
$\displaystyle=1-2\sqrt{\varepsilon}+\varepsilon$ $\displaystyle\geq
1-2\sqrt{\varepsilon}.$

Hence

$\displaystyle K_{r,t}^{A,D}(x,a,b)$
$\displaystyle\geq(1-2\sqrt{\varepsilon})(r-t)+K_{r,t}^{A}(a,b)-2\sqrt{\varepsilon}(r-t)-O(\log
r)$ $\displaystyle\geq(1-4\sqrt{\varepsilon})(r-t)+K_{r,t}^{A}(a,b)-O(\log
r).$

Combining this with inequality (12) when $r$ is sufficiently large gives

$K_{r,t}^{A}(x,ax+b)\geq(1-13\sqrt{\varepsilon})(r-t)+K_{r,t}^{A}(a,b)$ (13)

or, in the case that $t\geq(1-\sqrt{\varepsilon})r$,

$K_{r,t}^{A}(x,ax+b)\geq K_{r,t}^{A}(a,b)-13\sqrt{\varepsilon}(r-t).$ (14)

Lower bound on yellow intervals: Having done the teal case, the yellow case is
straightforward. We call an interval $[t,r]$ yellow if

$K_{s}^{A}(a,b)\geq K_{t}^{A}(a,b)+(s-t)\qquad\forall\hskip
0.83298pts\in[t,r].$

In comparison with the previous case, the complexity function on teal
intervals lies above the line of slope 1 passing through the right endpoint,
while the complexity function on yellow intervals lies above the line of slope
$1$ passing through the left endpoint. It is an easy observation that, using
an oracle $D$, we can reduce the complexity of $K_{r}^{A}(a,b)$ so that the
teal property $K_{s}^{A,D}(a,b)\geq K_{r}^{A,D}(a,b)-(r-s)-O(\log r)$ holds on
$[t,r]$, and the average growth rate of $K_{s}^{A,D}(a,b)$ on $[t,r]$ is only
slightly smaller than 1. To be concrete, we pick $D$ as follows.

$K_{s}^{A}(a,\ b)$$r$$t$$K_{s}^{A}(a,\ b)$$r$$t$$K_{s}^{A}(a,\
b)$$r$$t_{1}$$K_{s}^{A}(a,\ b)$$r$$t$$D$$t_{2}$$(i)$$(ii)$$(iii)$$(iv)$ Figure
1. Several illustrations of the behavior of yellow and teal intervals. (i) A
typical teal interval. (ii) A typical yellow interval. (iii) A yellow interval
becomes a teal interval with average growth rate close to 1 upon the addition
of a well-chosen oracle $D$. (iv) The union of a yellow interval (interval
$[t_{1},t_{2}]$) followed by a teal interval (interval $[t_{2},r]$) is either
a single yellow or a single teal interval, in this case teal.

Let $\eta$ to be an element of the finite set
$\big{\\{}\tfrac{i}{2^{m}}:m=2-\lceil\log\varepsilon\rceil\text{ and }0\leq
i\leq 2^{m}\big{\\}}$ such that

$1-2\sqrt{\varepsilon}<\eta<1-\sqrt{\varepsilon}.$

Using Lemma 4.3, let
$D=D(A,2,r,(a,b),K_{t}^{A}(a,b)+\lfloor\eta(r-t)\rfloor)$. Thus, with this
choice of $\eta$, it is immediate that relative to $(A,D)$ and for
sufficiently large $r$, the first condition of Lemma 4.1 is satisfied. If we
defined $\tilde{D}=D(A,2,r,(a,b),K^{A}_{t}(a,b)+1(r-t))$, the teal property
would hold relative to $(A,\tilde{D})$. Comparatively, the oracle $D$ further
reduces $K_{r}^{A}(a,b)$ by at least $\sqrt{\varepsilon}(r-t)$, hence, as in
the previous case, we have $K_{s,t}^{A,D}(a,b)\geq
K_{r,t}^{A,D}(a,b)-(1-\sqrt{\varepsilon})(r-s)-O(\log r)$. Since we have the
$(1-\sqrt{\varepsilon})$-teal property relative to $(A,D$), we omit the
verification of the second condition, as it becomes identical to the teal
case. Now, applying Lemma 4.1, we have

$\displaystyle K_{r,t}^{A}(x,ax+b)$ $\displaystyle\geq K_{r,t}^{A,D}(x,ax+b)$
$\displaystyle\geq
K_{r,t}^{A,D}(x,a,b)-8\sqrt{\varepsilon}(r-t)-K(\varepsilon)-K(\eta)-O(\log
r)$ $\displaystyle\geq K_{r,t}^{A,D}(x,a,b)-8\sqrt{\varepsilon}(r-t)-O(\log
r).$

As in the previous case,

$K_{r,t}^{A,D}(x,a,b)\geq
K_{r}^{A,a,b}(x)-K_{t}^{A,a,b}(x)+K_{r,t}^{A,D}(a,b)-O(\log r).$

$D$ was chosen such that the average growth rate on $[t,r]$ is at least
$1-2\sqrt{\varepsilon}$, and the same bound on the complexity growth of $x$ as
in the previous case holds, hence, if $t<(1-\sqrt{\varepsilon})r$, then

$\displaystyle K_{r,t}^{A,D}(x,a,b)$ $\displaystyle\geq
K_{r}^{A,a,b}(x)-K_{t}^{A,a,b}(x)+(1-2\sqrt{\varepsilon})(r-t)-O(\log r)$
$\displaystyle\geq(2-4\sqrt{\varepsilon})(r-t)-O(\log r).$

Combining this with our main inequality when $r$ is sufficiently large gives

$K_{r,t}^{A}(x,ax+b)\geq(2-13\sqrt{\varepsilon})(r-t);$ (15)

or, in the case that $t\geq(1-\sqrt{\varepsilon})r$,

$K_{r,t}^{A}(x,ax+b)\geq(1-13\sqrt{\varepsilon})(r-t).$ (16)

Partitioning $\bm{[1,r]}$: Our aim is now to construct, given
$A\subseteq\\{0,1\\}^{*}$, $a,b\in\mathbb{R}$, and $r$ sufficiently large, a
partition $\mathcal{P}$ of $[1,r]$ having (at least) one of the following
forms:

  1. (1)

$\mathcal{P}_{r}$ consists of one element $[1,r]$, which is teal,

  2. (2)

$\mathcal{P}_{r}$ consists of one element $[1,r]$, which is yellow, or

  3. (3)

$\mathcal{P}_{r}$ consists of two elements, $[1,c_{r}]$ and $[c_{r},r]$, where
$[1,c_{r}]$ is teal and $[c_{r},r]$ is yellow.

Note that the partition does not depend on $x$. We use a strategy similar to
[22]. The difference is that we have no restriction on the maximum length of
our intervals in our partition. Start with the partition
$[1,2],[2,3],\dots,[r-1,r]$. The slopes are constant between consecutive
integers, so every element is either teal or yellow. It is easy to observe
that the union of yellow intervals is yellow, and the union of teal intervals
is teal, so first, combine all adjacent yellow and teal intervals. Similarly,
the union of a yellow interval followed by a teal interval is either yellow or
teal, so next combine every yellow-teal pair. Repeat the first and second step
in order until _neither_ step changes the partition, then output the current
partition as $\mathcal{P}_{r}$.

This process halts, since $r$ is a finite number and each step can only
increase the length of intervals. The halting condition implies
$\mathcal{P}_{r}$ contains no yellow-yellow, teal-teal, or yellow-teal pairs.
Check that every three element partition contains one of these pairs; thus
$\mathcal{P}_{r}$ has at most two elements. But, the only valid pair is teal-
yellow. So, $\mathcal{P}_{r}$ is either a teal interval followed by a yellow
interval, or consists of only one element, which validates the construction.

For convenience, we will always consider $\mathcal{P}_{r}$ to be
$\\{[1,c_{r}]$, $[c_{r},r]\\}$ by the convention that if $\mathcal{P}_{r}$ is
of form one then $c_{r}=r$, and if $\mathcal{P}_{r}$ is of form two then
$1=c_{r}$.

Essentially tight bounds via $\bm{\mathcal{P}_{r}}$: Now, we want to upper
bound $K_{r}^{A}(x,ax+b)$ for any given $x\in\mathbb{R}$. We use two facts.
The first is that on _any_ interval, $K_{r,t}^{A}(x,ax+b)$ is essentially
upper bounded by $2(r-t)$. The second, as we have used a few times, is that
$K_{r}^{A}(x,ax+b)$ is essentially upper bounded by $K_{r}^{A}(x,a,b)$, since
precision $r$ approximations of $x,a$, and $b$ are enough to compute $ax+b$ to
a similar precision.666It is _not_ true that $K_{r,t}^{A}(x,ax+b)\leq
K_{r,t}^{A}(x,a,b)$, since $x,a$, and $b$ could all be independently random on
$[1,t]$ and then consist only of 0s on $[t,r]$; in this case, the complexity
keeps growing for $(x,ax+b)$. Informally this is because the product of $a$ up
to precision $t$ and $x$ up to precision $t$ can have length $2t$. This would
present a problem for the proof, if we did not have from the previous step
that the partition cannot be a yellow and then teal interval. We want to use
the first bound on yellow intervals and the second on teal intervals.

More formally, assume $x$ is such that

$\operatorname{Dim}^{A}(x,ax+b)\geq\sup_{z\in\ell}\operatorname{Dim}^{A}(z)-\varepsilon.$

Clearly $(x,ax+b)\in\mathbb{R}^{2}$, so for sufficiently large $r$ we have

$K_{r,t}^{A}(x,ax+b)\leq 2(r-t)+o(r)\leq(2+\varepsilon)(r-t).$ (17)

At the same time, also for sufficiently large $r$,

$K_{r}^{A}(x,ax+b)\leq K_{r}^{A}(x,a,b)+o(r)\leq K_{r}^{A}(x,a,b)+\varepsilon
r.$ (18)

Now, assume $r$ is large enough that the above bounds hold for any $s>\log r$.
We use the partition $\mathcal{P}_{r}$, applying (18) on the interval
$[1,c_{r}]$ and (17) on $[c_{r},r]$. This gives

$\displaystyle K_{r}^{A}(x,ax+b)$ $\displaystyle\leq
K_{1,c_{r}}^{A}(x,ax+b)+K_{c_{r},r}^{A}(x,ax+b)+O(\log r)$ $\displaystyle\leq
K_{c_{r}}^{A}(x,a,b)+\varepsilon c_{r}+2(r-c_{r})+\varepsilon(r-c_{r})+O(\log
r)$ $\displaystyle\leq K_{c_{r}}^{A}(x,a,b)+2(r-c_{r})+2\varepsilon r$
$\displaystyle\leq c_{r}+K_{c_{r}}^{A}(a,b)+2(r-c_{r})+3\varepsilon r.$

Now, we lower bound the complexity of $x_{\varepsilon}$, where
$x_{\varepsilon}$ satisfies the hypothesis of the yellow and teal results,
namely that for sufficiently large $r$, $s>\log r$ implies
$(1-\varepsilon)s\leq K^{A,a,b}_{s}(x)\leq(1+\varepsilon)s$. We use the fact
that $\mathcal{P}_{r}$ (and hence $c_{r}$) only depended on $A,a,b$, and $r$,
and apply the yellow and teal interval lower bounds.

$\displaystyle K_{r}^{A}(x_{\varepsilon},ax_{\varepsilon}+b)$
$\displaystyle\geq
K^{A}_{c_{r}}(x_{\varepsilon},ax_{\varepsilon}+b)+K^{A}_{r,c_{r}}(x_{\varepsilon},ax_{\varepsilon}+b)-O(\log
r)$
$\displaystyle\geq(1-13\sqrt{\varepsilon})c_{r}+K_{c_{r}}^{A}(a,b)+(2-13\sqrt{\varepsilon})(r-c_{r})+2\sqrt{\varepsilon}r-O(\log
r)$ $\displaystyle\geq
c_{r}+K_{c_{r}}^{A}(a,b)+2(r-c_{r})-28\sqrt{\varepsilon}r-O(\log r)$
$\displaystyle\geq c_{r}+K_{c_{r}}^{A}(a,b)+2(r-c_{r})-29\sqrt{\varepsilon}r,$

where the extra $2\sqrt{\varepsilon}r$ came from possibly discarding one of
the intervals if it is too short to apply our yellow and teal bounds.
Combining this lower bound with the previous upper bound gives that, for all
sufficiently large $r$,

$K_{r}^{A}(x,ax+b)-K_{r}^{A}(x_{\varepsilon},ax_{\varepsilon}+b)\leq
32\sqrt{\varepsilon}r.$

Hence,

$\operatorname{Dim}^{A}(x,ax+b)-\operatorname{Dim}^{A}(x_{\varepsilon},ax_{\varepsilon}+b)\leq
32\sqrt{\varepsilon}.$

Finally, by our choice of $x$, this gives

$\operatorname{Dim}^{A}(x_{\varepsilon},ax_{\varepsilon}+b)\geq\sup_{z\in\ell}\operatorname{Dim}^{A}(z)-33\sqrt{\varepsilon}.$
(19)

We could pick $\varepsilon$ to be arbitrarily small, so this completes the
proof. $\square$

Using one of the last inequalities of the above proof, we establish a slight
strengthening of the generalized Kakeya conjecture for packing dimension in
the plane. Specifically, we show

###### Corollary 1.4, Restated.

Let $E\subseteq\mathbb{R}^{2}$ and let $D\subseteq\mathbb{P}^{n-1}$ be the set
of directions of lines intersecting $E$ in a set of Hausdorff dimension $1$.
If $D\neq\varnothing$, then

$\operatorname{\dim_{\mathrm{P}}}D+1\leq\operatorname{\dim_{\mathrm{P}}}E.$

Proof. Let
$\Lambda=\\{\ell\in\mathcal{A}(2,1)\\!:\operatorname{\dim_{\mathrm{H}}}(E\cap\ell)=1\\}$,
let $F_{\ell}$ denote the orthogonal projection of $E\cap\ell$ onto the
$x$-axis, and let $A$ be a packing oracle for both $E$ and $D$. Identifying
$D$ with the det of slopes of lines in $\Lambda$, we see by the point-to-set
principle that the desired inequality (1) is equivalent to

$\sup_{a\in D}\operatorname{Dim}^{A}(a)+1\leq\sup_{\ell\in\Lambda}\sup_{x\in
F_{\ell}}\operatorname{Dim}^{A}(x,ax+b).$

So it suffices to show that for every $a,b\in\mathbb{R}$,
$A\subseteq\mathbb{N}$, and $S\subseteq\mathbb{R}$ of Hausdorff dimension 1,

$\operatorname{Dim}^{A}(a)+1\leq\sup_{x\in S}\operatorname{Dim}^{A}(x,ax+b).$

By the point-to-set principle, this follows if for any
$x_{\varepsilon}\in\mathbb{R}$ such that
$\dim^{A,a,b}(x_{\varepsilon})>1-\frac{\varepsilon}{2}$,

$\operatorname{Dim}^{A}(a)+1\leq\lim_{\varepsilon\to
0}\operatorname{Dim}^{A}(x_{\varepsilon},ax_{\varepsilon}+b).$

In the last section of the proof of the main theorem, we obtained the bound

$K_{r}^{A}(x_{\varepsilon},ax_{\varepsilon}+b)\geq
c_{r}+K_{c_{r}}^{A}(a,b)+2(r-c_{r})-29\sqrt{\varepsilon}r.$ (20)

Assuming $r$ is sufficiently large, this implies

$\displaystyle K_{r}^{A}(x_{\varepsilon},ax_{\varepsilon}+b)$
$\displaystyle\geq c_{r}+K_{c_{r}}^{A}(a,b)+2(r-c_{r})-29\sqrt{\varepsilon}r$
$\displaystyle\geq c_{r}+K_{c_{r}}^{A}(a)+2(r-c_{r})-30\sqrt{\varepsilon}r$
$\displaystyle\geq
c_{r}+K_{c_{r}}^{A}(a)+(r-c_{r})+K_{r,c_{r}}^{A}(a)-31\sqrt{\varepsilon}r$
$\displaystyle\geq c_{r}+K_{r}^{A}(a)+(r-c_{r})-32\sqrt{\varepsilon}r$
$\displaystyle=r+K_{r}^{A}(a)-32\sqrt{\varepsilon}r.$

This holds at every sufficiently large precision $r$, so dividing by $r$ and
taking the limit superior on both sides completes the proof. $\square$

###  4.3. Packing extensions

In comparison with $1$-Hausdorff extensions, which do not increase either the
Hausdorff or packing dimension of $E\subseteq\mathbb{R}^{2}$, the $1$-packing
extensions behave much more poorly. It is clear that the $1$ packing extension
can increase the Hausdorff dimension of set; just let $E$ be a Hausdorff
dimension 0, packing dimension 1 subset of a line. Similarly, the $1$-packing
extension can maximally increase the packing dimension of some sets $E$,
illustrated in the following example.

###### Example 4.1 ($\bm{L_{1}^{\rm P}(E)}$ can increase the packing
dimension).

Let $r_{i}$ be a rapidly increasing sequence. Define

$\displaystyle X$
$\displaystyle=\big{\\{}x=0.x_{1}x_{2}x_{3}\dots\in[0,1]\\!:j\in[r_{2i-1},r_{2i})\text{
for some }i\in\mathbb{N}\Rightarrow x_{j}=0\big{\\}}\quad\text{and}$
$\displaystyle S$
$\displaystyle=\\{a=0.a_{1}a_{2}a_{3}\dots\in[0,1]\\!:j\in[r_{2i},r_{2i+1})\text{
for some }i\in\mathbb{N}\Rightarrow a_{j}=0\big{\\}}.$

Note that $X$ and $S$ both have packing dimension $1$. Further define

$E=\\{(x,ax)\in\mathbb{R}^{2}\\!:x\in X,\,a\in S\\}.$

Clearly $E$ has packing dimension at least $1$. We get equality using the
point to set principle. For any $A\subseteq\\{0,1\\}^{*}$, $x\in X$, and $a\in
S$,

$\displaystyle K_{r}^{A}(x,ax)$ $\displaystyle\leq K_{r}(x,ax)+O(\log r)$
$\displaystyle\leq K_{r}(x,a)+O(\log r)$ $\displaystyle\leq K_{r}(x+a)+O(\log
r)$ $\displaystyle\leq r+O(\log r),$

where the second-to-last inequality holds because $x$ and $a$ can only have
nonzero digits on disjoint sets of precisions, so their sum is enough to
compute both of them. Taking the limit superior, the effective packing
dimension of any point is no more than $1$, so
$\operatorname{\dim_{\mathrm{P}}}E=1$.

Since $E$ was defined to be a collection of packing dimension $1$ subsets of
lines with slope $a$,

$\\{(x,ax)\in\mathbb{R}^{2}:x\in\mathbb{R},\,a\in S\\}\subseteq L_{1}^{\rm
P}(E).$

Let $A$ be a packing oracle for $L_{1}^{\rm P}(E)$. Let $a\in S$ be such that,
removing the intervals $[r_{2i},r_{2i+1}-1]$ from its binary expansion and
letting $\tilde{a}$ denote the remaining string, $\tilde{a}$ is random
relative to $A$. Finally, let $x$ be random relative to $(a,A)$. Let
$\varepsilon>0$ be given. By the condition on $a$, for sufficiently large $i$,
adding an oracle $D$ makes $[r_{2i},r_{2i+1}]$ a teal interval with average
loss less than $\varepsilon$, hence

$\displaystyle K^{A}_{r_{2i+1}}(x,ax)$ $\displaystyle\geq
K^{A}_{r_{2i+1},r_{2i}}(x,ax)-O(\log r_{2i+1})$ $\displaystyle\geq
K^{A,D}_{r_{2i+1},r_{2i}}(x,ax)-O(\log r_{2i+1})$ $\displaystyle\geq
K^{A}_{r_{2i+1},r_{2i}}(x,a)-\varepsilon(r_{2i+1}-r_{2i})-O(\log r_{2i+1})$
$\displaystyle\geq K^{A}_{r_{2i+1},r_{2i}}(x,a)-\varepsilon
r_{2i+1}-o(r_{2i+1})$ $\displaystyle\geq K^{A}_{r_{2i+1}}(x,a)-\varepsilon
r_{2i+1}-o(r_{2i+1})$ $\displaystyle\geq
K^{A}_{r_{2i+1}}(x)+K^{A}_{r_{2i+1}}(a)-\varepsilon r_{2i+1}-o(r_{2i+1})$
$\displaystyle\geq r_{2i+1}+r_{2i+1}-\varepsilon r_{2i+1}-o(r_{2i+1})$
$\displaystyle\geq 2r_{2i+1}-2\varepsilon r_{2i+1}.$

Taking the limit superior and letting $\varepsilon$ go to zero shows that
$\operatorname{\dim_{\mathrm{P}}}(L_{1}^{\rm P}(E))=2$.

These examples illustrate the lack of nontrivial bounds on the increase of
Hausdorff and packing dimension for $1$-packing extensions in the plane. More
generally, for $s>0$ and $E\subseteq\mathbb{R}^{2}$ we could ask for upper
bounds on

$\dim_{H}(L_{s}^{\rm
P}(E))-\dim_{H}(E)\qquad\text{and}\qquad\operatorname{\dim_{\mathrm{P}}}(L_{s}^{\rm
P}(E))-\operatorname{\dim_{\mathrm{P}}}(E).$

Slightly modifying the above examples shows that the upper bound is at least
$1$ in both cases, but would not be surprised by better examples.777We
consider the extreme case of “two-point” extensions in the next section. We
note a related problem, dimension estimates for the exceptional sets of
orthogonal directions. For Hausdorff dimension in the plane, this was solved
in [21], and is indeed closely connected to the Furstenberg set problem and
thus to line segment extension. Analogous to the worse behavior of $s$-packing
extensions, attempting to bound the packing dimension of exceptional sets or
modifying the definition of exceptional sets using packing dimension results
in a rather different problem; see [9], [4] and [18].

##  5\. Extension in higher dimensions and related problems

Given a point $z$ on a line, there are two degrees of freedom in choosing
collinear points $x,y$ such that $x+t(y-x)=z$ for some $t\in\mathbb{R}$. To
prove Proposition 1.5, we choose $x$ and $y$ such that (along with another
condition) $x$’s first coordinate encodes the largest possible quantity of
information about $y$. We justify the possibility of such an encoding as a
lemma.

###### Lemma 5.1.

For all $y\in\mathbb{R}^{n}$, $A\subseteq\\{0,1\\}^{*}$, and $\varepsilon>0$,
there exists a dense set of points $x\in\mathbb{R}$ such that, for all
sufficiently large $r$ (depending on $x$),

$K_{r}^{A}(y\hskip 0.83298pt|\hskip
0.83298ptx)\leq\max\big{\\{}K_{r}^{A}(y)-(1-\varepsilon)r,\varepsilon
r\big{\\}}.$ (21)

The idea of the proof is simple; build the point $x\in\mathbb{R}$ such that
successive segments of its binary expansion are strings that aid in the
computation of successive segments of $y$.

Proof. Given a rational $0<\delta<1$, we build a point
$x_{\delta}\in\mathbb{R}$ as follows. For each $i\in\mathbb{N}$, let
$[r_{i},r_{i+1}]$ be an interval of length $\lceil(1+\delta)^{i}\rceil$, where
$r_{0}=1$. Let $\sigma_{i}$ denote a string testifying to
$K_{r_{i},r_{i+1}}^{A}(y)$ and let $x\in[0,1]$ be the real number with binary
expansion $0.\sigma_{0}\sigma_{1}\dots$.

Let $\pi=\pi_{1}\pi_{2}\pi_{3}$, where $U^{A}(\pi_{2})$ is a finite list of
positive integer lengths $l_{0},\dots,l_{m}$. Given a side information string
$\tau$, define an oracle Turing machine $M$ that computes $M^{A}(\pi\hskip
0.83298pt|\hskip 0.83298pt\tau)$ as follows. The machine $M$ first calculates
$U^{A}(\tau)=q\in\mathbb{Q}$ and determines the successive strings
$q_{0},\dots,q_{j}$ of lengths $l_{0},\dots,l_{j}$ formed from the binary
digits of $q$. It then iteratively computes $U^{A}(q_{1})=p_{1}$,
$U^{A}(q_{2},p_{1})=p_{2}$, …, $U^{A}(q_{j},p_{j-1})=p_{j}$ and returns
$M^{A}(\pi\hskip 0.83298pt|\hskip 0.83298pt\tau)=U^{A}(\pi_{1},p_{j})$ as the
output. Let $c_{M}$ be a constant for this machine.

Now let $r\in\mathbb{N}$ be sufficiently large and let $t=r_{k}$ be the lesser
of (1) the largest precision $r_{i}$ as defined above such that
$K_{r_{i}}^{A}(y)\leq r$ and (2) the smallest precision $r_{i}$ such that
$r_{i}\geq r$. (This $r$ can be assumed to be large enough that
$K_{r_{1}}^{A}(y)\leq r$.) If there is no largest such $r_{i}$ in (1), we
consider this term to be $\infty$ and default to the $r_{i}$ given by (2). As
$\\{r_{i}\\}_{i\in\mathbb{N}}$ is an increasing sequence tending to infinity,
such an $r_{i}$ clearly exists.

Let $\pi_{1}$ testify to $K_{r,t}^{A}(y)$, let $\pi_{2}$ testify to
$K^{A}\big{(}K^{A}_{r_{0}}(y),K^{A}_{r_{1},r_{0}}(y),\dots,K^{A}_{r_{k},r_{k-1}}(y)\big{)}$,
and let $\tau$ testify to $K_{r}^{A}(x_{\delta})$. It is easy to check that,
on these inputs, $M$ outputs a precision $r$ estimate of $y$; from the
definition of $x$, the $q_{i}$ are precisely the strings that give the
additional information in $y$ from precision $r_{i}$ to precision $r_{i+1}$.
Hence

$\displaystyle K_{r}^{A}(y\hskip 0.83298pt|\hskip 0.83298ptx_{\delta})$
$\displaystyle\leq
K_{r,t}^{A}(y)+K^{A}\big{(}K^{A}_{r_{0}}(y),K_{r_{1},r_{0}}^{A}(y),\dots,K_{r_{k},r_{k-1}}^{A}(y)\big{)}+c_{M}$
$\displaystyle\leq K_{r,t}^{A}(y)+O(k\log r),$

where the second inequality follows from the fact that each complexity in the
list is some integer between $0$ and $r$. Since $k\leq O(\log r)$ by the
definition of $t$,

$K_{r}^{A}(y\hskip 0.83298pt|\hskip 0.83298ptx_{\delta})\leq
K_{r,t}^{A}(y)+O((\log r)^{2}).$

Now consider the two cases for the choice of $t$. If $t>r$, then
$K_{r,t}^{A}(y)\leq O(\log r)$ and for sufficiently large $r$

$K_{r}^{A}(y\hskip 0.83298pt|\hskip 0.83298ptx_{\delta})\leq O((\log
r)^{2})<3n\delta r.$ (22)

For the case that $t<r$, let $s$ be the smallest integer precision such that
$K_{s}^{A}(y)\geq r$. Then $t\leq s$, so

$\displaystyle K_{r}^{A}(y\hskip 0.83298pt|\hskip 0.83298ptx_{\delta})$
$\displaystyle\leq K_{r,s}^{A}(y)+K_{s,t}^{A}(y)+O((\log r)^{2})$
$\displaystyle\leq K_{r}^{A}(y)-K_{s}^{A}(y)+K_{s,t}^{A}(y)+O((\log r)^{2})$
$\displaystyle\leq K_{r}^{A}(y)-r+K_{s,t}^{A}(y)+O((\log r)^{2})$
$\displaystyle\leq K_{r}^{A}(y)-r+n(s-t)+O((\log r)^{2})$

by the choice of $t$ and $s$, $s<r_{k+1}$. Hence,

$\displaystyle K_{r}^{A}(y\hskip 0.83298pt|\hskip 0.83298ptx_{\delta})$
$\displaystyle\leq K_{r}^{A}(y)-r+n(r_{k+1}-r_{k})+O((\log r)^{2})$
$\displaystyle\leq K_{r}^{A}(y)-r+2n\delta r_{k+1}+O((\log r)^{2})$
$\displaystyle\leq K_{r}^{A}(y)-r+2n\delta r+O((\log r)^{2}).$

So, for all $r$ sufficiently large that $n\delta r$ dominates the $O((\log
r)^{2})$ term, we have

$K_{r}^{A}(y\hskip 0.83298pt|\hskip 0.83298ptx_{\delta})\leq
K_{r}^{A}(y)-r+3n\delta r.$ (23)

Picking $\delta<\tfrac{\varepsilon}{3n}$ and combining (22) and (23) gives the
existence of one $x$ satisfying (21). Appending the digits of $x$ to any
dyadic number (which are dense) gives the same property for sufficiently large
$r$, completing the proof. $\square$

For simplicity and considering how it is used below, we stated the lemma for
$x\in\mathbb{R}$, but an almost identical proof allows one to encode
information about $y\in\mathbb{R}^{n}$ within $x\in\mathbb{R}^{m}$.

###### Proposition 1.5, Restated.

If $E\subseteq\mathbb{R}^{n}$ is a union of line segments, then

$\operatorname{\dim_{\mathrm{H}}}\mathrm{\mathbf{L}}(E)\leq\operatorname{\dim_{\mathrm{H}}}E+\operatorname{\dim_{\mathrm{P}}}E-1\quad\text{and}\quad\operatorname{\dim_{\mathrm{P}}}\mathrm{\mathbf{L}}(E)\leq
2\operatorname{\dim_{\mathrm{P}}}E-1.$

Proof. Let $A\subseteq\\{0,1\\}^{*}$ be both a Hausdorff oracle and a packing
oracle for $E$ and let $\varepsilon>0$. Given a point $z\in\mathbb{R}^{n}$, we
construct a machine $M$ that operates as follows. Take any
$y\in\mathbb{R}^{n}$ such that $[2^{c}y_{1}]=[2^{c}z_{1}]$ for some
$c\in\mathbb{N}$, where $[\,\cdot\,]$ denotes the fractional part of a real
number; that is, the first coordinates of $y$ and $z$ agree from the $c$th
binary digit onwards. Next, let $x\in\mathbb{R}^{n}$ with $x_{1}\neq y_{1}$
and let

$t=\frac{z_{1}-x_{1}}{y_{1}-x_{1}}.$

We form a program $\pi=\pi_{1}\pi_{2}\pi_{3}\pi_{4}$, where $U^{A}(\pi_{1})=p$
is a precision $r+s$ approximation of $x$, $U^{A}(\pi_{2}\hskip
0.83298pt|\hskip 0.83298pt\pi_{1})=q$ is a precision $r+s$ approximation of
$y$, and $U^{A}(\pi_{3}\hskip 0.83298pt|\hskip
0.83298pt\pi_{1},\pi_{2},\pi_{4})=u$ is a precision $r+s$ approximation of
$t$, where $U^{A}(\pi_{4})=\lceil 2^{c}z_{1}\rceil$ and $s\in\mathbb{N}$ is
large enough that $p+u(q-p)\in B(z,2^{-r})$. (Note that $s$ depends only on
$|z_{1}-x_{1}|$ and $|z_{1}-y_{1}|$. In particular, it does not depend on
$r$.) With this data, $M^{A}(\pi)$ computes $p+u(q-p)$ by computing $p$, $q$,
and $u$ as just described.

Now let $z\in\ell_{I}\subseteq F$ and let $y\in I$ be a point such that, up to
a permutation of the axes, $[2^{c}y_{1}]=[2^{c}z_{1}]$ for some
$c\in\mathbb{N}$. Next, let $x\in I$ be a point with $x_{1}\neq y_{1}$ such
that $x_{1}$ assists in the computation of $y$ as in Lemma 5.1, i.e., such
that

$K_{r}^{A}(y\hskip 0.83298pt\hskip 0.83298pt|\hskip 0.83298pt\hskip
0.83298ptx_{1})\leq\max\big{\\{}K_{r}^{A}(y)-(1-\varepsilon)r,\varepsilon
r\big{\\}}$

for all sufficiently large $r$. Up to a loss of $O(\log r)$, the same
inequality holds with $x$ in place of $x_{1}$, the other $n-1$ coordinates of
$x$ being ignored in the computation of $y$. Finally, let $t$ be as before,
and let $\pi_{1}$, $\pi_{2}$, $\pi_{3}$, and $\pi_{4}$ witness
$K_{r+s}^{A}(x)$, $K_{r+s}^{A}(y\hskip 0.83298pt|\hskip 0.83298ptx)$,
$K_{r+s}^{A}\big{(}t\hskip 0.83298pt|\hskip 0.83298ptx,y,\lceil
2^{c}z_{1}\rceil\big{)}$, and $K^{A}\big{(}\lceil 2^{c}z_{1}\rceil\big{)}$,
respectively. Since $t$ is computable from $x$, $y$, and $\lceil
2^{c}z_{1}\rceil$, we have

$K_{r+s}^{A}\big{(}t\hskip 0.83298pt|\hskip 0.83298ptx,y,\lceil
2^{c}z_{1}\rceil\big{)}=o(r+s)=o(r).$

Hence, by the design of $M$, the choice of $x$, and symmetry of information,
the following holds for all large $r\in\mathbb{N}$:

$\displaystyle K_{r}^{A}(z)$
$\displaystyle\leq|\pi_{1}\pi_{2}\pi_{3}\pi_{4}|+c_{M}$ $\displaystyle\leq
K_{r+s}^{A}(x)+K_{r+s}^{A}(y\hskip 0.83298pt|\hskip
0.83298ptx)+K_{r+s}^{A}\big{(}t\hskip 0.83298pt|\hskip 0.83298ptx,y,\lceil
2^{c}z_{1}\rceil\big{)}+K^{A}\big{(}\lceil 2^{c}z_{1}\rceil\big{)}+c_{M}$
$\displaystyle\leq K_{r+s}^{A}(x)+K_{r+s}^{A}(y\hskip 0.83298pt|\hskip
0.83298ptx)+o(r)$ $\displaystyle\leq K_{r}^{A}(x)+K_{r}^{A}(y\hskip
0.83298pt|\hskip 0.83298ptx)+2sn+o(r)$ $\displaystyle\leq
K_{r}^{A}(x)+\max\big{\\{}K_{r}^{A}(y)-(1-\varepsilon)r,\varepsilon
r\big{\\}}+o(r).$

Dividing through by $r$ and taking the limit inferior as $r\to\infty$ gives

$\displaystyle\dim^{A}(z)$
$\displaystyle\leq\dim^{A}(x)+\max\big{\\{}\operatorname{Dim}^{A}(y)-(1-\varepsilon),\varepsilon\big{\\}}$
$\displaystyle\leq\operatorname{\dim_{\mathrm{H}}}E+\operatorname{\dim_{\mathrm{P}}}E-(1-\varepsilon),$

where we have chosen the first alternative in the maximum because
$\operatorname{\dim_{\mathrm{P}}}E\geq 1$. Taking the supremum over all $z\in
F$ gives the first inequality in (2) modulo an $\epsilon$, which we let
decrease to $0$. To obtain the second inequality in (2), we simply take the
limit superior instead of the limit inferior. $\square$

On some level, the argument is morally similar to that of [6] Theorem 6, which
leverages the dimension inequalities for product sets. Their Kakeya set
estimate

$\operatorname{\dim_{\mathrm{H}}}K+\operatorname{\dim_{\mathrm{P}}}K\geq n+1$

improves on Corollary 1.8 by $+1$, but this is to be expected, as they prove
their estimate directly rather than by way of line segment extension.

By taking the oracle $A$ in the proof of Proposition 1.5 to encode the set
$D\subseteq\mathbb{P}^{n-1}$ of directions of the segments in $\mathcal{I}$
and then computing $z$ using $x,\tfrac{x-y}{|x-y|}$ and $t$, one can modify
the conclusions of Proposition 1.5 to

$\displaystyle\operatorname{\dim_{\mathrm{H}}}\mathrm{\mathbf{L}}(E)\leq\min\big{\\{}\operatorname{\dim_{\mathrm{H}}}E+\operatorname{\dim_{\mathrm{P}}}D,\hskip
0.83298pt\operatorname{\dim_{\mathrm{H}}}D+\operatorname{\dim_{\mathrm{P}}}E\hskip
0.83298pt\big{\\}}\quad\text{and}$
$\displaystyle\operatorname{\dim_{\mathrm{P}}}\mathrm{\mathbf{L}}(E)\leq\operatorname{\dim_{\mathrm{P}}}E+\operatorname{\dim_{\mathrm{P}}}D.$

As suggested, instead of bounding the complexity of $z$ in terms of the
complexities of $x$, $y$, and $t$, one bounds this in terms of the
complexities of $x,\tfrac{x-y}{|x-y|}$ and $t$, although this renders Lemma
5.1 inapplicable as stated—hence the disappearance of the $-1$ terms. Bounding
the dimension of $D$ in terms of the dimension of $E$ is the generalized
Kakeya problem, so in practice these inequalities are no more useful than
those in (2). Playing with the choices of $x$ and $y$ in the proof likewise
allows one to derive similar inequalities that, in the absence of specific
information about $E$, do not lead to more profound information about
$\mathrm{\mathbf{L}}(E)$.

In this vein, at the cost of control over the base point $x$ and the scalar
$t$, one can turn the inequality for line segment extensions into an
inequality for “two-point extensions” (recall Definition 1.1).

###### Proposition 5.2.

If $E\subseteq\mathbb{R}^{n}$, then

$\operatorname{\dim_{\mathrm{H}}}L_{0}(E)\leq\operatorname{\dim_{\mathrm{H}}}E+\operatorname{\dim_{\mathrm{P}}}E+1\quad\text{and}\quad\operatorname{\dim_{\mathrm{P}}}L_{0}(E)\leq
2\operatorname{\dim_{\mathrm{P}}}E+1.$ (24)

Proof. The proof is the same in spirit as that of Proposition 1.5, but
forgoing the encodings greatly simplifies the matter. Let $z\in L_{0}(E)$, so
that $z=x+ty$ for some $x,y\in E$ and some $t\in\mathbb{R}$. Taking the limit
inferior of both sides of

$K_{r}^{A}(z)\leq K_{r}^{A}(x)+K_{r}^{A}(y)+K_{r}^{A}(t)+o(r)\leq
K_{r}^{A}(x)+K_{r}^{A}(y)+r+o(r)$

gives the first inequality and taking the limit superior gives the second.
$\square$

###### Example 5.1 (Sharpness of Proposition 5.2).

The inequalities in (24) are sharp in $\mathbb{R}^{2}$. Let
$C_{\alpha}\subset[0,1]$ be the middle-$\alpha$ Cantor set,
$\alpha\in\big{(}\tfrac{1}{2},1\big{)}$, so that

$s:=\operatorname{\dim_{\mathrm{H}}}C_{\alpha}=\operatorname{\dim_{\mathrm{P}}}C_{\alpha}=\frac{\log
2}{\log\tfrac{1}{2}(1-2\alpha)}\in\big{(}0,\tfrac{1}{2}\big{)}.$

Then $\mathcal{H}^{2s}(C_{\alpha}\times C_{\alpha})>0$, so by Marstrand’s
projection theorem,
$\operatorname{\dim_{\mathrm{H}}}(tC_{\alpha}-C_{\alpha})=2s$ for
$\mathcal{L}^{1}$-a.e. $t\in\mathbb{R}$. In fact, by Proposition 1.3 of [19],
it is also the case that
$\operatorname{\dim_{\mathrm{P}}}(tC_{\alpha}-C_{\alpha})=2s$ for a.e.
$t\in\mathbb{R}$, so we fix a $t$ satisfying both these equations and let

$E:=(\\{0\\}\times C_{\alpha})\cup(\\{1\\}\times tC_{\alpha}).$

Then the set of slopes of lines in $L_{0}(E)$ is simply
$(tC_{\alpha}-C_{\alpha})\cup\\{\infty\\}$, and in particular the set
$D\subset\mathbb{P}^{1}$ of directions in which $L_{0}(E)$ contains a line has
both Hausdorff and packing dimension $2s$. By the generalized Kakeya
conjecture in the plane (cf. Conjecture 2 and Theorem 2.2 above),

$\displaystyle\operatorname{\dim_{\mathrm{P}}}L_{0}(E)$
$\displaystyle\geq\operatorname{\dim_{\mathrm{H}}}L_{0}(E)\geq\operatorname{\dim_{\mathrm{H}}}D+1=2s+1$
$\displaystyle=\operatorname{\dim_{\mathrm{H}}}E+\operatorname{\dim_{\mathrm{P}}}E+1=2\operatorname{\dim_{\mathrm{P}}}E+1.$

Hence, both inequalities in (24) hold with equality. Taking an intersection of
the exceptional sets in [19] Proposition 1.3 shows that our argument similarly
works when $\alpha=\tfrac{1}{2}$ (although $tC_{\alpha}-C_{\alpha}$ may have
zero $1$-dimensional packing measure), yielding the extreme case
$\operatorname{\dim_{\mathrm{H}}}E=\operatorname{\dim_{\mathrm{P}}}E=\tfrac{1}{2}$.
In the other extreme, any two-point set poses a sharp example for
$\operatorname{\dim_{\mathrm{H}}}E=\operatorname{\dim_{\mathrm{P}}}E=0$.

Interestingly, $\operatorname{\dim_{\mathrm{P}}}E$ cannot be replaced with
$\operatorname{\dim_{\mathrm{H}}}E$ in the first inequality of Proposition
5.2. In fact, no nontrivial inequality bounding the Hausdorff dimension of the
two-point extension of a set is possible solely in terms of the Hausdorff
dimension of the original set.

###### Example 5.2 (Failure of
$\bm{\operatorname{\dim_{\mathrm{H}}}L_{0}(E)\leq
2\operatorname{\dim_{\mathrm{H}}}E+1}$).

Through a simple argument (in the spirit of [3] Example 7.8, [7], or the
construction in [1] Theorem 1.4) we observe that the analogous bound for the
Hausdorff dimension of two-point extensions severely fails. Let
$E=\\{x\in\mathbb{R}^{n}:\dim(x)=0\\}$. It is immediate by the point-to-set
principle that this set has Hausdorff dimension $0$ (although this also
follows from a simpler counting argument; see [13] Theorem 3.3.1). Its two-
point extension is

$\displaystyle L_{0}(E)$
$\displaystyle=\\{x+t(y-x)\in\mathbb{R}^{n}\\!:\dim(x)=0,\,\dim(y)=0,\,t\in\mathbb{R}\\}$
$\displaystyle\supseteq\\{2y-x\in\mathbb{R}^{n}:\dim(x)=0,\,\dim(y)=0\\},$

and since scaling a vector by a nonzero rational does not change its pointwise
dimension, it follows that

$L_{0}(E)\supseteq\\{x+y\in\mathbb{R}^{n}\\!:\dim(x)=0,\,\dim(y)=0\\}.$

Now observe that any $z\in\mathbb{R}^{n}$ can be written as the sum of two
Hausdorff dimension-$0$ points. We illustrate for $z\in[0,1]$ with binary
representation $0.z_{1}z_{2}z_{3}\dots$. Let $x=0.x_{1}x_{2}x_{3}\dots$, where
$x_{i}=z_{i}$ when there exists even $j\in\mathbb{N}$ such that $j!\leq
i<(j+1)!$ and $x_{i}=0$ otherwise. If $y=z-x$, then $x$ and $y$ both consist
of alternating blocks of zeros which rapidly increase in length; hence, they
both have effective Hausdorff dimension $0$. Repeating the same construction
in each coordinate gives the result in $\mathbb{R}^{n}$. Consequently,
$L_{0}(E)=\mathbb{R}^{n}$, so

$\operatorname{\dim_{\mathrm{H}}}L_{0}(E)=n\qquad\text{but}\qquad\operatorname{\dim_{\mathrm{H}}}E=0.$

This also poses a counterexample to any sort of “reverse continuum Beck’s
theorem”; see [20] Corollary 1.5.

## Acknowledgements

The authors thank Tamás Keleti, Don Stull, Raymond Tana, and Josh Zahl for
helpful comments on an earlier version of this paper.

## References

  * [1] Iqra Altaf, Ryan Bushling, and Bobby Wilson.  Distance sets bounds for polyhedral norms via effective dimension.  arXiv preprint arXiv:2305.06937, 2023.
  * [2] Adam Case and Jack H. Lutz.  Mutual dimension.  ACM Trans. Comput. Theory, 7(3):1–26, 2015.
  * [3] Kenneth J. Falconer.  Fractal Geometry: Mathematical Foundations and Applications.  John Wiley & Sons, 2004.
  * [4] Kenneth J. Falconer and Pertti Mattila.  The packing dimension of projections and sections of measures.  Math. Proc. Cambridge Philos. Soc., 119(4):695–713, 1996.
  * [5] Kenneth J. Falconer and Pertti Mattila.  Strong Marstrand theorems and dimensions of sets formed by subsets of hyperplanes.  J. Fractal Geom., 3(4):319–329, 2016.
  * [6] Jonathan M. Fraser, Eric J. Olson, and James C. Robinson.  Some results in support of the Kakeya conjecture.  Real Anal. Exchange, 42(2):253–268, 2017.
  * [7] Kaoru Hatano.  Notes on Hausdorff dimensions of Cartesian product sets.  Hiroshima Math. J., 1(1):17–25, 1971.
  * [8] Kornélia Héra, Tamás Keleti, and András Máthé.  Hausdorff dimension of unions of affine subspaces and of Furstenberg-type sets.  J. Fractal Geom., 6(3):263–284, 2019.
  * [9] Maarit Järvenpää.  On the upper minkowski dimension, the packing dimension, and orthogonal projections.  Ann. Acad. Sci. Fenn. Ser. A I Math. Dissertationes, 99, 1994.
  * [10] Tamás Keleti.  Are lines much bigger than line segments?  Proc. Amer. Math. Soc., 144(4):1535–1541, 2016.
  * [11] Tamás Keleti and András Máthé.  Equivalences between different forms of the Kakeya conjecture and duality of Hausdorff and packing dimensions for additive complements.  arXiv preprint arXiv:2203.15731, 2022.
  * [12] David G. Larman.  A compact set of disjoint line segments in ${E}^{3}$ whose end set has positive measure.  Mathematika, 18(1):112–125, 1971.
  * [13] Ming Li and Paul Vitányi.  An Introduction to Kolmogorov Complexity and Its Applications.  Springer, 3 edition, 2008.
  * [14] Jack H. Lutz and Neil Lutz.  Algorithmic information, plane Kakeya sets, and conditional dimension.  ACM Trans. Comput. Theory, 10(2):1–22, 2018.
  * [15] Neil Lutz and Donald M. Stull.  Bounding the dimension of points on a line.  Inform. and Comput., 275:104601, 2020.
  * [16] Ursula Molter and Ezequiel Rela.  Furstenberg sets for a fractal set of directions.  Proc. Amer. Math. Soc., 140(8):2753–2765, 2012.
  * [17] Otton Nikodym.  Sur la mesure des ensembles plans dont tous les points sont rectilinéairement accessibles.  Fund. Math., 10:116–168, 1927.
  * [18] Tuomas Orponen.  On the packing dimension and category of exceptional sets of orthogonal projections.  Ann. Mat. Pura Appl., 194:843–880, 2015.
  * [19] Yuval Peres, Károly Simon, and Boris Solomyak.  Self-similar sets of zero Hausdorff measure and positive packing measure.  Israel J. Math., 117:353–379, 2000.
  * [20] Kevin Ren.  Discretized radial projections in $\mathbb{R}^{d}$.  arXiv preprint arXiv:2309.04097, 2023.
  * [21] Kevin Ren and Hong Wang.  Furstenberg sets estimate in the plane.  arXiv preprint 2308.08819, 2023.
  * [22] Donald M. Stull.  Pinned distance sets using effective dimension.  arXiv preprint 2207.12501, 2022.