Theorem 7, p. 7 — the composition of synchronizing complete codes is synchronizing, with shortest absorbing pair between mℓ and 2Mℓ + 2c
ProvedSyncPrefix.Huffman.theorem_7codescomposition-of-codesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1synchronizing-codes
Let be a code over an alphabet and a code over , both synchronizing complete codes (complete codes with an absorbing pair). Assume is finite, let and be the lengths of a shortest and a longest codeword of , and let be a bijection. Let and be the lengths of shortest absorbing pairs of and . Then the composition is a synchronizing complete code, and the length of a shortest absorbing pair of satisfies
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 and .
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 withZ), 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.