finite_product_one_sub_lower_bound_by_fibres
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
- wild_partition_of_resource_boundsLet n>0 and let a proper coloring of K_n use the color set Fin n. Fix a partition map b from the vertices onto q blocks, with a specified…
- wild_number_complete_graph_279_min_proper_coloring_eqNew case of OP-306: every minimum proper edge colouring of K_279 has wild number 186 = floor(4*ceil(279/2)/3). The lower bound is the…
- wild_triple_partition_mass_criterionFor an odd number q of triple blocks, q>=3, a proper edge coloring of K_(3q) with 3q colors and a bijection between colors and their…
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)$.
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.
uses
Finset.induction_onclassical induction s using Finset.induction_on with | empty => simp
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)$.
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] nlinarithFor 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)$.
uses
Finset.filter_subset,finite_product_one_sub_lower_bound_by_fibres_auxclassical 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
$(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.
uses
Finset.prod_const,Finset.prod_le_prodcalc (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
$\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`.
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$.
- In step 2, Lean's `nlinarith` tactic automatically deduces the induction step from the induction hypothesis together with the bounds $0 \le w_a \le 1$ and $0 \le \prod_{i \in s} (1 - w_i) \le 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_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)