11 Dimension[0YH]

Let \((X,d)\) be a metric space. Let in the following \(K\) a compact non-empty subset of \(X\), and \(N(𝜌)\) the minimum number of balls of radius \(𝜌\) that are needed to cover \(K\).  ¹

If the limit does not exist, we can still use the limsup and the liminf to define the upper and lower dimension.

Note that this definition depends a priori on the choice of the distance, i.e. \(N=N(𝜌,K,d)\) and \(\dim =\dim (K,d)\). See in particular 317.

E316

[0YK]Show that \(N(𝜌)\) is decreasing as a function of \(𝜌\). [UNACCESSIBLE UUID ’0YM’]

[0YN] Prerequisites: 4.Difficulty:*.Show that \(N(𝜌)\) is bounded if and only if \(K\) contains only a finite number of points. Hidden solution: [UNACCESSIBLE UUID ’0YP’] So if \(K\) is infinite, then \(\lim _{𝜌→ 0+}N(𝜌)=∞\). [0YQ] Let \(N'(𝜌)\) be the minimum number of balls, with radius \(𝜌\) and centered in \(K\), that are necessary to cover \(K\): then

So the dimension does not change if you require the balls to be centered at points of \(K\). Hidden solution: [UNACCESSIBLE UUID ’0YR’] [0YS] Let \(P(𝜌)\) be the maximum number of balls, with radius \(𝜌\) and centered in \(K\), that are disjoint. Show that

So the dimension can also be calculated as

Such a construction is known as ball packing. Hidden solution: [UNACCESSIBLE UUID ’0YT’] [0YV] In the exercise 1 it is important to require that the balls are centered in points of \(K\). Find an example of metric space \((X,d)\) and compact \(K⊆ X\) of finite dimension, but such that, for every \(n∈ℕ\) and every \(𝜌{\gt}0\), there are infinite disjoint balls each containing only one point of \(K\).

Hidden solution: [UNACCESSIBLE UUID ’0YW’] [0YX] Show that the dimension does not change if you use disks

instead of balls \(B(x,r)\). Hidden solution: [UNACCESSIBLE UUID ’0YY’] [0YZ] Prerequisites:5.Let \(K⊆ X\) compact; fix \(𝛼{\gt}1\); define \(\tilde d(x,y)=\sqrt[𝛼]{d(x,y)}\). We know from 5 that it is a distance. Show that

In particular \(K=[0,1]\) (the interval \(K⊆ X=ℝ\)) with the distance \(\tilde d(x,y)=\sqrt[𝛼]{|x-y|}\) has dimension \(𝛼\).

Hidden solution: [UNACCESSIBLE UUID ’0Z0’] [0Z1] Topics:norm.Prerequisites:325.

Let \(K\) be a compact in \(ℝ^ n\); we write \(\dim (K,|⋅|)\) to denote the limit that defines the dimension, using the balls of the Euclidean norm. Given a norm \(𝜙\) we can define the distance \(d(x,y)=𝜙(x-y)\), and with this calculate the dimension \(\dim (K,𝜙)\). Show that \(\dim (K,|⋅|)=\dim (K,𝜙)\), in the sense that, if one limit exists, then the other limit exists, and they are equal. Hidden solution: [UNACCESSIBLE UUID ’0Z2’] [0Z3] We indicate an operating policy that can be used in the following exercises.

• If there is a descending sequence \(𝜌_ j→ 0\) and \(h_ j\) positive such that \(h_ j\) balls of radious \(𝜌_ j\) are enough to cover \(K\), then

  \begin{equation} \limsup _{𝜌→ 0+}\frac{\log N(𝜌)}{\log (1/𝜌)} ≤ \limsup _{j→ ∞}\frac{\log h_{j+1}}{\log (1/𝜌_ j)}~ ~ .\label{eq:dimens_ sup_ per_ copertura} \end{equation}

  318

• If, on the other hand, there is a descending sequence \(r_ j→ 0\), and \(C_ n⊆ K\) finite families of points that are at least distant \(r_ j\) from each other, i.e. for which

  \begin{equation} ∀ x,y∈ C_ n,x≠ y ⇒ d(x,y)≥ r_ j~ ,\label{eq:punti_ sparpagliati} \end{equation}

  319

  then 

  \begin{equation} \liminf _{𝜌→ 0+}\frac{\log N(𝜌)}{\log (1/𝜌)} ≥ \liminf _{j→ ∞}\frac{\log l_ j}{\log (1/r_{j+1})}~ ~ . \label{eq:dimens_ inf_ per_ sparpagl} \end{equation}

  320

  where \(l_ j=|C_ j|\) is the cardinality of \(C_ j\). Note that the points of \(x∈ C_ j\) are centers of disjoint balls \(B(x,r_ j/2)\), therefore \(l_ j≤ P(r_ j/2)\), as defined in 1.

In particular, if

then the set \(K\) has dimension \(𝛽\).

[UNACCESSIBLE UUID ’0Z4’] Hidden solution: [UNACCESSIBLE UUID ’0Z5’][UNACCESSIBLE UUID ’0Z6’] [0Z7]Prerequisites: 333 317 317.Difficulty:*.Let \(K⊆ ℝ^ m\) compact. Consider the family of closed cubes with edge length \(2^{-n}\) and centers at the grid points \(2^{-n}ℤ^ m\). We call it ”n-tessellation”. Let \(N_ n\) be the number of cubes of the n-tessellation intersecting \(K\). Show that \(N_ n\) is weakly increasing. Show that the following limit exists

if and only if the limit ?? (that defines the dimension) exists. Show that, when they both exist, they coincide. This approach to computing the dimension is called Box Dimension.

Hidden solution: [UNACCESSIBLE UUID ’0Z8’][UNACCESSIBLE UUID ’0Z9’]

These quantities have an interpretation in rate-distortion theory. ”\(n\)” is the position of the last significant digit (in base 2) in determining the position of a point \(x\). ”\(\log _ 2 N_ n\)” is the number of ”bits” needed to identify any \(x∈ K\) with such precision. [0ZB]Let \(a_ n\) be an infinitesimal decreasing positive sequence. Let \(K⊆ ℝ\) given by

note that it is compact. Study the dimension of \(K\) in these cases:

• \(a_ n=n^{-𝜃}\) with \(𝜃{\gt}0\);

• \(a_ n=𝜃^{-n}\) with \(𝜃{\gt}1\).

Hidden solution: [UNACCESSIBLE UUID ’0ZC’] [0ZD]Let \(1≤ d≤ n\) be integers. Let \([0,1]^ d\) be a cube of dimension \(d\), we see it as a subset of \(ℝ^ n\) by defining

namely

Show that the dimension of \(K\) is \(d\).

Hidden solution: [UNACCESSIBLE UUID ’0ZF’] [0ZG] Show that the dimension of the (image of) Koch curve is \(\log 4/\log 3\). (See for example [ 58 ] for the definition).

Hidden solution: [UNACCESSIBLE UUID ’0ZH’] [0ZJ]Show that the dimension of the Cantor set is \(\log (2)/\log (3)\).

Hidden solution: [UNACCESSIBLE UUID ’0ZK’] [0ZM]Prerequisites:349,2.Inside the Banach space \(X=C^ 0([0,a])\) endowed with the norm \(‖⋅ ‖_∞\) we consider

where \(L{\gt}0,a{\gt}0\) are fixed.

Estimate \(N(𝜌)\) for \(𝜌→ 0\) [UNACCESSIBLE UUID ’0ZN’] [0ZP]Topics:ultrametric.Prerequisites:304.

Fix \(𝜆{\gt}0\). We define the ultrametric space of sequences as in Sec. ??: let \(I\) be a finite set, of cardinality \(p\); let \(X=I^ℕ\) be the space of sequences; define \(c\) as in eqn. ??; define \(d(x,y)=𝜆^{-c(x,y)}\). We know from exercises 3 and 306 that \((X,d)\) is compact.

Show that the dimension of \((X,d)\) is \(\log p/\log 𝜆\).

Hidden solution: [UNACCESSIBLE UUID ’0ZQ’] [0ZR]Difficulty:*.Describe a compact set \(K⊂ ℝ\) for which the limit ?? does not exist.

[UNACCESSIBLE UUID ’0ZS’]