Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.8 — Integral closure membership in CH and non-integrality reduction

Open
APSCounting893.Main.Supplement.integral_closure_in_ch

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

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

For valid circuit or sparse inputs over the encoded rational, number or finite fields, let fff be the first output, let F=(f1,…,fm)F=(f_1,\ldots,f_m)F=(f1​,…,fm​) be the remaining outputs, and let A=k[f1,…,fm]A=k[f_1,\ldots,f_m]A=k[f1​,…,fm​]. Integral-closure membership has a single fixed-level Counting Hierarchy decider, and non-integrality admits a deterministic polynomial-time many-one reduction to APS:

ICM∈CH,non-ICM≤mPAPS.\mathrm{ICM}\in\mathrm{CH},\qquad\mathrm{non\text{-}ICM}\le_m^{\mathrm P}\mathrm{APS}.ICM∈CH,non-ICM≤mP​APS.

The decider and reduction work uniformly over all valid inputs, including division gates with the published promises and sparse lists with binary exponents. Integrality is over the described base field and APS over its algebraic closure. There is no restriction on expanded degree, characteristic or separability. This supplies the paper's integral-closure complexity conclusion alongside the referenced APS goal.

Differences from the source:

  • encoding: binary circuit and sparse instances and their promises → a common SystemInput wrapper, with f first and valid-source many-one correctness; reason: representation tags, field descriptions and all bit lengths remain charged; invalid inputs impose no correctness requirement
  • encoding: membership belongs to CH → existence of a total language in CH agreeing on every valid integral instance; reason: one language, level, machine and polynomial bound precede every input; no particular CH level is asserted
  • encoding: Problem 1.2 uses the complex subalgebra on rational input, and Remark 1.9 uses the base field → integrality over the presented base-field subalgebra for all encoded families; reason: integral dependence of these polynomials descends and ascends under scalar extension, so rational inputs give the same decisions
Preamble
import Definitions.Def_APSCounting893_Main_Supplement_DecisionProblems

set_option autoImplicit false
Formal statement
namespace APSCounting893.Main.Supplement

/-- Theorem 1.8, including binary sparse inputs, division promises and Remarks 1.9/7.10.
The language, level, machines and polynomial bounds precede every field and input. -/
theorem integral_closure_in_ch :
    (∃ L : Language, InCountingHierarchy L ∧
      ∀ I : SystemInput, I.ValidIntegral → (L I.encode ↔ I.Integral)) ∧
    PolynomialManyOne SystemInput.ValidIntegral (fun I => ¬ I.Integral)
      SystemInput.Valid SystemInput.APS := by sorry

end APSCounting893.Main.Supplement
Source
Sanyam Agarwal, Archit Hari, Anurag Pandey, Himanshu Shukla, STOC 2027 submission #893 (October 2026), Theorem 1.8, p. 4

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