Exact-cover input encoding and coefficient extraction for Theorem 6.3
DefinitionCountOrderings_NFree_OracleReductioncounting-complexitylinear-extensions
Encode an indexed family of triples by two unary headers for the universe parameter and family size, followed by its row-major incidence matrix. The decoder rejects malformed inputs. The common denominator, interpolation nodes, and rational coefficient functional specify the exact postprocessing of the amplified linear-extension counts in Appendix A.12. Lists of query or reply words use unary length prefixes.
Definition code
import Mathlib.LinearAlgebra.Lagrange
import Definitions.Def_BinaryNat_Encoding
import Definitions.Def_CountOrderings_NFree_Reduction
set_option autoImplicit false
namespace CountOrderings.NFree
/-- Parse unary headers for the universe parameter and family size, followed by the
row-major incidence matrix. Each row must encode a three-element set. -/
def decodeX3C (x : List Bool) : Option X3CInstance :=
let h := (x.takeWhile id).length
let rest := x.drop (h + 1)
let n := (rest.takeWhile id).length
let body := rest.drop (n + 1)
let S : Fin n → Finset (Fin (3 * h)) := fun i =>
Finset.univ.filter (fun j => body.getD (i.val * (3 * h) + j.val) false = true)
if x.getD h true = false ∧ rest.getD n true = false ∧ body.length = n * (3 * h) then
if hs : ∀ i, (S i).card = 3 then some ⟨h, n, S, hs⟩ else none
else none
/-- Count exact covers of the decoded indexed family, with zero on malformed strings. -/
noncomputable def x3cCount (x : List Bool) : ℕ :=
((decodeX3C x).map X3CInstance.numExactCovers).getD 0
/-- A length-prefixed encoding of a sequence of bit strings. Each word is itself
preceded by its unary length, so word boundaries can be recovered by a scan. -/
def packWords (words : List (List Bool)) : List Bool :=
CookLevin.encodeNat words.length ++
words.flatMap (fun word => CookLevin.encodeNat word.length ++ word)
/-- Decode the data bits after the unary bit-length header of a canonical reply. -/
def decodeCountReply (word : List Bool) : ℕ :=
(word.drop ((word.takeWhile id).length + 1)).foldr Nat.bit 0
/-- A safe degree bound for the numerator with the common denominator. -/
def interpolationDegree (I : X3CInstance) : ℕ :=
4 * I.n * (3 * I.h + I.n + 1)
/-- The common denominator of the normalized counts, evaluated at the original
amplification parameter (q). -/
def interpolationDenominator (I : X3CInstance) (q : ℕ) : ℚ :=
∏ i ∈ Finset.Icc 1 (4 * I.n), ∏ c ∈ Finset.range (3 * I.h + I.n + 1),
((i : ℚ) + (q : ℚ) * (c : ℚ))
/-- Value at zero of the nonvanishing part of the common denominator in the shifted
variable (t=q+1). A factor with (i=c) contributes (i) after division by (t). -/
def interpolationConstant (I : X3CInstance) : ℚ :=
∏ i ∈ Finset.Icc 1 (4 * I.n), ∏ c ∈ Finset.range (3 * I.h + I.n + 1),
if i = c then (i : ℚ) else (i : ℚ) - (c : ℚ)
/-- Interpolate the shifted numerator from the samples at (q=1,ldots,d+1).
Extract the coefficient at degree (n-h) and apply the exact-cover scaling. -/
noncomputable def recoverExactCoverCount (I : X3CInstance) (sample : ℕ → ℕ) : ℚ :=
let P := Lagrange.interpolate (Finset.range (interpolationDegree I + 1))
(fun j : ℕ => (j : ℚ) + 2) (fun j : ℕ =>
interpolationDenominator I (j + 1) * (sample (j + 1) : ℚ) /
((4 * I.n + 3 * I.h * (j + 1) + I.n * (j + 1)).factorial : ℚ))
(4 : ℚ) ^ I.h * (3 : ℚ) ^ (I.n - I.h) *
P.coeff (I.n - I.h) / interpolationConstant I
/-- The exact rational postprocessing on standing instances. On degenerate instances,
the count is specified directly and can be obtained by coverage and size checks. -/
noncomputable def finishX3C (x : List Bool) (replies : List (List Bool)) : ℕ := by
classical
exact match decodeX3C x with
| none => 0
| some I =>
if I.Standing then
(Rat.floor (recoverExactCoverCount I (fun q =>
decodeCountReply (replies.getD (q - 1) [])))).toNat
else I.numExactCovers
end CountOrderings.NFree
Source
Arenas, Schild and Subercaseaux, Hardness of Counting Orderings: Taking Gadget Amplification to the Limit, STOC 2027 submission #1207, https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1207.pdf, Appendix A.12, pp. 37–38 (PDF pp. 38–39), proof of Theorem 6.3