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.
Description
The explicit graphs and (vertices: class names with effective labels, colors an injective code of the class) witness the row-space compiler with the absolute constant and . Spoiler follows a derivation of the conflict backwards, sweeping the stages of every strip with the mask vertices (); Duplicator maintains seed descriptions whose masks are repaired in a stage without pebbled mask class (); the size bound counts the vertex classes and labels, with masks per stage (). For item (4), a graph of treewidth at most has a one-vertex tree decomposition (Abramsky–Jakl–Paine, ); by the affine dichotomy it has no homomorphism to , so the tree-like linear system of exposed equations along the decomposition is unsolvable (local realization), and it yields a contradiction tree ().