Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 (proof), p. 5 — the pipe automaton of a Set Cover instance is strongly acyclic with p² + 1 states, and its shortest synchronizing word has the minimum cover size as length

Proved
SyncPrefix.Huffman.theorem_2_reduction

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

p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reductionsset-coversynchronizing-automata

Let X={x1,…,xp}X = \{x_1, \dots, x_p\}X={x1​,…,xp​} and let C=(c1,…,cm)C = (c_1, \dots, c_m)C=(c1​,…,cm​) be a family of subsets of XXX that covers XXX. Let AAA be the pipe automaton of the instance: one letter per set, the states q1(j),…,qp(j)q^{(j)}_1, \dots, q^{(j)}_pq1(j)​,…,qp(j)​ for every point xjx_jxj​ and a state fff, where for 1≤i≤p−11 \le i \le p-11≤i≤p−1 the letter kkk maps qi(j)q^{(j)}_iqi(j)​ to fff if xj∈ckx_j \in c_kxj​∈ck​ and to qi+1(j)q^{(j)}_{i+1}qi+1(j)​ otherwise, and every letter maps qp(j)q^{(j)}_pqp(j)​ and fff to fff.

Then AAA has p2+1p^2 + 1p2+1 states and mmm letters, AAA is strongly acyclic and synchronizing, and

ℓ(A)=OPT(X,C),\ell(A) = \mathrm{OPT}(X, C),ℓ(A)=OPT(X,C),

the length of a shortest synchronizing word of AAA equals the minimum size of a subfamily of CCC covering XXX.

This is the gap-preserving reduction from Set Cover behind Theorem 2 and, through Lemma 5, behind Corollary 8.

Differences from the source:

  • reading: the Set Cover input is a family covering X (the proof: "such subfamily trivially exists if C covers X") → hypothesis I.Coverable; reason: without a cover the minimum is undefined.
  • encoding: states q^{(j)}i and f → Fin (p·p + 1), with q^{(j+1)}{i+1} ↦ j·p + i and f ↦ p²; reason: Lean convention, the same automaton.
Preamble
import Mathlib
import Definitions.Def_SyncPrefix_Huffman_Constructions
Formal statement
namespace SyncPrefix.Huffman

open SetCoverThreshold.SetCover

/-- Theorem 2's reduction (p. 5): for a Set Cover instance in which every point lies in some set,
the pipe automaton has `p² + 1` states and one letter per set, is strongly acyclic and
synchronizing, and the length of its shortest synchronizing word is the minimum size of a set
cover. -/
theorem theorem_2_reduction (I : SCInstance) (hI : I.Coverable) :
    (scAutomaton I).n = I.n ^ 2 + 1 ∧ (scAutomaton I).k = I.sets.length ∧
      StronglyAcyclic (scAutomaton I).δ ∧ IsSynchronizing (scAutomaton I).δ ∧
        syncLength (scAutomaton I).δ = minCover I := by sorry

end SyncPrefix.Huffman
Source
Ryzhikov & Szykuła, Finding Short Synchronizing Words for Prefix Codes, arXiv:1806.06299v1, p. 5, proof of Theorem 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