Integer interpolation on packed exact-cover inputs and oracle replies
DefinitionCountOrderings_NFree_InterpolationWordProgramThe explicit integer program decodes the packed reply list, forms Lagrange coefficient numerators with common signed denominators, and obtains the specified exact-cover count by a single final division.
Definition code
import Definitions.Def_CountOrderings_NFree_OracleReduction
set_option autoImplicit false
namespace CountOrderings.NFree
/-- Multiply a coefficient list by (X - a), emitting the supplied constant carry. -/
def shiftedCoefficients (a carry : ℤ) : List ℤ → List ℤ
| [] => [carry]
| c :: cs => (carry - a * c) :: shiftedCoefficients a c cs
/-- Zero-based interpolation indexes other than the specified node. -/
def otherNodes (d j : ℕ) : List ℕ := (List.range (d + 1)).filter fun m => m != j
/-- Requested coefficient in the unnormalized Lagrange basis numerator. -/
def integerBasisCoeff (d j k : ℕ) : ℤ :=
((otherNodes d j).foldl (fun cs (m : ℕ) => shiftedCoefficients ((m : ℤ) + 2) 0 cs) [1]).getD k 0
/-- Signed factor from the differences of the Lagrange nodes. -/
def integerBasisDenominator (d j : ℕ) : ℤ :=
((otherNodes d j).map fun m : ℕ => (j : ℤ) - (m : ℤ)).prod
/-- The common denominator evaluated at the positive sample q. -/
def integerInterpolationDenominator (I : X3CInstance) (q : ℕ) : ℤ :=
((List.range' 1 (4 * I.n)).map fun i : ℕ =>
((List.range (3 * I.h + I.n + 1)).map fun c : ℕ =>
(i : ℤ) + (q : ℤ) * (c : ℤ)).prod).prod
/-- The constant factor after removing the zero at q = -1. -/
def integerInterpolationConstant (I : X3CInstance) : ℤ :=
((List.range' 1 (4 * I.n)).map fun i : ℕ =>
((List.range (3 * I.h + I.n + 1)).map fun c : ℕ =>
if i = c then (i : ℤ) else (i : ℤ) - (c : ℤ)).prod).prod
/-- Add two numerator/denominator pairs without a gcd computation. -/
def addUnreducedFraction (a b : ℤ × ℤ) : ℤ × ℤ :=
(a.1 * b.2 + b.1 * a.2, a.2 * b.2)
def sumUnreducedFractions (xs : List (ℤ × ℤ)) : ℤ × ℤ :=
xs.foldr addUnreducedFraction (0, 1)
/-- One summand of the requested coefficient, in exact signed integer arithmetic. -/
def integerInterpolationSummand (I : X3CInstance) (sample : ℕ → ℕ) (j : ℕ) : ℤ × ℤ :=
let q := j + 1
(integerInterpolationDenominator I q * (sample q : ℤ) *
integerBasisCoeff (interpolationDegree I) j (I.n - I.h),
((4 * I.n + 3 * I.h * q + I.n * q).factorial : ℤ) *
integerBasisDenominator (interpolationDegree I) j)
/-- Explicit integer numerator and denominator for the recovered #X3C value.
Coefficients are obtained by repeated multiplication by linear polynomials. -/
def recoverExactCoverFraction (I : X3CInstance) (sample : ℕ → ℕ) : ℤ × ℤ :=
let fraction := sumUnreducedFractions
((List.range (interpolationDegree I + 1)).map (integerInterpolationSummand I sample))
((4 : ℤ) ^ I.h * (3 : ℤ) ^ (I.n - I.h) * fraction.1,
integerInterpolationConstant I * fraction.2)
/-- Signed integer division with a positive divisor computes the rational floor. -/
def integerFractionFloor (a : ℤ × ℤ) : ℤ :=
if a.2 < 0 then (-a.1) / (a.2.natAbs : ℤ) else a.1 / (a.2.natAbs : ℤ)
/-- Check coverage by enumerating the universe and scanning the indexed family. -/
def interpolationCovered (I : X3CInstance) : Bool :=
(List.finRange (3 * I.h)).all fun j =>
(List.finRange I.n).any fun i => decide (j ∈ I.S i)
/-- Integer implementation of the postprocessing specification, including invalid or
degenerate inputs and arbitrary oracle replies. -/
def finishX3CInteger (x : List Bool) (replies : List (List Bool)) : ℕ :=
match decodeX3C x with
| none => 0
| some I =>
if interpolationCovered I then
if I.h < I.n then
(integerFractionFloor (recoverExactCoverFraction I fun q =>
decodeCountReply (replies.getD (q - 1) []))).toNat
else if I.h = I.n then 1 else 0
else 0
/-- Read the indicated number of unary-length-prefixed fields. -/
def unpackInterpolationFields : ℕ → List Bool → List (List Bool)
| 0, _ => []
| n + 1, bits =>
let header := CookLevin.decodeNatFuel bits.length bits
header.2.take header.1 :: unpackInterpolationFields n (header.2.drop header.1)
/-- Read a field count followed by the fields. -/
def unpackInterpolationWords (bits : List Bool) : List (List Bool) :=
let header := CookLevin.decodeNatFuel bits.length bits
unpackInterpolationFields header.1 header.2
/-- Total executable bit-string implementation of the interpolation postprocessor. -/
def interpolationWordProgram (input : List Bool) : List Bool :=
match unpackInterpolationWords input with
| [] => NPBinary.encodeNat 0
| x :: replies => NPBinary.encodeNat (finishX3CInteger x replies)
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