Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Corollary 8, p. 8 (corrected: Z_L has 3·2^{L−1} words, not 2^L) — the Wielandt code is a maximal prefix code whose shortest synchronizing word has length between L² − L + 1 and L²

Proved
SyncPrefix.Huffman.wielandt_code

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

p2o-batch-pfp2ap2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1prefix-codessynchronizing-codeswielandt-automaton

For an integer L≥1L \ge 1L≥1 let

ZL=0{0,1}L−1∪1{0,1}LZ_L = 0\{0,1\}^{L-1} \cup 1\{0,1\}^{L}ZL​=0{0,1}L−1∪1{0,1}L

be the set of binary words of length LLL beginning with 000 and of length L+1L+1L+1 beginning with 111. Then

  1. ZLZ_LZL​ is a maximal prefix code;
  2. ZLZ_LZL​ has exactly 3⋅2L−13 \cdot 2^{L-1}3⋅2L−1 words;
  3. its shortest codewords have length LLL and its longest codewords have length L+1L + 1L+1;
  4. there is a word www of length at most L2L^2L2 with {0,1}∗w⊆ZL∗\{0,1\}^* w \subseteq Z_L^*{0,1}∗w⊆ZL∗​;
  5. every word www with {0,1}∗w⊆ZL∗\{0,1\}^* w \subseteq Z_L^*{0,1}∗w⊆ZL∗​ has length at least L2−L+1L^2 - L + 1L2−L+1.

The minimal automaton of ZL∗Z_L^*ZL∗​ is the Wielandt automaton with L+1L + 1L+1 states, and items 4 and 5 are the paper's "synchronizing word of length Θ((log⁡k)2)\Theta((\log k)^2)Θ((logk)2)" with L=log⁡kL = \log kL=logk. The code is used in the proof of Corollary 8 to make the alphabet binary.

Differences from the source:

  • correction: the proof takes Z = 0{0,1}^{log k−1} ∪ 1{0,1}^{log k} as the image of a bijection from an alphabet of size k = 2^{log k} → |Z_L| = 3·2^{L−1}; reason: for L = 1, Z_1 = {0, 10, 11} has 3 words, not k = 2, so no bijection from a 2-letter alphabet exists; the alphabet must be padded to 3·2^{L−1} letters instead.
  • reading: "a synchronizing word of length Θ((log k)²)" → the explicit bracket L² − L + 1 ≤ |w| ≤ L² for words w with {0,1}* w ⊆ Z_L*; reason: the lower end is the reset threshold n² − 3n + 3 of the Wielandt automaton ([1]) at n = L + 1, and the upper end makes the Θ explicit.
  • encoding: the letters 0, 1 and log k → false, true and L ≥ 1; reason: Lean convention.
Preamble
import Mathlib
import Definitions.Def_SyncPrefix_Huffman_Constructions
Formal statement
namespace SyncPrefix.Huffman

open Computability

/-- The Wielandt code (p. 8): for `L ≥ 1`, `Z_L = 0{0,1}^{L-1} ∪ 1{0,1}^{L}` is a maximal prefix
code with `3 · 2^{L-1}` words, of lengths `L` and `L + 1`, and the shortest word `w` with
`u w ∈ Z_L∗` for every word `u` has length between `L² − L + 1` and `L²`. -/
theorem wielandt_code (L : ℕ) (hL : 1 ≤ L) :
    IsMaximalPrefixCode (lang (wielandtCode L)) ∧
      (wielandtCode L).card = 3 * 2 ^ (L - 1) ∧
      IsLeast ((fun z : List Bool => z.length) '' (wielandtCode L : Set (List Bool))) L ∧
      IsGreatest ((fun z : List Bool => z.length) '' (wielandtCode L : Set (List Bool))) (L + 1) ∧
      (∃ w : List Bool, w.length ≤ L ^ 2 ∧ ∀ u : List Bool, u ++ w ∈ (lang (wielandtCode L))∗) ∧
      ∀ w : List Bool, (∀ u : List Bool, u ++ w ∈ (lang (wielandtCode L))∗) →
        L ^ 2 - L + 1 ≤ w.length := by sorry

end SyncPrefix.Huffman
Source
Ryzhikov & Szykuła, Finding Short Synchronizing Words for Prefix Codes, arXiv:1806.06299v1, p. 8, proof of Corollary 8 (second paragraph, the code Z)
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