is_weighted_subcube_sum
def
A function h on the n-dimensional Boolean cube is a sum of s nonnegative weighted subcube indicators if h τ = ∑_{j : Fin s} (w_j if τ agrees with the partial assignment (S_j, a_j) on every coordinate of S_j, and 0 otherwise), for some nonnegative weights w_j and some partial assignments given by a fixed coordinate set S_j and fixed values a_j. This is the canonical form of a bounded-bias depth-three AMC proof: each bounded-bias rank-one product is a nonnegative multiple of a subcube indicator.
Statement
def is_weighted_subcube_sum {n : ℕ} (h : (Fin n → Bool) → ℝ) (s : ℕ) : Prop
- Source
- step towards op_983_exists_asymptotic_separation_witness
- Verified
- 04 Nov 2026
- Axioms
- none listed
Lean source view module on GitHub
/-- `h` is a sum of `s` nonnegative multiples of subcube indicators of the n-cube. -/ def is_weighted_subcube_sum {n : ℕ} (h : (Fin n → Bool) → ℝ) (s : ℕ) : Prop := ∃ w : Fin s → ℝ, (∀ j, 0 ≤ w j) ∧ ∃ (S : Fin s → Finset (Fin n)) (a : Fin s → Fin n → Bool), ∀ τ : Fin n → Bool, h τ = ∑ j : Fin s, (if ∀ i ∈ S j, τ i = a j i then w j else 0)