Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.10 — a delayed BCN is trajectory controllable iff Q is irreducible

Proved
DelayedBCN.Controllability.trajControllable_iff_irreducible

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

boolean-control-networkcontrollabilityirreducible-matrixp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider a delayed Boolean control network (2.2) with nnn state nodes, mmm inputs, delay length μ≥1\mu\ge1μ≥1 and arbitrary update functions, and let QQQ be its transition-count matrix (Qb,aQ_{b,a}Qb,a​ = number of input values taking trajectory aaa to trajectory bbb in one step). Then

the network is trajectory controllable  ⟺  Q is irreducible.\text{the network is trajectory controllable}\iff Q \text{ is irreducible}.the network is trajectory controllable⟺Q is irreducible.

Trajectory controllability is Definition 3.1: for every initial trajectory X(0)X(0)X(0) and every trajectory XdX_dXd​ there are k≥1k\ge1k≥1 and a control sequence of length kkk with X(k)=XdX(k)=X_dX(k)=Xd​. Irreducibility is Definition 3.7, applied to QQQ with its entries viewed as real numbers.

The theorem replaces a search over control sequences of unbounded length by a finite matrix test.

Formalization Note Controllability is defined through the dynamics and control sequences, not through powers of QQQ. The step count in Definition 3.1 is k≥1k\ge1k≥1 (see the model file). No assumption on nnn, mmm or the update functions is made.

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

/-- Theorem 3.10 (Lu et al. 2016, p. 486): the delayed BCN is trajectory controllable
(Definition 3.1) if and only if `Q` is irreducible (Definition 3.7). -/
theorem trajControllable_iff_irreducible {μ n m : ℕ} [NeZero μ] (F : Network μ n m) :
    TrajControllable F ↔ IsIrreducibleMat ((Q F).map (fun x : ℕ => (x : ℝ))) := 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. 486, Theorem 3.10
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)).

Claim.

F is trajectory controllable  ⟺  Qˉ is irreducible,F\text{ is trajectory controllable}\iff \bar Q\text{ is irreducible},F is trajectory controllable⟺Qˉ​ is irreducible,

where Qˉ\bar QQˉ​ is the matrix 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} with its entries cast to real numbers.

Trajectory controllable. For every initial trajectory X0X^0X0 and every trajectory XdX^dXd there are some k≥1k\ge1k≥1 and some U∈(Bm)kU\in(\mathbb B^m)^kU∈(Bm)k with yU(k)=Xdy_U(k)=X^dyU​(k)=Xd. Here yU(0)=X0y_U(0)=X^0yU​(0)=X0 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)). The requirement k≥1k\ge1k≥1 applies even when Xd=X0X^d=X^0Xd=X0.

Irreducible. Let N=2μnN=2^{\mu n}N=2μn be the number of trajectories. Qˉ\bar QQˉ​ is irreducible if there is no bijection e:{0,…,N−1}→(Bn)μe:\{0,\dots,N-1\}\to(\mathbb B^n)^\mue:{0,…,N−1}→(Bn)μ together with an rrr, 1≤r≤N−11\le r\le N-11≤r≤N−1, such that Qˉ(ei,ej)=0\bar Q(e_i,e_j)=0Qˉ​(ei​,ej​)=0 for all i≥ri\ge ri≥r and j<rj<rj<r. Equivalently, there is no split of the trajectories into two nonempty parts SSS and TTT with Q(t,s)=0Q(t,s)=0Q(t,s)=0 for all t∈Tt\in Tt∈T and s∈Ss\in Ss∈S.

Degenerate cases.

  • n=0n=0n=0. There is exactly one trajectory, so Qˉ\bar QQˉ​ is 1×11\times11×1 and irreducible by definition. The statement asserts that FFF is then trajectory controllable, which holds because the unique trajectory is reached after one step.
  • m=0m=0m=0. Each trajectory has exactly one successor, and the statement applies unchanged.
  • Size. The index set is never empty, because N≥1N\ge1N≥1.
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