AFTD Auto-Formalizing Theoretical Domains

finite_product_one_sub_lower_bound_by_fibres

theoremverified

If each factor 1-w_i belongs to one of a finite set of groups, all weights are in [0,1], and every group has total weight at most M in [0,1], the product of all factors is at least (1-M) to the number of groups.

Statement

theorem finite_product_one_sub_lower_bound_by_fibres
    {I R : Type*} [DecidableEq I] [DecidableEq R]
    (N : Finset I) (S : Finset R) (f : I → R) (w : I → ℝ) (M : ℝ)
    (hM0 : 0 ≤ M) (hM1 : M ≤ 1)
    (hw : ∀ i ∈ N, 0 ≤ w i ∧ w i ≤ 1)
    (hf : ∀ i ∈ N, f i ∈ S)
    (hmass : ∀ r ∈ S, ∑ i ∈ N.filter (fun i => f i = r), w i ≤ M) :
    (1 - M) ^ S.card ≤ ∏ i ∈ N, (1 - w i)
Source
Product estimate for OP-306 permutation seal events. Assign each neighboring event one shared position or vertex; the total event weight per such resource is bounded by the explicit mass certificate.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 3

The proof, explained

The argument first proves an auxiliary inequality by induction on finite sets: for any weights $w_i \in [0, 1]$, $1 - \sum w_i \le \prod (1 - w_i)$. For the main theorem, applying this auxiliary lemma to each fibre $f^{-1}(r) \cap N$ yields $1 - M \le \prod_{f(i)=r} (1 - w_i)$, since each fibre has total weight at most $M$. Multiplying these bounds over all $r \in S$ produces $(1 - M)^{|S|} \le \prod_{r \in S} \prod_{f(i)=r} (1 - w_i)$. Finally, the double product is recognized as the fibrewise decomposition of the full product $\prod_{i \in N} (1 - w_i)$.

  1. The auxiliary inequality $1 - \sum_{i \in s} w_i \le \prod_{i \in s} (1 - w_i)$ holds when $s = \emptyset$.

    We proceed by induction on the finite set $s$ using `Finset.induction_on`. In the base case $s = \emptyset$, the empty sum is $0$ and the empty product is $1$, so the claim reduces to $1 - 0 \le 1$, which holds immediately.

    lines 5–7

    uses Finset.induction_on

      classical
      induction s using Finset.induction_on with
      | empty => simp
  2. If the auxiliary inequality holds for $s$, then it holds for $s \cup \{a\}$ when $a \notin s$.

    By `Finset.sum_insert` and `Finset.prod_insert`, inserting $a$ splits the sum into $w_a + \sum_{i \in s} w_i$ and the product into $(1 - w_a) \prod_{i \in s} (1 - w_i)$. Because $a$ and each element of $s$ belong to the inserted set (by `Finset.mem_insert_self` and `Finset.mem_insert_of_mem`), their weights lie in $[0, 1]$. The induction hypothesis gives $1 - \sum_{i \in s} w_i \le \prod_{i \in s} (1 - w_i)$. Since each factor $1 - w_i$ is non-negative (via `sub_nonneg.mpr`), the product over $s$ is non-negative by `Finset.prod_nonneg`. Furthermore, since each factor is at most $1$, the product over $s$ is at most $1$ by `Finset.prod_le_one`. Combining these bounds with $w_a \in [0, 1]$ and the induction hypothesis, non-linear arithmetic (`nlinarith`) establishes $1 - (w_a + \sum_{i \in s} w_i) \le (1 - w_a) \prod_{i \in s} (1 - w_i)$.

    lines 8–19

    uses Finset.sum_insert, Finset.prod_insert, Finset.mem_insert_self, Finset.mem_insert_of_mem, Finset.prod_nonneg, sub_nonneg.mpr, Finset.prod_le_one

      | insert a s ha ih =>
          rw [Finset.sum_insert ha, Finset.prod_insert ha]
          have hwa : 0 ≤ w a ∧ w a ≤ 1 := hw a (Finset.mem_insert_self a s)
          have hws : ∀ i ∈ s, 0 ≤ w i ∧ w i ≤ 1 := fun i hi => hw i (Finset.mem_insert_of_mem hi)
          have ih' : 1 - ∑ i ∈ s, w i ≤ ∏ i ∈ s, (1 - w i) := ih hws
          have hprod_nonneg : 0 ≤ ∏ i ∈ s, (1 - w i) :=
            Finset.prod_nonneg (fun i hi => sub_nonneg.mpr (hws i hi).2)
          have hprod_le_one : ∏ i ∈ s, (1 - w i) ≤ 1 := by
            apply Finset.prod_le_one
            · intro i hi; linarith [(hws i hi).2]
            · intro i hi; linarith [(hws i hi).1]
          nlinarith
  3. For each group $r \in S$, the product of factors $1 - w_i$ over the fibre $f^{-1}(r) \cap N$ is at least $1 - M$.

    For any $r \in S$, the fibre $N_r = \{i \in N \mid f(i) = r\}$ is a subset of $N$ by `Finset.filter_subset`, so every element in $N_r$ has weight in $[0, 1]$. Applying the auxiliary lemma `finite_product_one_sub_lower_bound_by_fibres_aux` to this fibre yields $1 - \sum_{i \in N_r} w_i \le \prod_{i \in N_r} (1 - w_i)$. Since the sum of weights on the fibre is at most $M$ by hypothesis, linear arithmetic gives $1 - M \le \prod_{i \in N_r} (1 - w_i)$.

    lines 29–39

    uses Finset.filter_subset, finite_product_one_sub_lower_bound_by_fibres_aux

      classical
      have hM : 0 ≤ M ∧ M ≤ 1 := ⟨hM0, hM1⟩
      have hfiber : ∀ r ∈ S, 1 - M ≤ ∏ i ∈ N.filter (fun i => f i = r), (1 - w i) := by
        intro r hr
        have hsub : N.filter (fun i => f i = r) ⊆ N := Finset.filter_subset _ _
        have hw' : ∀ i ∈ N.filter (fun i => f i = r), 0 ≤ w i ∧ w i ≤ 1 :=
          fun i hi => hw i (hsub hi)
        have hsum := hmass r hr
        have hprod := finite_product_one_sub_lower_bound_by_fibres_aux
          (N.filter (fun i => f i = r)) w hw'
        linarith
  4. $(1 - M)^{|S|} \le \prod_{r \in S} \prod_{i \in N, f(i) = r} (1 - w_i)$.

    By `Finset.prod_const`, $(1 - M)^{|S|}$ equals the product of $|S|$ constant factors $1 - M$. Because $M \le 1$, each factor is non-negative. Since $1 - M \le \prod_{i \in N, f(i) = r} (1 - w_i)$ for each $r \in S$ from the fibre bound, `Finset.prod_le_prod` implies that the product over $S$ of $1 - M$ is bounded by the product of the fibre products.

    lines 40–47

    uses Finset.prod_const, Finset.prod_le_prod

      calc
        (1 - M) ^ S.card = ∏ r ∈ S, (1 - M) := by rw [Finset.prod_const]
        _ ≤ ∏ r ∈ S, ∏ i ∈ N.filter (fun i => f i = r), (1 - w i) := by
          apply Finset.prod_le_prod
          · intro r hr
            linarith [hM.2]
          · intro r hr
            exact hfiber r hr
  5. $\prod_{r \in S} \prod_{i \in N, f(i) = r} (1 - w_i) = \prod_{i \in N} (1 - w_i)$, completing the proof.

    Because $f$ maps every element of $N$ into $S$, the product of $1 - w_i$ over all $i \in N$ decomposes fibrewise over $S$ by `Finset.prod_fiberwise_of_maps_to`.

    lines 48–49

    uses Finset.prod_fiberwise_of_maps_to

        _ = ∏ i ∈ N, (1 - w i) := by
          exact Finset.prod_fiberwise_of_maps_to hf (fun i => 1 - w i)
Finset.induction_on
To prove a property for all finite sets, it suffices to prove it for the empty set and show it is preserved when inserting an element not already present.
Finset.sum_insert
For an element $a \notin s$, the sum over $s \cup \{a\}$ is $f(a) + \sum_{x \in s} f(x)$.
Finset.prod_insert
For an element $a \notin s$, the product over $s \cup \{a\}$ is $f(a) \cdot \prod_{x \in s} f(x)$.
Finset.mem_insert_self
An element $a$ is a member of $\{a\} \cup s$.
Finset.mem_insert_of_mem
If an element belongs to $s$, it also belongs to $\{b\} \cup s$.
Finset.prod_nonneg
A finite product of non-negative real numbers is non-negative.
sub_nonneg.mpr
If $b \le a$, then $0 \le a - b$.
Finset.prod_le_one
A finite product of real numbers in $[0, 1]$ is at most $1$.
Finset.filter_subset
The filtered subset $\{x \in s \mid p(x)\}$ is a subset of $s$.
finite_product_one_sub_lower_bound_by_fibres_aux
For any finite set with weights $w_i \in [0, 1]$, $1 - \sum_{i \in s} w_i \le \prod_{i \in s} (1 - w_i)$.
Finset.prod_const
The product of a constant $b$ over a finite set $s$ equals $b^{|s|}$.
Finset.prod_le_prod
If $0 \le f(i) \le g(i)$ for all $i \in s$, then $\prod_{i \in s} f(i) \le \prod_{i \in s} g(i)$.
Finset.prod_fiberwise_of_maps_to
If $g$ maps $s$ into $t$, then the product over $s$ equals the iterated product over all fibres $g^{-1}(j) \cap s$ for $j \in t$.

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_product_one_sub_lower_bound_by_fibres_aux    {I : Type*} [DecidableEq I] (s : Finset I) (w : I → ℝ)    (hw : ∀ i ∈ s, 0 ≤ w i ∧ w i ≤ 1) :    1 - ∑ i ∈ s, w i ≤ ∏ i ∈ s, (1 - w i) := by  classical  induction s using Finset.induction_on with  | empty => simp  | insert a s ha ih =>      rw [Finset.sum_insert ha, Finset.prod_insert ha]      have hwa : 0 ≤ w a ∧ w a ≤ 1 := hw a (Finset.mem_insert_self a s)      have hws : ∀ i ∈ s, 0 ≤ w i ∧ w i ≤ 1 := fun i hi => hw i (Finset.mem_insert_of_mem hi)      have ih' : 1 - ∑ i ∈ s, w i ≤ ∏ i ∈ s, (1 - w i) := ih hws      have hprod_nonneg : 0 ≤ ∏ i ∈ s, (1 - w i) :=        Finset.prod_nonneg (fun i hi => sub_nonneg.mpr (hws i hi).2)      have hprod_le_one : ∏ i ∈ s, (1 - w i) ≤ 1 := by        apply Finset.prod_le_one        · intro i hi; linarith [(hws i hi).2]        · intro i hi; linarith [(hws i hi).1]      nlinariththeorem finite_product_one_sub_lower_bound_by_fibres    {I R : Type*} [DecidableEq I] [DecidableEq R]    (N : Finset I) (S : Finset R) (f : I → R) (w : I → ℝ) (M : ℝ)    (hM0 : 0 ≤ M) (hM1 : M ≤ 1)    (hw : ∀ i ∈ N, 0 ≤ w i ∧ w i ≤ 1)    (hf : ∀ i ∈ N, f i ∈ S)    (hmass : ∀ r ∈ S, ∑ i ∈ N.filter (fun i => f i = r), w i ≤ M) :    (1 - M) ^ S.card ≤ ∏ i ∈ N, (1 - w i) := by  classical  have hM : 0 ≤ M ∧ M ≤ 1 := ⟨hM0, hM1⟩  have hfiber : ∀ r ∈ S, 1 - M ≤ ∏ i ∈ N.filter (fun i => f i = r), (1 - w i) := by    intro r hr    have hsub : N.filter (fun i => f i = r) ⊆ N := Finset.filter_subset _ _    have hw' : ∀ i ∈ N.filter (fun i => f i = r), 0 ≤ w i ∧ w i ≤ 1 :=      fun i hi => hw i (hsub hi)    have hsum := hmass r hr    have hprod := finite_product_one_sub_lower_bound_by_fibres_aux      (N.filter (fun i => f i = r)) w hw'    linarith  calc    (1 - M) ^ S.card = ∏ r ∈ S, (1 - M) := by rw [Finset.prod_const]    _ ≤ ∏ r ∈ S, ∏ i ∈ N.filter (fun i => f i = r), (1 - w i) := by      apply Finset.prod_le_prod      · intro r hr        linarith [hM.2]      · intro r hr        exact hfiber r hr    _ = ∏ i ∈ N, (1 - w i) := by      exact Finset.prod_fiberwise_of_maps_to hf (fun i => 1 - w i)
See it in the graphDiscuss this resultChallenge it