Theorem 1.2: depth- circuits for -Clique need gates for and gates for
OpenHypercliqueAC0.FixedDepth.Supplement.theorem_1_2Let be the Boolean function of the edge bits of a graph on that outputs one exactly when the graph contains a clique on vertices. A depth- circuit is a De Morgan circuit of depth at most , and is its number of noninput gates. The theorem has two claims.
- For every integer and every there are and , depending only on and , such that for every and every integer with , every depth- circuit computing satisfies
- For every integer and every there are and thresholds such that for every and every integer with , every depth- circuit computing satisfies
The first claim is the bound over the whole range of , including constant . The second claim is the paper's statement that gates are needed when and , matching Rossman's exponent for constant .
Formalization Note is the published hyperclique n 2 k on Edge n 2. The second claim is written in uniform form: for every sequence with and it gives the bound, and conversely, if the uniform form failed for some , the counterexamples for and , , would form such a sequence violating the sequence form.
Differences from the source:
- encoding: and its pairs → with the edge subtype of cardinality ; reason: a relabeling bijection preserves every graph and every circuit instance
- encoding: integers and the threshold for "sufficiently large " → natural numbers, with real casts before division and exponentiation; reason: all are counts or lower thresholds, and a natural threshold can dominate any integer threshold
- encoding: the §3.2 convention that every gate reaches the output → arbitrary circuits, including unused gates and repeated input sources, with gate count equal to the gate-list length; reason: pruning unused gates and deleting repeated sources preserve output and depth and cannot increase gate count
- reading: " gates if is sufficiently large" → there exist and depending only on with for all ; reason: the subscript of names exactly , so is uniform in and
- reading: "if tends to infinity and , then gates" → for every there are and such that , imply ; reason: this uniform form is equivalent to the statement for all sequences with , (see the Formalization Note)
import Mathlib import Definitions.Def_MantriCVQ_ACCircuit import Definitions.Def_HypercliqueAC0_FixedDepth_Hypergraphs noncomputable section
namespace HypercliqueAC0.FixedDepth.Supplement
open HypercliqueAC0.FixedDepth
/-- Theorem 1.2, p. 4 (PDF 6), both claims. First claim: `n^{Ω_{h,ε}(k)}` is `n^{c k}` with
`c > 0` depending only on `h, ε`, for every `3 ≤ k ≤ n^{1/(h−1)−ε}` once `n ≥ n₀(h, ε)`.
Second claim ("if `k → ∞` and `k = n^{o(1)}`, then `n^{(1/4−o(1))k}` gates"), in its uniform
form: for every `η > 0` there are `δ > 0` and thresholds `k₀, n₀` such that every
`k₀ ≤ k ≤ n^δ`, `n ≥ n₀` forces `n^{(1/4−η)k}` gates. This is equivalent to the sequence reading. -/
theorem theorem_1_2 :
(∀ h : ℕ, 2 ≤ h → ∀ ε : ℝ, 0 < ε →
∃ c : ℝ, 0 < c ∧ ∃ n₀ : ℕ, ∀ n : ℕ, n₀ ≤ n → ∀ k : ℕ, 3 ≤ k →
(k : ℝ) ≤ (n : ℝ) ^ (1 / ((h : ℝ) - 1) - ε) →
∀ C : MantriCVQ.ACCircuit (Edge n 2), C.depth ≤ h →
(∀ x, C.eval x = hyperclique n 2 k x) →
(n : ℝ) ^ (c * (k : ℝ)) ≤ (C.gates.length : ℝ)) ∧
(∀ h : ℕ, 2 ≤ h → ∀ η : ℝ, 0 < η →
∃ δ : ℝ, 0 < δ ∧ ∃ k₀ n₀ : ℕ, ∀ n : ℕ, n₀ ≤ n → ∀ k : ℕ, k₀ ≤ k →
(k : ℝ) ≤ (n : ℝ) ^ δ →
∀ C : MantriCVQ.ACCircuit (Edge n 2), C.depth ≤ h →
(∀ x, C.eval x = hyperclique n 2 k x) →
(n : ℝ) ^ ((1 / 4 - η) * (k : ℝ)) ≤ (C.gates.length : ℝ)) := by sorry
end HypercliqueAC0.FixedDepth.Supplement