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

The matrix compiler

Lax119563.MatrixCompiler · concepts/Lax119563/MatrixCompiler.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 there are colored graphs G~0,G~1\widetilde G_0, \widetilde G_1, constructed from I\mathcal I, such that:

    1. If τ<∞\tau < \infty, then Spoiler wins the bijective pebble game on (G~0,G~1)(\widetilde G_0, \widetilde G_1) with k+1k + 1 pebbles in Ok(Λ(τ+1))O_k(\Lambda(\tau + 1)) rounds.
    2. Duplicator survives the bijective pebble game on (G~0,G~1)(\widetilde G_0, \widetilde G_1) with k+1k + 1 pebbles for τ−1\tau - 1 rounds, or indefinitely if τ=∞\tau = \infty.
    3. With an absolute constant, N~=∣V(G~0)∣+∣V(G~1)∣=O(S)\widetilde N = |V(\widetilde G_0)| + |V(\widetilde G_1)| = O(S), where S=∑v∈W∣Cv∣+(k+1)∑e∈Ennz⁡(Be)S = \sum_{v \in W} |\mathfrak C_v| + (k + 1) \sum_{e \in \mathcal E} \operatorname{nnz}(B_e), and the two graphs have at most 3N~3 \widetilde N edges. Their binary encoding has length O(Slog⁡(S+2))O(S \log (S + 2)); in particular, colors are written with O(log⁡(S+2))O(\log (S + 2)) bits.
    4. The binary encoding of the pair (G~0,G~1)(\widetilde G_0, \widetilde G_1) can be computed from the binary encoding of I\mathcal I by a deterministic multitape Turing machine in time O~(H+S)\widetilde O(H + S), where HH is the bit length of I\mathcal I and O~\widetilde O suppresses a fixed power of log⁡(H+S+2)\log(H + S + 2). The machine and all constants are absolute; in particular kk and ℓ\ell are part of the input.

    Here B∈F2(k−1+ℓ)×CB \in \mathbb F_2^{(k - 1 + \ell) \times \mathfrak C} is the check matrix of the code of codewords whose blocks have equal parity and whose block coordinates sum to zero: its rows are the k−1k - 1 block-parity checks comparing blocks 1,…,k−11, \dots, k - 1 with block kk, followed by the ℓ\ell checksum checks for the sum of the block coordinates. For a schema ee, BeB_e is obtained from BB by restricting to the columns in Ce\mathfrak C_e and deleting zero rows; mem_e is its number of rows and nnz⁡(Be)\operatorname{nnz}(B_e) its number of nonzero entries. Finally, Λ=1+max⁡({0}∪{me:e∈E})\Lambda = 1 + \max(\{0\} \cup \{m_e : e \in \mathcal E\}).

    Concept map
    10 concepts; 1 descendant hidden
    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.Data.Matrix.Basic
    2import Mathlib.Data.Nat.Log
    3import Lax119563.ColoredGraphs
    4import Lax119563.DeterministicTime
    5import Lax119563.ImplicitParitySystems
    6import Lax119563.ImplicitSystemEncodings
    7import Lax119563.PebbleGame
    8
    9/-!
    10---
    11title: The matrix compiler
    12type: theorem
    13---
    14Let 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)
    15 be an implicit parity system with coordinates
    16C=[k]×F2ℓ\mathfrak C = [k] \times \mathbb F_2^\ell and conflict round τ=τ(I)\tau = \tau(\mathcal I).
    17Then there are colored graphs G~0,G~1\widetilde G_0, \widetilde G_1, constructed from I\mathcal I, such
    18that:
    19
    201. If τ<∞\tau < \infty, then Spoiler wins the bijective pebble game on
    21 (G~0,G~1)(\widetilde G_0, \widetilde G_1) with k+1k + 1 pebbles in Ok(Λ(τ+1))O_k(\Lambda(\tau + 1)) rounds.
    222. Duplicator survives the bijective pebble game on (G~0,G~1)(\widetilde G_0, \widetilde G_1) with
    23 k+1k + 1 pebbles for τ−1\tau - 1 rounds, or indefinitely if τ=∞\tau = \infty.
    243. With an absolute constant, N~=∣V(G~0)∣+∣V(G~1)∣=O(S)\widetilde N = |V(\widetilde G_0)| + |V(\widetilde G_1)| = O(S),
    25 where S=∑v∈W∣Cv∣+(k+1)∑e∈Ennz⁡(Be)S = \sum_{v \in W} |\mathfrak C_v| + (k + 1) \sum_{e \in \mathcal E} \operatorname{nnz}(B_e)
    26, and the two graphs have at most 3N~3 \widetilde N edges. Their
    27 binary encoding has length O(Slog⁡(S+2))O(S \log (S + 2)); in particular, colors are written with
    28 O(log⁡(S+2))O(\log (S + 2)) bits.
    294. The binary encoding of the pair (G~0,G~1)(\widetilde G_0, \widetilde G_1) can be computed from the
    30 binary encoding of I\mathcal I by a deterministic multitape Turing machine in time
    31 O~(H+S)\widetilde O(H + S), where HH is the bit length of I\mathcal I and O~\widetilde O
    32 suppresses a fixed power of log⁡(H+S+2)\log(H + S + 2). The machine and all constants are absolute;
    33 in particular kk and ℓ\ell are part of the input.
    34
    35Here B∈F2(k−1+ℓ)×CB \in \mathbb F_2^{(k - 1 + \ell) \times \mathfrak C} is the check matrix of the code of
    36codewords whose blocks have equal parity and whose block coordinates sum to zero: its rows
    37are the k−1k - 1 block-parity checks comparing blocks 1,…,k−11, \dots, k - 1 with block kk,
    38followed by the ℓ\ell checksum checks for the sum of the block coordinates. For a schema ee,
    39BeB_e is obtained from BB by restricting to the columns in Ce\mathfrak C_e and deleting zero
    40rows; mem_e is its number of rows and nnz⁡(Be)\operatorname{nnz}(B_e) its number of nonzero entries.
    41Finally, Λ=1+max⁡({0}∪{me:e∈E})\Lambda = 1 + \max(\{0\} \cup \{m_e : e \in \mathcal E\}).
    42
    43# Implementation notes
    44
    45The paper states this theorem for the explicit graph construction of the matrix compiler,
    46together with its size bound and construction time (Lemma "Matrix size"). Here the
    47construction is an unspecified function `compile` from implicit parity systems to graph
    48pairs; its properties are the game clauses, the size bounds, and that a single deterministic
    49machine computes it within C(H+S)log⁡c(H+S+2)C (H + S) \log^c (H + S + 2) steps, where CC and cc are absolute.
    50Only the constant of the round bound may depend on kk.
    51
    52Since kk is part of the input of the machine, the statement serves both the quasi-linear
    53reduction for fixed kk and polynomial-time reductions in which kk grows with the input.
    54-/
    55
    56open Lax119563.ColoredGraphs Lax119563.PebbleGame Lax119563.ImplicitParitySystems
    57 Lax119563.ImplicitSystemEncodings Lax119563.BinaryEncodings Lax119563.DeterministicTime
    58open Lax489179.TuringMachine (Machine Deterministic)
    59
    60namespace Lax119563.MatrixCompiler
    61
    62variable {k ℓ : ℕ}
    63
    64/-- The check matrix `B`. Row `inl i` is the block-parity check comparing block `i` with the
    65last block; row `inr t` is the checksum check of bit `t` of the block coordinates. -/
    66def checkMatrix (k ℓ : ℕ) : Matrix (Fin (k - 1) ⊕ Fin ℓ) (Coord k ℓ) (ZMod 2) :=
    67 Matrix.of fun row c =>
    68 match row with
    69 | .inl i => if (c.1 : ℕ) = i ∨ (c.1 : ℕ) = k - 1 then 1 else 0
    70 | .inr t => c.2 t
    71
    72open Classical in
    73/-- The number `m_e` of rows of `B_e`: rows of `B` that are nonzero on `ℭ_e`. -/
    74noncomputable def numRows {w : ℕ} (e : Schema k ℓ w) : ℕ :=
    75 (Finset.univ.filter fun row => ∃ c ∈ e.domain, checkMatrix k ℓ row c ≠ 0).card
    76
    77open Classical in
    78/-- The number `nnz(B_e)` of nonzero entries of `B_e`. -/
    79noncomputable def nnz {w : ℕ} (e : Schema k ℓ w) : ℕ :=
    80 ((Finset.univ ×ˢ e.domain).filter fun x => checkMatrix k ℓ x.1 x.2 ≠ 0).card
    81
    82/-- `Λ = 1 + max ({0} ∪ {m_e : e ∈ 𝓔})`. -/
    83noncomputable def Λ (I : ImplicitParitySystem k ℓ) : ℕ :=
    84 1 + (I.schemas.map numRows).foldr max 0
    85
    86/-- The size parameter `S = ∑_v |ℭ_v| + (k+1) ∑_e nnz(B_e)`. -/
    87noncomputable def matrixSize (I : ImplicitParitySystem k ℓ) : ℕ :=
    88 ∑ v, (I.domain v).card + (k + 1) * (I.schemas.map nnz).sum
    89
    90/-- **The matrix compiler.** There is a construction `compile` of graph pairs from implicit
    91parity systems such that, for `k ≥ 3`, the bijective `(k+1)`-pebble game on the pair follows
    92unit propagation: Spoiler wins in `O_k(Λ(τ+1))` rounds if a conflict occurs in round `τ`, and
    93Duplicator survives `τ - 1` rounds. The graphs have `O(S)` vertices and at most three times
    94as many edges as vertices, and their encoding has length `O(S log (S + 2))`. A single deterministic machine computes the encoding of the pair
    95from the encoding of the system in time `O((H + S) log^c (H + S + 2))`. -/
    96axiom matrix_compiler :
    97 ∃ compile : ∀ {k ℓ : ℕ}, ImplicitParitySystem k ℓ → ColoredGraph × ColoredGraph,
    98 (∃ C : ℕ, ∀ k : ℕ, 3 ≤ k → ∃ Cₖ : ℕ, ∀ ℓ : ℕ, 1 ≤ ℓ →
    99 ∀ I : ImplicitParitySystem k ℓ,
    100 (∀ τ : ℕ, I.conflictRound = τ →
    101 SpoilerWinsWithin (k + 1) (Cₖ * Λ I * (τ + 1)) (compile I).1 (compile I).2) ∧
    102 (∀ r : ℕ, (r : ℕ∞) + 1 ≤ I.conflictRound →
    103 DuplicatorSurvives (k + 1) r (compile I).1 (compile I).2) ∧
    104 (compile I).1.n + (compile I).2.n ≤ C * matrixSize I ∧
    105 (compile I).1.numEdges + (compile I).2.numEdges ≤
    106 3 * ((compile I).1.n + (compile I).2.n) ∧
    107 (encodeGraphPair (compile I).1 (compile I).2).length ≤
    108 C * (matrixSize I + 1) * (Nat.log 2 (matrixSize I + 2) + 1)) ∧
    109 (∃ M : Machine, Deterministic M ∧ ∃ C c : ℕ, ∀ k : ℕ, 3 ≤ k → ∀ ℓ : ℕ, 1 ≤ ℓ →
    110 ∀ I : ImplicitParitySystem k ℓ,
    111 ComputesWithin M (encodeSystem I) (encodeGraphPair (compile I).1 (compile I).2)
    112 (C * (bitLength I + matrixSize I) *
    113 Nat.log 2 (bitLength I + matrixSize I + 2) ^ c))
    114
    115end Lax119563.MatrixCompiler
    116
    Show Proof

    Implementation notes

    The paper states this theorem for the explicit graph construction of the matrix compiler, together with its size bound and construction time (Lemma "Matrix size"). Here the construction is an unspecified function compilecompile from implicit parity systems to graph pairs; its properties are the game clauses, the size bounds, and that a single deterministic machine computes it within C(H+S)log⁡c(H+S+2)C (H + S) \log^c (H + S + 2) steps, where CC and cc are absolute. Only the constant of the round bound may depend on kk.

    Since kk is part of the input of the machine, the statement serves both the quasi-linear reduction for fixed kk and polynomial-time reductions in which kk grows with the input.

    Discussion

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

    Loading discussion…