AFTD Auto-Formalizing Theoretical Domains

discrete_max_principle_step

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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.

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

    lines 11–15

    uses Finset.mem_filter, Finset.mem_univ

      intro S
      have hmS : m ∈ S := by
        rw [Finset.mem_filter]
        exact ⟨Finset.mem_univ m, hm⟩
      have hS_nonempty : S.Nonempty := ⟨m, hmS⟩
  2. 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.

    lines 16–20

    uses Finset.mem_filter

      have h0_not_mem : (0 : Fin (k + 1)) ∉ S := by
        rw [Finset.mem_filter]
        rintro ⟨-, h0⟩
        rw [hw0] at h0
        linarith
  3. 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.

    lines 21–28

    uses Finset.mem_filter, Finset.mem_univ, Fin.exists_succ_eq.mpr

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

    lines 29–34

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

    lines 35–39

    uses Finset.mem_filter, Finset.mem_univ

      refine ⟨?_, ?_⟩
      · 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

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