finite_parent_collision_budget_with_cover
Under the same repeated-pair parent and charge assumptions, any dirty set covered by the parent sets and any missing set no larger than the total charges have combined size at most three times the excess multiplicity.
Statement
theorem finite_parent_collision_budget_with_cover (ι α β : Type) [DecidableEq ι] [DecidableEq α] [DecidableEq β] (S : Finset ι) (P C : ι → Finset α) (dirty : Finset α) (missing : Finset β) (hcover : dirty ⊆ S.biUnion P) (hcharge : missing.card ≤ ∑ e ∈ S, (C e).card) (hm : ∀ e ∈ S, 2 ≤ (P e).card) (hc : ∀ e ∈ S, C e ⊆ P e) (h2 : ∀ e ∈ S, (P e).card = 2 → (C e).card ≤ 1) : dirty.card + missing.card ≤ 3 * ∑ e ∈ S, ((P e).card - 1)
- Source
- Finite collision-charge assembly for the OP-110 small-overlap route.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
- Used by 5
- 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…
- 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_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 bounds the sum |dirty| + |missing| by combining individual bounds with an incidence budget inequality. Because the dirty set is covered by the parent sets, its size is at most the size of their union, while the missing set size is bounded by the total charges by assumption. Applying the incidence budget theorem finite_parent_collision_incidence_budget shows that the union of parent sets plus the total charges is bounded by three times the excess multiplicity. Linear arithmetic then chains these inequalities to conclude the claim.
|dirty| ≤ |⋃_{e ∈ S} P(e)|, and the parent and charge sets satisfy the incidence budget |⋃_{e ∈ S} P(e)| + ∑_{e ∈ S} |C(e)| ≤ 3 ∑_{e ∈ S} (|P(e)| - 1).
By monotonicity of cardinality under subset inclusion (Finset.card_le_card), the covering hypothesis dirty ⊆ S.biUnion P (hcover) implies that |dirty| ≤ |⋃_{e ∈ S} P(e)|. Applying the incidence budget theorem finite_parent_collision_incidence_budget to the hypotheses that parent sets have size at least 2 (hm), charges are subsets of parents (hc), and size-2 parents carry at most 1 charge (h2) establishes that the size of the union of parent sets plus the total charges is at most 3 ∑_{e ∈ S} (|P(e)| - 1).
uses
Finset.card_le_card,finite_parent_collision_incidence_budgethave hdirty := Finset.card_le_card hcover have hbudget := finite_parent_collision_incidence_budget ι α S P C hm hc h2
|dirty| + |missing| ≤ 3 ∑_{e ∈ S} (|P(e)| - 1).
Summing the bound |dirty| ≤ |⋃_{e ∈ S} P(e)| and the hypothesis |missing| ≤ ∑_{e ∈ S} |C(e)| (hcharge) yields |dirty| + |missing| ≤ |⋃_{e ∈ S} P(e)| + ∑_{e ∈ S} |C(e)|. Chaining this with the incidence budget bound from the previous step gives the desired inequality. The tactic omega closes the goal using linear natural arithmetic.
omega
Finset.card_le_card- If a finite set s is a subset of a finite set t, then |s| ≤ |t|.
finite_parent_collision_incidence_budget- For any index set S and families of finite sets P and C, if every parent set P(e) has size at least 2, each charge set C(e) is a subset of P(e), and |C(e)| ≤ 1 whenever |P(e)| = 2, then |⋃_{e ∈ S} P(e)| + ∑_{e ∈ S} |C(e)| ≤ 3 ∑_{e ∈ S} (|P(e)| - 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.
theorem finite_parent_collision_budget_with_cover (ι α β : Type) [DecidableEq ι] [DecidableEq α] [DecidableEq β] (S : Finset ι) (P C : ι → Finset α) (dirty : Finset α) (missing : Finset β) (hcover : dirty ⊆ S.biUnion P) (hcharge : missing.card ≤ ∑ e ∈ S, (C e).card) (hm : ∀ e ∈ S, 2 ≤ (P e).card) (hc : ∀ e ∈ S, C e ⊆ P e) (h2 : ∀ e ∈ S, (P e).card = 2 → (C e).card ≤ 1) : dirty.card + missing.card ≤ 3 * ∑ e ∈ S, ((P e).card - 1) := by have hdirty := Finset.card_le_card hcover have hbudget := finite_parent_collision_incidence_budget ι α S P C hm hc h2 omega