Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.1 — counting control sequences that reach a state while avoiding forbidden states

Proved
DelayedBCN.Controllability.numToStateAvoiding_eq_sum

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 delay length μ≥1\mu\ge1μ≥1 and transition-count matrix QQQ. Let CsC_sCs​ be a set of forbidden states, ΞCs\Xi^{C_s}ΞCs​ the set of trajectories containing at least one state of CsC_sCs​, and QCsQ_{C_s}QCs​​ the matrix obtained from QQQ by substituting zeros in the rows and columns of the trajectories in ΞCs\Xi^{C_s}ΞCs​. Let aaa be an initial trajectory, bsb_sbs​ a destination state and Ξμbs\Xi^{b_s}_\muΞμbs​​ the trajectories whose current state is bsb_sbs​. For every integer k>0k>0k>0, the number N2(k;a,bs,Cs)\mathbb N_2(k;a,b_s,C_s)N2​(k;a,bs​,Cs​) of control sequences of length kkk that steer the network from aaa to x(k)=bsx(k)=b_sx(k)=bs​ while avoiding CsC_sCs​ satisfies

N2(k;a,bs,Cs)=∑b∈ΞμbsN1(k;a,b,ΞCs)=∑b∈ΞμbsbT(QCs)ka.\mathbb N_2(k;a,b_s,C_s)=\sum_{b\in\Xi^{b_s}_\mu}\mathbb N_1(k;a,b,\Xi^{C_s})=\sum_{b\in\Xi^{b_s}_\mu} b^{\mathsf T}(Q_{C_s})^k a .N2​(k;a,bs​,Cs​)=b∈Ξμbs​​∑​N1​(k;a,b,ΞCs​)=b∈Ξμbs​​∑​bT(QCs​​)ka.

The result reduces state avoidance to trajectory avoidance, so that the forbidden-state problem is solved by the matrix algorithm of Proposition 3.5.

Formalization Note "Avoiding CsC_sCs​" is read as the theorem's middle term: no state x(i)x(i)x(i), i=1−μ,…,ki=1-\mu,\dots,ki=1−μ,…,k (the initial states included), belongs to CsC_sCs​, equivalently no trajectory y(0),…,y(k)y(0),\dots,y(k)y(0),…,y(k) lies in ΞCs\Xi^{C_s}ΞCs​. Both equalities are stated; k>0k>0k>0 as in the paper.

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

/-- Theorem 5.1 (Lu et al. 2016, pp. 489–490): for `k > 0`,
`ℕ₂(k; a, bs, Cs) = ∑_{b ∈ Ξ^{bs}_μ} ℕ₁(k; a, b, Ξ^{Cs}) = ∑_{b ∈ Ξ^{bs}_μ} bᵀ (Q_{Ξ^{Cs}})^k a`. -/
theorem numToStateAvoiding_eq_sum {μ n m : ℕ} [NeZero μ] (F : Network μ n m)
    (Cs : Finset (State n)) (a : Traj μ n) (bs : State n) (k : ℕ) (hk : 0 < k) :
    numToStateAvoiding F k a bs Cs = ∑ b ∈ xiLast bs, numAvoiding F k a b (xiForbidden Cs) ∧
      numToStateAvoiding F k a bs Cs =
        ∑ b ∈ xiLast bs, (QZeroed F (xiForbidden Cs) ^ k) b a := 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, pp. 489-490, Theorem 5.1, Eq. (5.1)
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)).
  • CsC_sCs​ is any finite set of states.
  • aaa is a trajectory and bsb_sbs​ is a state.
  • kkk is a natural number with k>0k>0k>0.

Claim. Both of the following equalities hold:

N2(k;a,bs,Cs)=∑b∈ΞμbsN1(k;a,b,ΞCs)andN2(k;a,bs,Cs)=∑b∈Ξμbs((QΞCs)k)(b,a).\mathbb N_2(k;a,b_s,C_s)=\sum_{b\in\Xi^{b_s}_\mu}\mathbb N_1(k;a,b,\Xi^{C_s})\qquad\text{and}\qquad\mathbb N_2(k;a,b_s,C_s)=\sum_{b\in\Xi^{b_s}_\mu}\big((Q_{\Xi^{C_s}})^k\big)(b,a).N2​(k;a,bs​,Cs​)=b∈Ξμbs​​∑​N1​(k;a,b,ΞCs​)andN2​(k;a,bs​,Cs​)=b∈Ξμbs​​∑​((QΞCs​​)k)(b,a).

The symbols mean the following:

  • yUy_UyU​. For U∈(Bm)kU\in(\mathbb B^m)^kU∈(Bm)k, yU(0)=ay_U(0)=ayU​(0)=a 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)).
  • N2(k;a,bs,Cs)\mathbb N_2(k;a,b_s,C_s)N2​(k;a,bs​,Cs​). The number of U∈(Bm)kU\in(\mathbb B^m)^kU∈(Bm)k that satisfy both of these:
    • the last entry of yU(k)y_U(k)yU​(k) is bsb_sbs​;
    • no entry, at any position, of any of yU(0),…,yU(k)y_U(0),\dots,y_U(k)yU​(0),…,yU​(k) lies in CsC_sCs​.
  • Ξμbs\Xi^{b_s}_\muΞμbs​​. The set of trajectories whose last entry is bsb_sbs​.
  • ΞCs\Xi^{C_s}ΞCs​. The set of trajectories having at least one entry in CsC_sCs​.
  • N1(k;a,b,ΞCs)\mathbb N_1(k;a,b,\Xi^{C_s})N1​(k;a,b,ΞCs​). The number of UUU with yU(k)=by_U(k)=byU​(k)=b and yU(i)∉ΞCsy_U(i)\notin\Xi^{C_s}yU​(i)∈/ΞCs​ for all i=0,…,ki=0,\dots,ki=0,…,k.
  • QQQ and QΞCsQ_{\Xi^{C_s}}QΞCs​​. Q(b,a)=#{u:σF(u,a)=b}Q(b,a)=\#\{u:\sigma_F(u,a)=b\}Q(b,a)=#{u:σF​(u,a)=b}, and QΞCsQ_{\Xi^{C_s}}QΞCs​​ is QQQ with every row and column indexed by a trajectory in ΞCs\Xi^{C_s}ΞCs​ set to zero. The power is taken over the natural numbers.

Degenerate cases.

  • k=0k=0k=0. Excluded by hypothesis.
  • Empty CsC_sCs​. ΞCs\Xi^{C_s}ΞCs​ is empty, and the statement reduces to the unrestricted counts with QkQ^kQk.
  • aaa or bsb_sbs​ forbidden. If aaa contains a state of CsC_sCs​, or bs∈Csb_s\in C_sbs​∈Cs​, all three expressions are asserted equal, and the left side is then 000.
  • CsC_sCs​ contains every state. Every trajectory is forbidden and all quantities are 000.
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