AFTD Auto-Formalizing Theoretical Domains

girth_charge_multiplicity_bound

theoremverified

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

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

  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.

    lines 4–9

    uses Nat.mul_le_mul_left, Nat.mul_le_mul_right

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

    lines 10–11

    uses Nat.mul_le_mul_left

      · have hgm : g ≤ m := by omega
        have h1 := Nat.mul_le_mul_left (g - 1) hc
  3. 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.

    lines 12–19

    uses Nat.sub_add_cancel, Nat.mul_add, Nat.add_le_add_left, Nat.sub_le_sub_right, Nat.add_mul

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

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