2026-08-31

Quick recap from 2026-8-17:

Lemma 1: Given a fractional vertex $u=(x^{+},x^{-},y^{+},y^{-})$ to the flat norm LP, the closest integral vertex can be found by solving

$$\underset{d\in {\mathbb{Z}}^n}{\min }(\Vert w\odot (Bd-r){\Vert }_1+\lambda \Vert v\odot d{\Vert }_1)$$

where

$$r=\lceil x^{+}\rceil -\lceil x^{-}\rceil -B(\lceil y^{+}\rceil -\lceil y^{-}\rceil )-c.$$

Lemma 2: If $\Vert r{\Vert }_{\infty }\le 1/2$, then the closest integral vertex can be found by taking the ceiling of $y^{+}$ and $y^{-}$ and computing

$$x=c+B(\lceil y^{+}\rceil -\lceil y^{-}\rceil ).$$

Numerical experimentation suggests found that $\Vert r{\Vert }_{\infty }=0$ for each weight in our example. Which means we cannot apply Lemma 2 and have to focus on the restricted search space:

$$\mathcal{L}=\left\{d\in {\mathbb{Z}}^n:\Vert \mathbf{w}\odot (Bd-r){\Vert }_1+\lambda \Vert \mathbf{v}\odot d{\Vert }_1\le \Vert \mathbf{w}\odot r{\Vert }_1\right\}.$$

Although it may be worthwhile using the alternative condition that

$$\lambda \Vert v\odot d{\Vert }_1-\sum _{i=1}^n{w}_i{h}_i((Bd{)}_i)\le 0$$

where $h_i(a)=|r_i|-|a-r_i|$.

---

Let $\lceil x^{\pm }\rceil =x^{\pm }+{ϵ}^{\pm }$ and $\lceil y^{\pm }\rceil =y^{\pm }+{\delta }^{\pm }$. Notice that

$$\begin{array}{rl}r& =\lceil x^{+}\rceil -\lceil x^{-}\rceil -B(\lceil y^{+}\rceil -\lceil y^{-}\rceil )-c\\ & =(x^{+}+{ϵ}^{+})-(x^{-}+{ϵ}^{-})-B((y^{+}+{\delta }^{+})-(y^{-}+{\delta }^{-}))-c\\ & =(x^{+}-x^{-})+({ϵ}^{-}-{ϵ}^{-})-B(y^{+}-y^{-})+B({\delta }^{+}-{\delta }^{-})-c\\ & ={ϵ}^{+}-{ϵ}^{-}-B({\delta }^{+}-{\delta }^{-}).\end{array}$$

Recall from 2026-07-20 that every vertex arises as follows: choose $T\subseteq [n]$ and $Z\subseteq [m]$ with $|Z|=|T|$ such that $\det B[Z,T]\ne 0$, where $B[Z,T]$ is the $|Z|\times |T|$ submatrix of $B$ with rows $Z$ and columns $T$; set

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

Consider the Smith normal form for $B[Z,T]$,

$$S=SNF(B[Z,T])=\text{diag}(d_1,d_2,\dots ,d_k)$$

where $d_1\mid d_2\mid \cdots \mid d_k$. Then it follows that there are unimodular matrices $U$ and $V$ such that $UB[Z,T]V=S$. Thus, it follows that $y_T=-V{S}^{-1}U{c}_Z$. Splitting $U$ into $k$ row-vectors $U_1,\dots ,U_k$ gives us that

$$y_T=-V\left[\begin{array}{c}\frac{1}{d_1}{U}_1{c}_Z\\ \frac{1}{d_2}{U}_2{c}_Z\\ ⋮\\ \frac{1}{d_k}{U}_k{c}_Z\end{array}\right].$$

Let ${\alpha }_i=d_k/d_i$. Then we get that for $1\le j\le k$,

$$(y_T{)}_j=-\sum _{i=1}^k{V}_{ji}\frac{U_i{c}_Z}{d_i}=-\frac{1}{d_k}\sum _{i=1}^k{V}_{ji}{\alpha }_i{U}_i{c}_Z=-\frac{Y_j}{d_k}.$$

Define ${\rho }_j$ such that ${\rho }_j=Y_j\mathrm{mod}{d}_k$. Then it follows that

$${\delta }_j^{+}=\{\begin{array}{ll}{\rho }_j/d_k& Y_j<0\\ 0& Y_j\ge 0\end{array}\text{ and }{\delta }_j^{-}=\{\begin{array}{ll}(d_k-{\rho }_j)/d_k& Y_j>0,{\rho }_j\ne 0\\ 0& \text{otherwise}.\end{array}$$

Notice that $y$ is supported on $T$ so it follows that $By=B[[m],T]y_T$. Thus,

$$x_i=c_i+B[\{i\},T]y_T=c_i-B[\{i\},T]B[Z,T{]}^{-1}{c}_Z.$$

Let $T=\{T_1,\dots ,T_k\}$. Then we get that

$$x_j=c_j+\sum _{i=1}^k{B}_{j,T_i}(y_T{)}_j=c_j-\frac{1}{d_k}\sum _{i=1}^k{B}_{j,T_i}{Y}_j=\frac{X_j}{d_k}.$$

Define ${\tau }_j$ such that ${\tau }_j=X_j\mathrm{mod}{d}_k$; then

$${ϵ}_j^{+}=\{\begin{array}{ll}(d_k-{\tau }_j)/d_k& X_j>0,{\tau }_j\ne 0\\ 0& \text{otherwise}\end{array}\text{ and }{ϵ}_j^{-}=\{\begin{array}{ll}{\tau }_j/d_k& X_j<0\\ 0& \text{otherwise}.\end{array}$$

Proposition 1: Assume that the optimal vertex of the flat norm LP has $d_k=2$, and let $T^{\prime }\subseteq T$ be the subcomplex consisting of the $p$-simplices with fractional values. Then it follows that

$$\Vert r{\Vert }_{\infty }\le \frac{1}{2}\left(1+{\Vert {\partial }_p{T}^{\prime }\Vert }_{\infty }\right).$$

In particular, if $K$ is a non-orientable manifold, then $\Vert r{\Vert }_{\infty }\le 3/2$.

Proof. Note that ${\delta }_i={\delta }^{+}-{\delta }^{-}=\pm 1/2$ for all $i\in T^{\prime }$. In such a case,

$$|(B\delta {)}_j|=\left|\sum _{i=1}^n{B}_{ji}{\delta }_i\right|=\frac{1}{2}\left|\sum _{i\in T^{\prime }}{B}_{ji}\right|.$$

Notice that ${\sum }_{i\in T^{\prime }}{B}_{ji}=(B{1}_{T^{\prime }}{)}_j=(\partial T^{\prime }{)}_j$, i.e., the row sum corresponds to the $(p-1)$-simplex ${\sigma }_j$ where $\sigma =\partial T^{\prime }$. So we get that

$$\sum _{i\in T^{\prime }}{B}_{ji}=\#\{\text{cofaces of σj in T′ with sign +1}\}-\#\{\text{cofaces of σj in T′ with sign −1}\}.$$

Let ${\mathcal{C}}_{T^{\prime }}({\sigma }_j)=\{{\tau }_i\in T^{\prime }:{\sigma }_j\subset {\tau }_i\}$. If $K$ is a non-orientable manifold, then we get that

$$\left|\sum _{i\in T^{\prime }}{B}_{ji}\right|=\left|\sum _{i\in {\mathcal{C}}_{T^{\prime }}({\sigma }_j)}{B}_{ji}\right|\le \sum _{i\in {\mathcal{C}}_{T^{\prime }}({\sigma }_j)}|B_{ji}|=\sum _{i\in {\mathcal{C}}_{T^{\prime }}({\sigma }_j)}1=\#{\mathcal{C}}_{T^{\prime }}({\sigma }_j)\le 2.$$

Note that $Y_j\in 2\mathbb{Z}+1$ for $j\in T^{\prime }$ and $Y_j\in 2\mathbb{Z}$ for $j\notin T^{\prime }$. Moreover

$$\begin{array}{rl}{X}_j& =2c_j-\sum _{i=1}^k{B}_{j,T_i}{Y}_j\\ & =2c_j-\sum _{i=1}^k{B}_{j,T_i}{Y}_j\\ & =2c_j-2\sum _{i=1}^k{B}_{j,T_i}{z}_j-\sum _{i\in T^{\prime }}{B}_{j,T_i}\\ & =\underset{\in 2\mathbb{Z}}{\underbrace{2c_j-2\sum _{i=1}^k{B}_{j,T_i}{z}_j}}-2(B\delta {)}_j.\end{array}$$

So we get that ${\tau }_j=\left(-2(B\delta {)}_j\right)\mathrm{mod}2$. Working through the six possible combinations of values of ${ϵ}^{\pm }$ gives us a value of $r_j$ given in the tables below:

If $(B\delta {)}_j\ge 0$:

	$X_j>0$	$X_j<0$	$X_j=0$
${\tau }_j=0$	$-\frac{1}{2}{\sum }_{i\in T^{\prime }}{B}_{ji}$	$-\frac{1}{2}{\sum }_{i\in T^{\prime }}{B}_{ji}$	$-\frac{1}{2}{\sum }_{i\in T^{\prime }}{B}_{ji}$
${\tau }_j=1$	$\frac{1}{2}\left(1-{\sum }_{i\in T^{\prime }}{B}_{ji}\right)$	$-\frac{1}{2}\left(1+{\sum }_{i\in T^{\prime }}{B}_{ji}\right)$	$-\frac{1}{2}{\sum }_{i\in T^{\prime }}{B}_{ji}$

If $(B\delta {)}_j<0$:

	$X_j>0$	$X_j<0$	$X_j=0$
${\tau }_j=0$	$\frac{1}{2}{\sum }_{i\in T^{\prime }}{B}_{ji}$	$\frac{1}{2}{\sum }_{i\in T^{\prime }}{B}_{ji}$	$\frac{1}{2}{\sum }_{i\in T^{\prime }}{B}_{ji}$
${\tau }_j=1$	$\frac{1}{2}\left(1+{\sum }_{i\in T^{\prime }}{B}_{ji}\right)$	$\frac{1}{2}\left(-1+{\sum }_{i\in T^{\prime }}{B}_{ji}\right)$	$-\frac{1}{2}{\sum }_{i\in T^{\prime }}{B}_{ji}$

Taking the absolute value gives us that

$$|r_j|\le \frac{1}{2}\left(1+\left|\sum _{i\in T^{\prime }}{B}_{ji}\right|\right)\le \frac{1}{2}\left(1+\Vert {\partial }_p{T}^{\prime }{\Vert }_{\infty }\right).$$

Therefore, if $K$ is a non-orientable manifold, then $|r_j|\le 3/2$. $\square$

Corollary: If every $(p-1)$-simplex ${\sigma }_j$ in $\partial T^{\prime }$ is a face of exactly one $p$-simplex, then $\Vert r{\Vert }_{\infty }\le 1$.

Proof. In such a case, $\#{\mathcal{C}}_{T^{\prime }}({\sigma }_j)=1$ for all $(p-1)$-simplices ${\sigma }_j$. $\square$

Remark: Notice that if ${\partial }_p{T}^{\prime }=0$, then we get that $\Vert r{\Vert }_{\infty }=0$ which implies that $T^{\prime }=\varnothing$. Therefore, that case would correspond to an integral solution from the flat norm LP.

Remark: The only way we get $\Vert r{\Vert }_{\infty }\le 1/2$ is if $\Vert {\partial }_p{T}^{\prime }{\Vert }_{\infty }=1$ and $X_j=0$ for all $1\le j\le m$. However, there may be another way to get $\mathcal{L}=\{0\}$.

---

Update 9/3:

Recall the alternative condition for feasibility of $d\in {\mathbb{Z}}^n$:

$$f(d)=\lambda \Vert v\odot d{\Vert }_1-\sum _{i=1}^n{w}_i{h}_i((Bd{)}_i)\le 0$$

where $h_i(a)=|r_i|-|a-r_i|$.

Proposition 2: If

$$\lambda \underset{j}{\min }{v}_j>(p+1)\underset{i}{\max }{w}_i$$

then $d^{\ast }=0$. Consequently, we can find the integral solution by taking the ceiling of $y^{\pm }$.

Proof. First notice that

$$h_i(a)=\{\begin{array}{ll}0& a=0\\ 2|r_i|-|a|& a\ne 0,\text{sgn}(a)=\text{sgn}(r_i)\\ -|a|& \text{otherwise}\end{array}⟹h_i=\{\begin{array}{ll}2|r_i|-|a|& a{r}_i>0\\ -|a|& a{r}_i\le 0\end{array}$$

as

$$\begin{array}{r}|a-r_i|=\{\begin{array}{ll}|r_i|& a=0\\ |a|-|r_i|& a\ne 0,\text{sgn}(a)=\text{sgn}(r_i)\\ |a|+|r_i|& \text{otherwise.}\end{array}\end{array}$$

Let $A(d)=\{i:(Bd{)}_i{r}_i>0\}$. Then it follows that

$$\begin{array}{rl}f(d)& =\lambda \Vert v\odot d{\Vert }_1-\sum _{i=1}^n{w}_i{h}_i((Bd{)}_i)\\ & =\lambda \Vert v\odot d{\Vert }_1-\sum _{i\in A(d)}{w}_i(2|r_i|-|(Bd{)}_i|)+\sum _{i\notin A(d)}{w}_i|(Bd{)}_i|\\ & =\lambda \Vert v\odot d{\Vert }_1+\sum _{i=1}^n{w}_i|(Bd{)}_i|-2\sum _{i\in A(d)}{w}_i|r_i|.\end{array}$$

Because $d\in {\mathbb{Z}}^n$, we get that $|(Bd{)}_i|\ge 1$. Thus,

$$\begin{array}{rl}f(d)& \ge \lambda \Vert v\odot d{\Vert }_1+\sum _{i=1}^n{w}_i-2\sum _{i\in A(d)}{w}_i|r_i|\\ & =\lambda \Vert v\odot d{\Vert }_1+\sum _{i\notin A(d)}{w}_i+\sum _{i\in A(d)}{w}_i(1-2|r_i|)\\ & \ge \lambda \Vert v\odot d{\Vert }_1+\sum _{i\in A(d)}{w}_i(1-2|r_i|)\\ & \ge \lambda \Vert v\odot d{\Vert }_1+\sum _{i\in \text{supp}(Bd)}{w}_i(1-2|r_i|)\\ & \ge \lambda \Vert v\odot d{\Vert }_1-\sum _{i\in \text{supp}(Bd)}{w}_i(2|r_i|-1)\end{array}$$

where $\text{supp}(Bd)=\{i:(Bd{)}_i\ne 0\}$.

We also note that

$$\lambda \Vert v\odot d{\Vert }_1\ge \lambda \left(\underset{j}{\min }{v}_j\right)\Vert d{\Vert }_1\ge \lambda \left(\underset{j}{\min }{v}_j\right)\Vert d{\Vert }_0$$

where $\Vert d{\Vert }_0=\#\{i:d_i\ne 0\}$. Because each column of $B$ has exactly $p+1$ non-zero entries, it follows that

$$\#\text{supp}(Bd)\le (p+1)\Vert d{\Vert }_0.$$

As a result,

$$\begin{array}{rlrl}f(d)& \ge \lambda \left(\underset{j}{\min }{v}_j\right)\Vert d{\Vert }_0-\sum _{i\in \text{supp}(Bd)}{w}_i(2|r_i|-1)& & \\ & \ge \lambda \left(\underset{j}{\min }{v}_j\right)\Vert d{\Vert }_0-\sum _{i\in \text{supp}(Bd)}\underset{i}{\max }(w_i(2|r_i|-1))& & \\ & \ge \lambda \left(\underset{j}{\min }{v}_j\right)\Vert d{\Vert }_0-\sum _{i\in \text{supp}(Bd)}\underset{i}{\max }(w_i)& & (|r_i|\le 1)\\ & \ge \lambda \left(\underset{j}{\min }{v}_j\right)\Vert d{\Vert }_0-(p+1)\underset{i}{\max }(w_i)\Vert d{\Vert }_0& & \\ & =\Vert d{\Vert }_0\left(\lambda \underset{j}{\min }{v}_j-(p+1)\underset{i}{\max }{w}_i\right).& & \end{array}$$

Therefore, whenever $d\ne 0$ we get $\Vert d{\Vert }_0>0$ which implies that $f(d)>0$. As a consequence, $d=0$ is the only feasible solution. $\square$

Corollary: Let $F(j)=\{i:B_{ij}\ne 0\}$. If

$$\lambda v_j>\sum _{i\in F(j)}{w}_i$$

for all $1\le j\le n$, then $d^{\ast }=0$.

Proof. Using that $|r_i|\le 1$, we get that

$$\begin{array}{rl}f(d)& \ge \lambda \Vert v\odot d{\Vert }_1-\sum _{i\in \text{supp}(Bd)}{w}_i(2|r_i|-1)\\ & \ge \lambda \Vert v\odot d{\Vert }_1-\sum _{i\in \text{supp}(Bd)}{w}_i\end{array}$$

Taking $d=\pm e_j$ gives us that $(Bd{)}_i\ne 0$ only on $i\in F(j)$ which implies that

$$f(\pm e_j)\ge \lambda v_j-\sum _{i\in F(j)}{w}_i.$$

Using $e_1,\dots ,e_n$ as a basis gives us that if $d\ne 0$ then

$$\begin{array}{rlrl}f(d_1{e}_1+\cdots +d_n{e}_n)& \ge \lambda \sum _{j=1}^n|d_j|v_j-\sum _{i\in \text{supp}(Bd)}{w}_i& & \\ & \ge \lambda \sum _{j\in \text{supp}(d)}|d_j|v_j-\sum _{j\in \text{supp}(d)}\sum _{i\in F(j)}{w}_i& & \\ & \ge \sum _{j\in \text{supp}(d)}\left(\lambda v_j-\sum _{i\in F(j)}{w}_i\right).& & (d_j\in \mathbb{Z}).\end{array}$$

Therefore $d^{\ast }=0$ as $d=0$ is the only feasible solution. $\square$

Remark: From a topological point of view, the above corollary states that if the weight of every triangle (scaled by $\lambda$) is greater than the weights of its boundary edges, then $d^{\ast }=0$. Unfortuntely, as $\lambda <<1$ the above sufficient condition is likely rare to occur.3