The row-space compiler
Lax119563.RowSpaceCompiler · concepts/Lax119563/RowSpaceCompiler.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Let and , and let be an implicit parity system with coordinates and conflict round . Then the row-space construction yields colored graphs such that:
- If , then Spoiler wins the bijective pebble game on with pebbles in rounds.
- Duplicator survives the bijective pebble game on with pebbles for rounds, or indefinitely if .
- With an absolute constant, , where .
- If a colored graph with satisfies , then the parity system of has a contradiction tree with at most nodes.
Here is the check matrix restricted to the columns in , as for the matrix compiler; deleting its zero rows does not change its rank.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.LinearAlgebra.Matrix.Rank |
| 2 | import Lax119563.ColoredHomomorphisms |
| 3 | import Lax119563.ContradictionTrees |
| 4 | import Lax119563.MatrixCompiler |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: The row-space compiler |
| 9 | type: theorem |
| 10 | --- |
| 11 | Let and , and let |
| 12 | be an implicit parity system with coordinates |
| 13 | and conflict round . |
| 14 | Then the row-space construction yields colored graphs such that: |
| 15 | |
| 16 | 1. If , then Spoiler wins the bijective pebble game on with |
| 17 | pebbles in rounds. |
| 18 | 2. Duplicator survives the bijective pebble game on with pebbles for |
| 19 | rounds, or indefinitely if . |
| 20 | 3. With an absolute constant, , where |
| 21 | |
| 22 | . |
| 23 | 4. If a colored graph with satisfies |
| 24 | , then the parity system of has a |
| 25 | contradiction tree with at most nodes. |
| 26 | |
| 27 | Here is the check matrix restricted to the columns in , as for the |
| 28 | matrix compiler; deleting its zero rows does not change its rank. |
| 29 | |
| 30 | # Implementation notes |
| 31 | |
| 32 | The paper states items 1–3 for the explicit row-space construction, and item 4 as a separate |
| 33 | theorem about the same construction, for graphs with a tree decomposition of width at |
| 34 | most in which adjacent bags differ in one vertex; by a theorem of Abramsky, Jakl and |
| 35 | Paine, every graph of treewidth at most has such a decomposition. Here the graphs are |
| 36 | asserted to exist. The constant of the size bound is absolute, while the constant of the round |
| 37 | bound may depend on . Unlike `Lax119563.MatrixCompiler`, which states a single construction |
| 38 | `compile` because it also asserts a machine computing it, this statement only asserts that |
| 39 | suitable graphs exist for each system. |
| 40 | -/ |
| 41 | |
| 42 | open Lax119563.ColoredGraphs Lax119563.PebbleGame Lax119563.ImplicitParitySystems |
| 43 | Lax119563.MatrixCompiler Lax119563.ColoredHomomorphisms Lax119563.ContradictionTrees |
| 44 | |
| 45 | namespace Lax119563.RowSpaceCompiler |
| 46 | |
| 47 | variable {k ℓ : ℕ} |
| 48 | |
| 49 | /-- The rank of `B_e`, the check matrix restricted to the coordinate domain of `e`. -/ |
| 50 | noncomputable def rowRank {w : ℕ} (e : Schema k ℓ w) : ℕ := |
| 51 | (Matrix.of fun row (c : e.domain) => checkMatrix k ℓ row c).rank |
| 52 | |
| 53 | /-- The size parameter `∑_v |ℭ_v| + (k+1) ∑_e (|ℭ_e| + 2^{rank B_e})` of the row-space |
| 54 | construction. -/ |
| 55 | noncomputable def rowSpaceSize (I : ImplicitParitySystem k ℓ) : ℕ := |
| 56 | ∑ v, (I.domain v).card + (k + 1) * (I.schemas.map fun e => e.domain.card + 2 ^ rowRank e).sum |
| 57 | |
| 58 | /-- **The row-space compiler.** Every implicit parity system with `k ≥ 3` blocks compiles to a |
| 59 | pair of colored graphs on which the bijective `(k+1)`-pebble game follows unit propagation: |
| 60 | Spoiler wins in `O_k(τ+1)` rounds if a conflict occurs in round `τ`, and Duplicator survives |
| 61 | `τ - 1` rounds. The graphs have `O(S)` vertices, and every distinguishing homomorphism count |
| 62 | from a graph of treewidth at most `k` yields a contradiction tree of comparable size. -/ |
| 63 | axiom rowspace_compiler : ∃ C : ℕ, ∀ k : ℕ, 3 ≤ k → ∃ Cₖ : ℕ, ∀ ℓ : ℕ, 1 ≤ ℓ → |
| 64 | ∀ I : ImplicitParitySystem k ℓ, ∃ G₀ G₁ : ColoredGraph, |
| 65 | (∀ τ : ℕ, I.conflictRound = τ → SpoilerWinsWithin (k + 1) (Cₖ * (τ + 1)) G₀ G₁) ∧ |
| 66 | (∀ r : ℕ, (r : ℕ∞) + 1 ≤ I.conflictRound → DuplicatorSurvives (k + 1) r G₀ G₁) ∧ |
| 67 | G₀.n + G₁.n ≤ C * rowSpaceSize I ∧ |
| 68 | (∀ F : ColoredGraph, TreewidthAtMost F k → hom F G₀ ≠ hom F G₁ → |
| 69 | HasContradictionWithin I.toParitySystem (5 * F.n + 1)) |
| 70 | |
| 71 | end Lax119563.RowSpaceCompiler |
| 72 |
Implementation notes
The paper states items 1–3 for the explicit row-space construction, and item 4 as a separate theorem about the same construction, for graphs with a tree decomposition of width at most in which adjacent bags differ in one vertex; by a theorem of Abramsky, Jakl and Paine, every graph of treewidth at most has such a decomposition. Here the graphs are asserted to exist. The constant of the size bound is absolute, while the constant of the round bound may depend on . Unlike , which states a single construction because it also asserts a machine computing it, this statement only asserts that suitable graphs exist for each system.
Used by
none
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments