On Measures of Size and Complexity
Introduction
People like to measure things. In mathematical analysis there is a notion of measure studied in Measure theory. In Topology we have a notion of topological dimension. In Information Theory we have a notion of entropy. In Computational Complexity Theory we have notions of time and space complexities. So the general idea is to quantify size or complexity of the given object. Then we can talk about whether this object is somehow bigger/more complex than the other object. In this post I would like to say few things about Hausdorff dimension.
Motivation
Why do we need Hausdorff dimension? There are many reasons. One of the reasons people talk most is its fineness. In other words Hausdorff measure can provide some meaningful information when Lebesgue measure gives none. To see that, observe that there are many sets of measure $0$. A single point is of measure $0$ and a Cantor space is of measure $0$. However, it is clear that those two are completely different objects. For this reason, we need some kind of refined tool. A Hausdorff dimension provides such kind of tool.
Definition
There are many resources discussing Hausdorff dimension in full generality such as Wikipedia and Terence Tao's blog. Since I am doing theory of computations, I want to focus in Hausdorff dimension [1] in the context of Cantor space. Let $\mathcal{C}$ denote a Cantor space, which is a collection of one-way infinite binary sequences. So, an element $\xi\in\mathcal{C}$ looks like:
\[
\xi = 1001011100101\ldots
\]
Given $\xi\in\mathcal{C}$, $Pref(\xi)$ denotes a set of its prefixes. For our given example, $Pref(\xi) = \{1,10,100,\ldots\}$. We can turn $\mathcal{C}$ into a metric space by defining a following metric:
\[
d(\xi,\zeta) = 2^{-p(\xi,\zeta)}
\]
where $p(\xi,\zeta)$ denotes a longest common prefix among given sequences. In formulas:
\[
p(\xi,\zeta) = \sup\{\vert w \vert : w\in Pref(\xi)\cap Pref(\zeta) \}
\]
Given any string $w$, we can define a basic open set $C_w$ associated with $w$:
\[
C_w = \{\xi\mid w\prec \xi \}
\]
In other words it is a collection of all sequences extending $w$. Given above metric, we can observe that the diameter of $C_w$ is exactly $2^{-\vert w \vert}$. Now we are ready to start measuring things. Let $X$ be any subset of $\mathcal{C}$. We say that $\{C_{w_i} \}_{i=1}^{\infty}$ is $\delta$-cover of $X$ if:
So it is exactly what its name suggests. Then we go on defining;
\[
\mathcal{H}_{\delta}^s = \inf\left\{\sum_{i=1}^{\infty} [d(C_{w_i})]^s\mid \{C_{w_i} \} \text{ is }\delta-\text{cover of }X\right\}
\]
Observe that $\mathcal{H}_{\delta}^s$ is a decreasing function of $\delta$. So we can define:
\[
\mathcal{H}^s(X) = \lim_{\delta\to\infty} \mathcal{H}_{\delta}^s(X)
\]
And finally we define Hausdorff dimension of $X$:
\[
dim_H(X) = \inf\{s\ge 0\mid \mathcal{H}^s(X)=0 \}
\]
Properties
Let us list some properties of Hausdorff dimension together with some discussions. Let $X$ be any subset of $\mathcal{C}$.
1. Behavior
If $\mathcal{H}^s(X)<\infty$ for some $s\ge 0$, then $\mathcal{H}^t(X) = 0 $ for any $t>s$.
Suppose that we given some $\delta$-cover of $X$. Observe that $d(C_w)^t \le \delta^{t-s} d(C_w)$, thus by letting $\delta\to 0$ we can have that $\mathcal{H}_0^t(X)=0$. Remembering that $\mathcal{H}_{\delta}^t(X)$ is descreasing in $\delta$, we verify this claim.
2. Relation with Lebesgue measure
If given $X$ of positive Lebesgue measure, then its Hausdorff dimension is $1$, i.e. $\lambda(X)>0 \Rightarrow dim_H(X)=1$.
Clearly we cannot have $dim_H(X)<1$. On the other hand, $\mathcal{H}^1(X)\ge 0$ and finite, showing that $dim_H(X)=1$.
3. Monotonicity
If $X\subset Y$ then $dim_H(X)\le dim_H(Y)$.
4. Stability
For $X,Y\subseteq \mathcal{C}$. we have:
\[
dim_H(X\cup Y) = \max\{dim_H(X),dim_H(Y) \}
\]
5. Countable stability
Let $\{X_i \}_{i=1}^{\infty}$ be a countable collection of subsets, also known as classes. Then we have:
\[
dim_H\left(\bigcup_{i=1}^{\infty}X_i\right) = \sup_{i}\{dim_H(X_i)\}
\]
6. Geometric invariance
Let $f:\mathcal{C}\to \mathcal{C}$ be a bi-Lipschitz transformation. In other words we have:
\[
c_1 d(\xi,\zeta) \le d(f(\xi),f(\zeta)) \le c_2 d(\xi,\zeta)
\]
for some $c_1,c_2>0$. Then we have:
\[
dim_H(X) = dim_H(f(X))
\]
7. Geometric properties under Hölder transformations.
Let $f:\mathcal{C}\to \mathcal{C}$ be a Hölder transformation. In other words, we have:
\[
d(f(\xi),f(\zeta)) \le cd(\xi,\zeta)^{\alpha}
\]
for some $c, \alpha>0$. Then we have:
\[
dim_H(f(X)) \le \left(\frac{1}{\alpha}\right)dim_H(X)
\]
Conclusion
Let us conclude our post here. We have gone through the definition of Hausdorff dimension in the context of Cantor space. Next, we could observe how functions called gales defined by Lutz [2] give rise the to exact same notion as above.
References:
1. Reimann, Jan, and Frank Stephan. "Effective Hausdorff dimension." Logic Colloquium. Vol. 1. 2005.
2. Lutz, Jack H. "The dimensions of individual strings and sequences." Information and Computation 187.1 (2003): 49-79.
People like to measure things. In mathematical analysis there is a notion of measure studied in Measure theory. In Topology we have a notion of topological dimension. In Information Theory we have a notion of entropy. In Computational Complexity Theory we have notions of time and space complexities. So the general idea is to quantify size or complexity of the given object. Then we can talk about whether this object is somehow bigger/more complex than the other object. In this post I would like to say few things about Hausdorff dimension.
Motivation
Why do we need Hausdorff dimension? There are many reasons. One of the reasons people talk most is its fineness. In other words Hausdorff measure can provide some meaningful information when Lebesgue measure gives none. To see that, observe that there are many sets of measure $0$. A single point is of measure $0$ and a Cantor space is of measure $0$. However, it is clear that those two are completely different objects. For this reason, we need some kind of refined tool. A Hausdorff dimension provides such kind of tool.
Definition
There are many resources discussing Hausdorff dimension in full generality such as Wikipedia and Terence Tao's blog. Since I am doing theory of computations, I want to focus in Hausdorff dimension [1] in the context of Cantor space. Let $\mathcal{C}$ denote a Cantor space, which is a collection of one-way infinite binary sequences. So, an element $\xi\in\mathcal{C}$ looks like:
\[
\xi = 1001011100101\ldots
\]
Given $\xi\in\mathcal{C}$, $Pref(\xi)$ denotes a set of its prefixes. For our given example, $Pref(\xi) = \{1,10,100,\ldots\}$. We can turn $\mathcal{C}$ into a metric space by defining a following metric:
\[
d(\xi,\zeta) = 2^{-p(\xi,\zeta)}
\]
where $p(\xi,\zeta)$ denotes a longest common prefix among given sequences. In formulas:
\[
p(\xi,\zeta) = \sup\{\vert w \vert : w\in Pref(\xi)\cap Pref(\zeta) \}
\]
Given any string $w$, we can define a basic open set $C_w$ associated with $w$:
\[
C_w = \{\xi\mid w\prec \xi \}
\]
In other words it is a collection of all sequences extending $w$. Given above metric, we can observe that the diameter of $C_w$ is exactly $2^{-\vert w \vert}$. Now we are ready to start measuring things. Let $X$ be any subset of $\mathcal{C}$. We say that $\{C_{w_i} \}_{i=1}^{\infty}$ is $\delta$-cover of $X$ if:
- $d(C_{w_i})\le \delta$ for all $i$, and
- $X\subseteq \bigcup_{i=1}^{\infty} C_{w_i}$
So it is exactly what its name suggests. Then we go on defining;
\[
\mathcal{H}_{\delta}^s = \inf\left\{\sum_{i=1}^{\infty} [d(C_{w_i})]^s\mid \{C_{w_i} \} \text{ is }\delta-\text{cover of }X\right\}
\]
Observe that $\mathcal{H}_{\delta}^s$ is a decreasing function of $\delta$. So we can define:
\[
\mathcal{H}^s(X) = \lim_{\delta\to\infty} \mathcal{H}_{\delta}^s(X)
\]
And finally we define Hausdorff dimension of $X$:
\[
dim_H(X) = \inf\{s\ge 0\mid \mathcal{H}^s(X)=0 \}
\]
Properties
Let us list some properties of Hausdorff dimension together with some discussions. Let $X$ be any subset of $\mathcal{C}$.
1. Behavior
If $\mathcal{H}^s(X)<\infty$ for some $s\ge 0$, then $\mathcal{H}^t(X) = 0 $ for any $t>s$.
Suppose that we given some $\delta$-cover of $X$. Observe that $d(C_w)^t \le \delta^{t-s} d(C_w)$, thus by letting $\delta\to 0$ we can have that $\mathcal{H}_0^t(X)=0$. Remembering that $\mathcal{H}_{\delta}^t(X)$ is descreasing in $\delta$, we verify this claim.
2. Relation with Lebesgue measure
If given $X$ of positive Lebesgue measure, then its Hausdorff dimension is $1$, i.e. $\lambda(X)>0 \Rightarrow dim_H(X)=1$.
Clearly we cannot have $dim_H(X)<1$. On the other hand, $\mathcal{H}^1(X)\ge 0$ and finite, showing that $dim_H(X)=1$.
3. Monotonicity
If $X\subset Y$ then $dim_H(X)\le dim_H(Y)$.
4. Stability
For $X,Y\subseteq \mathcal{C}$. we have:
\[
dim_H(X\cup Y) = \max\{dim_H(X),dim_H(Y) \}
\]
5. Countable stability
Let $\{X_i \}_{i=1}^{\infty}$ be a countable collection of subsets, also known as classes. Then we have:
\[
dim_H\left(\bigcup_{i=1}^{\infty}X_i\right) = \sup_{i}\{dim_H(X_i)\}
\]
6. Geometric invariance
Let $f:\mathcal{C}\to \mathcal{C}$ be a bi-Lipschitz transformation. In other words we have:
\[
c_1 d(\xi,\zeta) \le d(f(\xi),f(\zeta)) \le c_2 d(\xi,\zeta)
\]
for some $c_1,c_2>0$. Then we have:
\[
dim_H(X) = dim_H(f(X))
\]
7. Geometric properties under Hölder transformations.
Let $f:\mathcal{C}\to \mathcal{C}$ be a Hölder transformation. In other words, we have:
\[
d(f(\xi),f(\zeta)) \le cd(\xi,\zeta)^{\alpha}
\]
for some $c, \alpha>0$. Then we have:
\[
dim_H(f(X)) \le \left(\frac{1}{\alpha}\right)dim_H(X)
\]
Conclusion
Let us conclude our post here. We have gone through the definition of Hausdorff dimension in the context of Cantor space. Next, we could observe how functions called gales defined by Lutz [2] give rise the to exact same notion as above.
References:
1. Reimann, Jan, and Frank Stephan. "Effective Hausdorff dimension." Logic Colloquium. Vol. 1. 2005.
2. Lutz, Jack H. "The dimensions of individual strings and sequences." Information and Computation 187.1 (2003): 49-79.
Comments
Post a Comment