Theorem 6.1: depth- circuits for -Clique with need more than gates
OpenHypercliqueAC0.FixedDepth.Supplement.theorem_6_1Let be the Boolean function that receives one bit for every pair of the vertex set and outputs one exactly when the graph contains a clique on vertices. A depth- circuit is a De Morgan circuit (unbounded fan-in AND and OR gates over literals and constants) of depth at most , and its gate size is the number of its noninput gates.
For every integer and every real there are integers and a real such that, for every and every integer with
every depth- circuit computing satisfies
The constants depend only on and . Compared with the hyperclique goal at , the range of is wider by one layer of the circuit: instead of .
Formalization Note is the published hyperclique n 2 k on the pair type Edge n 2. No restriction is added; for larger the range of may be empty, as in the source.
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: integer thresholds and integers → natural numbers, with real casts before division and exponentiation; reason: all are lower thresholds or counts, and a natural threshold can dominate any integer threshold without changing the conclusion
- 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
import Mathlib import Definitions.Def_MantriCVQ_ACCircuit import Definitions.Def_HypercliqueAC0_FixedDepth_Hypergraphs noncomputable section
namespace HypercliqueAC0.FixedDepth.Supplement
open HypercliqueAC0.FixedDepth
/-- Theorem 6.1, p. 20 (PDF 22). `k-Clique_n` is `hyperclique n 2 k` on the edge variables
`Edge n 2`; a depth-`h` circuit is a De Morgan circuit of depth at most `h`, and its gate size is
the length of its gate list. The constants `k₀, n₀, c` depend only on `h` and `ε`; the bound is
strict. No restriction `ε < 1/(h−1)` is added. -/
theorem theorem_6_1 (h : ℕ) (hh : 2 ≤ h) (ε : ℝ) (hε : 0 < ε) :
∃ k₀ n₀ : ℕ, ∃ c : ℝ, 0 < c ∧
∀ n : ℕ, n₀ ≤ n → ∀ k : ℕ, k₀ ≤ 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 : ℝ) := by sorry
end HypercliqueAC0.FixedDepth.Supplement