Theorem 1.2 (mathematical content) — the lattice-point count of an integral simplex is a signed sum over at most (2^d)^T primitive cones per vertex
ProvedBarvinokCount.ShortFormula.latticeCount_eq_short_signed_sumLet and let be affinely independent, so that is a -dimensional integral simplex. For each vertex let be the supporting cone of at (Definition 2.6), and let be the index of the cone generated by the edge vectors (). Then for each there are primitive cones , given by primitive generators , and integers , , such that
- , where is the smallest integer with ( if );
- , as characteristic functions on all of ;
- for every that is orthogonal to no generator of any , each constant term of the Laurent expansion of
at exists, and
This is what Barvinok's polynomial-time algorithm computes: for fixed the number of terms is bounded by a polynomial in the input size, and each is an explicit rational function of inner products (Corollary 4.2).
Formalization Note Theorem 1.2 states that a polynomial time algorithm for Problem 1.1 exists. No machine model is formalized; the statement is the identity established in the proof of Theorem 1.2 (p. 778), with the size of the decompositions from the proof of Theorem 5.4 (p. 777). The decompositions are chosen first and the formula holds for every admissible ; the size bound depends only on and the indices. Added or fixed choices: , because involves ; the generators of used for the index are the edge vectors , as in the proof's "integral generators "; is real; when the index is . The constant terms are unique when they exist, so the existential choice of the numbers is the paper's .
import Mathlib import Definitions.Def_BarvinokCount_ShortFormula_sigma import Definitions.Def_BarvinokCount_ShortFormula_integralSimplex import Definitions.Def_BarvinokCount_ShortFormula_iterCount
namespace BarvinokCount.ShortFormula
theorem latticeCount_eq_short_signed_sum {d k : ℕ} (hd : 2 ≤ d)
(v : Fin (k + 1) → Fin d → ℤ) (hv : AffineIndependent ℝ fun j => castVec (v j)) :
∃ (N : Fin (k + 1) → ℕ) (m : (j : Fin (k + 1)) → Fin (N j) → ℕ)
(g : (j : Fin (k + 1)) → (i : Fin (N j)) → Fin (m j i) → Fin d → ℤ)
(ε : (j : Fin (k + 1)) → Fin (N j) → ℤ),
(∀ j i, IsPrimitiveGens (g j i)) ∧
(∀ j, N j ≤ (2 ^ d) ^ iterCount d (coneIndex (edgeGens v j))) ∧
(∀ j, IsSignedConeDecomp (supportingCone (simplex v) (castVec (v j))) (g j) (ε j)) ∧
∀ c : Fin d → ℝ, (∀ j i, IsRegular (g j i) c) →
∃ R : (j : Fin (k + 1)) → Fin (N j) → ℝ,
(∀ j i, IsLaurentConstTerm
(fun t => Real.exp (t * (c ⬝ᵥ castVec (v j))) * sigma (g j i) (t • c)) (R j i)) ∧
(latticeCount (simplex v) : ℝ) = ∑ j, ∑ i, (ε j i : ℝ) * R j i := by sorry
end BarvinokCount.ShortFormula
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.