k_submod_hidden_fn_monotone
For n > 0, k ≥ 2, σ : Fin n → Fin k, and H : ℝ → ℝ → ℝ satisfying is_k_submod_kernel, the function k_submod_hidden_fn H σ satisfies is_k_submod_monotone.
Statement
theorem k_submod_hidden_fn_monotone
{n k : ℕ} (hn : 0 < n) (hk : 2 ≤ k) (σ : Fin n → Fin k)
(H : ℝ → ℝ → ℝ) (hH : is_k_submod_kernel H) :
is_k_submod_monotone (k_submod_hidden_fn H σ)- Source
- arXiv:2610.26677, Lemma 2.2
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- 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.
- 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 1
- 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…
Read back from the Lean
For any natural numbers $n$ and $k$ with $n > 0$ and $k \ge 2$, any function $\sigma : \text{Fin } n \to \text{Fin } k$, and any function $H : \mathbb{R} \to \mathbb{R} \to \mathbb{R}$ satisfying is_k_submod_kernel H, the function k_submod_hidden_fn H σ is monotone with respect to the partial order k_submod_le on $\text{Fin } n \to \text{Option } (\text{Fin } k)$. That is, if $x, y : \text{Fin } n \to \text{Option } (\text{Fin } k)$ satisfy $x(e) = \text{none} \lor x(e) = y(e)$ for all $e \in \text{Fin } n$, then k_submod_hidden_fn H σ x ≤ k_submod_hidden_fn H σ y.
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
To prove that the hidden-label function f_σ is monotone with respect to the partial assignment ordering x ≤ y, the coordinates are partitioned into correctly and incorrectly labeled elements. Because any assigned coordinate of x must match that of y, both the set of correct coordinates and the set of incorrect coordinates grow monotonically from x to y. The objective value is given by evaluating a bivariate kernel H on the normalized fractions of correct and incorrect coordinates, scaled by H(1, 0). Since H is separately non-decreasing in each argument on [0, 1]² and H(1, 0) > 0, applying monotonicity sequentially in each coordinate establishes that f_σ(x) ≤ f_σ(y).
Assume x ≤ y, and unfold the definitions of k-submodular ordering and the function f_σ.
We introduce the partial assignments x and y together with the hypothesis x ≤ y. Expanding k_submod_le and k_submod_hidden_fn expresses the goal as an inequality between the kernel H evaluated on the normalized counts of correct and incorrect assignments of x versus y, divided by H(1, 0).
uses
k_submod_hidden_fn,k_submod_leintro x y hxy simp only [k_submod_hidden_fn, k_submod_le] at hxy ⊢
The set of correctly labeled coordinates of x is a subset of that of y.
Let e be an element such that x(e) = some (σ(e)). Since x ≤ y, either x(e) = none or x(e) = y(e). The first case contradicts that x(e) is assigned. Thus x(e) = y(e), which implies y(e) = some (σ(e)).
uses
Finset.mem_filter,Finset.mem_univ,true_andhave hAsub : ({e : Fin n | x e = some (σ e)} : Finset (Fin n)) ⊆ ({e : Fin n | y e = some (σ e)} : Finset (Fin n)) := by intro e he simp only [Finset.mem_filter, Finset.mem_univ, true_and] at he ⊢ rcases hxy e with h | h · rw [h] at he; simp at he · rw [← h]; exact he
The set of incorrectly labeled coordinates of x is a subset of that of y.
Let e be an element with x(e) ≠ none and x(e) ≠ some (σ(e)). From x ≤ y, the only consistent case is x(e) = y(e). Therefore y(e) is also assigned and differs from σ(e).
uses
Finset.mem_filter,Finset.mem_univ,true_andhave hWsub : ({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)) ⊆ ({e : Fin n | y e ≠ none ∧ y e ≠ some (σ e)} : Finset (Fin n)) := by intro e he simp only [Finset.mem_filter, Finset.mem_univ, true_and] at he ⊢ obtain ⟨hne, hwrong⟩ := he rcases hxy e with h | h · exact absurd h hne · rw [← h]; exact ⟨hne, hwrong⟩
The cardinalities of the sets of correct and incorrect coordinates are non-decreasing from x to y.
Because the subset relation between finite sets implies the corresponding inequality between their cardinalities, the inclusions established in the previous two steps yield |A_x| ≤ |A_y| and |W_x| ≤ |W_y|.
uses
Finset.card_le_cardhave hAcard : ({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card ≤ ({e : Fin n | y e = some (σ e)} : Finset (Fin n)).card := Finset.card_le_card hAsub have hWcard : ({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)).card ≤ ({e : Fin n | y e ≠ none ∧ y e ≠ some (σ e)} : Finset (Fin n)).card := Finset.card_le_card hWsub
For both x and y, the correctly labeled coordinates are a subset of all assigned coordinates.
If a coordinate is labeled with some value, it cannot be none.
uses
Finset.mem_filter,Finset.mem_univ,true_andhave 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 hAsubB' : ({e : Fin n | y e = some (σ e)} : Finset (Fin n)) ⊆ ({e : Fin n | y e ≠ none} : Finset (Fin n)) := by intro e he simp only [Finset.mem_filter, Finset.mem_univ, true_and] at he ⊢ rw [he]; simp
The number of assigned coordinates minus the number of correct coordinates equals the number of incorrect coordinates.
Since the correct coordinates form a subset of the assigned coordinates, their difference in cardinality equals the cardinality of the set difference. An assigned coordinate that is not correct is precisely an incorrect coordinate. This holds for both x and y.
uses
Finset.card_sdiff_of_subset,Finset.mem_sdiffhave hxsplit : ({e : Fin n | x e ≠ none} : Finset (Fin n)).card - ({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card = ({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)).card := by rw [← Finset.card_sdiff_of_subset hAsubB] congr 1 ext e; simp [Finset.mem_sdiff] have hysplit : ({e : Fin n | y e ≠ none} : Finset (Fin n)).card - ({e : Fin n | y e = some (σ e)} : Finset (Fin n)).card = ({e : Fin n | y e ≠ none ∧ y e ≠ some (σ e)} : Finset (Fin n)).card := by rw [← Finset.card_sdiff_of_subset hAsubB'] congr 1 ext e; simp [Finset.mem_sdiff]
The second argument of the kernel simplifies to the fraction of incorrect coordinates over n.
Casting the identity (|assigned| - |correct|) = |incorrect| to the real numbers and dividing by n allows us to rewrite the second argument of H in both sides of the goal directly as |incorrect| / n.
uses
Nat.cast_sub,Finset.card_le_cardhave hwx_eq : ((({e : Fin n | x e ≠ none} : Finset (Fin n)).card : ℝ) - (({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card : ℝ)) / (n:ℝ) = ((({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)).card : ℝ)) / (n:ℝ) := by rw [← Nat.cast_sub (Finset.card_le_card hAsubB), hxsplit] have hwy_eq : ((({e : Fin n | y e ≠ none} : Finset (Fin n)).card : ℝ) - (({e : Fin n | y e = some (σ e)} : Finset (Fin n)).card : ℝ)) / (n:ℝ) = ((({e : Fin n | y e ≠ none ∧ y e ≠ some (σ e)} : Finset (Fin n)).card : ℝ)) / (n:ℝ) := by rw [← Nat.cast_sub (Finset.card_le_card hAsubB'), hysplit] rw [hwx_eq, hwy_eq]
The cardinalities of the relevant coordinate sets are bounded above by n, and n > 0 in ℝ.
Any subset of Fin n has cardinality at most n. The hypothesis n > 0 casts to 0 < (n : ℝ), ensuring that the normalized fractions belong to [0, 1].
uses
Finset.card_le_univhave hAy_le_n : ({e : Fin n | y e = some (σ e)} : Finset (Fin n)).card ≤ n := by simpa using Finset.card_le_univ ({e : Fin n | y e = some (σ e)} : Finset (Fin n)) have hWx_le_n : ({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)).card ≤ n := by simpa using Finset.card_le_univ ({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)) have hWy_le_n : ({e : Fin n | y e ≠ none ∧ y e ≠ some (σ e)} : Finset (Fin n)).card ≤ n := by simpa using Finset.card_le_univ ({e : Fin n | y e ≠ none ∧ y e ≠ some (σ e)} : Finset (Fin n)) have hnR : (0:ℝ) < n := by exact_mod_cast hn
H(|A_x| / n, |W_x| / n) ≤ H(|A_y| / n, |W_x| / n).
This is monotonicity of H in its first argument, given by the kernel hypothesis. All required bounds—that the arguments are non-negative, at most 1, and that |A_x| / n ≤ |A_y| / n—follow from the previous inequalities and n > 0.
uses
div_nonneg,Nat.cast_nonneg,div_le_div_of_nonneg_right,Nat.cast_le.mpr,div_le_onehave step1 : H (({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card / (n:ℝ)) (({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)).card / (n:ℝ)) ≤ H (({e : Fin n | y e = some (σ e)} : Finset (Fin n)).card / (n:ℝ)) (({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)).card / (n:ℝ)) := by apply hH.2.2.2.1 · exact div_nonneg (Nat.cast_nonneg _) (Nat.cast_nonneg _) · exact div_le_div_of_nonneg_right (Nat.cast_le.mpr hAcard) (Nat.cast_nonneg _) · rw [div_le_one hnR]; exact Nat.cast_le.mpr hAy_le_n · exact div_nonneg (Nat.cast_nonneg _) (Nat.cast_nonneg _) · rw [div_le_one hnR]; exact Nat.cast_le.mpr hWx_le_n
H(|A_y| / n, |W_x| / n) ≤ H(|A_y| / n, |W_y| / n).
This is monotonicity of H in its second argument, given by the kernel hypothesis, with the preconditions verified by the bounds 0 ≤ |W_x| / n ≤ |W_y| / n ≤ 1 and 0 ≤ |A_y| / n ≤ 1.
uses
div_nonneg,Nat.cast_nonneg,div_le_one,div_le_div_of_nonneg_right,Nat.cast_le.mprhave step2 : H (({e : Fin n | y e = some (σ e)} : Finset (Fin n)).card / (n:ℝ)) (({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)).card / (n:ℝ)) ≤ H (({e : Fin n | y e = some (σ e)} : Finset (Fin n)).card / (n:ℝ)) (({e : Fin n | y e ≠ none ∧ y e ≠ some (σ e)} : Finset (Fin n)).card / (n:ℝ)) := by apply hH.2.2.2.2.1 · exact div_nonneg (Nat.cast_nonneg _) (Nat.cast_nonneg _) · rw [div_le_one hnR]; exact Nat.cast_le.mpr hAy_le_n · exact div_nonneg (Nat.cast_nonneg _) (Nat.cast_nonneg _) · exact div_le_div_of_nonneg_right (Nat.cast_le.mpr hWcard) (Nat.cast_nonneg _) · rw [div_le_one hnR]; exact Nat.cast_le.mpr hWy_le_n
f_σ(x) ≤ f_σ(y).
Chaining the two coordinate monotonicity steps by transitivity yields H(|A_x| / n, |W_x| / n) ≤ H(|A_y| / n, |W_y| / n). Dividing both sides by the positive constant H(1, 0) completes the proof.
uses
div_le_div_of_nonneg_right,le_trans,le_of_ltexact div_le_div_of_nonneg_right (le_trans step1 step2) (le_of_lt hH.2.1)
div_le_div_of_nonneg_right- If a ≤ b and c ≥ 0, then a / c ≤ b / c.
div_le_one- For b > 0, a / b ≤ 1 if and only if a ≤ b.
div_nonneg- If a ≥ 0 and b ≥ 0, then a / b ≥ 0.
Finset.card_le_univ- A finset of elements of type α has cardinality at most the cardinality of the type α.
Finset.card_le_card- If s ⊆ t for finsets s and t, then |s| ≤ |t|.
Finset.card_sdiff_of_subset- If s ⊆ t, then |t \ s| = |t| - |s|.
Finset.mem_filter- An element belongs to Finset.filter p s if and only if it belongs to s and satisfies p.
Finset.mem_sdiff- An element belongs to s \ t if and only if it belongs to s and not to t.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
k_submod_hidden_fn- The objective function f_σ(x) = H(c/n, (m - c)/n) / H(1, 0), where c is the count of correct coordinates and m is the count of assigned coordinates.
k_submod_le- The partial order x ≤ y on partial assignments, meaning that for each coordinate e, either x(e) = none or x(e) = y(e).
le_of_lt- Strict inequality a < b implies non-strict inequality a ≤ b.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Nat.cast_le.mpr- If m ≤ n for natural numbers, then their coercions into an ordered semiring satisfy ↑m ≤ ↑n.
Nat.cast_nonneg- The coercion of any natural number into an ordered ring is non-negative.
Nat.cast_sub- If m ≤ n, the coercion of n - m into an additive group with one equals ↑n - ↑m.
true_and- The proposition (True ∧ p) is equivalent to p.
- The monotonicity properties of the kernel H in its first and second arguments, as well as the positivity condition H 1 0 > 0, are accessed as coordinate projections (such as hH.2.2.2.1 and hH.2.1) of the conjunction defining is_k_submod_kernel.
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.
/-- The hidden-label function f_σ is monotone. -/theorem k_submod_hidden_fn_monotone {n k : ℕ} (hn : 0 < n) (hk : 2 ≤ k) (σ : Fin n → Fin k) (H : ℝ → ℝ → ℝ) (hH : is_k_submod_kernel H) : is_k_submod_monotone (k_submod_hidden_fn H σ) := by intro x y hxy simp only [k_submod_hidden_fn, k_submod_le] at hxy ⊢ have hAsub : ({e : Fin n | x e = some (σ e)} : Finset (Fin n)) ⊆ ({e : Fin n | y e = some (σ e)} : Finset (Fin n)) := by intro e he simp only [Finset.mem_filter, Finset.mem_univ, true_and] at he ⊢ rcases hxy e with h | h · rw [h] at he; simp at he · rw [← h]; exact he have hWsub : ({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)) ⊆ ({e : Fin n | y e ≠ none ∧ y e ≠ some (σ e)} : Finset (Fin n)) := by intro e he simp only [Finset.mem_filter, Finset.mem_univ, true_and] at he ⊢ obtain ⟨hne, hwrong⟩ := he rcases hxy e with h | h · exact absurd h hne · rw [← h]; exact ⟨hne, hwrong⟩ have hAcard : ({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card ≤ ({e : Fin n | y e = some (σ e)} : Finset (Fin n)).card := Finset.card_le_card hAsub have hWcard : ({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)).card ≤ ({e : Fin n | y e ≠ none ∧ y e ≠ some (σ e)} : Finset (Fin n)).card := Finset.card_le_card hWsub 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 hAsubB' : ({e : Fin n | y e = some (σ e)} : Finset (Fin n)) ⊆ ({e : Fin n | y 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 hxsplit : ({e : Fin n | x e ≠ none} : Finset (Fin n)).card - ({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card = ({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)).card := by rw [← Finset.card_sdiff_of_subset hAsubB] congr 1 ext e; simp [Finset.mem_sdiff] have hysplit : ({e : Fin n | y e ≠ none} : Finset (Fin n)).card - ({e : Fin n | y e = some (σ e)} : Finset (Fin n)).card = ({e : Fin n | y e ≠ none ∧ y e ≠ some (σ e)} : Finset (Fin n)).card := by rw [← Finset.card_sdiff_of_subset hAsubB'] congr 1 ext e; simp [Finset.mem_sdiff] have hwx_eq : ((({e : Fin n | x e ≠ none} : Finset (Fin n)).card : ℝ) - (({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card : ℝ)) / (n:ℝ) = ((({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)).card : ℝ)) / (n:ℝ) := by rw [← Nat.cast_sub (Finset.card_le_card hAsubB), hxsplit] have hwy_eq : ((({e : Fin n | y e ≠ none} : Finset (Fin n)).card : ℝ) - (({e : Fin n | y e = some (σ e)} : Finset (Fin n)).card : ℝ)) / (n:ℝ) = ((({e : Fin n | y e ≠ none ∧ y e ≠ some (σ e)} : Finset (Fin n)).card : ℝ)) / (n:ℝ) := by rw [← Nat.cast_sub (Finset.card_le_card hAsubB'), hysplit] rw [hwx_eq, hwy_eq] have hAy_le_n : ({e : Fin n | y e = some (σ e)} : Finset (Fin n)).card ≤ n := by simpa using Finset.card_le_univ ({e : Fin n | y e = some (σ e)} : Finset (Fin n)) have hWx_le_n : ({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)).card ≤ n := by simpa using Finset.card_le_univ ({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)) have hWy_le_n : ({e : Fin n | y e ≠ none ∧ y e ≠ some (σ e)} : Finset (Fin n)).card ≤ n := by simpa using Finset.card_le_univ ({e : Fin n | y e ≠ none ∧ y e ≠ some (σ e)} : Finset (Fin n)) have hnR : (0:ℝ) < n := by exact_mod_cast hn have step1 : H (({e : Fin n | x e = some (σ e)} : Finset (Fin n)).card / (n:ℝ)) (({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)).card / (n:ℝ)) ≤ H (({e : Fin n | y e = some (σ e)} : Finset (Fin n)).card / (n:ℝ)) (({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)).card / (n:ℝ)) := by apply hH.2.2.2.1 · exact div_nonneg (Nat.cast_nonneg _) (Nat.cast_nonneg _) · exact div_le_div_of_nonneg_right (Nat.cast_le.mpr hAcard) (Nat.cast_nonneg _) · rw [div_le_one hnR]; exact Nat.cast_le.mpr hAy_le_n · exact div_nonneg (Nat.cast_nonneg _) (Nat.cast_nonneg _) · rw [div_le_one hnR]; exact Nat.cast_le.mpr hWx_le_n have step2 : H (({e : Fin n | y e = some (σ e)} : Finset (Fin n)).card / (n:ℝ)) (({e : Fin n | x e ≠ none ∧ x e ≠ some (σ e)} : Finset (Fin n)).card / (n:ℝ)) ≤ H (({e : Fin n | y e = some (σ e)} : Finset (Fin n)).card / (n:ℝ)) (({e : Fin n | y e ≠ none ∧ y e ≠ some (σ e)} : Finset (Fin n)).card / (n:ℝ)) := by apply hH.2.2.2.2.1 · exact div_nonneg (Nat.cast_nonneg _) (Nat.cast_nonneg _) · rw [div_le_one hnR]; exact Nat.cast_le.mpr hAy_le_n · exact div_nonneg (Nat.cast_nonneg _) (Nat.cast_nonneg _) · exact div_le_div_of_nonneg_right (Nat.cast_le.mpr hWcard) (Nat.cast_nonneg _) · rw [div_le_one hnR]; exact Nat.cast_le.mpr hWy_le_n exact div_le_div_of_nonneg_right (le_trans step1 step2) (le_of_lt hH.2.1)