Submodularity of the explicit separating function
ProvedQAlgorithms.Papers.Independent.Intake100.P66.separatingF_submodularprove2quantum
Fix an integer , let and be disjoint, and set . For and , define
In the column order , the tables are
The only nonzero values are and , on those exact subsets of .
Then is submodular:
This supplies a separating set function for the independence argument; monotonicity and entropic realizability are not asserted.
Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intake100_P66
Formal statement
noncomputable section
namespace QAlgorithms.Papers.Independent.Intake100.P66
open scoped BigOperators
open QAlgorithms (IsDensityMatrix vnEntropy)
attribute [local instance] Classical.propDecidable Classical.decEq
/-- PDF pp.7--8, Proposition 3: the exact table (28)--(32) is submodular. -/
theorem separatingF_submodular (n : ℕ) (hn : 2 ≤ n) :
IsSubmodular (separatingF n) := by sorry
end QAlgorithms.Papers.Independent.Intake100.P66
end
Source
Infinitely many constrained inequalities for the von Neumann entropy, arXiv:1107.0624v1, PDF p. 7, Proposition 3, §IV: submodularity of the explicit function f
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every natural number , let , with distinct labels. For , put , , and define
where equals when holds and otherwise, and
Then, for every pair of subsets , including empty subsets,
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.