Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.1: depth-hhh circuits for kkk-Clique with k0≤k≤n1/(h−1)−εk_0\le k\le n^{1/(h-1)-\varepsilon}k0​≤k≤n1/(h−1)−ε need more than nckn^{ck}nck gates

Open
HypercliqueAC0.FixedDepth.Supplement.theorem_6_1

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricscomplexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let k-Cliquenk\text{-}\mathsf{Clique}_nk-Cliquen​ be the Boolean function that receives one bit xex_exe​ for every pair eee of the vertex set [n][n][n] and outputs one exactly when the graph {e:xe=1}\{e: x_e=1\}{e:xe​=1} contains a clique on kkk vertices. A depth-hhh circuit is a De Morgan circuit (unbounded fan-in AND and OR gates over literals and constants) of depth at most hhh, and its gate size G(C)G(C)G(C) is the number of its noninput gates.

For every integer h≥2h\ge2h≥2 and every real ε>0\varepsilon>0ε>0 there are integers k0,n0k_0,n_0k0​,n0​ and a real c>0c>0c>0 such that, for every n≥n0n\ge n_0n≥n0​ and every integer kkk with

k0≤k≤n1/(h−1)−ε,k_0\le k\le n^{1/(h-1)-\varepsilon},k0​≤k≤n1/(h−1)−ε,

every depth-hhh circuit CCC computing k-Cliquenk\text{-}\mathsf{Clique}_nk-Cliquen​ satisfies

G(C)>nck.G(C)>n^{ck}.G(C)>nck.

The constants depend only on hhh and ε\varepsilonε. Compared with the hyperclique goal at r=2r=2r=2, the range of kkk is wider by one layer of the circuit: n1/(h−1)n^{1/(h-1)}n1/(h−1) instead of n1/hn^{1/h}n1/h.

Formalization Note k-Cliquenk\text{-}\mathsf{Clique}_nk-Cliquen​ is the published hyperclique n 2 k on the pair type Edge n 2. No restriction ε<1/(h−1)\varepsilon<1/(h-1)ε<1/(h−1) is added; for larger ε\varepsilonε the range of kkk may be empty, as in the source.

Differences from the source:

  • encoding: [n]={1,…,n}[n]=\{1,\ldots,n\}[n]={1,…,n} and its pairs → Fin n\mathrm{Fin}\,nFinn with the edge subtype of cardinality 222; reason: a relabeling bijection preserves every graph and every circuit instance
  • encoding: integer thresholds k0,n0k_0,n_0k0​,n0​ and integers h,k,nh,k,nh,k,n → 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
Preamble
import Mathlib
import Definitions.Def_MantriCVQ_ACCircuit
import Definitions.Def_HypercliqueAC0_FixedDepth_Hypergraphs

noncomputable section
Formal statement
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
Source
Nikolai Chukhin, Exhaustive Search Is Hard to Beat in Constant Depth for Hyperclique and Orthogonal Vectors, STOC 2027 submission #830 (October 2026), source.pdf SHA-256 bd73fd887fe562527226e0ea2da24a55552a73cf89c2e90406a28965424a12de, p.20 (PDF p.22), Theorem 6.1

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me