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 }=4$ in most cases. 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: 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\}$.