Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

YAH rules, fixed suffix labels, and finite additive certificate data

Definition
CollatzWork_YAHFiniteObstructionStatement

by Sodelin · Sep 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

collatz-work-import

This interface fixes the eleven YAH mixed-base rewrite rules on \Sigma=\{f,t,0,1,2,\hat{},\},theircanonicalcontexts,natural−numberwordinterpretation,andthespecifiedtwo−statesuffixalgebra.Alabeledtokenisanelementof, their canonical contexts, natural-number word interpretation, and the specified two-state suffix algebra. A labeled token is an element of ,theircanonicalcontexts,natural−numberwordinterpretation,andthespecifiedtwo−statesuffixalgebra.AlabeledtokenisanelementofT=\Sigma\times{\mathrm{false},\mathrm{true}}.Italsodefineslocallegality,canonicallabeledextensions,andsymboloradjacent−paircountdifferences.Forafinitecertificate. It also defines local legality, canonical labeled extensions, and symbol or adjacent-pair count differences. For a finite certificate .Italsodefineslocallegality,canonicallabeledextensions,andsymboloradjacent−paircountdifferences.ForafinitecertificateCofpairsof pairsofpairs(a,r)\in\mathbb N\times\rho,anintegerfeaturedifference, an integer feature difference ,anintegerfeaturedifference\delta:\rho\times\varphi\to\mathbb Z,afinitefeaturelist, a finite feature list ,afinitefeaturelistF,andweights, and weights ,andweightsw:\varphi\to Minanintegermodulein an integer moduleinanintegermoduleM,andanarbitraryintegercoefficientfunction, and an arbitrary integer coefficient function ,andanarbitraryintegercoefficientfunctionc:\varphi\to\mathbb Z$, its central operations are

cC(e)=∑(a,r)∈Ca δ(r,e),Ew(c)=∑e∈Fc(e)w(e).c_C(e)=\sum_{(a,r)\in C}a\,\delta(r,e),\qquad E_w(c)=\sum_{e\in F}c(e)w(e).cC​(e)=(a,r)∈C∑​aδ(r,e),Ew​(c)=e∈F∑​c(e)w(e).

For an additive row gap g:ρ→Mg:\rho\to Mg:ρ→M, the weighted gap sum is ∑(a,r)∈Ca g(r)\sum_{(a,r)\in C}a\,g(r)∑(a,r)∈C​ag(r). These definitions provide a common statement language for the finite obstruction theorems; they contain no concrete cancellation certificate or assertion of termination. The source records the upstream YAH rule-file commit and hash.

Definition code
import Std
import Init.Grind.Ordered.Module
namespace CollatzWork.YAH

/-!
# Trusted statement layer for finite YAH obstruction certificates

This file fixes the exact eleven-rule mixed-base string-rewriting system used
by Yolcu--Aaronson--Heule (YAH), the project's two-state suffix algebra, and
the generic finite-certificate predicates.  It contains no concrete
cancellation certificate.

The intended scope is deliberately narrow: additive symbol or adjacent-edge
potentials for the exact data below.  Nothing in this file asserts termination
of the rewrite system or the Collatz conjecture.

Upstream provenance: `emreyolcu/rewriting-collatz` commit
`8a4dfda60f97a6d33ff0a24fdfa7a172d4bec340`, file `rules/collatz-T.srs`,
SHA-256 `e4777832e5cf8148a54299dffa48cf10254629680961006f2c15bcb6c55aa9d2`.
The ASCII source mapping is `a=f`, `b=t`, `c=^`, `d=$`, `e=0`, `f=1`,
`g=2`.
-/

universe u

open Lean.Grind

/-- The seven symbols of the exact YAH mixed binary/ternary system. -/
inductive Symbol where
  | f | t | d0 | d1 | d2 | hat | dollar
  deriving DecidableEq, BEq, Repr

/-- Stable names for the two dynamic and nine auxiliary YAH rules. -/
inductive RuleName where
  | Df | Dt
  | Xf0 | Xf1 | Xf2 | Xt0 | Xt1 | Xt2
  | Xhat0 | Xhat1 | Xhat2
  deriving DecidableEq, BEq, Repr

/-- One unlabelled string-rewriting rule. -/
structure Rule where
  name : RuleName
  lhs : List Symbol
  rhs : List Symbol
  dynamic : Bool
  deriving DecidableEq, BEq, Repr

/-- The exact eleven rules, with `true` marking the two Collatz-dynamic rows. -/
def rule : RuleName → Rule
  | .Df => ⟨.Df, [.f, .dollar], [.dollar], true⟩
  | .Dt => ⟨.Dt, [.t, .dollar], [.d2, .dollar], true⟩
  | .Xf0 => ⟨.Xf0, [.f, .d0], [.d0, .f], false⟩
  | .Xf1 => ⟨.Xf1, [.f, .d1], [.d0, .t], false⟩
  | .Xf2 => ⟨.Xf2, [.f, .d2], [.d1, .f], false⟩
  | .Xt0 => ⟨.Xt0, [.t, .d0], [.d1, .t], false⟩
  | .Xt1 => ⟨.Xt1, [.t, .d1], [.d2, .f], false⟩
  | .Xt2 => ⟨.Xt2, [.t, .d2], [.d2, .t], false⟩
  | .Xhat0 => ⟨.Xhat0, [.hat, .d0], [.hat, .t], false⟩
  | .Xhat1 => ⟨.Xhat1, [.hat, .d1], [.hat, .f, .f], false⟩
  | .Xhat2 => ⟨.Xhat2, [.hat, .d2], [.hat, .f, .t], false⟩

def allRuleNames : List RuleName :=
  [.Df, .Dt, .Xf0, .Xf1, .Xf2, .Xt0, .Xt1, .Xt2,
    .Xhat0, .Xhat1, .Xhat2]

def isDigit : Symbol → Bool
  | .f | .t | .d0 | .d1 | .d2 => true
  | .hat | .dollar => false

/-- Canonical syntactic words are exactly `^w$` with digit-only interior. -/
def canonical : List Symbol → Bool
  | .hat :: rest =>
      match rest.reverse with
      | .dollar :: middleRev => middleRev.all isDigit
      | _ => false
  | _ => false

/-- A chosen unlabelled rewrite occurrence, represented by its exterior. -/
structure UnlabelledInstance where
  ruleName : RuleName
  pre : List Symbol
  post : List Symbol
  deriving DecidableEq, BEq, Repr

def UnlabelledInstance.lhs (row : UnlabelledInstance) : List Symbol :=
  row.pre ++ (rule row.ruleName).lhs ++ row.post

def UnlabelledInstance.rhs (row : UnlabelledInstance) : List Symbol :=
  row.pre ++ (rule row.ruleName).rhs ++ row.post

/-- Executable legality check for a displayed canonical-context instance. -/
def validUnlabelledInstance (row : UnlabelledInstance) : Bool :=
  canonical row.lhs && canonical row.rhs

/-- Integer interpretation of a complete canonical YAH word. -/
def symbolValueStep (value : Nat) : Symbol → Nat
  | .f => 2 * value
  | .t => 2 * value + 1
  | .d0 => 3 * value
  | .d1 => 3 * value + 1
  | .d2 => 3 * value + 2
  | .hat | .dollar => value

def wordValue (word : List Symbol) : Nat :=
  word.foldl symbolValueStep 1

/-- The one-division shortcut map implemented by the two dynamic rules. -/
def shortcut (value : Nat) : Nat :=
  if value % 2 = 0 then value / 2 else (3 * value + 1) / 2

/-- Executable semantic check for a chosen canonical rewrite instance. -/
def validUnlabelledSemantics (row : UnlabelledInstance) : Bool :=
  if (rule row.ruleName).dynamic then
    wordValue row.rhs == shortcut (wordValue row.lhs)
  else
    wordValue row.rhs == wordValue row.lhs

/-- The fixed two-state suffix algebra used by `A-YAH-2STATE-001`. -/
def algebra : Symbol → Bool → Bool
  | .f, _ | .d0, _ | .hat, _ | .dollar, _ => false
  | .t, _ | .d2, _ => true
  | .d1, value => value

/-- Evaluate a word as a composition of unary algebra maps. -/
def evalWord : List Symbol → Bool → Bool
  | [], tail => tail
  | symbol :: rest, tail => algebra symbol (evalWord rest tail)

/-- A symbol paired with the value of its strict suffix. -/
abbrev Token := Symbol × Bool

/-- Deterministic right-to-left suffix labeling. -/
def labelWord : List Symbol → Bool → List Token
  | [], _ => []
  | symbol :: rest, tail =>
      (symbol, evalWord rest tail) :: labelWord rest tail

/-- One exact labeled row with at most one immediate neighbor on each side. -/
structure LabeledInstance where
  ruleName : RuleName
  tail : Bool
  left : Option Token
  right : Option Token
  deriving DecidableEq, BEq, Repr

def LabeledInstance.coreLhs (row : LabeledInstance) : List Token :=
  labelWord (rule row.ruleName).lhs row.tail

def LabeledInstance.coreRhs (row : LabeledInstance) : List Token :=
  labelWord (rule row.ruleName).rhs row.tail

def addContext (left : Option Token) (core : List Token)
    (right : Option Token) : List Token :=
  left.toList ++ core ++ right.toList

def LabeledInstance.lhs (row : LabeledInstance) : List Token :=
  addContext row.left row.coreLhs row.right

def LabeledInstance.rhs (row : LabeledInstance) : List Token :=
  addContext row.left row.coreRhs row.right

def validLeftContext (r : Rule) (tail : Bool) : Option Token → Bool
  | none => r.lhs.head? == some .hat
  | some (symbol, state) =>
      r.lhs.head? != some .hat &&
      (symbol == .hat || isDigit symbol) &&
      state == evalWord r.lhs tail

def validRightContext (r : Rule) (tail : Bool) : Option Token → Bool
  | none => r.lhs.getLast? == some .dollar && tail == false
  | some (symbol, state) =>
      r.lhs.getLast? != some .dollar &&
      ((isDigit symbol && algebra symbol state == tail) ||
        (symbol == .dollar && state == false && tail == false))

/-- Exact local-context legality for the fixed-terminal suffix labeling. -/
def validLabeledInstance (row : LabeledInstance) : Bool :=
  let r := rule row.ruleName
  evalWord r.lhs row.tail == evalWord r.rhs row.tail &&
  validLeftContext r row.tail row.left &&
  validRightContext r row.tail row.right

def labelsConsistent : List Token → Bool
  | [] | [_] => true
  | (_, leftState) :: (rightSymbol, rightState) :: rest =>
      leftState == algebra rightSymbol rightState &&
        labelsConsistent ((rightSymbol, rightState) :: rest)

/-- A full fixed-terminal canonical labeled word. -/
def canonicalLabeled (tokens : List Token) : Bool :=
  canonical (tokens.map Prod.fst) &&
    tokens.getLast? == some (.dollar, false) &&
    labelsConsistent tokens

/-- Deterministically embed a legal local labeled segment in a complete
fixed-terminal canonical word. -/
def canonicalExtension (tokens : List Token) : List Token :=
  let withLeft :=
    match tokens.head? with
    | some (.hat, _) => tokens
    | some (symbol, state) => (.hat, algebra symbol state) :: tokens
    | none => []
  match withLeft.getLast? with
  | some (.dollar, false) => withLeft
  | some (_, true) => withLeft ++ [(.t, false), (.dollar, false)]
  | some (_, false) => withLeft ++ [(.dollar, false)]
  | none => []

def allSymbols : List Symbol :=
  [.f, .t, .d0, .d1, .d2, .hat, .dollar]

def allTokens : List Token :=
  allSymbols.flatMap fun symbol => [(symbol, false), (symbol, true)]

def adjacentPairs {α : Type _} : List α → List (α × α)
  | [] => []
  | _ :: [] => []
  | first :: second :: rest =>
      (first, second) :: adjacentPairs (second :: rest)

def allTokenEdges : List (Token × Token) :=
  allTokens.flatMap fun left => allTokens.map fun right => (left, right)

def countDelta {α : Type _} [BEq α] (lhs rhs : List α) (feature : α) : Int :=
  Int.ofNat (lhs.count feature) - Int.ofNat (rhs.count feature)

def unlabelledEdgeDelta (row : UnlabelledInstance)
    (edge : Symbol × Symbol) : Int :=
  countDelta (adjacentPairs row.lhs) (adjacentPairs row.rhs) edge

def labeledSymbolDelta (row : LabeledInstance) (token : Token) : Int :=
  countDelta row.lhs row.rhs token

def labeledEdgeDelta (row : LabeledInstance) (edge : Token × Token) : Int :=
  countDelta (adjacentPairs row.lhs) (adjacentPairs row.rhs) edge

/-- Pointwise integer sum of a positive-multiplier row certificate. -/
def weightedCoefficient {ρ : Type _} {φ : Sort _} (certificate : List (Nat × ρ))
    (delta : ρ → φ → Int) (feature : φ) : Int :=
  certificate.foldr
    (fun entry total => Int.ofNat entry.1 * delta entry.2 feature + total) 0

/-- Weighted sum of row gaps in an abstract additive ordered target. -/
def weightedGapSum {ρ : Type _} {M : Type u} [NatModule M]
    (certificate : List (Nat × ρ)) (gap : ρ → M) : M :=
  certificate.foldr (fun entry total => entry.1 • gap entry.2 + total) 0

/-- Evaluation of a finite integer feature vector in an additive group. -/
def evalCoefficients {φ : Type _} {M : Type u} [IntModule M]
    (features : List φ) (weight : φ → M) (coeff : φ → Int) : M :=
  features.foldr (fun feature total => coeff feature • weight feature + total) 0

end CollatzWork.YAH
Source
https://github.com/Sodelin/Collatz-Conjecture-Work/blob/026aa4ad4be6453a005ab950b160a9f2204c5271/lean/CollatzWork/YAHFiniteObstructionStatement.lean#L1-L252

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