Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§5, pp. 7–8 (composition decoder) — substituting the tree of a finite maximal prefix code Z for the letters of a decoder gives a Huffman decoder for (Y ∘ Z)* with Θ(n_Y n_Z) states

Proved
SyncPrefix.Huffman.composition_decoder

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

composition-of-codeshuffman-codesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1prefix-codes

Let HYH_YHY​ be a complete automaton with nYn_YnY​ states over an alphabet ΣY\Sigma_YΣY​, let ZZZ be a finite maximal prefix code over a finite nonempty alphabet ΣZ\Sigma_ZΣZ​, with tree TZT_ZTZ​ of nZn_ZnZ​ vertices, and let β:ΣY→Z\beta : \Sigma_Y \to Zβ:ΣY​→Z be a bijection. Let HXH_XHX​ be the decoder obtained by hanging a copy of TZT_ZTZ​ from every state qqq of HYH_YHY​: the inner vertices are new states, and the leaf β(a)\beta(a)β(a) of the copy at qqq is merged with δY(q,a)\delta_Y(q, a)δY​(q,a). Then:

  1. the number NNN of states of HXH_XHX​ satisfies
∣ΣZ∣⋅N+nY=nY nZ,|\Sigma_Z|\cdot N + n_Y = n_Y\, n_Z,∣ΣZ​∣⋅N+nY​=nY​nZ​,

so N=nY(nZ−1)/∣ΣZ∣N = n_Y(n_Z - 1)/|\Sigma_Z|N=nY​(nZ​−1)/∣ΣZ​∣, which is Θ(nYnZ)\Theta(n_Y n_Z)Θ(nY​nZ​) for a fixed alphabet (for a binary ZZZ, N=nY(nZ−1)/2N = n_Y(n_Z-1)/2N=nY​(nZ​−1)/2); 2. HXH_XHX​ is strongly connected if HYH_YHY​ is, and HXH_XHX​ is a Huffman decoder if HYH_YHY​ is; 3. for every state rrr of HYH_YHY​, a word www over ΣZ\Sigma_ZΣZ​ maps rrr to itself in HXH_XHX​ if and only if w=β(y)w = \beta(y)w=β(y) for a word yyy over ΣY\Sigma_YΣY​ that maps rrr to itself in HYH_YHY​.

By item 3, if HYH_YHY​ recognizes Y∗Y^*Y∗ with rrr as initial and final state, then HXH_XHX​ recognizes β(Y∗)=(Y∘βZ)∗\beta(Y^*) = (Y \circ_\beta Z)^*β(Y∗)=(Y∘β​Z)∗. Item 3 is the decoder over the alphabet of ZZZ used in the proof of Corollary 8.

Differences from the source:

  • generalization: "a Huffman decoder with Θ(n_Y n_Z) states" → the exact count |Σ_Z|·N + n_Y = n_Y n_Z; reason: it gives Θ(n_Y n_Z) for every fixed alphabet Σ_Z, in particular the binary one of the application.
  • generalization: H_Y a Huffman decoder for a maximal prefix code Y → H_Y any complete automaton, with strong connectivity and the Huffman property each transferred, and item 3 for every state r; reason: specializes to the source's H_Y.
  • reading: "a Huffman decoder recognizing the star of X = Y ∘ Z" → item 3 (returns to r in H_X are the images of returns to r in H_Y); reason: H_Y recognizes Y* with r as initial and final state.
  • reading: Huffman decoder → strongly connected, with a state whose set of first-return words is finite; reason: the paper's setting for first-return codes (p. 3); the source's H_Y, a decoder recognizing Y*, is of this kind.
  • encoding: the alphabet Σ_Z → a finite nonempty type; reason: alphabets are finite and nonempty, and over the empty alphabet ∅ is a degenerate maximal prefix code.
Preamble
import Mathlib
import Definitions.Def_SyncPrefix_Huffman_Constructions
Formal statement
namespace SyncPrefix.Huffman

/-- The composition decoder (pp. 7–8). Let `δY` be a complete automaton over `β` and `Z` a finite
maximal prefix code over a finite nonempty alphabet `α`, with a bijection `e : β → Z`. The decoder obtained
by hanging a copy of the tree `T_Z` from every state:
(a) has `n_Y (n_Z − 1) / |α|` states, where `n_Y` is the number of states of `δY` and `n_Z` the
number of vertices of `T_Z`;
(b) is strongly connected if `δY` is, and is a Huffman decoder if `δY` is;
(c) for every state `r`, the words returning `r` to itself in the decoder are exactly the
substitutions `β(y)` of the words `y` returning `r` to itself in `δY` (so it recognizes the star
of `X = Y ∘ Z` when `δY` recognizes `Y∗`). -/
theorem composition_decoder {σ α β : Type} [Fintype σ] [DecidableEq σ] [Fintype α] [Nonempty α]
    [DecidableEq α] (δY : σ → β → σ) (Z : Finset (List α))
    (hZ : IsMaximalPrefixCode (lang Z)) (e : β ≃ {z // z ∈ Z}) :
    Fintype.card α * Fintype.card (DecoderState σ Z) + Fintype.card σ =
        Fintype.card σ * (allPrefixes Z).card ∧
      (StronglyConnected δY → StronglyConnected (composeDecoder δY Z e)) ∧
      (IsHuffmanDecoder δY → IsHuffmanDecoder (composeDecoder δY Z e)) ∧
      ∀ (r : σ) (w : List α), run (composeDecoder δY Z e) (rootState Z r) w = rootState Z r ↔
        ∃ y : List β, run δY r y = r ∧ w = subst e y := by sorry

end SyncPrefix.Huffman
Source
Ryzhikov & Szykuła, Finding Short Synchronizing Words for Prefix Codes, arXiv:1806.06299v1, pp. 7–8, §5 (the Huffman decoder of the composition Y ∘ Z, Figure 2)
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