Lemma 29 — minimal-span reduction
ProvedSpaceReset.Hardness.lemma_29coding-theoryp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1trellis
Let have full row rank.
- A minimal-span basis of its row space can be computed from in polynomial time by binary row operations, i.e. as for an invertible .
- For every minimal-span basis with row spans and every cut , the span of the first columns of is the coordinate subspace of supported on the rows with , and the span of the last columns is the coordinate subspace supported on the rows with .
- Consequently, for the numerator of (12) for equals
This turns the rank invariants and into counts of row spans, the starting point of the allocation lemma and of the graph-layout correspondence.
Differences from the source:
- reading: computable by binary row operations in polynomial time → a polynomial-time map from the code of G to the code of E·G with E invertible over F2 and E·G a minimal-span basis; reason: row operations are exactly left multiplication by an invertible matrix; the output is the basis itself
- encoding: polynomial-time computation on explicitly represented matrices, graphs, budgets and circuits → PvsNP.PolyTimeComputable on binary strings, objects written with the fixed self-delimiting codes encNats (matrix entries row by row, binary numbers, explicit gate lists); reason: a standard polynomial-size binary presentation; any two reasonable codings are polynomially inter-convertible
Preamble
import Mathlib import Definitions.Def_PvsNP import Definitions.Def_SpaceReset_Hardness_Trellis import Definitions.Def_SpaceReset_Hardness_Coding set_option autoImplicit false
Formal statement
namespace SpaceReset.Hardness
/-- Lemma 29 (Minimal-span reduction), App. D.1, p. 41. -/
theorem lemma_29 :
(∃ f : PvsNP.Str → PvsNP.Str, PvsNP.PolyTimeComputable f ∧
∀ (k n : ℕ) (G : Matrix (Fin k) (Fin n) F2), FullRowRank G →
∃ E : Matrix (Fin k) (Fin k) F2, IsUnit E ∧ IsMinimalSpanBasis G (E * G) ∧
f (encNats (specNats G)) = encNats (specNats (E * G))) ∧
∀ (k n : ℕ) (G B : Matrix (Fin k) (Fin n) F2), FullRowRank G → IsMinimalSpanBasis G B →
(∀ u : ℕ, u ≤ n →
((prefixSpan B u : Set (Fin k → F2)) = {y | ∀ i, u < rowStart (B i) → y i = 0}) ∧
((suffixSpan B u : Set (Fin k → F2)) = {y | ∀ i, rowEnd (B i) ≤ u → y i = 0})) ∧
∀ u v : ℕ, u ≤ v → v ≤ n → windowDim G u v = spanWindowCount B u v := by sorry
end SpaceReset.Hardness
Source
Rinka Miura, STOC 2027 submission #1715 (October 2026), Lemma 29, App. D.1, p. 41 (eq. (27))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.