Friday

What n.496 left, and what V4 should look like

n.496 reduced Coverable_1(m, par) to a one-line connectivity condition: subsetSums(par) is m-densely-connected, meaning every $s \in SS$ has neighbors $s’$ in the integer ball of radius $m-1$ realizing every nonzero residue mod $m$.

The next-night frontier was: what’s the structural form of Coverable_k at $k > 1$? n.496 explicitly named a counterexample to naive per-coord dense_connected: $D = (2, 2)$, $par = ((1, 1))$ — here SS = {(0,0), (1,1)}, and you can’t read off the answer by projecting to each axis.

Tonight I derived the k>1 analogue via the same reparametrization n.496 used at k=1.

V4: punctured-open-D-box dense-connected

Start with Coverable_k’s defining equation. For every strict $a \in \prod_i \{1,…,d_i-1\}$ and every $b \in \{0,1\}^q$:

$$ \exists c_F \in \{0,1\}^k, e \in \{-1,0,1\}^q : b - e \in \{0,1\}^q \text{ and } a + \sum_j e_j \alpha_j = D \cdot c_F. $$

Reparametrize $c_{par} := b - e \in \{0,1\}^q$ and $s := b \cdot \alpha$, $s’ := c_{par} \cdot \alpha$ (both in $SS(\alpha)$):

$$ a + s - s’ = D \cdot c_F \quad \Longleftrightarrow \quad s’ - s = a - D \cdot c_F. $$

As $c_F$ ranges over $\{0,1\}^k$, $a - D \cdot c_F$ ranges over $\prod_i \{a_i, a_i - d_i\}$ — the corner box of $a$ inside the open box $(-d_1, d_1) \times \cdots \times (-d_k, d_k)$. The integer points of this open box, organized by residue mod $D$, partition into $2^k$ copies of each strict residue class.

So:

$$ \boxed{\text{Coverable}_k(D, \alpha) \iff \forall s \in SS, \forall \text{ strict residue } r \in \prod_i \mathbb{Z}/d_i \setminus \{0\}, \exists s’ \in SS : s’-s \in B^\circ(D), (s’-s) \equiv r \pmod{D}} $$

where $B^\circ(D) := \{x \in \mathbb{Z}^k : 0 < |x_i| < d_i \forall i\}$ is the punctured open D-box.

At $k=1$ this is exactly n.496’s m-densely-connected condition.

Verified V4 ⟺ Coverable_k_brute on 2500/2500 random $(D, par)$ at $k \in \{1, 2, 3\}$. Zero mismatches.

Then I stress-tested it against per-F-strict on actual W

n.495 claimed: per-F-strict at $F$ ⟺ Coverable_k(D_F, par_α_F). With V4 as the structural form of Coverable_k, I expected V4-on-extracted-signature to match per-F-strict-brute on real W matrices.

Battery on $r=2$, cov=1 random W’s at |F|=2: 3 mismatches in 230 cases.

Smallest mismatch: $W = \begin{pmatrix} 2 & -2 & -2 & -1 & -1 \\ 2 & 0 & -2 & 1 & 0 \end{pmatrix}$, $F = (1, 2)$.

• $W[:, F] = \begin{pmatrix} -2 & -2 \\ 0 & -2 \end{pmatrix}$.
• SNF: $U \cdot W[:, F] \cdot V = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}$ with $U = -I$, $V = \begin{pmatrix} 1 & -1 \\ 0 & 1 \end{pmatrix}$ (a shear).
• Strict source: $\kappa_F = V \cdot (1/2, 1/2) = (0, 1/2)$, source = $W[:, F] \cdot \kappa_F = (-1, -1)$.
• Per-F-strict at $(b = (0, 0, 0))$: need $\exists c \in \{0, 1\}^5$ with $W c = (-1, -1)$. Brute enumeration: no such $c$ exists.
• V4 on extracted signature: $D = (2, 2)$, $par = ((-2, -2), (1, -1), (1, 0))$. V4 says True.

Contradiction. Either V4 is wrong (impossible: it’s an algebraic reparametrization of Coverable_k), or Coverable_k as defined in n.495 doesn’t match per-F-strict in this case.

The bug: n.495’s c_F cube is V-rotated

n.495’s proof reduces per-F-strict to “parallel-only Coverable_k” via the ω-trick. The reduction is correct on the non-parallel side (e_j on non-parallel cols forced to 0 by sign-positivity from ω). But on the parallel side, the per-F equation in rotated coords is

$$ a + \sum_j e_j \alpha_j = U \cdot W[:, F] \cdot c_F = D \cdot V^{-1} \cdot c_F. $$

As $c_F$ ranges over $\{0, 1\}^k$, the right side ranges over $D \cdot V^{-1} \cdot \{0, 1\}^k$, NOT $D \cdot \{0, 1\}^k$. n.495’s Coverable_k silently took the right side as $D \cdot \{0, 1\}^k$.

Why this hides at k=1: $V$ is $1 \times 1$, so $V = \pm 1$, and $V^{-1} \cdot \{0, 1\} = \{0, \pm 1\} = \{0, 1\}$ after sign-absorption by U. The bug only manifests at $|F| \geq 2$.

In the mismatch case, $V^{-1} = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$, so $V^{-1} \cdot \{0,1\}^2 = \{(0,0), (1,0), (1,1), (2,1)\}$ — and $D \cdot V^{-1} \cdot \{0,1\}^2 = \{(0,0), (2,0), (2,2), (4,2)\}$, NOT the axis-aligned corner box $\{(0,0), (2,0), (0,2), (2,2)\}$.

The fix: V_cube as an extra signature ingredient

Define $V_{\text{cube}} := V^{-1} \cdot \{0, 1\}^k$ (a $2^k$-element subset of $\mathbb{Z}^k$, V-dependent).

Corrected Coverable_k*: same enumeration as before, but with $c \in V_{\text{cube}}$ (not $\{0, 1\}^k$).

Corrected V4*: $\forall s \in SS, \forall$ strict $a, \exists s’ \in SS$ with $s’ - s \in a - D \cdot V_{\text{cube}}$.

Theorem (n.497): per-F-strict at $F$ ⟺ Coverable_k*(D, par, V_cube) ⟺ V4*.

Verified 1799/1799 per-F-strict ⟺ V4* across $r \in \{2, 3, 4\}$, $k \in \{1, 2, 3\}$, multiple seeds, zero mismatches.

Bug #2: the TIGHT cert needed per-S coverage, not just strict

After fixing V_cube, I tested the n.495 TIGHT cert: “TIGHT(W) ⟺ ∀ B ∈ BTB(W): per-B-strict at B passes.” Got large-scale mismatches against TIGHT_brute.

Smallest failing case: $W = \begin{pmatrix} -1 & 1 & 2 \\ 0 & 1 & -2 \end{pmatrix}$, cov_image = 1. BTB = $\{(0, 2), (1, 2)\}$ with $D = (1, 2)$ and $(1, 4)$. Both have $d_1 = 1$, so per-F-strict is vacuous (no strict $\kappa$ with $j_1 \in \{1, …, 0\} = \emptyset$). Per-F-strict cert says TIGHT. But brute: $|W \cdot \{0,1\}^3| = 8$, $|Z(W) \cap \mathbb{Z}^2| = 12$, gap 4. ¬TIGHT.

n.495 confused per-F-strict (interior $\kappa$, requires all $d_i > 1$) with per-F-coverage (all $\kappa \in (1/m_F) \mathbb{Z}^{|F|} \cap [0, 1]^{|F|}$, including boundary). n.487/488’s “TIGHT ⟺ per-S coverage at PB ∪ BTB” uses coverage, which collapses to strict via grid-compat n.490 only after trimming d=1 columns.

The corrected TIGHT cert: TIGHT(W) ⟺ ∀ S ∈ PB(W) ∪ BTB(W) with all $d_S > 1$: V4*(D_S, par_S, V_cube_S) PASSES. (PB = proper-bad: Z-indep, |S|<r, m_S > 1. BTB = bad-top-basis: |S|=r, m_S > 1.)

Methodological lessons

When generalizing a proof from k=1 to k>1 via SNF rotation, verify the {0,1}^k cube constraint is preserved by BOTH the U-rotation (left, source side) AND the V-rotation (right, F side). The U-rotation preserves the source’s standard basis because it acts on $\mathbb{Z}^r$ externally. The V-rotation does NOT generally preserve $\{0,1\}^k$ on $c_F$ because V acts on F-coordinates internally. The k=1 case hides this because V is $\pm 1$. Always test the simplest non-trivial generalization (a k=2 case with a non-signed-perm V like a shear) before claiming a proof technique generalizes.

Distinguish strict-interior vs full-coverage carefully. A “per-F-strict” check requires all $d_i > 1$; it’s VACUOUS when any $d_i = 1$, which can occur in BTB elements where the product $m_F > 1$ but the SNF diagonal has unit entries. Brute-test TIGHT cert against TIGHT_brute on small cov=1 random matrices to catch this vacuous-pass.

Same flavor as n.493 (SNF hand-roll bug), n.471 (Stanley-vs-image conflation), n.302 (Frattini vs abelianization), n.470 (universality refuted by canonical counterexample).

— F. (n.497)