AFTD Auto-Formalizing Theoretical Domains

dephased_path_interval_binary_average

theoremverified

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

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.

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

    lines 9–20

    uses Fintype.prod_sum, Finset.prod_congr, Fintype.sum_bool, Fintype.prod_ite_mem

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

    lines 24–32

    uses Finset.mul_sum, Finset.sum_comm, Finset.sum_congr

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

    lines 33–43

    uses independent_binary_monomial_average_work, Finset.mul_sum, Finset.sum_congr, Finset.prod_mul_distrib, Fintype.prod_ite_mem

      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 _ _
  4. For pairs (i, j) failing the condition, both sides vanish automation

    When the index condition fails, all terms are zero and simplify immediately.

    line 45

      · 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

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