AFTD Auto-Formalizing Theoretical Domains

dephased_path_constant_gap_implies_nonnegative

theoremverified

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

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.

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

    lines 5–8

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

    lines 9–12

    uses Finset.prod_nonneg, Set.mem_Icc

      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
  3. 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.

    lines 13–28

    uses Fin.ext

      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]
  4. 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.

    lines 29–37

    uses Finset.prod_mul_distrib, Fintype.prod_ite_mem, independent_binary_monomial_average_work

      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}
  5. 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.

    lines 38–56

    uses congrArg, mul_sub, Finset.sum_sub_distrib, sub_nonneg.mpr

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

    lines 57–63

    uses Finset.mul_sum, Finset.sum_comm, Finset.sum_nonneg

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

    lines 64–69

    uses dephased_path_interval_binary_average, le_trans, Finset.sum_le_sum, mul_le_mul_of_nonneg_left

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

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

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