Polynomial-time bit access to a scaled rational with odd denominator
ProvedAPSCounting893.Main.scaled_odd_rational_bit_polynomial_timeapsbinary-arithmeticchinese-remainderpolynomial-time
There is one deterministic finite binary multitape Turing machine, with one polynomial clock, that receives nonnegative integers in binary and, whenever is odd, returns the requested bit
The running time is polynomial in the combined binary input length. The exponent and bit position need not be bounded by a polynomial in the numerical values of the other inputs.
This is a scaled form of the reciprocal-bit calculation in Chinese remainder conversion. It allows very long rational approximations to be accessed without constructing their expanded binary strings. The denominator , the numerator zero, the exponent zero, and all bit positions are included.
Preamble
import Mathlib import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_Nat_BinaryDiv import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_List set_option autoImplicit false
Formal statement
theorem APSCounting893.Main.scaled_odd_rational_bit_polynomial_time :
∃ f : ℕ × (ℕ × (ℕ × ℕ)) → Bool,
Turing.MultiTapeTM.ComputableInPolyTime f
(Turing.MultiTapeTM.encPair Turing.MultiTapeTM.encNat
(Turing.MultiTapeTM.encPair Turing.MultiTapeTM.encNat
(Turing.MultiTapeTM.encPair Turing.MultiTapeTM.encNat Turing.MultiTapeTM.encNat)))
Turing.MultiTapeTM.encBool ∧
∀ a p H q : ℕ,Odd p → f (a,p,H,q)=(a*2^H/p).testBit q := by sorrySource
Hesse, Allender and Barrington, Uniform Constant-Depth Threshold Circuits for Division and Iterated Multiplication, JCSS 65(4), 2002, pp. 695–716, author manuscript p. 10, Lemma 4.2 and the Chinese remainder comparison argument of Lemma 4.3, https://www.cs.rutgers.edu/~allender/papers/division.pdf. Scaled extension obtained by multiplying the reciprocal by the explicitly supplied integer a; used for the arithmetic-to-threshold step 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.