has_depth_three_amc_bounded_bias_proof
Let n be a natural number, A a DNF formula represented as a list of terms where each term is a list of literals of type CnfLit (Fin n), ε a real shift parameter, and s a natural number. Then has_depth_three_amc_bounded_bias_proof n A ε s holds if and only if there exists a family of s functions R : Fin s → (Fin n → Bool) → ℝ such that for every j : Fin s, R j is a bounded-bias rank-one product—meaning there exists g : Fin n → Bool → ℝ with 0 ≤ g i b for all i and b, and for each i, g i true = 0, g i false = 0, or g i true = g i false, such that R j τ = ∏ i : Fin n, g i (τ i)—and for every truth assignment τ : Fin n → Bool, the number of terms in A satisfied by τ (the length of the sublist of terms in A whose literals all evaluate to true under τ) minus ε equals the sum over j : Fin s of R j τ.
Statement
open scoped Classical BigOperators in def has_depth_three_amc_bounded_bias_proof (n : ℕ) (A : List (List (CnfLit (Fin n)))) (ε : ℝ) (s : ℕ) : Prop
- Defined in
- arXiv:2611.01055, Section 2.3, Definition 2.5 and formula (1)
- Verified
- 04 Nov 2026
- Axioms
- none listed
- Built on 1
- CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.
- Used by 2
- depth_three_amc_of_bounded_biasFor every natural number n, every DNF formula A : List (List (CnfLit (Fin n))), every real shift parameter ε, and every proof size s : ℕ,…
- depth_three_amc_separation_from_asymptotic_familyAny asymptotic family of DNF formulas satisfying the AMC upper bound and bounded-bias lower bound for k ≥ k₀ extends to a full family…
Read back from the Lean
Given a natural number n, a list of lists of literals A : List (List (CnfLit (Fin n))), a real number ε : ℝ, and a natural number s : ℕ, has_depth_three_amc_bounded_bias_proof n A ε s asserts that:
There exists a family of functions R : Fin s → (Fin n → Bool) → ℝ such that:
1. For every index j : Fin s, there exists a function g : Fin n → Bool → ℝ such that:
- for all i : Fin n and b : Bool, 0 ≤ g i b;
- for all i : Fin n, g i true = 0 ∨ g i false = 0 ∨ g i true = g i false;
- for all truth assignments τ : Fin n → Bool, R j τ = ∏ i : Fin n, g i (τ i).
2. For all truth assignments τ : Fin n → Bool:
the number (counted with multiplicity in the list, cast to ℝ) of lists t ∈ A such that for every literal l ∈ t, τ v = true if l = CnfLit.pos v and τ v = false if l = CnfLit.neg v, minus ε, equals ∑ j : Fin s, R j τ.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
open scoped Classical BigOperators in /-- A DNF formula has a bounded-bias depth-three AMC proof of size s at shift parameter ε if its satisfied-term count minus ε is a sum of s bounded-bias rank-one products. -/ def has_depth_three_amc_bounded_bias_proof (n : ℕ) (A : List (List (CnfLit (Fin n)))) (ε : ℝ) (s : ℕ) : Prop := ∃ R : Fin s → (Fin n → Bool) → ℝ, (∀ j, ∃ g : Fin n → Bool → ℝ, (∀ i b, 0 ≤ g i b) ∧ (∀ i, g i true = 0 ∨ g i false = 0 ∨ g i true = g i false) ∧ ∀ τ, R j τ = ∏ i : Fin n, g i (τ i)) ∧ ∀ τ : Fin n → Bool, ((A.filter (fun t => ∀ l ∈ t, match l with | CnfLit.pos v => τ v = true | CnfLit.neg v => τ v = false)).length : ℝ) - ε = ∑ j : Fin s, R j τ