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

Implicit parity systems

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

definition

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

    Definition

    Fix k≥3k \geq 3 and ℓ≥1\ell \geq 1. The coordinates C=[k]×F2ℓ\mathfrak C = [k] \times \mathbb F_2^\ell consist of kk blocks, each a copy of F2ℓ\mathbb F_2^\ell, whose elements are the block coordinates. An address is a codeword with exactly one 11 per block whose block coordinates sum to zero; we represent it by the array a=(a1,…,ak)a = (a_1, \dots, a_k) of the block coordinates of its ones, subject to a1+⋯+ak=0a_1 + \dots + a_k = 0. Its support is supp⁡(a)={(i,ai):i∈[k]}\operatorname{supp}(a) = \{(i, a_i) : i \in [k]\}.

    A permutation π\pi of C\mathfrak C is block-induced if there are a permutation ff of [k][k] and δ1,…,δk∈F2ℓ\delta_1, \dots, \delta_k \in \mathbb F_2^\ell with ∑iδi=0\sum_i \delta_i = 0 such that π(i,b)=(f(i),b+δi)\pi(i, b) = (f(i), b + \delta_i). It maps an address aa to the address πa\pi a with supp⁡(πa)=π(supp⁡(a))\operatorname{supp}(\pi a) = \pi(\operatorname{supp}(a)), i.e., (πa)f(i)=ai+δi(\pi a)_{f(i)} = a_i + \delta_i.

    Let WW be a finite set of locations, each with a coordinate domain Cv⊆C\mathfrak C_v \subseteq \mathfrak C. A ternary equation schema e=(u,v,w,Ce,σ,τ,π)e = (u, v, w, \mathfrak C_e, \sigma, \tau, \pi) consists of three distinct locations, a coordinate domain Ce⊆C\mathfrak C_e \subseteq \mathfrak C, and block-induced permutations with σ(Ce)⊆Cu\sigma(\mathfrak C_e) \subseteq \mathfrak C_u, τ(Ce)⊆Cv\tau(\mathfrak C_e) \subseteq \mathfrak C_v and π(Ce)⊆Cw\pi(\mathfrak C_e) \subseteq \mathfrak C_w. For every allowed address aa, i.e., with supp⁡(a)⊆Ce\operatorname{supp}(a) \subseteq \mathfrak C_e, it gives the equation Xu,σa+Xv,τa+Xw,πa=0X_{u, \sigma a} + X_{v, \tau a} + X_{w, \pi a} = 0. A binary equation schema (u,v,Ce,σ,τ)(u, v, \mathfrak C_e, \sigma, \tau) analogously gives Xu,σa+Xv,τa=0X_{u, \sigma a} + X_{v, \tau a} = 0.

    An implicit parity system I=(W,C,(Cv)v∈W,E,ι)\mathcal I = (W, \mathfrak C, (\mathfrak C_v)_{v \in W}, \mathcal E, \iota) consists of locations WW with coordinate domains, a finite set E\mathcal E of binary or ternary equation schemas whose sets of locations pairwise intersect in at most one element, and an initialization ι ⁣:W→{0,1,⋆}\iota \colon W \to \{0, 1, \star\}. It defines a parity system: its variables are the Xv,aX_{v, a} for v∈Wv \in W and addresses aa with supp⁡(a)⊆Cv\operatorname{supp}(a) \subseteq \mathfrak C_v; its equations are those given by the schemas; and for every vv with ι(v)∈{0,1}\iota(v) \in \{0, 1\} it has the initial facts Xv,a=ι(v)X_{v, a} = \iota(v) for all these addresses aa. We write τ(I)\tau(\mathcal I) for the conflict round of this parity system.

    Concept map
    2 concepts; 4 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Mathlib.Data.Fintype.Pi
    2import Mathlib.Data.Fintype.Prod
    3import Mathlib.Data.ZMod.Basic
    4import Mathlib.Logic.Equiv.Fintype
    5import Lax119563.ParitySystems
    6
    7/-!
    8---
    9title: Implicit parity systems
    10type: definition
    11---
    12Fix k≥3k \geq 3 and ℓ≥1\ell \geq 1. The *coordinates* C=[k]×F2ℓ\mathfrak C = [k] \times \mathbb F_2^\ell
    13consist of kk *blocks*, each a copy of F2ℓ\mathbb F_2^\ell, whose elements are the *block
    14coordinates*. An *address* is a codeword with exactly one 11 per block whose block
    15coordinates sum to zero; we represent it by the array a=(a1,…,ak)a = (a_1, \dots, a_k) of the block
    16coordinates of its ones, subject to a1+⋯+ak=0a_1 + \dots + a_k = 0. Its *support* is
    17supp⁡(a)={(i,ai):i∈[k]}\operatorname{supp}(a) = \{(i, a_i) : i \in [k]\}.
    18
    19A permutation π\pi of C\mathfrak C is *block-induced* if there are a permutation
    20ff of [k][k] and δ1,…,δk∈F2ℓ\delta_1, \dots, \delta_k \in \mathbb F_2^\ell with
    21∑iδi=0\sum_i \delta_i = 0 such that π(i,b)=(f(i),b+δi)\pi(i, b) = (f(i), b + \delta_i). It maps an address aa to
    22the address πa\pi a with supp⁡(πa)=π(supp⁡(a))\operatorname{supp}(\pi a) = \pi(\operatorname{supp}(a)), i.e.,
    23(πa)f(i)=ai+δi(\pi a)_{f(i)} = a_i + \delta_i.
    24
    25Let WW be a finite set of *locations*, each with a *coordinate domain*
    26Cv⊆C\mathfrak C_v \subseteq \mathfrak C. A *ternary equation schema*
    27e=(u,v,w,Ce,σ,τ,π)e = (u, v, w, \mathfrak C_e, \sigma, \tau, \pi) consists of three distinct locations, a
    28coordinate domain Ce⊆C\mathfrak C_e \subseteq \mathfrak C, and block-induced permutations with
    29σ(Ce)⊆Cu\sigma(\mathfrak C_e) \subseteq \mathfrak C_u, τ(Ce)⊆Cv\tau(\mathfrak C_e) \subseteq \mathfrak C_v
    30and π(Ce)⊆Cw\pi(\mathfrak C_e) \subseteq \mathfrak C_w. For every *allowed* address aa, i.e., with
    31supp⁡(a)⊆Ce\operatorname{supp}(a) \subseteq \mathfrak C_e, it gives the equation
    32Xu,σa+Xv,τa+Xw,πa=0X_{u, \sigma a} + X_{v, \tau a} + X_{w, \pi a} = 0. A *binary equation schema*
    33(u,v,Ce,σ,τ)(u, v, \mathfrak C_e, \sigma, \tau) analogously gives Xu,σa+Xv,τa=0X_{u, \sigma a} + X_{v, \tau a} = 0.
    34
    35An *implicit parity system* I=(W,C,(Cv)v∈W,E,ι)\mathcal I = (W, \mathfrak C, (\mathfrak C_v)_{v \in W}, \mathcal E, \iota)
    36 consists of locations WW with coordinate domains, a finite set
    37E\mathcal E of binary or ternary equation schemas whose sets of locations pairwise intersect
    38in at most one element, and an *initialization* ι ⁣:W→{0,1,⋆}\iota \colon W \to \{0, 1, \star\}. It
    39defines a parity system: its variables are the Xv,aX_{v, a} for v∈Wv \in W and addresses aa with
    40supp⁡(a)⊆Cv\operatorname{supp}(a) \subseteq \mathfrak C_v; its equations are those given by the
    41schemas; and for every vv with ι(v)∈{0,1}\iota(v) \in \{0, 1\} it has the initial facts
    42Xv,a=ι(v)X_{v, a} = \iota(v) for all these addresses aa. We write τ(I)\tau(\mathcal I) for the conflict
    43round of this parity system.
    44
    45# Implementation notes
    46
    47The locations are W={0,…,w−1}W = \{0, \dots, w-1\}, the initialization value ⋆\star is `none`, and
    48the schemas are given as a list. The parity system has a variable Xv,aX_{v, a} for every
    49location vv and every array aa; those with aa not an address or with
    50supp⁡(a)⊈Cv\operatorname{supp}(a) \not\subseteq \mathfrak C_v occur in no equation and in no initial
    51fact, so they do not affect unit propagation.
    52-/
    53
    54open Lax119563.ParitySystems
    55
    56namespace Lax119563.ImplicitParitySystems
    57
    58/-- Block coordinates `𝔽₂^ℓ`. -/
    59abbrev BlockCoord (ℓ : ℕ) := Fin ℓ → ZMod 2
    60
    61/-- Coordinates `ℭ = [k] × 𝔽₂^ℓ`. -/
    62abbrev Coord (k ℓ : ℕ) := Fin k × BlockCoord ℓ
    63
    64variable {k ℓ w : ℕ}
    65
    66/-- An array `(a_1, …, a_k)` of block coordinates is an *address* if its entries sum to zero. -/
    67def 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`. -/
    71def 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`. -/
    75structure 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. -/
    83def 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`. -/
    87def 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}`. -/
    91inductive 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
    97namespace Schema
    98
    99/-- The coordinate domain `ℭ_e` of a schema. -/
    100def domain : Schema k ℓ w → Finset (Coord k ℓ)
    101 | binary _ _ D _ _ => D
    102 | ternary _ _ _ D _ _ _ => D
    103
    104/-- The set of locations of a schema. -/
    105def 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
    110into the coordinate domains of the respective locations. -/
    111def 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'}`,
    117written as pairs `(v, a')`. -/
    118def 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
    122end Schema
    123
    124/-- An *implicit parity system* with coordinates `[k] × 𝔽₂^ℓ`. -/
    125structure 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
    138namespace ImplicitParitySystem
    139
    140/-- The parity system defined by an implicit parity system. -/
    141def 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. -/
    163noncomputable def conflictRound (I : ImplicitParitySystem k ℓ) : ℕ∞ :=
    164 I.toParitySystem.conflictRound
    165
    166end ImplicitParitySystem
    167
    168end Lax119563.ImplicitParitySystems
    169

    Implementation notes

    The locations are W={0,…,w−1}W = \{0, \dots, w-1\}, the initialization value ⋆\star is nonenone, and the schemas are given as a list. The parity system has a variable Xv,aX_{v, a} for every location vv and every array aa; those with aa not an address or with supp⁡(a)⊈Cv\operatorname{supp}(a) \not\subseteq \mathfrak C_v 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.

    Loading discussion…