Height- and length-controlled digital carry homotopies
DefinitionAT260939824_SafeDigitalCarriesarxiv-2609-39824-positive
For a base , the positive word predicate at height bound and displacement is generated by the empty word of displacement zero, the letter of displacement one, concatenation, conjugation which multiplies displacement by 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 . For and ,
where is the compressed base- 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.