Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.3: depth-hhh circuits for kkk-OV in dimension d≥(log⁡n)Oh,ε(1)d\ge(\log n)^{O_{h,\varepsilon}(1)}d≥(logn)Oh,ε​(1) need nk(1−ε)n^{k(1-\varepsilon)}nk(1−ε) gates

Open
HypercliqueAC0.FixedDepth.Supplement.theorem_1_3

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

complexity-theoryorthogonal-vectorsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

An instance of k-OVn,dk\text{-}\mathsf{OV}_{n,d}k-OVn,d​ consists of kkk lists Ai=(ai,1,…,ai,n)A_i=(a_{i,1},\dots,a_{i,n})Ai​=(ai,1​,…,ai,n​) of vectors in {0,1}d\{0,1\}^d{0,1}d, and

k-OVn,d(A1,…,Ak)=1  ⟺  ∃(j1,…,jk)∈[n]k: ⋀i=1kai,ji=0d.k\text{-}\mathsf{OV}_{n,d}(A_1,\dots,A_k)=1\iff\exists(j_1,\dots,j_k)\in[n]^k:\ \bigwedge_{i=1}^k a_{i,j_i}=0^d .k-OVn,d​(A1​,…,Ak​)=1⟺∃(j1​,…,jk​)∈[n]k: i=1⋀k​ai,ji​​=0d.

A depth-hhh circuit is a De Morgan circuit of depth at most hhh, G(C)G(C)G(C) is its number of noninput gates, and log⁡\loglog is the base-two logarithm. The theorem has two claims.

  1. For every integer h≥1h\ge1h≥1 and every ε>0\varepsilon>0ε>0 there is an exponent KKK, depending only on hhh and ε\varepsilonε, such that for every fixed k≥2k\ge2k≥2 there is n0n_0n0​ with the following property: for every n≥n0n\ge n_0n≥n0​ and every dimension d≥(log⁡n)Kd\ge(\log n)^Kd≥(logn)K, every depth-hhh circuit CCC computing k-OVn,dk\text{-}\mathsf{OV}_{n,d}k-OVn,d​ satisfies
G(C)≥nk(1−ε).G(C)\ge n^{k(1-\varepsilon)}.G(C)≥nk(1−ε).
  1. For every integer h≥1h\ge1h≥1, every ε>0\varepsilon>0ε>0 and every k≥2k\ge2k≥2 there are an exponent K′K'K′ and n0n_0n0​ such that for every n≥n0n\ge n_0n≥n0​ and every d≥(log⁡n)K′d\ge(\log n)^{K'}d≥(logn)K′, every depth-hhh circuit CCC computing k-OVn,dk\text{-}\mathsf{OV}_{n,d}k-OVn,d​ satisfies
G(C)≥nk−ε.G(C)\ge n^{k-\varepsilon}.G(C)≥nk−ε.

The exhaustive-search circuit uses about nkn^knk gates, so the bound shows that exhaustive search is nearly optimal for kkk-OV at every fixed depth in polylogarithmic dimension.

Formalization Note k-OVn,dk\text{-}\mathsf{OV}_{n,d}k-OVn,d​ is the published ErrAmpOV.kOV k n d, whose variable (i, j, q) is coordinate qqq of vector jjj of list iii. In the first claim the exponent KKK is chosen before kkk, so it is uniform in kkk; in the second it may depend on kkk. Every dimension ddd above the threshold is covered.

Differences from the source:

  • encoding: kkk lists of nnn vectors in {0,1}d\{0,1\}^d{0,1}d → Boolean variables indexed by Fin k×Fin n×Fin d\mathrm{Fin}\,k\times\mathrm{Fin}\,n\times\mathrm{Fin}\,dFink×Finn×Find (the published ErrAmpOV.kOV); reason: a relabeling bijection preserves every instance
  • encoding: integers h,k,n,dh,k,n,dh,k,n,d and the threshold for "sufficiently large nnn" → natural numbers, with real casts before 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: "d≥(log⁡n)Oh,ε(1)d\ge(\log n)^{O_{h,\varepsilon}(1)}d≥(logn)Oh,ε​(1)" in the first claim → there is a real exponent KKK chosen after h,εh,\varepsilonh,ε and before kkk, and the claim holds for every d≥(log⁡n)Kd\ge(\log n)^Kd≥(logn)K; reason: the subscript names exactly h,εh,\varepsilonh,ε, and the proof takes K=⌈r/θ⌉+1K=\lceil r/\theta\rceil+1K=⌈r/θ⌉+1 depending only on h,εh,\varepsilonh,ε
  • reading: "d≥(log⁡n)Oh,k,ε(1)d\ge(\log n)^{O_{h,k,\varepsilon}(1)}d≥(logn)Oh,k,ε​(1)" in the second claim → there is a real exponent K′K'K′ chosen after h,ε,kh,\varepsilon,kh,ε,k; reason: the subscript names exactly h,k,εh,k,\varepsilonh,k,ε
Preamble
import Mathlib
import Definitions.Def_MantriCVQ_ACCircuit
import Definitions.Def_ErrAmpOV_kOV

noncomputable section
Formal statement
namespace HypercliqueAC0.FixedDepth.Supplement

/-- Theorem 1.3, p. 4 (PDF 6), both claims. `k-OV_{n,d}` is `ErrAmpOV.kOV k n d` on the
variables `Fin k × Fin n × Fin d`; `log` is base two. First claim: the exponent `K` of the
dimension threshold `(log n)^K` depends only on `h, ε` (it is chosen before `k`), and the
threshold `n₀` on `h, ε, k`. Second claim: the exponent `K'` may depend on `h, k, ε`. Every
dimension `d` above the threshold is covered. -/
theorem theorem_1_3 :
    (∀ h : ℕ, 1 ≤ h → ∀ ε : ℝ, 0 < ε → ∃ K : ℝ, ∀ k : ℕ, 2 ≤ k →
      ∃ n₀ : ℕ, ∀ n : ℕ, n₀ ≤ n → ∀ d : ℕ, (Real.logb 2 n) ^ K ≤ (d : ℝ) →
        ∀ C : MantriCVQ.ACCircuit (Fin k × Fin n × Fin d), C.depth ≤ h →
          (∀ x, C.eval x = ErrAmpOV.kOV k n d x) →
          (n : ℝ) ^ ((k : ℝ) * (1 - ε)) ≤ (C.gates.length : ℝ)) ∧
    (∀ h : ℕ, 1 ≤ h → ∀ ε : ℝ, 0 < ε → ∀ k : ℕ, 2 ≤ k → ∃ K : ℝ,
      ∃ n₀ : ℕ, ∀ n : ℕ, n₀ ≤ n → ∀ d : ℕ, (Real.logb 2 n) ^ K ≤ (d : ℝ) →
        ∀ C : MantriCVQ.ACCircuit (Fin k × Fin n × Fin d), C.depth ≤ h →
          (∀ x, C.eval x = ErrAmpOV.kOV k n d x) →
          (n : ℝ) ^ ((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.4 (PDF p.6), Theorem 1.3; k-OV defined in §3.1 p.10 (PDF p.12); proof §7 pp.22-23 (PDF pp.24-25)

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