Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Layerings and fan-in over the published circuit DAG

Definition
ParityBarrier563_Trilinear_Supplement_Layering

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

boolean-circuitscomplexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

A layering assigns every gate of the published circuit DAG to one of d alternating layers. Layer one reads literals and constants; later layers read previous-layer gates and constants; the output is the unique top-layer gate. Evaluation and gate count are those of the published circuit. Define

BottomBound⁡(C,τ,k)  ⟺  each bottom gate reads at most k live literal wires.\operatorname{BottomBound}(C,\tau,k)\iff\text{each bottom gate reads at most }k\text{ live literal wires}.BottomBound(C,τ,k)⟺each bottom gate reads at most k live literal wires.

The full bottom bound leaves all variables live. The top bound counts gate wires entering the output. Unary gates count as gates, constants do not count as live literals, and restrictions leave the DAG and its size intact. Repeated wires may be deleted without changing evaluation or increasing any size or fan-in bound. Either output kind is allowed.

Definition code
import Mathlib
import Definitions.Def_ParityBarrier563_Trilinear_Circuit
import Definitions.Def_ParityBarrier563_Trilinear_Supplement_FiniteAverages

set_option autoImplicit false
open scoped Classical

namespace ParityBarrier563.Trilinear.Supplement

/-- A layering of the published DAG: all actual gates remain counted, constants may enter
any layer, unary gates are actual gates, and the top layer consists of the output alone. -/
structure Layering {V : Type} (C : Circuit V) (d : ℕ) where
  level : Fin C.size → Fin d
  layerKind : Fin d → GateKind
  gateKind : ∀ i, C.kind i = layerKind (level i)
  alternating : ∀ i j, i.val + 1 = j.val → layerKind i ≠ layerKind j
  outputGate : Fin C.size
  output_eq : C.output = .gate outputGate
  outputLevel : (level outputGate).val + 1 = d
  top_unique : ∀ i, (level i).val + 1 = d → i = outputGate
  wires : ∀ i, ∀ a ∈ C.inputs i, match a with
    | .lit _ _ => (level i).val = 0
    | .const _ => True
    | .gate j => (level ⟨j.val, Nat.lt_trans j.isLt i.isLt⟩).val + 1 = (level i).val

/-- Fan-in counts literal wires. Under restriction, only live literals count; constants
and wires from previous gates do not. No simplifying or deleting gates takes place. -/
def BottomBound {V : Type} {C : Circuit V} {d : ℕ} (L : Layering C d)
    (τ : Restriction V) (k : ℝ) : Prop :=
  ∀ i, (L.level i).val = 0 →
    (((C.inputs i).countP (fun a => match a with
      | .lit v _ => (τ v).isNone
      | _ => false) : ℕ) : ℝ) ≤ k

/-- Unrestricted bottom fan-in bound. -/
def BottomBoundFull {V : Type} {C : Circuit V} {d : ℕ} (L : Layering C d)
    (k : ℝ) : Prop := BottomBound L (fun _ => none) k

/-- The top fan-in counts the preceding-layer gate wires read by the output. -/
def TopBound {V : Type} {C : Circuit V} {d : ℕ} (L : Layering C d) (t : ℝ) : Prop :=
  (((C.inputs L.outputGate).countP (fun a => match a with
    | .gate _ => true
    | _ => false) : ℕ) : ℝ) ≤ t

end ParityBarrier563.Trilinear.Supplement
Source
Nikolai Chukhin, Xin Li, Ivan Mihajlin, Yan Zhong, Breaking the Parity Barrier for Constant-Depth Circuits, STOC 2027 submission #563 (October 2026), §2, printed pp.10–11 / PDF 12–13; Lemma 6.3 preamble, printed p.27 / PDF 29

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