AFTD Auto-Formalizing Theoretical Domains

k_submod_hidden_fn_monotone

theoremverified

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).

  1. 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).

    lines 6–7

    uses k_submod_hidden_fn, k_submod_le

      intro x y hxy
      simp only [k_submod_hidden_fn, k_submod_le] at hxy ⊢
  2. 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)).

    lines 8–14

    uses Finset.mem_filter, Finset.mem_univ, true_and

      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
  3. 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).

    lines 15–22

    uses Finset.mem_filter, Finset.mem_univ, true_and

      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⟩
  4. 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|.

    lines 23–26

    uses Finset.card_le_card

      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
  5. 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.

    lines 27–36

    uses Finset.mem_filter, Finset.mem_univ, true_and

      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
  6. 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.

    lines 37–48

    uses Finset.card_sdiff_of_subset, Finset.mem_sdiff

      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]
  7. 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.

    lines 49–57

    uses Nat.cast_sub, Finset.card_le_card

      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]
  8. 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].

    lines 58–64

    uses Finset.card_le_univ

      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
  9. 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.

    lines 65–74

    uses div_nonneg, Nat.cast_nonneg, div_le_div_of_nonneg_right, Nat.cast_le.mpr, div_le_one

      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
  10. 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.

    lines 75–84

    uses div_nonneg, Nat.cast_nonneg, div_le_one, div_le_div_of_nonneg_right, Nat.cast_le.mpr

      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
  11. 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.

    line 85

    uses div_le_div_of_nonneg_right, le_trans, le_of_lt

      exact 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.

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

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