Logic – some compact thoughts

A rather annoying fact about Hausdorff dimension is that, if one has a family $X_t$ of sets parametrized by $t \in T$ , then it is typically not true, or at least not easy to show, that the Hausdorff dimension of $\bigcup_{t \in T} X_t$ is $\dim T + \sup_{t \in T} \dim X_t$ , as one would expect from, say, algebraic geometry. For example, if $X, Y$ are Borel sets, then it is not necessarily true that $\dim(X + Y) = \dim X + \dim Y$ . When one goes a bit beyond the Borel sets (and does not assume the existence of large cardinals), things get much more ridiculous, and in fact there can exist a coanalytic set of full dimension whose closed subsets are all countable.

I ran into this issue recently, when I needed the following theorem to be true:

Theorem. Let $\|\cdot\|$ be an asymmetric norm on $\mathbf R^n$ , let $V$ be a subset of the unit sphere of the dual norm of $\|\cdot\|$ , and let $S = \bigcup_{v \in V} v^*$ .
Then

$\displaystyle \dim S \leq \dim V + \sup_{v \in V} \dim(v^*)$ .

Here, $v^* := \{x \in \mathbf R^n: \langle v, x\rangle = \|x\| = 1\}$ is the dual flat of $v$ .

The techniques used to prove this theorem have nothing to do with the problem I am working on, and I think it is an instructive example of how they are used; so I record the theorem here, rather than in the paper I am writing.

Specifically, the theorem shall be proven using algorithmic randomness, following the framework of Algorithmic information, plane Kakeya, and conditional dimension. We recall this framework here.

Let $\Sigma$ be the set of all finite binary strings. If $\sigma, \sigma' \in \Sigma$ , we write $\sigma \frown \sigma'$ for their concatenation. We write $|\sigma|$ for the length of $\sigma$ .

A set $\Gamma \subset \Sigma$ is prefix-free if for every $\sigma, \sigma' \in \Gamma$ and $\tau \in \Sigma$ , if $\sigma \frown \tau = \sigma'$ , then $|\tau| = 0$ . By standard coding techniques one can represent points in $\mathbf Q^n$ or $\mathbf N$ as finite binary strings, in such a way that the set of binary strings which are used to code points in $\mathbf Q^n$ or $\mathbf N$ is prefix-free; we shall exploit this fact without comment.

A function $f: \mathrm{dom}(f) \to \Sigma$ is partial computable if $\mathrm{dom}(f) \subseteq \Sigma$ and there exists a Turing machine $\Phi$ such that for every binary string $\sigma$ , $\sigma \in \mathrm{dom}(f)$ iff $\Phi$ halts with input $\sigma$ , and if $\sigma \in \mathrm{dom}(f)$ , then $\Phi$ prints $f(\sigma)$ . A partial computable function $f$ is prefix-free if $\mathrm{dom}(f)$ is prefix-free. A prefix-free function $U$ is universal if for every prefix-free partial computable function $f$ , there exists $\rho_f \in \Sigma$ such that $\{\rho_f: f \text{ is a prefix-free function}\}$ is prefix-free, and for every $\sigma \in \mathrm{dom}(f)$ , $U(\rho_f \frown \sigma) = f(\sigma)$ . Thus $U$ is playing the role of a “compiler”. There exists a universal prefix-free function $U$ ; we fix one, once and for all. If $f$ is prefix-free and $\rho_f$ is chosen so that $f(\sigma) = U(\rho_f \frown \sigma)$ , then $\rho_f$ is a program which computes $f$ .

The Kolmogorov complexity of $\sigma \in \Sigma$ is

$\displaystyle K(\sigma) := \min \{|\rho|: U(\rho) = \sigma\}$ .

Since we can code rational points, or integers, as binary strings, it makes sense to take their Kolmogorov complexities. For any $j \in \mathbf N$ , the program which simply decodes the binary expansion of $j$ provides an upper bound on $K(j)$ , namely $K(j) \leq \log j + O(1)$ (where logarithms are base- $2$ ). Given $x \in \mathbf R^n$ and $r \geq 0$ , the Kolmogorov complexity of $x$ to $r$ bits is

$\displaystyle K_r(x) := \inf \{K(q): q \in \mathbf Q^n \cap B(x, 2^{-r})\}$ .

The effective Hausdorff dimension of $x$ is

$\displaystyle \dim(x) := \liminf_{r \to \infty} \frac{K_r(x)}{r}$ .

It can be shown that $\dim(x)$ does not depend on the choice of the universal function $U$ .

The above concepts can be relativized. Let $A \subseteq \Sigma$ , and in the above definitions, replace “Turing machine” with “Turing machine with oracle $A$ .” Let $K_r^A(x)$ and $\dim^A(x)$ denote the Kolmogorov complexity and effective Hausdorff dimension of $x \in \mathbf R^n$ measured with oracle $A$ .

The key theorem, which interprets Hausdorff dimension as a measure of indescribability, and is proven in Plane Kakeya… is,

Point-to-set principle. For every set $E \subseteq \mathbf R^n$ ,

$\displaystyle \dim E = \min_{A \subseteq \Sigma} \sup_{x \in E} \dim^A(x)$ .

In particular, for each set $E \subseteq \mathbf R^n$ , there exists an oracle $A_E \subseteq \Sigma$ such that if $A \geq_T A_E$ then $\dim E = \sup_{x \in E} \dim^A(x)$ . The oracle $A_E$ is called a Hausdorff oracle for $E$ .

Lemma 1. Let $X$ be a compact convex subset of $\mathbf R^n$ , and assume $s := \dim X \leq n - 1$ .
There exists $C \geq 1$ such that for every $h > 0$ , with $X_h := \{x \in \mathbf R^n: \mathrm{dist}(x, X) < h\}$ ,

$\displaystyle C^{-1} h^{n - s} \leq \mathrm{vol}(X_h) \leq Ch^{n - s}$ .

To prove the lemma, observe that since $s \leq n - 1$ , $X$ has empty interior. Since $X$ is convex, it follows that $X$ is contained in an $n - 1$ -plane $P$ . If $s \leq n - 2$ , then it is enough to prove the theorem with $\mathbf R^n$ replaced by $P$ , so we may use induction on $n - s$ to reduce to the case that $s = n - 1$ .

If $s = n - 1$ , then $X$ has nonempty interior in $P$ , so $X$ contains a ball $Y$ in $P$ , and (viewing $Y$ as a subset of $\mathbf R^n$ ) $Y_h$ is a cylinder of length $h$ , so $\mathrm{vol}(X_h) \geq \mathrm{vol}(Y_h) \gtrsim h$ . Conversely, since $X$ is compact, $X$ is contained in a ball $Z$ in $P$ , and the converse inequality holds, proving the lemma.

Lemma 2. Let $\|\cdot\|$ be an asymmetric norm on $\mathbf R^n$ . Then there exists $C > 0$ such that for each point $v$ on the unit sphere of the dual norm of $\|\cdot\|$ , and each $x \in \mathbf R^n$ ,

$\displaystyle \mathrm{dist}(x, v^*) \leq C(|\|x\| - 1| + |\langle v, x\rangle - 1|)$ .

This is just some linear algebra, and comparability of norms, so I’ll leave out the proof of this lemma.

Now to prove the main theorem. By the point-to-set principle, we may choose a Hausdorff oracle $A_V$ for $V$ . By rounding off $\|x\|$ to a suitable rational number for each $x \in \mathbf R^n$ , we may find a function $\psi: \mathbf Q^n \times \mathbf N \to \mathbf Q_+$ such that for each $q \in \mathbf Q^n$ and $r \geq 0$ , $|\psi(q, r) - \|q\|| < 2^{-r}$ . Then there is an oracle $A_\psi$ which computes $\psi$ ; let $A := A_\psi \oplus A_V$ .

For each $v \in V$ and $r \in \mathbf N$ , choose $v_r \in 2^{-r} \mathbf Z^n$ such that $|v - v_r| < \sqrt n/2^r$ and $K(v_r) \leq K_r(v) + O(1)$ . By comparability of norms, there exists $R \in \mathbf N$ such that for every $v, r, q$ , if $|\langle v_r, q\rangle - 1| + |\psi(q, r) - 1| \leq 1$ , then $q \in [-R, R]^n$ . So $2^{-r} \mathbf Z^n \cap [-R, R]^n$ is a finite set and therefore the function $f_{v, r}: \mathbf N \to 2^{-r} \mathbf Z^n$ which returns the lexicographically $j$ th $q \in 2^{-r} \mathbf Z^n$ such that $|\langle v_r, q\rangle - 1| + |\psi(q, r) - 1| < 2^{-(r-3)}$ , and returns $0$ if no such point exists, is well-defined.

Fix $v \in V$ and $r \in \mathbf N$ , and define the following algorithm which takes input $j$ , and uses $A$ as an oracle:

Let $i := 1$ .
For each in lexicographic order:
1. If $|\langle v_r, q\rangle - 1| + |\psi(q, r) - 1| < 2^{-(r-3)}$ , increment $i$ .
2. If $i = j$ , return $q$ .
Return $0$ .

Thus this algorithm computes $f_{v, r}$ , so for any $j$ such that $f_{v, r}(j) \neq 0$ ,

$\displaystyle K^A(f_{v, r}(j)) \leq K^A(v_r) + K(r) + K(j) + O(1)$ .

For each $x \in v^*$ , choose $x_r \in 2^{-r} \mathbf Z^n$ such that $|x - x_r| < \sqrt n/2^r$ . Then, if $r \geq \log n/2$ , one can check that

$\displaystyle |\langle v_r, x_r\rangle - 1| + |\psi(x_r, r) - 1| < 2^{-(r - 3)}$ ,

which establishes that there exists $j \in \mathbf N$ such that $x_r = f_{v, r}(j)$ . In particular, with $r_0 := \lceil \log n/2\rceil$ ,

$\displaystyle K_{r - r_0}^A(x) \leq K_r^A(v) + \log j + O(\log r)$ .

It remains to estimate $j$ , but by Lemma 2, there exists $r_1 \in \mathbf N$ which only depends on $\|\cdot\|$ , such that for every $j$ such that $f_{v, r}(j) \neq 0$ , $\mathrm{dist}(f_{v, r}(j), v^*) \leq 2^{-(r - r_1)}$ . Let $U := \{\mathrm{dist}(\cdot, v^*) < 2^{-(r - r_1 - 1)}\}$ , $j_0$ the largest $j$ such that $f_{v, r}(j) \neq 0$ , and $s := \dim(v^*)$ , so by Lemma 1, $\mathrm{vol}(U) \lesssim 2^{-r(n - s)}$ ; for any $j \leq j_0$ , $B(f_{v, r}(j), 2^{-r}) \subseteq U$ ; and for any $y \in U$ , $\mathrm{card} \{j \in J: |f_{v, r}(j) - y| < 2^{-r}\} \leq 2^n$ . Combining these facts, we see that