k_submod_c1_hidden_fn_properties
For all natural numbers n > 0 and k ≥ 2, every hidden label assignment σ : Fin n → Fin k, and every function H : ℝ → ℝ → ℝ satisfying is_c1_k_submod_kernel H, the normalized hidden-label function f = k_submod_hidden_fn H σ satisfies: (1) f x ≥ 0 for all x : Fin n → Option (Fin k); (2) is_k_submod_monotone f; (3) is_k_submodular f; (4) f (fun _ => none) = 0; (5) f x ≤ 1 for all x : Fin n → Option (Fin k); and (6) f (fun e => some (σ e)) = 1.
Statement
theorem k_submod_c1_hidden_fn_properties {n k : ℕ} (hn : 0 < n) (hk : 2 ≤ k) (σ : Fin n → Fin k) (H : ℝ → ℝ → ℝ) (hH : is_c1_k_submod_kernel H) : let f := k_submod_hidden_fn H σ (∀ x, 0 ≤ f x) ∧ is_k_submod_monotone f ∧ is_k_submodular f ∧ f (fun _ => none) = 0 ∧ (∀ x, f x ≤ 1) ∧ f (fun e => some (σ e)) = 1
- Formalizes
- arXiv:2610.26677 Lemma 2.2 -- A Tight Oracle Threshold for k-Submodular Maximization
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- is_c1_k_submod_kernelA bivariate function H : ℝ → ℝ → ℝ satisfies is_c1_k_submod_kernel if the map (fun p : ℝ × ℝ => H p.1 p.2) is continuously differentiable…
- k_submod_hidden_fnFor implicit n and k, a bivariate function H : ℝ → ℝ → ℝ, a hidden assignment σ : Fin n → Fin k, and a partial assignment x : Fin n →…
- is_k_submod_monotoneA function f : (Fin n → Option (Fin k)) → ℝ is monotone if x ≤ y under the componentwise order implies f x ≤ f y.
- is_k_submodularA function f : (Fin n → Option (Fin k)) → ℝ is k-submodular if for all x and y, f (x ⊓ y) + f (x ⊔ y) ≤ f x + f y.
- 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…
- k_submod_hidden_fn_monotoneFor n > 0, k ≥ 2, σ : Fin n → Fin k, and H : ℝ → ℝ → ℝ satisfying is_k_submod_kernel, the function k_submod_hidden_fn H σ satisfies…
- 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.
- 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.
- has_orthant_diminishing_returnsA 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…
- is_k_submod_kernelA two-variable kernel H : ℝ → ℝ → ℝ satisfies the hidden-label conditions if H(0,0) = 0, H(1,0) > 0, H(x,y) ≤ H(1,0) on [0,1]², H is…
Read back from the Lean
Given natural numbers $n, k$ such that $0 < n$ and $2 \le k$, a target assignment $\sigma : \mathrm{Fin}\ n \to \mathrm{Fin}\ k$, and a function $H : \mathbb{R} \to \mathbb{R} \to \mathbb{R}$ that is a $C^1$ $k$-submodular kernel (is_c1_k_submod_kernel H), the associated hidden function $f := \mathrm{k\_submod\_hidden\_fn}\ H\ \sigma$ satisfies:
1. $f$ is non-negative everywhere: $\forall x, 0 \le f(x)$;
2. $f$ is monotone with respect to the partial order on $\mathrm{Fin}\ n \to \mathrm{Option}(\mathrm{Fin}\ k)$ (is_k_submod_monotone f);
3. $f$ is $k$-submodular (is_k_submodular f);
4. $f$ evaluated at the all-none vector is $0$;
5. $f$ is bounded above by $1$: $\forall x, f(x) \le 1$;
6. $f$ evaluated at the vector $\lambda e \mapsto \mathrm{some}(\sigma(e))$ equals $1$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem establishes that the hidden-label function f = k_submod_hidden_fn(H, σ) satisfies the six defining properties of a normalized monotone k-submodular function. Monotonicity is inherited directly from the kernel properties of H, and k-submodularity follows because C¹ regularity of H ensures orthant diminishing returns, which together with monotonicity implies k-submodularity. The boundary values f(none) = 0 and f(σ) = 1 follow from evaluating H at (0, 0) and (1, 0), while nonnegativity holds because the empty configuration is minimal. Finally, f(x) ≤ 1 holds because the normalized counts of correct and assigned coordinates lie in [0, 1], where H is bounded above by H(1, 0).
The normalized hidden-label function f is monotone and k-submodular.
Let f = k_submod_hidden_fn(H, σ). Monotonicity of f is established by k_submod_hidden_fn_monotone using the kernel properties of H. Furthermore, because H is continuously differentiable, f satisfies orthant diminishing returns by k_submod_c1_hidden_fn_orthant_diminishing_returns. Monotonicity combined with orthant diminishing returns implies that f is k-submodular via k_submodular_of_monotone_of_orthant_diminishing_returns.
uses
k_submod_hidden_fn_monotone,k_submod_c1_hidden_fn_orthant_diminishing_returns,k_submodular_of_monotone_of_orthant_diminishing_returnsintro f have hmono : is_k_submod_monotone f := k_submod_hidden_fn_monotone hn hk σ H hH.2 have hdim := k_submod_c1_hidden_fn_orthant_diminishing_returns hn hk σ H hH have hsubmod : is_k_submodular f := k_submodular_of_monotone_of_orthant_diminishing_returns f hmono hdim
f(fun _ => none) = 0.
At the all-none configuration, no coordinate matches the hidden label σ and no coordinate is assigned, so both the matching set and the support set are empty. Their cardinalities are zero, meaning the arguments to H are 0/n = 0 and (0 - 0)/n = 0. Since H(0, 0) = 0 by the definition of a kernel, f(fun _ => none) = 0 / H(1, 0) = 0.
have hnone : f (fun _ => none) = 0 := by dsimp [f, k_submod_hidden_fn] have hc : ({e : Fin n | (fun _ : Fin n => (none : Option (Fin k))) e = some (σ e)} : Finset (Fin n)) = ∅ := by ext e; simp have hm : ({e : Fin n | (fun _ : Fin n => (none : Option (Fin k))) e ≠ none} : Finset (Fin n)) = ∅ := by ext e; simp rw [hc, hm] simp [hH.2.1]
f(x) ≥ 0 for all configurations x.
For any configuration x, the all-none configuration is a lower bound under the k-submodular order (every coordinate is either none or matches x), using Or.inl. Monotonicity of f then gives f(fun _ => none) ≤ f(x), and substituting f(fun _ => none) = 0 yields 0 ≤ f(x).
uses
Or.inlhave hnonneg : ∀ x, 0 ≤ f x := by intro x have hle : k_submod_le (fun _ => none) x := fun _ => Or.inl rfl have := hmono (fun _ => none) x hle rwa [hnone] at this
f(x) ≤ 1 for all configurations x.
Fix a configuration x, and let c be the number of coordinates matching σ and m the total number of assigned coordinates. Any coordinate that matches σ is assigned, so the matching set is a subset of the assigned set (using Finset.mem_filter, Finset.mem_univ, and true_and), which implies c ≤ m by Finset.card_le_card. Both sets have cardinality at most n by Finset.card_le_univ. Since n > 0 (by Nat.cast_pos.mpr), the normalized match ratio c/n lies in [0, 1] by div_nonneg, Nat.cast_nonneg, le_of_lt, div_le_one, and Nat.cast_le. Similarly, the normalized non-matching assigned ratio (m - c)/n lies in [0, 1] using div_nonneg, div_le_one, Nat.cast_nonneg, Nat.cast_le, and le_of_lt. The kernel property then guarantees H(c/n, (m - c)/n) ≤ H(1, 0). Dividing by H(1, 0) > 0 via div_le_one concludes that f(x) ≤ 1.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.card_le_card,Finset.card_le_univ,Nat.cast_pos.mpr,div_nonneg,Nat.cast_nonneg,le_of_lt,div_le_one,Nat.cast_lehave hle_one : ∀ x, f x ≤ 1 := by intro x dsimp [f, k_submod_hidden_fn] have hAsubB : ({e : Fin n | x e = some (σ e)} : Finset (Fin n)) ⊆ ({e : Fin n | x e ≠ none} : Finset (Fin n)) := by intro e he simp only [Finset.mem_filter, Finset.mem_univ, true_and] at he ⊢ rw [he]; simp have hclem : ({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card ≤ ({e : Fin n | x e ≠ none} : Finset (Fin n)).card := Finset.card_le_card hAsubB have hmlen : ({e : Fin n | x e ≠ none} : Finset (Fin n)).card ≤ n := by simpa using Finset.card_le_univ ({e : Fin n | x e ≠ none} : Finset (Fin n)) have hclen : ({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card ≤ n := by simpa using Finset.card_le_univ ({e : Fin n | x e = some (σ e)} : Finset (Fin n)) have hnR : (0 : ℝ) < (n : ℝ) := Nat.cast_pos.mpr hn have hH10 : (0 : ℝ) < H 1 0 := hH.2.2.1 have hx0 : 0 ≤ (({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card : ℝ) / (n : ℝ) := div_nonneg (Nat.cast_nonneg _) (le_of_lt hnR) have hx1 : (({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card : ℝ) / (n : ℝ) ≤ 1 := by rw [div_le_one hnR] exact (Nat.cast_le (α := ℝ)).mpr hclen have hy0 : 0 ≤ ((({e : Fin n | x e ≠ none} : Finset (Fin n)).card : ℝ) - (({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card : ℝ)) / (n : ℝ) := by apply div_nonneg · have : (({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card : ℝ) ≤ (({e : Fin n | x e ≠ none} : Finset (Fin n)).card : ℝ) := (Nat.cast_le (α := ℝ)).mpr hclem linarith · exact le_of_lt hnR have hy1 : ((({e : Fin n | x e ≠ none} : Finset (Fin n)).card : ℝ) - (({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card : ℝ)) / (n : ℝ) ≤ 1 := by rw [div_le_one hnR] have : (0 : ℝ) ≤ (({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card : ℝ) := Nat.cast_nonneg _ have : (({e : Fin n | x e ≠ none} : Finset (Fin n)).card : ℝ) ≤ (n : ℝ) := (Nat.cast_le (α := ℝ)).mpr hmlen linarith have hbound := hH.2.2.2.1 _ _ hx0 hx1 hy0 hy1 rw [div_le_one hH10] exact hbound
f(fun e => some (σ e)) = 1.
When every coordinate e is assigned its hidden label σ(e), both the matching set and the support set equal the entire universe Finset.univ, which has cardinality n by Finset.card_univ and Fintype.card_fin. The inputs to H are therefore n/n = 1 (using div_self and Nat.cast_ne_zero.mpr with ne_of_gt) and (n - n)/n = 0. Since H(1, 0) ≠ 0 by ne_of_gt, f evaluates to H(1, 0) / H(1, 0) = 1.
uses
Nat.cast_ne_zero.mpr,ne_of_gt,Finset.card_univ,Fintype.card_fin,div_selfhave htop : f (fun e => some (σ e)) = 1 := by dsimp [f, k_submod_hidden_fn] have hc : ({e : Fin n | (fun e' => some (σ e')) e = some (σ e)} : Finset (Fin n)) = Finset.univ := by ext e; simp have hm : ({e : Fin n | (fun e' => some (σ e')) e ≠ none} : Finset (Fin n)) = Finset.univ := by ext e; simp rw [hc, hm] have hnR : (n : ℝ) ≠ 0 := Nat.cast_ne_zero.mpr (ne_of_gt hn) have hH10 : H 1 0 ≠ 0 := ne_of_gt hH.2.2.1 simp [Finset.card_univ, Fintype.card_fin, div_self hnR, hH10]
All six desired properties of f hold simultaneously.
The proof concludes by packaging the six established properties—nonnegativity, monotonicity, k-submodularity, zero at the empty configuration, upper bounded by 1, and normalized to 1 at the hidden assignment—into the target conjunction.
exact ⟨hnonneg, hmono, hsubmod, hnone, hle_one, htop⟩
k_submod_hidden_fn_monotone- For positive n and k ≥ 2, the hidden-label function k_submod_hidden_fn(H, σ) is monotone in the k-submodular order if H is a k-submodular kernel.
k_submod_c1_hidden_fn_orthant_diminishing_returns- For positive n and k ≥ 2, the hidden-label function k_submod_hidden_fn(H, σ) satisfies orthant diminishing returns if H is a C¹ k-submodular kernel.
k_submodular_of_monotone_of_orthant_diminishing_returns- A function on (Fin n → Option (Fin k)) is k-submodular if it is monotone and satisfies orthant diminishing returns.
Or.inl- The left injection into a disjunction: from a proof of P, deduces P ∨ Q.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- The conjunction True ∧ P is equivalent to P.
Finset.card_le_card- If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
Finset.card_le_univ- The cardinality of any finset is at most the cardinality of the ambient finite type.
Nat.cast_pos.mpr- A natural number n satisfies 0 < n if and only if its cast to an ordered semiring satisfies 0 < (n : ℝ).
div_nonneg- The quotient a / b is non-negative if a ≥ 0 and b ≥ 0.
Nat.cast_nonneg- The cast of any natural number to an ordered semiring is non-negative.
le_of_lt- A strict inequality a < b implies the weak inequality a ≤ b.
div_le_one- For b > 0, the quotient a / b ≤ 1 if and only if a ≤ b.
Nat.cast_le- The inequality (m : ℝ) ≤ (n : ℝ) for cast natural numbers is equivalent to m ≤ n in ℕ.
Nat.cast_ne_zero.mpr- A natural number n ≠ 0 implies its cast (n : ℝ) ≠ 0.
ne_of_gt- If b < a, then a ≠ b.
Finset.card_univ- The cardinality of the universal finset Finset.univ equals Fintype.card of the underlying type.
Fintype.card_fin- The cardinality of the finite type Fin n is n.
div_self- For any non-zero element a in a group with zero, a / a = 1.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Monotonicity and k-submodularity of the hidden-label kernel function (Lemma 2.2). -/theorem k_submod_c1_hidden_fn_properties {n k : ℕ} (hn : 0 < n) (hk : 2 ≤ k) (σ : Fin n → Fin k) (H : ℝ → ℝ → ℝ) (hH : is_c1_k_submod_kernel H) : let f := k_submod_hidden_fn H σ (∀ x, 0 ≤ f x) ∧ is_k_submod_monotone f ∧ is_k_submodular f ∧ f (fun _ => none) = 0 ∧ (∀ x, f x ≤ 1) ∧ f (fun e => some (σ e)) = 1 := by intro f have hmono : is_k_submod_monotone f := k_submod_hidden_fn_monotone hn hk σ H hH.2 have hdim := k_submod_c1_hidden_fn_orthant_diminishing_returns hn hk σ H hH have hsubmod : is_k_submodular f := k_submodular_of_monotone_of_orthant_diminishing_returns f hmono hdim have hnone : f (fun _ => none) = 0 := by dsimp [f, k_submod_hidden_fn] have hc : ({e : Fin n | (fun _ : Fin n => (none : Option (Fin k))) e = some (σ e)} : Finset (Fin n)) = ∅ := by ext e; simp have hm : ({e : Fin n | (fun _ : Fin n => (none : Option (Fin k))) e ≠ none} : Finset (Fin n)) = ∅ := by ext e; simp rw [hc, hm] simp [hH.2.1] have hnonneg : ∀ x, 0 ≤ f x := by intro x have hle : k_submod_le (fun _ => none) x := fun _ => Or.inl rfl have := hmono (fun _ => none) x hle rwa [hnone] at this have hle_one : ∀ x, f x ≤ 1 := by intro x dsimp [f, k_submod_hidden_fn] have hAsubB : ({e : Fin n | x e = some (σ e)} : Finset (Fin n)) ⊆ ({e : Fin n | x e ≠ none} : Finset (Fin n)) := by intro e he simp only [Finset.mem_filter, Finset.mem_univ, true_and] at he ⊢ rw [he]; simp have hclem : ({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card ≤ ({e : Fin n | x e ≠ none} : Finset (Fin n)).card := Finset.card_le_card hAsubB have hmlen : ({e : Fin n | x e ≠ none} : Finset (Fin n)).card ≤ n := by simpa using Finset.card_le_univ ({e : Fin n | x e ≠ none} : Finset (Fin n)) have hclen : ({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card ≤ n := by simpa using Finset.card_le_univ ({e : Fin n | x e = some (σ e)} : Finset (Fin n)) have hnR : (0 : ℝ) < (n : ℝ) := Nat.cast_pos.mpr hn have hH10 : (0 : ℝ) < H 1 0 := hH.2.2.1 have hx0 : 0 ≤ (({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card : ℝ) / (n : ℝ) := div_nonneg (Nat.cast_nonneg _) (le_of_lt hnR) have hx1 : (({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card : ℝ) / (n : ℝ) ≤ 1 := by rw [div_le_one hnR] exact (Nat.cast_le (α := ℝ)).mpr hclen have hy0 : 0 ≤ ((({e : Fin n | x e ≠ none} : Finset (Fin n)).card : ℝ) - (({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card : ℝ)) / (n : ℝ) := by apply div_nonneg · have : (({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card : ℝ) ≤ (({e : Fin n | x e ≠ none} : Finset (Fin n)).card : ℝ) := (Nat.cast_le (α := ℝ)).mpr hclem linarith · exact le_of_lt hnR have hy1 : ((({e : Fin n | x e ≠ none} : Finset (Fin n)).card : ℝ) - (({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card : ℝ)) / (n : ℝ) ≤ 1 := by rw [div_le_one hnR] have : (0 : ℝ) ≤ (({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card : ℝ) := Nat.cast_nonneg _ have : (({e : Fin n | x e ≠ none} : Finset (Fin n)).card : ℝ) ≤ (n : ℝ) := (Nat.cast_le (α := ℝ)).mpr hmlen linarith have hbound := hH.2.2.2.1 _ _ hx0 hx1 hy0 hy1 rw [div_le_one hH10] exact hbound have htop : f (fun e => some (σ e)) = 1 := by dsimp [f, k_submod_hidden_fn] have hc : ({e : Fin n | (fun e' => some (σ e')) e = some (σ e)} : Finset (Fin n)) = Finset.univ := by ext e; simp have hm : ({e : Fin n | (fun e' => some (σ e')) e ≠ none} : Finset (Fin n)) = Finset.univ := by ext e; simp rw [hc, hm] have hnR : (n : ℝ) ≠ 0 := Nat.cast_ne_zero.mpr (ne_of_gt hn) have hH10 : H 1 0 ≠ 0 := ne_of_gt hH.2.2.1 simp [Finset.card_univ, Fintype.card_fin, div_self hnR, hH10] exact ⟨hnonneg, hmono, hsubmod, hnone, hle_one, htop⟩