oriented_overlap_multiplicity_budget
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
- zero_is_three_distant_convexThe zero game, where every coalition has value zero, is 3-distant convex.
- finite_parent_collision_incidence_budgetFor finite repeated-pair parent sets and charge sets contained in them, if a two-parent pair receives at most one charge, the number of…
- digraph_oriented_arc_map_missing_dirty_budgetFor a finite loopless oriented digraph and a chosen common predecessor for each arc, the number of dirty parents plus the number of arcs…
- finset_restricted_family_emptyThe restricted family of the empty family is empty.
- digraph_oriented_arc_map_twice_missing_budgetIn a finite loopless oriented digraph with a chosen common predecessor for every arc, twice the number of arcs missing from the resulting…
- digraph_trianglefree_arc_map_weighted_budgetFor a loopless oriented digraph of directed girth at least four with chosen common predecessors for its arcs, three times the number of…
- digraph_girth_arc_map_weighted_budgetFor a loopless oriented digraph of directed girth at least g, with g at least three and chosen common predecessors for its arcs, g−1 times…
- digraph_oriented_small_overlap_good_centerIn an oriented arc-dominated digraph, if repeated common-predecessor pair incidences are less than one third of the order, some vertex has…
- 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 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.
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.
by_cases h : m = 2 · have := h2 h omega · omega
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.
uses
Finset.sum_add_distrib,Finset.mul_sumrw [← Finset.sum_add_distrib, Finset.mul_sum]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$.
uses
Finset.sum_le_sum,in504_overlap_edge_budgetapply 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
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.
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)