Recovering a polynomial-length value from its CH bit language
ProvedAPSCounting893.Main.short_natural_graph_from_bitsapsbinary-arithmeticcounting-hierarchyoracle-machines
Let assign a natural number to each binary input word, and suppose fixed natural numbers bound its binary length on every input:
If the bit-query language of belongs to counting level , then its value-graph language belongs to level :
A graph query consists of a framed input word followed by arbitrary little-endian candidate bits. All such words, including candidates with trailing zeros, are covered.
This is an implicit short-value interface for arithmetic constructions: a bounded-length integer can be tested through its individual bits while retaining a fixed counting level. The hierarchy uses the published physical finite oracle machines.
Preamble
import Definitions.Def_APSCounting893_Main_BinaryOracleArithmetic set_option autoImplicit false open APSCounting893.Main
Formal statement
theorem APSCounting893.Main.short_natural_graph_from_bits
(F : Word → ℕ) (j a b : ℕ)
(hF : ∀ x,(F x).bits.length ≤ polyBound a b x.length)
(hbits : AtCHLevel j (NaturalBitLanguage F)) :
AtCHLevel (j+3) (NaturalGraphLanguage F) := by sorrySource
Finite-machine bit-to-value interface used for the short-integer operations in Hesse, Allender and Barrington, Uniform Constant-Depth Threshold Circuits for Division and Iterated Multiplication, JCSS 65(4), 2002, Section 4, pp. 8–11 of the author manuscript, https://www.cs.rutgers.edu/~allender/papers/division.pdf; arithmetic-to-threshold construction used in 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 overhead of three levels reflects the published native preprocessing and bounded-universal simulation interfaces.