10
$\begingroup$

(Preface: This may be a naive or easy question for experts....)

Consider an infinite tree, rooted on the left, where each node has two children; the number of nodes at each level (distance from the root) $n$ is $f(n) = 2^n$. The number of paths is $2^{\omega}$, the cardinality of the continuum (uncountable). Infinite tree with "growth rate" 2^n

Now consider a similar tree where only one node at each level has an extra child; the number of nodes at each level $n$ is $f(n) = n+1$. In this case, the number of paths is $\omega$; the paths here are countable. Infinite tree with linear "growth rate"

My question is, what happens in between? I would formalize the setting as follows (but maybe I have some details wrong): Suppose I have an infinite rooted tree, where each node has at least one child, and the number of nodes at distance $n$ from the root is $f(n)$ where $n \leq f(n) \leq 2^n$. Then what can we say about the number of paths in terms of the "growth rate" $f$?

Infinite tree with "growth rate" f(n)

For example, if the "growth rate" is polynomial, must there be a countable number of paths? Are there growth rate functions for which the cardinality of the number of paths is independent of ZFC, i.e. depends on the continuum hypothesis? Any other notes/comments?

$\endgroup$
  • 7
    $\begingroup$ The growth rate by itself doesn’t determine the number of paths. You can easily construct a tree with growth rate $f(n)=n+1$ and $2^\omega$ paths by choosing more liberally who gets the new child at each level. $\endgroup$ – Emil Jeřábek supports Monica Nov 6 '14 at 22:16
  • 4
    $\begingroup$ Also, I’m not sure how you intended the reference to the continuum hypothesis, but anyway the number of paths in any such tree is either countable or $2^\omega$ by the Cantor–Bendixson theorem. $\endgroup$ – Emil Jeřábek supports Monica Nov 6 '14 at 22:28
  • 2
    $\begingroup$ Another way to phrase Emil Jeřábek's first comment is that for any growth function $f$, there is a contracting homotopy from a "stretched" tree, given by inserting vertices of degree 2 so that only one branch appears at each level, that induces a bijection on the set of infinite paths. $\endgroup$ – S. Carnahan Nov 6 '14 at 22:31
  • 3
    $\begingroup$ The comments are correct, but there are some positive things to say, aren't there? For example, very high growth rate, near $2^n$, seems to force the tree to have $2^\omega$ many branches. We can interpret the question as: what can one say about sufficient rates of growth to ensure continuum many branches? For example, probably even superpolynomial growth does not suffice? $\endgroup$ – Joel David Hamkins Nov 6 '14 at 22:55
  • $\begingroup$ That’s right. I didn’t intend my comments to be positive or negative, but rather to make the OP think more about the question and clarify what he or she really wants. $\endgroup$ – Emil Jeřábek supports Monica Nov 6 '14 at 23:08
13
$\begingroup$

On the one hand, the comments explain that a low-growth-rate tree can still have continuum many branches. Indeed, the growth rate can be extremely slow, with most levels having no splitting at all, but then every once in a very long while, a single node splits. Just make sure at the $k^{th}$ such splitting that you are splitting at a node above the $k^{th}$ binary sequence of the tree (in some fixed standard enumeration of all finite binary sequences), and then the resulting tree $T$ will have the property that every node lies below a splitting node. This property will ensure a subtree of type $2^{<\omega}$, and hence give you continuum many branches.

In contrast, it is the converse question that I find extremely interesting, and which could be considered the real content of your question. Namely,

Question. What is a sufficient growth rate on the tree $T$ to ensure that it has continuum many branches?

The answer is that the growth rate must be essentially close to $2^n$, in the precise senses described by the following theorems. On the one hand, such a high growth rate suffices for continuum many paths:

Theorem. If $T\subset 2^{<\omega}$ is a binary tree with growth rate $\Omega(2^n)$ (in the Knuth sense big-Omega notation), then $T$ has continuum many branches.

Proof. What I intend to assume on the growth rate is that is that there is a positive real number $r>0$ such that the number of nodes on the $n^{th}$ level of $T$ is at least $r2^n$. Thus, the complement of the set of paths through $T$ is approximated by the unions of the cones above the omitted nodes on this level, and this has measure at most $1-r$ with respect to the usual coin-flipping probability measure on Cantor space. Since this is true at each level, it follows that the measure of the paths through $T$ is at least $r$, which is positive, and so there must be uncountably many paths through $T$. Since this is a closed set, it follows by the Cantor-Bendixson theorem that $T$ has continuum many paths. QED

On the other hand, any lower growth rate does not ensure continuum many paths.

Theorem. If $f:\mathbb{N}\to\mathbb{N}$ is in $o(2^n)$ (see little-o notation), then there is a tree $T$ with growth rate exceeding $f$, but having only countably many paths.

Proof. The growth rate assumption is that for every $r>0$, it will be true for large enough $n$ that $f(n)<r2^n$.

Let me describe a general procedure for building a tree $T$ with a very high growth rate, but with only countably many branches. We build $T$ in stages. First, we let $T$ use the full binary branching up to some level $n_0$. Then, at this stage, we kill off the future growth of half the branches, the ones beginning with $0$, forcing them to become isolated branches in the tree starting at level $n_0$, continued only with more $0$s after $n_0$. Meanwhile, we let the other "live" nodes, those having $1$ in their first bit, to continue splitting above $n_0$ until some much larger stage $n_1$. At that level, we again kill off half of them. Namely, any node beginning with $10$ will become isolated at $n_1$, and the others, beginning with $11$, will continue splitting up until the very much later stage $n_2$. And so on.

The general procedure is: at level $n_k$, the nodes beginning with $1^k0$ will become isolated at level $n_k$ (which is much larger than $k$), and the nodes beginning with $1^k$ are allowed to continue branching up to level $n_{k+1}$.

The resulting tree $T$ will have only countably many branches, since the only branches will be the isolated branches that we forced to occur, plus the all $11111\cdots$ branch, since whenever a sequence has its first $0$ in position $k$, it will become isolated at level $n_k$.

But now, the main point, is that by choosing the levels $n_0<n_1<n_2<\cdots$ to be very fast growing, we can ensure a growth rate exceeding $f$. Specifically, since $f$ is $o(2^n)$, there is for each $k$ a number $n_k$ such that $f(n)<2^{n-k}$ for all $n\geq n_k$, and we may also assume $n_0<n_1<n_2<\cdots$. Now, with the $T$ as defined above, it follows that the number of nodes of $T$ on level $n_k$ is at least $2^{n_k-k}$, and it remains at least $2^{n-k}$ for $n_k\leq n<n_{k+1}$, and this is larger than $f(n)$, as desired. So the growth rate of $T$ is at least $f$, even though $T$ has only countably many paths. QED

$\endgroup$
  • 1
    $\begingroup$ There is an unsettled middle ground for growth rates between $o(2^n)$ and $\Omega(2^n)$, and it isn't clear to me what is going on there. $\endgroup$ – Joel David Hamkins Nov 7 '14 at 2:15
  • 3
    $\begingroup$ There is an assumption in your first theorem that is not present in the question. Your assumption that there are at most $2$ children of each node makes the question more interesting. Without this, it might be that only the first node has multiple children, in which case the number of branches is countable. $\endgroup$ – Douglas Zare Nov 7 '14 at 7:52
  • 1
    $\begingroup$ Yes, I agree. But there is an analogous result, however, for at-most $d$-branching trees $T\subset d^{<\omega}$, using $d^n$ in place of $2^n$. $\endgroup$ – Joel David Hamkins Nov 7 '14 at 11:31
6
$\begingroup$

As explained in the various comments,

  • every tree has countably many or $2^\omega$ branches,

  • there are trees with $2^\omega$ branches of any unbounded admissible growth rate $f(n)$, and

  • if nodes can have arbitrarily many children, there are countable trees of arbitrary growth rate.

As Joel already mentioned, the question that remains is for which growth rates $f(n)$ there exist trees with countably many branches where every node has one or two children. (Below, I will assume the latter condition automatically, and call them just “trees”.)

Now, even for this question, the absolute growth rate is largely irrelevant, what really matters is how $f(n+1)$ relates to $f(n)$, as demonstrated by the following example.

First, let me define for convenience that $f\colon\mathbb N\to\mathbb N$ is admissible if there exists a tree of growth rate $f(n)$. This is equivalent to the conditions

  • $f(0)=1$,

  • $f(n)\le f(n+1)\le2f(n)$ for every $n\in\mathbb N$.

The question also demands $f(n)\ge n$, but as Joel notes, this has no good reason, so I will state this explicitly where intended.

Example:

  1. For every function $g\colon\mathbb N\to\mathbb N^{>0}$ such that $\lim_ng(n)=+\infty$, there is an admissible function $f(n)\le g(n)$ such that every tree of growth rate $f(n)$ has $2^\omega$ branches.

  2. There is an admissible function $f$ such that $n\le f(n)\le2n$ for $n>0$, and every tree of growth rate $f(n)$ has $2^\omega$ branches.

Proof: For 1, we can choose an infinite sequence $0=n_0<n_1<n_2<\dots$ such that $g(n)\ge2^k$ for every $n\ge n_k$, and define $$f(n)=2^k\text{ for }n_k\le n<n_{k+1}.$$ If $T$ is a tree of growth rate $f(n)$, all nodes at levels $n_k-1$ split, hence $T$ has $2^\omega$ branches.

The argument for 2 is similar: we fix a sequence $n_0,n_1,\dots$ such that $2n_k<n_{k+1}$ for every $k$, and put $$f(n)=\begin{cases}n&n\le n_0\text{ or }2n_k\le n\le n_{k+1},\\ 2n_k&n_k<n\le2n_k.\end{cases}$$ Again, all nodes at levels $n_k$ split.


It is in fact possible to characterize exactly what growth rates allow for trees with countably many branches.

If $f$ is an admissible function, put $$d(n)=2f(n)-f(n+1).$$ Note that $0\le d(n)\le f(n)$. If $T$ is a tree of growth rate $f$, then $d(n)$ counts the number of nodes at level $n$ that do not split.

A moment’s reflection reveals that if we want a tree of fixed growth rate to have as few branches as possible, we should try to put all splitting nodes on one side. With this in mind, define a tree $T_f$ of growth rate $f(n)$ as follows. The nodes at each level $n$ are numbered $1,\dots,f(n)$. Nodes $1,\dots,d(n)$ have one child each on level $n+1$, with the same number. Nodes $d(n)+1,\dots,f(n)$ have two children each, again numbered in the same fashion: that is, node $i>d(n)$ has children $2i-1-d(n)$ and $2i-d(n)$.

Theorem: For any admissible function $f$, the following are equivalent.

  1. All trees of growth rate $f$ have $2^\omega$ branches.

  2. $T_f$ has $2^\omega$ branches.

  3. There are $n_0\le n_1<n_2<n_3<\cdots$ such that $$\sum_{k=1}^\infty2^{-k}d(n_k)\le f(n_0)-1.$$

  4. There are $n_1<n_2<n_3<\cdots$ such that $$\sum_{k=1}^\infty2^{-k}d(n_k)<1.$$

Proof:

$1\to2$ is trivial.

$2\to3$: If $b$ is a branch in $T_f$, let $b(n)$ denote the number of the node of $b$ at level $n$. We observe that $b(n)$ is nondecreasing. If $b'(n_0)<b(n_0)$, then $b'(n)<b(n)$ for all $n\ge n_0$. If $b$ does not split after level $n$, then neither does any branch $b'$ below it; thus $b$ is isolated if and only if $b(n)$ is eventually constant. Let $b_m$ be the branch which goes through node $f(m)-1$ at level $m$, and then follows the higher child at each level where it splits. Every branch of $T$ except the topmost one is bounded above by some $b_m$, thus if every $b_m$ were eventually constant, all but one branch would be isolated, and the number of branches would be countable. Thus, let us fix $n_0$ such that $b:=b_{n_0}$ is not eventually constant.

We can compute $b(n)$ by an explicit recurrence: \begin{align} b(n_0)&=f(n_0)-1,\\ b(n+1)&=b(n)+\max\{0,b(n)-d(n)\} \end{align} for $n\ge n_0$. Since $b$ is not eventually constant, we have $b(n)>d(n)$ for infinitely many $n\ge n_0$; let us enumerate them as $n_1<n_2<\cdots$. Unwinding the recurrence, we see that $$b(n)=2^m(f(n_0)-1)-2^{m-1}d(n_1)-2^{m-2}d(n_2)-\dots-d(n_m)\qquad\text{for }n_m<n\le n_{m+1}.$$ Since $b(n)\ge0$, we obtain $$f(n_0)-1\ge\sum_{k=1}^m2^{-k}d(n_k)$$ for every $m$, which implies 3 in the limit.

$3\to4$: We have $$f(n_0)=2^{n_0}-2^{n_0-1}d(0)-2^{n_0-2}d(1)-\dots-d(n_0-1),$$ hence if we put $$n'_k=\begin{cases}k&k<n_0,\\n_{k+1-n_0}&\text{otherwise,}\end{cases}$$ we obtain $$1>1-2^{-n_0}\ge\sum_{k=1}^\infty2^{-k}d(n'_k).$$

$4\to1$:$\let\res\restriction\let\sset\subseteq\let\Sset\supseteq $ Let $T$ be a subtree of $2^{<\omega}$ of growth rate $f(n)$, $[T]\sset2^\omega$ the set of its branches, and $T_1\sset T$ the set of nonsplitting nodes of $T$. For any $b\in[T]\cup T$, let $B(b)\sset\mathbb N$ denote the set of levels on which $b$ goes through a splitting point of $T$. $b\res n\in2^n$ denotes the restriction of $b$ to the first $n$ levels.

We consider a probability measure on Borel subsets of $2^\omega$ defined by $$\Pr_{\sigma\in2^\omega}(\sigma\Sset t)=\begin{cases}2^{-|B(t)|}&t\in T\\0&\text{otherwise}\end{cases}$$ for $t\in2^{<\omega}$. That is, $[T]$ has measure 1, and if $t\in T\smallsetminus T_1$, the measure of the set of all branches going through $t$ is split evenly between the two children of $t$.

Claim: If $b\in[T]$, we have $$\Pr_\sigma(\sigma=b)\le\sum_{k:b\res n_k\in T_1}2^{-k}\Pr_\sigma(\sigma=b\mid\sigma\Sset b\res n_k).$$

Proof: We can assume wlog $\Pr(\sigma=b)>0$, which implies that $b$ is isolated. Let $k_1<k_2<\cdots$ be the enumeration of all $k$ such that $b\res n_k\in T_1$. Then \begin{multline} \frac1{\Pr(\sigma=b)}\sum_{k:b\res n_k\in T_1}2^{-k}\Pr_\sigma(\sigma=b\mid\sigma\Sset b\res n_k)=\sum_{j=1}^\infty\frac1{2^{k_j}\Pr(\sigma\Sset b\res n_{k_j})}\\=\sum_{j=1}^\infty2^{-k_j}2^{|B(b)\cap\{0,\dots,n_{k_j}-1\}|}\ge\sum_{j=1}^\infty2^{-k_j}2^{k_j-j}=1. \end{multline}

Now, assume for contradiction that $[T]$ is countable. Using countable additivity of the measure, and the claim, we obtain \begin{multline} 1>\sum_{k=1}^\infty2^{-k}d(n_k)=\sum_k\sum_{t\in T_1\cap2^{n_k}}2^{-k}\ge\sum_k\sum_{t\in T_1\cap2^{n_k}}2^{-k}\sum_{b\Sset t}\Pr_\sigma(\sigma=b\mid\sigma\Sset t)\\=\sum_{b\in[T]}\sum_{k:b\res n_k\in T_1}2^{-k}\Pr_\sigma(\sigma=b\mid\sigma\Sset b\res n_k)\ge\sum_{b\in[T]}\Pr_\sigma(\sigma=b)=1, \end{multline} a contradiction.

$\endgroup$
  • $\begingroup$ +1. It is interesting that any tree with growth rate exactly $f_A$ has continuum many branches, but the construction in my answer provides trees with growth rate exceeding $f_A$ (provided $A$ is co-infinite) with only countably many branches. So a tree can have a higher growth rate, but fewer branches. $\endgroup$ – Joel David Hamkins Nov 7 '14 at 12:20
  • $\begingroup$ It also seems natural to define $f_A(n+1)=f_A(n)$ in your second case, rather than $f_A(n)+1$ as you have done. This gets the same effect, but now the point is that the tree would have full splitting at levels $n\in A$, and no splitting at levels not in $A$. $\endgroup$ – Joel David Hamkins Nov 7 '14 at 12:27
  • $\begingroup$ Yes, $f(n+1)=f(n)$ works just the same, it’s just that I was under the unwarranted impression that the question insisted on $f(n+1)>f(n)$. $\endgroup$ – Emil Jeřábek supports Monica Nov 7 '14 at 15:01
  • $\begingroup$ I don’t have the time to think more about it at the moment, but it seems to me that the right parameter that decides whether there are countable trees should be something in the spirit of $\limsup_{n\to\infty}\frac{f(n+1)}{f(n)}$. $\endgroup$ – Emil Jeřábek supports Monica Nov 7 '14 at 15:03
  • $\begingroup$ Hmm. At the very least $\liminf_n2f(n)-f(n+1)<+\infty$ guarantees that the tree has $2^\omega$ paths (as the liminf bounds the number of isolated paths), but this is clearly too strong a condition. $\endgroup$ – Emil Jeřábek supports Monica Nov 7 '14 at 15:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.