Assume there exists a cut metric \(d_{w}\) on \(X\) such that \(id:(X,d) \to (X,d_{w})\) is a coarse embedding. Since each \((X_{n}, d_{n,w})\) isometrically embeds into a hypercube equipped with the standard graph metric, \((C_{n}, d_{n,C})\), \((X,d)\) coarsely embeds into the disjoint union of \(\{(C_{n}, d_{n, C})\}_{n \in \mathbb{N}}\)~\cite[Proposition~4.2.2]{deza:geometry}. Conversely, assume there exists a coarse disjoint union, \((C, d_{C})\), of a sequence of hypercubes, \((C_{n}, d_{n,C})_{n \in \mathbb{N}}\), equipped with the standard graph metric and a coarse embedding function \(f:(X, d) \to (C,d_{C})\) such that \(f(X_{n}) \subseteq C_{n}\) for all \(n \in \mathbb{N}\). Using the Hamming encoding of a hypercube we can create partitions of the vertices of each \(C_{n}\) such that for any \(x,y \in X_{n}\), \(d_{n,w}(x,y) = d_{n,C}(f(x),f(y))\). Fix an \(n \in \mathbb{N}\). \(C_{n}\) contains \(2^m\) vertices for some \(m \in \mathbb{N}\). Define partitions \(S^n_{1},\ldots,S^n_{m}\) of the vertices of \(X_{n}\) by \begin{equation*} S^n_{k} := \{ x : x \in X_{n}, h(f(x))_{k} = 1 \}. \end{equation*} The set of partitions \(S^n_{1},\ldots,S^n_{m}\) defines a cut metric, \(d_{n,w}\), on \(X_{n}\) by \begin{equation*} d_{n,w}(x,y) = |\{ k : |S^n_{k} \cap \{ x,y \}| = 1 \}|, ~\forall x,y \in X_{n} \end{equation*} which is equal to the number of bits which differ between \(h(f(x))\) and \(h(f(y))\). Hence, for all \(n \in \mathbb{N}\) and all \(x,y \in X_{n}\), \(d_{n,w}(x,y) = d_{n,C}(f(x), f(y))\). Let \(d_{w}:X \times X \to \mathbb{R}^{\geq 0}\) be defined such that \(d_{w}\restrict{X_{n}} = d_{n,w}\) and \(d_{w}(X_{n}, X_{m}) = d_{C}(f(X_{n}), f(X_{m}))\) for all \(m,n \in \mathbb{N}\). Then, for any \(x,y \in X\), \(d_{w}(x,y) = d_{C}(f(x),f(y))\) hence \(id:(X, d) \to (X, d_{w})\) is a coarse equivalence.

By assumption there exists a sequence of finite hypercube graphs \((C_{n})_{n \in \mathbb{N}}\), each equipped with the standard graph metric, and a coarse embedding function \(f:(X, d) \to (C, d_{C})\). We assume that each \(C_{n}\) is minimal in size and we let \(d_{C}\) be such that \(d(C_{i}, C_{j}) = \text{diam}(C_{i}) + \text{diam}(C_{j}) + i + j\). We will build \((B, d_{B})\) where \((B_{n})_{n \in \mathbb{N}}\) is a sequence of hypercubes, \(d_{B}\) when restricted to each cube is the standard graph metric, and \(d_{B}(B_{i}, B_{j}) = d(X_{i}, X_{j})\). To build \((B_{n})_{n \in \mathbb{N}}\) we use Hamming encoding of the vertices of the hypercubes \((C_{n})_{n \in \mathbb{N}}\). For all \(n \in \mathbb{N}\), denote by \(C_{n_{1}},C_{n_{2}},\ldots,C_{n_{m}}\) the hypercubes in \(C\) such that \(f(X_{n}) \cap C_{n_{i}}\neq \emptyset\). Let \begin{equation*} k = \sum_{j=1}^m 2\cdot\text{diam}(C_{n_{j}}) + j \end{equation*} and define \(B_{n}\) to be the hypercube on \(2^k\) vertices. Let \(x \in X_{n}\) and \(f(x) \in C_{n_{i}}\). We define \(g:(X, d) \to (B, d_{B})\) by defining the Hamming encoding of \(g(x)\) in \(B_{n}\). In words, \(g\) maps \(x\) to a vertex in \(B_{n}\) for which the only nonzero bits of \(h(g(x))\) are a string of ones with length equal to \(\text{diam}(C_{n_{i}}) + n_{i}\) immediately followed by the Hamming encoding of \(f(x)\) in \(C_{n_{i}}\). The number of zeros preceding the string of ones is long enough so that, for \(x,y \in X_{n}\), if \(f(x) \in C_{n_{i}}\) and \(f(y) \in C_{n_{j\neq i}}\) then \(g(x)\) and \(g(y)\) can not share a nonzero bit. Explicitly, for each \(i \in \{ 1,\ldots,m \}\), let \(k_{i}' = \sum_{j=1}^{i-1} 2\cdot\text{diam}(C_{n_{j}})+j\). Then \(g\) maps \(x\) to \begin{align*} g(x)_{j} = \begin{cases} 0 & j \leq k_{i}'\\ 1 & k_{i}' < j \leq k_{i}' + \text{diam} (C_{n_{i}}) + n_{i} \\ h(f(x))_{j - k_{i}' - \text{diam} (C_{n_{i}}) - n_{i}} & k_{i}' + \text{diam} (C_{n_{i}}) + n_i < j \leq k_{i}' + 2\text{diam} (C_{n_{i}}) + n_{i} \\ 0 & \text{else.} \end{cases} \end{align*} \begin{figure}[ht] \centering \includegraphics[width=0.65\textwidth]{rp-coarse-geometry-fig-1.pdf} \caption{ Example of the Hamming encoding of \(g(x)\) and \(g(y)\) given \(f(x) \in C_{n_{i}}\) and \(f(y) \in C_{n_{j}}\). The encodings share no nonzero bits and the number of bits that differ is at least \(\text{diam}(C_{n_{j}}) + n_{j} + \text{diam}(C_{n_{i}}) + n_{i}\) and at most \(2\cdot\text{diam}(C_{n_{j}}) + n_{j} + 2\cdot\text{diam}(C_{n_{i}}) + n_{i}\). } \label{fig:fig1} \end{figure} By construction, if \(x,y \in X_{n}\) and \(f(x), f(y) \in C_{n_{i}}\) then \(d_{B}(g(x), g(y))\) is the number of bits that differ between \(h(f(x))\) and \(h(f(y))\), hence \(d_{B}(g(x), g(y)) = d_{C}(f(x),f(y))\). If \(x,y \in X_{n}\), \(f(x) \in C_{n_{i}}\), and \(f(y) \in C_{n_{j}}\) with \(i\neq j\), then \(g(x)\) and \(g(y)\) differ in the bits that represent the encodings of \(\text{diam}(C_{n_{i}}) + n_{i}\) and \(\text{diam}(C_{n_{j}}) + n_{j}\). Further, if a bit in \(g(x)\) is nonzero and it is not in the encoding of \(\text{diam}(C_{n_{i}}) + n_{i}\) then it is the encoding of \(h(f(x))\) in which case the corresponding bit in \(g(y)\) is always a zero; the total number of bits for which this can be the case is \(\text{diam}(C_{n_{i}})\). Hence, the total number of bits which may differ between \(g(x)\) and \(g(y)\) is at most \(2\text{diam}(C_{n_{i}}) + 2\text{diam}(C_{n_{j}}) + n_{i} + n_{j}\). Thus, if \(x,y \in X_{n}\) then \begin{align*} \text{diam}(C_{n_{i}}) + \text{diam}(C{n_{j}}) + n_{i} + n_{j} &\leq d_{B}(g(x), g(y)) \leq 2\text{diam}(C_{n_{i}}) + 2\text{diam}(C_{n_{j}}) + n_{i} + n_{j}\\ \implies d_{C}(f(x),f(y)) &\leq d_{B}(g(x), g(y)) < 2d_{C}(f(x),f(y)) \end{align*} and if \(x \in X_{n}, y \in X_{m}, m\neq n\) then \(d(x,y) = d_{B}(g(x),g(y))\). We conclude that \((X,d)\) coarsely embeds into \((B,d_{B})\) and \(g(X_{n}) \subseteq B_{n}\) for all \(n \in \mathbb{N}\).