finset_midpoint_balanced_card_ge_three
Every midpoint-balanced finite subset of an additive commutative monoid has cardinality at least 3.
Statement
theorem finset_midpoint_balanced_card_ge_three {G : Type*} [AddCommMonoid G] [DecidableEq G] (B : Finset G) (hB : finset_is_midpoint_balanced B) : 3 ≤ B.card
- Source
- step towards finset_midpoint_balanced_exists_nonzero_minor
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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.
- 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
By definition, a midpoint-balanced set $B$ is nonempty, so it contains at least one element $b$. The balancing condition applied to $b$ yields two other elements $u, v \in B$ such that $b, u, v$ are pairwise distinct. Consequently, the three-element subset $\{b, u, v\}$ is contained in $B$, which implies $|B| \ge 3$.
There exist three distinct elements $b, u, v \in B$.
Because $B$ is midpoint-balanced, it is nonempty, so we can pick an element $b \in B$. Applying the midpoint-balanced property to $b$ gives elements $u, v \in B$ with $u \neq b$, $v \neq b$, and $u \neq v$ (such that $b + b = u + v$).
rcases hB with ⟨⟨b, hb⟩, h⟩ rcases h b hb with ⟨u, hu, v, hv, hub, hvb, huv, -⟩
$\{b, u, v\} \subseteq B$
For any $x \in \{b, u, v\}$, rewriting the membership condition using Finset.mem_insert and Finset.mem_singleton shows that $x = b$, $x = u$, or $x = v$. In each case, $x \in B$ follows from $b \in B$, $u \in B$, or $v \in B$.
uses
Finset.mem_insert,Finset.mem_singletonhave hsub : {b, u, v} ⊆ B := by intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl | rfl · exact hb · exact hu · exact hv
The set $\{b, u, v\}$ has cardinality 3.
We compute the size of the set by successively stripping elements using Finset.card_insert_of_notMem. Since $u \neq v$, $u \notin \{v\}$, so $|\{u, v\}| = |\{v\}| + 1 = 2$. Similarly, since $b \neq u$ and $b \neq v$, $b \notin \{u, v\}$, so $|\{b, u, v\}| = |\{u, v\}| + 1 = 3$.
uses
Finset.card_insert_of_notMemhave hcard : ({b, u, v} : Finset G).card = 3 := by rw [Finset.card_insert_of_notMem] · rw [Finset.card_insert_of_notMem] · simp · simp [huv] · simp [hub.symm, hvb.symm]
$3 \le |B|$
Rewriting 3 as $|\{b, u, v\}|$, the inequality $|\{b, u, v\}| \le |B|$ follows directly by Finset.card_le_card from the inclusion $\{b, u, v\} \subseteq B$.
uses
Finset.card_le_cardrw [← hcard] exact Finset.card_le_card hsub
Finset.mem_insert- An element $a$ belongs to the set formed by inserting $b$ into $s$ if and only if $a = b$ or $a \in s$.
Finset.mem_singleton- An element $b$ belongs to the singleton set $\{a\}$ if and only if $b = a$.
Finset.card_insert_of_notMem- Inserting an element $a$ into a finite set $s$ that does not contain $a$ yields a set of cardinality $|s| + 1$.
Finset.card_le_card- If a finite set $s$ is a subset of $t$, then $|s| \le |t|$.
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.
/-- Every midpoint-balanced finite subset of an additive commutative monoid has cardinality at least 3. -/theorem finset_midpoint_balanced_card_ge_three {G : Type*} [AddCommMonoid G] [DecidableEq G] (B : Finset G) (hB : finset_is_midpoint_balanced B) : 3 ≤ B.card := by rcases hB with ⟨⟨b, hb⟩, h⟩ rcases h b hb with ⟨u, hu, v, hv, hub, hvb, huv, -⟩ have hsub : {b, u, v} ⊆ B := by intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl | rfl · exact hb · exact hu · exact hv have hcard : ({b, u, v} : Finset G).card = 3 := by rw [Finset.card_insert_of_notMem] · rw [Finset.card_insert_of_notMem] · simp · simp [huv] · simp [hub.symm, hvb.symm] rw [← hcard] exact Finset.card_le_card hsub