Theorem 1 — Rank-sensitive distance lower bound

For every based binary chain complex $A$, every pair of natural numbers $r,c$ (although implicit in the notation, both are universally quantified), every $\mathbb F_2$-linear map $P:\mathbb F_2^c\to\mathbb F_2^r$, and every natural-number degree $j$, let $E=\mathcal E(P)$, let $\rho=\dim_{\mathbb F_2}(\operatorname{range}P)$, let $d_k(A)$ denote the degree-$k$ distance defined below, let $d_j^-(A)=\top$ when $j=0$ and $d_j^-(A)=d_{j-1}(A)$ when $j\ge1$, let $\delta=d_1(E)$, and let $D_j=d_j(A\otimes E)$ be the tensor-product distance defined below. The theorem asserts the conjunction of the following two implications, with no unconditional rank hypothesis:

$$\bigl(\rho<r\ \Longrightarrow\ \min\{d_j(A),\ d_j^-(A)\,\delta\}\le D_j\bigr) \quad\land\quad \bigl(\rho=r\ \Longrightarrow\ d_j^-(A)\,\delta\le D_j\bigr).$$

A binary word on a coordinate type $I$ is a function $I\to\mathbb Z/2\mathbb Z$. The complex $A$ supplies a natural-number dimension $a_k$ in every nonnegative degree, the standard-coordinate binary vector space $A_k=\mathbb F_2^{a_k}$, and for every $k\in\mathbb N$ a linear boundary

$$\partial_k^A:A_k\longrightarrow \begin{cases} 0,&k=0,\\ A_{k-1},&k\ge1, \end{cases}$$

where the degree-zero target is represented by words on the empty coordinate type. It also supplies the identities $\partial_k^A\partial_{k+1}^A=0$ for all $k$, a natural number $L$, and the condition $a_k=0$ whenever $L<k$. The number $L$ is only required to be an upper bound on the support of the dimensions: it need not be minimal, and neither $a_L$ nor any lower-degree dimension is required to be positive.

For linear maps $d:\mathbb F_2^I\to\mathbb F_2^K$ and $d_{\mathrm{next}}:\mathbb F_2^M\to\mathbb F_2^I$, where $I$ is finite with decidable equality, their homological distance is

$$\inf\bigl\{\operatorname{wt}(x):x\in\mathbb F_2^I,\ d(x)=0,\ x\notin\operatorname{range}(d_{\mathrm{next}})\bigr\} \in\mathbb N\cup\{\top\},$$

with $\operatorname{wt}(x)=\#\{i\in I:x_i\ne0\}$. More literally, the set whose infimum is taken consists of extended natural numbers $w$ for which there exists such an $x$ and $w$ equals the natural Hamming weight of $x$ embedded into $\mathbb N\cup\{\top\}$. Its infimum is $\top$ if there is no such $x$. Since zero lies in the range of every linear map, every admissible $x$ is nonzero, so every finite value of this distance is a positive natural number and the value is never $0$. The component distance used in the theorem is exactly

$$d_k(A)=\inf\bigl\{\operatorname{wt}(x):x\in A_k,\ \partial_k^A x=0,\ x\notin\operatorname{im}\partial_{k+1}^A\bigr\}.$$

Thus $d_0(A)$ minimizes over $A_0\setminus\operatorname{im}\partial_1^A$, because $\partial_0^A$ is necessarily the zero map into the zero-dimensional target, while for $k\ge1$ it minimizes over $\ker\partial_k^A\setminus\operatorname{im}\partial_{k+1}^A$. If this difference is empty, including whenever the corresponding homology is trivial or $A_k$ is the zero space, then $d_k(A)=\top$.

The one-complex $E=\mathcal E(P)$ has $E_0=\mathbb F_2^r$, $E_1=\mathbb F_2^c$, $E_k=0$ for $k\ge2$, boundaries $\partial_0^E=0$, $\partial_1^E=P$, and $\partial_k^E=0$ for $k\ge2$, and declared length $1$. Consequently, the sole distance from $E$ that occurs in the theorem is

$$\delta=d_1(E) =\inf\bigl\{\operatorname{wt}(x):x\in\mathbb F_2^c,\ P x=0,\ x\ne0\bigr\}.$$

The condition $x\ne0$ here is exactly the condition that $x$ not lie in the range of the zero boundary $\partial_2^E$. Hence $\delta=\top$ precisely when $P$ is injective, including when $c=0$; otherwise $\delta$ is the least positive Hamming weight of a nonzero vector in $\ker P$.

The degree-$k$ tensor coordinate type used to define $D_k$ is the disjoint union, over all ordered pairs of nonnegative integers $(p,q)$ satisfying $p+q=k$, of

$$\operatorname{Fin}(a_p)\times\operatorname{Fin}(\dim E_q).$$

The pair $(p,q)$ is represented by two elements of $\operatorname{Fin}(k+1)$ together with the proof that their natural-number values sum to $k$; thus all and only the decompositions $p+q=k$ occur, including the endpoints $(0,k)$ and $(k,0)$. For $E=\mathcal E(P)$, only $q=0$ and $q=1$ can contribute coordinates. Therefore tensor degree $0$ has the component $A_0\otimes\mathbb F_2^r$, while tensor degree $k\ge1$ has the two potentially nonempty components $A_k\otimes\mathbb F_2^r$ and $A_{k-1}\otimes\mathbb F_2^c$; a component is actually empty whenever one of its displayed dimensions is zero.

The tensor boundary in degree $0$ is the zero map from tensor degree $0$ to the zero-dimensional space. For $k\ge1$, take an output coordinate in tensor degree $k-1$ described by $p+q=k-1$, $a\in\operatorname{Fin}(a_p)$, and $b\in\operatorname{Fin}(\dim E_q)$. For a tensor word $e$ in degree $k$, the value of its boundary at that coordinate is defined exactly by

$$(\partial_k^{\otimes}e)_{p,q,a,b} = \left(\partial_{p+1}^A\bigl(a'\mapsto e_{p+1,q,a',b}\bigr)\right)_a + \left(\partial_{q+1}^E\bigl(b'\mapsto e_{p,q+1,a,b'}\bigr)\right)_b,$$

with addition in $\mathbb F_2$. In particular, on the output component with $q=0$, the second summand applies $\partial_1^E=P$ to the input component $A_p\otimes E_1$, while on the output component with $q=1$ the second summand applies the zero map $\partial_2^E$; the first summand always uses the boundary $\partial_{p+1}^A:A_{p+1}\to A_p$. The coordinate injections on the two input slices increase respectively the left degree from $(p,q)$ to $(p+1,q)$ and the right degree from $(p,q)$ to $(p,q+1)$. Consecutive tensor boundaries compose to zero. The tensor-product distance in the theorem is then

$$D_j =\inf\bigl\{\operatorname{wt}(e):e\text{ is a word on the degree-}j\text{ tensor coordinates},\ \partial_j^{\otimes}e=0,\ e\notin\operatorname{im}\partial_{j+1}^{\otimes}\bigr\},$$

again with value $\top$ when this witness set is empty. At $j=0$, the cycle condition is automatic because $\partial_0^{\otimes}=0$, and only nonmembership in $\operatorname{im}\partial_1^{\otimes}$ remains.

All inequalities, products, minima, and infima in the theorem are in $\mathbb N\cup\{\top\}$. A finite distance factor is positive; therefore a product of the displayed distance factors is finite exactly when both factors are finite, and it is $\top$ when either factor is $\top$. Formally, multiplication by $0$ would make a product $0$ even in the presence of $\top$, but none of these distance factors can equal $0$. A lower bound of $\top\le D_j$ is equivalent to $D_j=\top$, whereas every finite value is automatically at most $\top$.

The endpoint $j=0$ is included. Since $d_0^-(A)=\top$ and $\delta$ is nonzero, $d_0^-(A)\delta=\top$. Thus the first implication specializes literally to

$$\rho<r\ \Longrightarrow\ d_0(A)\le D_0,$$

because $\min\{d_0(A),\top\}=d_0(A)$, while the second specializes to

$$\rho=r\ \Longrightarrow\ \top\le D_0,$$

which forces $D_0=\top$. For $j\ge1$, the shifted quantity is exactly $d_j^-(A)=d_{j-1}(A)$, so the two implications become

$$\rho<r\ \Longrightarrow\ \min\{d_j(A),\ d_{j-1}(A)\delta\}\le D_j, \qquad \rho=r\ \Longrightarrow\ d_{j-1}(A)\delta\le D_j.$$

The rank $\rho$ is specifically the finite module rank of the range subspace of $P$ over $\mathbb F_2$, not an additional integer supplied as data. Since that range is a subspace of $\mathbb F_2^r$, one has $\rho\le r$: the two antecedents $\rho<r$ and $\rho=r$ are mutually exclusive and exhaust the possible ranks, although the theorem presents them as two separate implications joined by conjunction. If an antecedent is false, its implication is vacuously true and imposes no bound. The first antecedent says that the range is a proper subspace of the codomain; the second says that the range has the full codomain dimension. No relation between $r$ and $c$ is assumed. In particular, if $r>c$, then $\rho=r$ is impossible and the second implication is vacuous; if $r=0$, then $\rho<r$ is impossible, $\rho=r=0$ automatically, and only the second implication is substantive. If $c=0<r$, then $\rho=0<r$ and $\delta=\top$, so the first implication reduces to $d_j(A)\le D_j$ for every $j$. If $r=c=0$, then the second antecedent holds and $\delta=\top$, so its lower bound forces $D_j=\top$ for every $j$.

No hypothesis requires $j$ to lie at or below the declared length of $A$, requires $L$ to be positive or minimal, requires any coordinate set or chain group to be nonempty, requires any homology group or distance to be finite, constrains the ranks of the boundaries of $A$, or assumes that $P$ is injective, surjective, square, nonzero, or of a prescribed rank. The rank conditions occur only as the antecedents of the two implications. If $j>L+1$, both potentially nonempty tensor components use $A_j=0$ or $A_{j-1}=0$, so the degree-$j$ tensor coordinate type is empty and $D_j=\top$; also $d_j(A)=d_j^-(A)=\top$, so either active rank implication has lower bound $\top$. The conclusion is therefore still an assertion in these out-of-range and all other degenerate cases, with false rank antecedents producing vacuous implications and empty homological witness sets producing the value $\top$.