Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Height- and length-controlled digital carry homotopies

Definition
AT260939824_SafeDigitalCarries

by username · Oct 19, 2026 · Mathlib c5ea003 (Lean v4.30.0)

arxiv-2609-39824-positive

For a base m∈Nm\in\mathbb Nm∈N, the positive word predicate at height bound KKK and displacement nnn is generated by the empty word of displacement zero, the letter aaa of displacement one, concatenation, conjugation w↦twt−1w\mapsto twt^{-1}w↦twt−1 which multiplies displacement by mmm and raises height by one, and enlargement of the height bound. A safe homotopy between such words uses presentation-cell moves in context, with every intermediate word retaining the same positive shape and length at most BBB. For m≥2m\ge2m≥2 and n<Rn<Rn<R,

Wm(n)a≃safeWm(n+1),K=⌊log⁡mR⌋,B=(m+1)(K+1)+m+3,W_m(n)a\simeq_{\rm safe}W_m(n+1),\qquad K=\lfloor\log_mR\rfloor,\quad B=(m+1)(K+1)+m+3,Wm​(n)a≃safe​Wm​(n+1),K=⌊logm​R⌋,B=(m+1)(K+1)+m+3,

where Wm(n)W_m(n)Wm​(n) is the compressed base-mmm word. This keeps the carry deformation within one finite carrier and one logarithmic length bound.

Definition code
import Definitions.Def_AT260939824_BoundedCarries
import Definitions.Def_AT260939824_CompressedWords
import Definitions.Def_AT260939824_IntervalCarriers
import Init
import Lean.Elab.Tactic.Omega
import Mathlib.Algebra.BigOperators.Group.List.Basic
import Mathlib.Algebra.Group.Conj
import Mathlib.Combinatorics.SimpleGraph.Maps
import Mathlib.Combinatorics.SimpleGraph.Walk.Maps
import Mathlib.Data.Finset.Prod
import Mathlib.Data.Int.Interval
import Mathlib.Data.List.Basic
import Mathlib.Data.Nat.Log
import Mathlib.Tactic.Positivity
import Mathlib.Tactic.Ring

set_option autoImplicit false

/-!
# Carry certificates retaining every vertex of the literal carrier

`PositiveBSWord` records the actual nonnegative digit-path shape, including
its displacement and maximum height. `SafeBSHomotopic` retains that shape
for every intermediate word, in addition to the logarithmic length budget.
-/

namespace AbelianTargets

inductive PositiveBSWord (m : ℕ) : ℕ → ℕ → List BSLetter → Prop
  | nil (K) : PositiveBSWord m K 0 []
  | a (K) : PositiveBSWord m K 1 [BSLetter.a]
  | append {K n q w z} : PositiveBSWord m K n w → PositiveBSWord m K q z →
      PositiveBSWord m K (n+q) (w++z)
  | conjugate {K n w} : PositiveBSWord m K n w →
      PositiveBSWord m (K+1) (m*n) (conjugateWord w)
  | mono {K L n w} : PositiveBSWord m K n w → K ≤ L → PositiveBSWord m L n w

theorem PositiveBSWord.aWord (m K n : ℕ) : PositiveBSWord m K n (aWord n) := by
  induction n with
  | zero => exact .nil K
  | succ n ih => simpa only [aWord_succ] using ih.append (.a K)

theorem compressedWord_positive (m : ℕ) (hm : 2 ≤ m) (n : ℕ) :
    PositiveBSWord m (Nat.log m n) n (compressedWord m hm n) := by
  induction n using Nat.strong_induction_on with
  | h n ih =>
    by_cases hn : n < m
    · rw [compressedWord_of_lt m hm hn]
      exact PositiveBSWord.aWord m _ n
    · have hq : n/m < n := Nat.div_lt_self (by omega) (by omega)
      have hlog : 1 ≤ Nat.log m n := by
        apply Nat.le_log_of_pow_le (by omega)
        simpa only [Nat.pow_one] using (show m ≤ n by omega)
      have hlogq : Nat.log m (n/m)+1 = Nat.log m n := by rw [Nat.log_div_base]; omega
      have h := (ih (n/m) hq).conjugate
      rw [hlogq] at h
      have h' := h.append (PositiveBSWord.aWord m (Nat.log m n) (n%m))
      have hnum : m*(n/m)+n%m = n := Nat.div_add_mod n m
      rw [hnum] at h'
      simpa only [compressedWord_conjugate m hm (show m ≤ n by omega)] using h'

inductive SafeBSHomotopic (m B K n : ℕ) : List BSLetter → List BSLetter → Prop
  | refl (w) (hlen : w.length ≤ B) (hshape : PositiveBSWord m K n w) :
      SafeBSHomotopic m B K n w w
  | cell {w z} (h : BSCellMove m w z) (p s : List BSLetter)
      (hw : (p++w++s).length ≤ B) (hz : (p++z++s).length ≤ B)
      (hsw : PositiveBSWord m K n (p++w++s))
      (hsz : PositiveBSWord m K n (p++z++s)) :
      SafeBSHomotopic m B K n (p++w++s) (p++z++s)
  | symm {w z} : SafeBSHomotopic m B K n w z → SafeBSHomotopic m B K n z w
  | trans {u v w} : SafeBSHomotopic m B K n u v → SafeBSHomotopic m B K n v w →
      SafeBSHomotopic m B K n u w



theorem SafeBSHomotopic.shapes {m B K n : ℕ} {w z : List BSLetter}
    (h : SafeBSHomotopic m B K n w z) :
    PositiveBSWord m K n w ∧ PositiveBSWord m K n z := by
  induction h with
  | refl w hl hs => exact ⟨hs,hs⟩
  | cell h p s hw hz hsw hsz => exact ⟨hsw,hsz⟩
  | symm h ih => exact ih.symm
  | trans h₁ h₂ ih₁ ih₂ => exact ⟨ih₁.1,ih₂.2⟩

theorem SafeBSHomotopic.mono {m B C K L n : ℕ} {w z : List BSLetter}
    (h : SafeBSHomotopic m B K n w z) (hBC : B ≤ C) (hKL : K ≤ L) :
    SafeBSHomotopic m C L n w z := by
  induction h with
  | refl w hl hs => exact .refl w (hl.trans hBC) (hs.mono hKL)
  | cell h p s hw hz hsw hsz =>
      exact .cell h p s (hw.trans hBC) (hz.trans hBC) (hsw.mono hKL) (hsz.mono hKL)
  | symm h ih => exact ih.symm
  | trans h₁ h₂ ih₁ ih₂ => exact ih₁.trans ih₂

theorem SafeBSHomotopic.of_eq {m B K n : ℕ} {w z : List BSLetter}
    (heq : w = z) (hw : w.length ≤ B) (hshape : PositiveBSWord m K n w) :
    SafeBSHomotopic m B K n w z := by
  subst z
  exact .refl _ hw hshape

theorem SafeBSHomotopic.conjugate {m B K n : ℕ} {w z : List BSLetter}
    (h : SafeBSHomotopic m B K n w z) :
    SafeBSHomotopic m (B+2) (K+1) (m*n) (conjugateWord w) (conjugateWord z) := by
  induction h with
  | refl w hl hs =>
      exact .refl _ (by simp only [conjugateWord, List.length_append,
        List.length_cons,List.length_nil]; omega) hs.conjugate
  | @cell w₀ z₀ h p s hw hz hsw hsz =>
      have hsw' : PositiveBSWord m (K+1) (m*n)
          (([BSLetter.t]++p)++w₀++(s++[BSLetter.tInv])) := by
        simpa only [conjugateWord,List.append_assoc] using hsw.conjugate
      have hsz' : PositiveBSWord m (K+1) (m*n)
          (([BSLetter.t]++p)++z₀++(s++[BSLetter.tInv])) := by
        simpa only [conjugateWord,List.append_assoc] using hsz.conjugate
      have h' := SafeBSHomotopic.cell (B := B+2) h ([BSLetter.t]++p) (s++[BSLetter.tInv])
        (by simp only [List.length_append,List.length_cons,List.length_nil] at hw ⊢; omega)
        (by simp only [List.length_append,List.length_cons,List.length_nil] at hz ⊢; omega) hsw' hsz'
      simpa only [conjugateWord,List.append_assoc] using h'
  | symm h ih => exact ih.symm
  | trans h₁ h₂ ih₁ ih₂ => exact ih₁.trans ih₂

theorem compressedWord_safe_carry (m : ℕ) (hm : 2 ≤ m) (n : ℕ) :
    SafeBSHomotopic m (carryLengthBound m n) (Nat.log m (n+1)) (n+1)
      (compressedWord m hm n ++ [BSLetter.a]) (compressedWord m hm (n+1)) := by
  induction n using Nat.strong_induction_on with
  | h n ih =>
    have hlen := compressedWord_append_a_length_le m hm n
    have hshape : PositiveBSWord m (Nat.log m (n+1)) (n+1)
        (compressedWord m hm n ++ [BSLetter.a]) :=
      ((compressedWord_positive m hm n).mono
        (Nat.log_mono_right (show n ≤ n+1 by omega))).append (.a _)
    by_cases hn : n < m
    · by_cases hn' : n+1 < m
      · apply SafeBSHomotopic.of_eq _ hlen hshape
        rw [compressedWord_of_lt m hm hn, compressedWord_of_lt m hm hn']
        exact (aWord_succ n).symm
      · have hnm : n+1 = m := by omega
        have hleft : compressedWord m hm n ++ [BSLetter.a] = aWord m := by
          rw [compressedWord_of_lt m hm hn]
          change aWord n ++ [BSLetter.a] = aWord m
          rw [← aWord_succ n, hnm]
        have hright : compressedWord m hm (n+1) = [BSLetter.t,BSLetter.a,BSLetter.tInv] := by
          rw [hnm, compressedWord_conjugate m hm le_rfl]
          rw [Nat.div_self (by omega), Nat.mod_self, compressedWord_of_lt m hm (show 1 < m by omega)]
          simp [conjugateWord, aWord]
        have hsleft : PositiveBSWord m (Nat.log m (n+1)) (n+1) (aWord m) := by
          simpa only [hleft] using hshape
        have hsright : PositiveBSWord m (Nat.log m (n+1)) (n+1)
            [BSLetter.t,BSLetter.a,BSLetter.tInv] := by
          simpa only [hright] using compressedWord_positive m hm (n+1)
        rw [hleft,hright]
        simpa only [List.nil_append,List.append_nil] using
          SafeBSHomotopic.cell (B := carryLengthBound m n)
            (BSCellMove.symm (BSCellMove.relation (m := m))) [] []
            (by simpa [hleft] using hlen)
            (by simp only [List.nil_append,List.append_nil,List.length_cons,List.length_nil];
                dsimp [carryLengthBound]; omega)
            (by simpa only [List.nil_append,List.append_nil] using hsleft)
            (by simpa only [List.nil_append,List.append_nil] using hsright)
    · by_cases hrem : n%m+1 < m
      · obtain ⟨hquot,hmod⟩ := quotient_remainder_succ_no_carry hm hrem
        apply SafeBSHomotopic.of_eq _ hlen hshape
        rw [compressedWord_conjugate m hm (n := n) (by omega),
          compressedWord_conjugate m hm (n := n+1) (by omega), hquot,hmod,aWord_succ]
        simp only [List.append_assoc]
      · have hrem' : n%m+1 = m := by
          have := Nat.mod_lt n (show 0 < m by omega)
          omega
        obtain ⟨hnum,hquot,hmod⟩ := quotient_remainder_succ_carry hm hrem'
        let q := n/m
        let w := compressedWord m hm q
        let B := carryLengthBound m n
        let C := (m+1)*(Nat.log m (q+1)+1)
        let K := Nat.log m (n+1)
        have hq : q < n := Nat.div_lt_self (by omega) (by omega)
        have hw : w.length ≤ C := compressedWord_interval_uniform_length m hm (q+1) q (by omega)
        have hlog : K = Nat.log m (q+1)+1 := by
          dsimp [K]
          rw [hnum,Nat.mul_comm]
          exact Nat.log_mul_base (b := m) (n := q+1) (by omega) (Nat.succ_ne_zero q)
        have hK : 1 ≤ K := by omega
        have hB : B = C+(m+1)+m+3 := by
          dsimp [B,C,carryLengthBound]
          change (m+1)*(K+1)+m+3 = _
          rw [hlog]
          ring
        have hnum' : m*(q+1) = n+1 := hnum.symm
        have hleft : compressedWord m hm n ++ [BSLetter.a] = conjugateWord w ++ aWord m := by
          rw [compressedWord_conjugate m hm (by omega),List.append_assoc,← aWord_succ,hrem']
        have hright : compressedWord m hm (n+1) = conjugateWord (compressedWord m hm (q+1)) := by
          rw [compressedWord_conjugate m hm (by omega),hquot,hmod]
          simp only [aWord,List.replicate_zero,List.append_nil]
          rfl
        have hwshape : PositiveBSWord m (Nat.log m (q+1)) q w :=
          (compressedWord_positive m hm q).mono (Nat.log_mono_right (show q ≤ q+1 by omega))
        have hconj : PositiveBSWord m K (m*q) (conjugateWord w) := by
          rw [hlog]
          exact hwshape.conjugate
        have htail : PositiveBSWord m K m [BSLetter.t,BSLetter.a,BSLetter.tInv] := by
          have h := (PositiveBSWord.a (m := m) 0).conjugate.mono hK
          simpa [conjugateWord] using h
        have hstart : PositiveBSWord m K (n+1) (conjugateWord w ++ aWord m) := by
          have h := hconj.append (PositiveBSWord.aWord m K m)
          have heq : m*q+m = n+1 := by simpa only [Nat.mul_add,Nat.mul_one] using hnum'
          simpa only [heq] using h
        let expanded := [BSLetter.t]++w++[BSLetter.tInv,BSLetter.t,BSLetter.a,BSLetter.tInv]
        have hexpanded : PositiveBSWord m K (n+1) expanded := by
          have h := hconj.append htail
          have heq : m*q+m = n+1 := by simpa only [Nat.mul_add,Nat.mul_one] using hnum'
          simpa only [heq,conjugateWord,expanded,List.append_assoc,List.cons_append,List.nil_append] using h
        have hmiddle : PositiveBSWord m K (n+1) (conjugateWord (w++[BSLetter.a])) := by
          have h := (hwshape.append (.a _)).conjugate
          rw [← hlog,hnum'] at h
          exact h
        rw [hleft,hright]
        have h₁ : SafeBSHomotopic m B K (n+1) (conjugateWord w ++ aWord m) expanded := by
          have h := SafeBSHomotopic.cell (B := B) (BSCellMove.symm (BSCellMove.relation (m := m)))
            ([BSLetter.t]++w++[BSLetter.tInv]) []
            (by simp only [List.length_append,List.length_cons,List.length_nil,aWord,List.length_replicate];
                rw [hB]; omega)
            (by simp only [List.length_append,List.length_cons,List.length_nil]; rw [hB]; omega)
            (by simpa only [conjugateWord,List.append_nil] using hstart)
            (by simpa only [expanded,List.append_nil,List.append_assoc,List.cons_append,List.nil_append] using hexpanded)
          simpa only [conjugateWord,expanded,List.append_assoc,List.append_nil,List.cons_append,List.nil_append] using h
        have h₂ : SafeBSHomotopic m B K (n+1) expanded (conjugateWord (w++[BSLetter.a])) := by
          have h := SafeBSHomotopic.cell (B := B) (BSCellMove.cancelDownUp (m := m))
            ([BSLetter.t]++w) [BSLetter.a,BSLetter.tInv]
            (by simp only [List.length_append,List.length_cons,List.length_nil]; rw [hB]; omega)
            (by simp only [List.length_append,List.length_cons,List.length_nil]; rw [hB]; omega)
            (by simpa only [expanded,List.append_assoc,List.cons_append,List.nil_append] using hexpanded)
            (by simpa only [conjugateWord,List.append_assoc,List.cons_append,List.nil_append] using hmiddle)
          simpa only [conjugateWord,expanded,List.append_assoc,List.cons_append,List.nil_append] using h
        have h₃ : SafeBSHomotopic m B K (n+1) (conjugateWord (w++[BSLetter.a]))
            (conjugateWord (compressedWord m hm (q+1))) := by
          have h := (ih q hq).conjugate
          have hbound : carryLengthBound m q+2 ≤ B := by
            dsimp [carryLengthBound]
            change C+m+3+2 ≤ B
            rw [hB]
            omega
          rw [← hlog,hnum'] at h
          exact h.mono hbound le_rfl
        exact h₁.trans (h₂.trans h₃)

theorem compressedWord_interval_safe_carry (m : ℕ) (hm : 2 ≤ m)
    (R n : ℕ) (hn : n < R) :
    SafeBSHomotopic m ((m+1)*(Nat.log m R+1)+m+3) (Nat.log m R) (n+1)
      (compressedWord m hm n ++ [BSLetter.a]) (compressedWord m hm (n+1)) := by
  have hlog := Nat.log_mono_right (b := m) (show n+1 ≤ R by omega)
  apply (compressedWord_safe_carry m hm n).mono _ hlog
  dsimp [carryLengthBound]
  exact Nat.add_le_add_right (Nat.add_le_add_right
    (Nat.mul_le_mul_left _ (Nat.add_le_add_right hlog 1)) m) 3

end AbelianTargets
Source
Ruijun Wang, Continuous graph homomorphisms of higher dimensional abelian group actions, arXiv:2609.39824v1 (30 September 2026), Sections 2–7, supporting construction for Theorem 1.4 and Proposition 7.1; https://arxiv.org/html/2609.39824v1. Formalization-specific infrastructure in the import closure; individual helper assertions are not represented as separately numbered paper theorems. Original Lean module AbelianTargets/SafeDigitalCarries.lean, selected declaration lines 14-21, 23-26, 28-45, 47-57, 67-74, 76-84, 86-90, 92-111, 113-234, 236-244; SHA-256 3b342b8b5d15f028060791d6ae3c370ef0c67710ca4bf6725b2b40f4328e79a2. Selected spans are from the final generated manifest. The original source snapshot is local; no public repository URL or commit was available.

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