Birkhoff cost selection
ProvedDerivativeChainPhaseLock.birkhoff_cost_selectioncovariancederivative-chainsfinite-history-lawsprefix-laws
For each natural number , write , with . Let , , , , . Assume
Then
Decompose the doubly stochastic matrix into a convex combination of permutation matrices. One permutation has cost no larger than the weighted average.
Formalization Note. Natural-number subtraction is truncated. Named functions, index embeddings and field projections use their exact imported definitions.
Preamble
import Mathlib set_option autoImplicit false namespace DerivativeChain end DerivativeChain namespace DerivativeChainContinuation end DerivativeChainContinuation namespace DerivativeChainFiniteHistory end DerivativeChainFiniteHistory namespace DerivativeChainPhaseLock end DerivativeChainPhaseLock namespace DerivativeChainPrefixLaws end DerivativeChainPrefixLaws namespace DerivativeChainPrivate end DerivativeChainPrivate set_option autoImplicit false set_option backward.isDefEq.respectTransparency false set_option maxHeartbeats 2000000 open scoped BigOperators open Matrix universe v open DerivativeChainPhaseLock
Formal statement
theorem DerivativeChainPhaseLock.birkhoff_cost_selection {ι : Type v} [Fintype ι] [DecidableEq ι]
(S : Matrix ι ι ℝ) (hS : S ∈ doublyStochastic ℝ ι) (c : ι → ι → ℝ) :
∃ σ : Equiv.Perm ι, (∑ i,c i (σ i)) ≤ ∑ i,∑ j,S i j*c i j := by sorrySource
New frozen formal source /Users/amal/.codex/worktrees/prove2me-sync-20261026/derivative-chain-prize/submission_sync/new_formal/phase_lock/BirkhoffCostSelection.lean, lines 11-41, SHA-256 a2f6359892d5400364cd29a8958d0d74baaf3997b29ce18a08afbb424f2f813a. The source manifest pins the author receipts and analytic provenance. This new code is not attributed to the older public checkpoint. Shared canonical history and prefix interfaces. The phase26 and prefix-core19 frozen author manifests supply exact proof receipts and source provenance; no extension or new global U is included.