Ehrhart-Macdonald reciprocity for the Birkhoff polytope
OpenMagicSquares.ehrhart_macdonald_birkhoff_posLet and let be a rational polynomial with for every natural . Then for every natural , the value of at equals, up to the sign , the number of interior lattice points of the -fold dilation of the Birkhoff polytope .
Here is the set of doubly stochastic matrices (nonnegative real matrices with all row and column sums equal to ), formalized as doublyStochastic; its vertices are the permutation matrices by the Birkhoff-von Neumann theorem, so it is an integral polytope of dimension . Its interior lattice points in the -fold dilation are exactly the strictly positive integer matrices with line sum . This is the Ehrhart-Macdonald reciprocity law applied to , due to Ehrhart and to Stanley (magic labelings of graphs). It is the geometric input of Stanley's proof: combined with the identification of the interior count with , it yields reciprocity at positive dilations.
Formalization Note Lean works with -valued matrices and counts with Set.ncard (no finiteness instance needed to state it). The dilation is written with an explicit scaled witness. The hypothesis is essential: at the left side is while the interior is empty, so the unqualified statement is false.
import Mathlib import Definitions.Def_MagicSquares import Definitions.Def_MagicSquares_positiveInteriorCount open MagicSquares
namespace MagicSquares
theorem ehrhart_macdonald_birkhoff_pos (n : ℕ) (hn : 1 ≤ n) (p : Polynomial ℚ) (hp : ∀ t : ℕ, p.eval (t : ℚ) = (semiMagicCount n t : ℚ)) : ∀ t : ℕ, 1 ≤ t → p.eval (-(t : ℚ)) = (-1 : ℚ) ^ ((n - 1) ^ 2) * (Set.ncard {M : Matrix (Fin n) (Fin n) ℚ | (∃ D, D ∈ doublyStochastic ℚ (Fin n) ∧ M = (t : ℚ) • D) ∧ ∀ i j, 0 < M i j ∧ ∃ k : ℕ, M i j = (k : ℚ)} : ℚ) := by sorry
end MagicSquares