SAS

Abstract

I will discuss the constructive dimension of points in random translates of the Cantor set. The Cantor set ``cancels randomness'' in the sense that some of its members, when added to Martin-Löf random reals, identify a point with lower constructive dimension than the random itself. In particular, we find the Hausdorff dimension of the set of points in a Cantor set translate with a given constructive dimension.

More specifically, let $\mathcal{C}$ denote the standard middle third Cantor set, and for each real $\alpha$ let $\mathcal{E}_{\alpha}$ consist of all real numbers with constructive dimension $\alpha$. Our result is the following.

If $1 -\log2/\log3 \leq \alpha \leq 1$ and $r$ is a Martin-Löf random real, then the Hausdorff dimension of the set $ (\mathcal{C}+r) \cap \mathcal{E}_{\alpha}$ is $\alpha -(1 -\log 2/\log 3)$.

From this theorem we obtain a simple relation between the effective and classical Hausdorff dimensions of this set; the difference is exactly $1$ minus the dimension of the Cantor set. We conclude that many points in the Cantor set additively cancel randomness.

On the surface, the theorem above describes a connection between algorithmic randomness and classical fractal geometry. Less obvious is its relationship to additive number theory. In 1954, G. G. Lorentz proved the following statement.

There exists a constant $c$ such that for any integer $k$, if $A\subseteq [0, k)$ is a set of integers with ${\left|A\right|} \geq \ell \geq 2$, then there exists a set of integers $B \subseteq (-k,k)$ such that $A + B \supseteq [0, k)$ with ${\left|B\right|} \leq ck\frac{\log \ell}{\ell}$.

Given a Martin-Löf random real $r$, I will show how Lorentz's Lemma can be used to identify a point $x\in\mathcal{C}$ such that the constructive dimension of $x+r$ is close to $1 - \log 2 / \log 3$, which is as small as it can possibly be.

This talk is based on joint work with Randy Dougherty, Jack Lutz, and Dan Mauldin.