Lower Bounds on the Homology of Vietoris–Rips Complexes of Hypercube Graphs

Abstract

We provide novel lower bounds on the Betti numbers of Vietoris–Rips complexes of hypercube graphs of all dimensions and at all scales. In more detail, let $Q_n$ be the vertex set of $2^n$ vertices in the n-dimensional hypercube graph, equipped with the shortest path metric. Let $\textrm{VR}(Q_n;r)$ be its Vietoris–Rips complex at scale parameter $r \ge 0$, which has $Q_n$ as its vertex set, and all subsets of diameter at most r as its simplices. For integers $r<r'$ the inclusion $\textrm{VR}(Q_n;r)\hookrightarrow \textrm{VR}(Q_n;r')$ is nullhomotopic, meaning no persistent homology bars have length longer than one, and we therefore focus attention on the individual spaces $\textrm{VR}(Q_n;r)$. We provide lower bounds on the ranks of homology groups of $\textrm{VR}(Q_n;r)$. For example, using cross-polytopal generators, we prove that the rank of $H_{2^r-1}(\textrm{VR}(Q_n;r))$ is at least $2^{n-(r+1)}\left( {\begin{array}{c}n\\ r+1\end{array}}\right)$. We also prove a version of homology propagation: if $q\ge 1$ and if p is the smallest integer for which $\textrm{rank}H_q(\textrm{VR}(Q_p;r))\ne 0$, then $\textrm{rank}H_q(\textrm{VR}(Q_n;r)) \ge \sum _{i=p}^n 2^{i-p} \left( {\begin{array}{c}i-1\\ p-1\end{array}}\right) \cdot \textrm{rank}H_q(\textrm{VR}(Q_p;r))$ for all $n \ge p$. When $r\le 3$, this result and variants thereof provide tight lower bounds on the rank of $H_q(\textrm{VR}(Q_n;r))$ for all n, and for each $r \ge 4$ we produce novel lower bounds on the ranks of homology groups. Furthermore, we show that for each $r\ge 2$, the homology groups of $\textrm{VR}(Q_n;r)$ for $n \ge 2r+1$ contain propagated homology not induced by the initial cross-polytopal generators.

1 Introduction

Let $Q_n$ be the vertex set of the hypercube graph, equipped with the shortest path metric. In other words, $Q_n$ can be thought of the set of all $2^n$ binary strings of 0’s and 1’s equipped with the Hamming distance, or alternatively, as the set $\{0,1\}^n\subseteq \mathbb {R}^n$ equipped with the $\ell ^1$ metric.

In this paper, we study the topology of the Vietoris–Rips simplicial complexes of $Q_n$. Given a metric space X and a scale $r\ge 0$, the Vietoris–Rips simplicial complex $\textrm{VR}(X;r)$ has X as its vertex set, and a finite subset $\sigma \subseteq X$ as a simplex if and only if the diameter of $\sigma$ is at most r. Originally introduced for use in algebraic topology [24] and geometric group theory [8, 17], Vietoris–Rips complexes are now a commonly used tool in applied and computational topology in order to approximate the shape of a dataset [9, 13]. Important results include the fact that nearby metric spaces give nearby Vietoris–Rips persistent homology barcodes [11, 12], that Vietoris–Rips complexes can be used to recover the homotopy types of manifolds [18,19,20, 26], and that Vietoris–Rips persistent homology barcodes can be efficiently computed [7]. Nevertheless, not much is known about Vietoris–Rips complexes of manifolds or of simple graphs at large-scale parameters, unless the manifold is the circle [3], unless the graph is a cycle graph [2, 5], or unless one restricts attention to 1-dimensional homology [16, 25].

Let $\textrm{VR}(Q_n;r)$ be the Vietoris–Rips complex of the vertex set of the n-dimensional hypercube at scale parameter r. The homotopy types of $\textrm{VR}(Q_n;r)$ are known for $r\le 3$ (and otherwise mostly unknown); see Table 1. For $r=0$, $\textrm{VR}(Q_n;0)$ is the disjoint union of $2^n$ vertices, and hence homotopy equivalent to the $(2^n-1)$-fold wedge sum of zero-dimensional spheres. For $r=1$, $\textrm{VR}(Q_n;1)$ is a connected graph (the hypercube graph), which by a simple Euler characteristic computation is homotopy equivalent to a $((n-2)2^{n-1}+1)$-fold wedge sum of circles. For $r=2$, Adams and Adamaszek [4] prove that $\textrm{VR}(Q_n;2)$ is homotopy equivalent to a wedge sum of 3-dimensional spheres; see Theorem 2.4 for a precise statement which also counts the number of 3-spheres. For $r=3$, Shukla proved in [22, Theorem A] that for $n\ge 5$, the q-dimensional homology of $\textrm{VR}(Q_n;3)$ is nontrivial if and only if $q=7$ or $q=4$. The study of $r=3$ was furthered by Feng [14] (based on work by Feng and Nukula [15]), who proved that $\textrm{VR}(Q_n;3)$ is always homotopy equivalent to a wedge sum of 7-spheres and 4-spheres; see Theorem 2.5 for a precise statement which also counts the number of spheres of each dimension. When $r=n-1$, $\textrm{VR}(Q_n;n-1)$ is isomorphic to the boundary of the cross-polytope with $2^n$ vertices and hence is homeomorphic to a sphere of dimension $2^{n-1}-1$. For $r\ge n$, the space $\textrm{VR}(Q_n;n)$ is a complete simplex and hence contractible. However, there is an entire infinite “triangle” of parameters, namely $r\ge 4$ and $r\le n-2$, for which essentially nothing is known about the homotopy types of $\textrm{VR}(Q_n;r)$.

Table 1 Black entries are the known homotopy types of $\textrm{VR}(Q_n;r)$; blue entries are sample novel lower bounds on the Betti numbers of $\textrm{VR}(Q_n;r)$ based on Theorem 4.1

In this paper, instead of focusing on a single value of r, we provide novel lower bounds on the ranks of homology groups of $\textrm{VR}(Q_n;r)$ for all values of r. Some of these lower bounds are shown in blue in Table 1: using cross-polytopal generators, in Theorem 4.1 we prove $\textrm{rank}H_{2^r-1}( \textrm{VR}(Q_{n};r)) \ge 2^{n-(r+1)}\left( {\begin{array}{c}n\\ r+1\end{array}}\right)$ (although we show in Sect. 7 that for $r\ge 2$ and $n > 2r$ this does not constitute the entire reduced homology in all dimensions). This is the first result showing that the topology of $\textrm{VR}(Q_n;r)$ is nontrivial for all values of $r\le n-1$. Furthermore, we often show that $\textrm{VR}(Q_n;r)$ is far from being contractible, with the rank of $(2^r-1)$-dimensional homology tending to infinity exponentially fast as a function of n (with n increasing and with r fixed).

Our general strategy, which we refer to as homology propagation, is as follows. Let $q\ge 1$. Suppose that one can show that the q-dimensional homology group $H_q(\textrm{VR}(Q_{p};r))$ is nonzero (for example, using a homology computation on a computer, or alternatively a theoretical result such as the mentioned cross-polytopal elements or the geometric generators of Sect. 7). Then we provide lower bounds on the ranks of the homology groups $H_q(\textrm{VR}(Q_{n};r))$ for all $n\ge p$. In particular, in Theorem 6.4 we prove that if $p\ge 1$ is the smallest integer for which $H_q(\textrm{VR}(Q_{p};r))\ne 0$, then

$$\begin{aligned} \textrm{rank}H_{q}(\textrm{VR}(Q_{n};r)) \ge \sum _{i=p}^n 2^{i-p} \left( {\begin{array}{c}i-1\\ p-1\end{array}}\right) \cdot \textrm{rank}H_{q}(\textrm{VR}(Q_{p};r)). \end{aligned}$$

Thus, a homology computation for a low-dimensional hypercube $Q_p$ has consequences for the homology of $\textrm{VR}(Q_{n};r)$ for all $n\ge p$. See Table 2 for some consequences of this result and of related results.

As we explain in Sect. 6.4, when $r\le 3$ our results are known to provide tight lower bounds on all Betti numbers of $\textrm{VR}(Q_{n};r)$. We take this as partial evidence that our novel results on the Betti numbers of $\textrm{VR}(Q_{n};r)$ for $r\ge 4$ are likely to be good lower bounds, though we do not know how close they are to being tight as no upper bounds are known. Indeed, the main “upper bound” we know of on the Betti numbers of $\textrm{VR}(Q_{n};r)$ is a triviality result for 2-dimensional homology: Carlsson and Filippenko [10] prove that $H_2(\textrm{VR}(Q_n;r))=0$ for all n and r.

For integers $r<r'$, we prove via a simple argument that the inclusion $\textrm{VR}(Q_n;r)\hookrightarrow \textrm{VR}(Q_n;r')$ is nullhomotopic. Therefore, there are no persistent homology bars of length longer than one, and all homological information about the filtration $\textrm{VR}(Q_n;\bullet )$ is determined by $\textrm{VR}(Q_n;r)$ for individual integer values of r.

Though we have stated our results for $Q_n=\{0,1\}^n$ equipped with the $\ell ^1$ metric, we remark that these results hold for any $\ell ^p$ metric with $1\le p < \infty$. Indeed for $x,y\in Q_n$, the i-th coordinates of x and y differ by either 0 or 1 for each $1\le i\le n$, and hence $\textrm{VR}((Q_n,\ell ^p);r)=\textrm{VR}((Q_n,\ell ^1);r^p)$. So, our results can be translated into any $\ell ^p$ metric by a simple reparametrization of scale.

We expect that some of our work could be transferred over to provide results for Čech complexes of hypercube graphs, as studied in [6], though we do not pursue that direction here.

We begin with some preliminaries in Sect. 2. In Sect. 3 we review contractions, and we prove that $\textrm{VR}(Q_n;\bullet )$ has no persistent homology bars of length longer than one. In Sect. 4 we use cross-polytopal generators to prove $\textrm{rank}H_{2^r-1}( \textrm{VR}(Q_{n};r)) \ge 2^{n-(r+1)}\left( {\begin{array}{c}n\\ r+1\end{array}}\right)$. We introduce concentrations in Sect. 5, which we use to prove our more general forms of homology propagation in Sect. 6. In Sect. 7 we prove the existence of novel lower-dimensional homology generators, and we conclude with some open questions in Sect. 8.

2 Preliminaries and Geometry of Hypercubes

2.1 Homology

All homology groups will be considered with coefficients in $\mathbb {Z}$ or in a field. The rank of a finitely generated abelian group is the cardinality of a maximal linearly independent subset. We let $\beta _q$ denote the q-th Betti number of a space, i.e., the rank of the q-dimensional homology group.

2.2 Hypercubes

Hypercubes are among the simplest examples of product spaces.

Definition 2.1

Given $n\in \{1,2,\ldots \}$, the hypercube graph $Q_n$ is the metric space $\{0,1\}^n$, equipped with the $\ell ^1$ metric. In particular, the elements of the space are n-tuples $(a_1, a_2, \ldots , a_n)=(a_i)_{i\in [n]}$ with $a_i\in \{0,1\}$, and the $\ell ^1$ distance is defined as

$$\begin{aligned} d \big ((a_1, a_2, \ldots , a_n),(b_1, b_2, \ldots , b_n)\big )= \sum _{i=1}^n |a_i-b_i|. \end{aligned}$$

In other words, the distance between two n-tuples is the number of coordinates in which they differ.

For $a\in Q_n$, its antipodal point $\bar{a}$ is given as $\bar{a} = (1,1,\ldots , 1)-a$. In particular, $\bar{a}$ is the furthest point in $Q_n$ from a and thus shares no coordinate with a. Observe that $d(a,\bar{a})=n$.

2.3 Vietoris–Rips Complexes

A Vietoris–Rips complex is a way to “thicken” a metric space, as we describe via the definitions below.

Definition 2.2

Given a metric space X and a finite subset $A \subseteq X$, the diameter of A is

$$\begin{aligned} \textrm{diam}(A) = \max _{a,b\in A} d(a,b). \end{aligned}$$

The local diameter of A at a point $a\in A$ equals

$$\begin{aligned} \textrm{localDiam}(A,a) = \max _{b\in A} d(a,b). \end{aligned}$$

Definition 2.3

Given $r \ge 0$ and a metric space X the Vietoris–Rips complex $\textrm{VR}(X;r)$ is the simplicial complex with vertex set X, and with a finite subset $\sigma \subseteq X$ being a simplex whenever $\textrm{diam}(\sigma ) \le r$.

This is the closed Vietoris–Rips complex, since we are using the convention $\le$ instead of <. But, since the metric spaces $Q_n$ are finite, all of our results have analogues if one instead considers the open Vietoris–Rips complex that uses the < convention.

In [4] it was proven that $\textrm{VR}(Q_n;2)$ is homotopy equivalent to a wedge sum of 3-dimensional spheres. A remark regarding notation is that we write either $\bigvee ^k X$ or $\displaystyle \bigvee _k X$ for the k-fold wedge some of the space X with itself, with the prior notation being used in-line (see Tables 1 and 2), and with the latter notation being used in displayed equations, especially when k is a complicated formula (see Theorems 2.4 and 2.5).

Theorem 2.4

(Theorem 1 of [4]) For $n\ge 3$, we have the homotopy equivalence

$$\begin{aligned} \textrm{VR}(Q_n;2) \simeq \bigvee _{c_n} S^3, \text { where } c_n= \sum _{0 \le j< i < n}(j+1)(2^{n-2}- 2^{i-1}). \end{aligned}$$

See [21] for some relationships between this result and generating functions.

In [14], it was proven that $\textrm{VR}(Q_n;3)$ is always homotopy equivalent to a wedge sum of 7-spheres and 4-spheres:

Theorem 2.5

(Theorem 24 of [14]) For $n\ge 5$, we have the homotopy equivalence

$$\begin{aligned} \textrm{VR}(Q_n;3) \simeq \bigvee _{2^{n-4}\left( {\begin{array}{c}n\\ 4\end{array}}\right) } S^7 \ \vee \bigvee _{\sum _{i=4}^{n-1} 2^{i-4} \left( {\begin{array}{c}i\\ 4\end{array}}\right) } S^4. \end{aligned}$$

2.4 Embeddings of Hypercubes

For k a positive integer, let $[k]=\{1,2,\ldots , k\}$. Given $p \in [n-1]$ there are many isometric copies of $Q_p$ in $Q_n$. For any subset $S \subseteq [n]$ of cardinality p we can isometrically embed $Q_p$ in $Q_n$, using set S as its variable coordinates, and leaving the rest of the entries fixed. In more detail, we define an isometric embedding $\iota _S^b :Q_p \hookrightarrow Q_n$ associated to a subset $S=\{s_1,s_2, \ldots , s_p\} \subseteq [n]$ of coordinates and an offset $(b_i)_{i\in [n]{\setminus } S} \in \{0,1\}^{n-|S|}$, by mapping $(a_i)_{i\in [p]}$ to $(a'_i)_{i\in [n]}$ with:

• $a'_{s_i}=a_i$ for $i\in [p]$, and

• $a'_i=b_i$ otherwise.

Given a fixed set S, there are $2^{n-p}$ such embeddings $\iota _S^b$, each associated to a different offset b. Let $\pi _S :Q_n \rightarrow Q_p$ be the map projecting onto the coordinates in S. Then $\pi _s \circ \iota _S = id_{Q_p}$ for any map $\iota _S$ (i.e., for any choice of an offset b). Given an offset $(b_i)_{i\in [n]\setminus S}$, let $Q_p^b$ denote the image of $\iota _S^b$ corresponding to the offset b, and let $\pi _S^b :Q_n \rightarrow Q_p^b$ be defined as $\iota _S^b \circ \pi _S$. Given $B \subseteq Q_n$ its cubic hull $\textrm{cHull}(B)$ is the smallest isometric copy of a cube (i.e., the image of $Q_{p'}$ via some map $\iota$) containing B.

For our purposes we will only consider isometric embeddings $Q_p \hookrightarrow Q_n$ (also denoted by $Q_p \le Q_n$) that retain the order of coordinates, although any permutation of coordinates of $Q_p$ results in a nonconstant isometry of $Q_p$ and thus a different isometric embedding into $Q_n$. With this convention of retaining the coordinate order, there are $\left( {\begin{array}{c}n\\ p\end{array}}\right) 2^{n-p}$ isometric embeddings $\iota :Q_p \hookrightarrow Q_n$ and $\left( {\begin{array}{c}n\\ p\end{array}}\right)$ projections $\pi :Q_n \rightarrow Q_p$.

3 Contractions and the Persistent Homology of Hypercubes

In this section we prove the following results. First, fix the scale $r\ge 0$, and let $p\le n$. An isometric embedding $Q_p \hookrightarrow Q_n$ gives an inclusion $\textrm{VR}(Q_p;r)\hookrightarrow \textrm{VR}(Q_n;r)$, which is injective on homology in all dimensions. Alternatively, fix dimension n, and consider integer scale parameters $r < r'$. The inclusion $\textrm{VR}(Q_n;r)\hookrightarrow \textrm{VR}(Q_n;r')$ is nullhomotopic, and hence the filtration $\textrm{VR}(Q_n;\bullet )$ has no persistent homology bars of length longer than one. These results follow from the properties of contractions, which we introduce now.

3.1 Contractions

A map $f :X \rightarrow A$ from a metric space (X, d) onto a closed subspace $A \subseteq X$ is a contraction if $f|_{A}=id_A$ and if $d(f(x),f(y)) \le d(x,y)$ for all $x,y\in X$.

Our interest in contractions stems from the fact that if a contraction $X \rightarrow A$ exists, then the homology of a Vietoris–Rips complex of A maps injectively into the homology of the corresponding Vietoris–Rips complex of X:

Proposition 3.1

([27]) If $f:X \rightarrow A$ is a contraction, then the embedding $A \hookrightarrow X$ induces injections on homology $H_q(\textrm{VR}(A;r))\rightarrow H_q(\textrm{VR}(X;r))$ for all integers $q\ge 0$ and scales $r\ge 0$.

We prove that the projections from a higher-dimensional cube to a lower-dimensional cube in Sect. 2.4 are contractions:

Lemma 3.2

Given a fixed $p\in [n-1]$, a set $S\subseteq [n]$ of cardinality p, and an offset b as in Sect. 2.4, the following hold:

• (1) The maps $\pi _S$ and $\pi _S^b$ are contractions.

• (2) For each $x\in Q_p^b$ and $y\in Q_n$, we have $d(x,y) = d(x, \pi _S^b(y)) + d(\pi _S^b(y),y)$.

• (3) For each offset $b'$:

  • (a) For each $x,y\in Q_p^{b'}$, we have $d(x,y)=d(\pi _p^b(x),\pi _p^b(y))$.

  • (b) For each $x\in Q_p^{b'}$ and $y\notin Q_p^{b'}$, we have $d(x,y) -1 \ge d(\pi _p^b(x),\pi _p^b(y)) \ge d(x,y) - (n-p)$.

Proof

For $x,y\in Q_n$, the distance d(x, y) is the number of components in which x and y differ. On the other hand, $d(\pi _S^b(x), \pi _S^b(y))$ is the number of components from S in which x and y differ (and the same holds for the map $\pi _S$ instead of $\pi _S^b$ as well). Thus $d(x,y) \le d(\pi _S^b(x), \pi _S^b(y))$ with:

• $d(x,y) = d(\pi _S^b(x), \pi _S^b(y))$ if $x,y\in Q_p^{b'}$ as their coordinates outside S agree, yielding (1) and (3)(a), and

• (3)(b) follows from the fact that for each $x\in Q_p^{b'}, y\notin Q_p^{b'}$, the number of coordinates outside of S on which x and y disagree is at least 1 (due to x, y not being in the same $Q_p^\bullet$) and at most $n-p$ (which is the cardinality of $[n]\setminus S$).

Item (2) follows from the observation that:

• $d(x, \pi _S^b(y))$ is the number of components from S in which x and y differ, and

• $d(\pi _S^b(y),y)$ is the number of components from $[n]\setminus S$ in which x and y differ, as $x\in Q_p^b$.

This completes the proof. $\square$

Since each of the projections $\pi :Q_n \rightarrow Q_p$ is a contraction by Lemma 3.2, Proposition 3.1 then implies that each of the embeddings $Q_p \hookrightarrow Q_n$ induces an injective map on homology $H_q(\textrm{VR}(Q_p;r)) \rightarrow H_q(\textrm{VR}(Q_n;r))$ for all dimensions q.

3.2 Persistent Homology of Hypercubes

The emphasis in modern topology is often on persistent homology arising from the Vietoris–Rips filtration. However, in the setting of Vietoris–Rips complexes of hypercubes, persistent homology does not provide any more information beyond the homology groups at fixed scale parameters. Indeed, the following proposition implies that for any integers $r < r'$, the inclusion $\textrm{VR}(Q_n;r) \hookrightarrow \textrm{VR}(Q_n;r+1)$ induces a map that is trivial on homology.

Proposition 3.3

For any positive integers n and r, the natural inclusion $\textrm{VR}(Q_n;r) \hookrightarrow \textrm{VR}(Q_n;r+1)$ is homotopically trivial.

Proof

We first claim that the inclusion $\textrm{VR}(Q_n;r) \hookrightarrow \textrm{VR}(Q_n;r+1)$ is homotopic to the projection $\pi _{[n-1]}:\textrm{VR}(Q_n;r) \rightarrow \textrm{VR}(Q_{n-1};r)$ in $\textrm{VR}(Q_n;r+1)$. In order to prove the claim we will show that the two maps are contiguous in $\textrm{VR}(Q_n;r+1)$ (i.e., for each simplex $\sigma \in \textrm{VR}(Q_n;r)$ the union $\sigma \cup \pi _{[n-1]}(\sigma )$ is contained in a simplex of $\textrm{VR}(Q_n;r+1)$), which implies that the two maps are homotopic.

Let $\sigma \in \textrm{VR}(Q_n;r)$. By definition $\textrm{diam}(\sigma )\le r$. As $\pi _{[n-1]}(\sigma )$ is obtained by dropping the final coordinate we also have $\textrm{diam}(\pi _{[n-1]}(\sigma ))\le r$. Taking $x\in \sigma$ and $y\in \pi _{[n-1]}(\sigma )$, i.e., $y=\pi _{[n-1]}(y')$ for some $y'\in \sigma$, we see that

$$\begin{aligned} d(x,y)\le d(x,y')+d(y',y) \le r + 1 \end{aligned}$$

as $d(y,y')\le 1$. This $\sigma \cup \pi _{[n-1]}(\sigma ) \in \textrm{VR}(Q_n;r+1)$, and the claim is proved.

We proceed inductively, proving that each projection $\pi _{[k]}:\textrm{VR}(Q_n;r) \rightarrow \textrm{VR}(Q_k;r)$ is homotopic to the projection $\pi _{[k-1]}:\textrm{VR}(Q_n;r) \rightarrow \textrm{VR}(Q_{k-1};r)$ in $\textrm{VR}(Q_n;r+1)$, by the same argument as above. As a result, the embedding $\textrm{VR}(Q_n;r) \hookrightarrow \textrm{VR}(Q_n;r+1)$ is homotopic to the projection $\pi _{\{1\}}:\textrm{VR}(Q_n;r) \rightarrow \textrm{VR}(Q_1;r)$. Since $\textrm{VR}(Q_1;r)$ is clearly contractible, this completes the proof. $\square$

4 Homology Bounds via Cross-Polytopes and Maximal Simplices

Fix a scale $r\ge 2$, and consider an isometric embedding $\iota :Q_{r+1} \hookrightarrow Q_n$ for $n\ge r+1$. The aim of this section is to prove not only that the induced map $\textrm{VR}(Q_{r+1};r)\hookrightarrow \textrm{VR}(Q_n;r)$ is injective on $(2^r-1)$-dimensional homology, but also that different (ordered) embeddings $\iota$ produce independent homology generators. Let us explain this in detail.

We first observe that $\textrm{VR}(Q_{r+1};r)$ is homeomorphic to a $(2^r-1)$-dimensional sphere, i.e., $\textrm{VR}(Q_{r+1};r) \cong S^{2^r-1}$. The reason is that each vertex $x \in Q_{r+1}$ is connected by an edge in $\textrm{VR}(Q_{r+1};r)$ to every vertex of $Q_{r+1}$ except for $\bar{x}$, the antipodal vertex. Therefore, after taking the clique complex of this set of edges, we see that $\textrm{VR}(Q_{r+1};r)$ is isomorphic (as simplicial complexes) to the boundary of the cross-polytope with $2^{r+1}$ vertices. This cross-polytope is a $2^r$-dimensional ball in $2^r$-dimensional Euclidean space, and therefore its boundary is a sphere of dimension $2^r-1$. In particular, $\textrm{rank}H_{2^r-1}( \textrm{VR}(Q_{r+1};r))=1$.

Since $\textrm{VR}(Q_{r+1};r)$ is the boundary of a cross-polytope, there is a convenient $(2^r -1)$-dimensional cycle $\gamma$ generating $H_{2^r-1}( \textrm{VR}(Q_{r+1};r))$. Define the set of maximal antipode-free simplices as

$$\begin{aligned} \mathcal {A}_r = \{Y \subseteq Q_{r+1} \mid x \in Y \Leftrightarrow \bar{x} \notin Y\}. \end{aligned}$$

The cycle $\gamma$ is defined as the sum of appropriately oriented elements of $\mathcal {A}_r$. The space $Q_{r+1}$ consists of $2^{r+1}$ points, which can be partitioned into $2^r$ pairs of mutually antipodal points. If a subset of $Q_{r+1}$ contains exactly one point from each such pair, it is of cardinality $2^r$. Thus $\mathcal {A}_r$ consists of sets of cardinality $2^r$. Given $x\in Q_{r+1}$, the only element of $Q_{r+1}$ which disagrees with x on all $r+1$ coordinates is $\bar{x}$. As a result each element of $\mathcal {A}_r$ is of diameter at most r and thus a simplex of $\textrm{VR}(Q_{r+1};r)$. Observe also that any element of $\mathcal {A}_r$ is a maximal simplex of $\textrm{VR}(Q_{r+1};r)$: adding any point to such a simplex would mean the presence of an antipodal pair, and so the diameter would thus grow to $r+1$.

As explained above, the embeddings $\iota :Q_{r+1} \hookrightarrow Q_n$ induce injections on homology by Lemma 3.2 and Proposition 3.1. The fact that these embeddings give independent homology generators is formalized in the following statement, which is also the main result of this section.

Theorem 4.1

For $r \ge 2$,

$$\begin{aligned} \textrm{rank}H_{2^r-1}( \textrm{VR}(Q_{n};r)) \ge 2^{n-(r+1)}\left( {\begin{array}{c}n\\ r+1\end{array}}\right) . \end{aligned}$$

The proof will be provided at the conclusion of the section. Recall that $2^{n-(r+1)}\left( {\begin{array}{c}n\\ r+1\end{array}}\right)$ is the number of different (ordered) embeddings $\iota :Q_{r+1} \hookrightarrow Q_n$. We will use maximal simplices and the pairing between homology and cohomology in order to prove that these $2^{n-(r+1)}\left( {\begin{array}{c}n\\ r+1\end{array}}\right)$ different embeddings provide independent cross-polytopal generators for homology.

Proposition 4.2

Suppose K is a simplicial complex and $\sigma$ is a maximal simplex of dimension p in K. If there is a p-cycle $\alpha$ in K in which $\sigma$ appears with a nontrivial coefficient $\lambda$, then any representative p-cycle of $[\alpha ]$ also contains $\sigma$ with the same coefficient $\lambda$.

Proof

As $\sigma$ is maximal, the p-cochain mapping $\sigma$ to 1 and all other p-simplices to 0 is a p-cocycle denoted by $\omega _\sigma$. Utilizing the cap product we see that for each representative $\alpha '$ of $[\alpha ]$, the cap product $[\omega _\sigma ] \frown [\alpha '] = \lambda$ is the coefficient of $\sigma$ in $\alpha '$. $\square$

Remark 4.3

Proposition 4.2 could also be proved directly. If $\alpha$ and $\alpha '$ are homologous p-cycles, then their difference is a boundary of a $(p+1)$-chain. The latter cannot contain $\sigma$ since $\sigma$ is maximal; hence the coefficients of $\sigma$ in $\alpha$ and in $\alpha '$ coincide.

We emphasize the cohomological proof because we will use the cochain $\omega _\sigma$ again.

We next focus on the construction of maximal simplices of $\textrm{VR}(Q_{r+1};r)$ which are furthermore also maximal simplices in $\textrm{VR}(Q_{n};r)$. The following is a simple criterion identifying such a simplex as a maximal simplex in $\textrm{VR}(Q_{n};r)$; see Fig. 1. (We recall that the local diameter of $\sigma \subseteq Q_n$ at a point $w\in \sigma$ is defined as $\textrm{localDiam}(\sigma ,w) = \max _{z\in \sigma } d(w,z)$.)

Fig. 1

(Left) Subcube $Q_3$ with a maximal simplex $\sigma \in \textrm{VR}(Q_3;2)$ drawn in blue, illustrating Proposition 4.4, and also Lemma 4.5 when r is even. An inclusion of $\sigma$ in $Q_4$ also gives a maximal simplex $\iota _S^b(\sigma )\in \textrm{VR}(Q_4;2)$. (Right) Subcube $Q_4$ with a maximal simplex $\sigma \times \{0,1\}\in \textrm{VR}(Q_4;3)$ drawn in blue, illustrating Lemma 4.5 when r is odd

Proposition 4.4

Let $n\ge r+1$, let $S \subseteq [n]$, and let b be an associated offset. Let $\sigma \subseteq Q_{r+1}^b$, and suppose $\sigma \in \mathcal {A}_r$ as a subset of $Q_{r+1}$. If $\textrm{localDiam}(\sigma ,w) = r$ for all $w \in \sigma$, then $\sigma$ is a maximal simplex in $\textrm{VR}(Q_{n};r)$.

Proof

Assume a point $x\in Q_n\setminus \sigma$ is added to $\sigma$. We will show that this increases the diameter of $\sigma$ beyond r, by repeatedly using Lemma 3.2.

• If $\pi _S^b(x) \notin \sigma$ then $\overline{\pi _S^b(x)} \in \sigma$ and thus

  $$\begin{aligned} d(x,\overline{\pi _S^b(x)} ) = d(x,\pi _S^b(x)) + d(\pi _S^b(x),\overline{\pi _S^b(x)}) \ge 0 + (r+1) =r+1. \end{aligned}$$

• If $\pi _S^b(x) \in \sigma$ then $d(x,\pi _S^b(x)) \ge 1$, and also the local diameter assumption implies there exists $y\in \sigma$ with $d(\pi _S^b(x),y)=r$. Thus

  $$\begin{aligned} d(x,y ) = d(x,\pi _S^b(x)) + d(\pi _S^b(x),y) \ge 1 + r. \end{aligned}$$

Hence $\sigma$ is maximal in $\textrm{VR}(Q_n;r)$. $\square$

We now construct maximal simplices $\sigma$ in $\textrm{VR}(Q_{r+1};r)$ that, by Proposition 4.4, will remain maximal in $\textrm{VR}(Q _n;r)$. We recall that the cubic hull $\textrm{cHull}(\sigma )$ is the smallest isometric copy of a cube containing $\sigma$. That the convex hull of $\sigma$ is all of $Q_{r+1}$ will later be used to give the independence of homology generators in the proof of Theorem 4.1.

Lemma 4.5

If $r \ge 2$, then there exists a maximal simplex $\sigma \subseteq Q_{r+1}$ from $\mathcal {A}_r$ with $\textrm{localDiam}(\sigma ,y)=r$ for all $y \in \sigma$, and with $\textrm{cHull}(\sigma )=Q_{r+1}$.

Proof

We first prove the case when $r\ge 2$ is even (before afterward handling the case when $r\ge 3$ is odd). Define $\sigma$ as the collection of vertices in $Q_{r+1}$ whose coordinates contain an even number of values 1. As $r+1$ is odd, this means $x\in \sigma$ iff $\bar{x} \notin \sigma$, so $\sigma \in \mathcal {A}_r$.

We proceed by determining the local diameter. Let $y\in \sigma$ and define $y'$ by taking $\bar{y}$ and flipping one of its coordinates. Then $y' \in \sigma$ as it has an even number of ones, and it disagrees with y on all coordinates except the flipped one, hence $d(y,y')=r$. So $\textrm{localDiam}(\sigma ,y) = r$ for all $y\in \sigma$.

It remains to show that $\textrm{cHull}(\sigma )=Q_{r+1}$. If $\textrm{cHull}(\sigma ) \subsetneq Q_{r+1}$, there would be a single coordinate shared by all the points of $\sigma$. However, as $r \ge 2$ we can prescribe any single coordinate as we please and then fill in the rest of the coordinates to obtain a vertex of $\sigma$:

• if the chosen coordinate was 1, fill another coordinate as 1 and the rest as 0;

• if the chosen coordinate was 0, fill all other coordinates as 0.

Next, we handle the case when $r\ge 3$ is odd. Let $\tau$ be the maximal simplex in $Q_r$ obtained in the proof of the even case. Define

$$\begin{aligned} \sigma = \tau \times \{0,1\}\subseteq Q_{r+1}. \end{aligned}$$

Formally speaking, $\sigma = \iota _{[r]}^{(0)}(Q_r) \cup \iota _{[r]}^{(1)}(Q_r) = Q_r^{(0)} \cup Q_r^{(1)}$, with the associated index set being $S=[r]$. We first prove $\sigma \in \mathcal {A}_r$. A point $x\in \sigma$ is of the form $x=y \times \{i\}$ with $y\in \tau , i\in \{0,1\}$. As $\bar{x} = \bar{y} \times \{1-i\}$ and $y\in \mathcal {A}_{r-1}$, we see that $x\in \sigma$ iff $\bar{x} \notin \sigma$.

We proceed by determining the local diameter. Take $x=y \times \{i\} \in \sigma$. As $\textrm{localDiam}(\tau ,y)=r-1$, there exists $y'\in \tau$ with $d(y,y')=r-1$. But then $y' \times \{1-i\} \in \sigma$ and $d\left( y \times \{i\},y' \times \{1-i\}\right) =r$.

It remains to show that $\textrm{cHull}(\sigma )=Q_{r+1}$. Similarly as in the proof of the even case, this follows from the fact that as $r \ge 3$ we can prescribe any single coordinate as we please, and then fill in the rest of the coordinates to obtain a vertex of $\sigma$:

• the last coordinate can be chosen freely by the construction of $\sigma$;

• any of the first r coordinates can be chosen freely by the construction and by the even case.

$\square$

We are now in position to prove the main result of this section, Theorem 4.1, which states that $\textrm{rank}H_{2^r-1}( \textrm{VR}(Q_{n};r)) \ge 2^{n-(r+1)}\left( {\begin{array}{c}n\\ r+1\end{array}}\right)$.

Proof of Theorem 4.1

For notational convenience, let $k = 2^{n-(r+1)}\left( {\begin{array}{c}n\\ r+1\end{array}}\right)$. There are k isometric copies of $Q_{r+1}$ in $Q_n$ obtained via embeddings $\iota$, which we enumerate as $C_1, C_2, \ldots , C_{k}$. For each i:

• (1) Let $\sigma _i$ be the maximal simplex in $C_i$ obtained from Proposition 4.4 and Lemma 4.5.

• (2) Let $[\alpha _i]$ be the mentioned cross-polytopal generator of $H_{2^r -1}(\textrm{VR}(C_i;r))$, and recall the coefficient of $\sigma _i$ in $\alpha _i$ is 1.

• (3) Let $\omega _i$ be the $(2^r - 1)$-cochain on $Q_n$ mapping $\sigma _i$ to 1 and the rest of the $(2^r-1)$-dimensional simplices to 0. As $\sigma _i$ is a maximal simplex in $Q_n$, the cochains $\omega _i$ are cocycles.

• (4) Note that $\sigma _i$ is not contained as a term in $\alpha _j$ for any $i \ne j$. Indeed, if that was the case, $\sigma _i$ would be contained in the lower-dimensional cube $C_i \cap C_j$, contradicting the conclusion $\textrm{cHull}(\sigma )=Q_{r+1}$ from Lemma 4.5. As a result, $[\omega _i] \frown [\alpha _i]=1$ and $[\omega _i] \frown [\alpha _j]=0$ for $i \ne j$.

It remains to prove that the homology classes $[\alpha _i]$ in $H_{2^r-1}( \textrm{VR}(Q_{n};r))$ (via the natural inclusion) are linearly independent. If $\sum _{i=1}^{k} \lambda _i [\alpha _i]=0$ for some $\lambda _i \in \mathbb {Z}$, then applying $[\omega _j]$ via the cap product we obtain $\lambda _j=0$ by (4) above. Hence the rank of $H_{2^r-1}( \textrm{VR}(Q_{n};r))$ is at least $k=2^{n-(r+1)}\left( {\begin{array}{c}n\\ r+1\end{array}}\right)$. $\square$

5 More Contractions: Concentrations

Up to now the only contractions that we have utilized are the projections $\pi _S$. In order to establish additional homology bounds we need to employ a new kind of contraction called concentration. The idea of such maps in low-dimensional settings is shown in Figs. 2 and 3. We proceed with an explanation of the general case.

Fig. 2

Two contractions on $Q_2$: a projection $\pi _{[1]}$ and a concentration map

Let $n > k$ be positive integers. Choose $a=(a_{k+1}, a_{k+2}, \ldots , a_n) \in \{0,1\}^{n-k}$ and let C denote the copy of $Q_k$ identified as $Q_k^a$, i.e.,

$$\begin{aligned} C= \{0,1\}^k \times \{a_{k+1}\} \times \{a_{k+2}\} \times \ldots \times \{a_{n}\}. \end{aligned}$$

Working toward a contraction we define a concentration map $f:Q_n \rightarrow C$ of codimension $n-k$ by the following rule:

• (1) $f|_C = \text {Id}_C$, and

• (2) for $x=(x_1, x_2, \ldots , x_n)\in Q_n \setminus C$ we define

  $$\begin{aligned} f(x)=(x_1, x_2, \ldots , x_{k-1}, 1, a_{k+1}, a_{k+2}, \ldots , a_n). \end{aligned}$$

In particular, we concentrate the k-th coordinate of $Q_n {\setminus } C$ to 1 (although we might as well have used 0). Permuting the coordinates of $Q_n$ generates other concentration maps. In order to discuss the properties of concentration functions it suffices to consider the concentrations defined as f above.

Fig. 3

Two concentrations of codimension one. In both cases there are two codimension one subcubes that are being mapped isometrically (the thick $Q_1$ on the left and the shaded $Q_2$ on the right). On the left we have $n=2$, $k=1$, and $a_2=0$, and on the right we have $n=3$, $k=2$, and $a_3=0$

Proposition 5.1

Let f be the concentration map as defined above. Then the following hold.

• (i) The map f is a contraction.

• (ii) The $n-k+1$ many k-dimensional cubes $Q_{k}\subseteq Q_n$ containing the $(k-1)$-dimensional cube

  $$\begin{aligned} \{0,1\}^{k-1} \times \{0\} \times \{a_{k+1}\} \times \{a_{k+2}\} \times \ldots \times \{a_{n}\} \end{aligned}$$

  are mapped onto C isometrically by f.

• (iii) The map f maps all other k-dimensional cubes $Q_{k}\subseteq Q_n$ onto cubes of dimension less than k.

Proof

(i) We verify the claim by a case analysis.

For $x,y\in C$ we have

$$\begin{aligned} d(f(x),f(y))=d(x,y) \end{aligned}$$

as f is the identity on C.

For $x,y\notin C$ the quantity d(x, y) is the number of coordinates in which x and y differ, while d(f(x), f(y)) is the number of coordinates among the first $k-1$ in which x and y differ. Thus $d(f(x),f(y)) \le d(x,y)$.

Let $x\in C, y\notin C$. Then d(x, y) is the sum of the following two numbers:

• the number of coordinates among the first k coordinates in which x and y differ;

• the number of coordinates among the last $n-k$ coordinates in which x and y differ. Note that this quantity is at least 1 as $y \notin C$.

On the other side, d(f(x), f(y)) is less than or equal to the sum of the following two numbers:

• the number of coordinates among the first $k-1$ coordinates in which x and y differ;

• the number 1 if the k-th coordinate of x does not equal 1.

Together we obtain $d(f(x),f(y)) \le d(x,y)$.

This covers all possible cases. We conclude that f is a contraction.

(ii) The $n-k+1$ copies of $Q_k$ in question are the ones of the form

$$\begin{aligned} \{0,1\}^{k-1} \times \{0\} \times \{a_{k+1}\} \times \{a_{k+2}\} \times \ldots \times \{a_{p-1}\} \times \{0,1\} \times \{a_{p+1}\} \times \ldots \times \{a_{n}\} \end{aligned}$$

for $p\in \{k, k+1, \ldots , n\}$. The case $p=k$ shows that C is one of these copies. Note that the part

$$\begin{aligned} \{0,1\}^{k-1} \times \{0\} \times \{a_{k+1}\} \times \{a_{k+2}\} \times \ldots \times \{a_{p-1}\} \times \{a_p\} \times \{a_{p+1}\} \times \ldots \times \{a_{n}\} \end{aligned}$$

is contained in C and thus f is the identity on it. On the other hand, the part

$$\begin{aligned} \{0,1\}^{k-1} \times \{0\} \times \{a_{k+1}\} \times \{a_{k+2}\} \times \ldots \times \{a_{p-1}\} \times \{1- a_p\} \times \{a_{p+1}\} \times \ldots \times \{a_{n}\} \end{aligned}$$

gets mapped to

$$\begin{aligned} \{0,1\}^{k-1} \times \{1\} \times \{a_{k+1}\} \times \{a_{k+2}\} \times \ldots \times \{a_{p-1}\} \times \{a_p\} \times \{a_{p+1}\} \times \ldots \times \{a_{n}\} \end{aligned}$$

by retaining the first $k-1$ coordinates. Together these two parts form C.

(iii) Any k-dimensional cube $Q_{k}\subseteq Q_n$ not mentioned in (2) has one of the first $k-1$ coordinates (say, the p-th coordinate) constant. Thus the same holds for its image via f and consequently, its image is contained in the corresponding $Q_{k-1}\subseteq Q_n$, i.e., the one having the p-th coordinate constant, and having the last $n-k$ coordinates prescribed as in C. $\square$

6 Homology Bounds via Contractions

In Sect. 4 we showed how the appearance of cross-polytopal homology classes in certain dimensions of the Vietoris–Rips complexes of cubes generate independent homology elements in Vietoris–Rips complexes of higher-dimensional cubes. Applying Proposition 3.1 to the canonical projections implies that the homology of each smaller subcube embeds. However, the independence of homology classes arising from various subcubes was proved using maximal simplices; this argument depended heavily on the fact that convenient (cross-polytopal) homology representatives were available to us. In this section we aim to provide an analogous result for homology in any dimension, without prior knowledge of homology generators.

Fig. 4

(Left) The projection onto the front bottom $Q_1$ isometrically identifies the four bold copies of $Q_1$ and sends other copies of $Q_1$ to a point. (Right) The concentration onto the bottom left $Q_1$, mapping all hollow-square vertices to the solid square vertex, isometrically identifies the three bold copies of $Q_1$ and sends the other copies of $Q_1$ to a point. In this case the concentration is of codimension 2, i.e., maps $Q_3 \rightarrow Q_1$. As the codimension t increases, the number of isometrically identified subcubes is exponential $2^t$ for projections and linear $t+1$ for concentrations. The exponential increase leads to a weaker lower bound in Theorem 6.2 than the linear increase in Theorems 6.3 and 6.4

Example 6.1

As a motivating example, consider the graph $\textrm{VR}(Q_3;1)$. The cube $Q_3$ contains six subcubes $Q_2$ and each $\textrm{VR}(Q_2;1)\simeq S^1$ has the first Betti number equal to 1. However, the first Betti number of $Q_3$ is not 6 but rather 5, demonstrating that homology classes of various subcubes might in general interfere, i.e., not be independent. In Theorem 4.1 we proved there is no such interference in a specific case (involving cross-polytopes). In the more general case of this section, we prove lower bounds even when independence may not hold.

The general setting of this section: Fix $r, q\in \{1,2,\ldots \}$. Let $p\ge 1$ be the smallest integer for which $H_q(\textrm{VR}(Q_p;r))\ne 0$. We implicitly assume that such a p exists, i.e., that $H_q(\textrm{VR}(Q_n;r))$ is nontrivial for some n.

The cube $Q_n$ contains $2^{n-p} \left( {\begin{array}{c}n\\ p\end{array}}\right)$ canonical $Q_p$ subcubes, which are described in Sect. 2.4 by the inclusions $\iota _S^b :Q_p \hookrightarrow Q_n$ associated to a subset $S=\{s_1,s_2, \ldots , s_p\} \subseteq [n]$ of coordinates and an offset $(b_i)_{i\in [n]{\setminus } S} \in \{0,1\}^{n-|S|}$. We aim to estimate the rank of the homomorphism

$$\begin{aligned} \bigoplus _{{2^{n-p} \left( {\begin{array}{c}n\\ p\end{array}}\right) }} H_q(\textrm{VR}(Q_p;r)) \rightarrow H_q(\textrm{VR}(Q_n;r)) \end{aligned}$$

induced by the map

$$\begin{aligned} \coprod _{2^{n-p} \left( {\begin{array}{c}n\\ p\end{array}}\right) } Q_p \rightarrow Q_n, \end{aligned}$$

consisting of the natural inclusions $\iota _S^b$ of the disjoint union of the $Q_p$ subcubes.

6.1 Homology Bounds via Projections

We will start with the simplest argument to demonstrate how contractions, in this case projections, may be used to lower bound the homology.

Theorem 6.2

Let $q\ge 1$. If p is the smallest integer for which $H_q(\textrm{VR}(Q_p;r))\ne 0$, then for $n \ge p$,

$$\begin{aligned} \textrm{rank}H_{q}( \textrm{VR}(Q_{n};r)) \ge \left( {\begin{array}{c}n\\ p\end{array}}\right) \cdot \textrm{rank}H_{q}( \textrm{VR}(Q_{p};r)). \end{aligned}$$

Proof

Let $Q_p^\bullet$ denote the $\left( {\begin{array}{c}n\\ p\end{array}}\right) 2^{n-p}$ different p-dimensional subcubes of $Q_n$ (say as $\bullet$ varies from 1 to $\left( {\begin{array}{c}n\\ p\end{array}}\right) 2^{n-p}$). For a subset $S \subseteq [n]$ of cardinality p, define the projection $\pi _S :Q_n \rightarrow Q_p$ by omitting the coordinates not in S. The map $\pi _S$ is an isometry on $2^{n-p}$ of the subcubes $Q_p^\bullet$ (the ones having exactly the coordinates S as the free coordinates). For each such S choose one of these cubes and designate it as $Q_{p,S}$, thus marking $\left( {\begin{array}{c}n\\ p\end{array}}\right)$ copies of $Q_{p,S} \subseteq Q_n$. For each S let $a_{1,S}, a_{2,S}, \ldots , a_{\textrm{rank}H_{q}( \textrm{VR}(Q_{p};r)),S}$ denote a largest linearly independent collection in $H_{q}( \textrm{VR}(Q_{p,S};r))$. We claim that the collection $\{a_{i,S}\}$ of cardinality $\left( {\begin{array}{c}n\\ p\end{array}}\right) \cdot \textrm{rank}H_{q}( \textrm{VR}(Q_{p};r))$ is linearly independent in $H_{q}( \textrm{VR}(Q_{n};r))$.

Assume

$$\begin{aligned} \sum _{i,S}\lambda _{i,S} \cdot a_{i,S}=0 \end{aligned}$$

for some coefficients $\lambda _{i,S}$. Fix a subset $S' \subseteq [n]$ of cardinality p, and to the equality above apply the map on $H_q$ induced by the projection $\pi _{S'}:Q_n \rightarrow Q_p$. As p is the minimal dimension of a cube in which $H_q$ is nontrivial on Vietoris–Rips complexes, and as $\pi _{S'}$ maps all of the $Q_p^\bullet$ to a smaller-dimensional cube except for the ones with exactly the coordinates in $S'$ as the free coordinates, we obtain $(\pi _{S'})_*(a_{i,S})=0$ for all $S \ne S'$, where $*$ denotes the induced map on homology. As $\pi _{S'}|_{Q_{p,S'}}\rightarrow Q_p$ is a bijection on the corresponding Vietoris–Rips complexes and induces an isomorphism homology, we have reduced our equation to

$$\begin{aligned} \sum _{i}\lambda _{i,S'} \cdot a_{i,S'}=0. \end{aligned}$$

Consequently, $\lambda _{i,S'}=0$ for all i, as $\{a_{i,S'}\}$ forms a linearly independent collection in $H_{q}( \textrm{VR}(Q_{p};r))$ by definition. As $S'$ was arbitrary we conclude $\lambda _{i,S}=0$ for all i and S, and thus the claim holds. $\square$

6.2 Codimension 1 Homology Bounds via Concentrations

The following result states that in codimension 1 (i.e., when we increase the dimension of the cube by 1 from p to $p+1$), all but at most one of the subcubes induce independent inclusions on homology. Example 6.1 shows that all subcubes need not induce independent inclusions of homology (and we see that Theorem 6.3 is tight in the case of Example 6.1).

Theorem 6.3

Let $q\ge 1$. If p is the smallest integer for which $H_q(\textrm{VR}(Q_p;r))\ne 0$, then

$$\begin{aligned} \textrm{rank}H_{q}( \textrm{VR}(Q_{p+1};r)) \ge (2p+1) \cdot \textrm{rank}H_{q}( \textrm{VR}(Q_{p};r)). \end{aligned}$$

Proof

The cube $Q_{p+1}$ contains $2p+2$ subcubes $Q_p$, which we enumerate as $Q_{p,1}, Q_{p,2}, \ldots , Q_{p,2p+2}$. For each $1 \le j \le 2p+1$, let $\{a_{i,j} \mid 1\le i \le \textrm{rank}H_{q}( \textrm{VR}(Q_{p};r))\}$ denote a largest linearly independent collection in $H_{q}( \textrm{VR}(Q_{p,j};r))$. We claim that the collection

$$\begin{aligned} \left\{ a_{i,j}\mid 1\le i \le \textrm{rank}H_{q}( \textrm{VR}(Q_{p};r)), 1\le j\le 2p+1\right\} \end{aligned}$$

of cardinality $(2p+1)\cdot \textrm{rank}H_{q}( \textrm{VR}(Q_{p};r))$ is linearly independent.

Assume

$$\begin{aligned} \sum _{i,j}\lambda _{i,j} \cdot a_{i,j}=0 \end{aligned}$$

(1)

for some coefficients $\lambda _{i,j}$ with $1\le i \le \textrm{rank}H_{q}( \textrm{VR}(Q_{p};r))$ and $1\le j\le 2p+1$. Note that there are no representatives from $Q_{p,2p+2}$. Choose a subcube $Q_{p-1}\subseteq Q_{p,2p+2}$. It is the intersection of $Q_{p,2p+2}$ and another p-dimensional cube of the form $Q_{p,*}$, say $Q_{p,1}$. We apply the concentration map f corresponding to these choices using Proposition 5.1. Then, we get the following.

• (i) f is bijective on exactly two p-cubes: $Q_{p,2p+2}$ and $Q_{p,1}$.

• (ii) f maps all other p-cubes to cubes of dimension less than p. By the choice of p (as the first dimension of a cube in which nontrivial p-dimensional homology appears in its Vietoris–Rips complex), we get $f_*(a_{i,j})=0$ for all $i>1$.

• (iii) As a result, after applying the induced map $f_*$ on homology, Equation (1) simplifies to

  $$\begin{aligned} \sum _{j}\lambda _{j} \cdot a_{1,j}=0. \end{aligned}$$

  Consequently, $\lambda _{1,j}=0$ for all i, as $\{a_{1,j}\}$ forms a linearly independent collection in $H_{q}( \textrm{VR}(Q_{p,1};r))$ by definition.

We keep repeating the procedure of the previous paragraph.

• Choose a subcube $Q_{p,j}$, whose corresponding coefficients $\lambda _{i,j}$ have been determined to be zero, and choose a neighboring subcube $Q_{p,j'}$ (i.e., a subcube with a common $(p-1)$-dimensional cube), whose corresponding coefficients $\lambda _{i,j'}$ have not yet been determined to be zero.

• Apply the concentration map corresponding to these two p-dimensional cubes to deduce that the coefficients $\lambda _{i,j'}$ also equal zero.

Any cube $Q_{p,j'}$ can be reached from $Q_{p,2p+2}$ by an appropriate sequence of cubes (i.e., $Q_{p,2p+2}$, a $(p-1)$-dimensional subcube thereof, an enclosing p-dimensional cube, a $(p-1)$-dimensional subcube thereof, $\ldots , Q_{p,j'}$). Therefore, we can eventually deduce that $\lambda _{i,j}=0$ for all i and j. Hence the rank bound holds due to the setup of Equation (1). $\square$

6.3 General Homology Bounds via Concentrations

In this subsection we will generalize the argument of Theorem 6.3 to deduce a lower bound on homology on all subsequent larger (not just codimension one) cubes.

The core idea is the following. In the previous subsection we were able to “connect” p-dimensional cubes by concentrations. Each chosen concentration was bijective on exactly two adjacent cubes of the form $Q_p$ sharing a common $(p-1)$-dimensional cube; see item (i) in the proof of Theorem 6.3. If the coefficients of Equation (1) corresponding to one of the two copies of $Q_p$ were known to be trivial, then the homological version of said concentration transformed Equation (1) so that only the coefficients corresponding to the other of the two cubes $Q_p$ were retained; see item (ii). These coefficients were then deduced to be trivial by their definition as the resulting equation contained only terms arising from a single $Q_p$, see item (iii).

In this subsection we generalize this argument to all higher-dimensional cubes. Instead of concentrations isolating 2 adjacent copies of $Q_p$ (as happens in codimension 1), the concentrations will in general isolate $n-p+1$ (i.e., codimension plus one; see Proposition 5.1(ii)) copies of $Q_p$. The main technical question is thus to determine how many of the subcubes are independent in the above sense.

Theorem 6.4

Let $q\ge 1$. If p is the smallest integer for which $H_q(\textrm{VR}(Q_p;r))\ne 0$, then for $n \ge p$,

$$\begin{aligned} \textrm{rank}H_{q}( \textrm{VR}(Q_{n};r)) \ge \sum _{i=p}^n 2^{i-p} \left( {\begin{array}{c}i-1\\ p-1\end{array}}\right) \cdot \textrm{rank}H_{q}( \textrm{VR}(Q_{p};r)). \end{aligned}$$

In particular cases, Theorem 6.4 reduces to the following. For $n=p$ we get the tautology that $\textrm{rank}H_{q}( \textrm{VR}(Q_{p};r))$ is at least as large as itself. For $n=p+1$ we recover Theorem 6.3:

$$\begin{aligned} \textrm{rank}H_{q}( \textrm{VR}(Q_{n};r))&\ge \textrm{rank}H_{q}( \textrm{VR}(Q_{p};r))+ 2 \left( {\begin{array}{c}p\\ p-1\end{array}}\right) \cdot \textrm{rank}H_{q}( \textrm{VR}(Q_{p};r)) \\&= (2p+1)\cdot \textrm{rank}H_{q}( \textrm{VR}(Q_{p};r)). \end{aligned}$$

Fig. 5

A sketch of the proof of Theorem 6.4. In each step the thick dashed lines represent copies of $Q_p$ in $M_n$ yielding new independent homology classes within the Vietoris–Rips complex of $Q_n$, in addition to the established independent homology classes (thick solid lines) arising from certain copies of $Q_p$, denoted by $F_n$, within the front face $Q_{n-1}^1$. The multiplicative factor in the theorem is the total number of the thick edges, both dashed and solid ones

Proof of Theorem 6.4

The cube $Q_n$ consists of two disjoint copies of $Q_{n-1}$; see Fig. 5:

• the rear one with the last coordinate 0, denoted by $Q_{n-1}^0$, and

• the front one with the last coordinate 1, denoted by $Q_{n-1}^1$.

We partition the $Q_p$ subcubes of $Q_n$ into three classes:

• The ones contained in the rear $Q_{n-1}^0$ where vertices have last coordinate 0, denoted by $R_n$.

• The ones contained in the front $Q_{n-1}^1$ where vertices have last coordinate 1, denoted by $F_n$.

• The ones contained in the middle passage between them, denoted by $M_n$. Each such $Q_p$ in $M_n$ is of the form $D \times \{0,1\}$, where $D \subseteq Q_{n-1}$ is a copy of $Q_{p-1}$.

We will prove that the following $Q_p$ subcubes of $Q_n$ induce independent embeddings on homology $H_q$ of Vietoris–Rips complexes: the elements of $M_n$ (dashed cubes in Fig. 5) and the elements of $F_n$ that have inductively been shown to include independent embeddings on homology $H_q$ of Vietoris–Rips complexes on $Q^1_{n-1}$ (bold cubes in Fig. 5). The initial cases of the inductive process have been discussed in the paragraph before the proof. For $n=p+1$ this is Theorem 6.3.

The cardinality of $M_n$ is $2^{(n-1)-(p-1)} \left( {\begin{array}{c}n-1\\ p-1\end{array}}\right) = 2^{n-p} \left( {\begin{array}{c}n-1\\ p-1\end{array}}\right)$, which is the number of $Q_{p-1}$ subcubes in $Q_{n-1}^0$. Each such subcube has the last coordinate constantly 0. Taking a union with a copy of the same $Q_{p-1}$ subcube with the last coordinates changed to 1, we obtain a $Q_p$ subcube in $M_n$. It is apparent that all elements of $M_n$ arise this way. Let us enumerate the elements of $M_n$ as $Q_{p,j}^M$ with $1\le j \le 2^{n-p} \left( {\begin{array}{c}n-1\\ p-1\end{array}}\right)$. For each such j let $\{a_{i,j}\mid 1\le i \le \textrm{rank}H_{q}( \textrm{VR}(Q_{p};r))\}$ denote a largest linearly independent collection in $H_{q}( \textrm{VR}(Q_{p,j}^M;r))$.

The cardinality of the copies of $Q_p$ in $F_n$ that have inductively been shown to include independent embeddings on homology $H_q$ of Vietoris–Rips complexes on $Q^1_{n-1}$ equals $\sum _{i=p}^{n-1} 2^{i-p} \left( {\begin{array}{c}i-1\\ p-1\end{array}}\right)$, by inductive assumption. Let us enumerate them by $Q_{p,j}^F$ with $1\le j\le \sum _{i=p}^{n-1} 2^{i-p} \left( {\begin{array}{c}i-1\\ p-1\end{array}}\right)$. For each such j let $\{b_{i,j} \mid 1\le i\le \textrm{rank}H_{q}( \textrm{VR}(Q_{p};r))\}$ denote a largest linearly independent collection in $H_{q}( \textrm{VR}(Q_{p,j}^F;r))$.

Assuming the equality

$$\begin{aligned} \sum _{i,j}\lambda _{i,j} \cdot a_{i,j} + \sum _{i,j}\mu _{i,j} \cdot b_{i,j}=0 \end{aligned}$$

(2)

in $H_{q}( \textrm{VR}(Q_{n};r))$ for some coefficients $\lambda _{i,j}$, $\mu _{i,j}$, we claim that all coefficients equal zero. This will prove the theorem as the number of involved terms equals $\sum _{i=p}^n 2^{i-p} \left( {\begin{array}{c}i-1\\ p-1\end{array}}\right) \cdot \textrm{rank}H_{q}( \textrm{VR}(Q_{p};r))$.

We will first prove that the coefficients $\lambda _{i,j}$ are all zero. Fix some $1\le j \le 2^{n-p} \left( {\begin{array}{c}n-1\\ p-1\end{array}}\right)$, and let D be the copy of $Q_{p-1}$ in $Q_{n-1}^0$ so that $C:= D \times \{0,1\}$ is equal to $Q_{p,j}^M$. Let f be any concentration $Q_n \rightarrow C:=D \times \{0,1\}$. (For example, in Fig. 4 one can visualize D as the solid round vertex, and C as the edge between the two solid vertices.) By Proposition 5.1:

• f maps any $Q_p$ subcube of $Q_n$ that contains D bijectively onto $C=Q_{p,j}^M$. All such subcubes except for C are contained in $R_n$.

• f maps all of the other $Q_p$ subcubes of $Q_n$ to lower-dimensional subcubes.

These two observations imply that applying the induced map $f_*$ on homology to Equation (2), we obtain $\sum _{i}\lambda _{i,j} \cdot a_{i,j}=0.$ By the choice of $\{a_{i,j}\}_i$ as an independent collection of homology classes for $H_{q}(\textrm{VR}(Q_{p,j}^M;r))$, we obtain $\lambda _{i,j}=0$ for all i. Since this can be done for any $1\le j \le 2^{n-p} \left( {\begin{array}{c}n-1\\ p-1\end{array}}\right)$, we have $\lambda _{i,j}=0$ for all i and j.

We have thus reduced Equation (2) to $\sum _{i,j}\mu _{i,j} \cdot b_{i,j}=0.$ Let $\pi _S :Q_n \rightarrow Q_{n-1}$ be the projection that forgets the last coordinate of each vector (explicitly, $S=[n-1]\subseteq [n]$). Note that the restrictions of $\pi _S$ to $Q_n^0$ and to $Q_n^1$ are bijections. Hence, after applying the induced map $(\pi _S)_*$ on homology, the inductive definition of the $b_{i,j}$ implies that $\mu _{i,j}=0$ for all i and j.

$\square$

6.4 Comparison with Known Results

In this subsection we demonstrate that our lower bounds agree with actual ranks of homology in many known cases. In particular, for $r=1,2,3$, if we assume that we know the homotopy types or Betti numbers for the first few cases ($n\le r+1$ or $n \le r+2$), then we show that our lower bounds on the Betti numbers of $\textrm{VR}(Q_n;r)$ are tight (i.e., optimal) for all n and for all dimensions of homology. For $r=4$ we explain the best lower bounds we know on the Betti numbers of $\textrm{VR}(Q_n;4)$, which are based on homology computations by Ziqin Feng. Since the homotopy types of $\textrm{VR}(Q_n;4)$ are unknown for $n\ge 6$, we do not know if these bounds are tight. For a summary see Table 2.

6.4.1 The Case $\mathbf {r=1}$

Assuming the obvious homeomorphism $\textrm{VR}(Q_2;1) \cong S^1$, the lower bound of Theorem 6.4 with $p=2$ gives

$$\begin{aligned} \textrm{rank}H_1(\textrm{VR}(Q_n;1)) \ge \sum _{i=2}^n 2^{i-2} \left( {\begin{array}{c}i-1\\ 1\end{array}}\right) =\sum _{i=2}^n (i-1) 2^{i-2} =n 2^{n-1} - 2^n + 1, \end{aligned}$$

where the last step is explained in Appendix A.1. This inequality is actually an equality, as one can see via an Euler characteristic computation. Indeed, $\textrm{VR}(Q_n;1)$ has $2^n$ vertices and $n2^{n-1}$ edges, and so the Euler characteristic is $2^n - n2^{n-1}$. As $\textrm{VR}(Q_n;1)$ is connected, the rank of $H_1(\textrm{VR}(Q_n;1))$ equals $n 2^{n-1} - 2^n + 1$. See [10, Proposition 4.12] for a related computation.

6.4.2 The Case $\mathbf {r=2}$

We know that the embedding of each individual subcube induces an injection on homology. Our results provide the lower bounds on the rank of the map on homology induced by the inclusion of all subcubes $Q_p$ (where p is the dimension of the first appearance of q-dimensional homology $H_q$). The upper bound for homology obtained in this way is $2^{n-p}\left( {\begin{array}{c}n\\ p\end{array}}\right) \textrm{rank}H_q(\textrm{VR}(Q_p;r))$, where the multiplicative constant is the number of all $Q_p$ subcubes on $Q_n$. These possible generators are all independent in the case of cross-polytopal generators (Theorem 4.1). In case this bound is exceeded we can thus deduce that certain new homology classes appear that are not generated by the embeddings of $Q_p$ subcubes.

Table 2 For each of $r=1,2,3,4$, the pair of columns represent the comparison between (left) known homotopy types and homology groups of $\textrm{VR}(Q_n;r)$ with (right) the bounds arising from our results

In the case $r=2$, $H_{3}( \textrm{VR}(Q_{3};2))$ has rank one and is generated by a cross-polytopal element. Even though $Q_4$ has only $2 \left( {\begin{array}{c}4\\ 1\end{array}}\right) =8$ subcubes $Q_3$, we have $\textrm{rank}H_{3}( \textrm{VR}(Q_{4};2))=9>8$. This indicates the appearance of a homology class $\alpha$ not generated by embedded homologies of $Q_3$ subcubes; see Sect. 7 for a description of this “geometric” generator. This new homology class contributes to the homology of higher-dimensional cubes in the same way as the homology described by Theorem 6.4. We formalize this in the next subsection; see Theorem 6.5. Together, this cross-polytopal generator and this geometric generator $\alpha$ explain all of the homology when $r=2$:

• (a) The cross-polytopal elements provide $2^{n-3} \left( {\begin{array}{c}n\\ 3\end{array}}\right)$ independent generators for $H_{3}( \textrm{VR}(Q_{n};2))$ (Theorem 4.1).

• (b) The noncross-polytopal element $\alpha$ provides $\sum _{i=4}^n 2^{i-4} \left( {\begin{array}{c}i-1\\ 3\end{array}}\right) =\sum _{i=3}^{n-1} 2^{i-3} \left( {\begin{array}{c}i\\ 3\end{array}}\right)$ more independent generators for $H_{3}( \textrm{VR}(Q_{n};2))$ (Theorem 6.5).

Thus, the combined lower bound says that the rank of $H_{3}( \textrm{VR}(Q_{n};2))$ is at least

$$\begin{aligned}&2^{n-3} \left( {\begin{array}{c}n\\ 3\end{array}}\right) + \sum _{i=3}^{n-1} 2^{i-3} \left( {\begin{array}{c}i\\ 3\end{array}}\right) \\&\quad = \sum _{i=3}^{n} 2^{i-3} \left( {\begin{array}{c}i\\ 3\end{array}}\right) \\&\quad = 2^{n-2}\left( {\begin{array}{c}n\\ 3\end{array}}\right) - \sum _{i=1}^{n-2} 2^{i-1}\left( {\begin{array}{c}i+1\\ 2\end{array}}\right) \qquad \text {as explained in Appendix~A.2}\\&\quad = \sum _{i=1}^{n-2} \left( 2^{n-2}-2^{i-1}\right) \left( {\begin{array}{c}i+1\\ 2\end{array}}\right) \quad \qquad \text {since }\left( {\begin{array}{c}n\\ 3\end{array}}\right) =\sum _{i=1}^{n-2}\left( {\begin{array}{c}i+1\\ 2\end{array}}\right) \\&\quad = \sum _{i=1}^{n-1} \left( 2^{n-2}-2^{i-1}\right) \left( {\begin{array}{c}i+1\\ 2\end{array}}\right) \quad \qquad \text {since }2^{n-2}-2^{(n-1)-1}=0 \\&\quad = \sum _{0 \le j< i < n}(j+1)(2^{n-2}- 2^{i-1}) \qquad \text {since }\left( {\begin{array}{c}i+1\\ 2\end{array}}\right) =\sum _{j=0}^{i-1}(j+1) \\&\quad =: c_n. \end{aligned}$$

Since $\textrm{VR}(Q_n;2) \simeq \bigvee _{c_n} S^3$ (Theorem 2.4), this combined lower bound explains all of the homology when $r=2$.

6.4.3 The Case $\mathbf {r=3}$

Using only the cross-polytopal generator for $\textrm{VR}(Q_4;3) \cong S^7$ and also the homotopy equivalence $\textrm{VR}(Q_5;3) \simeq \bigvee ^{10} S^7 \bigvee S^4$, we obtain the following lower bounds on homology when $r=3$:

• (a) The cross-polytopal elements provide $2^{n-4} \left( {\begin{array}{c}n\\ 4\end{array}}\right)$ independent generators for $H_{7}( \textrm{VR}(Q_{n};3))$ (Theorem 4.1).

• (b) The noncross-polytopal four-dimensional homology element appearing at $n=5$ provides $\sum _{i=5}^n 2^{i-5} \left( {\begin{array}{c}i-1\\ 4\end{array}}\right) = \sum _{i=4}^{n-1} 2^{i-4} \left( {\begin{array}{c}i\\ 4\end{array}}\right)$ independent generators for $H_{4}( \textrm{VR}(Q_{n};3))$ (Theorem 6.4).

The total lower bound equals the actual rank of all homology of $\textrm{VR}(Q_{n};3)$, due to Theorem 2.5 which says

$$\begin{aligned} \textrm{VR}(Q_n;3) \simeq \bigvee _{2^{n-4}\left( {\begin{array}{c}n\\ 4\end{array}}\right) } S^7 \ \vee \bigvee _{\sum _{i=4}^{n-1} 2^{i-4} \left( {\begin{array}{c}i\\ 4\end{array}}\right) } S^4. \end{aligned}$$

6.4.4 The Case $\mathbf {r=4}$

Ziqin Feng at Auburn University has computed the homology of $\textrm{VR}(Q_6;4)$. To do so, he used the Easley Cluster at Auburn University (a system for high-performance and parallel computing), about 180 GB of memory, and the Ripser software package [7]. His computations show that

$$\begin{aligned} H_q(\textrm{VR}(Q_6;4);\mathbb {Z}/2) \cong {\left\{ \begin{array}{ll} 0 &{} \text {if }1\le q\le 6\\ (\mathbb {Z}/2)^{239} &{} \text {if }q=7\\ 0 &{} \text {if }8\le q\le 14\\ (\mathbb {Z}/2)^{14} &{} \text {if }q=15. \end{array}\right. } \end{aligned}$$

This computation is shown in the first $r=4$ column in Table 2, and the consequences implied by this computation and by our results are shown in the second $r=4$ column in that table.

6.4.5 The Case of General $\textbf{r}$

In Sect. 7 we prove that in each column of Tables 1 or 2 with $r \ge 2$, a new homology generator appears in $\textrm{VR}(Q_n;r)$ with $n\ge r+1$, i.e., below the diagonal entry $n=r+1$ where the cross-polytopal generator appears. Examples of these new homology generators are in the items (b) above for $r=2$ and 3.

6.5 Propagation of Noninitial Homology

For positive integers $m < n$ let

$$\begin{aligned} \Psi _{m,n} :\coprod _{2^{n-m} \left( {\begin{array}{c}n\\ m\end{array}}\right) } Q_m \rightarrow Q_n \end{aligned}$$

denote the natural inclusion of all the ${2^{n-m} \left( {\begin{array}{c}n\\ m\end{array}}\right) }$-many $Q_m$ subcubes of $Q_n$ in accordance with the subcube structure introduced in Sect. 2.4. Given a positive integer q, let the homomorphism

$$\begin{aligned} (\Psi _{m,n})_* :\bigoplus _{{2^{n-m} \left( {\begin{array}{c}n\\ m\end{array}}\right) }} H_q(\textrm{VR}(Q_m;r)) \rightarrow H_q(\textrm{VR}(Q_n;r)) \end{aligned}$$

be the induced map on homology.

Our previous results have provided lower bounds on the rank of maps $(\Psi _{p,n})_*$, where p is the smallest parameter for which $H_q(\textrm{VR}(Q_p;r))$ is nontrivial. Our next result explains how an analogous result also holds for other maps $(\Psi _{m,n})_*$.

Theorem 6.5

Let $q\ge 1$. Let

$$\begin{aligned} \mathcal {R}_m = \textrm{rank}\Big (H_q(\textrm{VR}(Q_m;r)) \ \big / \ \textrm{im}(\Psi _{m-1,m})_*\Big ). \end{aligned}$$

Then for $n \ge m \ge p$,

$$\begin{aligned} \textrm{rank}\Big (H_q(\textrm{VR}(Q_n;r)) \ \big / \ \textrm{im}(\Psi _{m-1,n})_*\Big ) \ge \sum _{i=m}^n 2^{i-m} \left( {\begin{array}{c}i-1\\ m-1\end{array}}\right) \cdot \mathcal {R}_m. \end{aligned}$$

Note that $(\Psi _{p-1,p})_*=0$ by the definition of p, and so we recover Theorem 6.4 by setting $m=p$ in Theorem 6.5.

Proof

The proof proceeds by induction on m. We will actually prove

$$\begin{aligned} \textrm{rank}(\rho _{m,n}) \ge \sum _{i=m}^n 2^{i-m} \left( {\begin{array}{c}i-1\\ m-1\end{array}}\right) \cdot \mathcal {R}_m, \quad \text {where} \quad \rho _{m,n}=\textrm{im}(\Psi _{m,n})_* \ \big / \ \textrm{im}(\Psi _{m-1,n})_* \end{aligned}$$

The base case of the induction at $m=p$ is Theorem 6.4, since in this case $\textrm{im}(\Psi _{p-1,p})_*=0$ as $H_q(\textrm{VR}(Q_{p-1};r))=0$. It remains to show the inductive step. Our proof is essentially the same as the proof of Theorem 6.4 applied to $\rho _{m,n}$ instead of to $H_q(\textrm{VR}(Q_n;r))$.

The cube $Q_n$ consists of two disjoint copies of $Q_{n-1}$; see Fig. 5:

• the rear one with the last coordinate 0, denoted by $Q_{n-1}^0$, and

• the front one with the last coordinate 1, denoted by $Q_{n-1}^1$.

We partition the $Q_m$ subcubes of $Q_n$ into three classes:

• The ones contained in the rear $Q_{n-1}^0$ where vertices have last coordinate 0, denoted by $R_n$.

• The ones contained in the front $Q_{n-1}^1$ where vertices have last coordinate 1, denoted by $F_n$.

• The ones contained in the middle passage between them, denoted by $M_n$. Each such $Q_m$ in $M_n$ is of the form $D \times \{0,1\}$, where $D \subseteq Q_{n-1}$ is a copy of $Q_{m-1}$.

We will prove that the following $Q_m$ subcubes of $Q_n$ induce independent homology in $\rho _{m,n}$: the elements of $M_n$ (dashed cubes in Fig. 5) and the elements of $F_n$ that have inductively been shown to include independent embeddings in $H_{q}(\textrm{VR}(Q^1_{n-1};r)) /\textrm{im}(\Psi _{m-1,n-1})_*$ (bold cubes in Fig. 5). The base case of the inductive process is Theorem 6.4.

The cardinality of $M_n$ is $2^{(n-1)-(m-1)} \left( {\begin{array}{c}n-1\\ m-1\end{array}}\right) = 2^{n-m} \left( {\begin{array}{c}n-1\\ m-1\end{array}}\right)$, which is the number of $Q_{m-1}$ subcubes in $Q_{n-1}^0$. Each such subcube has the last coordinate constantly 0. Taking a union with a copy of the same $Q_{m-1}$ subcube with the last coordinates changed to 1, we obtain a $Q_m$ subcube in $M_n$. It is apparent that all elements of $M_n$ arise this way. Let us enumerate the elements of $M_n$ as $Q_{m,j}^M$ with $1\le j \le 2^{n-m} \left( {\begin{array}{c}n-1\\ m-1\end{array}}\right)$. For each such j let $\{a_{i,j}\mid 1\le i \le \mathcal {R}_m\}$ denote a largest linearly independent collection in $H_{q}( \textrm{VR}(Q_{m,j}^M;r))/\textrm{im}(\Psi _{m-1,m})_*$.

The cardinality of the copies of $Q_m$ in $F_n$ that have inductively been shown to include independent embeddings in $H_{q}(\textrm{VR}(Q^1_{n-1};r))/\textrm{im}(\Psi _{m-1,n-1})_*$ equals $\sum _{i=m}^{n-1} 2^{i-m} \left( {\begin{array}{c}i-1\\ m-1\end{array}}\right)$, by inductive assumption. Let us enumerate them by $Q_{m,j}^F$ with $1\le j\le \sum _{i=m}^{n-1} 2^{i-m} \left( {\begin{array}{c}i-1\\ m-1\end{array}}\right)$. For each such j let $\{b_{i,j} \mid 1\le i\le \mathcal {R}_m\}$ denote a largest linearly independent collection in $H_{q}( \textrm{VR}(Q_{m,j}^F;r))/\textrm{im}(\Psi _{m-1,m})_*$.

Assuming the equality

$$\begin{aligned} \sum _{i,j}\lambda _{i,j} \cdot a_{i,j} + \sum _{i,j}\mu _{i,j} \cdot b_{i,j}=0 \end{aligned}$$

(3)

in $\rho _{m,n}$ for some coefficients $\lambda _{i,j}$, $\mu _{i,j}$, we claim that all coefficients equal zero. This will prove the theorem as the number of involved terms equals $\sum _{i=m}^n 2^{i-m} \left( {\begin{array}{c}i-1\\ m-1\end{array}}\right) \cdot \mathcal {R}_m$.

We will first prove that the coefficients $\lambda _{i,j}$ are all zero. Fix some $1\le j \le 2^{n-m} \left( {\begin{array}{c}n-1\\ m-1\end{array}}\right)$, and let D be the copy of $Q_{m-1}$ in $Q_{n-1}^0$ so that $C:= D \times \{0,1\}$ is equal to $Q_{m,j}^M$. Let f be any concentration $Q_n \rightarrow C:=D \times \{0,1\}$. (For example, in Fig. 4 one can visualize D as the solid round vertex and C as the edge between the two solid vertices.) By Proposition 5.1:

• f maps any $Q_m$ subcube of $Q_n$ that contains D bijectively onto $C=Q_{m,j}^M$. All such subcubes except for C are contained in $R_n$.

• f maps all of the other $Q_m$ subcubes of $Q_n$ to lower-dimensional subcubes, and hence the map

  $$\begin{aligned} H_q (\textrm{VR}(Q_m;r))\ \big / \ \textrm{im}(\Psi _{m-1,m})_* \rightarrow H_q(\textrm{VR}(C;r))\ \big / \ \textrm{im}(\Psi _{m-1,m})_* \end{aligned}$$

  induced by $f|_C$ is trivial.

These two observations imply that applying the induced map $f_*$ on homology to Equation (3), we obtain $\sum _{i}\lambda _{i,j} \cdot a_{i,j}=0.$ By the choice of $\{a_{i,j}\}_i$ as an independent collection of homology classes, we obtain $\lambda _{i,j}=0$ for all i. Since this can be done for any $1\le j \le 2^{n-p} \left( {\begin{array}{c}n-1\\ p-1\end{array}}\right)$, we have $\lambda _{i,j}=0$ for all i and j.

We have thus reduced Equation (3) to $\sum _{i,j}\mu _{i,j} \cdot b_{i,j}=0.$ Let $\pi _S :Q_n \rightarrow Q_{n-1}$ be the projection that forgets the last coordinate of each vector (explicitly, $S=[n-1]\subseteq [n]$). Note that the restrictions of $\pi _S$ to $Q_n^0$ and to $Q_n^1$ are bijections. Hence, after applying the induced map $(\pi _S)_*$ on homology, the inductive definition of the $b_{i,j}$ as being independent in $H_{q}(\textrm{VR}(Q^1_{n-1};r))/\textrm{im}(\Psi _{m-1,n-1})_*$ implies that $\mu _{i,j}=0$ for all i and j. $\square$

7 Geometric Generators

Definition 7.1

For $r\ge 0$, let $f_n:\textrm{VR}(Q_n;r)\rightarrow [0,1]^n$ be the map defined by sending each vertex of $Q_n$ to the corresponding point in $\{0,1\}^n\subseteq [0,1]^n$, and then by extending linearly to simplices. In particular, if $v_1, v_2, \ldots , v_k$ is a subset of $Q_n \subset [0,1]^n$ of diameter at most r, then $f_n \left( \sum _{i=1}^k \lambda _i v_i \right) = \sum _{i=1}^k \lambda _i v_i$, where the first sum represents the barycentric coordinates in $\textrm{VR}(Q_n;r)$, while the second sum represents the convex combination in $[0,1]^n$.

Let $n(r)\in \{0,1,\ldots \}$ be the smallest integer n such that $f_n:\textrm{VR}(Q_n;r)\rightarrow [0,1]^n$ is not surjective. The fact that this is well-defined follows from Lemma 7.6, which proves that $n(r) \le 2r+1$.

The main theorem in this section is the following.

Theorem 7.2

For all $r\ge 2$,

• (i) There exists some $m \le n(r)$ such that $\pi _{m-1}(\textrm{VR}(Q_m;r))\ne 0$;

• (ii) There exists some $k \le m$ such that $H_{k-1}(\textrm{VR}(Q_m;r))\ne 0$;

• (iii) Not all of the above nontrivial homotopy group (resp. homology group) is generated by the initial cross-polytopal spheres, i.e., the image of the induced map $(\Psi _{r+1,m})_*$ of Vietoris–Rips complexes $\textrm{VR}(Q_{r+1};r) \hookrightarrow \textrm{VR}(Q_m;r)$ at scale r is not all of $\pi _{m-1}(\textrm{VR}(Q_m;r))$ (resp. $H_{k-1}(\textrm{VR}(Q_m;r))$).

Statement (ii) above is true for homology taken with any choice of coefficients.

An important consequence of this theorem is the following. Together, statements (i)–(iii) imply that for each $r\ge 2$, there is a new topological feature in $\textrm{VR}(Q_m;r)$ that is not induced from an inclusion $\textrm{VR}(Q_{r+1};r)\hookrightarrow \textrm{VR}(Q_m;r)$. In Table 2, these appear as the new blue $S^3$ feature in $\textrm{VR}(Q_4;2)\simeq \vee ^9 S^3$, and as the new blue $S^4$ feature in $\textrm{VR}(Q_5;3)\simeq \vee ^{10} S^7 \vee S^4$.

In the following example, when $r=2$, we see that we can take $k=m=n(r)$. However, we do not know if this is the case in general.

Example 7.3

Fix $r=2$. Note that $n(2)=4$ is the smallest integer n such that $f_n:\textrm{VR}(Q_n;2)\rightarrow [0,1]^n$ is not surjective. We will use this to show $\pi _3(\textrm{VR}(Q_4;2))\ne 0$. The following five tetrahedra form a triangulation of $[0,1]^3$ (see Sect. 5.3 and in particular Fig. 4 of [23]).

$$\begin{aligned} \tau _1&= \{(0,1,1),(1,1,0),(1,0,1),(0,0,0)\} \\ \tau _2&= \{(0,0,0),(1,0,0),(1,1,0),(1,0,1)\} \\ \tau _3&= \{(0,1,1),(1,1,0),(0,0,0),(0,1,0)\} \\ \tau _4&= \{(1,1,1),(0,1,1),(1,1,0),(1,0,1)\} \\ \tau _5&= \{(0,0,0),(0,1,1),(0,0,1),(1,0,1)\} \end{aligned}$$

Furthermore, each tetrahedron $\tau _i$ has diameter at most 2. Since $[0,1]^3=\bigcup _{i=1}^5 |\tau _i|$, and since each $\tau _i$ is a simplex in $\textrm{VR}(Q_3;2)$, we define a surjective map $h:[0,1]^3 \rightarrow \textrm{VR}(Q_3;2)$ by letting $h(x)=\sum _{v\in \sigma (x)}\lambda _v v$, where $\sigma (x)$ is the unique simplex in the triangulation $[0,1]^3=\bigcup _{i=1}^5 |\tau _i|$ that contains x in its interior.¹ We note that the map h is continuous. Note that $\partial ([0,1]^4)$ is composed of 8 faces, where each face is a 3-dimensional cube $[0,1]^3$. By piecing together 8 copies of the map h in a continuous way, we obtain a map $g:\partial ([0,1]^4) \rightarrow \textrm{VR}(Q_4;2)$. The map $f_4:\textrm{VR}(Q_4;2)\rightarrow [0,1]^4$ is not surjective, although its image does contain $\partial ([0,1]^4)$, which follows since $f_3:\textrm{VR}(Q_3;2)\rightarrow [0,1]^3$ is surjective. Therefore, there exists a point $v\in \textrm{int}([0,1]^4)\setminus \textrm{im}(f_4)$. We thus obtain a composition

$$\begin{aligned} \partial ([0,1]^4) \xrightarrow {g} \textrm{VR}(Q_4;2) \xrightarrow {f_4} [0,1]^4\setminus \{v\} \xrightarrow {\pi _v} \partial ([0,1]^4), \end{aligned}$$

where $\pi _v :[0,1]^4\setminus \{v\} \rightarrow \partial ([0,1]^4)$ is the radial projection away from the point $v\in \textrm{int}([0,1]^4)$. Note that the composition $\pi _v \circ f_4 \circ g$ is equal to the identity map on $\partial ([0,1]^4)$, and that we have a homeomorphism $\partial ([0,1]^4) \cong S^3$. Since this map $\pi _v \circ f_4 \circ g$ factors through $\textrm{VR}(Q_4;2)$, it follows that $\pi _3(\textrm{VR}(Q_4;2))\ne 0$. The proof of Theorem 7.2 follows this strategy.

Example 7.4

Fix $r=3$. By [14] we have $\textrm{VR}(Q_5;3) \simeq \bigvee ^{10} S^7 \vee S^4$. Theorem 7.2 is satisfied with $m=k=5$.

Non-Example 7.5

Fix $r=4$. By Ziqin Feng’s homology computations in Sect. 6.4.4 we have $H_7(\textrm{VR}(Q_6;4);\mathbb {Z}/2)\cong (\mathbb {Z}/2)^{239}$, $H_{15}(\textrm{VR}(Q_6;4);\mathbb {Z}/2)\cong (\mathbb {Z}/2)^{14}$, and $H_{q}(\textrm{VR}(Q_6;4);\mathbb {Z}/2)=0$ for $1\le q\le 6$ and $8 \le q\le 14$. Since the dimensions 7 and 15 of nontrivial homology are not smaller than 6, neither of these nontrivial homology groups fits the description in Theorem 7.2(ii). This shows that $m>6$ when $r=4$. In other words, Theorem 7.2 guarantees that a new topological feature not yet present in the $r=4$ row of Table 2 will appear in some $\textrm{VR}(Q_m;4)$ with $m>6$.

We now build up toward the proof of Theorem 7.2. We will use the following notation:

• $C_n = [0,1]^n$ denotes the n-dimensional cube.

• $\textrm{Conv}Q_i$ is the convex hull of $Q_i\subset [0,1]^i.$

• 0-skeleton: $C_n^{(0)}=Q_n$ is the set of vertices of $C_n$.

• k-skeleton for $k>0$: $C_n^{(k)}= \cup \{k\text {-dimensional subcubes of } C_n \}= \cup \{\textrm{Conv}Q_k \mid Q_k \le Q_n\}$.

• $\partial C_n = C_n^{(n-1)} \cong S^{n-1}$.

We will use the following lemma in the proof of Theorem 7.2.

Lemma 7.6

For each $r\ge 2$ the following hold:

• 1. $n(r) \le 2r+1$.

• 2. The image of $f_{n(r)}$ contains $\partial C_{n(r)-1}$.

• 3. For each $r\ge 2$ and for each n, $\textrm{VR}(Q_n;r)$ is connected and simply connected.

Proof

(1) Choose a simplex $\sigma \in \textrm{VR}(Q_{n(r)-1};r)$ whose image via $f_{n(r)-1}$ contains the center $z=(\frac{1}{2}, \frac{1}{2}, \ldots , \frac{1}{2})$ of the cube. Without loss of generality (due to the symmetry) we may assume $\sigma$ contains the origin $(0, 0, \ldots , 0)$. As $||z||_{\ell _1}= \frac{n(r)-1}{2}$, $\sigma$ must contain a vertex of $\ell _1$-norm at least $\frac{n(r)-1}{2}$. On the other hand, the $\ell _1$-norm of each vertex of $\sigma$ is at most r, due to the inclusion of the origin in $\sigma$. Thus $\frac{n(r)-1}{2} \le r$, which implies (1).

(2) holds since $f_{n(r)-1}$ is not surjective.

(3) Choose $r \ge 2$. The complex $\textrm{VR}(Q_n;r)$ is obviously connected. Let $\alpha$ be a based simplicial loop in $\textrm{VR}(Q_n;r)$ and let [v, w] be an edge, which is a part of $\alpha$. Setting $v=v_0$ and $w=v_r$, we can replace [v, w] by a homotopic (rel {v,w}) concatenation of edges $[v_0,v_1] * [v_1, v_2]* \ldots * [v_{r-1},v_r]$, whose pairwise distances are at most 1. In particular, since v and w differ in at most r coordinates, we can choose $v_i$ inductively so that $v_i$ differs from $v_{i+1}$ in at most one coordinate. Thus $\textrm{diam}\{v_0, v_1, \ldots , v_r\} \le r$ which means that the defined vertices $v_i$ form a simplex contained in $\textrm{VR}(Q_n;r)$. As any simplex is contractible, [v, w] is homotopic (rel {v,w}) to the concatenation of edges $[v_0,v_1] * [v_1, v_2]* \ldots * [v_{r-1},v_r]$.

Replacing each edge of $\alpha$ in this manner we obtain a based homotopic simplicial loop $\beta$, such that the endpoints of all the edges are at distance at most 1. The loop $\beta$ is thus contained $\textrm{VR}(Q_n;2)$, which is simply connected by [4], and contained in $\textrm{VR}(Q_n;r)$. As a result, $\beta$ and $\alpha$ are contractible loops. As $\alpha$ was arbitrary, this means $\textrm{VR}(Q_n;r)$ is simply connected. $\square$

Proof of Theorem 7.2

(i): Fix $r\ge 2$. In order to show (i), it is equivalent to assume $\pi _{n-1}(\textrm{VR}(Q_n;r))$ is trivial for all $n \in \{1,2, \ldots , n(r)-1\}$, and then prove that $\pi _{N-1}(\textrm{VR}(Q_{N};r))\ne 0$ for $N:= n(r)$. This is what we will do.

First, we define $\varphi :\partial C_{N} \rightarrow \textrm{VR}(Q_{N};r)$ by induction on the skeleta of $C_{N}$. For the base case, the 0-skeleton, define $\varphi |_{C_{N}^{(0)}}$ as the identity on $Q_{N}$, mapping a point of $Q_{N}$ to the corresponding vertex in $\textrm{VR}(Q_{N};r)$. Now, assume that

$$\begin{aligned} \varphi :C_{N}^{(j)} \rightarrow \textrm{VR}(Q_{N};r) \end{aligned}$$

has been defined for some $j \in \{0,1,\ldots , N-2\}$ in a subcube-preserving manner, i.e.,

$$\begin{aligned} \forall i \le j, \ \forall Q_i \le Q_{N}: \ \varphi (\textrm{Conv}Q_i) \subseteq \textrm{VR}(Q_i;r). \end{aligned}$$

(4)

Before defining $\varphi$ on all of $C_N^{(j+1)}$, we first explain how to define $\varphi$ on a single $(j+1)$-dimensional cube. Fix $Q_{j+1} < Q_{N}$, and let $C_{j+1} = \textrm{Conv}Q_{j+1}$. Define $\varphi |_{C_{j+1}} :C_{j+1} \rightarrow \textrm{VR}(Q_{j+1};r)$ as follows:

• By (4) above we have

  $$\begin{aligned} \varphi ({\partial C_{j+1}}) \subseteq \bigcup _{Q_j \le Q_{j+1}} \textrm{VR}(Q_j;r) \le \textrm{VR}(Q_{j+1};r). \end{aligned}$$

• By the assumption at the beginning of the proof, $\varphi |_{\partial C_{j+1}} :\partial C_{j+1} \rightarrow \textrm{VR}(Q_{j+1};r)$ is contractible and can thus be extended over $C_{j+1}$. In particular, the subcube-preserving condition $\varphi ({ C_{j+1}}) \subseteq \textrm{VR}(Q_{j+1};r)$ holds.

Defining $\varphi$ on $\textrm{Conv}Q_j$ for each $Q_j \le Q_{j+1}$ we obtain a continuous subcube-preserving map $\varphi$ defined on $\partial C_{N}^{(j+1)}$. This concludes the inductive step, and thus we obtain a subcube-preserving map

$$\begin{aligned} \varphi :\partial C_{N} \rightarrow \textrm{VR}(Q_{N};r). \end{aligned}$$

Next, we show that $\varphi$ is not contractible. Choose $z\in C_{N} {\setminus } \partial C_{N}$ such that z is not contained in the image of $f_{N}$. Let $\nu :C_{N} {\setminus } \{z\} \rightarrow \partial C_{N}$ be the radial projection map, which is a retraction. Define $\psi = \nu \circ f_{N} \circ \varphi :\partial C_{N} \rightarrow \partial C_{N}$ as the composition of maps

$$\begin{aligned} \partial C_{N} {\mathop {\rightarrow }\limits ^{\varphi }} \textrm{VR}(Q_{N};r){\mathop {\rightarrow }\limits ^{f_{N}}} C_{N} \setminus \{z\} {\mathop {\rightarrow }\limits ^{\nu }} \partial C_{N}, \end{aligned}$$

and note it is a map between topological $(N-1)$-spheres. Observe that $\psi$ is subcube-preserving, i.e., $\forall Q_j < Q_{N}: \psi (\textrm{Conv}Q_j) \subseteq \textrm{Conv}Q_j$. The map $\psi :\partial C_{N} \rightarrow \partial C_{N}$ is homotopic to the identity, as is demonstrated by the linear homotopy

$$\begin{aligned} H :\partial C_{N} \times I \rightarrow \partial C_{N}, \qquad H(x,t) = (1-t)\varphi (x) + t x, \end{aligned}$$

which is well-defined by the subcube-preserving property. As $\psi$ is homotopically nontrivial, so is $\varphi$. Since $\textrm{VR}(Q_{N};r)$ is path connected, this implies $\pi _{N} (\textrm{VR}(Q_{N};r))$ is nontrivial regardless of which basepoint is used, giving (i).

(ii): By the Hurewicz theorem and Lemma 7.6(3), the first nontrivial homotopy group of $\textrm{VR}(Q_m;r)$ is isomorphic to the corresponding homology group with integer coefficients in the same dimension. By (i), the mentioned dimension is at most $m-1$.

(iii): Let $m \in \{1,2, \ldots , n(r)\}$ be the parameter from the proof of (i) that satisfies $\pi _{m-1}\textrm{VR}(Q_{m};r)\ne 0$. For $r>2$ we claim that $m-1 < 2^r-1$. Indeed, $m-1 \le n(r)-1 \le 2r < 2^r-1$ by Lemma 7.6(2). So for $r>2$, the dimension ($m-1$ or lower) of the homotopy and homology groups in (i) and (ii) is lower than the dimension $2^r-1$ of the $\Psi _{r+1, m}$ induced invariants, giving (iii). Finally, in the case $r=2$, we have $m=2$ and $\textrm{VR}(Q_4;2) \simeq \vee ^9 S^3$ by [4]. Since $Q_4$ contains only 8 copies of $Q_3$, the image of the $\Psi _{3,4}$ induced map on $\pi _3$ is of rank at most 8; thus the claim (iii) follows also for $r=2$. $\square$

8 Conclusion and Open Questions

We conclude with a description of some open questions. We remind the reader of questions from [4], which ask if $\textrm{VR}(Q_n;r)$ is always a wedge of spheres, what the homology groups and homotopy types of $\textrm{VR}(Q_n;r)$ are for $3\le r\le n-2$, and if $\textrm{VR}(Q_n;r)$ collapses to its $(2^r-1)$-skeleton (which would imply that the homology groups $H_q(\textrm{VR}(Q_n;r))$ are zero for $q\ge 2^r$). Below we pose some further questions.

The first four questions are related to the geometric generators in Sect. 7. Understanding the answers to any of them would provide further information about parameters of Theorem 7.2.

Question 8.1

Recall that $n(r)\in \{0,1,\ldots \}$ is the smallest integer n such that $f_n:\textrm{VR}(Q_n;r)\rightarrow [0,1]^n$ is not surjective. What are the values of n(r) as a function of r?

Question 8.2

If $f_n:\textrm{VR}(Q_n;r)\rightarrow [0,1]^n$ is not surjective, then is it necessarily the case that the center $(\frac{1}{2}, \frac{1}{2}, \ldots , \frac{1}{2})$ is not in the image of $f_n$?

Question 8.3

If $f_n:\textrm{VR}(Q_n;r)\rightarrow [0,1]^n$ is surjective, then does there exist a triangulation of $[0,1]^n$ by simplices of diameter at most r?

Question 8.4

The following question is based on a StackExchange post [1]. A subset $B\subseteq \{0,1\}^n$ is balanced if $\frac{1}{|B|}\sum _{b\in B} b = (\frac{1}{2},\ldots ,\frac{1}{2})\in \mathbb {R}^n$. For example, the tetrahedron $\tau _1$ in Example 7.3 is a set of four vertices that forms a balanced subset. If $(\frac{1}{2}, \frac{1}{2}, \ldots , \frac{1}{2})$ is in the image of $f_n:\textrm{VR}(Q_n;r)\rightarrow [0,1]^n$, then does there necessarily exist a balanced subset of $\{0,1\}^n$ of diameter at most r? One of the reasons we ask this question is that the answers to the StackExchange post [1] place constraints on the smallest diameter for a balanced subset of the n-dimensional cube.

The remaining questions are more general.

Question 8.5

In Sect. 4 we described cross-polytopal homology generators. In Sect. 7 we described geometric homology generators. In Non-Example 7.5 we described homology generators, due to computations by Ziqin Feng, that are neither cross-polytopal in the sense of Sect. 4 (arising from an isometric embedding $Q_{r+1}\hookrightarrow Q_n$) nor geometric in the sense of Sect. 7. What other types of homology generators are there for $H_q(\textrm{VR}(Q_n;r))$?

Question 8.6

Our main results show how the homology (and persistent homology) of $\textrm{VR}(Q_p;r)$ for $1\le p \le m$ place lower bounds on the Betti numbers of $\textrm{VR}(Q_n;r)$ for all $n\ge m$. For every $r\ge 1$, is there some integer m(r) such that our induced lower bounds are tight for all $n\ge m(r)$ and for all homology dimensions?

Question 8.7

The group of symmetries of the n-dimensional cube is the hyperoctahedral group. How does this group act on the homology $H_q(\textrm{VR}(Q_n;r))$?

Question 8.8

What homology propagation results can be proven for Čech complexes of hypercube graphs, as studied in [6]?

Appendix A: Proofs of Numerical Identities

This appendix contains two short proofs of numerical identities, both of which are used in Sect. 6.4 in the cases $r=1$ and $r=2$.

1.1 A.1 First proof

Let $S_n=\sum _{i=2}^n (i-1) 2^{i-2}$; we claim $S_n = n2^{n-1}-2^n+1$. Indeed, note that

$$\begin{aligned}&S_n=2 S_n - S_n=0 +2 +2\cdot 2^2 +3\cdot 2^3 +\ \ \ \ \ \ldots +(n-2)\cdot 2^{n-2}+(n-1)\cdot 2^{n-1}\\&\ \ \ -1 -2\cdot 2 -3\cdot 2^2 -4\cdot 2^3 -\ \ \ \ \ \ldots -(n-1)\cdot 2^{n-2}\\&=-1 -2 -2^2 -2^3 -\ \ \ \ \ \ldots -2^{n-2}+(n-1)\cdot 2^{n-1}, \end{aligned}$$

which gives $S_n = -(2^{n-1}-1)+(n-1)2^{n-1} = n2^{n-1}-2^n+1$.

1.2 A.2 s Proof

We prove that $\sum _{i=3}^{n} 2^{i-3} \left( {\begin{array}{c}i\\ 3\end{array}}\right) = 2^{n-2}\left( {\begin{array}{c}n\\ 3\end{array}}\right) - \sum _{i=1}^{n-2} 2^{i-1}\left( {\begin{array}{c}i+1\\ 2\end{array}}\right)$ by induction on n. For the base case $n=3$, note that both sides equal 1. For the inductive step, note that if we assume the formula is true for $n-1$, then as desired we get

$$\begin{aligned} \sum _{i=3}^{n} 2^{i-3} \left( {\begin{array}{c}i\\ 3\end{array}}\right)&= 2^{n-3} \left( {\begin{array}{c}n\\ 3\end{array}}\right) + \left( 2^{n-3}\left( {\begin{array}{c}n-1\\ 3\end{array}}\right) - \sum _{i=1}^{n-3} 2^{i-1} \left( {\begin{array}{c}i+1\\ 2\end{array}}\right) \right) \\&= 2^{n-3} \left( {\begin{array}{c}n\\ 3\end{array}}\right) + 2^{n-3}\left( {\begin{array}{c}n-1\\ 3\end{array}}\right) + 2^{n-3}\left( {\begin{array}{c}n-1\\ 2\end{array}}\right) - \sum _{i=1}^{n-2} 2^{i-1} \left( {\begin{array}{c}i+1\\ 2\end{array}}\right) \\&= 2^{n-3} \left( {\begin{array}{c}n\\ 3\end{array}}\right) + 2^{n-3}\left( {\begin{array}{c}n\\ 3\end{array}}\right) - \sum _{i=1}^{n-2} 2^{i-1} \left( {\begin{array}{c}i+1\\ 2\end{array}}\right) \\&= 2^{n-2}\left( {\begin{array}{c}n\\ 3\end{array}}\right) - \sum _{i=1}^{n-2} 2^{i-1}\left( {\begin{array}{c}i+1\\ 2\end{array}}\right) . \end{aligned}$$