Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7, p. 7 — the composition of synchronizing complete codes is synchronizing, with shortest absorbing pair between mℓ and 2Mℓ + 2c

Proved
SyncPrefix.Huffman.theorem_7

by mikedeng1 · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

codescomposition-of-codesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1synchronizing-codes

Let YYY be a code over an alphabet ΣY\Sigma_YΣY​ and ZZZ a code over ΣZ\Sigma_ZΣZ​, both synchronizing complete codes (complete codes with an absorbing pair). Assume ZZZ is finite, let mmm and MMM be the lengths of a shortest and a longest codeword of ZZZ, and let β:ΣY→Z\beta : \Sigma_Y \to Zβ:ΣY​→Z be a bijection. Let ℓ\ellℓ and ccc be the lengths of shortest absorbing pairs of YYY and ZZZ. Then the composition X=Y∘βZX = Y \circ_\beta ZX=Y∘β​Z is a synchronizing complete code, and the length ℓX\ell_XℓX​ of a shortest absorbing pair of XXX satisfies

m ℓ≤ℓX≤2Mℓ+2c.m\,\ell \le \ell_X \le 2M\ell + 2c.mℓ≤ℓX​≤2Mℓ+2c.

The theorem says that composition changes the alphabet of a synchronizing code while preserving the length of a shortest absorbing pair up to the factors mmm and 2M2M2M.

Differences from the source:

  • encoding: codes over alphabets → codes over arbitrary types α, β; reason: the hypotheses force both to be finite (a finite complete code uses finitely many letters, and β is in bijection with Z), so no new instance arises.
Preamble
import Mathlib
import Definitions.Def_SyncPrefix_Huffman_Constructions
Formal statement
namespace SyncPrefix.Huffman

/-- Theorem 7 (p. 7): the composition `X = Y ∘ Z` of two synchronizing complete codes, `Z`
finite with shortest and longest codeword lengths `m` and `M`, is synchronizing, and its
shortest absorbing pair has length between `m ℓ` and `2 M ℓ + 2 c`, where `ℓ` and `c` are the
lengths of shortest absorbing pairs of `Y` and `Z`. -/
theorem theorem_7 {α β : Type} (Y : Language β) (Z : Language α)
    (hY : IsSyncCode Y) (hZ : IsSyncCode Z) (hZfin : Set.Finite (Z : Set (List α)))
    (e : β ≃ {z // z ∈ Z}) (m M : ℕ)
    (hm : IsLeast ((fun z : List α => z.length) '' (Z : Set (List α))) m)
    (hM : IsGreatest ((fun z : List α => z.length) '' (Z : Set (List α))) M) :
    IsSyncCode (compose Y Z e) ∧ m * absorbLength Y ≤ absorbLength (compose Y Z e) ∧
      absorbLength (compose Y Z e) ≤ 2 * M * absorbLength Y + 2 * absorbLength Z := by sorry

end SyncPrefix.Huffman
Source
Ryzhikov & Szykuła, Finding Short Synchronizing Words for Prefix Codes, arXiv:1806.06299v1, p. 7, Theorem 7
Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 24, 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