dephased_path_interval_binary_average
The colored interval polynomial at arbitrary real weights equals its weighted average over all zero-one profiles.
Statement
open scoped Classical BigOperators in theorem dephased_path_interval_binary_average (n : ℕ) (color : Fin n → Fin 4) (left right : Finset (Fin 4)) (q : Fin n → ℝ) : (∑ f : Fin n → Bool, (∏ i : Fin n, if f i then q i else 1 - q i) * dephased_path_interval_polynomial n color left right (fun i => if f i then 1 else 0)) = dephased_path_interval_polynomial n color left right q
- Source
- Multi-affine expansion in the OP-827 constant-gap certificate route.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- dephased_path_interval_polynomialThe explicit interval expansion of the block-polynomial tripartite gap on an active path; left and right record the colors of fully…
- dephased_path_interval_blockThe positions of the same parity as the left endpoint in a finite path interval.
- dephased_color_coefficientThe tripartite inclusion-exclusion coefficient for an event requiring all colors in I and excluding all colors in O, with color 3 outside…
- Used by 1
- dephased_path_constant_gap_implies_nonnegativeA binary constant-gap certificate implies the continuous path inequality under the local noise inequalities.
The proof, explained
The theorem expresses the colored interval polynomial as a linear combination of monomials over index intervals. By interchanging the summation over binary profiles with the double sum over interval endpoints, the identity reduces to the fact that the expectation of an indicator monomial under independent Bernoulli variables is the monomial evaluated at the marginal probabilities.
The expectation of a monomial over independent Bernoulli trials equals the product of probabilities
By expanding the sum over assignments into a product of sums over each coordinate, each factor evaluates to q i for i in X and 1 for i not in X, yielding the product over X.
uses
Fintype.prod_sum,Finset.prod_congr,Fintype.sum_bool,Fintype.prod_ite_memclassical calc _ = ∏ i, ∑ b : Bool, (if b then q i else 1 - q i) * (if i ∈ X then (if b then 1 else 0) else 1) := (Fintype.prod_sum (fun i (b : Bool) => (if b then q i else 1 - q i) * (if i ∈ X then (if b then 1 else 0) else 1))).symm _ = ∏ i, if i ∈ X then q i else 1 := by apply Finset.prod_congr rfl intro i hi rw [Fintype.sum_bool] by_cases hiX : i ∈ X <;> simp [hiX] <;> ring _ = _ := Fintype.prod_ite_mem X q
Expand the definition of the polynomial and interchange the sum over profiles with the double sum over indices
Unfolding the definition and distributing multiplication allows swapping the profile summation past the i and j summations.
uses
Finset.mul_sum,Finset.sum_comm,Finset.sum_congrclassical unfold dephased_path_interval_polynomial simp_rw [Finset.mul_sum] rw [Finset.sum_comm] apply Finset.sum_congr rfl intro i hi rw [Finset.sum_comm] apply Finset.sum_congr rfl intro j hj
For pairs (i, j) satisfying the parity and ordering conditions, the profile average matches the monomial at q
In the valid range, each term is a constant times a monomial; applying the monomial average lemma establishes equality term by term.
uses
independent_binary_monomial_average_work,Finset.mul_sum,Finset.sum_congr,Finset.prod_mul_distrib,Fintype.prod_ite_memby_cases h : i.val ≤ j.val ∧ i.val % 2 = j.val % 2 · simp only [h, true_and, if_true] have hgen (c : ℝ) (X : Finset (Fin n)) : (∑ f : Fin n → Bool, (∏ a : Fin n, if f a then q a else 1 - q a) * (c * ∏ a ∈ X, if f a then 1 else 0)) = c * ∏ a ∈ X, q a := by rw [← independent_binary_monomial_average_work q X, Finset.mul_sum] apply Finset.sum_congr rfl intro f hf rw [Finset.prod_mul_distrib, Fintype.prod_ite_mem] ring exact hgen _ _
For pairs (i, j) failing the condition, both sides vanish automation
When the index condition fails, all terms are zero and simplify immediately.
· simp only [h, false_and, and_false, if_false, mul_zero, Finset.sum_const_zero]
Fintype.prod_sum- Exchange finite product and finite sum over function types
Finset.prod_congr- Congruence for products over equal sets with equal terms
Fintype.sum_bool- A sum over Bool equals the value at true plus the value at false
Fintype.prod_ite_mem- A product of an indicator function over a universe equals the product over the subset
Finset.mul_sum- Multiplication distributes over finite sums
Finset.sum_comm- Exchange the order of two finite summations
Finset.sum_congr- Congruence for sums over equal sets with equal terms
Finset.prod_mul_distrib- Multiplication distributes over factors in a finite product
independent_binary_monomial_average_work- The weighted average of a binary monomial over independent Bernoulli assignments equals the monomial evaluated at the probabilities
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.
open scoped BigOperatorsset_option maxHeartbeats 2000000theorem independent_binary_monomial_average_work {ι : Type*} [Fintype ι] [DecidableEq ι] (q : ι → ℝ) (X : Finset ι) : (∑ f : ι → Bool, ∏ i : ι, (if f i then q i else 1 - q i) * (if i ∈ X then (if f i then 1 else 0) else 1)) = ∏ i ∈ X, q i := by classical calc _ = ∏ i, ∑ b : Bool, (if b then q i else 1 - q i) * (if i ∈ X then (if b then 1 else 0) else 1) := (Fintype.prod_sum (fun i (b : Bool) => (if b then q i else 1 - q i) * (if i ∈ X then (if b then 1 else 0) else 1))).symm _ = ∏ i, if i ∈ X then q i else 1 := by apply Finset.prod_congr rfl intro i hi rw [Fintype.sum_bool] by_cases hiX : i ∈ X <;> simp [hiX] <;> ring _ = _ := Fintype.prod_ite_mem X qopen scoped Classical BigOperators intheorem dephased_path_interval_binary_average (n : ℕ) (color : Fin n → Fin 4) (left right : Finset (Fin 4)) (q : Fin n → ℝ) : (∑ f : Fin n → Bool, (∏ i : Fin n, if f i then q i else 1 - q i) * dephased_path_interval_polynomial n color left right (fun i => if f i then 1 else 0)) = dephased_path_interval_polynomial n color left right q := by classical unfold dephased_path_interval_polynomial simp_rw [Finset.mul_sum] rw [Finset.sum_comm] apply Finset.sum_congr rfl intro i hi rw [Finset.sum_comm] apply Finset.sum_congr rfl intro j hj by_cases h : i.val ≤ j.val ∧ i.val % 2 = j.val % 2 · simp only [h, true_and, if_true] have hgen (c : ℝ) (X : Finset (Fin n)) : (∑ f : Fin n → Bool, (∏ a : Fin n, if f a then q a else 1 - q a) * (c * ∏ a ∈ X, if f a then 1 else 0)) = c * ∏ a ∈ X, q a := by rw [← independent_binary_monomial_average_work q X, Finset.mul_sum] apply Finset.sum_congr rfl intro f hf rw [Finset.prod_mul_distrib, Fintype.prod_ite_mem] ring exact hgen _ _ · simp only [h, false_and, and_false, if_false, mul_zero, Finset.sum_const_zero]