Bounds on the dimension of lineal extensions
Ryan E. G. Bushling Jacob B. Fiedler


Bounds on the dimension of lineal extensions]Bounds on the dimension of lineal extensions

Department of Mathematics 
 University of Washington, Box 354350 
 Seattle, WA 98195-4350
reb28@uw.edu

Department of Mathematics 
 University of Wisconsin, 480 Lincoln Drive 
 Madison, WI 53706-1325
jbfiedler2@wisc.edu
[2020]Primary: 03D32, 28A80; Secondary: 68Q30

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



    Let E ⊆ℝ^n be a union of line segments and F ⊆ℝ^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 ℝ^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.


[
    Jacob B. Fiedler
    April 29, 2024
====================





§ INTRODUCTION AND MAIN RESULTS


Let E = ⋃ℐ, where ℐ is a family of line segments in ^n, n ≥ 2. Throughout, ℐ is assumed to be maximal in the sense that, if I is a line segment and I ⊆⋃ℐ, then I ∈ℐ—a hypothesis that results in no loss of generality in what follows. Denoting by 𝒜(n,1) the affine Grassmannian of lines in ^n, we define the lineal extension of E to be the set L(E) formed from E by extending each I ∈ℐ to the unique line ℓ_I ⊂^n containing I:

    L(E)  :=  ⋃_I ∈ℐℓ_I  =  ⋃{ℓ∈𝒜(n,1) : E ∩ℓ contains a line segment}.

With this setup, Keleti <cit.> proposed the following conjecture. Let  denote Hausdorff dimension.

 
    Let E ⊆^n be a union of line segments and L(E) its lineal extension. Then L(E) =  E.


Conjecture <ref> is open in dimensions n ≥ 3 but is known for n=2.

 
    If E ⊆^2 is a union of line segments, then L(E) =  E.


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



 §.§ Line segment extension in R2


We begin by introducing some notation. Let  denote packing dimension.

 
    For s ∈ (0,1] and E ⊆^n a union of subsets of lines with (packing or Hausdorff) dimension at least s, let
    
    L_s^ H(E)    := ⋃{ℓ∈𝒜(n,1) :  (ℓ∩ E) ≥ s }and
            L_s^ P(E)    := ⋃{ℓ∈𝒜(n,1) :  (ℓ∩ E) ≥ s }

    be, respectively, the s-Hausdorff extension and s-packing extension of E.[Alternatively, in the above definitions, we could drop the requirement that E be the union of certain subsets of lines and instead write L_s^ H(E) := ⋃{ℓ∈𝒜(n,1) :  (E ∩ℓ) ≥ s }∪ 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_lines, it is easy to see that L_s^ H(E)=L_s^ H (E_lines) ∪ 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) := ⋃{ℓ∈𝒜(n,1) : # (ℓ∩ E) ≥ 2 },

    which we call the two-point extension of E.


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

 
    Let s ∈ [0,1] and let E ⊆^2 be a union of (at least) s-Hausdorff-dimensional subsets of lines. Then (L_s^ H(E)) ≤ E + 2 - 2s. In particular, if E is a union of line segments and L(E) is its lineal extension, then L(E) =  E.


Keleti's proof of Theorem <ref> combines Marstrand's slicing theorem and the “Fubini inequality" for Hausdorff measures in a simple and elegant argument, whereas we prove Proposition <ref> by effective methods that, in particular, hinges on a result <cit.> of N. Lutz and Stull (Theorem <ref> below). We remark here that this is in fact implied by the Furstenberg set bound <cit.> of Molter and Rela; cf. <ref> below.

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

 
    If E ⊆^2 is a union of 1-Hausdorff-dimensional subsets of lines, then (L_1^ H(E)) =  E. In particular, if E is a union of line segments and L(E) is its lineal extension, then L(E) =  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 <ref> is establishing this analogue, which involves a sort of multiscale application of the ideas underlying <cit.>.

A strong “generalized Kakeya conjecture" for packing dimension (see <ref>) follows readily from the final step of the proof of Theorem <ref>. Let ^n-1 := ^n-1/{± 1} be the set of directions of lines in ^n.

 
    Let E ⊆^2 and let D ⊆^1 be the set of directions of lines intersecting E in a set of Hausdorff dimension 1. If D ≠∅, then
    
    D + 1 ≤ E.





 §.§ Line segment extension in Rn 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 <cit.> Theorem 1.2.

 
    If E ⊆^n is a union of line segments, then
    
    L(E) ≤ E +  E - 1   and  L(E) ≤ 2  E - 1.



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

  0

    
  * If the line segment extension conjecture holds in ^n for some n ≥ 2, then every Besicovitch set in ^n has Hausdorff dimension at least n-1.
    
  * If the line segment extension conjecture holds in ^n for all n ≥ 2, then, for every n ≥ 2, every Besicovitch set in ^n has packing dimension n.



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

 
    Suppose there is a function g : [0,n]^2 → [0,n] such that the following holds: -0.2
    
        If E is a union of line segments in ^n, then g( E,  E) ≥L(E). -0.65
    
    Then g( K,  K) ≥ n-1 for every Besicovitch set K ⊆^n.


As an immediate consequence of this lemma and Proposition <ref>, we obtain an elementary estimate on the dimension of Besicovitch sets in ^n. (See also <ref> for implications for the generalized Kakeya conjecture.)

 
    If K ⊆^n is a Besicovitch set, then
    
    K +  K ≥ 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.



§ BACKGROUND ON THE LINE SEGMENT EXTENSION CONJECTURE AND ITS RELATIVES
 



 §.§ History and context
 

Keleti <cit.> introduced the line segment extension problem as a natural follow-up to the constructions of Nikodym <cit.> and Larman <cit.> showing that a union of closed line segments in ^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 <cit.> 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 <ref> that E contains many line segments to the hypothesis that it contains many positive-measure subsets of lines, which Proposition <ref> further weakens to s-dimensional subsets of lines (possibly of ℋ^s-measure 0). Another consequence of <cit.> is an equation for the dimension of a family of hyperplanes in terms of that of its union. Héra, Keleti, and Máthé <cit.> pursued this direction in arbitrary dimension and codimension, bounding the dimension of families Λ⊆𝒜(n,k) from above in terms of the dimension of any set giving large slices to ⋃Λ.

Redirecting attention back to the connection between the line segment extension problem and the Kakeya problem, Keleti and Máthé <cit.> showed that Theorem <ref> has a strong converse.

 
    If the Kakeya conjecture is true in ^n, then the line segment extension conjecture is true in ^n.


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

 
    Let E ⊆^n and let D ⊆^n-1 be the set of directions in which E contains a line segment. If D ≠∅, then
    
    D + 1 ≤ E.



In particular, this conjecture is true in ^2 but open in all higher dimensions. Unlike Conjecture <ref>, the generalized Kakeya conjecture for packing dimension does not seem to readily imply the packing dimension analogue of Conjecture <ref>. On the Hausdorff side this implication follows from Marstrand's slicing theorem, of which the packing dimension analogue is considerably weaker (cf. <cit.>). In fact, without additional hypotheses, replacing Hausdorff dimension with packing dimension in the proof of Conjecture <ref> from Conjecture <ref> only gives the trivial lower bound E ≥ 1. It is furthermore not obvious to us that the argument used to establish the equivalence between Kakeya and generalized Kakeya in <cit.> easily adapts to packing dimension, and for these reasons it seems surprising that both Theorem <ref> and Corollary <ref> fall out of a single proof.

On a different note, it should also be remarked here that the implication in Theorem <ref> 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 <ref>, 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 <cit.> is also quantitative:

 
    Let E ⊆^n and let ∅≠ D ⊆^n-1 be the set of directions in which E contains a line segment. Then there exists a compact Besicovitch set K ⊂^n with
    
    K ≤ n-1 +  E -  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 <ref>; see the remarks following the proof of Proposition <ref> in <ref>.



 §.§ Proposition <ref> and the Furstenberg set conjecture


We take a moment to expound on the relationship between Proposition <ref> and the Furstenberg set conjecture. Call a set E ⊆^2 an (s,t)-Furstenberg set if there exists a t-Hausdorff-dimensional set Λ⊆𝒜(2,1) such that

    E = ⋃_ℓ∈Λ (E ∩ℓ),     where    (E ∩ℓ) ≥ s 0.25∀ℓ∈Λ.

A special case of the aforementioned <cit.> Theorem 3.2 gives L_s^ H(E) = t, which in conjunction with Proposition <ref> entails

    t ≤ E + 2 - 2s,     i.e.,     2s + t - 2 ≤ E.

When E is Borel, this is essentially a consequence of the Furstenberg set bound of Molter and Rela <cit.>, and running the argument in reverse in turn yields Proposition <ref> for Borel sets from the Furstenberg set estimate.[The 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.


    If E ⊆^2 is a Borel (s,t)-Furstenberg set, then
    
    E ≥min{ s+t, 3s+t/2, s+1 }.



A corollary, then, is a sharpening of Proposition <ref> for Borel sets.

 
    Let s ∈ [0,1] and let E ⊆^2 be a union of (at least) s-dimensional subsets of lines. If E is Borel, then
    
    (L_s^ H(E)) ≤max{ E + 1 - s,   2  E + 1 - 3s,   2 - s }.



The maximum here is attained according to the numerical relationship between (L_s^ H(E)) and s, and in fact the final step in the proof of Proposition <ref> shows that 

    (L_s^ H(E)) ≤ E + 1 - s     when     s ≥(L_s^ H(E)),

recovering the corresponding case of Corollary <ref>.

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




§ PRELIMINARIES ON EFFECTIVE METHODS
 



 §.§ 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 <cit.>, 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 ∅. Fixing some prefix-free universal oracle Turing machine U, we define for each pair σ,τ∈{0,1}^* the Kolmogorov complexity of σ given τ to be the minimal length of a program that, when given to U as an input with side information τ, returns σ as the output:

    K(σ|τ) := min{ |π| ∈: π∈{0,1}^*,   U(π,τ) = σ}.

When τ = ∅, we write K(σ) := K(σ|∅) and simply call this quantity the Kolmogorov complexity of σ.

Identifying the family of all rational vectors with {0,1}^* via some effective encoding ⋃_n ∈^n ↪{0,1}^*, we may extend these definitions from strings to real vectors as follows. Let x ∈^n, y ∈^m, and r,s ∈. We call

    K_r(x)   := min_p ∈ B(x,2^-r) ∩^n K(p)

the Kolmogorov complexity of x to precision r and

    K_r,s(x|y)   := max_q ∈ B(y,2^-s) ∩^m( min_p ∈ B(x,2^-r) ∩^n K(p | q) )

the Kolmogorov complexity of x to precision r given y to precision s. When s=r we simply write K_r(x | y) := K_r,r(x | y), and when y=x we write K_r,s(x | x) := 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 π_M ∈{0,1}^* such that

    U(π_M,σ) = M(σ)     ∀σ∈{0,1}^*.

The length of the shortest such π_M is called the machine constant of M. When it is more awkward to work with U(π_M,  · ) 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 σ such that M(σ) = τ when computing the Kolmogorov complexity of τ.

By allowing a machine access to an oracle A ⊆{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) ≤ K_r^A(x) + O(log r)

for all x ∈^n.

Using some standard encoding, we can consider points in ^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) ≤ K_r^A(y | x) + O(log r).




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

 
    For all A ⊆{0,1}^*, x ∈^n, y ∈^m, and r,s ∈ with r ≥ s: -0.15
    
        
  * | K_r^A(x | y) + K_r^A(y) - K_r^A(x,y) | ≤ O(log r) + O(loglogy).
        
  * | K_r,s^A(x) + K_s^A(x) - K_r^A(x) | ≤ O(log r) + O(loglogx).
    


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) ≈ K_r^A(x | y) + K_r^A(y)   and   K_r^A(y) ≈ 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 <cit.> showed that, for any A ⊆{0,1}^*, r,s ∈, and x ∈^n,

    K_r^A(x) ≤ K_r+s^A(x) ≤ 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 ∈^n to bound their asymptotic information density. Given an oracle A ⊆{0,1}^*, we call

    ^A(x) := lim inf_r →∞K_r^A(x)/r  and  ^A(x) := lim sup_r →∞K_r^A(x)/r

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

 
    For every set E ⊆^n,
    
    E   = min_A ⊆{0,1}^*sup_x ∈ E^A(x)    and    E   = min_A ⊆{0,1}^*sup_x ∈ E^A(x).



We frequently use the following immediate consequence of this theorem: given some E ⊆^n, for any oracle A and > 0, there exists some x ∈ E such that ^A(x) >  E -, 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 ⊆{0,1}^* and any x,a,b ∈, 

    K_r^A(x, ax+b) ≤ K_r^A(x,a,b) + O_x,a,b(log r).

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 <cit.> 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.

 
    For all a,b,x ∈ and A ⊆{0,1}^*,
    
    ^A(x | a,b) + min{^A(a,b), ^a,b(x) }≤^A(x,ax+b).



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



§ LINE SEGMENT EXTENSION IN THE PLANE
 



 §.§ The Hausdorff dimension bound for s-Hausdorff extensions
 We begin this section by using Theorem <ref> of <cit.> 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 <ref>.

[<ref>, Restated]
    Let s ∈ [0,1] and let E ⊆^2 be a union of (at least) s-Hausdorff-dimensional subsets of lines. Then (L_s^ H(E)) ≤ E + 2 - 2s. In particular, if E is a union of line segments and L(E) is its lineal extension, then L(E) =  E.


Proof. Write

    E = ⋃_ℓ∈Λ E_ℓ,

where Λ⊆𝒜(2,1) is the family of lines ℓ such that E_ℓ≥ s and E_ℓ := ℓ∩ E. By the point-to-set principle,

    E = min_A ⊆{0,1}^*sup_z ∈ E^A(z) = min_A ⊆{0,1}^*sup_ℓ∈Λsup_z ∈ E_ℓ^A(z)

and

    L_s^ H(E) = min_A ⊆{0,1}^*sup_z ∈ L_s^ H(E)^A(z) = min_A ⊆{0,1}^*sup_ℓ∈Λsup_z ∈ℓ^A(z).

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

    sup_z ∈ℓ^A(z) ≤sup_z ∈ E_ℓ^A(z) + 2 - 2s

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

    K_r^A(x,ax+b) ≤ K_r^A(x,a,b) + o(r) ≤ r + K_r^A(a,b) + o(r).

Hence ^A(x,ax+b) ≤min { 1 + ^A(a,b), 2} and, consequently,

    sup_z∈ℓ^A(z) ≤min {1 + ^A(a,b), 2}.

Now, let S be the projection of E_ℓ onto the x-axis. Then (S) ≥ s, so by the point-to-set principle, for every >0, there exists x_∈ S such that ^A,a,b(x_) ≥ s-. Applying Theorem <ref>, we have
 
    ^A(x_, ax_ + b)   ≥^A(x_| a, b) + min {^A(a,b), ^a, b(x_)}
       ≥^A, a, b(x_) + min {^A(a,b), ^A, a, b(x_)}
       ≥ s- + min {^A(a,b), s-}.

Letting  go to zero gives

    sup_z∈ E_ℓ^A(z)≥min {s + ^A(a,b), 2s}.

The difference in the minima is largest when ^A(a,b) ≥ 1, which gives the desired bound. 



 §.§ The packing dimension bound for 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 <ref> 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.

[<ref>, Restated]
    If E ⊆^2 is a union of 1-Hausdorff-dimensional subsets of lines, then (L_1^ H(E)) =  E. In particular, if E is a union of line segments and L(E) is its lineal extension, then L(E) =  E.


The proof will proceed in four main steps. We need to establish a variant of Theorem <ref> 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 <cit.>. 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 <cit.>.

 
    Suppose x,a,b ∈, B ⊆{0,1}^*, r,t ∈, δ∈^+, and ,η∈^+ satisfy r > log(2|a| + |x| + 5) + 1, t < r, and the following:
    
        
  * K_r,t^B(a,b) ≤ (η + ) (r-t).
        
  * For every (u,v) ∈ B( (a,b), 2^-t) such that ux+v = ax+b,
        
    K_r,t^B(u,v) ≥ (η - )(r-t) + δ (r-s)

        where s = -log |(a,b) - (u,v)| ∈ (t,r].
    
    Then 
    
    K_r,t^B(x, ax+b) ≥ K_r,t^B(x,a,b) - 4/δ (r-t) - K^B() - K^B(η) - 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 <cit.> 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, δ, , and η be as above. We first prove that it suffices to show that

    K_r,t^B(x,u,v | x,a,b) ≤ K_r,t^B( x, ax+b | a,b,x) + K^B(η) + K^B() + O(log r).

whenever (u,v) satisfies K_r,t^B(u,v) ≤ (η + ) (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 | x,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 | a,b,x) ≤ K_r,t^B(x, ax+b) + O(log r).

Applying these two facts to (<ref>) yields

    K_r,t^B(x,u,v) ≤ K_r,t^B(x, ax+b) + K^B(η) + K^B() + O(log r).

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) ≥ K_r,t^B(x,a,b) - 2(r-s) - O(log r).

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

    (η + ) (r-t) ≥ K_r,t^B(u,v) ≥ (η - ) (r-t) + δ (r-s),     so    2/δ(r-t) ≥ (r-s).

This in conjunction with (<ref>) entails

    K_r,t^B(x,u,v) ≥ K_r,t^B(x,a,b) - 4/δ (r-t) - O(log r),

and combining this with (<ref>) gives the desired bound. 

We now direct our attention to proving (<ref>). Let M be an oracle Turing machine that does the following given access to B and inputs (w_1, w_2, w_3) ∈^3, π = π_1 π_2 π_3 π_4 π_5 ∈{0,1}^* such that

    U^B(π_2) = s_1 ∈,    U^B(π_3) = s_2 ∈,    U^B(π_4) = ζ∈,    U^B(π_5) = ι∈.

First, M^B computes U^B(π_1, (w_1, w_2, w_3)) = (q_1, q_2). For every program σ∈{0,1}^* with length less than or equal to (ζ + ι)(s_2 - s_1), it simulates U^B(σ, (w_2, w_3)) = (p_1, p_2) in parallel. If one of the simulations halts with (p_1, p_2) ∈ B( (w_2, w_3), 2^-s_1) 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 π_1, π_2, π_3, π_4, and π_5 testify to

    K_r,t^B(x, ax+b | x,a,b),    K^B(t),    K^B(r),    K^B(η),   and   K^B(),

respectively, and let w_1, w_2, w_3 be the K-minimizing rationals at precision t for x,a,b. Then U^B(π_1, (w_1, w_2, w_3)) gives (x, ax+b) to precision r. By our hypothesis that K_r,t^B(a,b) ≤ (η + ) (r-t), there is a string σ of length at most (η + ) (r-t) such that U^B(σ, (w_2, w_3)) gives (a,b) to precision r. Thus, M(π, (w_1, w_2, w_3)) halts by the same geometric argument as in <cit.>, and the output (q_1, p_1, p_2) lies in B((x,u,v), 2^γ+1-r) for some γ depending only on |x| and |a|. Absorbing γ into the error term gives 

    K_r,t^B(x,u,v | x,a,b) ≤ |π| + c_M + O(log r) 
           ≤ K_r,t^B(x, ax+b | x,a,b) + K^B(t) + K^B(r) + K^B(η) + K^B() + O(log r) 
           ≤ K_r,t^B(x, ax+b | x,a,b) + K^B(η) + K^B() + O(log r).

Finally observe that the string σ which computes (u, v) given access to its first t bits has length, by assumption, no greater than (η + ) (r-t). Hence K_r,t^B(u,v) ≤ (η + ) (r-t), which in conjunction with the above inequality completes the proof. 

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

 
    Let x,a,b ∈. For all (u,v) ∈ B((a,b), 2^-t) such that ux+v = ax+b and for all r ≥ s := -log |(a,b) - (u,v)|,
    
    K_r^A(u,v) ≥ K_s^A(a,b) + K^A_r-s,r(x | a,b) - O(log r).



 
    Let A ⊆{0,1}^*, r∈, z ∈^n, and γ∈^+. There is an oracle D = D(A, n, r, z, γ) satisfying the following:
    
        
  * For every natural number t ≤ r, 
        
    K_t^A,D(z) = min{γ r, K^A_t(z)} + O(log r).

        
  * For every m,t ∈ and y ∈^m, 
        
    K^A,D_t, r(y| z) = K^A_t, r(y| z) + O(log r)   and   K^A,D,z_t(y) = K^A,z_t(y) + O(log r).

        
  * If B ⊆{0,1}^* satisfies K^A,B_r(z) ≥ K_r^A(z) - O(log r)
        
    K^A, B, D_r(z) ≥ K^A,D_r(z)- O(log r).

        
  * For every m,t ∈, u∈^n, and w ∈^m,
        
    K_r^A(u | w)≤ K_r^A,D(u | w) + K_r^A(z)-γ r.

    


Lemma <ref> 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 <ref> 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 <ref>. By the same application of the point-to-set principle used in Proposition <ref>, it suffices to show that for any planar line ℓ with slope-intercept pair (a,b) and for any oracle A ⊆{0,1}^*, if ^A,a,b(x_) ≥ 1-/2 for a collection of x_, then

    lim_→ 0^A(x_, ax_ + b) = sup_z∈ℓ^A(z).

With this aim in mind, let a,b ∈ and A ⊆{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 ≥ 1 by linear interpolation. For ease of notation, we continue to use K_s^A(a,b) to denote this extended function. Let ∈ (0,1) ∩ and assume x∈ is such that ^A,a,b(x) ≥ 1-/2. In the following, we will always assume r is large enough that for s>log r, (1-) s≤ K^A,a,b_s(x) ≤ (1+) s.
    
Lower bound on teal intervals: Call an interval [t,r] of precisions teal if 

    K_s^A(a,b) ≥ K_r^A(a,b) - (r-s)      ∀ s ∈ [t,r].

We want to prove a lower bound on the complexity growth of (x, ax+b) on such intervals by applying Lemma <ref>. If possible,[If the average growth of K_r,t^A(a,b) is smaller than, say, 2√(), just set η=0. We'll get the trivial bound of 0 for the growth on this interval with this choice of , but in practice, we will pick up any actual growth as we pass through with smaller and smaller .] pick η to be an element of the finite set {i/2^m: m = 2 - ⌈log⌉ and  0≤ i ≤ 2^m } such that 

    K_r,t^A(a,b)/r-t - 2 √() < η < K_r,t^A(a,b)/r-t - √().

Using Lemma <ref>, let D=D(A, 2, r, (a,b), K^A_t(a,b) + ⌊η (r-t)⌋). In particular, observe that D lowers the complexity of K_r^A(a,b) by at most 2√()(r-t) + O(log r). Thus, with this choice of η, it is immediate that relative to (A, D) and for sufficiently large r, the first condition of Lemma <ref> is satisfied. 
    
Now we show the second is also satisfied. For (u, v)∈ B_2^-t(a,b), by symmetry of information, Lemma <ref>, and the second property of D, we have

    K_r,t^A,D(u, v)    ≥ K_r^A,D(u,v) - K_t^A,D(u, v) - O(log r) 
       ≥ K_s^A,D(a,b) + K_r-s,r^A,D(x | a,b) - K_t^A,D(u,v) - O(log r) 
       = K_s^A,D(a,b) + K_r-s,r^A,D(x | a,b) - K_t^A,D(a,b) - O(log r) 
       ≥ K_s,t^A,D(a,b) + K_r-s,r^A,D(x | a,b) - O(log r) 
       ≥ K_s,t^A,D(a,b) + K_r-s,r^A(x| a,b) - O(log r) 
       ≥ 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) ≥ 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 √()(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 - √()) and K_s^A,D(a,b) will still be above it on [t, r]. More concretely, K_s^A,D(a,b)≥ K^A,D_r(a,b)-(1 - √()(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)≥ K_r,t^A,D(a,b) - (1 - √())(r-s) - O(log r). Hence, 

    K_r,t^A,D(u, v)≥  K_r,t^A,D(a,b) - (1 - √())(r-s) + K_r-s^A, a, b(x) - O(log r).

Now by our assumption on x, either r-s≤log(r) or  K^A, a, b_r-s(x)≥ (1-) (r-s) holds. In both cases, we have 

    K_r,t^A,D(u,v)    ≥ K_r,t^A,D(a,b) - (1 - √())(r-s) + (1-) (r-s) - O(log r) 
       = K_r,t^A,D(a,b) - ( - √())(r-s) - O(log r) 
       ≥η(r-t) - ( - √())(r-s)  - O(log r) 
       = (η -  + )(r-t) - ( - √())(r-s) - O(log r) 
       ≥ (η -)(r-t) - ( - - √())(r-s) -O(log r) 
       ≥ (η -)(r-t) + √()(r-s) - O(log r).

Thus, for sufficiently large r, we have

    K_r,t^A,D(u, v)≥ (η - ) (r-t) + √()/2(r-s).

This is precisely the second condition of Lemma <ref> with δ=√()/2. Both conditions of Lemma <ref> are satisfied, hence applying it without any additional oracle, we obtain

    K_r,t^A,D(x, ax + b) ≥ K_r,t^A,D(x, a, b) - 8 √() (r-t)  - K() - K(η) - O(log r).

In practice, we will keep the same choice of  throughout a partitioning argument even as r goes to infinity, and we chose η from a fixed set that depends only on . 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) ≥ K_r,t^A,D(x, a, b) - 8 √() (r-t) - O(log r).

Now, applying symmetry of information and the properties of D to K_r,t^A,D(x, a, b), we obtain

    K_r,t^A,D(x, a, b)   ≥ K_r^A,D(x, a, b) - K_t^A,D(x, a, b) - O(log r) 
       ≥ K_r^A,D(x| a, b) + K_r^A,D(a,b) - K_t^A,D(x| a, b) - K_t^A,D(a,b) - O(log r) 
       ≥ 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) 
       ≥ 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) 
       ≥ 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)  ≥ K_r^A, a, b(x) - K_t^A, a, b(x) + K_r,t^A(a,b) - 2 √() (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) ≥ (1-) r - O(log r), which is better than the bound we get below. Otherwise, recall the upper bound K_t^A, a, b(x)≤ (1 + ) 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) ≥ (1 - ) 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-√()) r. Then

    K_r^A, a, b(x)- K_t^A, a, b(x)r-t   ≥(1-)r - (1 +  )tr-t
       ≥(1-)r - (1 +  )(1 - √())rr-(1 - √())r
       =1 - 2√() + 
       ≥ 1 - 2√().

Hence

    K_r,t^A,D(x, a, b)     ≥ (1 - 2√())(r-t) + K_r,t^A(a,b) - 2√() (r-t) - O(log r)
       ≥ (1 - 4√())(r-t) + K_r,t^A(a,b) - O(log r).

Combining this with inequality (<ref>) when r is sufficiently large gives

    K_r,t^A(x, ax + b)≥ (1 - 13√())(r-t) + K_r,t^A(a,b)

or, in the case that t ≥ (1-√()) r,

    K_r,t^A(x, ax + b) ≥ K_r,t^A(a,b) - 13√()(r-t).


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)≥ K_t^A(a,b) + (s-t)     ∀ s ∈ [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)≥ 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.



Let η to be an element of the finite set {i2^m: m = 2 -⌈log⌉ and  0 ≤ i ≤ 2^m } such that 

    1 -2 √() <η < 1 -√().

Using Lemma <ref>, let D=D(A, 2, r, (a,b), K_t^A(a,b) + ⌊η (r-t)⌋). Thus, with this choice of η, it is immediate that relative to (A, D) and for sufficiently large r, the first condition of Lemma <ref> is satisfied. If we defined D̃ = D(A, 2, r, (a,b), K^A_t(a,b) + 1 (r-t)), the teal property would hold relative to (A, D̃). Comparatively, the oracle D further reduces K_r^A(a,b) by at least √()(r-t), hence, as in the previous case, we have K_s,t^A,D(a,b)≥ K_r,t^A,D(a,b) - (1 - √())(r-s) - O(log r). Since we have the (1 - √())-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 <ref>, we have

    K_r,t^A(x, ax + b)    ≥ K_r,t^A,D(x, ax + b)
       ≥ K_r,t^A,D(x, a, b) - 8 √() (r-t) - K() - K(η) - O(log r)
       ≥ K_r,t^A,D(x, a, b) - 8 √() (r-t) -  O(log r).

As in the previous case, 

    K_r,t^A,D(x, a, b)≥ 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√(), and the same bound on the complexity growth of x as in the previous case holds, hence, if t<(1 - √())r, then

    K_r,t^A,D(x, a, b)    ≥ K_r^A, a, b(x)- K_t^A, a, b(x) + (1 - 2√()) (r-t)  - O(log r) 
       ≥ (2 - 4√())(r-t)  - O(log r).

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

    K_r,t^A(x, ax + b)≥ (2 - 13√())(r-t);

or, in the case that t≥(1-√()) r,

    K_r,t^A(x, ax + b)≥ (1 - 13√())(r-t).

    
Partitioning [1,r]: Our aim is now to construct, given A⊆{0,1}^*, a, b∈, and r sufficiently large, a partition 𝒫 of [1, r] having (at least) one of the following forms:

    
  * 𝒫_r consists of one element [1, r], which is teal,
    
  * 𝒫_r consists of one element [1, r], which is yellow, or
    
  * 𝒫_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 <cit.>. 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], …, [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 𝒫_r.

This process halts, since r is a finite number and each step can only increase the length of intervals. The halting condition implies 𝒫_r contains no yellow-yellow, teal-teal, or yellow-teal pairs. Check that every three element partition contains one of these pairs; thus 𝒫_r has at most two elements. But, the only valid pair is teal-yellow. So, 𝒫_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 𝒫_r to be {[1, c_r], [c_r, r]} by the convention that if 𝒫_r is of form one then c_r=r, and if 𝒫_r is of form two then 1=c_r. 

Essentially tight bounds via 𝒫_r: Now, we want to upper bound K_r^A(x, ax + b) for any given x∈. 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.[It is not true that K_r,t^A(x, ax+b)≤ 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 

    ^A(x, a x + b) ≥sup_z∈ℓ^A(z) - .

Clearly (x, ax + b)∈^2, so for sufficiently large r we have

    K_r,t^A(x, ax + b)≤ 2(r - t) + o(r) ≤ (2+ )(r - t).

At the same time, also for sufficiently large r,

    K_r^A(x, ax+b)≤ K_r^A(x, a, b) + o(r) ≤ K_r^A(x, a, b) +  r.

Now, assume r is large enough that the above bounds hold for any s>log r. We use the partition 𝒫_r, applying (<ref>) on the interval [1, c_r] and (<ref>) on [c_r, r]. This gives

    K_r^A(x, ax+b)   ≤ K_1,c_r^A(x, ax+b) + K_c_r, r^A(x, ax+b) + O(log r) 
       ≤ K_c_r^A(x, a, b) +  c_r + 2(r - c_r) +  (r - c_r) + O(log r) 
       ≤ K_c_r^A(x, a, b) + 2(r - c_r) + 2  r 
       ≤ c_r + K_c_r^A(a,b) + 2(r - c_r) + 3  r.

Now, we lower bound the complexity of x_, where x_ satisfies the hypothesis of the yellow and teal results, namely that for sufficiently large r, s>log r implies (1-) s≤ K^A, a, b_s(x)≤ (1+) s. We use the fact that 𝒫_r (and hence c_r) only depended on A, a, b, and r, and apply the yellow and teal interval lower bounds. 

    K_r^A(x_, ax_ + b)   ≥ K^A_c_r(x_, ax_ + b) +  K^A_r, c_r(x_, ax_ + b) - O(log r)
       ≥ (1 - 13√())c_r + K_c_r^A(a,b) + (2 - 13√())(r-c_r)  + 2√()r - O(log r)
       ≥ c_r + K_c_r^A(a,b) + 2(r-c_r)  - 28√()r - O(log r)
       ≥ c_r + K_c_r^A(a,b) + 2(r-c_r)  - 29√()r,

where the extra 2√() 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_, ax_ + b) ≤ 32√()r.

Hence, 

    ^A(x, ax+b) - ^A(x_, ax_ + b) ≤ 32√().

Finally, by our choice of x, this gives

    ^A(x_, ax_ + b) ≥sup_z∈ℓ^A(z) - 33√().

We could pick  to be arbitrarily small, so this completes the proof. 

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

[<ref>, Restated]
Let E ⊆^2 and let D ⊆^n-1 be the set of directions of lines intersecting E in a set of Hausdorff dimension 1. If D ≠∅, then

    D + 1 ≤ E.



Proof. Let Λ = {ℓ∈𝒜(2,1) : (E ∩ℓ) = 1 }, let F_ℓ denote the orthogonal projection of E ∩ℓ 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 Λ, we see by the point-to-set principle that the desired inequality (<ref>) is equivalent to

    sup_a ∈ D^A(a) + 1 ≤sup_ℓ∈Λsup_x ∈ F_ℓ^A(x,ax+b).

So it suffices to show that for every a, b∈, A⊆, and S⊆ of Hausdorff dimension 1, 

    ^A(a)+1≤sup_x∈ S^A(x, ax+b).

By the point-to-set principle, this follows if for any x_∈ such that ^A,a,b(x_) > 1 - /2,

    ^A(a) + 1 ≤lim_→ 0^A(x_, ax_ + b).

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

    K_r^A(x_, a x_ +b) ≥ c_r + K_c_r^A(a, b) + 2(r - c_r) - 29 √() r.

Assuming r is sufficiently large, this implies

    K_r^A(x_, a x_ +b)    ≥ c_r + K_c_r^A(a, b) + 2(r - c_r) - 29 √() r 
       ≥ c_r + K_c_r^A(a) + 2(r - c_r) - 30 √() r 
       ≥ c_r + K_c_r^A(a) + (r - c_r) + K_r, c_r^A(a) - 31 √() r 
       ≥ c_r + K_r^A(a) + (r - c_r) - 32 √() r 
       = r + K_r^A(a) - 32 √() r.

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




 §.§ Packing extensions


In comparison with 1-Hausdorff extensions, which do not increase either the Hausdorff or packing dimension of E⊆^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. 

[L_1^ P(E) can increase the packing dimension] Let r_i be a rapidly increasing sequence. Define 

    X    = { x = 0.x_1x_2x_3 …∈ [0,1] : j ∈ [r_2i-1, r_2i)  for some  i ∈⇒ x_j = 0 }  and
    
        S    = {a = 0.a_1a_2a_3 …∈ [0,1] : j ∈ [r_2i, r_2i+1)  for some  i ∈⇒ a_j = 0 }.

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

    E = { (x,ax) ∈^2 : x ∈ X,   a ∈ S }.

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

    K_r^A(x, ax)    ≤ K_r(x,ax) + O(log r) 
       ≤ K_r(x,a) + O(log r) 
       ≤ K_r(x+a) + O(log r) 
       ≤ 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 E = 1. 

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

    { (x,ax) ∈^2: x ∈,   a ∈ S }⊆ L_1^ P(E).

Let A be a packing oracle for L_1^ P(E). Let a ∈ S be such that, removing the intervals [r_2i, r_2i+1-1] from its binary expansion and letting ã denote the remaining string, ã is random relative to A. Finally, let x be random relative to (a, A). Let > 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 , hence

    K^A_r_2i+1(x, ax)   ≥ K^A_r_2i+1, r_2i(x, ax) - O(log r_2i+1)
       ≥ K^A, D_r_2i+1, r_2i(x, ax) - O(log r_2i+1)
       ≥ K^A_r_2i+1, r_2i(x, a) -  (r_2i+1- r_2i) - O(log r_2i+1)
       ≥ K^A_r_2i+1, r_2i(x, a) -  r_2i+1- o(r_2i+1)
       ≥ K^A_r_2i+1(x, a) -  r_2i+1- o(r_2i+1)
       ≥ K^A_r_2i+1(x) + K^A_r_2i+1(a) -  r_2i+1- o(r_2i+1)
       ≥ r_2i+1 + r_2i+1 -  r_2i+1- o(r_2i+1)
       ≥ 2 r_2i+1 - 2  r_2i+1.

Taking the limit superior and letting  go to zero shows that (L_1^ 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 ⊆^2 we could ask for upper bounds on

    _H(L_s^ P(E)) - _H(E)     and    (L_s^ P(E)) - (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.[We 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 <cit.>, 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 <cit.>, <cit.> and <cit.>.



§ 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 ∈. To prove Proposition <ref>, 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.

 
    For all y ∈^n, A ⊆{0,1}^*, and > 0, there exists a dense set of points x ∈ such that, for all sufficiently large r (depending on x), 
    
    K_r^A(y | x) ≤max{ K_r^A(y) - (1 - ) r,  r }.



The idea of the proof is simple; build the point x∈ 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 < δ < 1, we build a point x_δ∈ as follows. For each i ∈, let [r_i,r_i+1] be an interval of length ⌈(1 + δ)^i⌉, where r_0 = 1. Let σ_i denote a string testifying to K_r_i,r_i+1^A(y) and let x ∈ [0,1] be the real number with binary expansion 0.σ_0 σ_1 ….

Let π = π_1 π_2 π_3, where U^A(π_2) is a finite list of positive integer lengths l_0, …, l_m. Given a side information string τ, define an oracle Turing machine M that computes M^A(π|τ) as follows. The machine M first calculates U^A(τ) = q ∈ and determines the successive strings q_0, …, q_j of lengths l_0, …, 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(π|τ) = U^A(π_1, p_j) as the output. Let c_M be a constant for this machine.

Now let r ∈ 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) ≤ r and (2) the smallest precision r_i such that r_i ≥ r. (This r can be assumed to be large enough that K_r_1^A(y) ≤ r.) If there is no largest such r_i in (1), we consider this term to be ∞ and default to the r_i given by (2). As {r_i}_i∈ is an increasing sequence tending to infinity, such an r_i clearly exists. 

Let π_1 testify to K_r,t^A(y), let π_2 testify to K^A(K^A_r_0(y), K^A_r_1, r_0(y), …, K^A_r_k, r_k-1(y) ), and let τ testify to K_r^A(x_δ). 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

    K_r^A(y | x_δ)    ≤ K_r,t^A(y) + K^A(K^A_r_0(y), K_r_1, r_0^A(y), …, K_r_k, r_k-1^A(y) ) + c_M 
       ≤ 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 ≤ O(log r) by the definition of t, 

    K_r^A(y | x_δ) ≤ 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) ≤ O(log r) and for sufficiently large r

    K_r^A(y | x_δ)≤  O((log r)^2) < 3n δ r.

For the case that t<r, let s be the smallest integer precision such that K_s^A(y) ≥ r. Then t ≤ s, so 

    K_r^A(y | x_δ)    ≤ K_r,s^A(y) + K_s,t^A(y) + O((log r)^2) 
       ≤ K_r^A(y) - K_s^A(y) + K_s,t^A(y)  + O((log r)^2) 
       ≤ K_r^A(y) - r + K_s,t^A(y)  + O((log r)^2) 
       ≤ K_r^A(y) - r + n(s-t) + O((log r)^2)

by the choice of t and s, s < r_k+1. Hence, 

    K_r^A(y | x_δ)    ≤ K_r^A(y) - r + n(r_k+1 - r_k)  + O((log r)^2) 
       ≤ K_r^A(y) - r + 2n δ r_k+1 + O((log r)^2) 
       ≤ K_r^A(y) - r + 2n δ r + O((log r)^2).

So, for all r sufficiently large that n δ r dominates the O((log r)^2) term, we have

    K_r^A(y | x_δ) ≤ K_r^A(y) - r + 3n δ r.

Picking δ < 3n and combining (<ref>) and (<ref>) gives the existence of one x satisfying (<ref>). Appending the digits of x to any dyadic number (which are dense) gives the same property for sufficiently large r, completing the proof. 

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

[<ref>, Restated]
    If E ⊆^n is a union of line segments, then
    
    L(E) ≤ E +  E - 1   and  L(E) ≤ 2  E - 1.



Proof. Let A ⊆{0,1}^* be both a Hausdorff oracle and a packing oracle for E and let > 0. Given a point z ∈^n, we construct a machine M that operates as follows. Take any y ∈^n such that [ 2^c y_1 ] = [ 2^c z_1 ] for some c ∈, where [  ·  ] denotes the fractional part of a real number; that is, the first coordinates of y and z agree from the cth binary digit onwards. Next, let x ∈^n with x_1 ≠ y_1 and let

    t = z_1 - x_1/y_1 - x_1.

We form a program π = π_1 π_2 π_3 π_4, where U^A(π_1) = p is a precision r+s approximation of x, U^A(π_2 |π_1) = q is a precision r+s approximation of y, and U^A(π_3 |π_1, π_2, π_4) = u is a precision r+s approximation of t, where U^A(π_4) = ⌈ 2^c z_1 ⌉ and s ∈ is large enough that p + u(q-p) ∈ 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(π) computes p + u(q-p) by computing p, q, and u as just described.

Now let z ∈ℓ_I ⊆ F and let y ∈ I be a point such that, up to a permutation of the axes, [ 2^c y_1 ] = [ 2^c z_1 ] for some c ∈. Next, let x ∈ I be a point with x_1 ≠ y_1 such that x_1 assists in the computation of y as in Lemma <ref>, i.e., such that

    K_r^A(y | x_1) ≤max{ K_r^A(y) - (1 - ) r,  r }

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 π_1, π_2, π_3, and π_4 witness K_r+s^A(x), K_r+s^A(y | x), K_r+s^A( t | x,y, ⌈ 2^c z_1 ⌉), and K^A( ⌈ 2^c z_1 ⌉), respectively. Since t is computable from x, y, and ⌈ 2^c z_1 ⌉, we have

    K_r+s^A( t | x,y, ⌈ 2^c z_1 ⌉) = 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 ∈:

    K_r^A(z)    ≤ |π_1 π_2 π_3 π_4| + c_M 
       ≤ K_r+s^A(x) + K_r+s^A(y | x) + K_r+s^A( t | x,y, ⌈ 2^c z_1 ⌉) + K^A( ⌈ 2^c z_1 ⌉) + c_M 
       ≤ K_r+s^A(x) + K_r+s^A(y | x) + o(r) 
       ≤ K_r^A(x) + K_r^A(y | x) + 2sn + o(r) 
       ≤ K_r^A(x) + max{ K_r^A(y) - (1 - ) r,  r } + o(r).

Dividing through by r and taking the limit inferior as r →∞ gives

    ^A(z)    ≤^A(x) + max{^A(y) - (1 - ), }
       ≤ E +  E - (1 - ),

where we have chosen the first alternative in the maximum because E ≥ 1. Taking the supremum over all z ∈ F gives the first inequality in (<ref>) modulo an ϵ, which we let decrease to 0. To obtain the second inequality in (<ref>), we simply take the limit superior instead of the limit inferior. 

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

    K +  K ≥ n+1

improves on Corollary <ref> 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 <ref> to encode the set D ⊆^n-1 of directions of the segments in ℐ and then computing z using x, x-y|x-y| and t, one can modify the conclusions of Proposition <ref> to

    L(E) ≤min{ E +  D,  D +  E }  and
    L(E) ≤ E +  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, x-y|x-y| and t, although this renders Lemma <ref> 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 (<ref>). 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 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 <ref>).

 
    If E ⊆^n, then
    
    L_0(E) ≤ E +  E + 1   and   L_0(E) ≤ 2  E + 1.



Proof. The proof is the same in spirit as that of Proposition <ref>, but forgoing the encodings greatly simplifies the matter. Let z ∈ L_0(E), so that z = x + ty for some x,y ∈ E and some t ∈. Taking the limit inferior of both sides of

    K_r^A(z) ≤ K_r^A(x) + K_r^A(y) + K_r^A(t) + o(r) ≤ K_r^A(x) + K_r^A(y) + r + o(r)

gives the first inequality and taking the limit superior gives the second. 

[Sharpness of Proposition <ref>] 
    The inequalities in (<ref>) are sharp in ^2. Let C_α⊂ [0,1] be the middle-α Cantor set, α∈( 12, 1 ), so that
    
    s :=  C_α =  C_α = log 2/log12 (1 - 2α)∈( 0, 12).

    Then ℋ^2s(C_α× C_α) > 0, so by Marstrand's projection theorem, (tC_α - C_α) = 2s for ℒ^1-a.e. t ∈. In fact, by Proposition 1.3 of <cit.>, it is also the case that (tC_α - C_α) = 2s for a.e. t ∈, so we fix a t satisfying both these equations and let
    
    E := ({0}× C_α) ∪ ({1}× t C_α).

    Then the set of slopes of lines in L_0(E) is simply (tC_α - C_α) ∪{∞}, and in particular the set D ⊂^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 <ref> and Theorem <ref> above),
    
    L_0(E)    ≥ L_0(E) ≥ D + 1 = 2s + 1 
       =  E +  E + 1 = 2  E + 1.

    Hence, both inequalities in (<ref>) hold with equality. Taking an intersection of the exceptional sets in <cit.> Proposition 1.3 shows that our argument similarly works when α = 12 (although tC_α - C_α may have zero 1-dimensional packing measure), yielding the extreme case E =  E = 12. In the other extreme, any two-point set poses a sharp example for E =  E = 0.


Interestingly, E cannot be replaced with E in the first inequality of Proposition <ref>. 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.

[Failure of L_0(E) ≤ 2  E + 1] Through a simple argument (in the spirit of <cit.> Example 7.8, <cit.>, or the construction in <cit.> Theorem 1.4) we observe that the analogous bound for the Hausdorff dimension of two-point extensions severely fails. Let E = { x ∈^n: (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 <cit.> Theorem 3.3.1). Its two-point extension is

    L_0(E)    = { x + t(y-x) ∈^n : (x) = 0,  (y) = 0,   t ∈}
       ⊇{ 2y-x ∈^n: (x) = 0,  (y) = 0 },

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

    L_0(E) ⊇{ x+y ∈^n : (x) = 0,  (y) = 0 }.

Now observe that any z ∈^n can be written as the sum of two Hausdorff dimension-0 points. We illustrate for z ∈ [0,1] with binary representation 0.z_1z_2z_3 …. Let x = 0.x_1x_2x_3 …, where x_i = z_i when there exists even j ∈ such that j! ≤ 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 ^n. Consequently, L_0(E) = ^n, so

    L_0(E) = n     but     E = 0.



This also poses a counterexample to any sort of “reverse continuum Beck's theorem"; see <cit.> 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.

plain


