k_submod_kernel_proj
The coordinate projection function (fun x _ => x) : ℝ → ℝ → ℝ satisfies is_k_submod_kernel.
Statement
theorem k_submod_kernel_proj : is_k_submod_kernel (fun x _ => x)
- Source
- arXiv:2610.26677, Lemma 2.1
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
- Used by 1
- c1_k_submod_kernel_projThe first coordinate projection function (fun x _ => x) : ℝ → ℝ → ℝ satisfies is_c1_k_submod_kernel.
Read back from the Lean
The function $H : \mathbb{R} \to \mathbb{R} \to \mathbb{R}$ defined by $H(x, y) = x$ (the projection onto the first argument) satisfies is_k_submod_kernel.
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 coordinate projection function $H(x, y) = x$ is shown to be a $k$-submodular kernel by directly verifying the seven conditions in the definition. Normalization at the origin, strict positivity at $(1, 0)$, boundedness by $H(1, 0)$, and monotonicity in both arguments are either trivial equalities or follow immediately from domain hypotheses and order reflexivity. The two derivative inequalities reduce to $1 \le 1$ and $0 \le 0$, respectively, because the derivative of the identity is identically $1$ and the derivative of a constant is identically $0$.
The definition of `is_k_submod_kernel` expands to seven conditions for the projection function $H(x, y) = x$.
We simplify the definition of a $k$-submodular kernel applied to $H(x, y) = x$. This reduces the goal to proving seven properties: $0 = 0$, $0 < 1$, $x \le 1$ for all $x \in [0, 1]$, $x_1 \le x_2$ whenever $x_1 \le x_2$, $x \le x$, and two inequalities on partial derivatives.
dsimp [is_k_submod_kernel]The first five conditions (normalization, positivity, upper bound by $H(1, 0)$, and monotonicity in each argument) hold.
The equality $0 = 0$ holds by reflexivity (`rfl`). Strict positivity $0 < 1$ is given by `zero_lt_one`. The upper bound $x \le 1$ and monotonicity in the first coordinate $x_1 \le x_2$ follow directly from the corresponding hypotheses on the domain. Monotonicity in the second coordinate $x \le x$ holds by reflexivity of the order (`le_rfl`).
uses
zero_lt_one,le_rflrefine ⟨rfl, zero_lt_one, fun _ _ _ hx1 _ _ => hx1, fun _ _ _ _ hx12 _ _ _ => hx12, fun _ _ _ _ _ _ _ _ => le_rfl,
The derivative inequality with respect to the first argument holds: $\frac{\partial H}{\partial x}(x_2, y_2) \le \frac{\partial H}{\partial x}(x_1, y_1)$.
For $H(t, y) = t$, the derivative with respect to $t$ is identically $1$ everywhere by `deriv_id''`. The required inequality thus simplifies to $1 \le 1$, which holds by reflexivity (`le_refl`).
uses
deriv_id'',le_reflfun _ _ _ _ _ _ _ _ _ _ => by simp only [deriv_id'', le_refl],
The derivative inequality with respect to the second argument holds: $\frac{\partial H}{\partial y}(x_2, y_2) \le \frac{\partial H}{\partial y}(x_1, y_1)$.
For $H(x, t) = x$, which is constant with respect to $t$, the derivative is identically $0$ everywhere by `deriv_const`. The required inequality simplifies to $0 \le 0$, which holds by reflexivity (`le_refl`).
uses
deriv_const,le_reflfun _ _ _ _ _ _ _ _ _ _ => by simp only [deriv_const, le_refl]⟩
zero_lt_one- In any ordered structure with zero and nonzero one, zero is strictly less than one ($0 < 1$).
le_rfl- The preorder relation $\le$ is reflexive: $a \le a$ for any element $a$.
le_refl- The preorder relation $\le$ is reflexive: $a \le a$ for any element $a$.
deriv_id''- The derivative of the identity function $t \mapsto t$ is the constant function $1$.
deriv_const- The derivative of a constant function at any point is $0$.
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 coordinate projection function satisfies the kernel conditions. -/theorem k_submod_kernel_proj : is_k_submod_kernel (fun x _ => x) := by dsimp [is_k_submod_kernel] refine ⟨rfl, zero_lt_one, fun _ _ _ hx1 _ _ => hx1, fun _ _ _ _ hx12 _ _ _ => hx12, fun _ _ _ _ _ _ _ _ => le_rfl, fun _ _ _ _ _ _ _ _ _ _ => by simp only [deriv_id'', le_refl], fun _ _ _ _ _ _ _ _ _ _ => by simp only [deriv_const, le_refl]⟩