2
$\begingroup$

In this question it was established that if the growth of the number of branches of an at-most $k$-branching tree is $\Omega(k^n)$ (in the Knuth sense), then the tree has continuum many branches.

This can be interpreted as a statement about closed subsets of $k^\omega$ interpreted as a metric space with the a certain metric, i.e. the distance between two points is $2^{-n}$ where $n$ is the index of first disagreement. Specifically:

Given a closed set $F\subseteq k^\omega$, if $N_\varepsilon(F)\in\Omega \left(\varepsilon^{-\log_2 k}\right)$ (as $\varepsilon$ goes to 0), then $F$ has cardinality of the continuum,

where $N_\varepsilon$(A) here is the number of open balls needed to cover $F$. I don't think internal vs. external covering number matters here and any of the covering numbers mentioned in the Wikipedia article ought to work because of the inequalities relating them and the fact that we're requiring that $N_\varepsilon (F)$ be asymptotic to a power of $\varepsilon$. There's nothing special about $2$ and typically choosing $k$ would be 'more natural' but I wanted the example to have a non-trivial doubling dimension.

Alternatively you can just consider $F$ as a metric space on its own with the induced metric. This suggests an easy generalization of this to compact doubling ultrametric spaces, specifically:

Given a compact ultrametric space $X$ with doubling dimension $s$, if $N_\varepsilon(X)\in\Omega\left(\varepsilon^{-s}\right)$, then $X$ has cardinality of the continuum,

where $s$ is the least number such that every open $\varepsilon$-ball can be covered by at most $2^s$ open $\varepsilon/2$-balls. You can prove this by giving the open $2^{-n} \delta $-balls of $X$ a tree structure (for some $\delta>0$) and then relying on the result for discrete trees again. Then you argue that the choice of $\delta$ doesn't actually matter for the asymptotic behavior of $N_\varepsilon (X)$.


Generalizing any further seems unclear. The best I think I can do is in the case of totally disconnected compact metric spaces. You can consider the number of '$\varepsilon$-connected components':

  • A set $A$ is '$\varepsilon$-connected' (also called '$\varepsilon$-chainable') if for any two $x,y\in A$ there is a finite chain of points $\{z_i\}_{i=0}^n$ such that $x=z_0$, $y=z_n$, and $d(z_i,z_{i+1})<\varepsilon$ for each $i$.
  • The $\varepsilon$-connected component of a point $x$ is the union of all $\varepsilon$-connected sets containing $x$.
  • For any $\varepsilon>0$, a compact metric space admits a decomposition into a finite collection of disjoint $\varepsilon$-connected components.
  • Also the intersection of the $\varepsilon$-connected components of $x$ for all $\varepsilon>0$ is the topological connected component of $x$. In particular in a totally disconnected space it is just $\{x\}$. (Edit: This fact relies on compactness.)

I believe what you can say for a totally disconnected compact metric space is that if it has finite 'connected doubling dimension,' i.e. a uniform bound of $2^\ell$ on the number of $\varepsilon/2$-connected components of any $\varepsilon$-connected component of $X$, and if the number of $\varepsilon$-connected components is $\Omega(\varepsilon^{-\ell})$, then $X$ has cardinality of the continuum. The proof would work in exactly the same way as the ultrametric case, specifically the $2^{-n}\delta $-connected components have a natural tree structure whose infinite paths are precisely the points of $X$.

This is a direct generalization of the ultrametric case because the $\varepsilon$-connected components of a ultrametric space are its open $\varepsilon$-balls, but it's very unsatisfying because while you can upper bound the number of $\varepsilon$-connected components of a metric space with the open $\varepsilon$-covering number there's probably no nice way of lower bounding the number of $\varepsilon$-connected components without strong assumptions about the metric space (such as being an ultrametric space). Also it would be nice not to have to assume that the space is totally disconnected, but clearly the $\varepsilon$-connected component approach can fail when there are non-trivial connected components.


So my question is this: Is there a direct generalization of the 'large growth rate implies continuum size' results to arbitrary compact doubling metric spaces where the growth rate is measured in terms of covering numbers?

$\endgroup$
  • $\begingroup$ What if you take a countable (compact) subset of the unit interval with accumulation point at zero, and define $X_n$ by gluing a copy of that set on each axis in $\mathbb R^n$ so that the copies touch at the origin. As far as I understand the doubling constant of such a space should be essentially the same as for $\mathbb R^n$. $\endgroup$ – Teri Jun 1 '17 at 18:02
  • $\begingroup$ Yes but can you arrange it so that the covering numbers grow like $\varepsilon^{-n}$? $\endgroup$ – James Hanson Jun 1 '17 at 18:18
  • $\begingroup$ What about a space of the form $\{0\}\cup\{\frac1{\ln n}\}_{n=2}^\infty\subset\mathbb R$. It is doubling (being a subspace of $\mathbb R$) and has box-counting dimension 1, so the covering number has growth $\approx (1/\varepsilon)$. Yet $X$ is countable. $\endgroup$ – Taras Banakh Jan 28 '18 at 10:25
  • $\begingroup$ Does $X$ being a subspace of a doubling space guarantee that $X$ is a doubling space? The intersection of a ball in $\mathbb{R}$ with $X$ isn't always a ball in $X$. $\endgroup$ – James Hanson Jan 29 '18 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.