depth_three_amc_separation_from_asymptotic_family
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.
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.
refine ⟨ε, hε_pos, hε_le, v, hv, fun k => if k < k₀ then [[]] else A k, ?_, ?_, ?_⟩
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 τ.
uses
if_true· intro k by_cases hk : k < k₀ · simp only [hk, if_true] intro τ; exact ⟨[], by simp, by simp⟩
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.
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
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.
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⟩
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.
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
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.
/-- 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