Theorem 1.5: depth-three circuits for -OV in dimension need wires
OpenHypercliqueAC0.FixedDepth.Supplement.theorem_1_5Let be Orthogonal Vectors on two lists of vectors in : it outputs one exactly when some vector of the first list and some vector of the second list have no coordinate where both are one. A depth-three circuit is a De Morgan circuit (unbounded fan-in AND and OR gates over literals and constants) of depth at most three, and its wire size is the number of edges of its underlying graph. is the base-two logarithm.
For every fixed there is a constant such that, for all sufficiently large and every , every depth-three circuit computing satisfies
The input has bits, so a quadratic number of wires is far above the input length; this resolves the depth-three case of a conjecture of Kane and Williams for -OV in logarithmic dimension.
Formalization Note is the published ErrAmpOV.kOV 2 n d. is the total fan-in, the sum of the lengths of the gates' input lists, not the published size (gates plus wires). The constant and the threshold on depend only on .
Differences from the source:
- encoding: two lists of vectors in → Boolean variables indexed by (the published
ErrAmpOV.kOV 2 n d); reason: a relabeling bijection preserves every instance - encoding: integers and the threshold for "sufficiently large " → natural numbers, with real casts; reason: all are counts or lower thresholds, and a natural threshold can dominate any integer threshold
- encoding: the number of edges of the circuit graph, under the §3.2 convention that every gate reaches the output → the total length of the gates' input lists over arbitrary circuits, including unused gates and repeated entries; reason: pruning unused gates and deleting repeated entries preserve output and depth and cannot increase this count, and on a pruned circuit without repetitions it equals the number of edges
import Mathlib import Definitions.Def_ErrAmpOV_kOV import Definitions.Def_HypercliqueAC0_FixedDepth_Supplement_Wires noncomputable section
namespace HypercliqueAC0.FixedDepth.Supplement
/-- Theorem 1.5, p. 24 (PDF 26), stated also on p. 5 (PDF 7). `2-OV_{n,d}` is
`ErrAmpOV.kOV 2 n d`; a depth-three circuit has depth at most three; `log` is base two; the wire
size `W(C)` is the total fan-in `wires C`. The constant `c_η` and the threshold `n₀` depend only
on `η`, and every dimension `d ≥ (1+η) log n` is covered. -/
theorem theorem_1_5 (η : ℝ) (hη : 0 < η) :
∃ c : ℝ, 0 < c ∧ ∃ n₀ : ℕ, ∀ n : ℕ, n₀ ≤ n → ∀ d : ℕ,
(1 + η) * Real.logb 2 n ≤ (d : ℝ) →
∀ C : MantriCVQ.ACCircuit (Fin 2 × Fin n × Fin d), C.depth ≤ 3 →
(∀ x, C.eval x = ErrAmpOV.kOV 2 n d x) →
c * (n : ℝ) ^ 2 ≤ (wires C : ℝ) := by sorry
end HypercliqueAC0.FixedDepth.Supplement