Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Integral-closure certificates, powered systems and algebraic branches

Definition
APSCounting893_Main_Supplement_Certificates

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

algebraic-geometrycomplexity-theoryintegral-closurep2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

For a field KKK, a tuple F=(f1,…,fm)F=(f_1,\ldots,f_m)F=(f1​,…,fm​) and a target fff in K[x1,…,xn]K[x_1,\ldots,x_n]K[x1​,…,xn​], introduce an independent variable uuu and set Φ=(f1,…,fm,u,1−uf)\Phi=(f_1,\ldots,f_m,u,1-uf)Φ=(f1​,…,fm​,u,1−uf). A certificate Q∈K[Y1,…,Ym,U,V]Q\in K[Y_1,\ldots,Y_m,U,V]Q∈K[Y1​,…,Ym​,U,V] satisfies

Q(f1,…,fm,u,1−uf)=0,Q(Y1,…,Ym,0,0)=1.Q(f_1,\ldots,f_m,u,1-uf)=0,\qquad Q(Y_1,\ldots,Y_m,0,0)=1.Q(f1​,…,fm​,u,1−uf)=0,Q(Y1​,…,Ym​,0,0)=1.

The first equality is a polynomial identity in (x,u)(x,u)(x,u); the second is a polynomial identity in all YYY. The complex annihilator is the published substitution kernel with its outputs reindexed. Put Δ=max⁡{deg⁡fi,deg⁡f+1}\Delta=\max\{\deg f_i,\deg f+1\}Δ=max{degfi​,degf+1} and D0=(ρ+2)Δρ+1D_0=(\rho+2)\Delta^{\rho+1}D0​=(ρ+2)Δρ+1, where ρ\rhoρ is the transcendence degree of the generated fraction field. Define ΨM=(uf1M,…,ufmM,u,1−uf)\Psi_M=(uf_1^M,\ldots,uf_m^M,u,1-uf)ΨM​=(uf1M​,…,ufmM​,u,1−uf). Zero polynomials have total degree zero and Δ≥1\Delta\ge1Δ≥1.

For the boundedness criterion, algebraic branches of C(t)‾\overline{\mathbb C(t)}C(t)​ are realized inside the published Puiseux ambient field: a branch is a Puiseux series satisfying a nonzero polynomial in C[t][X]\mathbb C[t][X]C[t][X]. This is the algebraic part of the Puiseux closure, with unrestricted ramification. Its valuation is the series order, including val⁡t(0)=+∞\operatorname{val}_t(0)=+\inftyvalt​(0)=+∞. These constructions define the actual polynomial objects used by the certificate and reduction theorems.

Definition code
import Definitions.Def_APSCounting893_Main_Supplement_Integrality

set_option autoImplicit false

namespace APSCounting893.Main.Supplement

/-- Output variables are Y indexed by Fin m, followed by U and V indexed by Fin 2. -/
abbrev Certificate (K : Type) [CommSemiring K] (m : ℕ) :=
  MvPolynomial (Fin m ⊕ Fin 2) K

noncomputable def phiSystem {K : Type} [Field K] {n m : ℕ}
    (F : PolynomialMap K n m) (f : Polynomials K n) : PolynomialMap K (n + 1) (m + 2) :=
  Fin.addCases (fun i => extendPolynomial (F i))
    (fun j : Fin 2 => if j = 0 then freshVariable n
      else 1 - freshVariable n * extendPolynomial f)

/-- Substitution in the full polynomial ring, with u independent of x. -/
noncomputable def certificateSubstitute {K : Type} [Field K] {n m : ℕ}
    (F : PolynomialMap K n m) (f : Polynomials K n) :
    Certificate K m →+* Polynomials K (n + 1) :=
  MvPolynomial.eval₂Hom MvPolynomial.C
    (Sum.elim (fun i => extendPolynomial (F i))
      (fun j : Fin 2 => if j = 0 then freshVariable n
        else 1 - freshVariable n * extendPolynomial f))

/-- Restriction to U=V=0 is a polynomial in every Y coordinate. -/
noncomputable def certificateSlice {K : Type} [Field K] {m : ℕ} :
    Certificate K m →+* Polynomials K m :=
  MvPolynomial.eval₂Hom MvPolynomial.C (Sum.elim MvPolynomial.X (fun _ => 0))

noncomputable def certificateAt {K : Type} [Field K] {m : ℕ}
    (c : Affine K m) (Q : Certificate K m) : K :=
  MvPolynomial.eval (Sum.elim c (fun _ => 0)) Q

/-- Reuse the published complex annihilator through the canonical output reindexing. -/
noncomputable def certificateAnnihilates {n m : ℕ} (F : PolynomialMap ℂ n m)
    (f : Polynomials ℂ n) (Q : Certificate ℂ m) : Prop :=
  MvPolynomial.rename (Sum.elim (fun i : Fin m => i.castAdd 2)
    (fun j : Fin 2 => j.natAdd m)) Q ∈ annihilator (phiSystem F f)

def GlobalCertificate {K : Type} [Field K] {n m : ℕ}
    (F : PolynomialMap K n m) (f : Polynomials K n) (Q : Certificate K m) : Prop :=
  certificateSubstitute F f Q = 0 ∧ certificateSlice Q = 1

noncomputable def certificateDelta {K : Type} [Field K] {n m : ℕ}
    (F : PolynomialMap K n m) (f : Polynomials K n) : ℕ :=
  max (Finset.univ.sup (fun i => (F i).totalDegree)) (f.totalDegree + 1)

noncomputable def certificateBound {K : Type} [Field K] {n m : ℕ}
    (F : PolynomialMap K n m) (f : Polynomials K n) : ℕ :=
  (generatorRank F + 2) * certificateDelta F f ^ (generatorRank F + 1)

/-- The power is on each generator, before multiplication by u. -/
noncomputable def poweredSystem {K : Type} [Field K] {n m : ℕ}
    (F : PolynomialMap K n m) (f : Polynomials K n) (M : ℕ) :
    PolynomialMap K (n + 1) (m + 2) :=
  Fin.addCases (fun i => freshVariable n * extendPolynomial (F i) ^ M)
    (fun j : Fin 2 => if j = 0 then freshVariable n
      else 1 - freshVariable n * extendPolynomial f)

/-- Algebraic branches of C(t) in a fixed Puiseux algebraic closure. The polynomial relation
has coefficients in C[t] and is nonzero as a polynomial before specialization. Clearing
rational-function denominators loses no algebraic branch. -/
def IsAlgebraicBranch (s : PuiseuxAmbient) : Prop :=
  IsPuiseux s ∧ ∃ p : Polynomial (Polynomial ℂ), p ≠ 0 ∧
    Polynomial.eval₂
      (Polynomial.eval₂RingHom HahnSeries.C (HahnSeries.single (1 : ℚ) (1 : ℂ))) s p = 0

end APSCounting893.Main.Supplement
Source
Sanyam Agarwal, Archit Hari, Anurag Pandey, Himanshu Shukla, STOC 2027 submission #893 (October 2026), §7, pp. 28–32; Theorems 7.3, 7.5, 7.7–7.8 and Corollary 7.6

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