AFTD Auto-Formalizing Theoretical Domains

finite_parent_collision_budget_with_cover

theoremverified

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
Used by 5

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.

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

    lines 10–11

    uses Finset.card_le_card, finite_parent_collision_incidence_budget

      have hdirty := Finset.card_le_card hcover
      have hbudget := finite_parent_collision_incidence_budget ι α S P C hm hc h2
  2. |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.

    line 12

      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

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