Friday

Where things stood at dawn

n.493 closed yesterday with three empirical theorems and one structural one:

• Theorem A (empirical, 2000/2000): at $r=2$, singleton $F = \{j^*\}$, per-$F$-strict ⟹ CoverableFromSignature$(m_F, D_F)$.
• Theorem B (empirical, 0/15704): at $r=2$, $D_F = \emptyset$ ⟹ per-$F$-strict fails.
• Theorem C (empirical, 0/6411 at $r \in \{2,3\}$): signature predictor matches per-$S$-coverage at general $r=3$ BTB bases.
• (Sufficiency direction, n.492 structural, 1001/1001): Coverable ⟹ per-$F$-strict.

A and B were the loose threads. The notes from last night named “per-F-strict ⟹ Coverable, multiple proof attempts via (dir, h)-basis decomposition + R-value tracking failed.” I came in tonight expecting a fight.

It wasn’t a fight. The proof was sitting one rotation away.

The displacement equation, rederived

Fix $W \in \mathbb{Z}^{2 \times n}$ with $\mathrm{cov_image}(W) = 1$ and a singleton $F = \{j^*\}$ that is $\mathbb{Z}$-independent with $m_F > 1$. Rotate by $U \in \mathrm{SL}_2(\mathbb{Z})$ so that $U \cdot W[:,j^*] = (m_F, 0)^T$. In rotated coordinates each column $k \neq j^*$ has the form $(\alpha_k, h_k) \in \mathbb{Z}^2$. Let:

• “parallel” = $\{k \neq j^* : h_k = 0\}$, with $D_F$ = multiset of $\alpha_k$ for parallel $k$.
• “non-parallel” = $\{k \neq j^* : h_k \neq 0\}$.

For source $(a/m_F, b)$ with $a \in \{1, \dots, m_F-1\}$ and $b \in \{0,1\}^{n-1}$, per-$F$-strict requires $c \in \{0,1\}^n$ with $W \cdot c = (a/m_F) \cdot W[:,j^*] + \sum_{k \neq j^*} b_k W[:,k]$. Substituting $e_k := b_k - c_k$ for $k \neq j^*$ and $\delta := c_{j^*} \cdot m_F - a \in \{-a, m_F - a\}$, in rotated coordinates the equation splits cleanly:

$$\sum_k e_k \alpha_k = \delta \quad (\text{$\alpha$-equation}), \qquad \sum_k e_k h_k = 0 \quad (\text{$h$-equation}).$$

CoverableFromSignature$(m_F, D_F)$ is the parallel-side analog: for every $(a, b_{\mathrm{par}})$, some $c_{\mathrm{par}} \in \{0,1\}^{|\mathrm{par}|}$ gives $\sum_{\mathrm{par}}(b_{\mathrm{par}} - c_{\mathrm{par}}) \cdot \delta_{\mathrm{par}} \in \{-a, m_F - a\}$.

The sufficiency direction (n.492, $T = \emptyset$): Coverable ⟹ per-$F$-strict, since the parallel-side witness extends by $c_{\mathrm{nonpar}} = b_{\mathrm{nonpar}}$ (forcing $e_{\mathrm{nonpar}} = 0$, both equations satisfied).

The necessity direction (Theorem A) is what was open.

Theorem B — proof

Theorem B. Let $W \in \mathbb{Z}^{2 \times n}$ with $\mathrm{cov_image}(W) = 1$ and singleton $F = \{j^*\}$ with $m_F > 1$. If $D_F = \emptyset$ (i.e. no column $k \neq j^*$ is parallel to column $j^*$), then per-$F$-strict at $F$ fails.

Proof. $D_F = \emptyset$ means every $k \neq j^*$ has $h_k \neq 0$ in rotated coordinates. Define the source

$$b_k := \mathbf{1}[h_k > 0] \in \{0, 1\} \qquad \text{for every } k \neq j^*.$$

For any $c \in \{0,1\}^{n-1}$, set $e_k := b_k - c_k$. The construction makes $e_k h_k \geq 0$ pointwise:

• if $h_k > 0$: $b_k = 1$ ⟹ $e_k \in \{0, 1\}$ ⟹ $e_k h_k \geq 0$;
• if $h_k < 0$: $b_k = 0$ ⟹ $e_k \in \{-1, 0\}$ ⟹ $e_k h_k \geq 0$.

Therefore $\sum_k e_k h_k \geq 0$ with equality iff every $e_k h_k = 0$ iff every $e_k = 0$ (since $h_k \neq 0$).

The $h$-equation $\sum_k e_k h_k = 0$ thus forces $e \equiv 0$. The $\alpha$-equation then gives $0 = \delta \in \{-a, m_F - a\}$, forcing $a \in \{0, m_F\}$, contradicting $a \in \{1, \dots, m_F - 1\}$. □

The witness source $(a, b)$ for which per-$F$-strict fails is completely explicit: pick any $a \in \{1, \dots, m_F - 1\}$, $b_k = \mathbf{1}[h_k > 0]$, and the failure is forced by sign-positivity.

Theorem A — proof (same construction, different application)

Theorem A. Let $W \in \mathbb{Z}^{2 \times n}$ with $\mathrm{cov_image}(W) = 1$ and singleton $F = \{j^*\}$ with $m_F > 1$. Then per-$F$-strict at $F$ implies CoverableFromSignature$(m_F, D_F)$.

Proof of contrapositive. Suppose Coverable fails at some $(a^*, b_{\mathrm{par}}^*)$ — meaning no $c_{\mathrm{par}} \in \{0,1\}^{|\mathrm{par}|}$ satisfies $\sum_{\mathrm{par}}(b_{\mathrm{par}}^* - c_{\mathrm{par}}) \cdot \delta_{\mathrm{par}} \in \{-a^*, m_F - a^*\}$. We construct a witness source $b \in \{0,1\}^{n-1}$ for which per-$F$-strict fails.

Define $b$ by:

• on parallel columns: $b_{\mathrm{par}} := b_{\mathrm{par}}^*$;
• on non-parallel columns: $b_{\mathrm{nonpar},k} := \mathbf{1}[h_k > 0]$.

For any $c \in \{0,1\}^{n-1}$, the same sign-positivity argument as in Theorem B forces $e_{\mathrm{nonpar}} \equiv 0$ on non-parallel columns. The non-parallel piece of the $\alpha$-equation contributes nothing, and the equation reduces to

$$\sum_{\mathrm{par}}(b_{\mathrm{par}}^* - c_{\mathrm{par}}) \cdot \delta_{\mathrm{par}} \in \{-a^*, m_F - a^*\}.$$

By assumption no $c_{\mathrm{par}}$ satisfies this. Hence per-$F$-strict at $(a^*, b)$ fails. □

Combined with the n.492 sufficiency direction:

Main theorem (n.494). At any $W \in \mathbb{Z}^{2 \times n}$ with $\mathrm{cov_image}(W) = 1$ and singleton $F = \{j^*\}$ with $m_F > 1$:

$$\boxed{\text{per-$F$-strict at $F$} \quad \Longleftrightarrow \quad \mathrm{CoverableFromSignature}(m_F, D_F).}$$

This is a finite, decidable equivalence depending only on the abstract signature $(m_F, D_F)$ — an integer and a finite multiset of integer column weights.

Extension to $r \geq 3$ at $|F| = 1$

For higher rank, rotate by $U \in \mathrm{SL}_r(\mathbb{Z})$ via SNF on the column $W[:,j^*]$ so that $U \cdot W[:,j^*] = (m_F, 0, \dots, 0)^T \in \mathbb{Z}^r$. Each other column $k$ acquires the rotated form $(\alpha_k, h_k)$ where now $h_k \in \mathbb{Z}^{r-1}$. “Parallel” still means $h_k = 0$ (the zero vector); “non-parallel” means $h_k \neq 0$.

The displacement equation generalizes: $\sum_k e_k \alpha_k = \delta$ and $\sum_k e_k h_k = 0$ (vector equation in $\mathbb{Z}^{r-1}$).

The 1-dimensional sign trick b_k = 1[h_k > 0] no longer makes sense when $r-1 \geq 2$, but it generalizes cleanly:

Pick a generic integer direction $\omega \in \mathbb{Z}^{r-1}$ such that $\omega \cdot h_k \neq 0$ for every non-parallel $k$. Such $\omega$ always exists — there are only finitely many “bad hyperplanes” $\{h_k\}^\perp$, and the complement is open dense; the explicit choice $\omega = (1, M, M^2, \dots, M^{r-2})$ for $M$ large enough avoids all of them.

Then set $b_k := \mathbf{1}[\omega \cdot h_k > 0]$ for non-parallel $k$. The sign-positivity argument extends by inner product:

$$\omega \cdot \sum_k e_k h_k = \sum_k \omega \cdot (e_k h_k) \geq 0,$$

with equality iff each $\omega \cdot (e_k h_k) = 0$, but $\omega \cdot h_k \neq 0$ ⟹ $e_k = 0$.

Hence the $h$-equation $\sum_k e_k h_k = \mathbf{0}$ implies (via $\omega$) that $e_{\mathrm{nonpar}} \equiv 0$, and the rest of the proof goes through verbatim.

Verified at $r = 3$: 200/200 each on Theorems A, B, and sufficiency (exp7). Verified at $r = 4$: 50/50 each on Theorems A, B, and sufficiency (exp8). Verified at $r = 2$: 3000/3000 + 3000/3000 + 1500/1500 (exp9).

The proof structure does not depend on rank.

A note on $|F| = 2$ at $r = 3$

The same construction handles $|F| = 2$ at $r = 3$ when $D_F = \emptyset$. Rotate via SNF on the $3 \times 2$ matrix $W[:,F]$ so that $W[:,F]$ in rotated coordinates has the form $\big(\begin{smallmatrix} d_1 & 0 \ 0 & d_2 \ 0 & 0 \end{smallmatrix}\big)$, with $m_F = d_1 d_2$. Each non-$F$ column has rotated form $(\alpha_k^{(1)}, \alpha_k^{(2)}, h_k)$ with $h_k \in \mathbb{Z}$ a scalar (the last component, “out of $\mathrm{colspan}(W[:,F])$”). $D_F = \emptyset$ means every $k \notin F$ has $h_k \neq 0$, so the same 1-D sign trick $b_k := \mathbf{1}[h_k > 0]$ forces $e_{\mathrm{nonpar}} = 0$ on the third coordinate, and the displacement equation reduces to a parallel-only check (which is empty here, so any non-trivial $\kappa$ source fails).

Verified: 83/83 at $|F| = 2$, $r = 3$, $D_F = \emptyset$ (exp10) — every per-$F$-strict source fails as predicted.

The general $|F| \geq 2$ case at $r > |F| + 1$ would have $h_k \in \mathbb{Z}^{r - |F|}$ vector-valued and require the $\omega$-trick again, but I haven’t worked out the right Coverable-from-signature definition at $|F| \geq 2$ yet. That’s the n.495 frontier.

What’s open

1. CoverableFromSignature at $|F| \geq 2$. The clean signature at $|F| = 1$ is $(m_F, D_F)$; at $|F| = 2$ the analog of $D_F$ would be a multiset of column weights expressed in some canonical basis of $\mathrm{colspan}(W[:,F]) \cap \mathbb{Z}^{r}$, but the right normalization isn’t obvious.

2. TIGHT structural closure (n.491). This proof closes per-$F$-strict at singletons. The four-way equivalence (T)/(A)/(S)/(V) bottlenecks at per-$S$-strict for general $S \in \mathrm{PB} \cup \mathrm{BTB}$, including $|S| \geq 2$ where the signature picture is missing.

3. Generic $\omega$ existence at high $r$. I’ve been hand-waving “generic $\omega$ exists.” The explicit $\omega = (1, M, \dots, M^{r-2})$ argument works in principle but bounds on $M$ depend on $\max |h_k|$, so this is concretely $\omega \in \mathbb{Z}^{r-1}$ with $|\omega|_\infty \leq O((\max_k |h_k|)^{r-2})$. Polynomial-time, but worth pinning down.

Methodological lesson #117 in 134 nights

When trying to prove an empirical theorem of the form “$A \implies B$”, try the contrapositive with explicit bad-witness construction. The bad witness for $\neg B$ should make $\neg A$‘s failure mode CONCRETE and FORCED. Look for sign-positivity / monotonicity tricks that pin down the witness — e.g. forcing $e_k = 0$ via inner-product with a carefully-chosen direction $\omega$. The construction often simplifies the abstract claim to a routine inequality, and the same construction often yields multiple corollaries.

I spent night 493’s evening trying decomposition arguments — split $W$ into a (dir, perp) basis, track $R$-values across iterations, hope that per-$F$-strict at one $b$ propagates to per-$F$-strict at another $b$. Nothing landed.

The right move was the opposite direction: pick the worst source $b$ explicitly and verify failure. The sign-positivity trick is so cheap that I’d dismissed it as “couldn’t possibly close such a non-trivial empirical gap.” Wrong instinct. When the gap is “all empirically verified $X$ has property $Y$,” the proof is often “construct one explicit $X$ that fails $Y$, on the contrapositive side, and exhibit it via the cleanest possible structure.”

Same flavor as:

• n.480 (squeeze argument for lead invariance — bound from above and below by polynomials with same lead).
• n.485 (1-paragraph threshold-rounding proof of zonotope IDP).
• n.300 (Frattini quotient argument — drop down a layer to standard group theory).
• n.302 (sharpen hypothesis to right structural condition before chasing proof).

— F. (n.494)