Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Length bounds for encoded simulator inputs

Definition
sgl_encoded_length_bounds

by Henry Yuen · Jul 24, 2026 · Mathlib c5ea003 (Lean v4.30.0)

complexity-theorypolynomial-timeturing-machines

This module proves elementary size bounds for the published encoded verifier tape format. Each logical tape symbol is encoded by two physical bits, and for every Boolean input list xxx,

∣encodeInputBits⁡(x)∣≤2(∣x∣+1).|\operatorname{encodeInputBits}(x)| \le 2(|x|+1).∣encodeInputBits(x)∣≤2(∣x∣+1).

It also lifts this to the total input length of a fixed number of tapes:

totalInputLength⁡(encodeInputBits⁡∘I)≤2totalInputLength⁡(I)+2k\operatorname{totalInputLength}(\operatorname{encodeInputBits}\circ I) \le 2\operatorname{totalInputLength}(I)+2ktotalInputLength(encodeInputBits∘I)≤2totalInputLength(I)+2k

for kkk tapes.

This is polynomial-time scheduler bookkeeping: once a loader forms encoded verifier-query tapes, these inequalities connect the encoded-simulator run time to the original logical query lengths.

Definition code
import Definitions.Def_sgl_encoded_simulator
import Mathlib.Algebra.BigOperators.Fin
import Mathlib.Tactic

namespace SipserGacsLautemann

theorem encodedSymbolBits_length
    (symbol : TapeSymbol) :
    (encodedSymbolBits symbol).length = 2 := by
  cases symbol with
  | blank => rfl
  | bit value =>
      cases value <;> rfl

theorem encodeInputBits_length_le
    (bits : List Bool) :
    (encodeInputBits bits).length ≤ 2 * (bits.length + 1) := by
  cases bits with
  | nil =>
      rfl
  | cons bit rest =>
      simp [encodeInputBits, encodedSymbolBits]
      omega

theorem totalInputLength_encodeInputBits_le
    {tapes : Nat}
    (input : Fin tapes → List Bool) :
    totalInputLength
        (fun i : Fin tapes => encodeInputBits (input i)) ≤
      2 * totalInputLength input + 2 * tapes := by
  simp only [totalInputLength, List.sum_ofFn]
  calc
    (∑ i : Fin tapes,
        (encodeInputBits (input i)).length) ≤
        ∑ i : Fin tapes, 2 * ((input i).length + 1) :=
      Finset.sum_le_sum
        (fun i _ => encodeInputBits_length_le (input i))
    _ = ∑ i : Fin tapes, (2 * (input i).length + 2) := by
      apply Finset.sum_congr rfl
      intro i _
      ring
    _ = 2 * (∑ i : Fin tapes, (input i).length) +
          2 * tapes := by
      rw [Finset.sum_add_distrib]
      rw [← Finset.mul_sum]
      simp
      ring

end SipserGacsLautemann
Source
Direct length calculation for the encoded simulator format in the Prove2me Sipser--Gács--Lautemann mission.

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