The binary Sink-of-DAG CNF and lifted length
DefinitionUnaryParityLifting_Exact_Supplement_sinkDAGLet h=n². There are h² successor pointers, each with b=ceil(log₂(h+1)) bits, null code 0 and target names 1,…,h. The formula contains range clauses excluding each unused code, the disjunction making the distinguished (1,1) pointer nonnull, unit clauses making every last-row pointer null, and, for each internal pointer and k∈[h], the implication that pointer value k forces the next-row target pointer to be nonnull. These are actual clauses over the bit variables.
The grid bits are renamed bijectively to Fin N for the unchanged published lift. The lifted length is the fixed binary CNF length, including variable names, rather than a variable or clause count. The intended family has n≥1; n=0 is defined as an empty grid and excluded from the assertions.
import Definitions.Def_UnaryParityLifting_Exact_Supplement_encoding
import Definitions.Def_LiftSAParity_lift
noncomputable section
open Classical
open scoped BigOperators
namespace UnaryParityLifting.Exact.Supplement
def gridSide (n : ℕ) : ℕ := n ^ 2
def pointerBits (h : ℕ) : ℕ := Nat.clog 2 (h + 1)
abbrev GridBit (h : ℕ) := Fin h × Fin h × Fin (pointerBits h)
/-- Actual variable count: h² ceil(log₂(h+1)), h=n². -/
def baseVariables (n : ℕ) : ℕ := Fintype.card (GridBit (gridSide n))
/-- Clause excluding one pointer value (little-endian binary). -/
def forbidPointer (h : ℕ) (r c : Fin h) (k : ℕ) : LiftSAParity.Clause (GridBit h) :=
Finset.univ.image (fun j : Fin (pointerBits h) => ((r,c,j), !Nat.testBit k j.val))
def activePointer (h : ℕ) (r c : Fin h) : LiftSAParity.Clause (GridBit h) :=
Finset.univ.image (fun j : Fin (pointerBits h) => ((r,c,j), true))
/-- Range clauses, active source, null last row, and active successors. -/
def gridCNF (h : ℕ) : LiftSAParity.CNF (GridBit h) :=
(Finset.univ.biUnion fun r : Fin h => Finset.univ.biUnion fun c : Fin h =>
((Finset.range (2 ^ pointerBits h)).filter (fun k => h < k)).image (forbidPointer h r c)) ∪
((Finset.univ.filter (fun r : Fin h => r.val = 0)).biUnion fun r =>
(Finset.univ.filter (fun c : Fin h => c.val = 0)).image (activePointer h r)) ∪
((Finset.univ.filter (fun r : Fin h => r.val + 1 = h)).biUnion fun r =>
Finset.univ.biUnion fun c : Fin h =>
Finset.univ.image (fun j : Fin (pointerBits h) => ({((r,c,j), false)} : LiftSAParity.Clause (GridBit h)))) ∪
(Finset.univ.biUnion fun r : Fin h => Finset.univ.biUnion fun s : Fin h =>
if s.val = r.val + 1 then
Finset.univ.biUnion fun c : Fin h =>
Finset.univ.image (fun k : Fin h => forbidPointer h r c (k.val + 1) ∪ activePointer h s k)
else ∅)
/-- Rename the concrete bit grid to Fin N for the immutable lift interface. -/
def sinkDAG (n : ℕ) : LiftSAParity.CNF (Fin (baseVariables n)) :=
(gridCNF (gridSide n)).image (fun C =>
C.image (fun l => ((Fintype.equivFin (GridBit (gridSide n))) l.1, l.2)))
def liftedSink {m : ℕ} (g : (Fin m → Bool) → Bool) (n : ℕ) :=
LiftSAParity.lift (sinkDAG n) g
def liftedLength {m : ℕ} (g : (Fin m → Bool) → Bool) (n : ℕ) : ℕ :=
cnfBits (liftedSink g n)
end UnaryParityLifting.Exact.Supplement