Proposition 3.5 — the number of k-step control sequences avoiding C_t is an entry of (Q_{C_t})^k
ProvedDelayedBCN.Controllability.card_controls_avoiding_eq_zeroed_powConsider a delayed Boolean control network with trajectories of length , a set of forbidden trajectories and two trajectories . Let be the transition-count matrix and the matrix obtained from by substituting zeros in the rows and columns of the trajectories in . For every integer , the number of control sequences that steer the network from to with for satisfies
that is, it is the entry of in row and column .
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 is the paper's ("Fix an arbitrary integer ", p. 483); at the identity fails when . The entry is the matrix entry with rows and columns indexed by trajectories.
import Mathlib import Definitions.Def_DelayedBCN_Controllability_Model import Definitions.Def_DelayedBCN_Controllability_Matrix
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setup.
- ; are arbitrary natural numbers.
- is an arbitrary network. One step is .
- is any finite set of trajectories.
- are trajectories in .
- is a natural number with .
Claim.
The symbols mean the following:
- Left-hand side. is the number of control sequences that satisfy both of these, where and for :
- ;
- for all .
- . .
- . It equals except that whenever or .
- Right-hand side. The -th power of the natural-number matrix , read at row and column .
Degenerate cases.
- . Excluded by hypothesis.
- Endpoint in . If or , the left side is by definition, so the right side is asserted to be .
- Empty . Then and the count has no avoidance condition.
- . There is exactly one control sequence, so both sides are or .
- . There is exactly one trajectory, and the claim is about a matrix.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.