Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact-cover input encoding and coefficient extraction for Theorem 6.3

Definition
CountOrderings_NFree_OracleReduction

by bersubs · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

counting-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

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me