2026-05-11

Recall that a homology class $[b] \in H_{q} (K; Z)$ is said to have torsion if there is an integer $n \in Z$ such that $n \cdot [b] = 0$ , i.e, there is a chain $c \in C_{p + 1} (K)$ such that $nb = \partial c$ . I claim that $[b]$ being torsion-free is a necessary condition for the OHCP LP giving integral solutions.

Assume that there is some $n \in Z$ and chain $c \in C_{p + 1} (K)$ such that $nb = \partial c$ . Then notice that letting $y = c / n$ gives

[I B] [0 c / n] = \frac{1}{n} B c = b,

which has a cost of

0 \cdot i = 1 \sum m ∣ x_{i} ∣ = 0.

Thus, $[0, c / n]^{⊤}$ is the optimal solution and is fractional.

Recall from 2026-05-07 that it appears that $Z^{m} /Λ (B) ≅ (Z / k Z)^{t}$ where

Λ (B) = {B z : z \in Z^{m}} .

Thus, it follows that $x_{B} \in Z^{m}$ if and only if $b \in Λ (B)$ , i.e., $b \in [0] \in Z^{m} /Λ (B)$ . This leads the question, what condition results in $b$ laying the 0 coset?

Assume that $b, b^{'} \in C_{p} (K)$ such that $[b] = [b^{'}]$ and $b \in [0]$ . Then $b^{'} = b + \partial c$ for some $c \in C_{p + 1} (K)$ . Moreover, it follows that

G_{B} b^{'} = G_{B} (b + \partial c) = G_{B} b + G_{B} \partial c .

Thus, $b^{'} \in [0]$ whenever

G_{B} \partial c \equiv 0 mod k_{B} .

Unfortunately, numerical experiments show that $G_{B} [\partial] \neq \equiv 0 mod k_{B}$ which would have directly shown that $b \in [0]$ if and only if $b^{'} \in [0]$ . That being said, this result also does not disprove the claim.

Take the following instance:

Testing B_5808.txt
 - G[\partial]
<Compressed Sparse Row sparse matrix of dtype 'int64'
	with 26 stored elements and shape (1, 444)>
  Coords	Values
  (0, 0)	2
  (0, 3)	-2
  (0, 27)	-2
  (0, 29)	-2
  (0, 125)	1
  (0, 130)	1
  (0, 131)	-1
  (0, 137)	-1
  (0, 141)	1
  (0, 142)	-2
  (0, 143)	1
  (0, 152)	1
  (0, 154)	1
  (0, 155)	-2
  (0, 160)	-2
  (0, 163)	1
  (0, 165)	-1
  (0, 183)	2
  (0, 185)	-2
  (0, 221)	2
  (0, 222)	2
  (0, 226)	2
  (0, 228)	-2
  (0, 244)	2
  (0, 249)	2
  (0, 250)	-2

What happens if we set $b^{'} = b + \partial c$ where $c = e_{125}$ ? If the same basis $B$ was encountered, then $G [\partial] c = 1 \neq \equiv 0 mod k_{B}$ which would imply that we do not get an integral solution despite $[b^{'}] = [b]$ . However, there is no guarantee that the same basis would be encountered. Upon testing, setting $b^{'}$ as the input gave a different set of basis matrices encountered. In fact, further testing shows that

G b^{'} \neq \equiv 0 mod k

but $x_{B} = B^{- 1} b^{'} \neq \geq 0$ , i.e., $B$ is not a feasible basis for $b^{'}$ .

Conjecture: Let $b^{'} = b + \partial c$ in which $b \in [0]$ . Then for any feasible basis $B$ of $b$ in which $B$ is a feasible basis of $b^{'}$ , it follows that

G_{B} b^{'} \equiv 0 mod k_{B} .

Consequently, $b^{'} \in [0]$ .

The above can be thought of as the following conditions

$B^{- 1} b \geq 0$
$B^{- 1} (b + \partial c) \geq 0$
$G_{B} b \equiv 0 mod k_{B}$ imply that $G_{B} (b + \partial c) \equiv 0 mod k_{B}$ .

Consider the following cone

F_{B} = {b \in C_{q} (K; Z) : B^{- 1} b \geq 0}

which consists of all right-hand side vectors $b$ such that $B$ is a feasible basis. From experimentation, we know that is possible for $[b] = [b^{'}]$ with $b \in F_{B}$ but $b^{'} \neq \in F_{B}$ . But, does it follow that if $b^{'} = b + \partial c \in F_{B}$ , then $G_{B} \partial c \equiv 0 mod k_{B}$ ? Note that if $B^{- 1} \partial c \geq 0$ , then it follows that $\partial c \in F_{B}$ , but it may be the case that $\partial c \neq \in F_{B}$ .

Define

C_{B} = {c \in C_{q + 1} (K; Z) : B^{- 1} \partial c \geq - B^{- 1} b} .

Then we need that $G_{B} \partial c \equiv 0 mod k_{B}$ for all $c \in C_{B}$ . Note that if $B^{- 1} \partial c \in Z^{m}$ , then we get $G_{B} \partial c \equiv 0 mod k$ for free. Indeed,

x_{B} = B^{- 1} \partial c = V [F \partial c \frac{1}{k} G_{B} \partial c] \in Z^{m}

if and only if $G_{B} \partial c \equiv 0 mod k$ as $F \in Z^{m \times n}$ and $V$ is unimodular.

Right now our only known sufficient condition is that $b \in B$ where

B = feasible bases B ⋂ {b \in C_{q} (K; Z) : G_{B} b \equiv 0 mod k_{B}} .

We also know that the cone

F_{B} = {b \in C_{q} (K; Z) : B^{- 1} b \geq 0}

does not contain homology classes. That is, $[b] = [b^{'}]$ and $b \in F_{B}$ does not imply that $b^{'} \in F_{B}$ . Notice that because $Z^{m} /Λ (B) ≅ (Z / k Z)^{t}$ it follows that $[Z^{m} : B_{B}] = k_{B}^{t_{B}}$ where

B_{B} = {b \in Z^{m} : G_{B} b \equiv 0 mod k_{B}} .

Recall that $[G : H \cap K] \leq [G : H] [G : K]$ . Thus it follows that

[Z^{m} : B] \leq feasible bases B \prod k_{B}^{t_{B}}

which is likely huge. Numerical tests put this upper bound at least $1 0^{123}$ . This is an upper bound, we would like a lower bound.

We can slightly improve this condition. Let $B_{1}, \dots, B_{ℓ}$ be the bases visited during simplex method. Define

B_{n} = i = 1 ⋂ n {b \in Z^{m} : G_{B_{i}} b \equiv 0 mod k_{B_{i}}}

where $G_{B} = 0$ when $∣ det B ∣ = 1$ . Then the condition becomes that

G_{B_{1}} G_{B_{2}} ⋮ G_{B_{ℓ}} b \equiv 00 ⋮ 0 mod k_{1} k_{2} ⋮ k_{ℓ}

where the modulo congruence is done entry-wise. Notice that $G_{B_{i}} b \equiv 0 mod k_{i}$ is true if and only if $G_{B_{i}} b - k_{i} I_{t_{i}} z = 0$ for some $z \in Z^{m}$ . Thus we may define the system

G_{B_{1}} G_{B_{2}} ⋮ G_{B_{ℓ}} - k_{1} I_{t_{1}} - k_{2} I_{t_{2}} ⋱ - k_{ℓ} I_{t_{ℓ}} b z_{1} ⋮ z_{ℓ} = 0,

which we denote in short form by $Cw = 0$ . From, here we get that

B = {b \in Z^{m} : \exists z \in Z^{(\sum t_{i}) - m} s.t. C [b^{⊤} z^{⊤}]^{⊤} = 0} .

Notes

Explorer

2026-05-11

Graph View

Backlinks

Source code