Number of paths through infinite trees with given "growth rates"

Question

(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).

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.

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$?

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?

Answer 1

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

Answer 2

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.