AFTD Auto-Formalizing Theoretical Domains

oriented_overlap_multiplicity_budget

theoremverified

Summed multiplicities and charges cost at most three times overlap when multiplicity-two edges have at most one charge.

Statement

theorem oriented_overlap_multiplicity_budget
    (ι : Type) [DecidableEq ι] (S : Finset ι) (m c : ι → ℕ)
    (hm : ∀ e ∈ S, 2 ≤ m e)
    (hc : ∀ e ∈ S, c e ≤ m e)
    (h2 : ∀ e ∈ S, m e = 2 → c e ≤ 1) :
    (∑ e ∈ S, m e) + (∑ e ∈ S, c e) ≤ 3 * ∑ e ∈ S, (m e - 1)
Source
Finite arithmetic helper for the oriented small-overlap packing route to OP-110.
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 9

The proof, explained

The proof proceeds by establishing a budget bound for each edge and then summing over the set. First, a helper lemma shows that any individual edge with multiplicity $m \ge 2$ and charge $c \le m$ (with $c \le 1$ when $m = 2$) satisfies $m + c \le 3(m - 1)$, using a case split on $m = 2$ and linear arithmetic. For the main theorem, the sum of multiplicities and sum of charges are combined into a single sum, and the factor of 3 is distributed inside the right-hand sum. Finally, the inequality between sums is reduced to the pointwise bound on each edge, which holds by the helper lemma.

  1. Any edge with multiplicity $m \ge 2$ and charge $c \le m$ (with $c \le 1$ when $m = 2$) satisfies the budget bound $m + c \le 3(m - 1)$.

    We split into cases on whether $m = 2$. In the case $m = 2$, hypothesis $h_2$ gives $c \le 1$, and linear integer arithmetic verifies that $2 + c \le 2 + 1 = 3 = 3(2 - 1)$. In the case $m \ne 2$, we have $m \ge 3$ because $m \ge 2$; since $c \le m$, it follows that $m + c \le 2m \le 3(m - 1)$, which linear arithmetic also confirms.

    lines 4–7

      by_cases h : m = 2
      · have := h2 h
        omega
      · omega
  2. The inequality is rewritten as $\sum_{e \in S} (m(e) + c(e)) \le \sum_{e \in S} 3(m(e) - 1)$.

    We combine the two sums on the left into a single sum using `Finset.sum_add_distrib` in reverse. On the right, `Finset.mul_sum` distributes the scalar factor 3 inside the summation.

    line 15

    uses Finset.sum_add_distrib, Finset.mul_sum

      rw [← Finset.sum_add_distrib, Finset.mul_sum]
  3. The budget inequality holds term by term for every $e \in S$, which implies the inequality for the entire sum.

    By `Finset.sum_le_sum`, the inequality between sums reduces to checking $m(e) + c(e) \le 3(m(e) - 1)$ for every $e \in S$. For each element $e \in S$, this is precisely the single-edge bound `in504_overlap_edge_budget`, whose preconditions are satisfied by evaluating the hypotheses $hm$, $hc$, and $h2$ at $e$.

    lines 16–18

    uses Finset.sum_le_sum, in504_overlap_edge_budget

      apply Finset.sum_le_sum
      intro e he
      exact in504_overlap_edge_budget (m e) (c e) (hm e he) (hc e he) (h2 e he)
Finset.sum_add_distrib
The sum of a pointwise sum over a finite set equals the sum of the individual sums: $\sum_{x \in s} (f(x) + g(x)) = \sum_{x \in s} f(x) + \sum_{x \in s} g(x)$.
Finset.mul_sum
A constant factor distributes over a finite sum: $a \cdot \sum_{i \in s} f(i) = \sum_{i \in s} a \cdot f(i)$.
Finset.sum_le_sum
An inequality between sums holds if it holds pointwise for every term: if $f(i) \le g(i)$ for all $i \in s$, then $\sum_{i \in s} f(i) \le \sum_{i \in s} g(i)$.
in504_overlap_edge_budget
For natural numbers $m$ and $c$, if $2 \le m$, $c \le m$, and $c \le 1$ whenever $m = 2$, then $m + c \le 3(m - 1)$.

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

private theorem in504_overlap_edge_budget (m c : ℕ)    (hm : 2 ≤ m) (hc : c ≤ m) (h2 : m = 2 → c ≤ 1) :    m + c ≤ 3 * (m - 1) := by  by_cases h : m = 2  · have := h2 h    omega  · omegatheorem oriented_overlap_multiplicity_budget    (ι : Type) [DecidableEq ι] (S : Finset ι) (m c : ι → ℕ)    (hm : ∀ e ∈ S, 2 ≤ m e)    (hc : ∀ e ∈ S, c e ≤ m e)    (h2 : ∀ e ∈ S, m e = 2 → c e ≤ 1) :    (∑ e ∈ S, m e) + (∑ e ∈ S, c e) ≤ 3 * ∑ e ∈ S, (m e - 1) := by  rw [← Finset.sum_add_distrib, Finset.mul_sum]  apply Finset.sum_le_sum  intro e he  exact in504_overlap_edge_budget (m e) (c e) (hm e he) (hc e he) (h2 e he)
See it in the graphDiscuss this resultChallenge it