AFTD Auto-Formalizing Theoretical Domains

depth_three_amc_of_bounded_bias

theoremverifiedformalization

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.

  1. 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.

    lines 5–6

      obtain ⟨R, hR, hsum⟩ := h
      refine ⟨R, ?_, hsum⟩
  2. 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.

    lines 7–9

      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

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