has_orthant_diminishing_returns
A function f : (Fin n → Option (Fin k)) → ℝ has orthant diminishing returns if for all x ≤ y, unassigned e in y, and label i, f (y + i 1_e) - f y ≤ f (x + i 1_e) - f x.
Statement
def has_orthant_diminishing_returns {n k : ℕ} (f : (Fin n → Option (Fin k)) → ℝ) : Prop
- Defined in
- arXiv:2610.26677, Eq. (2)
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Built on 1
- k_submod_leComponentwise partial order on assignments Fin n → Option (Fin k), where x ≤ y if for every element e, x e = none or x e = y e.
- Used by 4
- k_submodular_of_monotone_of_orthant_diminishing_returnsA monotone function on assignments Fin n → Option (Fin k) that satisfies orthant diminishing returns is k-submodular.
- not_k_submod_hidden_fn_orthant_diminishing_returnsThe statement
k_submod_hidden_fn_orthant_diminishing_returnsis false: The definitionis_k_submod_kernellacks… - k_submod_c1_hidden_fn_propertiesFor all natural numbers n > 0 and k ≥ 2, every hidden label assignment σ : Fin n → Fin k, and every function H : ℝ → ℝ → ℝ satisfying…
- k_submod_c1_hidden_fn_orthant_diminishing_returnsFor all natural numbers n > 0 and k ≥ 2, every hidden assignment σ : Fin n → Fin k, and every function H : ℝ → ℝ → ℝ satisfying…
Read back from the Lean
For a given function f : (Fin n → Option (Fin k)) → ℝ, the predicate has_orthant_diminishing_returns f asserts that: for all x, y : Fin n → Option (Fin k), every element e : Fin n, and every label i : Fin k, if x is less than or equal to y under k_submod_le (meaning for every coordinate e', either x e' = none or x e' = y e') and y e = none (which also implies x e = none), then the marginal return of updating e to some i in y is less than or equal to the marginal return of updating e to some i in x: f (Function.update y e (some i)) - f y ≤ f (Function.update x e (some i)) - f x.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Orthant diminishing returns (orthant submodularity) for a function on assignments. -/ def has_orthant_diminishing_returns {n k : ℕ} (f : (Fin n → Option (Fin k)) → ℝ) : Prop := ∀ (x y : Fin n → Option (Fin k)) (e : Fin n) (i : Fin k), k_submod_le x y → y e = none → f (Function.update y e (some i)) - f y ≤ f (Function.update x e (some i)) - f x