depth_three_amc_of_bounded_bias
For every natural number n, every DNF formula A : List (List (CnfLit (Fin n))), every real shift parameter ε, and every proof size s : ℕ, if A has a bounded-bias depth-three AMC proof of size s at shift ε (has_depth_three_amc_bounded_bias_proof n A ε s), then A has an arbitrary-bias depth-three AMC proof of size s at shift ε (has_depth_three_amc_proof n A ε s).
Statement
theorem depth_three_amc_of_bounded_bias (n : ℕ) (A : List (List (CnfLit (Fin n)))) (ε : ℝ) (s : ℕ)
(h : has_depth_three_amc_bounded_bias_proof n A ε s) :
has_depth_three_amc_proof n A ε s- Formalizes
- arXiv:2611.01055, Section 2.3, page 23
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- has_depth_three_amc_bounded_bias_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), ε…
- 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_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.
Read back from the Lean
For every natural number $n$, list of lists of CNF literals over variables $\mathrm{Fin}\ n$ $A$, real number $\varepsilon$, and natural number $s$, if $A$ has a depth-three algebraic model counting (AMC) bounded-bias proof of size $s$ with error $\varepsilon$ (has_depth_three_amc_bounded_bias_proof n A ε s), then $A$ has a depth-three AMC proof of size $s$ with error $\varepsilon$ (has_depth_three_amc_proof n A ε s).
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 observes that every bounded-bias depth-three AMC proof is already an arbitrary-bias depth-three AMC proof. Both definitions represent the shifted satisfaction count of a DNF formula as a sum of rank-one products, but bounded-bias proofs additionally require the product factors to satisfy a bias trichotomy. Reusing the same family of functions R and discarding the unused bias condition immediately produces the required arbitrary-bias proof.
The same family of functions R witnesses the arbitrary-bias depth-three AMC proof, reducing the goal to showing that each R_j is a rank-one product.
From the hypothesis h that A has a bounded-bias proof, we unpack the family of functions R : Fin s → (Fin n → Bool) → ℝ, the factorization property hR of each component, and the sum equality hsum relating the shifted DNF count to ∑ j, R j. Proposing the same R as the witness for the arbitrary-bias proof, the sum equality is already satisfied by hsum, leaving only the requirement that each R j is a rank-one product.
obtain ⟨R, hR, hsum⟩ := h refine ⟨R, ?_, hsum⟩
Each component function R_j is a rank-one product.
Fix an arbitrary index j. The bounded-bias hypothesis provides a non-negative function g : Fin n → Bool → ℝ representing R j as the product ∏ i, g i (τ i), alongside a bias restriction. Discarding the superfluous bias restriction and supplying g with its non-negativity and product representation directly establishes that R j is a rank-one product.
intro j obtain ⟨g, hg0, -, hg⟩ := hR j exact ⟨g, hg0, hg⟩
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.
/-- Every bounded-bias depth-three AMC proof is an arbitrary-bias depth-three AMC proof of the same size and shift. -/theorem depth_three_amc_of_bounded_bias (n : ℕ) (A : List (List (CnfLit (Fin n)))) (ε : ℝ) (s : ℕ) (h : has_depth_three_amc_bounded_bias_proof n A ε s) : has_depth_three_amc_proof n A ε s := by obtain ⟨R, hR, hsum⟩ := h refine ⟨R, ?_, hsum⟩ intro j obtain ⟨g, hg0, -, hg⟩ := hR j exact ⟨g, hg0, hg⟩