2026-07-20

I gave Claude’s new Fable AI the problem. Below is me walking through the response. Here is the log: https://claude.ai/share/826092ab-b1b5-4eef-95c0-c51c24b731b0.

Prompt Given:

Consider the following linear program:

$$\begin{array}{rlr}& \text{minimize}& \sum _{i=1}^m{w}_i(x_i^{+}+x_i^{-})+\lambda \sum _{j=1}^n{v}_j(y_j^{+}+y_j^{-})\\ & \text{subject to}& x^{+}-x^{-}-By=c\\ & & x^{+},x^{-},y^{+},y^{-}\ge 0\end{array}$$

where $I$ is the $m\times m$-identity matrix, $B$ is the boundary matrix for $\partial :C_p(K)\to C_{p-1}(K)$} for some simplicial complex $K$ embedded in ${\mathbb{R}}^{p+1}$, $w$ and $v$ are real non-negative vectors, $\lambda \in \mathbb{R}$ with $\lambda \ge 0$, and $c$ is a $(p-1)$-chain. In the majority of cases, the optimal solution $(x^{\ast },y^{\ast })$ is integral; even if the boundary matrix $B$ is not totally unimodular. However, I was able to find one instance by playing with the weights in which simplex method gave a fractional solution. Forcing integral constraints gave an integral solution with the same objective value. Details on that example are listed here: https://notes.thrall.me/Daily/2026/2026-07-09. The example was constructed from a Mobius strip, as the presence of a Mobius strip enforces a non-TU boundary matrix.

Please characterize the set of solutions in which the optimal solution is integral. Make sure to prove your statements. You may work on this as long you’d like.

---

The feasibility region of the flat norm is given by

$$P=\{(x^{+},x^{-},y^{+},y^{-})\ge 0:x^{+}-x^{-}-B(y^{+}-y^{-})=c\}$$

where $B=[{\partial }_p]\in {\mathbb{Z}}^{m\times n}$. For $Z\subseteq [m]$ and $T\subseteq [n]$, denote by $B[Z,T]$ the $|Z|\times |T|$ submatrix of $B$ with rows $Z$ and columns $T$. Each vertex of $P$ is then indexed by a pair $(Z,T)$ where $B[Z,T]$ is nonsingular. The vertex is integral if and only if $c{|}_Z$ is in the lattice $B[Z,T]{\mathbb{Z}}^T$.

We start by reducing the problem into an ${\ell }^1$ problem by eliminating the $x$-variables:

Lemma 1: Define

$$F(y)=\sum _{i=1}^m{w}_i|c_i+(By{)}_i|+\lambda \sum _{j=1}^n{v}_j|y_j|.$$

Then the LP value is ${\min }_{y\in {\mathbb{R}}^n}F(y)$ and the LP has integral optimal solution iff $F$ attains its minimum at $y\in {\mathbb{Z}}^n$.

Proof. Let $(x^{+},x^{-},y^{+},y^{-})$ be a feasible solution to the LP with objective $z$, set $x=x^{+}-x^{-}$ and $y=y^{+}-y^{-}$. Clearly, $F(y)=z$ as

$$x^{+}-x^{-}-B(y^{+}-y^{+})=c⟹x^{+}-x^{-}=c+B(y^{+}-y^{-}),$$

$|x_i^{+}-x_i^{-}|=x_i^{+}+x_i^{-}$, and $|y_j|=y^{+}+y^{-}$. Thus, the optimum $z^{\ast }$ is given by $\inf F$. $\square$

Vertices of $P$

Lemma 2: A point of a standard-form polyhedron $\{u\ge 0:Au=c\}$ is a vertex iff the columns of $A$ indexed by its strictly positive coordinates are linearly independent.

Proof. Assume that the columns $A_S$ are linearly dependent, where $S=\{j:u_j>0\}$. Thus, there is a vector $d$ with $Ad=0$ and $d_S\ne 0$. Consider $u\pm ϵd$ for small $ϵ>0$. Then $A(u\pm ϵd)=Au\pm ϵ\cdot 0=c$ and $(u\pm ϵd)\ge 0$ for small enough $ϵ$. Thus, we found two vectors such that

$$u=\frac{1}{2}(u+ϵd)+\frac{1}{2}(u-ϵd).$$

Now assume that the columns $A_S$ are linearly independent. Let $p,q$ be feasible with $u=\lambda p+(1-\lambda )q$. Notice that for $j\in S$, $u_j=0$ forces $p_j=q_j=0$. Moreover, $Ap=Aq=c$ implies that $A(p-q)=0$. So $A_S(p-q{)}_S=0$. Since $A_S$ is linearly independent, we get $p-q=0$. Thus, $u=p=q$. $\square$

Lemma 3: A point $u\in P$ is a vertex iff $x_i^{+}{x}_i^{-}=0$ and $y_j^{+}{y}_j^{-}=0$ for all $i,j$ and the submatrix $B[Z,T]$ has full rank, where $T=\{i:y_i\ne 0\}$ and $Z=\{i:x_i=0\}$.

Proof. Note that the active columns (up to sign) are

$$\{e_i:x_i\ne 0\}\cup \{B_j:y_j\ne 0\}.$$

Let $\alpha$ and $\beta$ be real-vectors such that

$$\sum _{i:x_i\ne 0}{\alpha }_i{e}_i+\sum _{j:y_j\ne 0}{\beta }_j{B}_j=0.$$

Looking at rows $Z$ ($\{i:x_i=0\}$) of the above sum, we get that $B[Z,T]\beta =0$. Thus, our active columns are linearly independent iff $B[Z,T]$ has trivial kernel, i.e., full rank. Now assume that $B[Z,T]\beta =0$ for some $\beta \ne 0$, then for all $i\notin Z$ we get ${\alpha }_i{e}_i+\sum {\beta }_j{B}_j=0$ implying that our active columns are not linearly independent. Thus, $u$ is not a vertex. $\square$

Lemma 4: Every vertex arises as follows: choose $T\subseteq [n]$ and $Z^{\prime }\subseteq [m]$ with $|Z^{\prime }|=|T|$ and $\det B[Z^{\prime },T]\ne 0$, set

$$\begin{array}{rlrlr}{y}_T=-B[Z^{\prime },T{]}^{-1}{c}_{Z^{\prime }}& & y_{[n]\setminus T}=0& & x=c+By\end{array}$$

split into positive and negative parts. Conversely, every such choice produces a vertex of $P$.

Proof. Let $B[Z,T]$ have full rank, pick $|T|$ independent rows $Z^{\prime }\subseteq Z$ where $Z=\{i:x_i=0\}$. To satisfy feasibility, we need $B[Z^{\prime },T]y_T=-c_{Z^{\prime }}$, indeed, since $x_{Z^{\prime }}=0$ we get

$$x_{Z^{\prime }}-B[Z^{\prime },T]y_T=c_{Z^{\prime }}⟹-B[Z^{\prime },T]y_T=c_{Z^{\prime }}.$$

Thus, $y_T=-B[Z^{\prime },T{]}^{-1}{c}_{Z^{\prime }}$.

For the converse, let $y_T=-B[Z^{\prime },T{]}^{-1}{c}_{Z^{\prime }}$, $y_{[n]\setminus T}=0$ and $x=c+By$ for $T\subseteq [n]$, $Z^{\prime }\subseteq [m]$ with $|Z^{\prime }|=|T|$. Notice that

$$\begin{array}{rl}{x}_{Z^{\prime }}& =c_{Z^{\prime }}+(By{)}_{Z^{\prime }}\\ & =c_{Z^{\prime }}+B[Z^{\prime },T]y_T\\ & =c_{Z^{\prime }}-B[Z^{\prime },T]B[Z^{\prime },T{]}^{-1}{c}_{Z^{\prime }}\\ & =0.\end{array}$$

$\square$

Question: Why are the active columns linearly independent in the converse direction? Claude just says its the same argument as before.

Let $u$ be a vertex represented by $(Z^{\prime },T)$ as in Lemma 4. Define the lattice

$$B[Z^{\prime },T]{\mathbb{Z}}^T=\{B[Z^{\prime },T]z:z\in {\mathbb{Z}}^T\}.$$

By Lemma 4, it is clear that $u$ is integral iff $c_{Z^{\prime }}\in B[Z^{\prime },T]{\mathbb{Z}}^T$ as $y_T=-B[Z^{\prime },T{]}^{-1}{c}_{Z^{\prime }}$ and $c_{Z^{\prime }}=B[Z^{\prime },T]z$ for some $z\in {\mathbb{Z}}^T$. A fancier way of saying this is that the class $[c_{Z^{\prime }}]$ vanishes in the finite abelian group

$$G(Z^{\prime },T)={\mathbb{Z}}^{Z^{\prime }}/B[Z^{\prime },T]{\mathbb{Z}}^T$$

where a coset $[c]$ is given by

$$[c]=c+B[Z^{\prime },T]{\mathbb{Z}}^T=\{c+B[Z^{\prime },T]z:z\in {\mathbb{Z}}^T\}.$$

The order of this group is $|\det B[Z^{\prime },T]|$.

Proposition 5: Let $u$ be a vertex represented by $(Z^{\prime },T)$ as in Lemma 4 with $c\in {\mathbb{Z}}^m$. Then

1. $u$ is integral iff $c_{Z^{\prime }}\in B[Z^{\prime },T]{\mathbb{Z}}^T$
2. The least common denominator of the entries of $u$ equals the order of $[c_{Z^{\prime }}]$ in $G(Z^{\prime },T):={\mathbb{Z}}^{Z^{\prime }}/B[Z^{\prime },T]{\mathbb{Z}}^T$.
3. If $|\det B[Z^{\prime },T]|=1$, then $u$ is integral.

Proof.

1. See paragraph above.
2. Let $k\ge 1$ be the smallest integer such that $ku\in {\mathbb{Z}}^T$. Then $k{c}_{Z^{\prime }}=B[Z^{\prime },T](k{y}_T)\in B[Z^{\prime },T]{\mathbb{Z}}^T$. The number $k$ here is the order $[c_{Z^{\prime }}]$ by definition.
3. Follows from Cramer’s rule:

$$y_{T_i}=-\frac{-\text{adj}(A_i)}{\det B[Z^{\prime },T]}$$

where $A_i$ is $B[Z^{\prime },T]$ with column $i$ replaced by $c_{Z^{\prime }}$. $\square$

Torsion

Claude simply cites Dey–Hirani–Krishnamoorthy’s Theorem 5.2.

Lemma 6: Let $T$ be a set of $p$-simplices and $Z$ a set of $(p-1)$-simplices of $K$. Let $L$ be the subcomplex given by the closure of $T\cup Z$. Let $L_0\subseteq L$ be the subcomplex given by the $(p-2)$-skeleton of $L$ together with all $(p-1)$-simplices of $L$ not in $Z$. Then

$$H_{p-1}(L,L_0;\mathbb{Z})\cong {\mathbb{Z}}^Z/B[Z,T]{\mathbb{Z}}^T.$$

Characterization Theorems

Theorem 1: Fix $c\in {\mathbb{Z}}^m$. The following are equivalent:

1. For every $w,v\ge 0,\lambda \ge 0$, the LP has an integral optimal solution;
2. every vertex of $P$ is integral;
3. for every $(Z^{\prime },T)$ with $B[Z^{\prime },T]$ square nonsingular, $[c{|}_{Z^{\prime }}]=0$ in $H_{p-1}(L,L_0)\cong {\mathbb{Z}}^{Z^{\prime }}/B[Z^{\prime },T]Z^T$

Theorem 2: The following are equivalent:

1. For every $c\in {\mathbb{Z}}^m$ and all $w,v,\lambda \ge 0$, the LP has an integral optimal solution;
2. $B$ is totally unimodular
3. $H_{p-1}(L,L_0)$ is torsion-free for all subcomplex pairs $L_0\subseteq L\subseteq K$.

Theorem 3: Fix $c\in {\mathbb{Z}}^m$. Parameterize objectives by $\theta =(w,\mu )\in {\mathbb{R}}_{\ge 0}^m\times {\mathbb{R}}_{\ge 0}^n$ with $\mu =\lambda v$, and for a vertex $u$ let $g(u)=(|x|,|y|)$, so the cost of $u$ is $⟨\theta ,g(u)⟩$. Then

1. The instance has an integral optimum iff ${\min }_{Z^n}F={\min }_{{\mathbb{R}}^n}F$. In particular, if some optimal vertex has vanishing certificate $[c{|}_{Z^{\prime }}]=0$, then an integral optimum exists.
2. Each vertex $u$ owns a closed polyhedral cone $N(u)=\{\theta :u\text{ optimal}\}$ and these finitely many cones cover the parameter space, and instances without integral optima occur only for $\theta \in \bigcup \{N(u):u\text{ fractional}\}$.
3. If $\theta$ is strictly positive and the optimal vertex $u$ is unique, then the optimal face is exactly $\{u\}$, and the instance has an integral optimum iff $[c{|}_{Z^{\prime }}]=0$ for $u$‘s data.

The Counterexample

Claude also discussed the counterexample from 2026-07-09. Recall that our fractional optimum was

$$\begin{array}{rl}z& =3.00009\\ \mathbf{x}& =\frac{1}{2}[3,4]+\frac{1}{2}[0,1]+\frac{1}{2}[1,2]+\frac{1}{2}[4,5]+\frac{1}{2}[2,3]-\frac{1}{2}[0,5]\\ \mathbf{y}& =\frac{1}{2}[3,4,6]+[0,4,6]-\frac{1}{2}[0,3,6]-\frac{1}{2}[1,4,6]-\frac{1}{2}[0,1,6]-[4,6,7]\\ & +\frac{1}{2}[1,4,7]-[2,4,7]-\frac{1}{2}[1,2,7]+\frac{1}{2}[4,5,7]-\frac{1}{2}[5,7,8]-\frac{1}{2}[2,7,8]\\ & -\frac{1}{2}[2,3,8]-\frac{1}{2}[0,5,8]-\frac{1}{2}[0,3,8]\end{array}$$

In the language above, $y^{\ast }$ is supported on 15 triangles $T$ and $x^{\ast }$ vanishes on 15 edges $Z^{\prime }$:

$$\begin{array}{rl}T& =\{[3,4,6],[0,4,6],[0,3,6],[1,4,6],[0,1,6],[4,6,7],[1,4,7],[2,4,7],[1,2,7],[4,5,7],[5,7,8],\\ & [2,7,8],[2,3,8],[0,5,8],[0,3,8]\}\\ Z^{\prime }& =\text{edges}\setminus \{[3,4],[0,1],[1,2],[4,5],[2,3],[0,5]\}.\end{array}$$

Our group corresponds to ${\mathbb{Z}}^{Z^{\prime }}/B[Z^{\prime },T]{\mathbb{Z}}^T\cong Z/2$ as $k=2$ is the smallest positive integer such that $k{c}_{Z^{\prime }}\in B[Z^{\prime },T]{\mathbb{Z}}^T$.

However, we did find that this solution tied with an integral solution. Consider our two solutions $u_{\text{int}}$ and $u_{\text{frac}}$. According to Theorem 3, there are two closed polyhedral cones:

$$\begin{array}{rl}N(u_{\text{int}})& =\{\theta :u_{\text{int}}\text{ optimal}\}\\ N(u_{\text{frac}})& =\{\theta :u_{\text{frac}}\text{ optimal}\}.\end{array}$$

Our example showed that $N(u_{\text{int}})\cap N(u_{\text{frac}})\ne \varnothing$. Theoretically, one could find a perturbation $ϵ$ such that $\theta +ϵ\in N(u_{\text{int}})$, that is, $ϵ$ points in the direction of $N(u_{\text{int}})$, but is small enough that it stays in the closed polyhedral cone.

The direction should be straightforward: if $\theta$ is sitting on a face of $N(u_{\text{frac}})$, then perturb $\theta$ normal to the face. However, this needs to be done without computing $N(u_{\text{frac}})$. The perturbation would also have to be done in a manner that does not change the objective. Hence, we would have to somehow extract $u_{\text{int}}$.