Lemma 2 — earlier feasible completions avoid their cancellation snapshot
DisprovedBalasAdditive.Convergence.lemma_2Let and be generated solutions with and . Suppose that for every with , the originally formed improving set has been completely cancelled during the processing of . If a feasible binary assignment strictly contains and has cost below , then
The conclusion restricts better completions of an earlier solution to indices outside its cancellation snapshot.
Formalization Note The hypothesis covers every in the printed range, not merely ancestors of . The paper's (the cancellations made before is obtained) is read in a state that is either the current state of iteration (cancellations so far; this also covers an iteration that ends with a stop) or the successor state in which is obtained, whose records are exactly . Cancellations only grow and stay inside , so the second choice is the printed lemma and the first is an instance of it. is the stored snapshot from the moment was obtained, and the ceiling is . The state is reachable, and need not have been generated.
import Mathlib import Definitions.Def_BalasAdditive_Convergence_Algorithm set_option autoImplicit false
namespace BalasAdditive.Convergence
/-- Lemma 2, p. 532, equation (53). `σ` is a state of iteration `s + 1` (`u^s` is the
latest generated solution). The printed `C_p^{s+1}` is read in `τ`: either `τ = σ`
(the cancellations accumulated so far, which also covers an iteration that ends in a
stop), or `τ` is the successor of `σ` in which `u^{s+1}` is obtained, whose records are
exactly the cancellations made before `u^{s+1}` was obtained. -/
theorem lemma_2 {n m : ℕ} (P : Problem n m) (σ τ : State n)
(hr : Reachable P σ)
(hτ : τ = σ ∨ (Step P σ τ ∧ τ.history.length = σ.history.length + 1)) (k : ℕ)
(hk : k < σ.history.length - 1)
(hancestor : σ.J k ⊂ σ.latest)
(hcancel : ∀ p, k < p → p ≤ σ.history.length - 1 → σ.N p = τ.currentC p)
(J : Finset (Fin n)) (hfeas : P.lp.Feasible J)
(hstrict : σ.J k ⊂ J)
(hcost : (↑(P.lp.cost J) : WithTop ℝ) < ceiling P σ) :
Disjoint (J \ σ.J k) (σ.snapshotC k) := by sorry
end BalasAdditive.Convergence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.