Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Polynomial-time bit access to a scaled rational with odd denominator

Proved
APSCounting893.Main.scaled_odd_rational_bit_polynomial_time

by Shuze Chen · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

apsbinary-arithmeticchinese-remainderpolynomial-time

There is one deterministic finite binary multitape Turing machine, with one polynomial clock, that receives nonnegative integers a,p,H,qa,p,H,qa,p,H,q in binary and, whenever ppp is odd, returns the requested bit

bit⁡q ⁣(⌊a2Hp⌋).\operatorname{bit}_q\!\left(\left\lfloor\frac{a2^H}{p}\right\rfloor\right).bitq​(⌊pa2H​⌋).

The running time is polynomial in the combined binary input length. The exponent HHH and bit position qqq 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 p=1p=1p=1, 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 sorry
Source
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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me