AFTD Auto-Formalizing Theoretical Domains

has_orthant_diminishing_returns

def

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

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
See it in the graphDiscuss this resultChallenge it