depth_three_amc_soundness
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.
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.
uses
has_depth_three_amc_proof.match_1classical obtain ⟨R, hR, hsum⟩ := h unfold has_depth_three_amc_proof.match_1 at hsum
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 τ.
intro τ by_contra hcon
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.
uses
List.length_eq_zero_iff,List.filter_eq_nil_iff,decide_eq_true_eqhave 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
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.
uses
Finset.sum_nonneg,Finset.prod_nonneghave 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))
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.
uses
Nat.cast_zerohave 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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