discrete_max_principle_step
If w_ext(0) = 0 and 2*w_ext(l.succ) = w_ext(u l.succ) + w_ext(v l.succ) for all l, and V > 0 is the maximum of w_ext, then S = {j | w_ext j = V} is nonempty, 0 ∉ S, and S is closed under u and v.
Statement
theorem discrete_max_principle_step (k : ℕ) (u v : Fin (k + 1) → Fin (k + 1)) (w_ext : Fin (k + 1) → ℤ) (hw0 : w_ext 0 = 0) (hmid : ∀ l : Fin k, 2 * w_ext l.succ = w_ext (u l.succ) + w_ext (v l.succ)) (V : ℤ) (hV : 0 < V) (m : Fin (k + 1)) (hm : w_ext m = V) (hmax : ∀ j, w_ext j ≤ V) : let S := Finset.univ.filter (fun j => w_ext j = V) S.Nonempty ∧ (0 : Fin (k + 1)) ∉ S ∧ ∀ i ∈ S, u i ∈ S ∧ v i ∈ S
- Source
- step towards finset_midpoint_balanced_exists_nonzero_minor
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- Used by 1
- finset_midpoint_balanced_exists_nonzero_minorEvery nonempty midpoint-balanced subset B of ZMod p contains an inclusion-minimal balanced subconfiguration of size k+1 ≤ |B| with k > 0…
The proof, explained
The theorem is a discrete maximum principle: if a function on indices Fin (k + 1) satisfies a midpoint averaging condition at interior (successor) points and vanishes at the boundary 0, its argmax set S at a strictly positive maximum V cannot contain 0 and is closed under the neighbor maps u and v. First, S is nonempty because the maximum V is achieved at m, and 0 ∉ S because w_ext 0 = 0 < V. For any i ∈ S, the fact that 0 ∉ S implies i ≠ 0, so i is a successor index l.succ where the midpoint equation applies. Since the two neighbors average to V and are bounded above by V, both neighbors must achieve the maximum V, so u i ∈ S and v i ∈ S.
The set S is nonempty.
We introduce S as the set of elements where w_ext attains the value V. By assumption, w_ext m = V, so m satisfies the membership condition for S; hence m ∈ S and S is nonempty.
uses
Finset.mem_filter,Finset.mem_univintro S have hmS : m ∈ S := by rw [Finset.mem_filter] exact ⟨Finset.mem_univ m, hm⟩ have hS_nonempty : S.Nonempty := ⟨m, hmS⟩
0 ∉ S.
If 0 were in S, then w_ext 0 = V. But by assumption w_ext 0 = 0 and V > 0, which would imply 0 = V > 0, an arithmetic contradiction.
uses
Finset.mem_filterhave h0_not_mem : (0 : Fin (k + 1)) ∉ S := by rw [Finset.mem_filter] rintro ⟨-, h0⟩ rw [hw0] at h0 linarith
It suffices to show that S is closed under u and v, and any element i ∈ S can be written as l.succ for some l : Fin k.
With nonemptiness and 0 ∉ S established, it remains to prove that u i ∈ S and v i ∈ S for all i ∈ S. Take an arbitrary i ∈ S, so w_ext i = V. Since 0 ∉ S, i ≠ 0. Every non-zero element of Fin (k + 1) is the successor of some index l : Fin k, so we can write i = l.succ.
uses
Finset.mem_filter,Finset.mem_univ,Fin.exists_succ_eq.mprrefine ⟨hS_nonempty, h0_not_mem, ?_⟩ intro i hi rw [Finset.mem_filter] at hi obtain ⟨-, hwi⟩ := hi have hne : i ≠ 0 := by rintro rfl exact h0_not_mem (by rw [Finset.mem_filter]; exact ⟨Finset.mem_univ 0, hwi⟩) obtain ⟨l, rfl⟩ := Fin.exists_succ_eq.mpr hne
w_ext (u l.succ) = V and w_ext (v l.succ) = V.
Applying the discrete midpoint equation at l.succ gives 2 * w_ext l.succ = w_ext (u l.succ) + w_ext (v l.succ). Since w_ext l.succ = V, the sum is 2 * V. Furthermore, because V is the maximum of w_ext, both w_ext (u l.succ) ≤ V and w_ext (v l.succ) ≤ V. Two values bounded above by V whose sum is 2 * V must both equal V.
have hsum : 2 * V = w_ext (u l.succ) + w_ext (v l.succ) := by linarith [hmid l] have hu_le : w_ext (u l.succ) ≤ V := hmax (u l.succ) have hv_le : w_ext (v l.succ) ≤ V := hmax (v l.succ) have hu_eq : w_ext (u l.succ) = V := by linarith have hv_eq : w_ext (v l.succ) = V := by linarith
u i ∈ S and v i ∈ S, completing the proof.
Because w_ext (u l.succ) = V and w_ext (v l.succ) = V, both u l.succ and v l.succ satisfy the defining condition of S.
uses
Finset.mem_filter,Finset.mem_univrefine ⟨?_, ?_⟩ · rw [Finset.mem_filter] exact ⟨Finset.mem_univ _, hu_eq⟩ · rw [Finset.mem_filter] exact ⟨Finset.mem_univ _, hv_eq⟩
Finset.mem_filter- an element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate
Finset.mem_univ- every element of a finite type belongs to the universal finset Finset.univ
Fin.exists_succ_eq.mpr- if an element of Fin (n + 1) is non-zero, then it is the successor of some element of Fin n
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.
/-- For an integer vector w_ext vanishing at 0 and satisfying the discrete midpoint harmonic equation at all succ indices, the argmax of a strictly positive maximum does not contain 0 and is closed under the midpoint index maps u and v. -/theorem discrete_max_principle_step (k : ℕ) (u v : Fin (k + 1) → Fin (k + 1)) (w_ext : Fin (k + 1) → ℤ) (hw0 : w_ext 0 = 0) (hmid : ∀ l : Fin k, 2 * w_ext l.succ = w_ext (u l.succ) + w_ext (v l.succ)) (V : ℤ) (hV : 0 < V) (m : Fin (k + 1)) (hm : w_ext m = V) (hmax : ∀ j, w_ext j ≤ V) : let S := Finset.univ.filter (fun j => w_ext j = V) S.Nonempty ∧ (0 : Fin (k + 1)) ∉ S ∧ ∀ i ∈ S, u i ∈ S ∧ v i ∈ S := by intro S have hmS : m ∈ S := by rw [Finset.mem_filter] exact ⟨Finset.mem_univ m, hm⟩ have hS_nonempty : S.Nonempty := ⟨m, hmS⟩ have h0_not_mem : (0 : Fin (k + 1)) ∉ S := by rw [Finset.mem_filter] rintro ⟨-, h0⟩ rw [hw0] at h0 linarith refine ⟨hS_nonempty, h0_not_mem, ?_⟩ intro i hi rw [Finset.mem_filter] at hi obtain ⟨-, hwi⟩ := hi have hne : i ≠ 0 := by rintro rfl exact h0_not_mem (by rw [Finset.mem_filter]; exact ⟨Finset.mem_univ 0, hwi⟩) obtain ⟨l, rfl⟩ := Fin.exists_succ_eq.mpr hne have hsum : 2 * V = w_ext (u l.succ) + w_ext (v l.succ) := by linarith [hmid l] have hu_le : w_ext (u l.succ) ≤ V := hmax (u l.succ) have hv_le : w_ext (v l.succ) ≤ V := hmax (v l.succ) have hu_eq : w_ext (u l.succ) = V := by linarith have hv_eq : w_ext (v l.succ) = V := by linarith refine ⟨?_, ?_⟩ · rw [Finset.mem_filter] exact ⟨Finset.mem_univ _, hu_eq⟩ · rw [Finset.mem_filter] exact ⟨Finset.mem_univ _, hv_eq⟩