Implicit parity systems
Lax119563.ImplicitParitySystems · concepts/Lax119563/ImplicitParitySystems.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
Fix and . The coordinates consist of blocks, each a copy of , whose elements are the block coordinates. An address is a codeword with exactly one per block whose block coordinates sum to zero; we represent it by the array of the block coordinates of its ones, subject to . Its support is .
A permutation of is block-induced if there are a permutation of and with such that . It maps an address to the address with , i.e., .
Let be a finite set of locations, each with a coordinate domain . A ternary equation schema consists of three distinct locations, a coordinate domain , and block-induced permutations with , and . For every allowed address , i.e., with , it gives the equation . A binary equation schema analogously gives .
An implicit parity system consists of locations with coordinate domains, a finite set of binary or ternary equation schemas whose sets of locations pairwise intersect in at most one element, and an initialization . It defines a parity system: its variables are the for and addresses with ; its equations are those given by the schemas; and for every with it has the initial facts for all these addresses . We write for the conflict round of this parity system.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Data.Fintype.Pi |
| 2 | import Mathlib.Data.Fintype.Prod |
| 3 | import Mathlib.Data.ZMod.Basic |
| 4 | import Mathlib.Logic.Equiv.Fintype |
| 5 | import Lax119563.ParitySystems |
| 6 | |
| 7 | /-! |
| 8 | --- |
| 9 | title: Implicit parity systems |
| 10 | type: definition |
| 11 | --- |
| 12 | Fix and . The *coordinates* |
| 13 | consist of *blocks*, each a copy of , whose elements are the *block |
| 14 | coordinates*. An *address* is a codeword with exactly one per block whose block |
| 15 | coordinates sum to zero; we represent it by the array of the block |
| 16 | coordinates of its ones, subject to . Its *support* is |
| 17 | . |
| 18 | |
| 19 | A permutation of is *block-induced* if there are a permutation |
| 20 | of and with |
| 21 | such that . It maps an address to |
| 22 | the address with , i.e., |
| 23 | . |
| 24 | |
| 25 | Let be a finite set of *locations*, each with a *coordinate domain* |
| 26 | . A *ternary equation schema* |
| 27 | consists of three distinct locations, a |
| 28 | coordinate domain , and block-induced permutations with |
| 29 | , |
| 30 | and . For every *allowed* address , i.e., with |
| 31 | , it gives the equation |
| 32 | . A *binary equation schema* |
| 33 | analogously gives . |
| 34 | |
| 35 | An *implicit parity system* |
| 36 | consists of locations with coordinate domains, a finite set |
| 37 | of binary or ternary equation schemas whose sets of locations pairwise intersect |
| 38 | in at most one element, and an *initialization* . It |
| 39 | defines a parity system: its variables are the for and addresses with |
| 40 | ; its equations are those given by the |
| 41 | schemas; and for every with it has the initial facts |
| 42 | for all these addresses . We write for the conflict |
| 43 | round of this parity system. |
| 44 | |
| 45 | # Implementation notes |
| 46 | |
| 47 | The locations are , the initialization value is `none`, and |
| 48 | the schemas are given as a list. The parity system has a variable for every |
| 49 | location and every array ; those with not an address or with |
| 50 | occur in no equation and in no initial |
| 51 | fact, so they do not affect unit propagation. |
| 52 | -/ |
| 53 | |
| 54 | open Lax119563.ParitySystems |
| 55 | |
| 56 | namespace Lax119563.ImplicitParitySystems |
| 57 | |
| 58 | /-- Block coordinates `𝔽₂^ℓ`. -/ |
| 59 | abbrev BlockCoord (ℓ : ℕ) := Fin ℓ → ZMod 2 |
| 60 | |
| 61 | /-- Coordinates `ℭ = [k] × 𝔽₂^ℓ`. -/ |
| 62 | abbrev Coord (k ℓ : ℕ) := Fin k × BlockCoord ℓ |
| 63 | |
| 64 | variable {k ℓ w : ℕ} |
| 65 | |
| 66 | /-- An array `(a_1, …, a_k)` of block coordinates is an *address* if its entries sum to zero. -/ |
| 67 | def IsAddress (a : Fin k → BlockCoord ℓ) : Prop := |
| 68 | ∑ i, a i = 0 |
| 69 | |
| 70 | /-- The support `{(i, a_i) : i ∈ [k]}` of the address with array `a`. -/ |
| 71 | def supp (a : Fin k → BlockCoord ℓ) : Finset (Coord k ℓ) := |
| 72 | Finset.univ.image fun i => (i, a i) |
| 73 | |
| 74 | /-- A *block-induced* permutation `(i, b) ↦ (f(i), b + δ_i)` of `ℭ`, where `∑ δ_i = 0`. -/ |
| 75 | structure BlockPerm (k ℓ : ℕ) where |
| 76 | /-- The permutation `f` of the blocks. -/ |
| 77 | perm : Equiv.Perm (Fin k) |
| 78 | /-- The shifts `δ_i`. -/ |
| 79 | shift : Fin k → BlockCoord ℓ |
| 80 | sum_shift : ∑ i, shift i = 0 |
| 81 | |
| 82 | /-- The block-induced permutation acting on a coordinate. -/ |
| 83 | def BlockPerm.apply (π : BlockPerm k ℓ) (c : Coord k ℓ) : Coord k ℓ := |
| 84 | (π.perm c.1, c.2 + π.shift c.1) |
| 85 | |
| 86 | /-- The block-induced permutation acting on an address: `(π a)_{f(i)} = a_i + δ_i`. -/ |
| 87 | def BlockPerm.act (π : BlockPerm k ℓ) (a : Fin k → BlockCoord ℓ) : Fin k → BlockCoord ℓ := |
| 88 | fun j => a (π.perm.symm j) + π.shift (π.perm.symm j) |
| 89 | |
| 90 | /-- A binary or ternary *equation schema* over the locations `{0, …, w-1}`. -/ |
| 91 | inductive Schema (k ℓ w : ℕ) |
| 92 | /-- The binary schema `(u, v, ℭ_e, σ, τ)`. -/ |
| 93 | | binary (u v : Fin w) (domain : Finset (Coord k ℓ)) (σ τ : BlockPerm k ℓ) |
| 94 | /-- The ternary schema `(u, v, w, ℭ_e, σ, τ, π)`. -/ |
| 95 | | ternary (u v w' : Fin w) (domain : Finset (Coord k ℓ)) (σ τ π : BlockPerm k ℓ) |
| 96 | |
| 97 | namespace Schema |
| 98 | |
| 99 | /-- The coordinate domain `ℭ_e` of a schema. -/ |
| 100 | def domain : Schema k ℓ w → Finset (Coord k ℓ) |
| 101 | | binary _ _ D _ _ => D |
| 102 | | ternary _ _ _ D _ _ _ => D |
| 103 | |
| 104 | /-- The set of locations of a schema. -/ |
| 105 | def locations : Schema k ℓ w → Finset (Fin w) |
| 106 | | binary u v _ _ _ => {u, v} |
| 107 | | ternary u v w' _ _ _ _ => {u, v, w'} |
| 108 | |
| 109 | /-- The locations of a schema are distinct, and its permutations map its coordinate domain |
| 110 | into the coordinate domains of the respective locations. -/ |
| 111 | def WellFormed (dom : Fin w → Finset (Coord k ℓ)) : Schema k ℓ w → Prop |
| 112 | | binary u v D σ τ => u ≠ v ∧ D.image σ.apply ⊆ dom u ∧ D.image τ.apply ⊆ dom v |
| 113 | | ternary u v w' D σ τ π => u ≠ v ∧ u ≠ w' ∧ v ≠ w' ∧ |
| 114 | D.image σ.apply ⊆ dom u ∧ D.image τ.apply ⊆ dom v ∧ D.image π.apply ⊆ dom w' |
| 115 | |
| 116 | /-- The equation given by a schema for the address `a`, as its set of variables `X_{v, a'}`, |
| 117 | written as pairs `(v, a')`. -/ |
| 118 | def equation : Schema k ℓ w → (Fin k → BlockCoord ℓ) → Finset (Fin w × (Fin k → BlockCoord ℓ)) |
| 119 | | binary u v _ σ τ, a => {(u, σ.act a), (v, τ.act a)} |
| 120 | | ternary u v w' _ σ τ π, a => {(u, σ.act a), (v, τ.act a), (w', π.act a)} |
| 121 | |
| 122 | end Schema |
| 123 | |
| 124 | /-- An *implicit parity system* with coordinates `[k] × 𝔽₂^ℓ`. -/ |
| 125 | structure ImplicitParitySystem (k ℓ : ℕ) where |
| 126 | /-- The number of locations; the locations are `0, …, numLocations - 1`. -/ |
| 127 | numLocations : ℕ |
| 128 | /-- The coordinate domain `ℭ_v` of each location. -/ |
| 129 | domain : Fin numLocations → Finset (Coord k ℓ) |
| 130 | /-- The equation schemas. -/ |
| 131 | schemas : List (Schema k ℓ numLocations) |
| 132 | /-- The initialization `ι`; `none` stands for `⋆`. -/ |
| 133 | init : Fin numLocations → Option (ZMod 2) |
| 134 | schema_wellFormed : ∀ e ∈ schemas, e.WellFormed domain |
| 135 | /-- The sets of locations of distinct schemas intersect in at most one location. -/ |
| 136 | schemas_meet : schemas.Pairwise fun e e' => (e.locations ∩ e'.locations).card ≤ 1 |
| 137 | |
| 138 | namespace ImplicitParitySystem |
| 139 | |
| 140 | /-- The parity system defined by an implicit parity system. -/ |
| 141 | def toParitySystem (I : ImplicitParitySystem k ℓ) : |
| 142 | ParitySystem (Fin I.numLocations × (Fin k → BlockCoord ℓ)) where |
| 143 | equations := {h | ∃ e ∈ I.schemas, ∃ a, IsAddress a ∧ supp a ⊆ e.domain ∧ h = e.equation a} |
| 144 | card_equation := by |
| 145 | rintro h ⟨e, he, a, -, -, rfl⟩ |
| 146 | have hwf := I.schema_wellFormed e he |
| 147 | cases e with |
| 148 | | binary u v D σ τ => |
| 149 | left |
| 150 | exact Finset.card_pair fun h => hwf.1 (congrArg Prod.fst h) |
| 151 | | ternary u v w' D σ τ π => |
| 152 | right |
| 153 | obtain ⟨huv, huw, hvw, -⟩ := hwf |
| 154 | have h₁ : (u, σ.act a) ∉ ({(v, τ.act a), (w', π.act a)} : Finset _) := by |
| 155 | simp only [Finset.mem_insert, Finset.mem_singleton, not_or] |
| 156 | exact ⟨fun h => huv (congrArg Prod.fst h), fun h => huw (congrArg Prod.fst h)⟩ |
| 157 | rw [Schema.equation, Finset.card_insert_of_notMem h₁, |
| 158 | Finset.card_pair fun h => hvw (congrArg Prod.fst h)] |
| 159 | initial := {f | ∃ b, I.init f.1.1 = some b ∧ f.2 = b ∧ |
| 160 | IsAddress f.1.2 ∧ supp f.1.2 ⊆ I.domain f.1.1} |
| 161 | |
| 162 | /-- The conflict round `τ(I)` of an implicit parity system. -/ |
| 163 | noncomputable def conflictRound (I : ImplicitParitySystem k ℓ) : ℕ∞ := |
| 164 | I.toParitySystem.conflictRound |
| 165 | |
| 166 | end ImplicitParitySystem |
| 167 | |
| 168 | end Lax119563.ImplicitParitySystems |
| 169 |
Implementation notes
The locations are , the initialization value is , and the schemas are given as a list. The parity system has a variable for every location and every array ; those with not an address or with occur in no equation and in no initial fact, so they do not affect unit propagation.
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments