Article: Dynamical covering sets

A few days ago, I uploaded a joint article with Balazs Barany and Henna Koivusalo to arXiv. The article is called Dynamical covering sets in self-similar sets and I will briefly summarise the paper here.

TLDR: Imagine you are trying to cover the circle $\mathbb{S}^1$ with randomly centred balls $B(x_k,r_k)$, where $x_k$ is distributed uniformly on $\mathbb{S}^1$ and $r_k$ is a decreasing sequence. The Dvoretzky covering question¹ asks for conditions on $r_k$ for the whole circle to be covered almost surely. Similarly, one can ask for when the cover is of full measure, or what size the covering set is.

In this article, we study an analogous dynamical problem for symbolic balls (cylinders) in self-similar sets, where we pick our initial point according to Bernoulli measures. We obtain a single pressure formula that describes the entire dimension theory, which shows distinct regions to the (known) homogeneous case.

IFS and Dynamical Covers

An iterated function system (IFS) is a finite collection of contractive maps $\lbrace f_1,\dots,f_N\rbrace$, whose unique non-empty compact attractor $\Lambda\subset\mathbb R^d$ satisfies

$$ \Lambda = \bigcup_{i=1}^N f_i(\Lambda). $$

When the $f_i$ are similitudes, $\Lambda$ is called self-similar and if the images of $f_i$ are suitably separated, the Hausdorff dimension $s_0$ of $\Lambda$ is given by
$$ \sum_{i=1}^N \lambda_i^{s_0} = 1, $$ where $\lambda_i\in(0,1)$ is the contraction ratio of $f_i$².

There is a natural expanding map $T\colon\Lambda\to\Lambda$ given locally by choosing the inverse branch of some $f_i$. Under separation hypotheses, $T$ is topologically conjugate to the left-shift $\sigma$ on the symbolic space $\Sigma=\lbrace 1,\dots,N\rbrace^\mathbb N$.

In dynamics one often studies shrinking-target problems: given a sequence of targets $A_n\subset X$, one asks for the size of

$$ R_{st} = \lbrace x \in X \mid T^n(x)\in A_n\text{ infinitely often}\rbrace = \limsup_{n\to\infty}T^{-n}(A_n). $$ and its Hausdorff dimension is known in many settings, see e.g. Hill and Velani³.

Here we replace arbitrary targets by symbolic cylinders that are moved by the left shift and are shrinking at a prescribed rate. Fix a coding $\omega\in\Sigma$ and an increasing $\ell\colon\mathbb N\to\mathbb N$ with

$$ \liminf_{n\to\infty}\frac{\ell(n)}{\log n}=\frac1\alpha. $$

Define the dynamical covering set

$$ R(\omega,\ell) = \pi\Bigl\lbrace i\in\Sigma \mid i\in[(\sigma^n\omega)]_{\ell(n)}\text{ infinitely often}\Bigr\rbrace, $$

where $\pi\colon\Sigma\to\Lambda$ is the coding map. Equivalently one may view this as

$$ \lbrace x\in\Lambda \mid x\in B(T^n(\pi(\omega)), \lambda_{(\sigma^n\omega)_{\ell(n)}})\text{ infinitely often}\rbrace. $$

It is the set of all points that get covered infinitely often by neighbourhoods of the orbit of $\omega$, where the size shrinks with respect to the self-similar contraction rate.

The result

Let $p=(p_1,\dots,p_N)$ be a probability vector (all $p_i>0$), and let $\mathbb P_p$ be the corresponding Bernoulli measure on $\Sigma$. Write $s(\alpha)$ for the almost-sure Hausdorff dimension of $R(\omega,\ell)$. We choose our initial starting position $\omega$ with respect to $\mathbb{P}_p$ and consider the associated random covering set. We get:

Theorem 1.
For $\mathbb P_p$-almost every $\omega$,

$$ \dim_H R(\omega,\ell) = s(\alpha), $$

where $s(\alpha)$ is the unique solution of the variational-pressure equation

$$ s(\alpha) = \inf_{q\in[0,1]} \Bigl\lbrace P_\alpha(q)\colon\sum_{i=1}^N \lambda_i^{P_\alpha(q)}(p_i e^{\alpha})^q = 1\Bigr\rbrace. $$

Moreover, writing $s_0=\dim_H\Lambda$, $p_{\min}=\min_i p_i$, then almost surely:

1. If $\alpha>-\log p_{\min}$, then $R(\omega,\ell)=\Lambda$.
2. If $-\sum_i\lambda_i^{s_0}\log p_i<\alpha<-\log p_{\min}$, then $R(\omega,\ell)$ has full $\mathcal H^{s_0}$-measure but is not the whole set.

We can also describe the sizes of the complement $\dim_H\bigl(R(\omega,\ell)^c\bigr)$ through a similar optimisation over negative $q$.

It is worth noting that the homogeneous case when all $\lambda_i$ agree had previously been studied by Liao and Seuret ⁴. In their results, the dimension behaviour was classified as three distinct regions:

1. A linear regime: for $\alpha<\dim_H \mathbb{P}_p$ the dimension of $R(\omega,\ell)$ is linear in $\alpha$.
2. A concave regime: Once the dimension reaches the dimension of the measure, for $\dim_H \mathbb{P}_p\le \alpha$ the dimension follows the multifractal spectrum of the measure $\mathbb{P}_p$.
3. Finally, once the spectrum is maximal, the dimension of the set remains maximal.

As it turns out, this is a special case of the pressure formula that we are observing above. The optimisation turns out to be the Lgendre transform of the $L^q$ dimension of the measure for the appropriate region, resulting in the same result. However, in our general set up, the initial regime is typically strictly convex and the optimisation is over those self-similar measures that “see” the returns to the centre.

Surprisingly, we can also classify our result in terms of a different pressure. It is the unique $s$ such that $$ \limsup_{n\to\infty} \frac{1}{n}\log \sum_{|\overline{j}|=n} \lambda_{\overline{j}}^s \big(1-(1-p_{\overline{j}})^{e^{\alpha n}}\big) = 0. $$ This pressure captures the heuristic well. The number of indices where we can see blocks of length $l(n)$ is approximately $e^{\alpha n}$. So, there are $\tfrac{1}{n}e^{\alpha n}\sim e^{\alpha n}$ possible “independent” trials where we can see a coding reappear. The probability that this happens at least once is $\big(1-(1-p_{\overline{j}})^{e^{\alpha n}}\big)$ and weighting this by the relative size of that coding, gives rise to the pressure above. It is not at all obvious that this pressure should give the right answer over the entire range of $\alpha$.

Finally, most of the technical challenge of the paper is the lower bound for the low $\alpha$ regime. Here we construct, as is typical, a random Cantor set to give the lower bound. However, the construction is rather delicate and requires various intricate martingale-type arguments. You have been warned.

Miscellaneous & Trivia

Balazs gave a talk at a OWF meeting on this article, which can be watched on YouTube.

This article is also a good motivator for resilience. We started on this project in February 2020 only weeks before the pandemic and lockdown. At the time, Henna and I were based in Vienna and with the lockdowns, the project was put on hold for a while. We picked it up regularly through visits and in the meantime Henna moved to Bristol, I moved to Oulu and later Uppsala. As such, the research received varied funding. From a collaborative grant of Aktion Österreich Ungarn for projects between University of Vienna and BME Budapest, to FWF and MSCA grants I held from 2020 to 2024, as well as Balazs’s research funding from the NKFIH. I also gave various talks on the topic in Bristol and Oulu at in-between stages of this project and much of what I said was probably wrong!

References