not_k_submod_hidden_fn_properties
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$.
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.
uses
inf_le_left,self_mem_nhdsWithin,not_le_of_gt,tendsto_const_nhds_ifflet 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
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`).
uses
lt_or_eq_of_le,IsOpen.mem_nhds,isOpen_Iio,not_le_of_gt,deriv_const,deriv_zero_of_not_differentiableAthave 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)
$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`.
uses
deriv_consthave 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]
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`.
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
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`.
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
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$).
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
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.
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.
- In Lean's Mathlib, `deriv f x` evaluates to zero by definition when `f` is not differentiable at `x`. The counterexample exploits this formal convention: the discontinuous step kernel $H_{\text{counter}}$ fails to be differentiable at $x = 1$, yet satisfies the derivative conditions of `is_k_submod_kernel` because its derivatives vanish identically on $[0, 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.
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