Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3.5 — the number of k-step control sequences avoiding C_t is an entry of (Q_{C_t})^k

Proved
DelayedBCN.Controllability.card_controls_avoiding_eq_zeroed_pow

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

boolean-control-networkcountingforbidden-statesp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider a delayed Boolean control network with trajectories of length μ≥1\mu\ge1μ≥1, a set CtC_tCt​ of forbidden trajectories and two trajectories ya,yby_a,y_bya​,yb​. Let QQQ be the transition-count matrix and QCtQ_{C_t}QCt​​ the matrix obtained from QQQ by substituting zeros in the rows and columns of the trajectories in CtC_tCt​. For every integer k>0k>0k>0, the number N1(k;ya,yb,Ct)\mathbb N_1(k;y_a,y_b,C_t)N1​(k;ya​,yb​,Ct​) of control sequences (u(0),…,u(k−1))(u(0),\dots,u(k-1))(u(0),…,u(k−1)) that steer the network from y(0)=yay(0)=y_ay(0)=ya​ to y(k)=yby(k)=y_by(k)=yb​ with y(i)∉Cty(i)\notin C_ty(i)∈/Ct​ for i=0,1,…,ki=0,1,\dots,ki=0,1,…,k satisfies

N1(k;ya,yb,Ct)=ybT (QCt)k ya,\mathbb N_1(k;y_a,y_b,C_t)=y_b^{\mathsf T}\,(Q_{C_t})^k\,y_a ,N1​(k;ya​,yb​,Ct​)=ybT​(QCt​​)kya​,

that is, it is the entry of (QCt)k(Q_{C_t})^k(QCt​​)k in row yby_byb​ and column yay_aya​.

The proposition turns the enumeration of admissible control sequences into matrix multiplication; Theorems 3.12 and 5.1 are built on it.

Formalization Note The restriction k>0k>0k>0 is the paper's ("Fix an arbitrary integer k>0k>0k>0", p. 483); at k=0k=0k=0 the identity fails when ya=yb∈Cty_a=y_b\in C_tya​=yb​∈Ct​. The entry ybTMyay_b^{\mathsf T}My_aybT​Mya​ is the matrix entry M(yb,ya)M(y_b,y_a)M(yb​,ya​) with rows and columns indexed by trajectories.

Preamble
import Mathlib
import Definitions.Def_DelayedBCN_Controllability_Model
import Definitions.Def_DelayedBCN_Controllability_Matrix
Formal statement
namespace DelayedBCN.Controllability

/-- Proposition 3.5 (Lu et al. 2016, p. 483): for `k > 0`, the number of control sequences of
length `k` that steer `ya` to `yb` while avoiding `Ct` is the `(yb, ya)` entry of `(Q_{C_t})^k`. -/
theorem card_controls_avoiding_eq_zeroed_pow {μ n m : ℕ} [NeZero μ] (F : Network μ n m)
    (Ct : Finset (Traj μ n)) (ya yb : Traj μ n) (k : ℕ) (hk : 0 < k) :
    numAvoiding F k ya yb Ct = (QZeroed F Ct ^ k) yb ya := by sorry

end DelayedBCN.Controllability
Source
Lu, Zhong, Ho, Tang & Cao, On Controllability of Delayed Boolean Control Networks, SIAM J. Control Optim. 54(2) 2016, p. 483, Proposition 3.5, Eq. (3.4)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setup.

  • μ≥1\mu\ge1μ≥1; n,mn,mn,m are arbitrary natural numbers.
  • F:Bm×(Bn)μ→BnF:\mathbb B^m\times(\mathbb B^n)^\mu\to\mathbb B^nF:Bm×(Bn)μ→Bn is an arbitrary network. One step is σF(u,X)=(X1,…,Xμ−1,F(u,X))\sigma_F(u,X)=(X_1,\dots,X_{\mu-1},F(u,X))σF​(u,X)=(X1​,…,Xμ−1​,F(u,X)).
  • CtC_tCt​ is any finite set of trajectories.
  • ya,yby_a,y_bya​,yb​ are trajectories in (Bn)μ(\mathbb B^n)^\mu(Bn)μ.
  • kkk is a natural number with k>0k>0k>0.

Claim.

N1(k;ya,yb,Ct)=((QCt)k)(yb,ya).\mathbb N_1(k;y_a,y_b,C_t)=\big((Q_{C_t})^k\big)(y_b,y_a).N1​(k;ya​,yb​,Ct​)=((QCt​​)k)(yb​,ya​).

The symbols mean the following:

  • Left-hand side. N1(k;ya,yb,Ct)\mathbb N_1(k;y_a,y_b,C_t)N1​(k;ya​,yb​,Ct​) is the number of control sequences U=(u(0),…,u(k−1))∈(Bm)kU=(u(0),\dots,u(k-1))\in(\mathbb B^m)^kU=(u(0),…,u(k−1))∈(Bm)k that satisfy both of these, where yU(0)=yay_U(0)=y_ayU​(0)=ya​ and yU(i+1)=σF(u(i),yU(i))y_U(i+1)=\sigma_F(u(i),y_U(i))yU​(i+1)=σF​(u(i),yU​(i)) for i<ki<ki<k:
    • yU(k)=yby_U(k)=y_byU​(k)=yb​;
    • yU(i)∉Cty_U(i)\notin C_tyU​(i)∈/Ct​ for all i=0,…,ki=0,\dots,ki=0,…,k.
  • QQQ. Q(b,a)=#{u∈Bm:σF(u,a)=b}Q(b,a)=\#\{u\in\mathbb B^m:\sigma_F(u,a)=b\}Q(b,a)=#{u∈Bm:σF​(u,a)=b}.
  • QCtQ_{C_t}QCt​​. It equals QQQ except that QCt(b,a)=0Q_{C_t}(b,a)=0QCt​​(b,a)=0 whenever b∈Ctb\in C_tb∈Ct​ or a∈Cta\in C_ta∈Ct​.
  • Right-hand side. The kkk-th power of the natural-number matrix QCtQ_{C_t}QCt​​, read at row yby_byb​ and column yay_aya​.

Degenerate cases.

  • k=0k=0k=0. Excluded by hypothesis.
  • Endpoint in CtC_tCt​. If ya∈Cty_a\in C_tya​∈Ct​ or yb∈Cty_b\in C_tyb​∈Ct​, the left side is 000 by definition, so the right side is asserted to be 000.
  • Empty CtC_tCt​. Then QCt=QQ_{C_t}=QQCt​​=Q and the count has no avoidance condition.
  • m=0m=0m=0. There is exactly one control sequence, so both sides are 000 or 111.
  • n=0n=0n=0. There is exactly one trajectory, and the claim is about a 1×11\times11×1 matrix.
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 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