Comparison language and exponentially indexed natural sums
DefinitionAPSCounting893_Main_ImplicitCountingArithmeticapsbinary-arithmeticcounting-hierarchy
For a natural-valued function on binary words, the comparison language tests whether the little-endian value written after a framed input is strictly below .
For fixed resource constants , let . The implicit indexed sum is
where the index uses exactly little-endian bits and denotes concatenation.
These objects support uniform counting arguments for short integer arithmetic. The sum is the actual finite natural-number sum; it does not assume a circuit, arithmetic oracle, or complexity bound.
Definition code
import Definitions.Def_APSCounting893_Main_BinaryOracleArithmetic
set_option autoImplicit false
namespace APSCounting893.Main
def NaturalLessLanguage (F : Word → ℕ) : Language :=
fun z => Turing.MultiTapeTM.ofBits (Turing.MultiTapeTM.dropFrame z)<F (Turing.MultiTapeTM.unframe z)
noncomputable def indexedNaturalSum (F : Word → ℕ) (a b : ℕ) (x : Word) : ℕ :=
∑ i : Fin (2^polyBound a b x.length),F (Turing.MultiTapeTM.frame x++
Cslib.BitString.lowBits (polyBound a b x.length) i.val)
end APSCounting893.Main
Source
Hesse, Allender and Barrington, Uniform Constant-Depth Threshold Circuits for Division and Iterated Multiplication, JCSS 65(4), 2002, author manuscript Section 4, pp. 8–11, including the iterated-addition steps in Lemmas 4.1 and 4.3, https://www.cs.rutgers.edu/~allender/papers/division.pdf; used in the arithmetic simulation 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.