Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Stable nonnegative unmarked runs lift through prime compression

Proved
Monodromy.Counter.Reversible.PrimeCompression.integer_internal_reaches

by Xiaoyang Liu · Nov 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

computabilitycovering-spacesmonodromy-computation

For arbitrary natural n,q,e, distinct-prime basis, source table with complementary same-register tests at shared sources and targets, and shift amounts restricted to ±1, choose a Boolean source-address marking and an invariant preserved by every successful source step. Suppose the invariant makes every register nonnegative. Any finite possibly empty integer source run from an invariant-satisfying state u to v, with a false mark at every departure address, induces a finite compressed-table run between the prime encodings of the configurations obtained by applying Int.toNat to their counters. Every compressed departure state avoids the marked retained source boundaries; no marking or halting assumption is imposed on v.

Statement dependencies: Monodromy.Counter.Reversible.Action.UnitShift, Monodromy.Counter.Reversible.Deterministic, Monodromy.Counter.Reversible.Edge, Monodromy.Counter.Reversible.PrimeCompression.InternalMarkedReaches, Monodromy.Counter.Reversible.PrimeCompression.encode, Monodromy.Counter.Reversible.PrimeCompression.toNatural, Monodromy.Counter.Reversible.Stable, Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.Table, Monodromy.Counter.Reversible.TargetCompatible, Monodromy.Counter.Reversible.step, Monodromy.PrimeCode.Basis.

Original proof dependencies: Monodromy.Counter.Reversible.Action.UnitShift, Monodromy.Counter.Reversible.Deterministic, Monodromy.Counter.Reversible.Edge, Monodromy.Counter.Reversible.PrimeCompression.InternalMarkedReaches, Monodromy.Counter.Reversible.PrimeCompression.InternalMarkedStep, Monodromy.Counter.Reversible.PrimeCompression.encode, Monodromy.Counter.Reversible.PrimeCompression.integer_unmarked_step, Monodromy.Counter.Reversible.PrimeCompression.size, Monodromy.Counter.Reversible.PrimeCompression.toNatural, Monodromy.Counter.Reversible.Stable, Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.Table, Monodromy.Counter.Reversible.TargetCompatible, Monodromy.Counter.Reversible.step, Monodromy.PrimeCode.Basis.

Statement elaboration dependencies: Monodromy.Counter.Reversible.Action.UnitShift, Monodromy.Counter.Reversible.Deterministic, Monodromy.Counter.Reversible.Edge, Monodromy.Counter.Reversible.PrimeCompression.InternalMarkedReaches, Monodromy.Counter.Reversible.PrimeCompression.encode, Monodromy.Counter.Reversible.PrimeCompression.toNatural, Monodromy.Counter.Reversible.Stable, Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.Table, Monodromy.Counter.Reversible.TargetCompatible, Monodromy.Counter.Reversible.step, Monodromy.PrimeCode.Basis.

Proof elaboration dependencies: Monodromy.Counter.Reversible.Action.UnitShift, Monodromy.Counter.Reversible.Deterministic, Monodromy.Counter.Reversible.Edge, Monodromy.Counter.Reversible.PrimeCompression.InternalMarkedReaches, Monodromy.Counter.Reversible.PrimeCompression.InternalMarkedStep, Monodromy.Counter.Reversible.PrimeCompression.encode, Monodromy.Counter.Reversible.PrimeCompression.integer_unmarked_step, Monodromy.Counter.Reversible.PrimeCompression.size, Monodromy.Counter.Reversible.PrimeCompression.toNatural, Monodromy.Counter.Reversible.Stable, Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.Table, Monodromy.Counter.Reversible.TargetCompatible, Monodromy.Counter.Reversible.step, Monodromy.PrimeCode.Basis.

Preamble
module
public import Definitions.Def_Monodromy_Counter
public import Lean.Elab.Tactic.Omega
public import Mathlib.Analysis.Analytic.Constructions
public import Mathlib.Analysis.Analytic.IsolatedZeros
public import Mathlib.Analysis.Analytic.Linear
public import Mathlib.Analysis.Calculus.DSlope
public import Mathlib.Analysis.Calculus.Deriv.Add
public import Mathlib.Analysis.Calculus.Deriv.Comp
public import Mathlib.Analysis.Calculus.Deriv.Mul
public import Mathlib.Analysis.Calculus.Deriv.Pow
public import Mathlib.Analysis.Complex.Basic
public import Mathlib.Analysis.Complex.CoveringMap
public import Mathlib.Analysis.Real.Pi.Bounds
public import Mathlib.Analysis.SpecialFunctions.Complex.Analytic
public import Mathlib.Analysis.SpecialFunctions.Complex.Circle
public import Mathlib.Computability.StateTransition
public import Mathlib.Computability.TuringMachine.PostTuringMachine
public import Mathlib.Data.Fin.Basic
public import Mathlib.Data.Fintype.Card
public import Mathlib.Data.Fintype.EquivFin
public import Mathlib.Data.Nat.Digits.Lemmas
public import Mathlib.Data.Nat.Factorization.Basic
public import Mathlib.Logic.Equiv.Fin.Basic
public import Mathlib.Logic.Equiv.Fin.Rotate
public import Mathlib.Logic.Function.Basic
public import Mathlib.Logic.Function.Conjugate
public import Mathlib.RingTheory.RootsOfUnity.Complex
public import Mathlib.Tactic.FieldSimp
public import Mathlib.Tactic.FinCases
public import Mathlib.Tactic.FunProp
public import Mathlib.Tactic.Linarith
public import Mathlib.Tactic.Ring
public import Mathlib.Topology.Homotopy.Lifting

@[expose] public section

open Monodromy
open Monodromy.Counter
open Monodromy.Counter.Reversible
open Monodromy.Counter.Reversible.PrimeCompression
variable {n q e : ℕ}

Formal statement
theorem Monodromy.Counter.Reversible.PrimeCompression.integer_internal_reaches (basis : PrimeCode.Basis n) (source : Table n q e)
    (deterministic : Deterministic source) (compatible : TargetCompatible source)
    (unit : ∀ edge, Action.UnitShift (source edge).action) (mark : Fin q → Bool)
    (valid : State n q → Prop) (stable : Stable source valid)
    (nonnegative : ∀ state, valid state → ∀ index, 0 ≤ state.2 index)
    {first last : State n q}
    (run : Relation.ReflTransGen (fun current next : State n q =>
      step source current = some next ∧ mark current.1 = false) first last)
    (first_valid : valid first) :
    InternalMarkedReaches basis source deterministic compatible mark
      (encode basis source deterministic compatible (toNatural first))
      (encode basis source deterministic compatible (toNatural last)) := by sorry
Source
Authoritative local working-tree snapshot SHA-256 e03ce2d08e07ee663140bec213fb21e995f44153a3c556c908fcf1c8d6fefe6c; repository https://github.com/ERHUTUZI123/monodromy. The remote Git base is incomplete and is not asserted to contain these declarations. src/Monodromy/Counter.lean (file SHA-256 40536289575067aae1ed4154805e219805a1c786ccfdfcbe632ea7478a40636a): Monodromy.Counter.Reversible.PrimeCompression.integer_internal_reaches at L8385-L8408 [UTF-8 438350:439891].
Read-back

What the Lean code literally says, in plain math · OpenAI Codex (independent agent)

Let n,q,e∈Nn,q,e\in\mathbb Nn,q,e∈N, let (pi)i<n(p_i)_{i<n}(pi​)i<n​ be an injective family of natural primes, and let PPP be an eee-edge table on qqq control positions and nnn integer registers. An edge is a source, a target, and either an unconditional register shift by an integer or a zero/nonzero test leaving all registers unchanged; a step chooses the least enabled edge at the current control. Assume distinct edges with a common source, and distinct edges with a common target, are in each case complementary tests on the same register; these are the two stated compatibility hypotheses. Put A(v)=∏i<npiviA(v)=\prod_{i<n}p_i^{v_i}A(v)=∏i<n​pivi​​ for natural register vectors. The encoding E(s)E(s)E(s) has counters (A(s.counters),0)(A(s.\mathrm{counters}),0)(A(s.counters),0) and control cP(s.pc)c_P(s.\mathrm{pc})cP​(s.pc). Here cPc_PcP​ is the retained control of the following finite two-counter table TTT: for each control with outgoing edges, take a source module RpiR_{p_i}Rpi​​ using the register of its least outgoing edge, reverse that module exactly when that edge is a shift by +1+1+1, and use the finish of remainder 000 as input in the reversed case and the usual input otherwise; for each target of a test edge, also take a reversed restoration module using its least incoming test's register; controls without outgoing edges are separate vertices. A shift module's output is glued to its source edge's target control; a test source's finish of remainder rrr is glued to the restoration input of an edge testing that register with Boolean flag (r≠0)(r\ne0)(r=0) and having that target; restoration outputs are glued to their target controls. Gluing replaces each linked exit by its designated entry and preserves the original module edges and their actions. The control cP(j)c_P(j)cP​(j) is the image of the source-module input for row jjj, or its separate stopped vertex. Suppose furthermore that every shift in PPP has amount +1+1+1 or −1-1−1 (tests impose no further condition), and let b:{0,…,q−1}→{false,true}b:\{0,\ldots,q-1\}\to\{\mathrm{false},\mathrm{true}\}b:{0,…,q−1}→{false,true} be any marking. Let VVV be any predicate on integer source states, preserved by every defined PPP step, such that V(j,z)V(j,z)V(j,z) implies zi≥0z_i\ge0zi​≥0 for every register iii. For integer states s,ts,ts,t, assume V(s)V(s)V(s) and a finite, possibly zero-length, chain from sss to ttt in which each transition is a defined PPP step and its source control jjj has b(j)=falseb(j)=\mathrm{false}b(j)=false. Then there is a finite, possibly zero-length, chain of defined TTT steps from E(ν(s))E(\nu(s))E(ν(s)) to E(ν(t))E(\nu(t))E(ν(t)) in which no step's source has control cP(j)c_P(j)cP​(j) with b(j)=trueb(j)=\mathrm{true}b(j)=true. Here ν(j,z)=(j,(max⁡(zi,0))i)\nu(j,z)=(j,(\max(z_i,0))_i)ν(j,z)=(j,(max(zi​,0))i​) converts each integer to its natural part; the invariant hypotheses ensure that no negative value occurs along the stated source run. The conclusion neither requires its endpoints to be marked nor forbids passing through unmarked source controls; a final endpoint may be marked. The two-integer-counter graph RpR_pRp​ has global vertices G0,G1,G2G_0,G_1,G_2G0​,G1​,G2​ and vertices Br,jB_{r,j}Br,j​ for 0≤r<p0\le r<p0≤r<p, 0≤j<80\le j<80≤j<8, with input G0G_0G0​ and finishes Br,7B_{r,7}Br,7​. Its global edges are G0→y=0B0,0G_0\xrightarrow{y=0}B_{0,0}G0​y=0​B0,0​, G1→y↦y+1G2G_1\xrightarrow{y\mapsto y+1}G_2G1​y↦y+1​G2​, G2→y≠0B0,0G_2\xrightarrow{y\ne0}B_{0,0}G2​y=0​B0,0​; for each rrr its other edges are Br,0→x=0Br,2B_{r,0}\xrightarrow{x=0}B_{r,2}Br,0​x=0​Br,2​, Br,0→x≠0Br,1B_{r,0}\xrightarrow{x\ne0}B_{r,1}Br,0​x=0​Br,1​, Br,1→x↦x−1NrB_{r,1}\xrightarrow{x\mapsto x-1}N_rBr,1​x↦x−1​Nr​, Br,2→x=0Br,3B_{r,2}\xrightarrow{x=0}B_{r,3}Br,2​x=0​Br,3​, Br,3→y=0Br,7B_{r,3}\xrightarrow{y=0}B_{r,7}Br,3​y=0​Br,7​, Br,3→y≠0Br,4B_{r,3}\xrightarrow{y\ne0}B_{r,4}Br,3​y=0​Br,4​, Br,4→y↦y−1Br,5B_{r,4}\xrightarrow{y\mapsto y-1}B_{r,5}Br,4​y↦y−1​Br,5​, Br,5→x↦x+1Br,6B_{r,5}\xrightarrow{x\mapsto x+1}B_{r,6}Br,5​x↦x+1​Br,6​ and Br,6→x≠0Br,3B_{r,6}\xrightarrow{x\ne0}B_{r,3}Br,6​x=0​Br,3​, where Nr=Br+1,0N_r=B_{r+1,0}Nr​=Br+1,0​ if r+1<pr+1<pr+1<p and Nr=G1N_r=G_1Nr​=G1​ otherwise. Tests leave the counters unchanged, shifts are unconditionally enabled, and a step takes the least enumerated enabled edge or is undefined if none is enabled.

Human review
  • Endorsed by marwahaha · Nov 6, 2026

  • Endorsed by Xiaoyang Liu · Nov 6, 2026

    Confirmed by the mission captain (proposal self-audit).

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