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

The row-space compiler

Lax119563.RowSpaceCompiler · concepts/Lax119563/RowSpaceCompiler.lean · lax-119563

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    Let k≥3k \geq 3 and ℓ≥1\ell \geq 1, and let I=(W,C,(Cv)v∈W,E,ι)\mathcal I = (W, \mathfrak C, (\mathfrak C_v)_{v \in W}, \mathcal E, \iota) be an implicit parity system with coordinates C=[k]×F2ℓ\mathfrak C = [k] \times \mathbb F_2^\ell and conflict round τ=τ(I)\tau = \tau(\mathcal I). Then the row-space construction yields colored graphs G0,G1G_0, G_1 such that:

    1. If τ<∞\tau < \infty, then Spoiler wins the bijective pebble game on (G0,G1)(G_0, G_1) with k+1k + 1 pebbles in Ok(τ+1)O_k(\tau + 1) rounds.
    2. Duplicator survives the bijective pebble game on (G0,G1)(G_0, G_1) with k+1k + 1 pebbles for τ−1\tau - 1 rounds, or indefinitely if τ=∞\tau = \infty.
    3. With an absolute constant, ∣V(G0)∣+∣V(G1)∣=O(S)|V(G_0)| + |V(G_1)| = O(S), where S=∑v∈W∣Cv∣+(k+1)∑e∈E(∣Ce∣+2rank⁡Be)S = \sum_{v \in W} |\mathfrak C_v| + (k + 1) \sum_{e \in \mathcal E} \bigl(|\mathfrak C_e| + 2^{\operatorname{rank} B_e}\bigr).
    4. If a colored graph FF with tw⁡(F)≤k\operatorname{tw}(F) \leq k satisfies hom⁡(F,G0)≠hom⁡(F,G1)\hom(F, G_0) \neq \hom(F, G_1), then the parity system of I\mathcal I has a contradiction tree with at most 5∣V(F)∣+15 |V(F)| + 1 nodes.

    Here BeB_e is the check matrix BB restricted to the columns in Ce\mathfrak C_e, as for the matrix compiler; deleting its zero rows does not change its rank.

    Concept map
    14 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Mathlib.LinearAlgebra.Matrix.Rank
    2import Lax119563.ColoredHomomorphisms
    3import Lax119563.ContradictionTrees
    4import Lax119563.MatrixCompiler
    5
    6/-!
    7---
    8title: The row-space compiler
    9type: theorem
    10---
    11Let k≥3k \geq 3 and ℓ≥1\ell \geq 1, and let I=(W,C,(Cv)v∈W,E,ι)\mathcal I = (W, \mathfrak C, (\mathfrak C_v)_{v \in W}, \mathcal E, \iota)
    12 be an implicit parity system with coordinates
    13C=[k]×F2ℓ\mathfrak C = [k] \times \mathbb F_2^\ell and conflict round τ=τ(I)\tau = \tau(\mathcal I).
    14Then the row-space construction yields colored graphs G0,G1G_0, G_1 such that:
    15
    161. If τ<∞\tau < \infty, then Spoiler wins the bijective pebble game on (G0,G1)(G_0, G_1) with
    17 k+1k + 1 pebbles in Ok(τ+1)O_k(\tau + 1) rounds.
    182. Duplicator survives the bijective pebble game on (G0,G1)(G_0, G_1) with k+1k + 1 pebbles for
    19 τ−1\tau - 1 rounds, or indefinitely if τ=∞\tau = \infty.
    203. With an absolute constant, ∣V(G0)∣+∣V(G1)∣=O(S)|V(G_0)| + |V(G_1)| = O(S), where
    21 S=∑v∈W∣Cv∣+(k+1)∑e∈E(∣Ce∣+2rank⁡Be)S = \sum_{v \in W} |\mathfrak C_v| + (k + 1) \sum_{e \in \mathcal E} \bigl(|\mathfrak C_e| + 2^{\operatorname{rank} B_e}\bigr)
    22.
    234. If a colored graph FF with tw⁡(F)≤k\operatorname{tw}(F) \leq k satisfies
    24 hom⁡(F,G0)≠hom⁡(F,G1)\hom(F, G_0) \neq \hom(F, G_1), then the parity system of I\mathcal I has a
    25 contradiction tree with at most 5∣V(F)∣+15 |V(F)| + 1 nodes.
    26
    27Here BeB_e is the check matrix BB restricted to the columns in Ce\mathfrak C_e, as for the
    28matrix compiler; deleting its zero rows does not change its rank.
    29
    30# Implementation notes
    31
    32The paper states items 1–3 for the explicit row-space construction, and item 4 as a separate
    33theorem about the same construction, for graphs FF with a tree decomposition of width at
    34most kk in which adjacent bags differ in one vertex; by a theorem of Abramsky, Jakl and
    35Paine, every graph of treewidth at most kk has such a decomposition. Here the graphs are
    36asserted to exist. The constant of the size bound is absolute, while the constant of the round
    37bound may depend on kk. Unlike `Lax119563.MatrixCompiler`, which states a single construction
    38`compile` because it also asserts a machine computing it, this statement only asserts that
    39suitable graphs exist for each system.
    40-/
    41
    42open Lax119563.ColoredGraphs Lax119563.PebbleGame Lax119563.ImplicitParitySystems
    43 Lax119563.MatrixCompiler Lax119563.ColoredHomomorphisms Lax119563.ContradictionTrees
    44
    45namespace Lax119563.RowSpaceCompiler
    46
    47variable {k ℓ : ℕ}
    48
    49/-- The rank of `B_e`, the check matrix restricted to the coordinate domain of `e`. -/
    50noncomputable 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
    54construction. -/
    55noncomputable 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
    59pair of colored graphs on which the bijective `(k+1)`-pebble game follows unit propagation:
    60Spoiler 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
    62from a graph of treewidth at most `k` yields a contradiction tree of comparable size. -/
    63axiom 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
    71end Lax119563.RowSpaceCompiler
    72
    Show Proof

    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 FF with a tree decomposition of width at most kk in which adjacent bags differ in one vertex; by a theorem of Abramsky, Jakl and Paine, every graph of treewidth at most kk 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 kk. Unlike Lax119563.MatrixCompilerLax119563.MatrixCompiler, which states a single construction compilecompile because it also asserts a machine computing it, this statement only asserts that suitable graphs exist for each system.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…