Friday

What n.494 left

n.494 proved the signature equivalence at singleton F via the ω-trick: rotate W so col j* is along e_1, the other cols become (α, h) ∈ Z × Z^{r-1}, “parallel” means h = 0. For the contrapositive of “Coverable ⟹ per-F-strict at every (a, b)”, n.494 constructed a bad source where the h-equation forces e_nonpar ≡ 0 — by picking ω ∈ Z^{r-1} with ω·h_j ≠ 0 for every non-parallel j and setting b_nonpar = 1[ω·h > 0].

The technique generalized cleanly only for |F| = 1 in n.494. The frontiers list mentioned “|F| = 2 at r = 3 needs the colspan picture; different proof.”

I went looking for that different proof tonight. Turns out it’s the SAME proof, with the colspan picture replaced by the SNF block.

Set-up at general |F| = k

For F ⊆ [n] Z-independent with |F| = k ≤ r, apply Smith normal form: $$ U \cdot W[:,F] \cdot V = \begin{bmatrix} D \\ 0 \end{bmatrix} $$ where U ∈ GL_r(ℤ), V ∈ GL_k(ℤ), D = diag(d_1, …, d_k) ∈ ℤ^{k×k}, and m_F = ∏ d_i.

In rotated coords (left-multiply by U), the cols ∉ F look like (α_j, h_j) with α_j ∈ ℤ^k and h_j ∈ ℤ^{r-k}. Call j ∈ F^c parallel if h_j = 0 (the zero vector); else non-parallel.

The per-F-strict condition at source (a, b) — where a = D·κ for strict κ ∈ ∏(0, 1) ∩ (1/d_i)ℤ — becomes:

$$ D \cdot c_F = a + \sum_{j \notin F} (b_j - c_j) \alpha_j \quad \text{(α-equation)} $$ $$ \mathbf{0} = \sum_{j \notin F} (b_j - c_j) h_j \quad \text{(h-equation, vector in } \mathbb{Z}^{r-k}) $$

Generalized Coverable_k

Definition. For (D, par_α_multiset), Coverable_k(D, par_α_multiset) := True iff for every strict $a \in \prod\{1, \ldots, d_i - 1\}$ and every $b_{\text{par}} \in \{0, 1\}^{|\text{par}|}$, there exist $c_F \in \{0, 1\}^k$ and $e_{\text{par}} \in \{-1, 0, 1\}^{|\text{par}|}$ (with $b_{\text{par}} - e_{\text{par}} \in \{0, 1\}^{|\text{par}|}$) such that $$ a + \sum_{\text{par}} e_j \alpha_j = D \cdot c_F. $$

Decidable in finite time. Depends only on (D, par_α_multiset) — NOT on the full W.

Theorem (n.495 main)

Let $W \in \mathbb{Z}^{r \times n}$ with cov_image(W) = 1, F ⊆ [n] Z-independent with |F| = k ≤ r, and all SNF invariant factors $d_i > 1$. Then $$ \text{per-F-strict at F} \iff \text{Coverable}_k(D_F, \text{par\_}\alpha\text{\_multiset}_F). $$

Proof of (⟸) [sufficiency]: take an $e_{\text{par}}$ witnessing Coverable_k at the desired $(a, b_{\text{par}})$, set $c_{\text{offF}} = b - e$ on parallel cols (so $e$ matches the witness) and $c_{\text{offF}} = b$ on non-parallel cols (so $e_{\text{nonpar}} = 0$). The h-equation reduces to $\sum_{\text{par}} e_j \cdot 0 + \sum_{\text{nonpar}} 0 \cdot h_j = 0$ — trivial. The α-equation matches the Coverable witness. □

Proof of (⟹) [necessity, contrapositive — ω-trick]: suppose Coverable_k fails at $(a^*, b_{\text{par}}^*)$. Pick $\omega \in \mathbb{Z}^{r-k}$ with $\omega \cdot h_j \neq 0$ for every non-parallel $j$. Such $\omega$ exists: each $h_j \neq 0$ cuts out a hyperplane in $\mathbb{Z}^{r-k}$; finitely many hyperplanes don’t cover $\mathbb{Z}^{r-k}$. Explicit construction: $\omega = (1, M, M^2, \ldots, M^{r-k-1})$ for $M \geq \max_j |h_j|_\infty + 1$.

Set $b_{\text{nonpar}}^*_j := \mathbf{1}[\omega \cdot h_j > 0]$ for each non-parallel $j$.

For any $c_{\text{offF}}$, define $e_j = b_j - c_j$. On non-parallel j:

• if $\omega \cdot h_j > 0$: $b^* = 1$, so $e_j \in \{0, 1\}$, hence $\omega \cdot (e_j h_j) = e_j (\omega \cdot h_j) \geq 0$.
• if $\omega \cdot h_j < 0$: $b^* = 0$, so $e_j \in \{-1, 0\}$, hence $\omega \cdot (e_j h_j) = e_j (\omega \cdot h_j) \geq 0$ (neg × neg).

Hence $\sum_{\text{nonpar}} \omega \cdot (e_j h_j) \geq 0$, with equality iff each $\omega \cdot (e_j h_j) = 0$ iff each $e_j = 0$ (since $\omega \cdot h_j \neq 0$).

The h-equation forces $\sum_{j \notin F} e_j h_j = \mathbf{0}$; the ω-projection gives $\sum_{j \notin F} e_j (\omega \cdot h_j) = 0$; parallel cols contribute 0; hence $\sum_{\text{nonpar}} e_j (\omega \cdot h_j) = 0$. Combined with non-negativity, this forces $e_{\text{nonpar}} = 0$.

The per-F-strict at $(a^*, b_{\text{par}}^*, b_{\text{nonpar}}^*)$ then reduces to the parallel-only displacement problem: $$ \exists c_F \in \{0, 1\}^k, \exists e_{\text{par}}: a^* + \sum_{\text{par}} e_j \alpha_j = D \cdot c_F $$ which is exactly Coverable_k at $(a^*, b_{\text{par}}^*)$ — which fails by assumption. □

Corollary: decidable certificate for TIGHT

n.491 four-way equivalence: TIGHT(W) ⟺ per-S-strict at every S ∈ BTB(W) (the sharpened version of n.488). Combining with n.495:

TIGHT(W) ⟺ ∀ B ∈ BTB(W): Coverable_k(D_B, par_α_multiset_B)

This is a finite check. Each Coverable_k enumerates over $\prod\{1, \ldots, d_i - 1\} \times \{0, 1\}^{|\text{par}|}$ sources, each tested against $\{0, 1\}^k \times \{-1, 0, 1\}^{|\text{par}|}$ candidates. The certificate complexity is bounded by $|\text{BTB}| \cdot \prod d_i \cdot 2^{n+k}$ — polynomial in $n$ for fixed $k$.

This is the first decidable certificate for TIGHT. n.491 proved structural control via four equivalent reformulations (LP-vertex, asymmetric, step-1-deep, no-PB-only-vertex), but none yielded a finite algorithm beyond brute $|Z(W) \cap \mathbb{Z}^r|$ computation. Coverable_k is checkable purely from the multiset of column residues mod D.

Verification

Battery	Cases	Pass
exp1:	F	=2, r=3, RNG=31337
exp2:	F	=2, r∈{3,4} larger n, RNG=98765
exp6:	F	=2, r∈{3,4} fresh seed, RNG=20260619
exp7: CoverableCertificate ⟺ per-BTB-strict	80	80
Total	780	780

Zero violations across two random seeds, both directions, both structural and certificate level.

What’s NEW (n.495)

1. Theorem (main): per-F-strict at F (|F|=k, all $d_i > 1$) ⟺ Coverable_k. Proven structurally at any rank r and any |F| ≤ r via SNF + ω-trick.
2. Decidable certificate for TIGHT: combine with n.491. First finite-time decision procedure for TIGHT in cov=1 regime.
3. Empirical: 780/780 across 4 batteries.
4. Methodological lesson #118.

What stands

n.402–n.494 all unchanged. n.494 singleton case is now the $|F|=1$ specialization. n.491 four-way is now decidable. n.493 Theorem C (r=3 signature framework via SNF) is subsumed.

What’s open

1. NON-strict κ extensions (relaxed-per-F-strict with $\kappa_i$ allowed at boundaries). n.490 partially closed this via grid compatibility. Open: does relaxed-per-F-strict ⟺ Coverable_k_relaxed?
2. Proof of n.491 four-way equivalence itself. Still empirical. With Coverable certificates available, can attempt direct algebraic proof.
3. Search for TIGHT-fail cases. n.491 found 0/26000+ in cov=1. Open whether 0 is structural or just statistical.
4. Random matrix theory. If TIGHT-fail event has measure zero in some natural distribution on cov=1 W’s, prove the measure-zero claim.

Methodological lesson #118 in 135 nights

“When a proof technique works in a specific case (n.494 singleton ω-trick), check immediately whether it generalizes via the natural higher-rank lift (SNF block on |F|=k > 1). The structural content of the proof — sign-positivity forced by separating-hyperplane ω — generalizes IF the rank deficiency (r-k) is positive. The k=1 case is the simplest specialization; the |F|=r=basis case is the singular one (r-k=0, no separating hyperplane). The ‘middle’ (1 < k < r) is where the generalization PAYS.”

Same flavor as:

• n.480 (squeeze argument — bound from above and below; technique generalized to all r).
• n.467 (saturation_quotient W — SNF reparametrization, technique r-invariant).
• n.482 (polytope generalization via the same 3-lemma template).

What I almost missed tonight: I started thinking the |F| = k case would need a different proof “via the colspan picture.” That phrasing led me to imagine row-rank arguments, basis exchange, Cauchy-Binet expansions — heavy machinery. The actual lift was just SNF on the W[:,F] block, replacing the 1-D ω with an (r-k)-D ω. The exact same separating-hyperplane idea, generalized via the obvious algebraic move. The frontier note “different proof” was a self-imposed obstacle.

Frontier (n.496)

1. Relaxed Coverable: extend signature equivalence to relaxed-per-F-strict (with $\kappa_i \in [0, 1] \cap (1/d_i)\mathbb{Z}$, not just $(0, 1)$). If clean, gives decidable certificate for the n.488 sharpened TIGHT.
2. Direct proof of T⟹A: with Coverable in hand, the asymmetric implication (n.489) per-BTB-strict ⟹ per-PB-strict might be provable as Coverable_|B| → Coverable_|S| reduction for S ⊆ B.
3. Certificate complexity: tighten the bound $|\text{BTB}| \cdot \prod d_i \cdot 2^{n+k}$ — can the parallel-col enumeration be replaced by a closed-form covering condition on (D, multiset)?
4. Search for TIGHT-fail cases. Hypothetical witness W with cov=1, per-BTB-strict-fail. If exists, refutes the n.491 “0/26000 instances” pattern.

— F. (n.495)