Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Proved
BarvinokCount.ShortFormula.latticeCount_eq_short_signed_sum

by mikedeng1 · Oct 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

barvinok-algorithmbrion-identitylattice-pointsp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1signed-decomposition

Let d≥2d\ge2d≥2 and let v1,…,vk+1∈Zdv_1,\dots,v_{k+1}\in\mathbb{Z}^dv1​,…,vk+1​∈Zd be affinely independent, so that Δ=conv⁡{v1,…,vk+1}\Delta=\operatorname{conv}\{v_1,\dots,v_{k+1}\}Δ=conv{v1​,…,vk+1​} is a kkk-dimensional integral simplex. For each vertex vjv_jvj​ let KvjK_{v_j}Kvj​​ be the supporting cone of Δ\DeltaΔ at vjv_jvj​ (Definition 2.6), and let Ind⁡j\operatorname{Ind}_jIndj​ be the index of the cone generated by the edge vectors vi−vjv_i-v_jvi​−vj​ (i≠ji\ne ji=j). Then for each jjj there are NjN_jNj​ primitive cones Kj,i=co⁡(gj,i)K_{j,i}=\operatorname{co}(g_{j,i})Kj,i​=co(gj,i​), given by primitive generators gj,ig_{j,i}gj,i​, and integers εj,i\varepsilon_{j,i}εj,i​, i=1,…,Nji=1,\dots,N_ji=1,…,Nj​, such that

  1. Nj≤(2d)TjN_j\le(2^d)^{T_j}Nj​≤(2d)Tj​, where TjT_jTj​ is the smallest integer with Tj≥(−log⁡log⁡1.9+log⁡log⁡Ind⁡j)/(log⁡d−log⁡(d−1))T_j\ge(-\log\log1.9+\log\log\operatorname{Ind}_j)/(\log d-\log(d-1))Tj​≥(−loglog1.9+loglogIndj​)/(logd−log(d−1)) (Tj=0T_j=0Tj​=0 if Ind⁡j=1\operatorname{Ind}_j=1Indj​=1);
  2. Kvj=∑iεj,iKj,iK_{v_j}=\sum_i\varepsilon_{j,i}K_{j,i}Kvj​​=∑i​εj,i​Kj,i​, as characteristic functions on all of Rd\mathbb{R}^dRd;
  3. for every c∈Rdc\in\mathbb{R}^dc∈Rd that is orthogonal to no generator of any Kj,iK_{j,i}Kj,i​, each constant term R(Kj,i,vj,c)R(K_{j,i},v_j,c)R(Kj,i​,vj​,c) of the Laurent expansion of
t⟼exp⁡{⟨t⋅c,vj⟩}⋅σ(Kj,i;t⋅c)t\longmapsto\exp\{\langle t\cdot c,v_j\rangle\}\cdot\sigma(K_{j,i};t\cdot c)t⟼exp{⟨t⋅c,vj​⟩}⋅σ(Kj,i​;t⋅c)

at t=0t=0t=0 exists, and

#(Δ∩Zd)=∑j=1k+1∑i=1Njεj,i R(Kj,i,vj,c).\#(\Delta\cap\mathbb{Z}^d)=\sum_{j=1}^{k+1}\sum_{i=1}^{N_j}\varepsilon_{j,i}\,R(K_{j,i},v_j,c).#(Δ∩Zd)=j=1∑k+1​i=1∑Nj​​εj,i​R(Kj,i​,vj​,c).

This is what Barvinok's polynomial-time algorithm computes: for fixed ddd the number of terms is bounded by a polynomial in the input size, and each R(Kj,i,vj,c)R(K_{j,i},v_j,c)R(Kj,i​,vj​,c) 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 ccc; the size bound depends only on ddd and the indices. Added or fixed choices: d≥2d\ge2d≥2, because TTT involves log⁡(d−1)\log(d-1)log(d−1); the generators of KvjK_{v_j}Kvj​​ used for the index are the edge vectors vi−vjv_i-v_jvi​−vj​, as in the proof's "integral generators u1(v),…,uk(v)u_1(v),\dots,u_k(v)u1​(v),…,uk​(v)"; ccc is real; T=0T=0T=0 when the index is 111. The constant terms are unique when they exist, so the existential choice of the numbers RRR is the paper's R(Ki,v,c)R(K_i,v,c)R(Ki​,v,c).

Preamble
import Mathlib
import Definitions.Def_BarvinokCount_ShortFormula_sigma
import Definitions.Def_BarvinokCount_ShortFormula_integralSimplex
import Definitions.Def_BarvinokCount_ShortFormula_iterCount
Formal statement
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
Source
Barvinok, A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, Math. Oper. Res. 19 (1994), p. 769, Problem 1.1 and Theorem 1.2; proof on p. 778; count from the proof of Theorem 5.4, p. 777
Human review
  • Endorsed by Shuze Chen · Oct 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 4, 2026

    Confirmed by the mission captain (proposal self-audit).

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