Bit access to implicit sums of long integers stays in CH
ProvedAPSCounting893.Main.implicit_long_integer_sums_in_chapsbinary-arithmeticcounting-hierarchyimplicit-sums
Let be a total natural-valued function on binary words. Assume that its bit language, with a length-delimited input and a binary bit index, belongs to counting level . For fixed natural numbers , set and define the actual sum
Then
There is no hypothesis on the bit length of . The relative hierarchy overhead and all machine resource constants precede the input word and the queried bit index. This supplies uniform iterated addition for exponentially indexed integer families, including the long dyadic numerators used in Chinese remainder comparison.
Preamble
import Definitions.Def_APSCounting893_Main_ImplicitCountingArithmetic set_option autoImplicit false open APSCounting893.Main
Formal statement
theorem APSCounting893.Main.implicit_long_integer_sums_in_ch (F : Word → ℕ) (j a b : ℕ)
(hF : AtCHLevel j (NaturalBitLanguage F)) :
AtCHLevel (j+22) (NaturalBitLanguage (indexedNaturalSum F a b)) := by sorrySource
Iterated-addition ingredient in Hesse, Allender and Barrington, Uniform Constant-Depth Threshold Circuits for Division and Iterated Multiplication, JCSS 65(4), 2002, author manuscript Section 3, p. 7, and Section 4, Lemma 4.3, pp. 10–11, https://www.cs.rutgers.edu/~allender/papers/division.pdf. Explicit finite oracle-machine bit-language implementation for 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 relative level 22 is an implementation bound proved here, not a numerical level claimed by either source.