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

Binary encodings of implicit parity systems

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

    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) with coordinates C=[k]×F2ℓ\mathfrak C = [k] \times \mathbb F_2^\ell is given to a Turing machine explicitly, as a list of natural numbers encoded as in the binary encodings of graph pairs.

    • A block coordinate b∈F2ℓb \in \mathbb F_2^\ell is written with fixed width, as its ℓ\ell bits b0,…,bℓ−1b_0, \dots, b_{\ell - 1}, and a coordinate (i,b)(i, b) as i,b0,…,bℓ−1i, b_0, \dots, b_{\ell - 1}. Thus every coordinate and every shift listed in the input costs Ω(ℓ)\Omega(\ell) bits.
    • A coordinate domain D⊆CD \subseteq \mathfrak C is described by ∣D∣|D| followed by its coordinates, ordered by the numbers i⋅2ℓ+∑t<ℓbt2ti \cdot 2^\ell + \sum_{t < \ell} b_t 2^t.
    • A block-induced permutation π(i,b)=(f(i),b+δi)\pi(i, b) = (f(i), b + \delta_i) is described by f(0),…,f(k−1)f(0), \dots, f(k - 1) followed by δ0,…,δk−1\delta_0, \dots, \delta_{k - 1}.
    • A binary schema (u,v,Ce,σ,τ)(u, v, \mathfrak C_e, \sigma, \tau) is described by 2,u,v2, u, v, the domain Ce\mathfrak C_e, and the permutations σ,τ\sigma, \tau; a ternary schema (u,v,w,Ce,σ,τ,π)(u, v, w, \mathfrak C_e, \sigma, \tau, \pi) by 3,u,v,w3, u, v, w, the domain, and σ,τ,π\sigma, \tau, \pi.
    • The initialization value ⋆\star is written 00, and the values 0,10, 1 are written 1,21, 2.

    The system is described by k,ℓ,∣W∣k, \ell, |W|, then for each location v=0,…,∣W∣−1v = 0, \dots, |W| - 1 its initialization value followed by its domain Cv\mathfrak C_v, then ∣E∣|\mathcal E|, and finally the descriptions of the schemas in order. Its bit length HH is the length of the binary code of this list; it accounts for the explicit domains, argument maps and initializations, including their indices.

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

    Lean source view on GitHub

    1import Mathlib.Data.Finset.Sort
    2import Lax119563.BinaryEncodings
    3import Lax119563.ImplicitParitySystems
    4
    5/-!
    6---
    7title: Binary encodings of implicit parity systems
    8type: definition
    9---
    10An implicit parity system I=(W,C,(Cv)v∈W,E,ι)\mathcal I = (W, \mathfrak C, (\mathfrak C_v)_{v \in W}, \mathcal E, \iota)
    11 with coordinates C=[k]×F2ℓ\mathfrak C = [k] \times \mathbb F_2^\ell is given to a
    12Turing machine explicitly, as a list of natural numbers encoded as in the binary encodings of
    13graph pairs.
    14
    15* A block coordinate b∈F2ℓb \in \mathbb F_2^\ell is written with fixed width, as its ℓ\ell bits
    16 b0,…,bℓ−1b_0, \dots, b_{\ell - 1}, and a coordinate (i,b)(i, b) as i,b0,…,bℓ−1i, b_0, \dots, b_{\ell - 1}. Thus
    17 every coordinate and every shift listed in the input costs Ω(ℓ)\Omega(\ell) bits.
    18* A coordinate domain D⊆CD \subseteq \mathfrak C is described by ∣D∣|D| followed by its
    19 coordinates, ordered by the numbers i⋅2ℓ+∑t<ℓbt2ti \cdot 2^\ell + \sum_{t < \ell} b_t 2^t.
    20* A block-induced permutation π(i,b)=(f(i),b+δi)\pi(i, b) = (f(i), b + \delta_i) is described by
    21 f(0),…,f(k−1)f(0), \dots, f(k - 1) followed by δ0,…,δk−1\delta_0, \dots, \delta_{k - 1}.
    22* A binary schema (u,v,Ce,σ,τ)(u, v, \mathfrak C_e, \sigma, \tau) is described by 2,u,v2, u, v, the
    23 domain Ce\mathfrak C_e, and the permutations σ,τ\sigma, \tau; a ternary schema
    24 (u,v,w,Ce,σ,τ,π)(u, v, w, \mathfrak C_e, \sigma, \tau, \pi) by 3,u,v,w3, u, v, w, the domain, and
    25 σ,τ,π\sigma, \tau, \pi.
    26* The initialization value ⋆\star is written 00, and the values 0,10, 1 are written 1,21, 2.
    27
    28The system is described by k,ℓ,∣W∣k, \ell, |W|, then for each location v=0,…,∣W∣−1v = 0, \dots, |W| - 1
    29its initialization value followed by its domain Cv\mathfrak C_v, then ∣E∣|\mathcal E|, and
    30finally the descriptions of the schemas in order. Its *bit length* HH is the length of the
    31binary code of this list; it accounts for the explicit domains, argument maps and
    32initializations, including their indices.
    33
    34# Implementation notes
    35
    36The fixed width of block coordinates matters for running times: with a variable-length code
    37of block coordinates, small coordinates would be cheaper than the ℓ\ell-bit coordinates
    38the matrix compiler has to compute from them, and HH would undercount the input.
    39-/
    40
    41open Lax119563.ImplicitParitySystems Lax119563.BinaryEncodings
    42
    43namespace Lax119563.ImplicitSystemEncodings
    44
    45variable {k ℓ w : ℕ}
    46
    47/-- The number `∑_t b_t 2^t` of a block coordinate. -/
    48def blockNum (b : BlockCoord ℓ) : ℕ :=
    49 ∑ t : Fin ℓ, (b t).val * 2 ^ (t : ℕ)
    50
    51/-- The number `i · 2^ℓ + b` of a coordinate `(i, b)`. -/
    52def coordNum (c : Coord k ℓ) : ℕ :=
    53 (c.1 : ℕ) * 2 ^ ℓ + blockNum c.2
    54
    55/-- The fixed-width description `b₀, …, b_{ℓ-1}` of a block coordinate. -/
    56def blockDescription (b : BlockCoord ℓ) : List ℕ :=
    57 (List.finRange ℓ).map fun t => (b t).val
    58
    59/-- The description `i, b₀, …, b_{ℓ-1}` of the coordinate with number `c = i · 2^ℓ + b`. -/
    60def coordNumDescription (ℓ c : ℕ) : List ℕ :=
    61 c / 2 ^ ℓ :: (List.range ℓ).map fun t => if c.testBit t then 1 else 0
    62
    63/-- The description `|D|, c₁, …, c_{|D|}` of a coordinate domain, with the coordinates in
    64increasing order of their numbers. -/
    65def domainDescription (D : Finset (Coord k ℓ)) : List ℕ :=
    66 let l := (D.image coordNum).sort (· ≤ ·)
    67 l.length :: l.flatMap (coordNumDescription ℓ)
    68
    69/-- The description `f(0), …, f(k-1), δ₀, …, δ_{k-1}` of a block-induced permutation, with the
    70shifts written with fixed width. -/
    71def permDescription (π : BlockPerm k ℓ) : List ℕ :=
    72 (List.finRange k).map (fun i => (π.perm i : ℕ)) ++
    73 (List.finRange k).flatMap (fun i => blockDescription (π.shift i))
    74
    75/-- The description of an equation schema. -/
    76def schemaDescription : Schema k ℓ w → List ℕ
    77 | .binary u v D σ τ =>
    78 [2, (u : ℕ), (v : ℕ)] ++ domainDescription D ++ permDescription σ ++ permDescription τ
    79 | .ternary u v w' D σ τ π =>
    80 [3, (u : ℕ), (v : ℕ), (w' : ℕ)] ++ domainDescription D ++ permDescription σ ++
    81 permDescription τ ++ permDescription π
    82
    83/-- The number of an initialization value: `⋆ ↦ 0`, `0 ↦ 1`, `1 ↦ 2`. -/
    84def initNum : Option (ZMod 2) → ℕ
    85 | none => 0
    86 | some b => b.val + 1
    87
    88/-- The description of an implicit parity system as a list of natural numbers. -/
    89def systemDescription (I : ImplicitParitySystem k ℓ) : List ℕ :=
    90 [k, ℓ, I.numLocations] ++
    91 (List.finRange I.numLocations).flatMap
    92 (fun v => initNum (I.init v) :: domainDescription (I.domain v)) ++
    93 I.schemas.length :: I.schemas.flatMap schemaDescription
    94
    95/-- The binary encoding of an implicit parity system. -/
    96def encodeSystem (I : ImplicitParitySystem k ℓ) : List Bool :=
    97 encodeNats (systemDescription I)
    98
    99/-- The bit length `H` of an implicit parity system. -/
    100def bitLength (I : ImplicitParitySystem k ℓ) : ℕ :=
    101 (encodeSystem I).length
    102
    103end Lax119563.ImplicitSystemEncodings
    104

    Implementation notes

    The fixed width of block coordinates matters for running times: with a variable-length code of block coordinates, small coordinates would be cheaper than the ℓ\ell-bit coordinates the matrix compiler has to compute from them, and HH would undercount the input.

    Discussion

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

    Loading discussion…