Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.3 — counting control sequences that reach a destination state

Proved
DelayedBCN.Controllability.numToState_eq_sum

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

boolean-control-networkcountingp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1state-controllability

Consider a delayed Boolean control network with delay length μ≥1\mu\ge1μ≥1 and transition-count matrix QQQ. Let aaa be an initial trajectory, bsb_sbs​ a destination state and Ξμbs\Xi^{b_s}_\muΞμbs​​ the set of trajectories whose current (last) state is bsb_sbs​. For every integer k>0k>0k>0, the number N2(k;a,bs)\mathbb N_2(k;a,b_s)N2​(k;a,bs​) of control sequences of length kkk that steer the network from aaa to x(k)=bsx(k)=b_sx(k)=bs​ satisfies

N2(k;a,bs)=∑b∈ΞμbsN1(k;a,b)=∑b∈ΞμbsbTQka.\mathbb N_2(k;a,b_s)=\sum_{b\in\Xi^{b_s}_\mu}\mathbb N_1(k;a,b)=\sum_{b\in\Xi^{b_s}_\mu} b^{\mathsf T}Q^k a .N2​(k;a,bs​)=b∈Ξμbs​​∑​N1​(k;a,b)=b∈Ξμbs​​∑​bTQka.

The formula transfers the counting results for trajectories to the counting of control sequences reaching a prescribed state.

Formalization Note Both equalities are stated. Ξμp\Xi^{p}_\muΞμp​ is defined as the trajectories whose last entry is ppp, as in eq. (4.3); the index formula (4.4) has a misprinted range and is not transcribed. k>0k>0k>0 follows the paper ("Fix an arbitrary integer k>0k>0k>0", p. 489).

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

/-- Theorem 4.3 (Lu et al. 2016, p. 489): for `k > 0`,
`ℕ₂(k; a, bs) = ∑_{b ∈ Ξ^{bs}_μ} ℕ₁(k; a, b) = ∑_{b ∈ Ξ^{bs}_μ} bᵀ Q^k a`. -/
theorem numToState_eq_sum {μ n m : ℕ} [NeZero μ] (F : Network μ n m)
    (a : Traj μ n) (bs : State n) (k : ℕ) (hk : 0 < k) :
    numToState F k a bs = ∑ b ∈ xiLast bs, numSteering F k a b ∧
      numToState F k a bs = ∑ b ∈ xiLast bs, (Q F ^ 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, p. 489, Theorem 4.3, Eq. (4.6)
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)).
  • aaa is a trajectory and bs∈Bnb_s\in\mathbb B^nbs​∈Bn is a state.
  • kkk is a natural number with k>0k>0k>0.

Claim. Both of the following equalities hold:

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

The symbols mean the following:

  • yUy_UyU​. For a control sequence 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)\mathbb N_2(k;a,b_s)N2​(k;a,bs​). The number of U∈(Bm)kU\in(\mathbb B^m)^kU∈(Bm)k for which the last entry of yU(k)y_U(k)yU​(k) equals bsb_sbs​.
  • Ξμbs\Xi^{b_s}_\muΞμbs​​. The set of trajectories whose last entry is bsb_sbs​.
  • N1(k;a,b)\mathbb N_1(k;a,b)N1​(k;a,b). The number of U∈(Bm)kU\in(\mathbb B^m)^kU∈(Bm)k with yU(k)=by_U(k)=byU​(k)=b.
  • 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} over the natural numbers, and QkQ^kQk is its kkk-th matrix power.

Degenerate cases.

  • k=0k=0k=0. Excluded by hypothesis.
  • n=0n=0n=0. There is exactly one state and one trajectory, so every term equals 2mk2^{mk}2mk.
  • m=0m=0m=0. Each count is 000 or 111.
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