finset_midpoint_balanced_exists_nonzero_minor
Every nonempty midpoint-balanced subset B of ZMod p contains an inclusion-minimal balanced subconfiguration of size k+1 ≤ |B| with k > 0 whose certificate matrix has at least one non-vanishing minor.
Statement
theorem finset_midpoint_balanced_exists_nonzero_minor {p : ℕ} [Fact p.Prime] (B : Finset (ZMod p)) (hB : finset_is_midpoint_balanced B) : ∃ (k : ℕ) (hk0 : 0 < k) (hk : k + 1 ≤ B.card) (u v : Fin (k + 1) → Fin (k + 1)) (b : Fin (k + 1) → ZMod p) (hinj : Function.Injective b) (hmid : ∀ i, 2 * b i = b (u i) + b (v i)) (i₀ j₀ : Fin (k + 1)), ((Matrix.of fun (i j : Fin (k + 1)) => (if j = i then (2 : ℤ) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix i₀.succAbove j₀.succAbove).det ≠ 0
- Source
- step towards finset_card_ge_one_add_clog_of_midpoint_balanced
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- finset_midpoint_balanced_card_ge_threeEvery midpoint-balanced finite subset of an additive commutative monoid has cardinality at least 3.
- finset_exists_minimal_midpoint_balancedEvery midpoint-balanced finite set B contains an inclusion-minimal midpoint-balanced subset B₀.
- discrete_max_principle_stepIf 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…
- finset_image_balanced_of_closedIf b is injective, u, v are midpoint witnesses with u i ≠ i, v i ≠ i, u i ≠ v i, and S is a nonempty subset closed under u and v, then…
- finset_is_midpoint_balancedA finite set B is balanced: it is nonempty and every b ∈ B satisfies 2b = u + v for two distinct elements u, v of B other than b.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- finset_card_ge_one_add_clog_of_midpoint_balancedFor a prime p, every nonempty balanced subset B of Z/pZ has |B| ≥ 1 + ⌈log₂ p⌉.
The proof, explained
To find a subconfiguration with a non-vanishing minor, we first extract an inclusion-minimal midpoint-balanced subset B₀ ⊆ B and index its k + 1 elements via an injection b. For each element, we choose the two distinct neighbors witnessing the midpoint balance and form the Laplacian-like certificate matrix. If the k × k principal minor obtained by deleting the index 0 vanishes, there is a non-trivial integer vector in its kernel, which yields a non-trivial harmonic function on {1, ..., k} vanishing at 0. By the discrete maximum principle, the set of vertices attaining the strictly positive maximum is closed under the neighbor maps, so its image under b forms a strictly smaller balanced subconfiguration of B₀, contradicting the minimality of B₀.
The sum of f(j) over all j ∈ Fin (k + 1) is zero.
We evaluate the l-th row equation of M w = 0. Extending w by setting w_ext(0) = 0, the term at index 0 vanishes, and the sum over successor indices equals the l-th component of M w = 0.
uses
congr_fun,Fin.sum_univ_succ,Fin.cons_zero,mul_zero,zero_add,Finset.sum_congr,Fin.cons_succintro w_ext l have hl := congr_fun hM l dsimp [Matrix.mulVec, dotProduct] at hl let f : Fin (k + 1) → ℤ := fun j => ((if j = l.succ then (2 : ℤ) else 0) - (if j = u l.succ then 1 else 0) - (if j = v l.succ then 1 else 0)) * w_ext j have hsplit : ∑ j : Fin (k + 1), f j = 0 := by rw [Fin.sum_univ_succ f] have h0 : f 0 = 0 := by dsimp [f, w_ext] rw [Fin.cons_zero, mul_zero] rw [h0, zero_add] have heq : (∑ m : Fin k, f m.succ) = ∑ m : Fin k, (((if m.succ = l.succ then (2 : ℤ) else 0) - (if m.succ = u l.succ then 1 else 0) - (if m.succ = v l.succ then 1 else 0)) * w m) := by apply Finset.sum_congr rfl intro m _ dsimp [f, w_ext] rw [Fin.cons_succ] rw [heq, hl]
The sum of f(j) over all j expands to 2 * w_ext(l.succ) - w_ext(u(l.succ)) - w_ext(v(l.succ)).
Rewriting each f(j) by distributing the multiplication over the indicator terms and summing each indicator separately over Fin (k + 1) isolates the values of w_ext at l.succ, u(l.succ), and v(l.succ).
uses
sub_sub,Finset.sum_sub_distrib,Finset.sum_add_distrib,Finset.sum_ite_eq'have hsum : ∑ j : Fin (k + 1), f j = 2 * w_ext l.succ - w_ext (u l.succ) - w_ext (v l.succ) := by have h1 : ∀ j : Fin (k + 1), f j = (if j = l.succ then 2 * w_ext j else 0) - (if j = u l.succ then w_ext j else 0) - (if j = v l.succ then w_ext j else 0) := by intro j dsimp [f] split_ifs <;> ring simp_rw [h1, sub_sub] rw [Finset.sum_sub_distrib, Finset.sum_add_distrib] simp [Finset.sum_ite_eq']
The harmonicity equation 2 * w_ext(l.succ) = w_ext(u(l.succ)) + w_ext(v(l.succ)) holds. automation
Linear arithmetic combines the two expressions for the sum of f(j), which must both be zero, yielding the harmonicity identity.
linarith [hsplit, hsum]The extended vector w_ext has a non-zero coordinate at some successor index.
Since w ≠ 0, there is some coordinate l with w(l) ≠ 0. The extension w_ext at l.succ equals w(l), so it is also non-zero.
uses
Fin.cons_succhave hw_ex : ∃ l : Fin k, w l ≠ 0 := by by_contra h push Not at h exact hw (funext h) obtain ⟨l, hl⟩ := hw_ex let w_ext : Fin (k + 1) → ℤ := Fin.cons 0 w have hl_ext : w_ext l.succ ≠ 0 := by dsimp [w_ext] rw [Fin.cons_succ] exact hl
There exists an extension w' vanishing at 0, harmonic on Fin k, with a strictly positive coordinate.
By trichotomy, w_ext(l.succ) is either negative or positive. If negative, we take w' = -w_ext, which is harmonic and positive at l.succ; if positive, we take w' = w_ext.
uses
lt_or_gt_of_nercases lt_or_gt_of_ne hl_ext with hneg | hpos · refine ⟨-w_ext, ?_, ?_, l.succ, ?_⟩ · simp [w_ext] · intro l' dsimp linarith [h_harm l'] · dsimp linarith · refine ⟨w_ext, ?_, h_harm, l.succ, hpos⟩ simp [w_ext]
B contains an inclusion-minimal midpoint-balanced subset B₀ with cardinality k + 1 ≥ 3, so k > 0 and k + 1 ≤ |B|.
We extract an inclusion-minimal balanced subset B₀ ⊆ B. Any midpoint-balanced subset has at least 3 elements, so setting k = |B₀| - 1 gives k > 0 and k + 1 ≤ |B|.
uses
finset_exists_minimal_midpoint_balanced,finset_midpoint_balanced_card_ge_three,Finset.card_le_cardobtain ⟨B₀, hB₀B, hB₀bal, hB₀min⟩ := finset_exists_minimal_midpoint_balanced B hB have _hcard3 := finset_midpoint_balanced_card_ge_three B₀ hB₀bal let k := B₀.card - 1 have hk0 : 0 < k := by dsimp [k]; omega have hkeq : k + 1 = B₀.card := by dsimp [k]; omega have hkB : k + 1 ≤ B.card := by rw [hkeq] exact Finset.card_le_card hB₀B
We obtain an injective indexing b : Fin (k + 1) → ZMod p whose image is B₀.
Since k + 1 = |B₀|, there is a bijection between Fin (k + 1) and the subtype B₀. Composing this with the inclusion into ZMod p gives an injective map b whose image is exactly B₀.
uses
finCongr,Finset.equivFin,Subtype.ext,Set.mem_univhave e1 : Fin (k + 1) ≃ Fin B₀.card := (finCongr hkeq.symm).symm have e2 : Fin B₀.card ≃ ↥B₀ := (Finset.equivFin B₀).symm let e : Fin (k + 1) ≃ ↥B₀ := e1.trans e2 let b : Fin (k + 1) → ZMod p := fun i => (e i : ZMod p) have hinj : Function.Injective b := by intro x y hxy have : e x = e y := Subtype.ext hxy exact e.injective this have h_range : Finset.univ.image b = B₀ := by ext a simp only [Finset.mem_image, Finset.mem_univ, true_and] constructor · rintro ⟨i, rfl⟩ exact (e i).2 · intro ha have : (⟨a, ha⟩ : ↥B₀) ∈ Set.range e := e.surjective.range_eq ▸ Set.mem_univ _ obtain ⟨i, hi⟩ := this refine ⟨i, ?_⟩ dsimp [b] rw [hi]
Each element b(i) in B₀ has distinct balanced neighbors b(u(i)) and b(v(i)) in B₀.
By the midpoint-balanced property of B₀, every element b(i) is the midpoint of two other distinct elements of B₀. Using the bijection b, we pull back these elements to index functions u, v : Fin (k + 1) → Fin (k + 1).
uses
Finset.mem_image_of_mem,Finset.mem_image,two_mulhave h_each : ∀ i : Fin (k + 1), ∃ (ui vi : Fin (k + 1)), ui ≠ i ∧ vi ≠ i ∧ ui ≠ vi ∧ 2 * b i = b ui + b vi ∧ b i + b i = b ui + b vi := by intro i have hbi : b i ∈ B₀ := by rw [← h_range] exact Finset.mem_image_of_mem b (Finset.mem_univ i) obtain ⟨u', hu', v', hv', hune, hvne, huvne, hmid'⟩ := hB₀bal.2 (b i) hbi rw [← h_range, Finset.mem_image] at hu' hv' obtain ⟨ui, _, rfl⟩ := hu' obtain ⟨vi, _, rfl⟩ := hv' have hui : ui ≠ i := fun h => hune (by rw [h]) have hvi : vi ≠ i := fun h => hvne (by rw [h]) have huvi : ui ≠ vi := fun h => huvne (by rw [h]) have h2 : 2 * b i = b ui + b vi := by rw [two_mul, hmid'] exact ⟨ui, vi, hui, hvi, huvi, h2, hmid'⟩ choose u v hu hv huv hmid hmid_add using h_each
If the principal minor det(M) vanishes, there is a harmonic integer vector w' vanishing at 0 with a positive value.
A vanishing determinant over the integers implies the existence of a non-trivial vector w in the kernel of M. By the previous lemmas, w extends to a vector w' vanishing at 0, harmonic on the remaining indices, and strictly positive somewhere.
uses
Matrix.exists_mulVec_eq_zero_iff,finset_midpoint_balanced_exists_nonzero_minor_mulVec_zero_harmonic,finset_midpoint_balanced_exists_nonzero_minor_pos_harmonicrefine ⟨k, hk0, hkB, u, v, b, hinj, hmid, 0, 0, ?_⟩ let M := (Matrix.of fun (i j : Fin (k + 1)) => (if j = i then (2 : ℤ) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix (0 : Fin (k + 1)).succAbove (0 : Fin (k + 1)).succAbove intro hdet have h_kernel := (@Matrix.exists_mulVec_eq_zero_iff (Fin k) _ ℤ _ _ M _).symm.mp hdet obtain ⟨w, hw_ne, hw_mul⟩ := h_kernel have h_harm := finset_midpoint_balanced_exists_nonzero_minor_mulVec_zero_harmonic k u v w hw_mul obtain ⟨w', hw'0, hw'_harm, j, hjpos⟩ := finset_midpoint_balanced_exists_nonzero_minor_pos_harmonic k u v w hw_ne h_harm
The set S where w' achieves its positive maximum does not contain 0 and is closed under u and v.
Let V > 0 be the maximum value of w', achieved at some index m. Applying the discrete maximum principle, the argmax set S cannot contain 0 (where w'(0) = 0 < V), and harmonicity implies that whenever i ∈ S, its neighbors u(i) and v(i) must also lie in S.
uses
Finset.exists_max_image,Finset.univ_nonempty,lt_of_lt_of_le,Finset.mem_univ,discrete_max_principle_stepobtain ⟨m, _, hm⟩ := Finset.exists_max_image Finset.univ w' Finset.univ_nonempty have hV : 0 < w' m := lt_of_lt_of_le hjpos (hm j (Finset.mem_univ j)) have hmax : ∀ j, w' j ≤ w' m := fun j => hm j (Finset.mem_univ j) have hstep := discrete_max_principle_step k u v w' hw'0 hw'_harm (w' m) hV m rfl hmax rcases hstep with ⟨hSne, h0notinS, hS_closed⟩
The image b(S) equals B₀, which forces 0 ∈ S, a contradiction.
Because S is nonempty and closed under u and v, its image b(S) is midpoint-balanced. Since b(S) ⊆ B₀, minimality of B₀ forces b(S) = B₀. Hence b(0) ∈ b(S), and injectivity of b implies 0 ∈ S, contradicting 0 ∉ S. Therefore det(M) ≠ 0.
uses
finset_image_balanced_of_closed,Finset.image_subset_image,Finset.subset_univ,Finset.mem_image_of_mem,Finset.mem_univ,Finset.mem_imagelet S := Finset.univ.filter (fun j => w' j = w' m) have hS_bal : finset_is_midpoint_balanced (S.image b) := finset_image_balanced_of_closed b hinj u v hu hv huv hmid_add S hSne hS_closed have h_sub : S.image b ⊆ B₀ := by rw [← h_range] exact Finset.image_subset_image (Finset.subset_univ S) have heq : S.image b = B₀ := hB₀min (S.image b) h_sub hS_bal have hb0_in : b 0 ∈ B₀ := by rw [← h_range] exact Finset.mem_image_of_mem b (Finset.mem_univ 0) rw [← heq, Finset.mem_image] at hb0_in obtain ⟨j₀, hj₀, hj₀0⟩ := hb0_in have : j₀ = 0 := hinj hj₀0 exact h0notinS (this ▸ hj₀)
congr_fun- If two functions are equal, their values on any input are equal.
Fin.sum_univ_succ- Splits a sum over Fin (n + 1) into the term at 0 and the sum over the successors.
Fin.cons_zero- The value of Fin.cons at 0 is the prepended head.
mul_zero- Multiplying any element by zero on the right gives zero.
zero_add- Adding zero on the left is the identity.
Finset.sum_congr- Sums of equal functions over equal sets are equal.
Fin.cons_succ- The value of Fin.cons at a successor index is the corresponding element of the tail.
sub_sub- Subtracting b and then c is equivalent to subtracting b + c.
Finset.sum_sub_distrib- The sum of differences is the difference of sums.
Finset.sum_add_distrib- The sum of sums is the sum of the individual sums.
Finset.sum_ite_eq'- The sum of an indicator function over a finite set equals the function value if the element is in the set, and zero otherwise.
lt_or_gt_of_ne- Two unequal elements in a linear order satisfy either a < b or b < a.
finset_exists_minimal_midpoint_balanced- Every nonempty midpoint-balanced finite set contains an inclusion-minimal midpoint-balanced subset.
finset_midpoint_balanced_card_ge_three- A midpoint-balanced finite set has cardinality at least three.
Finset.card_le_card- A subset has cardinality at most that of the superset.
finCongr- Equivalence between Fin n and Fin m induced by an equality n = m.
Finset.equivFin- A finite set s of size n is in bijection with Fin n.
Subtype.ext- Two subtypes are equal if their underlying values are equal.
Finset.mem_univ- Every element belongs to the universal finset.
Finset.mem_image_of_mem- Membership in the image of a finset under a function.
two_mul- Twice an element equals the element added to itself.
Matrix.exists_mulVec_eq_zero_iff- Over an integral domain, a square matrix has non-trivial kernel if and only if its determinant is zero.
finset_midpoint_balanced_exists_nonzero_minor_mulVec_zero_harmonic- A zero vector in the kernel of the certificate submatrix yields a harmonic extension.
finset_midpoint_balanced_exists_nonzero_minor_pos_harmonic- A nonzero harmonic vector can be chosen to have a strictly positive maximum.
Finset.exists_max_image- A function on a nonempty finite set attains its maximum value.
Finset.univ_nonempty- The universal set of a nonempty finite type is nonempty.
lt_of_lt_of_le- Transitivity of strict and non-strict inequality: a < b and b ≤ c imply a < c.
discrete_max_principle_step- The discrete maximum principle: the argmax set of a harmonic function is nonempty, avoids zero, and is closed under the neighbor maps.
finset_image_balanced_of_closed- The image of a closed subset under an injective map preserving midpoints is midpoint-balanced.
Finset.image_subset_image- Taking images preserves set inclusion.
Finset.subset_univ- Every finset is a subset of the universal finset.
Finset.mem_image- Characterization of elements in the image of a finset.
Set.mem_univ- Every element belongs to the universal set.
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.
lemma finset_midpoint_balanced_exists_nonzero_minor_mulVec_zero_harmonic (k : ℕ) (u v : Fin (k + 1) → Fin (k + 1)) (w : Fin k → ℤ) (hM : Matrix.mulVec ((Matrix.of fun (i j : Fin (k + 1)) => (if j = i then (2 : ℤ) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix (0 : Fin (k + 1)).succAbove (0 : Fin (k + 1)).succAbove) w = 0) : let w_ext : Fin (k + 1) → ℤ := Fin.cons 0 w ∀ l : Fin k, 2 * w_ext l.succ = w_ext (u l.succ) + w_ext (v l.succ) := by intro w_ext l have hl := congr_fun hM l dsimp [Matrix.mulVec, dotProduct] at hl let f : Fin (k + 1) → ℤ := fun j => ((if j = l.succ then (2 : ℤ) else 0) - (if j = u l.succ then 1 else 0) - (if j = v l.succ then 1 else 0)) * w_ext j have hsplit : ∑ j : Fin (k + 1), f j = 0 := by rw [Fin.sum_univ_succ f] have h0 : f 0 = 0 := by dsimp [f, w_ext] rw [Fin.cons_zero, mul_zero] rw [h0, zero_add] have heq : (∑ m : Fin k, f m.succ) = ∑ m : Fin k, (((if m.succ = l.succ then (2 : ℤ) else 0) - (if m.succ = u l.succ then 1 else 0) - (if m.succ = v l.succ then 1 else 0)) * w m) := by apply Finset.sum_congr rfl intro m _ dsimp [f, w_ext] rw [Fin.cons_succ] rw [heq, hl] have hsum : ∑ j : Fin (k + 1), f j = 2 * w_ext l.succ - w_ext (u l.succ) - w_ext (v l.succ) := by have h1 : ∀ j : Fin (k + 1), f j = (if j = l.succ then 2 * w_ext j else 0) - (if j = u l.succ then w_ext j else 0) - (if j = v l.succ then w_ext j else 0) := by intro j dsimp [f] split_ifs <;> ring simp_rw [h1, sub_sub] rw [Finset.sum_sub_distrib, Finset.sum_add_distrib] simp [Finset.sum_ite_eq'] linarith [hsplit, hsum]lemma finset_midpoint_balanced_exists_nonzero_minor_pos_harmonic (k : ℕ) (u v : Fin (k + 1) → Fin (k + 1)) (w : Fin k → ℤ) (hw : w ≠ 0) (h_harm : ∀ l : Fin k, 2 * (Fin.cons 0 w : Fin (k + 1) → ℤ) l.succ = (Fin.cons 0 w : Fin (k + 1) → ℤ) (u l.succ) + (Fin.cons 0 w : Fin (k + 1) → ℤ) (v l.succ)) : ∃ (w' : Fin (k + 1) → ℤ), w' 0 = 0 ∧ (∀ l : Fin k, 2 * w' l.succ = w' (u l.succ) + w' (v l.succ)) ∧ ∃ j : Fin (k + 1), 0 < w' j := by have hw_ex : ∃ l : Fin k, w l ≠ 0 := by by_contra h push Not at h exact hw (funext h) obtain ⟨l, hl⟩ := hw_ex let w_ext : Fin (k + 1) → ℤ := Fin.cons 0 w have hl_ext : w_ext l.succ ≠ 0 := by dsimp [w_ext] rw [Fin.cons_succ] exact hl rcases lt_or_gt_of_ne hl_ext with hneg | hpos · refine ⟨-w_ext, ?_, ?_, l.succ, ?_⟩ · simp [w_ext] · intro l' dsimp linarith [h_harm l'] · dsimp linarith · refine ⟨w_ext, ?_, h_harm, l.succ, hpos⟩ simp [w_ext]/-- Every nonempty midpoint-balanced subset B of ZMod p contains a subconfiguration with a non-zero minor. -/theorem finset_midpoint_balanced_exists_nonzero_minor {p : ℕ} [Fact p.Prime] (B : Finset (ZMod p)) (hB : finset_is_midpoint_balanced B) : ∃ (k : ℕ) (hk0 : 0 < k) (hk : k + 1 ≤ B.card) (u v : Fin (k + 1) → Fin (k + 1)) (b : Fin (k + 1) → ZMod p) (hinj : Function.Injective b) (hmid : ∀ i, 2 * b i = b (u i) + b (v i)) (i₀ j₀ : Fin (k + 1)), ((Matrix.of fun (i j : Fin (k + 1)) => (if j = i then (2 : ℤ) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix i₀.succAbove j₀.succAbove).det ≠ 0 := by obtain ⟨B₀, hB₀B, hB₀bal, hB₀min⟩ := finset_exists_minimal_midpoint_balanced B hB have _hcard3 := finset_midpoint_balanced_card_ge_three B₀ hB₀bal let k := B₀.card - 1 have hk0 : 0 < k := by dsimp [k]; omega have hkeq : k + 1 = B₀.card := by dsimp [k]; omega have hkB : k + 1 ≤ B.card := by rw [hkeq] exact Finset.card_le_card hB₀B have e1 : Fin (k + 1) ≃ Fin B₀.card := (finCongr hkeq.symm).symm have e2 : Fin B₀.card ≃ ↥B₀ := (Finset.equivFin B₀).symm let e : Fin (k + 1) ≃ ↥B₀ := e1.trans e2 let b : Fin (k + 1) → ZMod p := fun i => (e i : ZMod p) have hinj : Function.Injective b := by intro x y hxy have : e x = e y := Subtype.ext hxy exact e.injective this have h_range : Finset.univ.image b = B₀ := by ext a simp only [Finset.mem_image, Finset.mem_univ, true_and] constructor · rintro ⟨i, rfl⟩ exact (e i).2 · intro ha have : (⟨a, ha⟩ : ↥B₀) ∈ Set.range e := e.surjective.range_eq ▸ Set.mem_univ _ obtain ⟨i, hi⟩ := this refine ⟨i, ?_⟩ dsimp [b] rw [hi] have h_each : ∀ i : Fin (k + 1), ∃ (ui vi : Fin (k + 1)), ui ≠ i ∧ vi ≠ i ∧ ui ≠ vi ∧ 2 * b i = b ui + b vi ∧ b i + b i = b ui + b vi := by intro i have hbi : b i ∈ B₀ := by rw [← h_range] exact Finset.mem_image_of_mem b (Finset.mem_univ i) obtain ⟨u', hu', v', hv', hune, hvne, huvne, hmid'⟩ := hB₀bal.2 (b i) hbi rw [← h_range, Finset.mem_image] at hu' hv' obtain ⟨ui, _, rfl⟩ := hu' obtain ⟨vi, _, rfl⟩ := hv' have hui : ui ≠ i := fun h => hune (by rw [h]) have hvi : vi ≠ i := fun h => hvne (by rw [h]) have huvi : ui ≠ vi := fun h => huvne (by rw [h]) have h2 : 2 * b i = b ui + b vi := by rw [two_mul, hmid'] exact ⟨ui, vi, hui, hvi, huvi, h2, hmid'⟩ choose u v hu hv huv hmid hmid_add using h_each refine ⟨k, hk0, hkB, u, v, b, hinj, hmid, 0, 0, ?_⟩ let M := (Matrix.of fun (i j : Fin (k + 1)) => (if j = i then (2 : ℤ) else 0) - (if j = u i then 1 else 0) - (if j = v i then 1 else 0)).submatrix (0 : Fin (k + 1)).succAbove (0 : Fin (k + 1)).succAbove intro hdet have h_kernel := (@Matrix.exists_mulVec_eq_zero_iff (Fin k) _ ℤ _ _ M _).symm.mp hdet obtain ⟨w, hw_ne, hw_mul⟩ := h_kernel have h_harm := finset_midpoint_balanced_exists_nonzero_minor_mulVec_zero_harmonic k u v w hw_mul obtain ⟨w', hw'0, hw'_harm, j, hjpos⟩ := finset_midpoint_balanced_exists_nonzero_minor_pos_harmonic k u v w hw_ne h_harm obtain ⟨m, _, hm⟩ := Finset.exists_max_image Finset.univ w' Finset.univ_nonempty have hV : 0 < w' m := lt_of_lt_of_le hjpos (hm j (Finset.mem_univ j)) have hmax : ∀ j, w' j ≤ w' m := fun j => hm j (Finset.mem_univ j) have hstep := discrete_max_principle_step k u v w' hw'0 hw'_harm (w' m) hV m rfl hmax rcases hstep with ⟨hSne, h0notinS, hS_closed⟩ let S := Finset.univ.filter (fun j => w' j = w' m) have hS_bal : finset_is_midpoint_balanced (S.image b) := finset_image_balanced_of_closed b hinj u v hu hv huv hmid_add S hSne hS_closed have h_sub : S.image b ⊆ B₀ := by rw [← h_range] exact Finset.image_subset_image (Finset.subset_univ S) have heq : S.image b = B₀ := hB₀min (S.image b) h_sub hS_bal have hb0_in : b 0 ∈ B₀ := by rw [← h_range] exact Finset.mem_image_of_mem b (Finset.mem_univ 0) rw [← heq, Finset.mem_image] at hb0_in obtain ⟨j₀, hj₀, hj₀0⟩ := hb0_in have : j₀ = 0 := hinj hj₀0 exact h0notinS (this ▸ hj₀)