AFTD Auto-Formalizing Theoretical Domains

depth_three_amc_separation_from_asymptotic_family

theoremverified

Any asymptotic family of DNF formulas satisfying the AMC upper bound and bounded-bias lower bound for k ≥ k₀ extends to a full family satisfying the separation theorem, using AMC soundness to establish tautology for k ≥ k₀ and padding with the empty clause for k < k₀.

Statement

theorem depth_three_amc_separation_from_asymptotic_family
    (ε : ℝ) (hε_pos : 0 < ε) (hε_le : ε ≤ 1)
    (v : ℕ → ℕ) (hv : ∀ k, k ≤ v k)
    (A : (k : ℕ) → List (List (CnfLit (Fin (v k)))))
    (c : ℕ) (k₀ : ℕ)
    (h_ub : ∀ k ≥ k₀, ∃ r ≤ (v k) ^ c + c, has_depth_three_amc_proof (v k) (A k) ε r)
    (h_lb : ∀ c' : ℕ, ∃ k₀' : ℕ, ∀ k ≥ k₀', ∀ s : ℕ, has_depth_three_amc_bounded_bias_proof (v k) (A k) ε s → (v k) ^ c' < s)
    (h_sound : ∀ n (F : List (List (CnfLit (Fin n)))) r, has_depth_three_amc_proof n F ε r → is_dnf_tautology F) :
    ∃ ε : ℝ, 0 < ε ∧ ε ≤ 1 ∧
      ∃ (v : ℕ → ℕ) (hv : ∀ k, k ≤ v k) (A : (k : ℕ) → List (List (CnfLit (Fin (v k))))),
        (∀ k, is_dnf_tautology (A k)) ∧
        (∃ c : ℕ, ∃ k₀ : ℕ, ∀ k ≥ k₀, ∃ r ≤ (v k) ^ c + c, has_depth_three_amc_proof (v k) (A k) ε r) ∧
        (∀ c : ℕ, ∃ k₀ : ℕ, ∀ k ≥ k₀, ∀ s : ℕ, has_depth_three_amc_bounded_bias_proof (v k) (A k) ε s → (v k) ^ c < s)
Source
step towards op_983_depth_three_amc_separation_at_constant_shift
Verified
05 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), ε…
  • CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.
  • 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), ε…
  • 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.

The proof, explained

To extend an asymptotic separation family to all k, we define a new family of DNF formulas that pads with the empty clause [[]] for indices k < k₀ and retains the original formulas A(k) for k ≥ k₀. The padded formula [[]] is trivially a tautology because its empty clause is satisfied by every assignment, while for k ≥ k₀ tautology follows from AMC soundness applied to the assumed AMC proof of A(k). The AMC upper bound persists with the original threshold k₀, and the bounded-bias lower bound persists by setting the threshold to max(k₀', k₀), where k₀' is the threshold for the given exponent.

  1. Define the extended family of formulas by setting A'(k) = [[]] when k < k₀ and A'(k) = A(k) when k ≥ k₀.

    We witness the existential quantifiers by providing the original error parameter ε, the variable-count function v, and a piecewise-defined formula family that pads with the empty-clause formula [[]] for indices k < k₀ and retains the original formulas A(k) for k ≥ k₀. This reduces the theorem to three subgoals: proving every formula in the extended family is a DNF tautology, verifying the depth-three AMC upper bound, and verifying the bounded-bias AMC lower bound.

    line 15

      refine ⟨ε, hε_pos, hε_le, v, hv, fun k => if k < k₀ then [[]] else A k, ?_, ?_, ?_⟩
  2. For k < k₀, the formula [[]] is a DNF tautology.

    When k < k₀, the definition evaluates to [[]]. A DNF formula is a tautology if every truth assignment satisfies at least one of its clauses (terms). Here, the formula contains the empty clause [], which has no literals to falsify and is therefore vacuously satisfied by every truth assignment τ.

    lines 16–19

    uses if_true

      · intro k
        by_cases hk : k < k₀
        · simp only [hk, if_true]
          intro τ; exact ⟨[], by simp, by simp⟩
  3. For k ≥ k₀, the formula A(k) is a DNF tautology.

    When k ≥ k₀, the definition evaluates to A(k). By the upper bound hypothesis (h_ub), A(k) admits a depth-three AMC proof of size r. AMC soundness (h_sound) then implies that A(k) is a DNF tautology.

    lines 20–22

    uses if_false, Nat.le_of_not_lt

        · simp only [hk, if_false]
          obtain ⟨r, _, hr⟩ := h_ub k (Nat.le_of_not_lt hk)
          exact h_sound (v k) (A k) r hr
  4. The extended family satisfies the depth-three AMC upper bound.

    Using the original degree bound c and threshold k₀, whenever k ≥ k₀ we have ¬(k < k₀), so the formula simplifies to A(k). The upper bound hypothesis on A(k) directly provides an AMC proof of size r ≤ (v(k))^c + c.

    lines 23–26

    uses Nat.not_lt.mpr

      · refine ⟨c, k₀, ?_⟩
        intro k hk
        obtain ⟨r, hr, hp⟩ := h_ub k hk
        exact ⟨r, hr, by simpa [Nat.not_lt.mpr hk] using hp⟩
  5. The extended family satisfies the superpolynomial lower bound against bounded-bias depth-three AMC proofs.

    Given any degree c', the lower bound hypothesis for A supplies a threshold k₀'. We set the new threshold to max(k₀', k₀). For any k ≥ max(k₀', k₀), transitivity yields both k ≥ k₀' and k ≥ k₀. Since k ≥ k₀, the formula coincides with A(k), so any bounded-bias proof of size s is a proof of A(k). Since k ≥ k₀', the lower bound hypothesis on A guarantees that (v(k))^{c'} < s.

    lines 27–35

    uses le_trans, le_max_left, le_max_right, Nat.not_lt.mpr

      · intro c'
        obtain ⟨k₀', hk'⟩ := h_lb c'
        refine ⟨max k₀' k₀, ?_⟩
        intro k hk s hs
        have h1 : k₀' ≤ k := le_trans (le_max_left _ _) hk
        have h2 : k₀ ≤ k := le_trans (le_max_right _ _) hk
        have hA : (if k < k₀ then [[]] else A k) = A k := by simp [Nat.not_lt.mpr h2]
        simp only [hA] at hs
        exact hk' k h1 s hs
if_true
An if-then-else expression whose condition is True simplifies to its then-branch.
if_false
An if-then-else expression whose condition is False simplifies to its else-branch.
Nat.le_of_not_lt
If a natural number is not strictly less than another, then the second is less than or equal to the first.
Nat.not_lt.mpr
If b ≤ a for natural numbers, then a is not strictly less than b.
le_trans
The inequality relation ≤ is transitive: if a ≤ b and b ≤ c, then a ≤ c.
le_max_left
For any elements a and b, a ≤ max a b.
le_max_right
For any elements a and b, b ≤ max a b.

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

/-- Given an asymptotic family separating depth-three AMC from bounded-bias AMC for k ≥ k₀, one can extend it to all k by padding small k with the empty clause [[]] and applying soundness for k ≥ k₀. -/theorem depth_three_amc_separation_from_asymptotic_family    (ε : ℝ) (hε_pos : 0 < ε) (hε_le : ε ≤ 1)    (v : ℕ → ℕ) (hv : ∀ k, k ≤ v k)    (A : (k : ℕ) → List (List (CnfLit (Fin (v k)))))    (c : ℕ) (k₀ : ℕ)    (h_ub : ∀ k ≥ k₀, ∃ r ≤ (v k) ^ c + c, has_depth_three_amc_proof (v k) (A k) ε r)    (h_lb : ∀ c' : ℕ, ∃ k₀' : ℕ, ∀ k ≥ k₀', ∀ s : ℕ, has_depth_three_amc_bounded_bias_proof (v k) (A k) ε s → (v k) ^ c' < s)    (h_sound : ∀ n (F : List (List (CnfLit (Fin n)))) r, has_depth_three_amc_proof n F ε r → is_dnf_tautology F) :    ∃ ε : ℝ, 0 < ε ∧ ε ≤ 1 ∧      ∃ (v : ℕ → ℕ) (hv : ∀ k, k ≤ v k) (A : (k : ℕ) → List (List (CnfLit (Fin (v k))))),        (∀ k, is_dnf_tautology (A k)) ∧        (∃ c : ℕ, ∃ k₀ : ℕ, ∀ k ≥ k₀, ∃ r ≤ (v k) ^ c + c, has_depth_three_amc_proof (v k) (A k) ε r) ∧        (∀ c : ℕ, ∃ k₀ : ℕ, ∀ k ≥ k₀, ∀ s : ℕ, has_depth_three_amc_bounded_bias_proof (v k) (A k) ε s → (v k) ^ c < s) := by  refine ⟨ε, hε_pos, hε_le, v, hv, fun k => if k < k₀ then [[]] else A k, ?_, ?_, ?_⟩  · intro k    by_cases hk : k < k₀    · simp only [hk, if_true]      intro τ; exact ⟨[], by simp, by simp⟩    · simp only [hk, if_false]      obtain ⟨r, _, hr⟩ := h_ub k (Nat.le_of_not_lt hk)      exact h_sound (v k) (A k) r hr  · refine ⟨c, k₀, ?_⟩    intro k hk    obtain ⟨r, hr, hp⟩ := h_ub k hk    exact ⟨r, hr, by simpa [Nat.not_lt.mpr hk] using hp⟩  · intro c'    obtain ⟨k₀', hk'⟩ := h_lb c'    refine ⟨max k₀' k₀, ?_⟩    intro k hk s hs    have h1 : k₀' ≤ k := le_trans (le_max_left _ _) hk    have h2 : k₀ ≤ k := le_trans (le_max_right _ _) hk    have hA : (if k < k₀ then [[]] else A k) = A k := by simp [Nat.not_lt.mpr h2]    simp only [hA] at hs    exact hk' k h1 s hs
See it in the graphDiscuss this resultChallenge it