2026-05-07

I was investigating the notion of torsion in relation to the flat norm LP as suggested by Bala’s conversation with Claude and I believe I came up with a counterexample.

I took a triangulation of $\mathbb{R}{P}^2$, fattened it up by replacing each triangle of $\mathbb{R}{P}^2$ with a tetrahedra where the fourth point is given by the barycentric coordinates of the triangle. I then randomly generated input chains until I found one that gave fractional solutions. I set $\lambda =0.05$. I did not use the area of the triangles as weights, I simply set the weights to one.

For the triangles ($y$-values) in the output, the yellow triangles belong to the original $\mathbb{R}{P}^2$ and have a coefficient of $\pm 0.5$. The orange triangles are protruding out of the $\mathbb{R}{P}^2$ along the created tetrahedra and have a coefficient of $\pm 1$.

The above can be ignored, this is codimension 3.

---

However, I may have found something of interest. I took an instance which had several instances of $|\det (B)|\ne 1$, where $B$ is the basis matrix for an intermediate step. In each case, I computed the Smith normal form of $B$ and found they all had the following form:

$$SNF(B)=S=\left[\begin{array}{cc}{I}_{m-t}& \\ & k{I}_t\end{array}\right]$$

where $k\in {\mathbb{Z}}_{+}$ and $0\le t<m$. The values of $k$ and $t$ vary across intermediate bfs’s.

Consider the lattice generated by $B$:

$$\Lambda (B)=\{Bz:z\in {\mathbb{Z}}^m\}\subset {\mathbb{Z}}^m.$$

Consider then the cokernel, ${\mathbb{Z}}^m/\Lambda (B)$, which has index $|\det (B)|$. From the above, it appears that our cokernel is of the form ${\mathbb{Z}}^m/\Lambda (B)\cong (\mathbb{Z}/k\mathbb{Z}{)}^t$. I further claim (without real evidence) that this is a $p$-group.

Recall that our bfs $B{x}_B=b$ has integral solution $x_B$ if and only if $b\in \Lambda (B)$. Let $b^{\prime }=Ub$ where $UBV=S$. Then $x_B=V{S}^{-1}{b}^{\prime }$. Note that $V$ is unimodular, so $x_B\in {\mathbb{Z}}^m$ if and only if $S^{-1}{b}^{\prime }\in {\mathbb{Z}}^m$. Thus, $x_B\in {\mathbb{Z}}^m$ if and only if

$$(Ub{)}_i\equiv 0(\mathrm{mod}k),\forall i>m-t.$$

Numerical experiments also suggest that

$$G_{B}b\equiv 0\mathrm{mod}k$$

where $G_B$ is the last $t$-rows of $U$ for every corresponding basis $B$. However, upon checking it appears that

$$G_B\not\equiv 0\mathrm{mod}k,$$

i.e., there exists some vector $b\in {\mathbb{Z}}^m$ such that $G_{B}b\not\equiv 0\mathrm{mod}k$. However, there is no guarantee that if we start with such a right-hand side $b$ that the corresponding basis $B$ for $G_B$ would appear. This suggests that the LP’s polyhedra may not be integral for all $b\in {\mathbb{Z}}^m$.

Define

$${\mathcal{B}}_B=\{\begin{array}{ll}{\mathbb{Z}}^m& \text{if }|\det (B)|=1\\ \{b\in {\mathbb{Z}}^m:G_{B}b\equiv 0\mathrm{mod}{k}_B\}& \text{otherwise}.\end{array}$$

Then we know the set of inputs $b\in {\mathbb{Z}}^m$ which give integral solutions contains the sublattice

$$\mathcal{B}=\bigcap _{\text{feasible bases B}}{\mathcal{B}}_B⊊{\mathbb{Z}}^m,$$

but is likely much larger as not all basis $B$ are visited. That is,

$$\mathcal{B}\subseteq \{b\in {\mathbb{Z}}^m:\text{LP gives integral solution}\}\subseteq {\mathbb{Z}}^m.$$

After testing thousands of randomly generated $m\times m$ minors, the property $G_{B}b\equiv 0\mathrm{mod}{k}_B$ does not hold for every submatrix $B$. However, I have yet to find a feasible basis $B$ in which the above property did not hold.