Effective dimension of points on a line

The purpose of this post is to describe the strategy Neil Lutz and I used to prove lower bounds on the effective dimension of points on a line in $\mathbb{R}^2$ . This strategy seems quite general, and has been the basis for a variety of results (e.g. https://arxiv.org/pdf/2102.00134.pdf, https://arxiv.org/pdf/1711.02124.pdf and https://arxiv.org/pdf/1701.04108.pdf).

In this post I will focus on the effective dimension of points. However, one of primary motivations of this work is that lower bounds on effective dimension can be converted into lower bounds on the (classical) Hausdorff dimension of sets. For example, Neil and I used the lower bounds on the effective dimension of points on a line to give better bounds on certain classes of Furstenberg sets. In a future post I might describe how to convert effective theorems into classical theorems using the point-to-set principle of Jack and Neil Lutz.

For this post, we will restrict ourselves to proving the following theorem.

Theorem: Let (a, b) be a slope-intercept pair of effective dimension d. Let x be a point whose effective dimension, relative to (a, b), is s >= min{d, 1}. Then

$dim(x, ax + b) \geq s + \min\{d, 1\}$ .

Lower bounds at fixed precisions

In this section, I will explain how to prove lower bounds of the complexity of a point on a line at fixed precisions. In the next section we’ll see how to use these ideas to give lower bounds for the effective dimension of a point on a line.

Let (a,b) be a slope-intercept pair with

$\text{dim}(a,b) = d$ .

We will make the further assumption that d < 1 (we will see how to remove this assumption in the next section). Let x be a point such that

$\text{dim}^{a,b}(x) = s > d$ .

Let r be a sufficiently large natural number (precision) such that

$K_r(a,b) = dr - o(r)$ .

Note that infinitely such r exist by the definition of effective dimension. Our goal is to prove that

$K_r(x, ax + b) \geq (s + d)r - o(r)\ \ \ \ (1)$ .

We in fact prove the stronger statement, that

$K_r(x, ax + b) \geq K_r(x, a, b)- o(r)\ \ \ \ (2)$ .

Remark: Using our assumption about the dimension of x relative to (a,b), it is clear that (2) implies (1). We should also note that, modulo the sublinear additive error, this lower bound is tight. Specifically,

$K_r(x, ax+b) \leq K_r(x,a,b) = (s+d)r - o(r)$ .

Therefore, we will show the slightly unintuitive fact that the point (x, ax + b) contains all of the information of the line (a,b) and the point x.

To prove (2) it suffices to establish the following lemma.

Lemma 1: Let (x, a, b) and precision r satisfy the previous properties. Suppose (u, v) is a line such that $K_r(u, v) \leq dr + o(r)$ and

$\vert ux + v - (ax + b) \vert < 2^{-r + O(1)} \ \ \ \ (3)$

Then

$\|(a,b) - (u,v)\| < 2^{-r + o(r)} \ \ \ \ (4)$ .

Remark: Assuming Lemma 1, we can quickly deduce (2) as desired. Given (a program producing) (x, ax + b) to precision r, search for the first line (u, v) satisfying (3) and

$K_r(u, v) \leq dr + o(r)$ .

Theorem 1 shows that any such line is very close to (a, b). Therefore, with an additional sublinear number of bits, we can produce (a, b) from (u, v), and we have (2) as desired.

Thus, it suffices to prove Lemma 1. One of the standard techniques of Kolmogorov complexity is the incompressibility argument. The idea is to show that some property P holds for a random string w by proving that if it didn’t, we could compress w (a contradiction, since w is random). The proof of Lemma 1 follows this pattern. Essentially we are arguing that if there were many lines (u, v) intersecting (x, ax + b), then x wouldn’t be random relative to (a,b).

To use this strategy, we rely on the simple geometric fact that two non-parallel lines intersect at exactly one point. Therefore, intuitively, to compute x, with oracle access to (a,b), it suffices to give any line (u, v) which intersects (x, ax + b). As x was chosen to have high complexity relative to (a, b), this implies that any such line (u, v) must have high complexity as well. Our assumption that s > d implies that $K_r(u, v) >> K_r(a,b)$ . Therefore, (a, b) is the unique line of low complexity intersecting (x, ax + b).

There is a major issue in formalizing the previous discussion. We aren’t working with infinite objects, but with Euclidean points up to finite precision. Thus we aren’t dealing with the intersection of two lines, but with the intersection of two $2^{-r}$ neighborhoods of lines (i.e., two tubes). Unlike lines, the intersection of two tubes has area. The size of this intersection depends on how orthogonal the two lines are. The key fact that allows us to continue with our idea is that the area depends linearly on the distance between the two lines. Formally,

$A \leq 2^{-r + t + O(1)}\ \ \ \ (5)$ ,

where A is the area of intersection of the $2^{-r}$-tubes around lines (a, b) and (u, v) and

$t = -\log\|(a,b) - (u,v)\|$ .

It is not difficult to translate (5) into the language of Kolmogorov complexity, which yields our next lemma.

Lemma 2: Let (a, b) and (u, v) be two lines and x be a point such that

$\vert ux + v - (ax + v) \vert < 2^{-r + O(1)}\ \ \ \ (3)$ .

Then

$K^{a,b}_{r-t -O(1)}(x) \leq K^{a,b}_r(u,v)$ ,

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

We are now in a position to prove Lemma 1, and thereby complete the proof of the lower bound (2).

Proof of Lemma 1: Let (u, v) satisfy (3) and $K_r(u,v) \leq dr + o(r)$ . By our assumption on the dimension of x relative to (a, b),

$K^{a,b}_{r - t-O(1)}(x) \geq s(r - t) - O(1)$ .

Therefore, by Lemma 2,

$s(r - t) - O(1) \leq K^{a,b}_r(u,v)$ .

To bound the RHS, we note that the oracle (a, b) gives complete information about (u, v) up to precision t. Therefore,

$K^{a,b}_r(u,v) \leq K_{r,t}(u, v) \vert u, v) = K_r(u,v) - K_t(u,v)$ .

Since any $2^{-t}$ approximation of (u,v) is also an approximation of (a,b), we have

$K^{a,b}_r(u,v) \leq K_r(u,v) - K_t(a,b)$ .

Recall that we assumed that dim(a,b) = d. Using this and our assumption about the complexity of (u, v) we conclude that

$s(r-t) - O(1) \leq dr + o(r) - (dt - o(t))$ .

Since s < d, this implies that

$r - t < o(r)$ ,

and the conclusion follows.

Lower bound for effective dimension

In this section we use the work of the previous section to prove the corresponding lower bound for the effective dimension of (x, ax + b). In order to do this, we need to prove a lower bound for the complexity of our point at every precision. In the previous section, we made the assumption that the complexity of (a, b) was essentially minimized at precision r. Obviously, at an arbitrary precision this property won’t necessarily hold.

The final technique needed is to, at an arbitrary precision r, artificially lower the complexity of (a, b) at r so that the minimization property holds (and so we can apply the results of the previous section).

Let r be any sufficiently large precision. By the “continuity” of $K_r(a,b)$ , there is a precision m such that

$K_m(a, b) = dr + o(r)$ .

Let $\pi$ be the time-minimizing program testifying to

$K((a,b) \upharpoonright r \, \mid \, (a,b) \upharpoonright m)\ \ \ \ (6)$ .

That is, the universal machine, given the first m bits of (a,b) and $\pi$ , outputs the first r bits of (a,b). Moreover, $\pi$ is the first program with this property in the standard dovetailing enumeration over all programs of length (6).

At this point there are two equivalent ways to tie this into the work of the previous section. I will follow the notation Neil and I used in the paper (instead of oracles, one can condition everything on $\pi$ , which is equivalent) . Let A be the oracle encoding the program $\pi$ . Then

$K^A_r(a,b) = K_m(a,b) + o(r) = dr + o(r)$ .

Since there is (almost) no information in A that isn’t in (a,b),

$K^{A, a, b}_t(x) = K^{a,b}_t(x) - o(r)$ ,

for all precisions t. Therefore, relative to this oracle A, we can use the results of the previous section to conclude that

$K^A_r(x, a, b) \leq K^A_r(x, ax + b) + o(r)$ .

The LHS is

$K^A_r(a, b) + K^A_r(x \mid a, b) = dr + sr - o(r)$ ,

We can therefore conclude that, for all sufficiently large r,

$(d + s)r - o(r) \leq K^A_r(x, ax + b)$ ,

and the proof is complete.

Remark: When the dimension of (a, b) is greater than 1, we can lower the complexity of (a, b) to a rational arbitrarily close to 1.

To finish the post, I wanted to quickly recap the strategy Neil and I introduced.

At precision r, decrease the complexity of (a, b) to roughly dim(a,b) r using conditional complexity.
The intersection lemma (Lemma 2 of this post), gives a lower bound on the complexity of any other line intersecting (x, ax + b).
If x, relative to (a,b) has dimension at least min{1, dim(a,b)}, this lower bound implies the only lines intersecting (x, ax + b) are very close to (a,b).
Therefore, given (x, ax + b), we can compute (x, a, b) with a sublinear amount of extra information.