Lemma 6.1 — Image dimension from exact feasibility
ProvedAPSCounting893.Main.image_dimension_in_chalgebraic-geometryapscomplexity-theoryp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let a rational arithmetic circuit represent a polynomial map , with every binary constant and wire charged in the input length. There are one language and one deterministic polynomial-time oracle machine computing a function such that every valid circuit input satisfies
The oracle, machine and polynomial bound are fixed for all circuits and dimensions, including constant maps. This provides the actual geometric dimension as a function output.
Differences from the source:
- encoding: dimension computable in deterministic polynomial time with a fixed-level CH oracle → one total bit-string function implemented by the finite oracle machine, returning the binary natural dimension; reason: fixes the source Turing model and includes the semantic circuit promise
Preamble
import Definitions.Def_APSCounting893_Main_SampledResultant set_option autoImplicit false
Formal statement
namespace APSCounting893.Main
theorem image_dimension_in_ch :
∃ (A : Language) (f : Word → Word), InCountingHierarchy A ∧ FunctionInPWithOracle A f ∧
∀ (n : ℕ) (C : ArithmeticCircuit n), ValidCircuit .rational C →
∃ r : ℕ,
RSCapacity.algDim (imageClosure (rationalComplexPolynomials C)) =
((r : ℕ∞) : WithBot ℕ∞) ∧ f C.encode = encodeNat r := by sorry
end APSCounting893.Main
Source
Sanyam Agarwal, Archit Hari, Anurag Pandey, Himanshu Shukla, STOC 2027 submission #893 (October 2026), Lemma 6.1, p. 23, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/893.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.