girth_charge_multiplicity_bound
A charged subset of an m-element parent set obeys the girth-dependent multiplicity bound if it is proper whenever the parent set has fewer than g elements.
Statement
theorem girth_charge_multiplicity_bound (g m c : ℕ)
(hg : 3 ≤ g) (hm : 2 ≤ m) (hc : c ≤ m)
(hshort : m < g → c < m) : (g - 1) * c ≤ g * (m - 1)- Source
- Girth-dependent collision accounting for the four-cycle campaign; experiment 13463.
- Verified
- 04 Nov 2026
- Axioms
Quot.soundpropext- Used by 2
- digraph_oriented_girth_degree_deficit_overlap_budgetIn a finite loopless oriented arc-dominated digraph whose directed cycles have at least g vertices, with g at least three, g−1 times the…
- digraph_girth_arc_map_missing_budgetFor a loopless oriented digraph of directed girth at least g, g−1 times the number of missing predecessor arc-map images is at most g…
The proof, explained
The proof proceeds by case analysis on whether m < g. If m < g, the hypothesis guarantees c < m, so c ≤ m - 1, and the bound follows by chaining (g - 1) * c ≤ (g - 1) * (m - 1) ≤ g * (m - 1). If m ≥ g, the assumption c ≤ m yields (g - 1) * c ≤ (g - 1) * m, reducing the goal to showing (g - 1) * m ≤ g * (m - 1). This key inequality is proved by expanding (g - 1) * m = (g - 1) * (m - 1) + (g - 1), bounding g - 1 ≤ m - 1, and recombining into g * (m - 1).
Under the assumption m < g, the bound (g - 1) * c ≤ g * (m - 1) holds.
We split into cases on whether m < g. In the branch where m < g, the hypothesis hshort guarantees c < m, which implies c ≤ m - 1 by natural number arithmetic. Multiplying this inequality on the left by g - 1 yields (g - 1) * c ≤ (g - 1) * (m - 1) via Nat.mul_le_mul_left. Since g - 1 ≤ g, multiplying on the right by m - 1 gives (g - 1) * (m - 1) ≤ g * (m - 1) via Nat.mul_le_mul_right. Chaining these two bounds by transitivity establishes the claim for this case.
uses
Nat.mul_le_mul_left,Nat.mul_le_mul_rightby_cases h : m < g · have hc' : c ≤ m - 1 := by have := hshort h; omega have h1 := Nat.mul_le_mul_left (g - 1) hc' have h2 : (g - 1) * (m - 1) ≤ g * (m - 1) := Nat.mul_le_mul_right (m - 1) (by omega) exact h1.trans h2
In the case where g ≤ m, we have (g - 1) * c ≤ (g - 1) * m.
When m < g does not hold, linear arithmetic implies g ≤ m. Multiplying the given assumption c ≤ m on the left by g - 1 yields (g - 1) * c ≤ (g - 1) * m via Nat.mul_le_mul_left.
uses
Nat.mul_le_mul_left· have hgm : g ≤ m := by omega have h1 := Nat.mul_le_mul_left (g - 1) hc
The inequality (g - 1) * m ≤ g * (m - 1) holds, which completes the case g ≤ m.
To relate (g - 1) * m to g * (m - 1), we write m as (m - 1) + 1 using Nat.sub_add_cancel (valid since 1 ≤ m, which follows from 2 ≤ m) and expand the product to (g - 1) * (m - 1) + (g - 1) using Nat.mul_add. Because g ≤ m, subtracting 1 gives g - 1 ≤ m - 1 by Nat.sub_le_sub_right, and adding (g - 1) * (m - 1) to both sides yields (g - 1) * (m - 1) + (g - 1) ≤ (g - 1) * (m - 1) + (m - 1) by Nat.add_le_add_left. Factoring out m - 1 on the right via Nat.add_mul produces ((g - 1) + 1) * (m - 1), which simplifies to g * (m - 1) by Nat.sub_add_cancel (valid since 1 ≤ g, which follows from 3 ≤ g). Finally, combining (g - 1) * c ≤ (g - 1) * m with this bound (g - 1) * m ≤ g * (m - 1) by transitivity finishes the proof.
uses
Nat.sub_add_cancel,Nat.mul_add,Nat.add_le_add_left,Nat.sub_le_sub_right,Nat.add_mulhave h2 : (g - 1) * m ≤ g * (m - 1) := by calc (g - 1) * m = (g - 1) * ((m - 1) + 1) := by rw [Nat.sub_add_cancel (by omega : 1 ≤ m)] _ = (g - 1) * (m - 1) + (g - 1) := by simp [Nat.mul_add] _ ≤ (g - 1) * (m - 1) + (m - 1) := Nat.add_le_add_left (Nat.sub_le_sub_right hgm 1) _ _ = ((g - 1) + 1) * (m - 1) := by simp [Nat.add_mul] _ = g * (m - 1) := by rw [Nat.sub_add_cancel (by omega : 1 ≤ g)] exact h1.trans h2
Nat.mul_le_mul_left- Multiplying both sides of an inequality of natural numbers on the left by a factor preserves the inequality.
Nat.mul_le_mul_right- Multiplying both sides of an inequality of natural numbers on the right by a factor preserves the inequality.
Nat.sub_add_cancel- For natural numbers m ≤ n, subtracting m from n and then adding m yields n.
Nat.mul_add- Multiplication of natural numbers distributes over addition on the left.
Nat.add_le_add_left- Adding a natural number to both sides of an inequality on the left preserves the inequality.
Nat.sub_le_sub_right- Subtracting a natural number from both sides of an inequality of natural numbers preserves the inequality.
Nat.add_mul- Multiplication of natural numbers distributes over addition on the right.
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.
theorem girth_charge_multiplicity_bound (g m c : ℕ) (hg : 3 ≤ g) (hm : 2 ≤ m) (hc : c ≤ m) (hshort : m < g → c < m) : (g - 1) * c ≤ g * (m - 1) := by by_cases h : m < g · have hc' : c ≤ m - 1 := by have := hshort h; omega have h1 := Nat.mul_le_mul_left (g - 1) hc' have h2 : (g - 1) * (m - 1) ≤ g * (m - 1) := Nat.mul_le_mul_right (m - 1) (by omega) exact h1.trans h2 · have hgm : g ≤ m := by omega have h1 := Nat.mul_le_mul_left (g - 1) hc have h2 : (g - 1) * m ≤ g * (m - 1) := by calc (g - 1) * m = (g - 1) * ((m - 1) + 1) := by rw [Nat.sub_add_cancel (by omega : 1 ≤ m)] _ = (g - 1) * (m - 1) + (g - 1) := by simp [Nat.mul_add] _ ≤ (g - 1) * (m - 1) + (m - 1) := Nat.add_le_add_left (Nat.sub_le_sub_right hgm 1) _ _ = ((g - 1) + 1) * (m - 1) := by simp [Nat.add_mul] _ = g * (m - 1) := by rw [Nat.sub_add_cancel (by omega : 1 ≤ g)] exact h1.trans h2