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

Parity systems and unit propagation

Lax119563.ParitySystems · concepts/Lax119563/ParitySystems.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

    A parity system P=(V,H,K0)\mathcal P = (V, \mathcal H, K_0) consists of a set VV of variables, each taking values in F2\mathbb F_2, a set H\mathcal H of homogeneous linear equations, and a set K0⊆V×F2K_0 \subseteq V \times \mathbb F_2 of initial facts. Every equation involves two or three distinct variables; formally, H⊆(V2)∪(V3)\mathcal H \subseteq \binom{V}{2} \cup \binom{V}{3}, where an equation hh states ∑X∈hX=0\sum_{X \in h} X = 0.

    Unit propagation infers facts of the form X=bX = b only. For an equation h ⁣:X+Y1+⋯+Ym=0h \colon X + Y_1 + \dots + Y_m = 0 with m∈{1,2}m \in \{1, 2\}, the rule infers X=b1+⋯+bmX = b_1 + \dots + b_m from Y1=b1,…,Ym=bmY_1 = b_1, \dots, Y_m = b_m. The facts KrK_r known after round rr are given by

    Kr+1=Kr∪{(X,b1+⋯+bm)∣{X,Y1,…,Ym}∈H, (Y1,b1),…,(Ym,bm)∈Kr}.K_{r+1} = K_r \cup \bigl\{(X, b_1 + \dots + b_m) \bigm| \{X, Y_1, \dots, Y_m\} \in \mathcal H,\ (Y_1, b_1), \dots, (Y_m, b_m) \in K_r\bigr\}.

    A conflict occurs when both X=0X = 0 and X=1X = 1 have been inferred for some variable XX. The conflict round τ(P)∈N∪{∞}\tau(\mathcal P) \in \mathbb N \cup \{\infty\} is the first round rr such that KrK_r contains a conflict, or ∞\infty if no conflict occurs.

    Concept map
    1 concept; 6 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Mathlib.Algebra.BigOperators.Group.Finset.Basic
    2import Mathlib.Data.ENat.Lattice
    3import Mathlib.Data.ZMod.Defs
    4
    5/-!
    6---
    7title: Parity systems and unit propagation
    8type: definition
    9---
    10A *parity system* P=(V,H,K0)\mathcal P = (V, \mathcal H, K_0) consists of a set VV of variables, each
    11taking values in F2\mathbb F_2, a set H\mathcal H of homogeneous linear equations, and a set
    12K0⊆V×F2K_0 \subseteq V \times \mathbb F_2 of *initial facts*. Every equation involves two or three
    13distinct variables; formally, H⊆(V2)∪(V3)\mathcal H \subseteq \binom{V}{2} \cup \binom{V}{3}, where an
    14equation hh states ∑X∈hX=0\sum_{X \in h} X = 0.
    15
    16*Unit propagation* infers facts of the form X=bX = b only. For an equation
    17h ⁣:X+Y1+⋯+Ym=0h \colon X + Y_1 + \dots + Y_m = 0 with m∈{1,2}m \in \{1, 2\}, the rule infers
    18X=b1+⋯+bmX = b_1 + \dots + b_m from Y1=b1,…,Ym=bmY_1 = b_1, \dots, Y_m = b_m. The facts KrK_r known after
    19round rr are given by
    20Kr+1=Kr∪{(X,b1+⋯+bm)∣{X,Y1,…,Ym}∈H, (Y1,b1),…,(Ym,bm)∈Kr}.K_{r+1} = K_r \cup \bigl\{(X, b_1 + \dots + b_m) \bigm| \{X, Y_1, \dots, Y_m\} \in \mathcal H,\ (Y_1, b_1), \dots, (Y_m, b_m) \in K_r\bigr\}.
    21
    22
    23A *conflict* occurs when both X=0X = 0 and X=1X = 1 have been inferred for some variable XX.
    24The *conflict round* τ(P)∈N∪{∞}\tau(\mathcal P) \in \mathbb N \cup \{\infty\} is the first round rr
    25such that KrK_r contains a conflict, or ∞\infty if no conflict occurs.
    26-/
    27
    28namespace Lax119563.ParitySystems
    29
    30/-- A *parity system* with variables of type `V`: homogeneous equations over `𝔽₂` in two or
    31three distinct variables, each given by its set of variables, and initial facts. -/
    32structure ParitySystem (V : Type*) where
    33 /-- The equations; `h` stands for `∑_{X ∈ h} X = 0`. -/
    34 equations : Set (Finset V)
    35 /-- Every equation involves two or three variables. -/
    36 card_equation : ∀ h ∈ equations, h.card = 2 ∨ h.card = 3
    37 /-- The initial facts `K₀`. -/
    38 initial : Set (V × ZMod 2)
    39
    40namespace ParitySystem
    41
    42variable {V : Type*} [DecidableEq V]
    43
    44/-- The set `K_r` of facts known after round `r` of unit propagation. In round `r + 1`, an
    45equation `h` and a variable `X ∈ h` infer `X = ∑_{Y ∈ h \ {X}} b_Y` from known facts
    46`Y = b_Y` for all other variables `Y ∈ h`. -/
    47def known (P : ParitySystem V) : ℕ → Set (V × ZMod 2)
    48 | 0 => P.initial
    49 | r + 1 => P.known r ∪
    50 {f | ∃ h ∈ P.equations, f.1 ∈ h ∧ ∃ b : V → ZMod 2,
    51 (∀ Y ∈ h, Y ≠ f.1 → (Y, b Y) ∈ P.known r) ∧ f.2 = ∑ Y ∈ h.erase f.1, b Y}
    52
    53/-- `K_r` contains a conflict. -/
    54def HasConflict (P : ParitySystem V) (r : ℕ) : Prop :=
    55 ∃ X, (X, 0) ∈ P.known r ∧ (X, 1) ∈ P.known r
    56
    57/-- The conflict round `τ(P)`: the first round with a conflict, or `⊤ = ∞` if none occurs. -/
    58noncomputable def conflictRound (P : ParitySystem V) : ℕ∞ :=
    59 ⨅ (r : ℕ) (_ : P.HasConflict r), (r : ℕ∞)
    60
    61end ParitySystem
    62
    63end Lax119563.ParitySystems
    64

    Discussion

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

    Loading discussion…