AFTD Auto-Formalizing Theoretical Domains

not_k_submod_hidden_fn_properties

theoremverifiedoriginal

The statement k_submod_hidden_fn_properties is false: The definition is_k_submod_kernel lacks a differentiability/continuity hypothesis on H. In Lean, deriv f x evaluates to 0 when f is not differentiable at x. Consequently, discontinuous functions like H(x, y) = if x ≥ 1 then 1 else 0 satisfy is_k_submod_kernel H because their derivatives vanish identically on [0,1]², satisfying conditions 6 and 7 vacuously. For this kernel, with n=2, k=2, σ ≡ 0, x = (some 0, none), y = (none, some 0), we find f(x ⊓ y) = 0, f(x ⊔ y) = 1, and f(x) = f(y) = 0, so f(x ⊓ y) + f(x ⊔ y) = 1 > 0 = f(x) + f(y), contradicting k-submodularity.

Statement

theorem not_k_submod_hidden_fn_properties : ¬ (∀ {n k : ℕ} (hn : 0 < n) (hk : 2 ≤ k) (σ : Fin n → Fin k)
    (H : ℝ → ℝ → ℝ) (hH : is_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)
Related work
refutes `k_submod_hidden_fn_properties`
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • 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.
  • 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_joinJoin of two assignments x and y in Fin n → Option (Fin k): at each coordinate e, if one is none it takes the other, if both agree it takes…
  • k_submod_meetMeet of two assignments x and y in Fin n → Option (Fin k): at each coordinate e, it is x e if x e = y e, and none otherwise.

The proof, explained

The theorem is disproved by constructing an explicit counterexample kernel $H_{\text{counter}}(x, y) = \text{if } x \ge 1 \text{ then } 1 \text{ else } 0$. Because Lean's derivative evaluates to zero at points of non-differentiability, $H_{\text{counter}}$ satisfies all derivative conditions of `is_k_submod_kernel` while being discontinuous at $x = 1$. Evaluating the induced hidden function for $n = 2, k = 2$ on two disjoint singletons yields meet value $0$, join value $1$, and individual values $0$, contradicting $k$-submodularity since $0 + 1 \not\le 0 + 0$.

  1. The slice $t \mapsto H_{\text{counter}}(t, y)$ of the step kernel $H_{\text{counter}}(x, y) = (\text{if } x \ge 1 \text{ then } 1 \text{ else } 0)$ is not differentiable at $t = 1$.

    We define $H_{\text{counter}}(x, y)$ to be $1$ if $x \ge 1$ and $0$ otherwise. If $t \mapsto H_{\text{counter}}(t, y)$ were differentiable at $t = 1$, it would be continuous there, so its left limit as $t \to 1^-$ within $(-\infty, 1)$ would equal $H_{\text{counter}}(1, y) = 1$. But on $(-\infty, 1)$, $t < 1$ and thus $H_{\text{counter}}(t, y) = 0$ identically. The limit of the constant zero function is $0$, which implies $0 = 1$ via `tendsto_const_nhds_iff`, a contradiction.

    lines 9–23

    uses inf_le_left, self_mem_nhdsWithin, not_le_of_gt, tendsto_const_nhds_iff

      let H_counter : ℝ → ℝ → ℝ := fun x _ => if x ≥ 1 then 1 else 0
      have H_counter_not_diff : ∀ y : ℝ, ¬ DifferentiableAt ℝ (fun t => H_counter t y) 1 := by
        intro y h
        have hc : ContinuousAt (fun t => H_counter t y) 1 := h.continuousAt
        have hlim : Filter.Tendsto (fun t => H_counter t y) (nhdsWithin 1 (Set.Iio 1)) (nhds (H_counter 1 y)) :=
          hc.tendsto.mono_left inf_le_left
        have h0 : (fun t => H_counter t y) =ᶠ[nhdsWithin 1 (Set.Iio 1)] (fun _ => (0 : ℝ)) := by
          filter_upwards [self_mem_nhdsWithin] with t ht
          have : ¬ (t ≥ 1) := not_le_of_gt ht
          simp [H_counter, this]
        have hlim0 : Filter.Tendsto (fun _ : ℝ => (0 : ℝ)) (nhdsWithin (1 : ℝ) (Set.Iio 1)) (nhds (H_counter 1 y)) :=
          hlim.congr' h0
        have h1 : H_counter 1 y = 1 := by simp [H_counter]
        rw [tendsto_const_nhds_iff] at hlim0
        simp [h1] at hlim0
  2. For any $y \in \mathbb{R}$ and any $x \le 1$, the derivative $\text{deriv}(t \mapsto H_{\text{counter}}(t, y))(x)$ is $0$.

    We split into cases: $x < 1$ or $x = 1$. When $x < 1$, the open set $(-\infty, 1)$ (`isOpen_Iio`) is a neighborhood of $x$ on which $t < 1$ and hence $H_{\text{counter}}(t, y) = 0$ identically; the derivative of a locally constant function is $0$ by `deriv_const`. When $x = 1$, the function is not differentiable by the previous step, so its derivative is $0$ by Mathlib's convention (`deriv_zero_of_not_differentiableAt`).

    lines 24–33

    uses lt_or_eq_of_le, IsOpen.mem_nhds, isOpen_Iio, not_le_of_gt, deriv_const, deriv_zero_of_not_differentiableAt

      have deriv_H_counter : ∀ (y : ℝ) (x : ℝ) (_ : x ≤ 1), deriv (fun t => H_counter t y) x = 0 := by
        intro y x hx
        dsimp [H_counter]
        rcases lt_or_eq_of_le hx with hx1 | rfl
        · have : (fun t => if t ≥ 1 then (1 : ℝ) else 0) =ᶠ[nhds x] (fun _ => 0) := by
            filter_upwards [IsOpen.mem_nhds isOpen_Iio hx1] with t ht
            have : ¬ (t ≥ 1) := not_le_of_gt ht
            simp [this]
          rw [this.deriv_eq, deriv_const]
        · exact deriv_zero_of_not_differentiableAt (H_counter_not_diff y)
  3. $H_{\text{counter}}$ satisfies all seven defining conditions of `is_k_submod_kernel`.

    We check each requirement: (1) $H_{\text{counter}}(0, 0) = 0$ since $0 < 1$; (2) $0 < H_{\text{counter}}(1, 0) = 1$ since $1 \ge 1$; (3) $H_{\text{counter}}(x, y) \le 1$ for all $x, y \in [0, 1]$; (4) monotonicity in $x$ holds because if $x_1 \ge 1$ then $x_2 \ge 1$; (5) monotonicity in $y$ is trivial as $H_{\text{counter}}$ ignores its second argument; (6) the derivative condition with respect to $x$ holds because both derivatives vanish by `deriv_H_counter`; (7) the derivative condition with respect to $y$ holds because slices in $y$ are constant, so their derivatives are $0$ by `deriv_const`.

    lines 34–50

    uses deriv_const

      have H_counter_kernel : is_k_submod_kernel H_counter := by
        refine ⟨by simp [H_counter], by norm_num [H_counter], ?_, ?_, ?_, ?_, ?_⟩
        · intro x y hx0 hx1 hy0 hy1
          dsimp [H_counter]
          split_ifs <;> linarith
        · intro x1 x2 y hx1 hx12 hx2 hy0 hy1
          dsimp [H_counter]
          split_ifs <;> linarith
        · intro x y1 y2 hx0 hx1 hy1 hy12 hy2
          dsimp [H_counter]
          split_ifs <;> linarith
        · intro x1 x2 y1 y2 hx1 hx12 hx2 hy1 hy12 hy2
          rw [deriv_H_counter y2 x2 hx2, deriv_H_counter y1 x1 (by linarith)]
        · intro x1 x2 y1 y2 hx1 hx12 hx2 hy1 hy12 hy2
          have e2 : (fun t => H_counter x2 t) = fun _ => H_counter x2 0 := by ext; rfl
          have e1 : (fun t => H_counter x1 t) = fun _ => H_counter x1 0 := by ext; rfl
          rw [e2, e1, deriv_const, deriv_const]
  4. For $n = 2$, $k = 2$, ground state $\sigma_2 \equiv 0$, and vectors $x_2 = (\text{some } 0, \text{none})$ and $y_2 = (\text{none}, \text{some } 0)$, their $k$-submodular meet is identically $\text{none}$ and their join is identically $\text{some } 0$.

    We define $x_2$ and $y_2$ coordinatewise on $\text{Fin } 2$. At coordinate $0$, $x_2(0) = \text{some } 0$ and $y_2(0) = \text{none}$; at coordinate $1$, $x_2(1) = \text{none}$ and $y_2(1) = \text{some } 0$. Because they never have non-$\text{none}$ values at the same coordinate, their meet is $\text{none}$ everywhere and their join combines their values to give $\text{some } 0$ everywhere, verified by exhausting all coordinates with `fin_cases`.

    lines 51–57

      let σ2 : Fin 2 → Fin 2 := fun _ => 0
      let x2 : Fin 2 → Option (Fin 2) := fun e => if e = 0 then some 0 else none
      let y2 : Fin 2 → Option (Fin 2) := fun e => if e = 1 then some 0 else none
      have meet_eq : k_submod_meet x2 y2 = fun _ => none := by
        ext e; fin_cases e <;> rfl
      have join_eq : k_submod_join x2 y2 = fun _ => some 0 := by
        ext e; fin_cases e <;> rfl
  5. Assuming the universal claim holds, the induced function $f = k\_submod\_hidden\_fn(H_{\text{counter}}, \sigma_2)$ must satisfy $f(x_2 \sqcap y_2) + f(x_2 \sqcup y_2) \le f(x_2) + f(y_2)$.

    We assume the universal statement for contradiction and specialize it to $n = 2$, $k = 2$, $\sigma = \sigma_2$, and $H = H_{\text{counter}}$ with its kernel proof. Extracting the submodularity property of $f$ and applying it to $x_2$ and $y_2$ yields the inequality $f(x_2 \sqcap y_2) + f(x_2 \sqcup y_2) \le f(x_2) + f(y_2)$, and we unfold the definition of `k_submod_hidden_fn`.

    lines 58–63

      intro hall
      have hspec := hall (by decide : 0 < 2) (by decide : 2 ≤ 2) σ2 H_counter H_counter_kernel
      dsimp only at hspec
      rcases hspec with ⟨-, -, hsub, -⟩
      have h := hsub x2 y2
      unfold k_submod_hidden_fn at h
  6. The number of matching coordinates and non-$\text{none}$ coordinates are $1$ and $1$ for $x_2$ and $y_2$, $0$ and $0$ for their meet, and $2$ and $2$ for their join.

    For each vector, the coordinates matching $\sigma_2$ and the non-$\text{none}$ coordinates are determined by case exhaustion on $\text{Fin } 2$ via `fin_cases` and `decide`. For $x_2$ and $y_2$ these subsets are the singletons $\{0\}$ and $\{1\}$ respectively, both with cardinality $1$. For the meet they are empty (cardinality $0$), and for the join they comprise the entire universe $\text{Fin } 2$ (cardinality $2$).

    lines 64–99

      have hc_x : ({e : Fin 2 | x2 e = some (σ2 e)} : Finset (Fin 2)).card = 1 := by
        have : ({e : Fin 2 | x2 e = some (σ2 e)} : Finset (Fin 2)) = {0} := by
          ext a; fin_cases a <;> decide
        rw [this]; rfl
      have hm_x : ({e : Fin 2 | x2 e ≠ none} : Finset (Fin 2)).card = 1 := by
        have : ({e : Fin 2 | x2 e ≠ none} : Finset (Fin 2)) = {0} := by
          ext a; fin_cases a <;> decide
        rw [this]; rfl
      have hc_y : ({e : Fin 2 | y2 e = some (σ2 e)} : Finset (Fin 2)).card = 1 := by
        have : ({e : Fin 2 | y2 e = some (σ2 e)} : Finset (Fin 2)) = {1} := by
          ext a; fin_cases a <;> decide
        rw [this]; rfl
      have hm_y : ({e : Fin 2 | y2 e ≠ none} : Finset (Fin 2)).card = 1 := by
        have : ({e : Fin 2 | y2 e ≠ none} : Finset (Fin 2)) = {1} := by
          ext a; fin_cases a <;> decide
        rw [this]; rfl
      have hc_m : ({e : Fin 2 | k_submod_meet x2 y2 e = some (σ2 e)} : Finset (Fin 2)).card = 0 := by
        rw [meet_eq]
        have : ({e : Fin 2 | (fun _ => (none : Option (Fin 2))) e = some (σ2 e)} : Finset (Fin 2)) = ∅ := by
          ext a; fin_cases a <;> decide
        rw [this]; rfl
      have hm_m : ({e : Fin 2 | k_submod_meet x2 y2 e ≠ none} : Finset (Fin 2)).card = 0 := by
        rw [meet_eq]
        have : ({e : Fin 2 | (fun _ => (none : Option (Fin 2))) e ≠ none} : Finset (Fin 2)) = ∅ := by
          ext a; fin_cases a <;> decide
        rw [this]; rfl
      have hc_j : ({e : Fin 2 | k_submod_join x2 y2 e = some (σ2 e)} : Finset (Fin 2)).card = 2 := by
        rw [join_eq]
        have : ({e : Fin 2 | (fun _ => some (0 : Fin 2)) e = some (σ2 e)} : Finset (Fin 2)) = Finset.univ := by
          ext a; fin_cases a <;> decide
        rw [this]; rfl
      have hm_j : ({e : Fin 2 | k_submod_join x2 y2 e ≠ none} : Finset (Fin 2)).card = 2 := by
        rw [join_eq]
        have : ({e : Fin 2 | (fun _ => some (0 : Fin 2)) e ≠ none} : Finset (Fin 2)) = Finset.univ := by
          ext a; fin_cases a <;> decide
        rw [this]; rfl
  7. The submodularity inequality simplifies to $1 \le 0$, which is impossible.

    Rewriting with the computed cardinalities evaluates the inputs to $H_{\text{counter}}$: $f(x_2 \sqcap y_2) = H_{\text{counter}}(0, 0) / 1 = 0$, $f(x_2 \sqcup y_2) = H_{\text{counter}}(1, 0) / 1 = 1$, and $f(x_2) = f(y_2) = H_{\text{counter}}(1/2, 0) / 1 = 0$. The submodularity inequality becomes $0 + 1 \le 0 + 0$, or $1 \le 0$. Numerical normalization (`norm_num`) evaluates this false inequality to close the goal.

    lines 100–102

      rw [hc_x, hm_x, hc_y, hm_y, hc_m, hm_m, hc_j, hm_j] at h
      dsimp [H_counter] at h
      norm_num at h
inf_le_left
In a semilattice with infimum, the meet $a \sqcap b$ is less than or equal to $a$.
self_mem_nhdsWithin
A set $s$ belongs to the neighborhood filter of any of its points restricted to $s$.
not_le_of_gt
If $a < b$, then $b \le a$ does not hold.
tendsto_const_nhds_iff
Along a non-trivial filter, a constant function with value $c$ converges to $d$ if and only if $c = d$.
lt_or_eq_of_le
In a partially ordered set, if $a \le b$, then either $a < b$ or $a = b$.
IsOpen.mem_nhds
If a set is open and contains $x$, then it is a neighborhood of $x$.
isOpen_Iio
The strictly lower interval $(-\infty, a)$ is open in any linear order with the order topology.
deriv_const
The derivative of a constant function at any point is zero.
deriv_zero_of_not_differentiableAt
In Mathlib, if a function is not differentiable at a point, its derivative at that point is defined to be zero.

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

theorem not_k_submod_hidden_fn_properties : ¬ (∀ {n k : ℕ} (hn : 0 < n) (hk : 2 ≤ k) (σ : Fin n → Fin k)    (H : ℝ → ℝ → ℝ) (hH : is_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  let H_counter : ℝ → ℝ → ℝ := fun x _ => if x ≥ 1 then 1 else 0  have H_counter_not_diff : ∀ y : ℝ, ¬ DifferentiableAt ℝ (fun t => H_counter t y) 1 := by    intro y h    have hc : ContinuousAt (fun t => H_counter t y) 1 := h.continuousAt    have hlim : Filter.Tendsto (fun t => H_counter t y) (nhdsWithin 1 (Set.Iio 1)) (nhds (H_counter 1 y)) :=      hc.tendsto.mono_left inf_le_left    have h0 : (fun t => H_counter t y) =ᶠ[nhdsWithin 1 (Set.Iio 1)] (fun _ => (0 : ℝ)) := by      filter_upwards [self_mem_nhdsWithin] with t ht      have : ¬ (t ≥ 1) := not_le_of_gt ht      simp [H_counter, this]    have hlim0 : Filter.Tendsto (fun _ : ℝ => (0 : ℝ)) (nhdsWithin (1 : ℝ) (Set.Iio 1)) (nhds (H_counter 1 y)) :=      hlim.congr' h0    have h1 : H_counter 1 y = 1 := by simp [H_counter]    rw [tendsto_const_nhds_iff] at hlim0    simp [h1] at hlim0  have deriv_H_counter : ∀ (y : ℝ) (x : ℝ) (_ : x ≤ 1), deriv (fun t => H_counter t y) x = 0 := by    intro y x hx    dsimp [H_counter]    rcases lt_or_eq_of_le hx with hx1 | rfl    · have : (fun t => if t ≥ 1 then (1 : ℝ) else 0) =ᶠ[nhds x] (fun _ => 0) := by        filter_upwards [IsOpen.mem_nhds isOpen_Iio hx1] with t ht        have : ¬ (t ≥ 1) := not_le_of_gt ht        simp [this]      rw [this.deriv_eq, deriv_const]    · exact deriv_zero_of_not_differentiableAt (H_counter_not_diff y)  have H_counter_kernel : is_k_submod_kernel H_counter := by    refine ⟨by simp [H_counter], by norm_num [H_counter], ?_, ?_, ?_, ?_, ?_⟩    · intro x y hx0 hx1 hy0 hy1      dsimp [H_counter]      split_ifs <;> linarith    · intro x1 x2 y hx1 hx12 hx2 hy0 hy1      dsimp [H_counter]      split_ifs <;> linarith    · intro x y1 y2 hx0 hx1 hy1 hy12 hy2      dsimp [H_counter]      split_ifs <;> linarith    · intro x1 x2 y1 y2 hx1 hx12 hx2 hy1 hy12 hy2      rw [deriv_H_counter y2 x2 hx2, deriv_H_counter y1 x1 (by linarith)]    · intro x1 x2 y1 y2 hx1 hx12 hx2 hy1 hy12 hy2      have e2 : (fun t => H_counter x2 t) = fun _ => H_counter x2 0 := by ext; rfl      have e1 : (fun t => H_counter x1 t) = fun _ => H_counter x1 0 := by ext; rfl      rw [e2, e1, deriv_const, deriv_const]  let σ2 : Fin 2 → Fin 2 := fun _ => 0  let x2 : Fin 2 → Option (Fin 2) := fun e => if e = 0 then some 0 else none  let y2 : Fin 2 → Option (Fin 2) := fun e => if e = 1 then some 0 else none  have meet_eq : k_submod_meet x2 y2 = fun _ => none := by    ext e; fin_cases e <;> rfl  have join_eq : k_submod_join x2 y2 = fun _ => some 0 := by    ext e; fin_cases e <;> rfl  intro hall  have hspec := hall (by decide : 0 < 2) (by decide : 2 ≤ 2) σ2 H_counter H_counter_kernel  dsimp only at hspec  rcases hspec with ⟨-, -, hsub, -⟩  have h := hsub x2 y2  unfold k_submod_hidden_fn at h  have hc_x : ({e : Fin 2 | x2 e = some (σ2 e)} : Finset (Fin 2)).card = 1 := by    have : ({e : Fin 2 | x2 e = some (σ2 e)} : Finset (Fin 2)) = {0} := by      ext a; fin_cases a <;> decide    rw [this]; rfl  have hm_x : ({e : Fin 2 | x2 e ≠ none} : Finset (Fin 2)).card = 1 := by    have : ({e : Fin 2 | x2 e ≠ none} : Finset (Fin 2)) = {0} := by      ext a; fin_cases a <;> decide    rw [this]; rfl  have hc_y : ({e : Fin 2 | y2 e = some (σ2 e)} : Finset (Fin 2)).card = 1 := by    have : ({e : Fin 2 | y2 e = some (σ2 e)} : Finset (Fin 2)) = {1} := by      ext a; fin_cases a <;> decide    rw [this]; rfl  have hm_y : ({e : Fin 2 | y2 e ≠ none} : Finset (Fin 2)).card = 1 := by    have : ({e : Fin 2 | y2 e ≠ none} : Finset (Fin 2)) = {1} := by      ext a; fin_cases a <;> decide    rw [this]; rfl  have hc_m : ({e : Fin 2 | k_submod_meet x2 y2 e = some (σ2 e)} : Finset (Fin 2)).card = 0 := by    rw [meet_eq]    have : ({e : Fin 2 | (fun _ => (none : Option (Fin 2))) e = some (σ2 e)} : Finset (Fin 2)) = ∅ := by      ext a; fin_cases a <;> decide    rw [this]; rfl  have hm_m : ({e : Fin 2 | k_submod_meet x2 y2 e ≠ none} : Finset (Fin 2)).card = 0 := by    rw [meet_eq]    have : ({e : Fin 2 | (fun _ => (none : Option (Fin 2))) e ≠ none} : Finset (Fin 2)) = ∅ := by      ext a; fin_cases a <;> decide    rw [this]; rfl  have hc_j : ({e : Fin 2 | k_submod_join x2 y2 e = some (σ2 e)} : Finset (Fin 2)).card = 2 := by    rw [join_eq]    have : ({e : Fin 2 | (fun _ => some (0 : Fin 2)) e = some (σ2 e)} : Finset (Fin 2)) = Finset.univ := by      ext a; fin_cases a <;> decide    rw [this]; rfl  have hm_j : ({e : Fin 2 | k_submod_join x2 y2 e ≠ none} : Finset (Fin 2)).card = 2 := by    rw [join_eq]    have : ({e : Fin 2 | (fun _ => some (0 : Fin 2)) e ≠ none} : Finset (Fin 2)) = Finset.univ := by      ext a; fin_cases a <;> decide    rw [this]; rfl  rw [hc_x, hm_x, hc_y, hm_y, hc_m, hm_m, hc_j, hm_j] at h  dsimp [H_counter] at h  norm_num at h
See it in the graphDiscuss this resultChallenge it