Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Distinct guard stages exchange an enabled owner-port pair

Proved
Monodromy.ReversibleRouting.run_pair

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

computabilitycovering-spacesmonodromy-computation

Let q,e be natural with q+e nonzero, let T be a two-integer-counter table, and assign each edge an owner vertex. Assume ownership is injective within each guard class and distinct edges with the same owner have complementary tests of the same register. For any integer register vector v, enabled edge j, and duplicate-free list of guard stages, running the corresponding native routing stages exchanges the prepared owner(j) state and edge-port q+j state exactly when the guard of j occurs in the list; otherwise both states are fixed. Both conclusions retain v, and the list may be empty.

Statement dependencies: Monodromy.Counter.Reversible.Action.enabled, Monodromy.Counter.Reversible.Edge, Monodromy.Counter.Reversible.Table, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.ReversibleControl.Guard, Monodromy.ReversiblePorts.Matching, Monodromy.ReversiblePorts.actionGuard, Monodromy.ReversiblePorts.selected, Monodromy.ReversibleRouting.CompatibleOwner, Monodromy.ReversibleRouting.point, Monodromy.ReversibleRouting.run.

Original proof dependencies: Monodromy.Counter.Reversible.Action.enabled, Monodromy.Counter.Reversible.Edge, Monodromy.Counter.Reversible.Table, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.CoupledContinuation.Program.advance, Monodromy.ReversibleControl.Guard, Monodromy.ReversiblePorts.Matching, Monodromy.ReversiblePorts.actionGuard, Monodromy.ReversiblePorts.selected, Monodromy.ReversibleRouting.CompatibleOwner, Monodromy.ReversibleRouting.point, Monodromy.ReversibleRouting.route, Monodromy.ReversibleRouting.route_owner, Monodromy.ReversibleRouting.route_port, Monodromy.ReversibleRouting.run, Monodromy.ReversibleRouting.run_cons.

Statement elaboration dependencies: Monodromy.Counter.Reversible.Action.enabled, Monodromy.Counter.Reversible.Edge, Monodromy.Counter.Reversible.Table, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.ReversibleControl.Guard, Monodromy.ReversiblePorts.Matching, Monodromy.ReversiblePorts.actionGuard, Monodromy.ReversiblePorts.selected, Monodromy.ReversibleRouting.CompatibleOwner, Monodromy.ReversibleRouting.point, Monodromy.ReversibleRouting.run.

Proof elaboration dependencies: Monodromy.Counter.Reversible.Action.enabled, Monodromy.Counter.Reversible.Edge, Monodromy.Counter.Reversible.Table, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.CoupledContinuation.Program.advance, Monodromy.ReversibleControl.Guard, Monodromy.ReversiblePorts.Matching, Monodromy.ReversiblePorts.actionGuard, Monodromy.ReversiblePorts.selected, Monodromy.ReversibleRouting.CompatibleOwner, Monodromy.ReversibleRouting.point, Monodromy.ReversibleRouting.route, Monodromy.ReversibleRouting.route_owner, Monodromy.ReversibleRouting.route_port, Monodromy.ReversibleRouting.run, Monodromy.ReversibleRouting.run_cons.

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.ReversibleRouting
open CoupledContinuation Counter.Reversible ReversiblePorts
variable {q e : ℕ} [NeZero (q + e)]
variable (table : Table 2 q e) (owner : Fin e → Fin q)
  (matching : ∀ guard, Matching owner (selected table guard))

Formal statement
theorem Monodromy.ReversibleRouting.run_pair (compatible : CompatibleOwner table owner) (values : Fin 2 → ℤ)
    (edge : Fin e) (enabled : (table edge).action.enabled values)
    (stages : List ReversibleControl.Guard) (distinct : stages.Nodup) :
    (run table owner matching stages (point values (Fin.castAdd e (owner edge))) =
      if actionGuard (table edge).action ∈ stages then point values (Fin.natAdd q edge)
      else point values (Fin.castAdd e (owner edge))) ∧
    (run table owner matching stages (point values (Fin.natAdd q edge)) =
      if actionGuard (table edge).action ∈ stages then point values (Fin.castAdd e (owner edge))
      else point values (Fin.natAdd q edge)) := 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.ReversibleRouting.run_pair at L3241-L3270 [UTF-8 157427:159164].
Read-back

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

Write τ=2πi\tau=2\pi iτ=2πi. The memory space M\mathcal MM consists of triples (zL,zR,w)(z_L,z_R,w)(zL​,zR​,w) of complex numbers with zL,zR≠0z_L,z_R\ne0zL​,zR​=0, ezL=ezR=ee^{z_L}=e^{z_R}=eezL​=ezR​=e, and ew=zLzRe^w=z_Lz_Rew=zL​zR​; its integer-labelled point Φ(l,r,c)\Phi(l,r,c)Φ(l,r,c) is (1+τl,1+τr,log⁡(1+τl)+log⁡(1+τr)+τc)(1+\tau l,1+\tau r,\log(1+\tau l)+\log(1+\tau r)+\tau c)(1+τl,1+τr,log(1+τl)+log(1+τr)+τc), using the principal complex logarithm. A degree-ddd native program, for d>0d>0d>0, assigns a finite word and a Boolean stop flag to each j∈{0,…,d−1}j\in\{0,\ldots,d-1\}j∈{0,…,d−1}. Its letters are left shift, right shift, left zero probe, right zero probe, and control shift, each with a reversal flag. Their geometric drivers respectively use the left or right base loop t↦e1+2πitt\mapsto e^{1+2\pi it}t↦e1+2πit or t↦exp⁡(e2πit)t\mapsto\exp(e^{2\pi it})t↦exp(e2πit), or the control loop t↦e2πitt\mapsto e^{2\pi it}t↦e2πit, leaving other components constant; a reversal reverses these paths. From a memory, lower exponential path lifts start at zL,zRz_L,z_RzL​,zR​, and an upper exponential lift starts at www over the product of those lower lifts and the control path; the endpoint is the new memory. A word concatenates these drivers in list order, with the empty word idle. Selection uses rd=exp⁡((w−log⁡zL−log⁡zR)/d)r_d=\exp((w-\log z_L-\log z_R)/d)rd​=exp((w−logzL​−logzR​)/d): the values at roots ωj=e2πij/d\omega_j=e^{2\pi ij/d}ωj​=e2πij/d are selected by ∑jKd(ωj,rd)vj\sum_j K_d(\omega_j,r_d)v_j∑j​Kd​(ωj​,rd​)vj​, where Kd(r,z)K_d(r,z)Kd​(r,z) is the divided slope of z↦zdz\mapsto z^dz↦zd at (r,z)(r,z)(r,z), divided by its derivative at rrr, with the divided slope equal to the derivative when z=rz=rz=r. The same selector applied to the 0/10/10/1 stop flags is the halt signal; a program step is absent exactly when that signal equals 111, and otherwise is its routed advance. Its partial evaluation returns the final state whose step is absent, and is undefined if no such state is reached. For all natural q,eq,eq,e with q+e>0q+e>0q+e>0, take an edge table with qqq vertices and eee edges, each action either an integer shift of one of two integer registers or a zero/nonzero test leaving registers unchanged, and a map ooo assigning every edge to an owner vertex. Write gfg_fgf​ for an edge's guard: unconditional for a shift, or (tested register, zero flag) for a test; a guard is enabled on v∈Z2v\in\mathbb Z^2v∈Z2 when it is unconditional or its specified zero/nonzero test holds. Suppose that for each guard, distinct edges with that guard have distinct owners (the matching hypothesis), and that any distinct edges with the same owner have test actions on the same register with opposite flags (compatible ownership). A guard's routing program conditionally swaps every selected edge port q+fq+fq+f with its owner vertex o(f)o(f)o(f), using the permutation given by those disjoint pairs and leaving all other vertices/ports fixed. For any integer register tuple vvv, any edge f<ef<ef<e whose action is enabled on vvv, and any duplicate-free finite list GGG of guards, let runG\mathrm{run}_GrunG​ be the left-to-right composition of those guarded native routing advances, and write pv(j)=Φ(v0,v1,j)p_v(j)=\Phi(v_0,v_1,j)pv​(j)=Φ(v0​,v1​,j). Then runG(pv(o(f)))\mathrm{run}_G(p_v(o(f)))runG​(pv​(o(f))) is pv(q+f)p_v(q+f)pv​(q+f) if gf∈Gg_f\in Ggf​∈G, and pv(o(f))p_v(o(f))pv​(o(f)) otherwise; simultaneously runG(pv(q+f))\mathrm{run}_G(p_v(q+f))runG​(pv​(q+f)) is pv(o(f))p_v(o(f))pv​(o(f)) if gf∈Gg_f\in Ggf​∈G, and pv(q+f)p_v(q+f)pv​(q+f) otherwise. The empty list is permitted; the assertion requires an actual edge argument, so zero-edge cases are vacuous.

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