AFTD Auto-Formalizing Theoretical Domains

has_depth_three_amc_proof

def

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