has_depth_three_amc_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 r a natural number. Then has_depth_three_amc_proof n A ε r holds if and only if there exists a family of r functions R : Fin r → (Fin n → Bool) → ℝ such that every R j is a nonnegative rank-one product (is_rank_one_product (R j)), and for every truth assignment τ : Fin n → Bool, the number of terms in A satisfied by τ (counted as the length of the sublist of terms in A whose literals all evaluate to true under τ) minus ε equals the sum over j : Fin r of R j τ.
Statement
open scoped Classical BigOperators in def has_depth_three_amc_proof (n : ℕ) (A : List (List (CnfLit (Fin n)))) (ε : ℝ) (r : ℕ) : Prop
- Defined in
- arXiv:2611.01055, Section 2.3, formula (2)
- Verified
- 04 Nov 2026
- Axioms
- none listed
- Built on 2
- is_rank_one_productA function R on the n-dimensional Boolean cube is a nonnegative rank-one product if it factors as the product of n nonnegative…
- CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.
- Used by 3
- depth_three_amc_soundnessFor any natural number n, any DNF formula A : List (List (CnfLit (Fin n))), any real shift parameter ε > 0, and any proof size r : ℕ, if A…
- 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 n : ℕ, a list of lists of literals A : List (List (CnfLit (Fin n))), ε : ℝ, and r : ℕ, has_depth_three_amc_proof n A ε r asserts that there exists a family of functions R : Fin r → (Fin n → Bool) → ℝ such that:
1. For every j : Fin r, R j is a rank-one product (is_rank_one_product (R j)).
2. For every assignment τ : Fin n → Bool, the number of terms t ∈ A that are satisfied under τ (meaning that for every literal l ∈ t, τ v = true if l = CnfLit.pos v and τ v = false if l = CnfLit.neg v), cast to ℝ, minus ε, is exactly equal to the sum ∑ j : Fin r, 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 depth-three AMC proof of size r at shift parameter ε if its satisfied-term count minus ε is a sum of r nonnegative rank-one product functions. -/ def has_depth_three_amc_proof (n : ℕ) (A : List (List (CnfLit (Fin n)))) (ε : ℝ) (r : ℕ) : Prop := ∃ R : Fin r → (Fin n → Bool) → ℝ, (∀ j, is_rank_one_product (R j)) ∧ ∀ τ : 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 r, R j τ