Bit codes of graphs, layouts, decompositions and outputs
DefinitionSubspaceConv_Supplement_graphCodeAlgorithms receive and return bit strings. A graph on vertices is coded by in unary followed by its adjacency bits, row by row. A linear layout is coded by the list of its vertices in order, each in unary. A rank-decomposition is coded by the number of tree nodes in unary, the adjacency bits of the tree, and the leaf of every vertex in unary. An output number is in binary; an output integer is a sign bit, the unary length of its binary absolute value, and that value; a polynomial is the list of its coefficients of degrees . (A coloring is output as the list of the colors of the vertices in unary, by the published HiddenPartition.Supplement.encodeLabels.)
These codes fix the inputs and outputs of the machines of Theorems 6, 8, 9 and 10. They are injective, and for layouts (and for decompositions with nodes) their length is polynomial in , so the exponents of the time bounds are not shifted.
Formalization Note Unary numbers use the published CookLevin.encodeNat; binary numbers use Mathlib's Nat.bits (least significant bit first).
import Mathlib
import Definitions.Def_CookLevin_Satisfiability
import Definitions.Def_ApproxCliqueWidth_Certificate_BranchDecomp
set_option autoImplicit false
open Classical
namespace SubspaceConv.Supplement
/-!
# Bit codes of graphs, layouts, decompositions and outputs
The inputs and outputs of the algorithms of Theorems 6, 8, 9 and 10 of Perles–Weinstein, *A Fast Algorithm for Subspace Convolution*, STOC 2027 submission manuscript (sha256 a8ffb1b4…604ab2) (p.16, 27, 30;
PDF p.17, 28, 31), as bit strings for the published `CookLevin` machine.
**Formalization Note** Natural numbers in inputs are unary (published `CookLevin.encodeNat`:
`n` ones then a zero). A graph on `Fin N` is `N` followed by its `N²` adjacency bits, row by
row. A linear layout `π` is the list `π(0), …, π(N−1)`. A rank-decomposition is the number `m` of
tree nodes, the `m²` adjacency bits of the tree, and the leaf `L(v)` of every vertex `v`. All these
codes are injective, and for layouts and for decompositions with `O(N)` nodes their length is
polynomial in `N`. Output numbers are binary (Mathlib `Nat.bits`, least significant bit first); an
output integer is a sign bit, the unary length of its binary absolute value, and that value; a
coefficient list is the `N + 1` coefficients of degrees `0, …, N` in order. (A coloring is output
with the published `HiddenPartition.Supplement.encodeLabels`: the colors `c(0), …, c(N−1)` in
unary.)
-/
/-- Code of a graph on `Fin N`: `N` in unary, then the adjacency matrix row by row. -/
noncomputable def graphCode {N : ℕ} (G : SimpleGraph (Fin N)) : List Bool :=
CookLevin.encodeNat N ++
(List.finRange N).flatMap (fun i => (List.finRange N).map (fun j => decide (G.Adj i j)))
/-- Code of a linear layout `π`: the vertices `π(0), …, π(N−1)` in unary. -/
def layoutCode {N : ℕ} (π : Fin N ≃ Fin N) : List Bool :=
(List.finRange N).flatMap (fun i => CookLevin.encodeNat (π i).val)
/-- Code of a rank-decomposition: the number of tree nodes, the tree's adjacency matrix, and the
leaf of every vertex. -/
noncomputable def rdCode {N : ℕ} (D : ApproxCliqueWidth.Certificate.BranchDecomp (Fin N)) :
List Bool :=
CookLevin.encodeNat D.n ++
(List.finRange D.n).flatMap (fun s => (List.finRange D.n).map (fun t => decide (D.T.Adj s t)))
++ (List.finRange N).flatMap (fun v => CookLevin.encodeNat (D.L v).val)
/-- Code of an output integer: sign bit, unary length of the binary absolute value, the value. -/
def intCode (z : ℤ) : List Bool :=
decide (z < 0) :: (CookLevin.encodeNat (Nat.bits z.natAbs).length ++ Nat.bits z.natAbs)
/-- Code of the ordinary coefficients of degrees `0, …, N` of an integer polynomial. -/
noncomputable def polyCode (N : ℕ) (P : Polynomial ℤ) : List Bool :=
(List.range (N + 1)).flatMap (fun i => intCode (P.coeff i))
end SubspaceConv.Supplement