AFTD Auto-Formalizing Theoretical Domains

depth_three_amc_soundness

theoremverifiedformalization

For 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 has a depth-three AMC proof of size r at shift ε (has_depth_three_amc_proof n A ε r), then A is a DNF tautology (is_dnf_tautology A).

Statement

theorem depth_three_amc_soundness (n : ℕ) (A : List (List (CnfLit (Fin n)))) (ε : ℝ) (hε : 0 < ε) (r : ℕ)
    (h : has_depth_three_amc_proof n A ε r) : is_dnf_tautology A
Formalizes
arXiv:2611.01055, Section 2.2, Proposition 2.2
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • has_depth_three_amc_proofLet 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), ε…
  • is_dnf_tautologyA DNF formula A is a tautology if for every Boolean truth assignment to its variables, at least one conjunction term in A is satisfied.
  • CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.
  • 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…

Read back from the Lean

For any natural number $n$, any list of lists of literals $A$ over variables in $\mathrm{Fin}\ n$ (interpreted as a DNF formula, where inner lists are conjunctions/terms of literals), any real number $\varepsilon > 0$, and any natural number $r$: If $A$ has a depth-three AMC proof with error parameter $\varepsilon$ and size $r$—meaning there exists a collection of $r$ functions $R_j : (\mathrm{Fin}\ n \to \mathrm{Bool}) \to \mathbb{R}$ (for $j \in \mathrm{Fin}\ r$) such that: 1. Each $R_j$ is a rank-one product (i.e., there exists a non-negative function $g : \mathrm{Fin}\ n \to \mathrm{Bool} \to \mathbb{R}$ such that $R_j(\tau) = \prod_{i \in \mathrm{Fin}\ n} g(i, \tau(i))$ for all assignments $\tau$), and 2. For every truth assignment $\tau : \mathrm{Fin}\ n \to \mathrm{Bool}$, the number of terms $t \in A$ satisfied by $\tau$ (cast to $\mathbb{R}$) minus $\varepsilon$ equals $\sum_{j \in \mathrm{Fin}\ r} R_j(\tau)$— then $A$ is a DNF tautology (that is, for every truth assignment $\tau : \mathrm{Fin}\ n \to \mathrm{Bool}$, there exists a term $t \in A$ such that every literal in $t$ is satisfied by $\tau$, meaning positive literals evaluate to $\mathrm{true}$ and negative literals evaluate to $\mathrm{false}$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof proceeds by contradiction. If the DNF formula A were not a tautology, some assignment τ would satisfy none of its terms, making the count of satisfied terms 0. The depth-three AMC proof identity evaluated at τ would then force -ε to equal the sum of the rank-one products at τ. But each rank-one product is non-negative everywhere, so the sum is non-negative, contradicting the assumption that ε > 0.

  1. We extract the family of rank-one products and the algebraic identity from the depth-three AMC proof hypothesis.

    By definition of a depth-three AMC proof of size r at shift ε, there exist rank-one products R₁,...,Rᵣ such that for every assignment τ, the number of terms in A satisfied by τ minus ε equals ∑ⱼ Rⱼ(τ). We unpack these functions, the proof that each is a non-negative rank-one product, and this identity.

    lines 4–6

    uses has_depth_three_amc_proof.match_1

      classical
      obtain ⟨R, hR, hsum⟩ := h
      unfold has_depth_three_amc_proof.match_1 at hsum
  2. To show that A is a tautology, we assume for contradiction that some truth assignment satisfies no term in A.

    We introduce an arbitrary truth assignment τ and assume, for the sake of contradiction, that τ does not satisfy the DNF formula A; that is, no term in A has all its literals satisfied by τ.

    lines 7–8

      intro τ
      by_contra hcon
  3. Under the falsifying assignment τ, the number of satisfied terms of A is zero.

    The number of terms satisfied by τ is the length of the filtered sublist of A. By `List.length_eq_zero_iff` and `List.filter_eq_nil_iff`, this length is 0 if and only if no term in A is satisfied. If any term in A were satisfied, all its literals would match τ, contradicting the assumption that no such term exists.

    lines 9–19

    uses List.length_eq_zero_iff, List.filter_eq_nil_iff, decide_eq_true_eq

      have hzero : (A.filter (fun t => decide (∀ l ∈ t,
          CnfLit.casesOn l (fun v => τ v = true) (fun v => τ v = false)))).length = 0 := by
        rw [List.length_eq_zero_iff, List.filter_eq_nil_iff]
        intro t ht
        simp only [decide_eq_true_eq]
        intro hh
        apply hcon
        refine ⟨t, ht, ?_⟩
        intro l hl
        have := hh l hl
        cases l <;> simpa using this
  4. The sum of the rank-one products evaluated at τ is non-negative: 0 ≤ ∑ⱼ Rⱼ(τ).

    A finite sum of non-negative terms is non-negative (`Finset.sum_nonneg`). Each term Rⱼ(τ) is by definition a product of non-negative factors g(i, τ(i)), and a product of non-negative numbers is non-negative (`Finset.prod_nonneg`). Therefore, each Rⱼ(τ) ≥ 0, and their sum is non-negative.

    lines 20–25

    uses Finset.sum_nonneg, Finset.prod_nonneg

      have hnonneg : 0 ≤ ∑ j : Fin r, R j τ := by
        apply Finset.sum_nonneg
        intro j _
        obtain ⟨g, hg, hRg⟩ := hR j
        rw [hRg τ]
        exact Finset.prod_nonneg (fun i _ => hg i (τ i))
  5. Evaluating the AMC identity at τ leads to the contradiction -ε ≥ 0 while ε > 0.

    Specializing the AMC identity to τ gives (count of satisfied terms) - ε = ∑ⱼ Rⱼ(τ). Substituting the count 0 and simplifying `Nat.cast_zero` gives -ε = ∑ⱼ Rⱼ(τ). Since the sum is non-negative, this implies -ε ≥ 0, which contradicts ε > 0 by linear arithmetic.

    lines 26–29

    uses Nat.cast_zero

      have hh := hsum τ
      rw [hzero] at hh
      simp only [Nat.cast_zero] at hh
      linarith
has_depth_three_amc_proof.match_1
The pattern-matching recursor that evaluates a literal into its positive or negative case.
List.length_eq_zero_iff
A list has length 0 if and only if it is the empty list.
List.filter_eq_nil_iff
Filtering a list yields the empty list if and only if no element satisfies the predicate.
decide_eq_true_eq
Deciding a decidable proposition equals true if and only if the proposition is true.
Finset.sum_nonneg
A finite sum of non-negative elements is non-negative.
Finset.prod_nonneg
A finite product of non-negative elements is non-negative.
Nat.cast_zero
The natural number 0 coerced to an additive monoid with one (such as the real numbers) is 0.

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

/-- Soundness: if a DNF formula admits a depth-three AMC proof at positive shift, it is a tautology. -/theorem depth_three_amc_soundness (n : ℕ) (A : List (List (CnfLit (Fin n)))) (ε : ℝ) (hε : 0 < ε) (r : ℕ)    (h : has_depth_three_amc_proof n A ε r) : is_dnf_tautology A := by  classical  obtain ⟨R, hR, hsum⟩ := h  unfold has_depth_three_amc_proof.match_1 at hsum  intro τ  by_contra hcon  have hzero : (A.filter (fun t => decide (∀ l ∈ t,      CnfLit.casesOn l (fun v => τ v = true) (fun v => τ v = false)))).length = 0 := by    rw [List.length_eq_zero_iff, List.filter_eq_nil_iff]    intro t ht    simp only [decide_eq_true_eq]    intro hh    apply hcon    refine ⟨t, ht, ?_⟩    intro l hl    have := hh l hl    cases l <;> simpa using this  have hnonneg : 0 ≤ ∑ j : Fin r, R j τ := by    apply Finset.sum_nonneg    intro j _    obtain ⟨g, hg, hRg⟩ := hR j    rw [hRg τ]    exact Finset.prod_nonneg (fun i _ => hg i (τ i))  have hh := hsum τ  rw [hzero] at hh  simp only [Nat.cast_zero] at hh  linarith
See it in the graphDiscuss this resultChallenge it