Implicit sums of exponentially many short integers stay in CH
ProvedAPSCounting893.Main.implicit_short_integer_sums_in_chapsbinary-arithmeticcounting-hierarchyimplicit-sums
Let be a total natural-valued function on binary words whose output length is bounded by fixed natural numbers :
For fixed natural numbers , put and define the actual implicit sum
If the value graph of belongs to counting level , then the value graph of belongs to level . Moreover,
All resource constants and the relative hierarchy overhead precede the input word. This supplies uniform short-integer iterated addition for implicit Chinese remainder arithmetic without constructing the exponentially long list of summands.
Preamble
import Definitions.Def_APSCounting893_Main_ImplicitCountingArithmetic set_option autoImplicit false open APSCounting893.Main
Formal statement
theorem APSCounting893.Main.implicit_short_integer_sums_in_ch
(F : Word → ℕ) (j a b e f : ℕ)
(hF : ∀ x,(F x).bits.length ≤ polyBound e f x.length)
(hgraph : AtCHLevel j (NaturalGraphLanguage F)) :
AtCHLevel (j+11) (NaturalGraphLanguage (indexedNaturalSum F a b)) ∧
∀ x,(indexedNaturalSum F a b x).bits.length ≤
polyBound (a+e*(a+4)^f+2) (max b ((b+1)*f)) x.length := by sorrySource
Implicit short-integer form of the iterated-addition steps in Hesse, Allender and Barrington, Uniform Constant-Depth Threshold Circuits for Division and Iterated Multiplication, JCSS 65(4), 2002, author manuscript Section 4, Lemmas 4.1 and 4.3, pp. 9–10, https://www.cs.rutgers.edu/~allender/papers/division.pdf. Used in the arithmetic-to-threshold argument of Agarwal, Hari, Pandey and Shukla, STOC 2027 submission #893, Theorem 6.4, pp. 25–26, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/893.pdf. The explicit eleven-level overhead comes from the published finite-machine comparison, counting and graph interfaces.