Infinite constant gap length trees in products of thick Cantor sets

Abstract

We show that products of sufficiently thick Cantor sets generate trees in the plane with constant distance between adjacent vertices. Moreover, we prove that the set of choices for this distance has non-empty interior. We allow our trees to be countably infinite, which further distinguishes this work from previous results on patterns in fractal sets. This builds on the authors’ previous work on graphs and distance sets over products of Cantor sets of sufficient Newhouse thickness.

1. Introduction

The study of finite point configurations within sets satisfying certain size conditions is a classic subject matter. The basic problem is to determine minimal size conditions satisfied by a subset of Euclidean space that guarantee the existence or abundance of various finite point configurations within the set. For subsets of the integers, size is quantified using cardinality or density. For instance, in [24] Ziegler showed that one can recover every simplex similarity type and all sufficiently large scalings inside subsets of $ {\mathbb {R}}^d$ of positive upper density. Her result builds on previous work by Furstenberg, Katznelson, and Weiss on configurations in sets of positive density [3]. In the continuous setting, it is a consequence of the Lebesgue density theorem that subsets of $ {\mathbb {R}}^n$ of positive Lebesgue measure contain a translated and scaled copy of every finite point set for an interval worth of scalings [18].

In the fractal setting, the size of a set may be quantified by notions of dimension, such as Hausdorff dimension. A number of works have appeared guaranteeing the existence [2, 10, 11] or abundance [4–8, 14] of certain point configurations within sets satisfying sufficient dimensional assumptions. In [1], Bennett, Iosevich, and the second listed author establish that a set of sufficiently large Hausdorff dimension contains arbitrarily long chains with vertices in the set. In more detail, define the set of $k$-chains of distances determined by a set $E$ by

(1.1)\begin{equation} \{(|x^1-x^2|,\ldots,|x^k-x^{k+1}|)\in {\mathbb{R}}^k:x^i\in E \text{ distinct}\}. \end{equation}

It is established in [1] that if the Hausdorff dimension of $E$ is greater than ${d+1}/{2}$, then the above set has non-empty interior in $ {\mathbb {R}}^k$. We refer to such a result as an abundance result, as it gives dimensional assumptions that guarantee the abundance of chains within a set. Moreover, the authors of [1] prove if the Hausdorff dimension of a set $E\subset {\mathbb {R}}^d$ is greater than ${d+1}/{2}$, then for each $k\in {\mathbb {N}}$, there exists a non-empty open interval $I$ so that for each $t\in I$, $E$ contains a $k$-chain of constant gap length $t$ (i.e., a chain satisfying $|x^i - x^{i+1}|=t$; Fig. 1(a)). We refer to this as an existence result. One can analogously define a constant gap tree (Fig. 1(b)). In a subsequent work, Iosevich and the second listed author generalized the results of [1] to arbitrary tree configurations, see [12].

Figure 1. Chains and trees, (a) chain with constant gap length, (b) tree with constant gap length.

In this article, we study the existence and abundance of chains and trees of constant gap length under a different notion of size in the fractal setting known as Newhouse thickness. Assumptions on Newhouse thickness have yielded several interesting results on patterns contained in Cantor sets. The precise definition of the thickness $\tau (K)$ of a Cantor set $K\subset {\mathbb {R}}$, as well as the precise definition of a Cantor set, will be given in the next section, but we first describe some of this work. Simon and the second listed author [17] proved the following foundational result.

Theorem 1.1 Simon-Taylor, [17]

Let $K_1,\,K_2\subset {\mathbb {R}}$ be Cantor sets satisfying $\tau (K_1)\tau (K_2)>1$. For any $x\in {\mathbb {R}}^2,$ the pinned distance set

\[ \Delta_x(K_1\times K_2):=\{|x-y|:y\in\operatorname{\mathcal{K}}_1\times K_2\} \]

has non-empty interior.

In our previous paper [15], we generalize Theorem 1.1 from single distances to finite trees, showing that if $K_1,\, K_2$ satisfy the thickness condition in that theorem then the set of ‘distance trees’ generated by $K_1\times K_2$ has non-empty interior (see the next section for precise definitions). In another direction, Yavicoli [22] proved that for any finite point configuration in $ {\mathbb {R}}$, certain sets above a thickness threshold contain a similar copy of that configuration (the threshold depends on the configuration, and is generally very large). In [21], Yavicoli gives a definition of thickness in $ {\mathbb {R}}^d$ that works even for totally disconnected sets satisfying a uniform denseness assumption, and proves there that sufficiently thick sets generate an interval worth of distances in any direction. Thickness theorems have applications in dynamical systems and fractal geometry [19], as well as number theory [13, 23].

The results of this article are a continuation of our work in [15]. In that work we showed that the hypothesis of Theorem 1.1 was enough to ensure an abundance of chains and trees, and we posed the question of whether one could also obtain chains and trees with constant gap length. In this article, we partially answer this question in the affirmative.

2. Definitions and main results

Let $G=(V,\,\mathcal {E})$ be a graph, and let $\sim$ denote the adjacency relation (i.e., $i\sim j$ if and only if $i,\,j\in V$ and $(i,\,j)\in \mathcal {E}$. Given a set $E\subset {\mathbb {R}}^d$, define

\[ \Delta_G(E):=\{(|x^i-x^j|)_{i\sim j}: x^i \in E, x^i\neq x^j \text{ if } i\neq j\}, \]

where $\sim$ denotes the adjacency relation on the graph $G$, and $(|x^i-x^j|)_{i\sim j}$ is the vector with coordinates $|x^i-x^j|$ indexed by the edges of $G$. In [15], the authors prove that if $G=T$ is a tree with $k+1$ vertices and $k$ edges, and $E=K_1\times K_2$ is a product of Cantor sets $K_1,\,K_2\subset {\mathbb {R}}$ with thickness (definition 2.2) satisfying $\tau (K_1)\cdot \tau (K_2)>1$, then $\Delta _T(K_1\times K_2)$ has non-empty interior. In this paper, we consider a variant of this problem. Given $E\subset {\mathbb {R}}^d$ and $t\in {\mathbb {R}}$, let $G_t(E)$ denote the graph with vertex set $E$ and an edge connecting $x,\,y\in E$ if and only if $|x-y|=t$. Given a finite or infinite graph $G$, define

\[ \Delta_G'(E)=\{t\in{\mathbb{R}}: G_t(E) \text{ contains a subgraph isomorphic to } G\}. \]

Note that two graphs are isomorphic if there is a bijection between their vertex sets which preserves adjacency. This new distance set corresponds to the diagonal elements of the previous distance set:

\[ \Delta_G'(E)=\{t\in{\mathbb{R}}:(t,\ldots,t)\in\Delta_G(E)\}. \]

Accordingly, we refer to it as the diagonal distance set.

Definition 2.1 A tree is a connected acyclic graph. Equivalently, $T$ is a tree if and only if any two distinct vertices are connected by exactly one path.

Definition 2.2 A Cantor set is a non-empty subset of $ {\mathbb {R}}^d$ which is compact, perfect, and totally disconnected. A gap of a Cantor set $K\subset {\mathbb {R}}$ is a connected component of the complement $ {\mathbb {R}}\setminus K$. If $u$ is the right endpoint of a bounded gap $G$, for $b\in {\mathbb {R}}\cup \{\infty \}$, let $(a,\,b)$ be the closest gap to $G$ with the property that $u< a$ and $|G|\le b-a$ (Fig. 2). The interval $[u,\,a]$ is called the bridge at $u$ and is denoted $B(u)$. Analogous definitions are made when $u$ is a left endpoint. The thickness of $K$ at $u$ is the quantity

\[ \tau(K,u):=\frac{|B(u)|}{|G|}. \]

Finally, the thickness of the Cantor set $K$ is the quantity

\[ \tau(K):=\inf_u \tau(K,u), \]

the infimum being taken over all endpoints $u$ of bounded gaps.

Figure 2. A gap and corresponding bridge.

It is worth noting that large thickness implies large Hausdorff dimension but not conversely. Specifically, one can prove the bound (see [16, pg. 77]):

\[ \dim_{\rm H}(K) \geq \frac{\log{2}}{\log{\left( 2 + \frac{1}{\tau(K)} \right) }}. \]

In [15], we studied the distance set $\Delta _T(K_1\times K_2)$ using the Newhouse gap lemma; this lemma states that if sets $K_1,\,K_2$ satisfy the condition $\tau (K_1)\tau (K_2)>1$, then either one set is contained in the other or their intersection is non-empty. In order to study the diagonal distance set $\Delta _T'(K_1\times K_2)$, however, we will need to ensure the intersection $K_1\cap K_2$ contains many points of a certain type. While the Newhouse gap lemma gives non-empty intersection, it is possible for the intersection to be a single point (for example, see [20]), and the gap lemma does not give us much control over what that point is. Therefore, we will use the following result of Hunt, Kan, and Yorke [9], which gives a thickness condition which ensures robust intersection. We start by defining this thickness condition.

Definition 2.3 The pair $(\tau _1,\,\tau _2)\in {\mathbb {R}}_{>0}^2$ is said to satisfy the Hunt–Kan–Yorke thickness condition (briefly, the HKY condition) if the following inequalities hold:

\begin{align*} \tau_1& \geq \tau_2 \\ \tau_1& > \frac{\tau_2^2+3\tau_2+1}{\tau_2^2} \\ \tau_2& > \frac{(2\tau_1+1)^2}{\tau_1^3}. \end{align*}

We say Cantor sets $K_1$ and $K_2$ satisfy the Hunt–Kan–Yorke thickness condition if either $(\tau (K_1),\,\tau (K_2))$ or $(\tau (K_2),\,\tau (K_1))$ satisfy the condition.

Remark 2.4 The following observations are easy to verify:

• • The Hunt–Kan–Yorke condition is monotone: if $(\tau _1,\,\tau _2)$ satisfies the condition and $\tau _1'\geq \tau _1,\,\tau _2'\geq \tau _2,\, \tau _1'\geq \tau _2'$, then $(\tau _1',\,\tau _2')$ satisfies the condition as well.

• • The Hunt–Kan–Yorke condition implies the Newhouse condition $\tau _1\cdot \tau _2>1$ (in fact, it implies $\tau _1\cdot \tau _2> 5$), but not conversely. More generally, there is no constant $c$ such that $\tau _1\cdot \tau _2>c$ implies the Hunt–Kan–Yorke condition.

• • If $\tau _1\geq \tau _2>\sqrt {2}+1$, then $(\tau _1,\,\tau _2)$ satisfies the Hunt–Kan–Yorke condition.

• • For any $\tau _2>0$, there exists $\tau _1>0$ such that $(\tau _1,\,\tau _2)$ satisfies the Hunt–Kan–Yorke condition. As $\tau _2\to 0$, we must have $\tau _1\gtrsim 1/\tau _2^2$, so this is asymptotically worse then the Newhouse thickness condition $\tau _1>1/\tau _2$.

This stronger thickness condition guarantees a more robust intersection of the sets $K_1$ and $K_2$ than is given by the Newhouse gap lemma.

Definition 2.5 Cantor sets $K_1,\,K_2\subset {\mathbb {R}}$ are said to be interleaved each has non-empty intersection with the interior of the convex hull of the other.

Lemma 2.6 Hunt–Kan–Yorke intersection theorem

Let $K_1,\,K_2\subset {\mathbb {R}}$ be interleaved Cantor sets satisfying the Hunt–Kan–Yorke thickness condition. Then, there exists a Cantor set $K\subset K_1\cap K_2$ satisfying $\tau (K)>0$.

Our main theorem is as follows.

Theorem 2.7 Let $T$ be a countable tree, and let $K_1,\,K_2\subset {\mathbb {R}}$ be Cantor sets satisfying the Hunt–Kan–Yorke thickness condition. For $j=1,\,2,$ if $\widetilde {K}_j\subset K_j$ is a Cantor set which does not contain the minimum or maximum element of $K_j$ and satisfies $\tau (\widetilde {K}_j)\geq \tau (K_j),$ then

\[ \Delta(\widetilde{K}_1\times \widetilde{K}_2)\subset \Delta_T'(K_1\times K_2). \]

In particular, by Theorem 1.1, the set $\Delta _T'(K_1\times K_2)$ has non-empty interior.

Theorem 2.7 says that diagonal distance set of $K_1\times K_2$ will have non-empty interior whenever the original single-distance set of an appropriate subset has non-empty interior; Theorem 1.1 simply gives us one way to recognize when this occurs. Note that Lemma 3.2 guarantees the existence of $\widetilde {K}_1,\, \widetilde {K}_2$ satisfying the hypotheses of Theorem 2.7. In general, if $I$ is a bridge in the construction of a Cantor set, $K$, then $K\cap I$ is Cantor and $\tau (K) \le \tau (K\cap I)$.

Example 2.8 Let $C_\alpha$ denote the middle $\alpha$-Cantor set obtained by removing the middle $\alpha$ portion of the unit interval $[0,\,1]$ and iterating; it is not hard to check that the thickness of such a set is ${1 - \alpha }/{2\alpha }$. If $\tau (C_\alpha ) > 1 + \sqrt {2}$, then the Hunt–Kan–Yorke (HKY) condition is satisfied by $C_\alpha$ paired with itself, which, rounding, holds when $\alpha \le 1/6$. So, $C_{1}/{6} \times C_{1}/{6}$ contains arbitrarily long trees with an interval worth of admissible gap lengths. Note that $C_{1/6}$ paired with itself satisfies both the Newhouse and HKY condition, while $C_{1/4}$ only satisfies the Newhouse condition.

Remark 2.9 Our method of proof relies on the intersection of two Cantor sets containing many points, which is guaranteed by the HKY condition. It is not clear if the assumption $\tau (K_1)\cdot \tau (K_2)>1$ is sufficient for any tree in light of the fact that, in general, such sets could intersect in a single point (see [20]).

3. Proofs

Our proof strategy is similar to the one used in [17] and [15]. The idea is to translate the statement that a distance is achieved into the statement that sets $K_2$ and $g(K_1)$ intersect for an appropriate function $g$. In order to get an intersection point, we first need to ensure that the relevant thickness condition is satisfied, which means we need to understand how thickness changes under mapping. It is easy to see that if $G$ is a gap of $K_1$, then $g(G)$ is a gap of $g(K_1)$. However, if $B$ is the corresponding bridge, it does not follow that $g(B)$ is also a bridge. This is because $g$ can distort lengths, so there may be a gap $G'\subset B$ which satisfies $|G'|<|G|$ but $|g(G')|>|g(G)|$. However, the key observation is that if we work locally, small intervals which are close together should be distorted by a similar amount. Therefore, thickness is ‘locally almost preserved’. The following lemma, a variant of [17, Lemma 3.8] and [15, Lemma 3.4], makes this idea precise.

Lemma 3.1 Thickness is locally almost preserved by smooth maps

Let $K$ be a Cantor set, and let $I$ be an interval such that $\widetilde {K}:=K\cap I$ is a Cantor set with thickness $\tau (\widetilde {K})\geq \tau (K)$. For any $0< c<1,$ there exists $\varepsilon >0$ such that if $g$ is a continuously differentiable monotone function on $I$ which satisfies

\[ \left|\frac{|g'(x)|}{|g'(y)|}-1\right|<\varepsilon \]

for all $x,\,y\in I,$ then

\[ \tau(g(\widetilde{K}))>c\tau(K). \]

Proof of lemma 3.1. Proof of lemma 3.1

Fix $0< c<1$, and let $I$ and $g$ satisfy the hypotheses of the theorem for some $\varepsilon >0$ to be determined later. We must show that $\tau (g(\widetilde {K}))>c\cdot \tau (K)$ if $\varepsilon$ is sufficiently small. The main idea behind the proof is the notion of ‘$\varepsilon$-thickness’ defined in [17, Definition 3.6]. Given a gap $G$ of a Cantor set $K$ with right endpoint $u$, let $(a,\,b)$ be the closest gap to $G$ which satisfies $a>u$ and $b-a>(1-\varepsilon )|G|$. The interval $[u,\,a]$ is called the $\varepsilon$-bridge of $K$ at $u$, denoted $B_\varepsilon (u)$. The $\varepsilon$-bridge at a left endpoint is defined analogously. The $\varepsilon$-thickness of $K$ at $u$ is

\[ \tau_\varepsilon(K,u):=\frac{|B_\varepsilon(u)|}{|G|}, \]

and the $\varepsilon$-thickness of $K$ is $\tau _e(K):=\inf _u \tau _\varepsilon (K,\,u)$. Thus, the thickness $\tau (K)$ is simply the $0$-thickness, and $\tau _\varepsilon (K)\nearrow \tau (K)$ as $\varepsilon \searrow 0$. By the mean value theorem, for any subinterval $J\subset I$ there exists $x_J\in J$ with $|g(J)|=|g'(x_J)|\cdot |J|$. Let $G$ be a bounded gap of $\widetilde {K}$ with endpoint $u$. If $H\subset B_\varepsilon (u)$ is another gap, the by definition we have $|H|\leq (1-\varepsilon )|G|$. It follows that

\begin{align*} |g(H)|& =|H|\cdot |g'(x_H)| \\ & \leq (1-\varepsilon)|G|\cdot \frac{|g'(x_H)|}{|g'(x_G)|}\cdot |g'(x_G)| \\ & <(1-\varepsilon)|G|\cdot (1+\varepsilon)\cdot |g'(x_G)| \\ & =(1-\varepsilon^2)|g(G)|. \end{align*}

Since any gap in $g(B_\varepsilon (u))$ is of the form $g(H)$ for some gap $H$ in $B_\varepsilon (u)$, this calculation shows that $g(B_\varepsilon (u))$ is contained in the $\varepsilon ^2$-bridge at $g(u)$:

\[ g(B_\varepsilon(u)) \subset B_{\varepsilon^2}(g(u)). \]

Therefore, the $\varepsilon ^2$-thickness of $g(\widetilde {K})$ at $g(u)$ satisfies

\begin{align*} \tau_{\varepsilon^2}(g(\widetilde{K}),g(u))& =\frac{|B_{\varepsilon^2}(g(u))|}{|g(G)|} \\ & \geq \frac{|g(B_\varepsilon(u))|}{|g(G)|} \\ & =\frac{|B_\varepsilon(u)|}{|G|}\cdot\frac{|g'(x_{B_\varepsilon(u)})|}{|g'(x_G)|} \\ & >\tau_\varepsilon(\widetilde{K},u)(1-\varepsilon). \end{align*}

Taking infima over $u$, we get $\tau _{\varepsilon ^2}(g(\widetilde {K}))\geq \tau _\varepsilon (\widetilde {K})(1-\varepsilon )$. Since $\tau (g(\widetilde {K}))\geq \tau _{\varepsilon ^2}(g(\widetilde {K}))$ for any $\varepsilon >0$ (this is not specific to $\widetilde {K}$, thickness is always greater than $\varepsilon$-thickness by definition), it follows that

\[ \tau(g(\widetilde{K}))\geq \tau_\varepsilon(\widetilde{K})(1-\varepsilon)\geq \tau_\varepsilon(K)(1-\varepsilon) . \]

Since $\tau _\varepsilon (K)(1-\varepsilon )\to \tau (K)$ as $\varepsilon \to 0$, we have $\tau _\varepsilon (K)(1-\varepsilon )>c\tau (K)$ if $\varepsilon$ is sufficiently small.

The key to applying the lemma in our context is, given sets $K_1$ and $K_2$ and function $g$, to choose a small interval $I$ and consider $\widetilde {K}_1:=K_1\cap I$, where $I$ is as in the hypotheses of Lemma 3.1. Since the Hunt–Kan–Yorke condition is monotone, the new sets will satisfy the condition also. Finally, since the Hunt–Kan–Yorke condition is an ‘open condition,” $g(\widetilde {K}_1)$ and $\widetilde {K}_2$ will satisfy it as well, provided $c$ is sufficiently close to $1$. Unfortunately, it is not true in general $\tau (K\cap I)\geq \tau (K)$ for an arbitrary interval $I$. For example, the middle-third Cantor set has thickness equal to $1$, but its intersection with $[{2}/{9},\, {7}/{9}]$ has thickness strictly less than $1$. However, this property does always hold if $I$ is replaced with a carefully chosen subinterval $J$. More precisely, we have the following lemma.

Lemma 3.2 Let $K\subset {\mathbb {R}}$ be a Cantor set, let $x\in K$, and let $I\subset {\mathbb {R}}$ be an open interval containing $x$. There exists a compact interval $J\subset I$, also containing $x$, such that $K':=K\cap J$ is a Cantor set satisfying $\tau (K')\geq \tau (K)$. If $x$ is a gap endpoint of $K$, then $J$ may be chosen so that $x$ is a gap endpoint of $K'$. If $x$ is not a gap endpoint of $K$, then $J$ may be chosen so that $x$ is not a gap endpoint of $K'$.

Proof. First assume $x$ is an endpoint of a gap $G$; without loss of generality suppose $x$ is the right endpoint of $G$. Since gaps are disjoint, the interval $I$ can intersect only finitely many gaps to the right of $x$ of length at least $|G|$. Let $G'$ be the leftmost such gap (if all bounded gaps to the right of $x$ are smaller than $G$, let $G'$ be a gap intersecting $I$ of maximal length). Let $y$ be the left endpoint of $G'$, let $J=[x,\,y]$, and let $K'=J\cap K$. Clearly $K'$ is a Cantor set, so it remains to show $\tau (K')\geq \tau (K)$. Since all bounded gaps of $K'$ are smaller than $|G|$ and $|G'|$ the bridge at any gap endpoint $u$ with respect to $K'$ is the same as the bridge at $u$ with respect to $K$. It follows that $\tau (K,\,u)=\tau (K',\,u)$ for each bounded gap endpoint $u$ of $K'$. Taking infima over bounded gap endpoints of $K'$ on the right and the larger class of bounded gap endpoints of $K$ on the left gives $\tau (K)\leq \tau (K')$.

Now, suppose $x$ is not a gap endpoint of $K$. Let $G_L$ be a gap to the left of $x$ which is contained in $I$, and let $G_R$ be a gap to the right of $x$ which is contained in $I$. Let $\ell =\min (|G_L|,\,|G_R|)$. There are at most finitely many gaps between $G_L$ and $x$ of length at least $\ell$; let $G_L'$ be the rightmost such gap, and let $u$ be its right endpoint (if there are no such gaps, take $G_L'=G_L$. Define $G_R'$ similarly, and let $v$ be its left endpoint. Let $J=[u,\,v]$, and let $K'=K\cap J$. As in the previous case, since each bounded gap of $K'$ is smaller than $|G_L'|$ and $|G_R'|$, the bridges with respect to $K'$ coincide with the bridges with respect to $K$, and therefore $\tau (K)\leq \tau (K')$.

We are now ready to begin constructing trees of constant gap length. Our first lemma requires a little more terminology.

Definition 3.3 Let $K_1,\,K_2\subset {\mathbb {R}}$ be Cantor sets, and assume $\tau (K_1)\geq \tau (K_2)$. A point $x=(x_1,\,x_2)\in K_1\times K_2$ is called a special point if $x_1$ is not a gap endpoint of $K_1$, and $x_2$ is not the maximum or minimum point of $K_2$.

Note that if $x_1 \in K_1$ is not an endpoint of a gap, then it is both a left and right-limit point of $K_i$. Moreover, it is also a left or right limit of left or right gap endpoints of $K_i$. This ensures that when we define $\widetilde {K}_1:=K_1\cap I$ for some interval $I$, we can assume $x_1$ is not the maximum or minimum point of $\widetilde {K}_1$. The following lemma states that, given arbitrary points $x,\, y \in K_1\times K_2$, provided $x$ is special, then the circle about $y$ through $x$ contains infinitely many points of $K_1 \times K_2$. This allows us to generate arbitrarily large ‘star-shaped graphs’.

Lemma 3.4 Star-shaped graph lemma

Let $K_1,\,K_2$ be Cantor sets satisfying the Hunt–Kan–Yorke condition. Let $y\in {\mathbb {R}}^2,$ let $x\in K_1\times K_2$ be a special point which does not share a coordinate with $y,$ and let $t=|x-y|$. Then, there are uncountably many $z\in K_1\times K_2$ such that $|y-z|=t$. In particular, there are uncountably many special points, $z,$ such that $|z-y|=t$

Proof. Assume $x_1< y_1$ and $x_2< y_2$, so the point $x=(x_1,\,x_2)$ is below and to the left of $y=(y_1,\,y_2)$. Because thickness does not change under symmetries, there is no loss of generality in this assumption. Define a function $g_{y,t}:(y_1-t,\,y_1+t)\to {\mathbb {R}}$ by

\[ g_{y,t}(s)=y_2-\sqrt{t^2-(s-y_1)^2}, \]

so that the graph of $g_{y,t}$ is the lower half circle centred at $y$ of radius $t$. In particular, $g_{y,t}(x_1)=x_2$. Note that $g_{y,t}$ is smooth, and the derivative $g_{y,t}'$ vanishes only at the point $y_1$. By lemma 3.2, we may choose an interval $J$ containing $x_1$ in its interior such that $\widetilde {K}_1:=K_1\cap J$ and $K_2$ satisfy the Hunt–Kan–Yorke thickness condition, and $x_1$ is not a gap endpoint of $\widetilde {K}_1$. We may also assume $J$ is as small as needed. Since $x_1$ is not a critical point of $g_{y,t}$, we may assume that $J$ satisfies the conditions of lemma 3.1, and hence $g_{y,t}(\widetilde {K}_1)$ and $K_2$ satisfy the Hunt–Kan–Yorke condition as well. Since $|y-z|=t$ whenever $g_{y,t}(z_1)=z_2$, the statement of the lemma follows from the claim that $g_{y,t}(\widetilde {K}_1)\cap K_2$ is uncountable. To prove this claim, suppose this set is countable. We will show $g_{y,t}(\widetilde {K}_1)$ and $K_2$ are interleaved, contradicting the Hunt–Kan–Yorke intersection theorem. Since $x_1$ is not a gap endpoint of $K_1$, it is not the maximum or minimum of $\widetilde {K}_1$, hence the set $\widetilde {K}_1$ contains uncountably many points to both the left and right of $x_1$. If $g_{y,t}(\widetilde {K}_1)$ intersects $K_2$ in only countably many places, then there exist $u_1,\,v_1\in \widetilde {K}_1$ such that $u_1< x_1< v_1$ and $g_{y,t}(u_1),\,g_{y,t}(v_1)\notin K_2$ (Fig. 3). Since $g_{y,t}$ is monotone decreasing in a neighbourhood of $x_1$, we have $g_{y,t}(v_1)< x_2< g_{y,t}(u_1)$. Since $x_2\in K_2$, each of the points $g_{y,t}(u_1)$ and $g_{y,t}(v_1)$ are contained in a different gap of $K_2$. A similar argument shows that there are points $u_2,\,v_2\in K_2$ contained in different gaps of $g_{y,t}(\widetilde {K}_1)$. The Hunt–Kan–Yorke intersection theorem (Lemma 2.6) then guarantees the intersection $g_{y,t}(\widetilde {K}_1)\cap K_2$ contains a Cantor set of positive thickness, contradicting countability. To prove the ‘in particular’ part of the lemma, observe that any graph of a function can contain at most countably many points of $K_1\times K_2$ that are not special points.

Figure 3. Constructing the sets $\widetilde {K}_j$.

To prove our main theorem, we will start with a single distance between two points and use it to build a tree one star-shaped graph at a time. This will almost prove the theorem, which says that ‘almost’ any distance is an admissible gap length for a tree. However, our Lemma 3.4 only allows us to use special points, so we have to ensure that we have not lost too many distances. This is accomplished by the following lemma.

Lemma 3.5 Let $K_1,\,K_2\subset {\mathbb {R}}$ be Cantor sets satisfying the Hunt–Kan–Yorke condition and assume $\tau (K_1)\geq \tau (K_2)$. For $j=1,\,2,$ let $\widetilde {K}_j\subset K_j$ be a Cantor set which does not contain the maximum or minimum of $K_j$ and satisfies $\tau (\widetilde {K}_j)\geq \tau (K_j),$ and let $\mathcal {S}$ be the set of special points of $K_1\times K_2$. Then, $\Delta (\widetilde {K}_1\times \widetilde {K}_2)\subset \Delta (\mathcal {S})$.

Proof. Let $t\in \Delta (\widetilde {K}_1\times \widetilde {K}_2)$, say $t=|x-y|$ with $x,\,y\in \widetilde {K}_1\times \widetilde {K}_2$. Let $r=x_1-y_1$ and $s=x_2-y_2$, so that $t^2=r^2+s^2$. By assumption, $x_2$ and $y_2$ are not the maximum or minimum points of $K_2$, so to prove the lemma it suffices to prove there exist $x_1',\,x_2'\in K_1$ which are not gap endpoints and satisfy $x_1'-y_1'=r$, since the points $(x_1',\,x_2)$ and $(y_1',\,y_2)$ would be special points with distance $t$. By monotonicity of the Hunt–Kan–Yorke condition and the assumption $\tau (K_1)\geq \tau (K_2)$, the set $K_1$ satisfies the Hunt–Kan–Yorke condition when paired with itself. Finally, since $\widetilde {K}_1$ does not contain the maximum or minimum points of $K_1$, we have $|r|<(\max K_1-\min K_1)$. Therefore, the Hunt–Kan–Yorke intersection theorem implies that $K_1$ and $r+K_1$ have uncountably many intersection points, meaning there are uncountably many pairs $(x_1',\,y_1')\in K_1\times K_1$ which satisfy the equation $x_1'=y_1'+r$. Since each choice of $y_1'$ yields a different $x_1'$ and there are only countably many gap endpoints, we conclude that we may find a solution such that neither $x_1'$ nor $y_1'$ is a gap endpoint.

3.1 Proof of theorem 2.7

Proof of Theorem 2.7. Proof of Theorem 2.7

Consider the tree $T^*$ with vertex set consisting of all finite sequences of positive integers (including the empty sequence, denoted $\varnothing$), with an edge between two sequences if and only if they are of the form $(i_1,\,\ldots,\, i_n)$ and $(i_1,\,\ldots,\,i_n,\,i_{n+1})$ (or $\varnothing$ and $(i_1)$) for $i_1,\,\ldots,\,i_{n+1}\in {\mathbb {N}}$ (Fig. 4). It is easy to see that every countable tree is a subgraph of $T^*$, so it suffices to prove the theorem in the case $T=T^*$. To prove this case, for any non-negative integer $n$, let $L_n$ denote the $n$-th ‘level’ of $T^*$, i.e., the set of sequences of length exactly $n$ (the empty sequence has length $0$). For each $w\in L_n$, let $L_{n+1}(w)$ be the sequences in $L_{n+1}$ which are adjacent to $w$; explicitly, if $w=(i_1,\,\ldots,\,i_n)$, then

\[ L_{n+1}(w)=\{(i_1,\ldots,i_n,i_{n+1}):i_{n+1}\in{\mathbb{N}}\}. \]

By lemma 3.5, to prove the theorem it suffices to show $\Delta (\mathcal {S})\subset \Delta _{T^*}'(K_1\times K_2)$, where $\mathcal {S}$ is the set of special points of $K_1\times K_2$. Given $t\in \Delta (\mathcal {S})$, for each finite sequence $w$ we construct a point $x^w\in K_1\times K_2$ such that $|x^w-x^{w'}|=t$ whenever $w\sim w'$. This construction is done by recursion on levels. First, since $t\in \Delta (\mathcal {S})$ we have $t=|x^\varnothing -x^1|$ with $x^\varnothing,\,x^1$ special. In particular, since $x^1$ is a special point, we may apply Lemma 3.4 with $y=x^\varnothing,\,x=x^1$ to generate a sequence $x^2,\,x^3,\,\ldots$ of distinct special points satisfying $|x^\varnothing -x^i|=t$ for every $i$ (Fig. 5(a)). This gives the construction of levels $L_0$ and $L_1$.

Figure 4. The tree $T^*$.

Figure 5. Constructing a short tree, (a) first level, (b) second level descendants of $x^3$.

Next, let $n\geq 1$ and suppose we have constructed distinct special points $x^w$ for every $w\in L_0 \cup \ldots \cup L_n$ such that for any $w'\in L_{n-1}$ with $w\sim w'$, we have $|x^w-x^{w'}|=t$. Fix some finite sequence $w=(i_1,\,\ldots,\,i_n)$, and let $w'=(i_1,\,\ldots,\,i_{n-1})\in L_{n-1}$. Since $|x^{w}-x^{w'}|=t$ and $x^{w'}$ is special, we may apply lemma 3.4 with $x=x^{w'},\,y=x^w$ to obtain a sequence of distinct special points $x^{(w,1)},\,x^{(w,2)},\,\ldots$ such that $|x^{w,i}-x^w|=t$ for every $i$. Moreover, since Lemma 3.4 gives uncountably many choices but we have only constructed countably many points so far, we may choose our new points to be distinct from all points at previous levels and not just from each other. This allows us to construct $L_{n+1}(w)$, the points in level $n+1$ which are children of $w$. Doing this for every $w\in L_n$ and ensuring no points are chosen more than once, we construct the entire level $L_{n+1}$.