Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A word-RAM test of whether a zero-padded prefix contains the whole instance and covers its size

Open
TwoFoldOPI.encodeLengthDecider_RAM

by sragavan · Nov 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

optimal-polynomial-intersectionuniformityword-ram

For an instance xxx of Theorem 7.4 let enc(x)\mathrm{enc}(x)enc(x) be its public bit encoding (field presentation, mmm, rrr, tag, matrix, forbidden values, precision) and scale(x)=m+r+q+t\mathrm{scale}(x)=m+r+q+tscale(x)=m+r+q+t. For s≥0s\ge0s≥0 let enc(x)[s]\mathrm{enc}(x)_{[s]}enc(x)[s]​ be the first sss bits of enc(x) 0∞\mathrm{enc}(x)\,0^\inftyenc(x)0∞.

There are a word-RAM algorithm AAA in the restricted instruction set and a function vvv on bit strings such that AAA computes vvv in polynomial time and, for every instance xxx and every sss,

v(enc(x)[s])=[ ∣enc(x)∣≤s  and  scale(x)≤s ].v\bigl(\mathrm{enc}(x)_{[s]}\bigr)=\bigl[\,|\mathrm{enc}(x)|\le s\ \text{ and }\ \mathrm{scale}(x)\le s\,\bigr].v(enc(x)[s]​)=[∣enc(x)∣≤s  and  scale(x)≤s].

The algorithm parses the self-delimiting encoding, using only the lengths it determines, and compares the size parameter with sss.

This is the test the uniformity bridge uses to locate the end of an encoding that carries no end marker.

Formalization Note. The output is the one-bit list [decide (…)]. RAMPolyTimeComputable is the published WordRAM.Complexity notion (time c(n+1)dc(n+1)^dc(n+1)d at the canonical word width). vvv is unconstrained on strings that are not padded prefixes of encodings.

Retired. Superseded by TwoFoldOPI.uniformFamily_of_RAMSerializableF: uniformity is now reduced through RAM-serializability on raw prefixes (TwoFoldOPI.RAMSerializableF), where the constructor itself recognises when a zero-padded prefix is long enough. This removes the separate parser lemmas.

Preamble
import Mathlib
import Definitions.Def_TwoFoldOPI_Input
import Definitions.Def_WordRAM_Complexity_BitIO
Formal statement
namespace TwoFoldOPI

theorem encodeLengthDecider_RAM :
    ∃ (A : WordRAM.Complexity.Algorithm .restricted) (v : List Bool → List Bool),
      WordRAM.Complexity.RAMPolyTimeComputable A v ∧
      ∀ (x : Input) (s : ℕ), v ((x.encode ++ List.replicate s false).take s) =
        [decide (x.encode.length ≤ s ∧ x.scale ≤ s)] := by sorry

end TwoFoldOPI
Source
Ragavan, Shutty, Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability, arXiv:2610.00502 (version held), §7.3, Theorem 7.4, p.40 ("running in poly(m, q, log(1/ϵ)) time") and §5.2 "Computational conventions", p.26; the instance encoding is TwoFoldOPI.Input.encode.

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