dephased_path_constant_gap_implies_nonnegative
A binary constant-gap certificate implies the continuous path inequality under the local noise inequalities.
Statement
open scoped Classical BigOperators in theorem dephased_path_constant_gap_implies_nonnegative (n : ℕ) (color : Fin n → Fin 4) (left right : Finset (Fin 4)) (q : Fin n → ℝ) (hq : ∀ i, q i ∈ Set.Icc (0 : ℝ) 1) (hlocal : ∀ i j k : Fin n, i.val + 1 = j.val → j.val + 1 = k.val → q j ≥ q i * q k) (E : Finset (Fin n)) (hE : ∀ i ∈ E, 0 < i.val ∧ i.val + 1 < n) (hcert : ∀ P : Finset (Fin n), (∑ i ∈ E, (dephased_path_binary_weight n P i.val - dephased_path_binary_weight n P (i.val - 1) * dephased_path_binary_weight n P (i.val + 1))) ≤ dephased_path_interval_polynomial n color left right (fun i => if i ∈ P then 1 else 0)) : 0 ≤ dephased_path_interval_polynomial n color left right q
- Source
- binary averaging reduction for the OP-827 path inequality.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- dephased_path_binary_weightThe zero-one weight of natural position k in the path support P.
- 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_binary_averageThe colored interval polynomial at arbitrary real weights equals its weighted average over all zero-one profiles.
The proof, explained
The proof establishes the continuous path inequality by viewing the parameter vector q as the marginal probabilities of independent Bernoulli random variables and taking the expectation of the binary constant-gap certificate. Under this product distribution, the expectation of each local noise expression B_j - B_{j-1} B_{j+1} evaluates to q_j - q_{j-1} q_{j+1}, which is non-negative by the local noise hypothesis. Because the interval polynomial evaluated at q equals its expectation over all binary configurations, and the certificate inequality holds pointwise for every binary configuration, taking expectations proves that the interval polynomial at q is non-negative.
Define the product distribution W, the indicator function B, and the active index sets P for boolean configurations f.
Set up classical logic and define for each boolean assignment f: Fin n → Bool: the probability mass W(f) as the product of q_i when f(i) is true and 1 - q_i when f(i) is false; the coordinate evaluation B(f, i) ∈ {0, 1}; and the subset P(f) ⊆ Fin n of indices where f evaluates to true.
classical let W (f : Fin n → Bool) : ℝ := ∏ i : Fin n, if f i then q i else 1 - q i let B (f : Fin n → Bool) (i : Fin n) : ℝ := if f i then 1 else 0 let P (f : Fin n → Bool) : Finset (Fin n) := Finset.univ.filter (fun i => f i)
Every probability weight W(f) is non-negative: 0 ≤ W(f).
The weight W(f) is a finite product of terms, where each term is either q_i or 1 - q_i. Since each q_i lies in [0, 1] by hypothesis hq, both choices are non-negative, and Finset.prod_nonneg ensures that their product is non-negative.
uses
Finset.prod_nonneg,Set.mem_Icchave hW (f : Fin n → Bool) : 0 ≤ W f := by apply Finset.prod_nonneg intro i hi split <;> have := hq i <;> simp_all [Set.mem_Icc] <;> linarith
For any boolean assignment f and index i, the binary weight of P(f) at i equals B(f, i).
By definition, dephased_path_binary_weight n (P f) i.val is 1 if some j ∈ P(f) has j.val = i.val and 0 otherwise. Since P(f) consists of those indices where f is true, two indices with the same value are identical by Fin.ext, so such a j exists if and only if f(i) = true. This coincides with B(f, i) in both cases.
uses
Fin.exthave hB (f : Fin n → Bool) (i : Fin n) : dephased_path_binary_weight n (P f) i.val = B f i := by unfold dephased_path_binary_weight B have hh : (∃ j ∈ P f, j.val = i.val) ↔ f i = true := by constructor · rintro ⟨j,hj,hji⟩ have : j = i := Fin.ext hji subst j simpa [P] using hj · intro hi exact ⟨i, by simp [P, hi], rfl⟩ by_cases hf : f i = true · have he := hh.mpr hf simp [he, hf] · have he : ¬ ∃ j ∈ P f, j.val = i.val := fun hx => hf (hh.mp hx) simp [he, hf]
The expectation under W of any monomial ∏_{i ∈ X} B(f, i) is ∏_{i ∈ X} q_i, yielding first moments q_i and second moments q_i * q_j for distinct i ≠ j.
The lemma independent_binary_monomial_average_work shows that under this independent Bernoulli measure, the expected product over X equals ∏_{i ∈ X} q_i. Specializing to a singleton {i} gives the first moment ∑_f W(f) B(f, i) = q_i, and specializing to a pair {i, j} with i ≠ j gives the second moment ∑_f W(f) B(f, i) B(f, j) = q_i * q_j.
uses
Finset.prod_mul_distrib,Fintype.prod_ite_mem,independent_binary_monomial_average_workhave hm (X : Finset (Fin n)) : (∑ f : Fin n → Bool, W f * ∏ i ∈ X, B f i) = ∏ i ∈ X, q i := by simpa only [Finset.prod_mul_distrib, Fintype.prod_ite_mem, W, B] using independent_binary_monomial_average_work q X have h1 (i : Fin n) : (∑ f : Fin n → Bool, W f * B f i) = q i := by simpa using hm {i} have h2 (i j : Fin n) (hij : i ≠ j) : (∑ f : Fin n → Bool, W f * (B f i * B f j)) = q i * q j := by simpa [hij] using hm {i,j}
For each edge index j ∈ E, the expected local noise difference is non-negative: 0 ≤ ∑_f W(f) * (B(f, j) - B(f, j-1) * B(f, j+1)).
For j ∈ E, the predecessor l = j - 1 and successor r = j + 1 are valid, distinct indices in Fin n (with l ≠ r verified using congrArg). Replacing the binary weights by B, expanding the product and sum with mul_sub and Finset.sum_sub_distrib, and substituting the moments reduces the expectation to q_j - q_l * q_r. This is non-negative by the local noise hypothesis hlocal and sub_nonneg.mpr.
uses
congrArg,mul_sub,Finset.sum_sub_distrib,sub_nonneg.mprhave hlocalavg (j : Fin n) (hj : j ∈ E) : 0 ≤ ∑ f : Fin n → Bool, W f * (dephased_path_binary_weight n (P f) j.val - dephased_path_binary_weight n (P f) (j.val - 1) * dephased_path_binary_weight n (P f) (j.val + 1)) := by have hj' := hE j hj let l : Fin n := ⟨j.val - 1, by omega⟩ let r : Fin n := ⟨j.val + 1, by omega⟩ have hl : l.val + 1 = j.val := by dsimp [l]; omega have hr : j.val + 1 = r.val := rfl have hlr : l ≠ r := by intro h; have := congrArg Fin.val h; dsimp [l,r] at this; omega have hlval : l.val = j.val - 1 := rfl have hrval : r.val = j.val + 1 := rfl have hbl (f : Fin n → Bool) : dephased_path_binary_weight n (P f) (j.val - 1) = B f l := by simpa only [hlval] using hB f l have hbr (f : Fin n → Bool) : dephased_path_binary_weight n (P f) (j.val + 1) = B f r := by simpa only [hrval] using hB f r simp_rw [hB, hbl, hbr, mul_sub, Finset.sum_sub_distrib, h1, h2 l r hlr] exact sub_nonneg.mpr (hlocal l j r hl hr)
The expected certificate sum over all i ∈ E is non-negative.
Distribute W(f) over the inner sum over E using Finset.mul_sum and interchange the order of summation using Finset.sum_comm. This expresses the total expectation as a sum over i ∈ E of the expected local terms from the previous step, which is non-negative by Finset.sum_nonneg.
uses
Finset.mul_sum,Finset.sum_comm,Finset.sum_nonneghave hnonneg : 0 ≤ ∑ f : Fin n → Bool, W f * ∑ i ∈ E, (dephased_path_binary_weight n (P f) i.val - dephased_path_binary_weight n (P f) (i.val - 1) * dephased_path_binary_weight n (P f) (i.val + 1)) := by simp_rw [Finset.mul_sum] rw [Finset.sum_comm] exact Finset.sum_nonneg (fun i hi => hlocalavg i hi)
The interval polynomial at q is non-negative: 0 ≤ dephased_path_interval_polynomial n color left right q.
By dephased_path_interval_binary_average, the polynomial evaluated at q equals its expectation under W. By le_trans, it suffices to show that the non-negative expected certificate sum is bounded above by this polynomial expectation. Applying Finset.sum_le_sum reduces this to configuration-by-configuration comparison: for each f, the certificate hypothesis hcert bounds the inner sum by the binary polynomial, and multiplying by W(f) ≥ 0 via mul_le_mul_of_nonneg_left preserves the inequality.
uses
dephased_path_interval_binary_average,le_trans,Finset.sum_le_sum,mul_le_mul_of_nonneg_leftrw [← dephased_path_interval_binary_average n color left right q] apply le_trans hnonneg apply Finset.sum_le_sum intro f hf apply mul_le_mul_of_nonneg_left _ (hW f) simpa [P] using hcert (P f)
congrArg- If a = b, then f(a) = f(b) for any function f.
dephased_path_interval_binary_average- The interval polynomial evaluated at continuous parameters q equals its expectation under the independent product Bernoulli distribution with marginal probabilities q.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural values are equal.
Fintype.prod_ite_mem- The product over a finite type of a function that is f(i) on s and 1 elsewhere equals the product of f over s.
Finset.mul_sum- Multiplication distributes over finite summation: a * ∑ i, f i = ∑ i, a * f i.
Finset.prod_mul_distrib- The product of two functions multiplied pointwise over a finite set equals the product of the individual products: ∏ (f * g) = (∏ f) * (∏ g).
Finset.prod_nonneg- A finite product of non-negative elements is non-negative.
Finset.sum_comm- The order of two finite summations can be interchanged: ∑ x, ∑ y, f x y = ∑ y, ∑ x, f x y.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i of a finite set, then ∑ i, f i ≤ ∑ i, g i.
Finset.sum_nonneg- A finite sum of non-negative elements is non-negative.
Finset.sum_sub_distrib- Finite summation distributes over subtraction: ∑ i, (f i - g i) = ∑ i, f i - ∑ i, g i.
independent_binary_monomial_average_work- Under independent binary variables with marginal expectations q, the expectation of the product ∏_{i ∈ X} B_i is ∏_{i ∈ X} q_i.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
mul_le_mul_of_nonneg_left- Multiplying both sides of an inequality b ≤ c on the left by a non-negative element a ≥ 0 preserves the inequality: a * b ≤ a * c.
mul_sub- Multiplication distributes over subtraction on the left: a * (b - c) = a * b - a * c.
Set.mem_Icc- An element x belongs to the closed interval [a, b] if and only if a ≤ x and x ≤ b.
sub_nonneg.mpr- If b ≤ a, then 0 ≤ a - b.
- The multilinear average identity `dephased_path_interval_binary_average` is proven separately in the knowledge base; it asserts that the continuous polynomial evaluation equals the expected value over the independent Bernoulli distribution.
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.
set_option maxHeartbeats 2000000open scoped Classical BigOperators intheorem dephased_path_constant_gap_implies_nonnegative (n : ℕ) (color : Fin n → Fin 4) (left right : Finset (Fin 4)) (q : Fin n → ℝ) (hq : ∀ i, q i ∈ Set.Icc (0 : ℝ) 1) (hlocal : ∀ i j k : Fin n, i.val + 1 = j.val → j.val + 1 = k.val → q j ≥ q i * q k) (E : Finset (Fin n)) (hE : ∀ i ∈ E, 0 < i.val ∧ i.val + 1 < n) (hcert : ∀ P : Finset (Fin n), (∑ i ∈ E, (dephased_path_binary_weight n P i.val - dephased_path_binary_weight n P (i.val - 1) * dephased_path_binary_weight n P (i.val + 1))) ≤ dephased_path_interval_polynomial n color left right (fun i => if i ∈ P then 1 else 0)) : 0 ≤ dephased_path_interval_polynomial n color left right q := by classical let W (f : Fin n → Bool) : ℝ := ∏ i : Fin n, if f i then q i else 1 - q i let B (f : Fin n → Bool) (i : Fin n) : ℝ := if f i then 1 else 0 let P (f : Fin n → Bool) : Finset (Fin n) := Finset.univ.filter (fun i => f i) have hW (f : Fin n → Bool) : 0 ≤ W f := by apply Finset.prod_nonneg intro i hi split <;> have := hq i <;> simp_all [Set.mem_Icc] <;> linarith have hB (f : Fin n → Bool) (i : Fin n) : dephased_path_binary_weight n (P f) i.val = B f i := by unfold dephased_path_binary_weight B have hh : (∃ j ∈ P f, j.val = i.val) ↔ f i = true := by constructor · rintro ⟨j,hj,hji⟩ have : j = i := Fin.ext hji subst j simpa [P] using hj · intro hi exact ⟨i, by simp [P, hi], rfl⟩ by_cases hf : f i = true · have he := hh.mpr hf simp [he, hf] · have he : ¬ ∃ j ∈ P f, j.val = i.val := fun hx => hf (hh.mp hx) simp [he, hf] have hm (X : Finset (Fin n)) : (∑ f : Fin n → Bool, W f * ∏ i ∈ X, B f i) = ∏ i ∈ X, q i := by simpa only [Finset.prod_mul_distrib, Fintype.prod_ite_mem, W, B] using independent_binary_monomial_average_work q X have h1 (i : Fin n) : (∑ f : Fin n → Bool, W f * B f i) = q i := by simpa using hm {i} have h2 (i j : Fin n) (hij : i ≠ j) : (∑ f : Fin n → Bool, W f * (B f i * B f j)) = q i * q j := by simpa [hij] using hm {i,j} have hlocalavg (j : Fin n) (hj : j ∈ E) : 0 ≤ ∑ f : Fin n → Bool, W f * (dephased_path_binary_weight n (P f) j.val - dephased_path_binary_weight n (P f) (j.val - 1) * dephased_path_binary_weight n (P f) (j.val + 1)) := by have hj' := hE j hj let l : Fin n := ⟨j.val - 1, by omega⟩ let r : Fin n := ⟨j.val + 1, by omega⟩ have hl : l.val + 1 = j.val := by dsimp [l]; omega have hr : j.val + 1 = r.val := rfl have hlr : l ≠ r := by intro h; have := congrArg Fin.val h; dsimp [l,r] at this; omega have hlval : l.val = j.val - 1 := rfl have hrval : r.val = j.val + 1 := rfl have hbl (f : Fin n → Bool) : dephased_path_binary_weight n (P f) (j.val - 1) = B f l := by simpa only [hlval] using hB f l have hbr (f : Fin n → Bool) : dephased_path_binary_weight n (P f) (j.val + 1) = B f r := by simpa only [hrval] using hB f r simp_rw [hB, hbl, hbr, mul_sub, Finset.sum_sub_distrib, h1, h2 l r hlr] exact sub_nonneg.mpr (hlocal l j r hl hr) have hnonneg : 0 ≤ ∑ f : Fin n → Bool, W f * ∑ i ∈ E, (dephased_path_binary_weight n (P f) i.val - dephased_path_binary_weight n (P f) (i.val - 1) * dephased_path_binary_weight n (P f) (i.val + 1)) := by simp_rw [Finset.mul_sum] rw [Finset.sum_comm] exact Finset.sum_nonneg (fun i hi => hlocalavg i hi) rw [← dephased_path_interval_binary_average n color left right q] apply le_trans hnonneg apply Finset.sum_le_sum intro f hf apply mul_le_mul_of_nonneg_left _ (hW f) simpa [P] using hcert (P f)