Affine layered ABPs, succinct descriptions and edge queries
DefinitionNCFactorClosure607_Circuits_Supplement_ABPAn affine layered algebraic branching program of length in the variables has layers of sizes , with (source and sink). For , vertex of layer and vertex of layer carry an affine linear label (label means no edge). Its value is
the sum over source-to-sink paths of the ordered products of the labels; its width is .
A succinct description is a bit string giving the layer sizes in binary together with an auxiliary string. An edge query is the description followed by in binary; the answer is the encoding of the label's coefficients over . The evaluating algorithm is a multi-tape Turing machine of the published Cook–Levin library; halts with output within steps means that after steps it is in its halting state with on its output tape.
These are the objects of Theorem 7.2.
import Mathlib
import Definitions.Def_CookLevin_Complexity
import Definitions.Def_NCFactorClosure607_Circuits_Supplement_Encoding
/-!
# Affine layered algebraic branching programs and succinct descriptions
Arvind–Joglekar, *Factor Closure in Noncommutative Algebraic Complexity*,
STOC 2027 submission #607, §5.2, p.13 (affine layered ABPs) and §7 opening, p.17 (succinct
descriptions).
An **affine layered ABP** of length `ℓ` in the variables `x_0, …, x_{m-1}` has layers
`0, 1, …, ℓ` of sizes `n_0, …, n_ℓ`, with `n_0 = n_ℓ = 1` (the source and the sink); vertex `i`
of layer `k-1` and vertex `j` of layer `k` are joined by an edge with an affine linear label
`a_0 + Σ_x a_x x` (label `0`: no edge). Its value is the sum over all source-to-sink paths of the
ordered product of the labels along the path. Its width is the largest layer size.
A **succinct description** gives the layer sizes, together with a fixed algorithm that on binary
indices `(i, j, k)` returns the label of the edge from vertex `i` of layer `k − 1` to vertex `j`
of layer `k`. Here the description is a bit string consisting of the layer sizes in binary and an
arbitrary auxiliary string, and the algorithm is a multi-tape Turing machine of the published
Cook–Levin library (`CookLevin.Machine`) that receives the description and the query indices;
a label over `F_q` is returned as the encodings of its `m + 1` coefficients.
-/
namespace NCFactorClosure607.Circuits.Supplement
open NCFactorClosure607.Circuits Polynomial
/-- An affine linear label in the variables `Fin m`: `a 0` is the constant term and `a (i+1)` the
coefficient of `x_i`. -/
abbrev AffineLabel (F : Type*) (m : ℕ) := Fin (m + 1) → F
/-- The polynomial `a_0 + Σ_i a_{i+1} x_i` of an affine label. -/
noncomputable def AffineLabel.toPoly {F : Type*} [Field F] {m : ℕ} (a : AffineLabel F m) :
FreeAlgebra F (Fin m) :=
algebraMap F (FreeAlgebra F (Fin m)) (a 0) + ∑ i : Fin m, a i.succ • FreeAlgebra.ι F i
/-- A layered ABP over `F` in the variables `Fin m`: length `len`, layer sizes `layer k`
(`0 ≤ k ≤ len`), and for every `k < len` the labels of the edges from layer `k` to layer `k+1`. -/
structure LayeredABP (F : Type*) (m : ℕ) where
len : ℕ
layer : Fin (len + 1) → ℕ
label : (k : Fin len) → Fin (layer k.castSucc) → Fin (layer k.succ) → AffineLabel F m
namespace LayeredABP
variable {F : Type*} [Field F] {m : ℕ}
/-- A single source and a single sink: the first and last layers have one vertex each. -/
def WellFormed (A : LayeredABP F m) : Prop := A.layer 0 = 1 ∧ A.layer (Fin.last A.len) = 1
/-- The width: the largest layer size. -/
def width (A : LayeredABP F m) : ℕ := Finset.univ.sup A.layer
/-- The value: the sum over all paths `(v_0, …, v_len)` (one vertex in every layer) of the
ordered product of the edge labels. With one source and one sink these are exactly the
source-to-sink paths. -/
noncomputable def eval (A : LayeredABP F m) : FreeAlgebra F (Fin m) :=
∑ v : (k : Fin (A.len + 1)) → Fin (A.layer k),
(List.ofFn fun k : Fin A.len => (A.label k (v k.castSucc) (v k.succ)).toPoly).prod
/-- The layer sizes, in order. -/
def layerSizes (A : LayeredABP F m) : List ℕ := List.ofFn A.layer
end LayeredABP
/-- The succinct description string: the layer sizes in binary, then the auxiliary string. -/
def descriptionString (sizes : List ℕ) (aux : List Bool) : List Bool :=
tuple [tuple (sizes.map bin), aux]
/-- The input of an edge query: the description, then `i`, `j`, `k` in binary (the edge from
vertex `i` of layer `k − 1` to vertex `j` of layer `k`). -/
def edgeQuery (sizes : List ℕ) (aux : List Bool) (i j k : ℕ) : List Bool :=
tuple [tuple (sizes.map bin), aux, bin i, bin j, bin k]
/-- The encoding of an affine label over `F_p[t]/(φ)`: its `m + 1` coefficients. -/
noncomputable def encLabel {p : ℕ} {φ : (ZMod p)[X]} (hφ : φ.Monic) {m : ℕ}
(a : AffineLabel (AdjoinRoot φ) m) : List Bool :=
tuple (List.ofFn fun i => encElt hφ (a i))
/-- The `k`-tape Cook–Levin machine `M`, started on input `x`, is in its halting state after `T`
steps and its output tape then holds `y` (the convention of `CookLevin.ComputesInTime`, for one
input). -/
def HaltsWithOutput (M : CookLevin.Machine) (k : ℕ) (x : List Bool) (T : ℕ) (y : List Bool) :
Prop :=
(CookLevin.execute M (CookLevin.startConfig2 k (CookLevin.boolsToSymbols x) []) T).1 =
M.length ∧
CookLevin.outputOf k
(CookLevin.execute M (CookLevin.startConfig2 k (CookLevin.boolsToSymbols x) []) T)
(T + 2) = y
end NCFactorClosure607.Circuits.Supplement