Theorem 4.3 — counting control sequences that reach a destination state
ProvedDelayedBCN.Controllability.numToState_eq_sumConsider a delayed Boolean control network with delay length and transition-count matrix . Let be an initial trajectory, a destination state and the set of trajectories whose current (last) state is . For every integer , the number of control sequences of length that steer the network from to satisfies
The formula transfers the counting results for trajectories to the counting of control sequences reaching a prescribed state.
Formalization Note Both equalities are stated. is defined as the trajectories whose last entry is , as in eq. (4.3); the index formula (4.4) has a misprinted range and is not transcribed. follows the paper ("Fix an arbitrary integer ", p. 489).
import Mathlib import Definitions.Def_DelayedBCN_Controllability_Model import Definitions.Def_DelayedBCN_Controllability_Matrix
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
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 a trajectory and is a state.
- is a natural number with .
Claim. Both of the following equalities hold:
The symbols mean the following:
- . For a control sequence , and .
- . The number of for which the last entry of equals .
- . The set of trajectories whose last entry is .
- . The number of with .
- . over the natural numbers, and is its -th matrix power.
Degenerate cases.
- . Excluded by hypothesis.
- . There is exactly one state and one trajectory, so every term equals .
- . Each count is or .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.