Prime compression turns a three-counter step into a first return
ProvedMonodromy.Counter.Compression.step_firstReturnFor every natural control size m and three-natural-counter program P, each successful source transition s→t becomes a first return from encode(s) to encode(t) in its two-counter compression. The encoding stores the source registers as and a zero workspace at a dispatch address. The return consists of one successful compiled step followed by a finite possibly empty chain whose departure addresses avoid all source dispatches.
Statement dependencies: Monodromy.Counter.Compression.FirstReturn, Monodromy.Counter.Compression.encode, Monodromy.Counter.Configuration, Monodromy.Counter.Program, Monodromy.Counter.step.
Original proof dependencies: Monodromy.Counter.Compression.FirstReturn, Monodromy.Counter.Compression.dec_succ_firstReturn, Monodromy.Counter.Compression.dec_zero_firstReturn, Monodromy.Counter.Compression.encode, Monodromy.Counter.Compression.inc_firstReturn, Monodromy.Counter.Configuration, Monodromy.Counter.Instruction, Monodromy.Counter.Program, Monodromy.Counter.step, Monodromy.Counter.step_dec_succ, Monodromy.Counter.step_dec_zero, Monodromy.Counter.step_inc.
Statement elaboration dependencies: Monodromy.Counter.Compression.FirstReturn, Monodromy.Counter.Compression.encode, Monodromy.Counter.Configuration, Monodromy.Counter.Program, Monodromy.Counter.step.
Proof elaboration dependencies: Monodromy.Counter.Compression.FirstReturn, Monodromy.Counter.Compression.dec_succ_firstReturn, Monodromy.Counter.Compression.dec_zero_firstReturn, Monodromy.Counter.Compression.encode, Monodromy.Counter.Compression.inc_firstReturn, Monodromy.Counter.Configuration, Monodromy.Counter.Instruction, Monodromy.Counter.Program, Monodromy.Counter.step, Monodromy.Counter.step_dec_succ, Monodromy.Counter.step_dec_zero, Monodromy.Counter.step_inc.
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.Compression
variable {m : ℕ}
theorem Monodromy.Counter.Compression.step_firstReturn (source : Program 3 m) {first last : Configuration 3 m}
(transition : step source first = some last) :
FirstReturn source (encode source first) (encode source last) := by sorry
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (independent agent)
For every natural , every natural-counter program with three registers and controls, and every pair of configurations , a defined source step implies a positive finite run of the specified two-counter program from to with no intermediate dispatch control. Source instructions increment a selected natural register and jump, or test it for zero and jump to the zero target while leaving it unchanged, or decrement a positive value and jump to the nonzero target, or halt. The encoding is . The controls of are one dispatch for each source row , plus an instruction-specific block: an increment of register uses a multiplication block with corresponding to , a decrement uses a probe block , and a halt uses an empty block. In , at phase test/decrement counter , sending zero to transfer and nonzero to phase ; phases increment counter and go to phase ; transfer tests/decrements , sending zero to finish and nonzero to restore; restore increments and returns to transfer; finish halts. The probe is the disjoint union of and a division block with consumption , transfer , restore , finish for each and a bump control: tests/decrements , with zero target and nonzero target if or bump otherwise; bump increments and goes to ; tests/decrements , with zero target and nonzero target ; increments and goes to ; each halts. Every division jump to for is redirected to phase of ; is the probe success and the multiplication finish is the probe failure. To form , multiplication-finish targets are redirected to the increment's next dispatch, probe-success targets to the decrement's nonzero dispatch, and probe-failure targets to its zero dispatch; other targets remain within their row's block. An increment dispatch tests/decrements scratch counter with both branches entering multiplication phase ; a decrement dispatch does the same with both branches entering consumption ; a halt dispatch halts. The asserted run means one defined step followed by a reflexive transitive chain of defined steps whose source controls are not any , ending at ; that latter chain may be empty. The boundary condition inspects only control, not the scratch value. All source counters may be zero, and if there are no source configurations satisfying the premise.
Confirmed by the mission captain (proposal self-audit).