AFTD Auto-Formalizing Theoretical Domains

k_submod_c1_hidden_fn_properties

theoremverifiedformalization

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

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

    lines 12–15

    uses k_submod_hidden_fn_monotone, k_submod_c1_hidden_fn_orthant_diminishing_returns, k_submodular_of_monotone_of_orthant_diminishing_returns

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

    lines 16–23

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

    lines 24–28

    uses Or.inl

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

    lines 29–65

    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_le

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

    lines 66–75

    uses Nat.cast_ne_zero.mpr, ne_of_gt, Finset.card_univ, Fintype.card_fin, div_self

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

    line 76

      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

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