Lines missing every random point 1

Abstract

We prove that there is, in every direction in Euclidean space, a line that misses every computably random point. We also prove that there exist, in every direction in Euclidean space, arbitrarily long line segments missing every double exponential time random point.

Keywords

Randomness algorithmic geometric measure theory computable analysis

1. Introduction

One objective of the theory of computing is to investigate the fine-scale geometry of algorithmic information in Euclidean space. Recent work along these lines has included algorithmic classifications of points lying on computable curves and arcs [6, 14, 23, 26, 32] and in more exotic sets [8, 15, 19, 22].

This paper concerns a simple, fundamental question: Can the direction of a line in Euclidean space force the line to meet at least one random point? That is, can the set of Martin–Löf random points, which is everywhere dense and contains almost every point in Euclidean space, be avoided by lines in every direction? For example, it is reasonable to conjecture that every line of random slope in $R^{2}$ contains a random point. We show here that this conjecture is false, and in fact that – regardless of slope – every line can be translated so that it contains no Martin–Löf random point. Moreover, the line can miss the larger class of all computably random points.

Our solution of this problem builds on a very old – and ongoing – line of research in geometric measure theory. In 1917 Fujiwara and Kakeya [13, 17] posed the question of the minimum area of a plane set in which a unit segment can be continuously reversed without leaving the set, a Kakeya needle set. This question was resolved in 1928 by Besicovitch [2]: such a set can have arbitrarily small measure. The work made use of a construction by Besicovitch from 1919 [1] (but not widely circulated until its republication in 1928 [3]) of a plane set of area 0 containing a unit line segment in every direction, a Kakeya set. This set was constructed using a clever iterated process of partitioning and translating the pieces of an equilateral triangle.

In 1964 Besicovitch used a duality principle to construct a plane set with area 0 that contains a line in every direction, a Besicovitch set [5]. Falconer [10, 11] used an alternative duality principle to give a somewhat simpler construction of a Besicovitch set. This latter set B, which is the point–line dual of a simply defined “fractal dust”, is described in detail in Section 4. Our main result is achieved by showing that B has computable measure 0, as does its Cartesian product with $R^{n}$ , for every $n \in N$ . We also sketch an alternative proof suggested to us by Turetsky (personal communication) and an anonymous reviewer.

Our main result leads us to conjecture that there is, in every direction in Euclidean space, a line that misses not only every computably random point, but every point that is feasibly random (i.e., polynomial time random, as defined in Section 2). We are unable to prove this conjecture at this time, but in Section 5 we prove a weaker result along these lines. Specifically, we show that there exist, in every direction in the Euclidean plane, arbitrarily long line segments missing every point that is double exponential time random (a randomness condition defined in Section 2). Our proof of this fact uses Besicovitch’s above-mentioned 1919 construction of a Kakeya set, together with later refinements of this proof by Perron [25], Schoenberg [29] and Falconer [11].

More recent work on the “sizes” of Besicovitch sets and Kakeya sets has focused on their dimensions. Davies showed that every Kakeya set in $R^{2}$ has Hausdorff dimension 2 [7], and the famous Kakeya conjecture states that Kakeya sets in $R^{n}$ have Hausdorff dimension n for all $n ⩾ 2$ . For more on this history, consult [11, 18].

The remainder of the paper is organized as follows. Section 2 contains preliminary information regarding computable and time-bounded measure and randomness in $R^{n}$ . In Section 3, we present a class of martingales for betting on open sets. In Section 4, we describe Falconer’s Besicovitch set B and prove the main theorem in $R^{2}$ . In Section 5, we describe a Kakeya set K and use it to prove our result on segments missing every double exponential time random point in $R^{2}$ . Section 6 extends our two theorems to $R^{n}$ ( $n ⩾ 2$ ). Section 7 mentions open problems.

2. Computable and time-bounded randomness in $R^{n}$

We now discuss the elements of computable measure and randomness in $R^{n}$ . For each $r \in N$ and each $u = (u_{1}, \dots, u_{n}) \in Z^{n}$ , let $Q_{r} (u) = [u_{1} \cdot 2^{- r}, (u_{1} + 1) \cdot 2^{- r}) \times \dots \times [u_{n} \cdot 2^{- r}, (u_{n} + 1) \cdot 2^{- r})$ be the r-dyadic cube at u. Note that each $Q_{r} (u)$ is “half-open, half-closed” in such a way that, for each $r \in N$ , the family $Q_{r} = {Q_{r} (u) ∣ u \in {0, \dots, 2^{r} - 1}^{n}}$ is a partition of the unit cube $Q_{0} (0) = {[0, 1)}^{n}$ . The family $Q = ⋃_{r = 0}^{\infty} Q_{r}$ is the set of all dyadic cubes in ${[0, 1)}^{n}$ .

A martingale on ${[0, 1)}^{n}$ is a function $d : Q \to [0, \infty)$ satisfying $d (Q_{r} (u)) = 2^{- n} \sum_{a \in {0, 1}^{n}} d (Q_{r + 1} (2 u + a))$ (1) for all $Q_{r} (u) \in Q$ . Intuitively, a martingale d is a strategy for placing successive bets on the location of a point $x \in {[0, 1)}^{n}$ . After r bets have been placed, the bettor’s capital is $d^{(r)} (x) = d (Q_{r} (u)),$ where u us the unique element of ${0, \dots, 2^{r} - 1}^{n}$ such that $x \in Q_{r} (u)$ . The bettor’s next bet is on which of the $2^{n}$ immediate subcubes $Q_{r + 1} (2 u + a)$ of $Q_{r} (u)$ has x as an element. The condition (1) says that the bettor’s expected capital after this bet is exactly the bettor’s capital before the bet, i.e., the payoffs are fair. A martingale d succeeds at a point $x \in {[0, 1)}^{n}$ if $\underset{r \to \infty}{lim sup} d^{(r)} (x) = \infty .$ A well known theorem of Ville [30], restated in the present setting, says that a set $E \subseteq {[0, 1)}^{n}$ has Lebesgue measure $m (E) = 0$ if and only if there is a martingale d that succeeds at every point $x \in E$ . It follows easily by the countable additivity and translation invariance of Lebesgue measure that a set $E \subseteq R^{n}$ has Lebesgue measure 0 if and only if there is a martingale d that succeeds at every point $x \in E^{#}$ , where $E^{#} = {[0, 1)}^{n} \cap ⋃_{t \in Z^{n}} (E + t) .$ (2)

Let $J = {(r, u) \in N \times Z^{n} ∣ u \in {0, \dots, 2^{r} - 1}^{n}} .$ Then a martingale $d : Q \to [0, \infty)$ is computable if there is a computable function $\hat{d} : N \times J \to Q \cap [0, \infty)$ such that, for all $(s, r, u) \in N \times J$ , $| \hat{d} (s, r, u) - d (Q_{r} (u)) | ⩽ 2^{- s} .$ (3) A set $E \subseteq R^{n}$ is defined to have computable measure 0 if there is a computable martingale d that succeeds at every point $x \in E^{#}$ , where $E^{#}$ is defined as in (2). A point $x \in R^{n}$ is computably random if it is not an element of any set of computable measure 0, i.e., if there is no computable martingale that succeeds at x. Computable randomness was introduced by Schnorr [27, 28]. It is well known [9, 24] that every random point in $R^{n}$ (i.e., every Martin–Löf random point in $R^{n}$ ) is computably random and that the converse does not hold. In particular, then, almost every point in $R^{n}$ is computably random.

Resource-bounded measure, a complexity-theoretic generalization of Lebesgue measure that induces measure on complexity classes, has been used to define complexity-theoretic notions of randomness [21]. Adapting these notions to Euclidean space, a martingale $d : Q \to [0, \infty)$ is p-computable (respectively, ee-computable) if there is a function $\hat{d} : N \times J \to Q \cap [0, \infty)$ that satisfies (3) and is computable in ${(s + r)}^{O (1)}$ time (respectively, in $2^{2^{O (s + r)}}$ time). A point $x \in R^{n}$ is p-random (or polynomial time random, or feasibly random) if no p-computable martingale succeeds at x [21]. A point $x \in R^{n}$ is ee-random (or double exponential time random) if no ee-computable martingale succeeds at x [16]. It is routine to show that every computably random point is ee-random, that every ee-random point is p-random, and that the converses of these statements are false.

3. Betting on open sets

In this section we describe a class of martingales that are used in the proof of the main theorem in Section 4. These martingales are also likely to be useful in future investigations.

For any set $G \subseteq {[0, 1)}^{n}$ with $m (G) > 0$ , define a martingale $d_{G} : Q \to [0, \infty)$ recursively as follows.

$d_{G} (Q_{0} (0)) = 1$ .

For all $r ⩾ 0$ , $u \in {0, \dots, 2^{r} - 1}^{n}$ , and $a \in {0, 1}^{n}$ , $d_{G} (Q_{r + 1} (2 u + a)) = \{\begin{matrix} 0 & if d_{G} (Q_{r} (u)) = 0, \\ 2^{n} d_{G} (Q_{r} (u)) \frac{m (G \cap Q_{r + 1} (2 u + a))}{m (G \cap Q_{r} (u))} & otherwise . \end{matrix}$

That is, for each cube

Q \in Q_{r}

, the values of the martingale on the immediate subcubes of Q are proportional to the measures of the subcubes’ intersections with G.

Theorem 3.1.
For every nonempty set G that is open as a subset of the subspace ${[0, 1)}^{n}$ of $R^{n}$ and every $x \in G$ , $d_{G}^{(r)} (x) = 1 / m (G)$ for all sufficiently large r.
Proof.
Let G be a nonempty open set in the subspace ${[0, 1)}^{n}$ of $R^{n}$ . Then $m (G) > 0$ , and by a routine induction argument, for any $r \in N$ and $u \in {0, \dots, 2^{r} - 1}^{n}$ , $d_{G} (Q_{r} (u)) = 2^{n r} \frac{m (G \cap Q_{r} (u))}{m (G)} .$ (4) For any $x \in G$ there exists $ε > 0$ such that $B_{ε} (x) \subseteq G \cap {[0, 1)}^{n}$ , where $B_{ε} (x)$ is the open ball of radius ε around x. Let $r > - log (ε)$ and $Q \in Q_{r}$ such that $x \in Q$ . Then $d_{G}^{(r)} (x) = d_{G} (Q)$ , and $2^{- r} < ε$ , so $Q \subseteq B_{ε} (x) \subseteq G$ . Applying (4), $d_{G}^{(r)} (x) = 2^{n r} \frac{m (G \cap Q)}{m (G)} = 2^{n r} \frac{m (Q)}{m (G)} = \frac{1}{m (G)} .$ □

When G is open, we call $d_{G}$ the open set martingale for G.
4. Betting on a Besicovitch set

This section reviews Falconer’s construction of the Besicovitch set B mentioned in the Introduction and proves that the set B in fact has computable measure 0. Hence B contains a line in every direction in $R^{2}$ , and each of these lines misses every computably random point in $R^{2}$ .

For each $m, b \in R$ , let $L_{m, b} \subseteq R^{2}$ be the line with slope m and y-intercept b. Falconer defined the line set operator $L : P (R^{2}) \to P (R^{2})$ , where $P (R^{2})$ is the set of all subsets of $R^{2}$ , by $L (F) = ⋃ {L_{m, b} ∣ (m, b) \in F}$ for all $F \subseteq R^{2}$ . We call $L (F)$ the line set of F. It is easy to verify that the operator $L$ is monotone and maps compact sets to closed sets.

We are interested in the line set of a particular self-similar fractal F, which we now define. Consider the alphabet $Σ = {0, 1, 2, 3}$ . For each $i \in Σ$ define the contraction $S_{i} : R^{2} \to R^{2}$ by $S_{i} (x, y) = \frac{1}{4} ((x, y) + (i, a_{i})),$ where $a_{0} = 2$ , $a_{1} = 0$ , $a_{2} = 3$ and $a_{3} = 1$ . For each $w \in Σ^{*}$ define the set $F (w) \subseteq R^{2}$ by the recursion $\begin{array}{rcl} F (λ) = {[0, 1]}^{2}, \\ F (i w) = S_{i} (F (w)) \end{array}$ for all $i \in Σ$ and $w \in Σ^{*}$ . For each $k \in N$ let $F_{k} = ⋃ {F (w) ∣ w \in Σ^{k}} .$

The sets $F_{0}$ and $F_{1}$ , along with their line sets, are depicted in Fig. 1. We are interested in the set $F = ⋂_{k = 0}^{\infty} F_{k} .$ This set F is an uncountable, totally disconnected set, informally called a “fractal dust”. More formally it is the attractor of the iterated function system $(S_{0}, S_{1}, S_{2}, S_{3})$ , i.e., it is a self-similar fractal.

Figure 1.

$F_{0}$ and $F_{1}$ , along with their line sets. $F_{0}$ and $L (F_{0})$ are shaded gray; $F_{1}$ and $L (F_{1})$ are black.

Let ${Ref}_{Y} : R^{2} \to R^{2}$ and ${Rot}_{θ} : R^{2} \to R^{2}$ denote reflection across the y-axis and rotation about the origin by the angle θ, respectively. The set $B = L (F) \cup {Rot}_{\frac{π}{2}} (L (F)) \cup {Ref}_{Y} (L (F) \cup {Rot}_{\frac{π}{2}} (L (F)))$ (5) is the Besicovitch set that we use for our main theorem.

Observation 4.1.

The set B contains a line in every direction in $R^{2}$ .

Proof.

Let $m \in [0, 1]$ . By (5) it suffices to show that $L (F)$ contains a line of slope m. But this is clear, since each $F_{k}$ , and hence F, contains a point of the form $(m, b)$ . □

Using the duality principle and some nontrivial fractal geometry, Falconer also proved the following.

Lemma 4.1 ([10, 11]).

The set B has Lebesgue measure 0 .

It is not obvious whether or how the proof of Lemma 4.1 can be effectivized. Nevertheless we prove the following.

Theorem 4.2 (Main theorem, in $R^{2}$ ).

The set B has computable measure 0. Hence there is, in every direction in $R^{2}$ , a line that misses every computably random point.

To prove Theorem 4.2, we begin with a property of the line set operator.

Lemma 4.3.
Let I and J be closed intervals of finite length, so that $R = I \times J$ is a solid rectangle. Let $R^{'} = (I \times J^{\circ}) \cup (I^{\circ} \times J)$ be R with its four corners removed. Then $L (R^{'}) \subseteq L {(R)}^{\circ} \cup Y,$ where $L {(R)}^{\circ}$ is the topological interior of $L (R)$ and $Y = {(0, y) ∣ y \in R}$ is the y-axis of $R^{2}$ .
Proof.
First let $(m, b) \in I \times J^{\circ}$ . Then there exists $ε > 0$ such that ${m} \times (b - ε, b + ε) \subseteq I \times J .$ Then $L_{m, b^{'}} \subseteq L (I \times J) = L (R)$ holds for all $b^{'} \in (b - ε, b + ε)$ , so $L_{m, b} \subseteq L {(R)}^{\circ}$ . This shows that $L (I \times J^{\circ}) \subseteq L {(R)}^{\circ}$ .

Now let $(m, b) \in I^{\circ} \times J$ . Then there exists $ε > 0$ such that $(m - ε, m + ε) \times {b} \subseteq I \times J .$ Then $L_{m^{'}, b} \subseteq L (I, J) = L (R)$ holds for all $m^{'} \in (m - ε, m + ε)$ , so $L_{m, b} \subseteq L {{(R)}^{\circ} \cup {(0, b)} \subseteq L (R)}^{\circ} \cup Y .$ This shows that $L (I^{\circ} \times J) \subseteq L (R) \cup Y$ . □

Lemma 4.3 has the following consequence for the stages $F_{k}$ in the construction of F.
Corollary 4.4.
For every $n \in N$ $L (F_{k + 1}) \subseteq L {(F_{k})}^{\circ} \cup Y .$
Proof.
It suffices to note that $F_{k + 1}$ dos not contain any of the corners of the squares comprising $F_{k}$ . □
Proof of Theorem 4.2.
Trivial martingale transformations show that the sets of computable measure 0 in $R^{2}$ are closed under $90^{\circ}$ rotations, reflections about the coordinate axes, and finite unions. Hence by (5) it suffices to prove that $L (F)$ has computable measure 0. We do this by presenting a computable martingale d that succeeds at every point $x \in L {(F)}^{#}$ , where $L {{(F)}^{#} = [0, 1)}^{2} \cap ⋃_{t \in Z^{2}} (L (F) + t)$ is defined as in (2).

For each $t \in Z^{2}$ and $k \in N$ let $H_{t, k} = {{[0, 1)}^{2} \cap (L (F_{k})}^{\circ} + t),$ noting that $H_{t, k}$ is an open set in the subspace ${[0, 1)}^{2}$ of $R^{2}$ . The sets $F_{k}$ are so simply defined that the function $h : Z^{2} \times N \to Q$ defined by $h (t, k) = m (H_{t, k})$ is computable. For each $t \in Z^{2}$ Lemma 4.1 tells us that $\begin{array}{rcl} 0 & = & m ({[0, 1)}^{2} \cap (L (F) + t)) \\ = & m (⋂_{k = 0}^{\infty} ({[0, 1)}^{2} \cap (L (F_{k}) + t))) \\ = & lim_{k \to \infty} m ({[0, 1)}^{2} \cap (L (F_{k}) + t)) \\ = & lim_{k \to \infty} h (t, k) . \end{array}$ Hence the function $k : Z^{2} \times N \to N$ defined by $k (t, j) = the least k such that h (t, k) ⩽ 2^{- j}$ is also computable.

For each $t = (t_{1}, t_{2}) \in Z^{2}$ and $j \in N$ , define the set $G_{t, j}$ and the coefficient $c_{t, j}$ as follows.
If $H_{t, k (t, | t_{1} | + | t_{2} | + j)} \neq \emptyset$ , then $G_{t, j} = H_{t, k (t, | t_{1} | + | t_{2} | + j)}$ and $c_{t, j} = m (G_{t, j}) .$

Otherwise, $G_{t, j} = {[0, 1)}^{2}$ and $c_{t, j} = 2^{- (| t_{1} | + | t_{2} | + j)} .$
Define the special-purpose martingale $d_{Y}$ by $d_{Y} (Q_{r} (u)) = \{\begin{matrix} 2^{r} & if u_{1} = 0, \\ 0 & if u_{1} > 0 \end{matrix}$ for all $r \in N$ and $u = (u_{1}, u_{2}) \in {0, \dots, 2^{r} - 1}^{2}$ . Finally, let $d = d_{Y} + \sum_{t \in Z^{2}} \sum_{j = 0}^{\infty} c_{t, j} d_{G_{t, j}},$ where each $d_{G_{t, j}}$ is defined from $G_{t, j}$ as in Section 3. Then $\begin{array}{rcl} d ({[0, 1)}^{2}) & ⩽ & 1 + \sum_{t \in Z^{2}} \sum_{j = 0}^{\infty} 2^{- (| t_{1} | + | t_{2} | + j)} \\ = & 19 < \infty, \end{array}$ so d is a martingale.

To see that d is computable, define $\hat{d} : N \times J \to Q$ (where J is defined as in Section 2) by $\hat{d} (s, r, u) = d_{Y} (Q_{r} (u)) + \sum_{t_{1} = - p}^{p} \sum_{t_{2} = - p}^{p} \sum_{j = 0}^{p} c_{t, j} d_{G_{t, j}} (Q_{r} (u)),$ where $p = s + 2 r + 6$ . Then $\hat{d}$ is computable, and it is clear that $\hat{d} (s, r, u) ⩽ d (Q_{r} (u))$ holds for all $(s, r, u) \in N \times J$ . We now fix $(s, r, u) \in N \times J$ , let $p = s + 2 r + 6$ , and estimate the difference $d (Q_{r} (u)) - \hat{d} (s, r, u)$ .

For each index set $I \subseteq Z^{2} \times N$ define the sums $σ (I) = \sum_{(t, j) \in I} c_{t, j} d_{G_{t, j}} (Q_{r} (u))$ and $τ (I) = {\sum_{(t, j) \in I} 2}^{- (| t_{1} | + | t_{2} | + j)} .$ By the trivial bound $d_{G_{t, j}} (Q_{r} (u)) ⩽ 4^{r}$ and the fact that $c_{t, j} ⩽ 2^{- (| t_{1} | + | t_{2} | + j)}$ always holds, we have $σ (I) ⩽ 4^{r} τ (I)$ for every $I \subseteq Z^{2} \times N$ . Now $d (Q_{r} (u)) = d_{Y} (Q_{r} (u)) + σ (Z^{2} \times N)$ and $\hat{d} (s, r, u) = d_{Y} (Q_{r} (u)) + σ (I_{0}),$ where $I_{0} = {(t_{1}, t_{2}, j) ∣ - p ⩽ t_{1} ⩽ p, - p ⩽ t_{2} ⩽ p, j ⩽ p},$ so $\begin{array}{rcl} d (Q_{r} (u)) - \hat{d} (s, r, u) & = & σ ((Z^{2} \times N) ∖ I_{0}) \\ ⩽ & 4^{r} τ ((Z^{2} \times N) ∖ I_{0}) . \end{array}$ If we let $I_{a} = {(t_{1}, t_{2}, j) ∣ | t_{a} | > p}$ for $a \in {1, 2}$ and $I^{+} = {(t_{1}, t_{2}, j) ∣ j > p},$ then $(Z^{2} \times N) ∖ I_{0} \subseteq I_{1} \cup I_{2} \cup I^{+},$ so $d (Q_{r} (u)) - \hat{d} (s, r, u) ⩽ 4^{r} (τ (I_{1}) + τ (I_{2}) + τ (I^{+})) .$ Now $\begin{array}{rcl} τ (I_{1}) & = & τ (I_{2}) \\ = & 2 \sum_{t_{1} = p + 1}^{\infty} 2^{- t_{1}} \sum_{t_{2} = - \infty}^{\infty} 2^{- | t_{2} |} \sum_{j = 0}^{\infty} 2^{- j} \\ = & 12 \sum_{t_{1} = p + 1}^{\infty} 2^{- t_{1}} \\ = & 12 \cdot 2^{- p} \end{array}$ and $\begin{array}{rcl} τ (I^{+}) & = & \sum_{t_{1} = - \infty}^{\infty} 2^{- | t_{1} |} \sum_{t_{2} = - \infty}^{\infty} 2^{- | t_{2} |} \sum_{j = p + 1}^{\infty} 2^{- j} \\ = & 9 \cdot 2^{- p}, \end{array}$ so $\begin{array}{rcl} d (Q_{r} (u)) - \hat{d} (s, r, u) & ⩽ & 4^{r} \cdot 33 \cdot 2^{- p} \\ = & 33 \cdot 2^{- (s + 6)} \\ < & 2^{- s} . \end{array}$ Hence $\hat{d}$ testifies that d is computable.

To see that d succeeds at every point in $L {(F)}^{#}$ , let $x \in {[0, 1)}^{2} \cap (L (F) + t)$ . By Corollary 4.4 we have two cases.

Case 1. $x \in Y$ . Then $\begin{array}{rcl} \underset{r \to \infty}{lim sup} d^{(r)} (x) & ⩾ & \underset{r \to \infty}{lim sup} d_{Y}^{(r)} (x) \\ = & \underset{r \to \infty}{lim sup} 2^{r} \\ = & \infty, \end{array}$ so d succeeds at x.

Case 2. $x \in L (F_{k})$ for every $k \in N$ . Then $x \in H_{t, k}$ for every $k \in N$ , so clause (i) holds in the definitions of $G_{t, j}$ and $c_{t, j}$ for every $j \in N$ , with $x \in G_{t, j}$ . By Theorem 3.1, this implies that $\begin{array}{rcl} \underset{r \to \infty}{lim sup} d^{(r)} (x) & ⩾ & \underset{r \to \infty}{lim sup} \sum_{j = 0}^{\infty} c_{t, j} d_{G_{t, j}}^{(r)} (x) \\ = & \underset{r \to \infty}{lim sup} \sum_{j = 0}^{\infty} m (G_{t, j}) d_{G_{t, j}}^{(r)} (x) \\ = & \infty, \end{array}$ whence d succeeds at x. □

In remarks on an early draft of this paper, Turetsky and an anonymous reviewer pointed out an alternative proof of Theorem 4.2. The key fact, proved by Wang [9, 31], is that every computably random point x is Kurtz random (also called weakly random [20]), meaning that x is not an element of any computably closed (i.e., $Π_{1}^{0}$ ) set of measure 0. Furthermore, the above-mentioned fact that the operator $L$ maps compact sets to closed sets can be extended to prove that $L$ maps bounded $Π_{1}^{0}$ sets to $Π_{1}^{0}$ sets. Finally, it is routine to verify that the fractal dust F is a bounded $Π_{1}^{0}$ set. These things and Lemma 4.1 imply that $L (F)$ contains no computably random point, whence Theorem 4.2 holds by Observation 4.1. This elegant proof is simpler than our martingale construction, even when Wang’s proof is included. However, we believe that the direct martingale construction may help illuminate the path to results on time-bounded randomness, so we retain the martingale proof in this paper.
5. Betting in doubly exponential time

In light of Theorem 4.2 it is natural to ask whether there is, in every direction in $R^{2}$ , a line that misses not only every computably random point, but every feasibly random point. We do not know the answer to this question at the time of this writing, but we prove a weaker result of this type in this section.

As noted in the Introduction, Besicovitch constructed a Kakeya set, a Lebesgue measure 0 plane set containing a unit line segment in every direction, in 1919. Our objective here is to specify a Kakeya set K and prove that it has ee-measure 0 (a condition defined in Section 2). Our specification and proof take advantage of Besicovitch’s original work, together with subsequent refinements by Perron [25], Schoenberg [29] and Falconer [11].

We first describe Perron trees, the building blocks of our set K. Let $τ = △ (u, v, w)$ be a triangle of height h with its base $\overline{uv}$ on the x-axis. In this discussion we regard triangles as including their interiors. Note that τ contains a line segment of length h in every direction between the directions of $\overline{uw}$ and $\overline{vw}$ . Given a positive integer k, cut τ into $2^{k}$ nonoverlapping triangles $τ_{1}, \dots, τ_{2^{k}}$ of equal area, as indicated in Fig. 2(a). (Throughout this discussion, sets in $R^{2}$ are nonoverlapping if their interiors are disjoint.) Besicovitch showed that these $2^{k}$ smaller triangles can be slid horizontally along the x-axis in such a way that their union, due to high overlap, has very small area. Perron simplified Besicovitch’s overlap scheme to that depicted in Fig. 2(b). Note that, notwithstanding its small area, the set in Fig. 2(b) still contains a line segment in every direction between the directions of $\overline{uw}$ and $\overline{vw}$ . Schoenberg coined the term Perron trees for sets of the type depicted in Fig. 2(b) and gave a simpler, recursive “sprouting construction” of the Perron tree $P_{k} (τ)$ as a union of $2^{k + 1} - 1$ nonoverlapping triangles as in Fig. 2(c).

Figure 2.

(a) A triangle cut into eight pieces $τ_{1}, \dots, τ_{8}$ ; (b) a Perron tree constructed by sliding those pieces together; (c) the same Perron tree via Schoenberg’s sprouting construction.

We now specify the Perron tree $P_{k} (τ)$ . Throughout this discussion script capital letters represent collections of nonoverlapping polygons. Let $(\hat{u}, \hat{v}, \hat{w}) = (\frac{2 u}{h}, \frac{2 v}{h}, \frac{2 w}{h}),$ so that $△ (\hat{u}, \hat{v}, \hat{w}) = \frac{2}{h} τ$ is a triangle of height 2, similar to τ, with its base on the x-axis. Let $T_{0} = {△ (\hat{u}, \hat{v}, \hat{w})},$ and $T_{1} = {△ (\frac{\hat{u} + \hat{w}}{2}, \hat{w}, \frac{3 \hat{w} - \hat{v}}{2}), △ (\frac{\hat{v} + \hat{w}}{2}, \hat{w}, \frac{3 \hat{w} - \hat{u}}{2})} .$ For $i ⩾ 2$ , let $T_{i} = ⋃_{t \in T_{i - 1}} {△ (m_{t}, c_{t}, 2 c_{t} - b_{t}), △ (b_{t}, c_{t}, 2 c_{t} - m_{t})},$ where for $t \in T_{i - 1}$ , $a_{t}$ , $b_{t}$ , and $c_{t}$ are the vertices of t with y-coordinates $i - 1$ , i, and $i + 1$ , respectively, and $m_{t}$ is the midpoint of $\overline{a_{t} c_{t}}$ . Let $T = ⋃_{i = 0}^{k} T_{i} .$ Then $P_{k} (τ) = \frac{h}{k + 2} \cup T$ is the k-level Perron tree based on τ.

As Schoenberg noted, we can define the same Perron tree as a union of shifted triangles $τ_{i}$ . Let $\begin{array}{rcl} C & = & {x ∣ (x, h) \in P_{k} (τ)} \\ = & {x ∣ c_{t} = (x, h) for some t \in T_{k}}, \end{array}$ and index the elements of C as $c_{1}, \dots, c_{2^{k}}$ , where $c_{i} > c_{i + 1}$ for $1 ⩽ i < 2^{k}$ . Let $P_{k} (τ) = {τ_{i} + (c_{i}, 0) ∣ 1 ⩽ i ⩽ 2^{k}} .$ Then $P_{k} (τ) = ⋃ P_{k} (τ) .$

Observation 5.1 (Falconer [11]).

$P_{k} (τ)$ is contained in the trapezoid with vertex set ${2 u - v, w - v + u, w + v - u, 2 v - u} .$

Theorem 5.1 (Schoenberg [29]).

$m (P_{k} (τ)) = \frac{m (τ)}{2 k + 4}$ .

We now construct a sequence ${S_{j}}_{j \in N}$ of plane sets. Each $S_{j}$ is the union of a collection $S_{j}$ of triangles. Define $S_{0} = {△ ((0, 0), (1, 0), (1 / 2, 1 / 2))},$ and for $j ⩾ 1$ , cut the base of each triangle in $S_{j - 1}$ into $2^{j + 1}$ equal pieces in the manner of Fig. 2(a) to form $p_{j} = 2^{j + 1} | S_{j - 1} |$ triangles $τ_{j}^{1}, \dots, τ_{j}^{p_{j}}$ , and let $P_{j}^{i} = P_{2^{j}} (τ_{j}^{i}) .$ Then define $S_{j} = ⋃_{i = 1}^{p_{j}} P_{j}^{i},$ and $S_{j} = ⋃ S_{j} .$

For $E \subseteq R^{2}$ and $ε > 0$ , define $G_{ε} (E) = ⋃_{δ \in (- ε, ε)} E^{\circ} + (δ, 0) .$ We will repeatedly make use of the fact that for any $E_{1}, E_{2} \subseteq R^{2}$ and $ε > 0$ , $G_{ε} (E_{1} \cup E_{2}) = G_{ε} (E_{1}) \cup G_{ε} (E_{2}) .$

For $j \in N$ , let $ε_{j} = \frac{1}{2^{j + 1} | S_{j} |},$ and define $G_{j} = G_{ε_{j}} (S_{j}) .$

Lemma 5.2.
For $j \in N$ , $G_{j + 1} \subseteq G_{j}$ .
Proof.
Since the base of each $τ_{j + 1}^{i}$ has length $\frac{1}{p_{j + 1}} = ε_{j} / 2$ , Observation 5.1 tells us for $i = 1, \dots, p_{j + 1}$ that $P_{j + 1}^{i} \subseteq \overline{G_{ε_{j} / 2} (τ_{j + 1}^{i})} .$ Since $ε_{j + 1} < ε_{j} / 2$ , this implies that $G_{ε_{j + 1}} (P_{j + 1}^{i}) \subseteq G_{ε_{j}} (τ_{j + 1}^{i}) .$ Thus $\begin{array}{rcl} G_{j + 1} & = & G_{ε_{j + 1}} (S_{j + 1}) \\ = & G_{ε_{j + 1}} (⋃_{i = 1}^{p_{j + 1}} P_{j + 1}^{i}) \\ = & ⋃_{i = 1}^{p_{j + 1}} G_{ε_{j + 1}} (P_{j + 1}^{i}) \\ \subseteq & ⋃_{i = 1}^{p_{j + 1}} G_{ε_{j}} (τ_{j + 1}^{i}) \\ = & G_{ε_{j}} (⋃_{i = 1}^{p_{j + 1}} τ_{j + 1}^{i}) \\ = & G_{ε_{j}} (S_{j}) \\ = & G_{j} . \end{array}$ □

Let $F = ⋂_{j \in N} \overline{G_{j}}$ and $K_{0} = ⋃_{c \in N} c F .$ Then let $K = K_{0} \cup {Rot}_{π / 4} (K_{0}) .$
Proposition 5.3.
K contains arbitrarily long line segments in every direction in $R^{2}$ .
Proof.
It suffices to show that F contains a closed segment of length $\frac{1}{3}$ in every direction $θ \in [\frac{π}{4}, \frac{3 π}{4}]$ . Fix $θ \in [\frac{π}{4}, \frac{3 π}{4}]$ . For each $j \in N$ , fix a closed segment $L_{j} \subseteq \overline{G_{j}}$ of length $\frac{1}{3}$ in direction θ. By compactness there is an infinite set $I \subseteq N$ such that the sequence $(L_{i} ∣ i \in I)$ converges (in Hausdorff distance) to a segment L. It is clear that L is a segment of length $\frac{1}{3}$ in direction θ. Using compactness again, we have $L \subseteq \overline{G_{j}}$ for each j, whence $L \subseteq F$ . □
Theorem 5.4.
The set K has ee-measure 0. Hence there exist, in every direction in $R^{2}$ , arbitrarily long line segments that miss every ee-random point.
Proof.
We first show by induction that $| S_{j} | ⩽ 2^{2^{j + 2}}$ . This holds for $j = 0$ . Fix $j ⩾ 1$ and suppose the claim holds for $j - 1$ . Then we have $\begin{array}{rcl} | S_{j} | & = & \sum_{i = 1}^{p_{j}} | P_{j}^{i} | \\ = & p_{j} \cdot 2^{2^{j}} \\ = & 2^{j + 1} | S_{j - 1} | \cdot 2^{2^{j}} \\ ⩽ & 2^{j + 1 + 2^{j + 1} + 2^{j}} \\ ⩽ & 2^{2^{j + 2}}, \end{array}$ so the claim holds for every $j \in N$ .

Now consider $G_{j}^{i} = G_{ε_{j}} (P_{j}^{i})$ . By Theorem 5.1, $\begin{array}{rcl} m (P_{j}^{i}) & = & \frac{1}{(4 p_{j}) (2 \cdot 2^{j} + 4)} \\ < & \frac{1}{2^{j + 3} p_{j}}, \end{array}$ and $\begin{array}{rcl} m (G_{j}^{i} ∖ P_{j}^{i}) & ⩽ & \sum_{t \in P_{j}^{i}} m (G_{ε_{j}} (t) ∖ t) \\ ⩽ & | P_{j}^{i} | ε_{j} \\ = & \frac{| S_{j} | ε_{j}}{p_{j}} \\ = & \frac{1}{2^{j + 1} p_{j}}, \end{array}$ so $m (G_{j}^{i}) < \frac{1}{2^{j} p_{j}} .$

Define the martingale $d : Q \to [0, \infty)$ by $d (Q) = \sum_{j = 0}^{\infty} 2^{- j} \sum_{i = 1}^{p_{j}} \frac{d_{G_{j}^{i}} (Q)}{p_{j}},$ where $d_{G_{j}^{i}}$ is the open set martingale, as defined in Section 3, for $G_{j}^{i}$ . Then by Theorem 3.1, for every $x \in G_{j}^{i}$ , $\begin{array}{rcl} lim_{r \to \infty} d_{G_{j}^{i}}^{(r)} (x) & = & \frac{1}{m (G_{j}^{i})} \\ > & 2^{j} p_{j} . \end{array}$ Thus since $G_{j} = ⋃_{i = 1}^{p_{j}} G_{j}^{i},$ we have $\underset{r \to \infty}{lim sup} d^{(r)} (x) ⩾ | {j ∣ x \in G_{j}} |,$ which is infinite for $x \in F$ , i.e., d succeeds on every $x \in F$ .

We now turn to proving that d is ee-computable. Let J be as in Section 2, and define the function $\hat{d} : N \times J \to Q \cap [0, \infty)$ by $\hat{d} (s, r, u) = \sum_{j = 0}^{2 r + s} 2^{- j} \sum_{i = 1}^{p_{j}} \frac{d_{G_{j}^{i}} (Q_{r} (u))}{p_{j}} .$ Then $\begin{array}{rcl} | d (Q_{r} (u)) - \hat{d} (s, r, u) | & = & \sum_{j = 2 r + s + 1}^{\infty} 2^{- j} \sum_{i = 1}^{p_{j}} \frac{d_{G_{j}^{i}} (Q_{r} (u))}{p_{j}} \\ ⩽ & 4^{r} \sum_{j = 2 r + s + 1}^{\infty} 2^{- j} \\ = & 2^{- s} . \end{array}$

It remains to be shown that $\hat{d} (s, r, u)$ is computable in time $2^{2^{O (r + s)}}$ . For this it is sufficient to show that $d_{G_{j}^{i}} (Q_{r} (u))$ is computable in time $2^{2^{O (r + s)}}$ for each $1 ⩽ i ⩽ p_{j}$ and $0 ⩽ j ⩽ 2 r + s$ . By (4), $d_{G_{j}^{i}} (Q_{r} (u)) = 4^{r} \frac{m (G_{j}^{i} \cap Q_{r} (u))}{m (G_{j}^{i})} .$ Now $\begin{array}{rcl} G_{j}^{i} & = & G_{ε_{j}} (P_{j}^{i}) \\ = & G_{ε_{j}} (⋃ P_{j}^{i}) \\ = & ⋃_{t \in P_{j}^{i}} G_{ε_{j}} (t) \end{array}$ is the union of $ν = 2^{2^{j}}$ trapezoids. The vertices of the triangles t come from the definition of $P_{j} (t)$ , and the vertices of the trapezoid follow immediately. This gives $4 ν$ segments whose intersections can be found efficiently. In total, the figure $G_{j}^{i}$ has at most $4 ν + (\binom{4 ν}{2}) = poly (ν)$ vertices, each of which can be found in $poly (ν)$ time. So it can be triangulated in $poly (ν)$ time into a set $N$ of nonoverlapping triangles with $| N | = poly (ν)$ , where the vertices of every triangle in $N$ an be found in $poly (ν)$ time. Then $m (G_{j}^{i}) = \sum_{t \in N} m (t),$ and for any $Q \in Q$ , $m (G_{j}^{i} \cap Q) = \sum_{t \in N} m (t \cap Q) .$ Hence we can compute $d_{G_{j}^{i}}$ in time $poly (ν) = 2^{2^{O (r + s)}}$ . □
6. Higher dimensions

For every $n \in N$ , the set $B \times R^{n}$ contains a line in every direction in $R^{n + 2}$ , and Fubini’s theorem implies that this set has Lebesgue measure 0 [12]. In this section we show that $B \times R^{n}$ also has computable measure 0.

For any set $E \subseteq R^{n}$ and $y \in R^{m}$ , for $1 ⩽ m < n$ , define $E_{y} = {(x_{1}, \dots, x_{n - m}) \in R^{n - m} ∣ (x_{1}, \dots, x_{n - m}, y_{1}, \dots, y_{m}) \in E} .$ The following computable Fubini theorem may be known, but we do not know a reference at the time of this writing.

Theorem 6.1.
Let $E \in R^{n}$ . If there is a computable martingale d on ${[0, 1)}^{n - m}$ such that the set $N_{E} (d) = {y \in {[0, 1)}^{m} ∣ \exists x \in E_{y}^{#} such that d does not succeed at x}$ has computable measure 0, then E has computable measure 0 .
Proof.
Let $d_{1}$ be such a martingale for E and let $d_{2}$ be a computable martingale on ${[0, 1)}^{m}$ that succeeds at every $y \in N_{E} (d_{1})$ . Define two martingales on ${[0, 1)}^{n}$ , $d_{1}^{'}$ and $d_{2}^{'}$ , by $\begin{array}{rcl} d_{1}^{'} (Q_{r} (u_{1}, \dots, u_{n})) = d_{1} (Q_{r} (u_{1}, \dots, u_{n - m})), \\ d_{2}^{'} (Q_{r} (u_{1}, \dots, u_{n})) = d_{2} (Q_{r} (u_{n - m + 1}, \dots, u_{n})) . \end{array}$ Note that both are computable.

Now let $x = (x_{1}, \dots, x_{n}) \in E^{#}$ . If $(x_{n - m + 1}, \dots, x_{n}) \in N_{E} (d_{1})$ , then $d_{2}^{'}$ succeeds at x; otherwise, $d_{1}^{'}$ succeeds at x. We conclude that the computable martingale $d = d_{1}^{'} + d_{2}^{'}$ succeeds at every $x \in E^{#}$ , whence E has computable measure 0. □
Corollary 6.2.
For every computable measure 0 set E and $n \in N$ , the set $E \times R^{n}$ has computable measure 0 .
Theorem 6.3 (Main theorem, in $R^{n}$ ).

For every $n ⩾ 2$ there is, in every direction in $R^{n}$ , a line that misses every computably random point.

Proof.
By Theorem 4.2, B has computable measure 0. Thus by Corollary 6.2, $B \times R^{n - 2}$ has computable measure 0 for every $n ⩾ 3$ . □

It is routine to prove double exponential time versions of Theorem 6.1 and Corollary 6.2, and hence to extend Theorem 5.4 to $R^{n}$ in a similar fashion.
7. Open problems

As noted in the Introduction, we conjecture that there is a line in every direction missing every feasibly random point in Euclidean space. Proving or disproving this conjecture may require a significant advance beyond current understanding of the algorithmic geometric measure theory of Besicovitch and Kakeya sets. In the meantime, more modest goals may be achieved. Can Theorem 5.4 be improved to singly exponential time, or to lines instead of segments?

Besicovitch’s duality idea for constructing the set B came soon after, and was perhaps prompted by, the Mathematical Association of America’s production of a film in which he explained his 1919 solution of the Kakeya needle problem. (The article [4] is based on this film.) Does a copy of this film still exist?

Footnotes

Acknowledgements

We thank Dan Turetsky and an anonymous reviewer for pointing out the alternate proof of Theorem and for a useful correction. We thank two other anonymous reviewers for several useful suggestions. Research of the first author supported in part by National Science Foundation Grant 1247051. Research of the second author supported in part by National Science Foundation Grant 1101690.

References

[1]

A.S.

Besicovitch , Sur deux questions d’intégrabilité des fonctions, Journal de la Société de physique et de mathematique de l’Universite de Perm 2 (1919), 105–123.

[2]

A.S.

Besicovitch, On Kakeya’s problem and a similar one, Mathematische Zeitschrift 27 (1928), 312–320.

[3]

A.S.

Besicovitch, On the fundamental geometric properties of linearly measurable plane sets of points, Mathematische Annalen 98 (1928), 422–464.

[4]

A.S.

Besicovitch, The Kakeya problem, American Mathematical Monthly 70 (1963), 697–706.

[5]

A.S.

Besicovitch, On fundamental geometric properties of plane line sets, Journal of the London Mathematical Society 39 (1964), 441–448.

[6]

P.J.

Couch,

B.D.

Daniel and

T.H.

McNicholl, Computing space-filling curves, Theory of Computing Systems 50(2) (2012), 370–386.

[7]

R.O.

Davies, Some remarks on the Kakeya problem, Proceedings of the Cambridge Philosophical Society 69 (1971), 417–421.

[8]

Dougherty,

J.H.

Lutz,

R.D.

Mauldin and

Teutsch, Translating the Cantor set by a random real, Transactions of the American Mathematical Society 366 (2014), 3027–3041.

[9]

Downey and

Hirschfeldt, Algorithmic Randomness and Complexity, Springer-Verlag, 2010.

10.

[10]

K.J.

Falconer, Sections of sets of zero Lebesgue measure, Mathematika 27 (1980), 90–96.

11.

[11]

K.J.

Falconer, The Geometry of Fractal Sets, Cambridge University Press, 1985.

12.

[12]

K.J.

Falconer, Fractal Geometry: Mathematical Foundations and Applications, 2nd edn, Wiley, 2003.

13.

[13]

Fujiwara and

Kakeya, On some problems of maxima and minima for the curve of constant breadth and the in-revolvable curve of the equilateral triangle, Tôhoku Mathematical Journal 11 (1917), 92–110.

14.

[14]

Gu,

J.H.

Lutz and

Mayordomo, Points on computable curves, in: FOCS, IEEE Computer Society, 2006, pp. 469–474.

15.

[15]

Gu,

J.H.

Lutz,

Mayordomo and

Moser, Dimension spectra of random subfractals of self-similar fractals, Annals of Pure and Applied Logic 366(11) (2014), 1701–1726.

16.

[16]

R.C.

Harkins and

J.M.

Hitchcock, Upward separations and weaker hypotheses in resource-bounded measure, Theoretical Computer Science 389(1–2) (2007), 162–171.

17.

[17]

Kakeya, Some problems on maxima and minima regarding ovals, Tôhoku Science Reports 6 (1917), 71–88.

18.

[18]

Katz and

Tao, Recent progress on the Kakeya conjecture, in: Proceedings of the 6th International Conference on Harmonic Analysis and Partial Differential Equations, Publicacions Matematiques, 2002, pp. 161–180.

19.

[19]

Kjos-Hanssen and

Nerode, Effective dimension of points visited by Brownian motion, Theoretical Computer Science 410(4–5) (2009), 347–354.

20.

[20]

Kurtz, Randomness and genericity in the degrees of unsolvability, PhD thesis, University of Illinois at Urbana-Champaign, 1981.

21.

[21]

J.H.

Lutz, Almost everywhere high nonuniform complexity, Journal of Computer and System Sciences 44(2) (1992), 220–258.

22.

[22]

J.H.

Lutz and

Mayordomo, Dimensions of points in self-similar fractals, SIAM J. Comput. 38(3) (2008), 1080–1112.

23.

[23]

T.H.

McNicholl, The power of backtracking and the confinement of length, Proceedings of the American Mathematical Society 141(3) (2013), 1041–1053.

24.

[24]

Nies, Computability and Randomness, Oxford Univ. Press, Inc., New York, NY, USA, 2009.

25.

[25]

Perron, Über einen Satz von Besicovitch, Mathematische Zeitschrift 28 (1928), 383–386.

26.

[26]

Rettinger and

Zheng, Points on computable curves of computable lengths, in: MFCS,

Královic and

Niwinski, eds, Lecture Notes in Computer Science, Vol. 5734, Springer, 2009, pp. 736–743.

27.

[27]

C.-P.

Schnorr, A unified approach to the definition of a random sequence, Mathematical Systems Theory 5 (1971), 246–258.

28.

[28]

C.-P.

Schnorr, Zufälligkeit und Wahrscheinlichkeit, Lecture Notes in Mathematics, Vol. 218, Springer-Verlag, 1971.

29.

[29]

I.J.

Schoenberg, On the Besicovitch–Perron solution of the Kakeya problem, in: Studies in Mathematical Analysis – Essays in Honour of G. Pólya, Stanford Univ. Press, Stanford, CA, 1962, pp. 383–386.

30.

[30]

Ville, Étude Critique de la Notion de Collectif, Gauthier-Villars, Paris, 1939.

31.

[31]

Wang, Randomness and complexity, PhD thesis, University of Heidelberg, 1996.

32.

[32]

Zheng and

Rettinger, Point-separable classes of simple computable planar curves, Logical Methods in Computer Science 8(3) (2012), 1–19.

Lines missing every random point 1

Abstract

Keywords

1. Introduction

2. Computable and time-bounded randomness in R n

Theorem 4.2 (Main theorem, in R 2 ).

Theorem 5.1 (Schoenberg [29]).

Footnotes

Acknowledgements

References

2. Computable and time-bounded randomness in $R^{n}$

Theorem 4.2 (Main theorem, in $R^{2}$ ).