While this submission is a draft, it cannot be used by other submissions.

Proof of `The row-space compiler`

groundedproofs/Lax119563Proofs/RowSpace/Main.lean · lax-119563

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

The explicit graphs rsGraphI0rsGraph I 0 and rsGraphI1rsGraph I 1 (vertices: class names with effective labels, colors an injective code of the class) witness the row-space compiler with the absolute constant 2020 and Ck=(4k+1)(k+2)+6kCₖ = (4k + 1)(k + 2) + 6k. Spoiler follows a derivation of the conflict backwards, sweeping the k+2k + 2 stages of every strip with the mask vertices (spoilerWinsspoilerWins); Duplicator maintains seed descriptions whose masks are repaired in a stage without pebbled mask class (duplicatorSurvivesduplicatorSurvives); the size bound counts the vertex classes and labels, with 2rankBe2^{rank B_e} masks per stage (cardnameslecard_names_le). For item (4), a graph of treewidth at most kk has a one-vertex tree decomposition (Abramsky–Jakl–Paine, oneVertexForestoftreewidthoneVertexForest_of_treewidth); by the affine dichotomy it has no homomorphism to G1G₁, so the tree-like linear system of exposed equations along the decomposition is unsolvable (local realization), and it yields a contradiction tree (patterntreepattern_tree).