Internal: Schnorr's Lower Bound for XOR Circuits

This internal module proves Schnorr's lower bound via the CircDesc model. The public definitions (Schnorr.xorBool, Schnorr.xorBool_flip, Schnorr.xorBool_essential) are in Complexitylib.Circuits.XOR. The public theorem schnorr_lower_bound_circuit is accessible through Complexitylib.Circuits.Schnorr.

def Complexity.Schnorr.insertAt {N : ℕ} (x : BitString N) (a : Fin (N + 1)) (b : Bool) : BitString (N + 1)

Insert value b at position a in a BitString.

Equations

• Complexity.Schnorr.insertAt x a b j = if h1 : ↑j < ↑a then x ⟨↑j, ⋯⟩ else if h2 : ↑j = ↑a then b else x ⟨↑j - 1, ⋯⟩

theorem Complexity.Schnorr.xorBool_insertAt {N : ℕ} (x : BitString N) (a : Fin (N + 1)) (b : Bool) : xorBool (N + 1) (insertAt x a b) = (b ^^ xorBool N x)

XOR with an inserted bit equals the inserted bit XORed with XOR of the rest.

CircDesc Insensitivity

theorem Complexity.Schnorr.wireVal_eq_of_unreferenced {N s : ℕ} (d : CircDesc N s) (a : Fin N) (b : Bool) (hno : ∀ (g : Fin s), ↑(d g).2.1.1 ≠ ↑a ∧ ↑(d g).2.1.2 ≠ ↑a) (x : BitString N) (w : Fin (N + s)) (hw : ↑w ≠ ↑a) : d.wireVal x w = d.wireVal (Function.update x a b) w

If no gate references input a, wire values are unchanged when a is modified.

theorem Complexity.Schnorr.eval_essential_means_referenced {N s : ℕ} (d : CircDesc N s) (hs : 0 < s) (a : Fin N) (hdep : ∃ (x : BitString N), CircDesc.eval hs d x ≠ CircDesc.eval hs d (Function.update x a !x a)) : ∃ (g : Fin s), ↑(d g).2.1.1 = ↑a ∨ ↑(d g).2.1.2 = ↑a

If evaluation depends on input a, some gate references a.

Circuit Restriction

def Complexity.Schnorr.remapWireR {N s : ℕ} (a : Fin (N + 1)) (b : Bool) (g : Fin s) (wi : Fin (N + 1 + s)) (ni : Bool) : Fin (N + s) × Bool

Remap a wire reference when fixing input a.

Equations

• Complexity.Schnorr.remapWireR a b g wi ni = if h1 : ↑wi = ↑a then (⟨N + ↑g, ⋯⟩, ni ^^ b) else if h2 : ↑wi < ↑a then (⟨↑wi, ⋯⟩, ni) else (⟨↑wi - 1, ⋯⟩, ni)

def Complexity.Schnorr.restrictD {N s : ℕ} (d : CircDesc (N + 1) s) (a : Fin (N + 1)) (b : Bool) : CircDesc N s

Fix primary input a of a CircDesc (N+1) s to value b.

Equations

• One or more equations did not get rendered due to their size.

theorem Complexity.Schnorr.eval_restrictD {N s : ℕ} (d : CircDesc (N + 1) s) (hs : 0 < s) (a : Fin (N + 1)) (b : Bool) (x : BitString N) : CircDesc.eval hs (restrictD d a b) x = CircDesc.eval hs d (insertAt x a b)

Evaluating the restricted circuit on x agrees with evaluating the original circuit on x with the fixed bit b inserted at position a.

Gate Elimination

inductive Complexity.Schnorr.GateRedirect (W : ℕ) : Type

How to redirect references to an eliminated gate.

• const {W : ℕ} (c : Bool) : GateRedirect W

  Replace references to the eliminated gate by the constant c.

• wire {W : ℕ} (w : Fin W) (flip : Bool) : GateRedirect W

  Replace references to the eliminated gate by wire w, XORed with flip.

def Complexity.Schnorr.remapWireE {N s : ℕ} (g : Fin (s + 1)) (rd : GateRedirect (N + s)) (i : Fin s) (wi : Fin (N + (s + 1))) (ni : Bool) : Fin (N + s) × Bool

Remap a wire reference when eliminating gate g.

Equations

• One or more equations did not get rendered due to their size.

def Complexity.Schnorr.elimGateD {N s : ℕ} (d : CircDesc N (s + 1)) (g : Fin (s + 1)) (rd : GateRedirect (N + s)) : CircDesc N s

Remove gate g from a CircDesc, redirecting references to it.

Equations

• One or more equations did not get rendered due to their size.

theorem Complexity.Schnorr.eval_elimGateD {N s : ℕ} (d : CircDesc N (s + 1)) (hs : 0 < s) (g : Fin (s + 1)) (rd : GateRedirect (N + s)) (hrd : ∀ (x : BitString N), d.wireVal x ⟨N + ↑g, ⋯⟩ = match rd with | GateRedirect.const c => c | GateRedirect.wire w flip => flip ^^ d.wireVal x ⟨↑w, ⋯⟩) (hrd_wire : ∀ (w' : Fin (N + s)) (flip : Bool), rd = GateRedirect.wire w' flip → ↑w' < N + ↑g) (hg_not_last : ↑g < s) (x : BitString N) : CircDesc.eval hs (elimGateD d g rd) x = CircDesc.eval ⋯ d x

Eliminating a non-output gate whose value the redirect rd correctly describes preserves the circuit's evaluation on every input.

XOR needs ≥ 3 gates

Restriction eliminates two gates

theorem Complexity.Schnorr.restriction_eliminates_two {n s : ℕ} (d : CircDesc (n + 1) s) (hs : 0 < s) (hn : 0 < n) (comp : Bool) (heval : ∀ (x : BitString (n + 1)), CircDesc.eval hs d x = (comp ^^ xorBool (n + 1) x)) (hessential : ∀ (a : Fin (n + 1)) (x : BitString (n + 1)), CircDesc.eval hs d x ≠ CircDesc.eval hs d (Function.update x a !x a)) : ∃ (s' : ℕ) (d' : CircDesc n s') (hs' : 0 < s') (comp' : Bool), s' + 2 ≤ s ∧ ∀ (x : BitString n), CircDesc.eval hs' d' x = (comp' ^^ xorBool n x)

Key inductive step: restricting one variable of a totally essential XOR circuit yields a circuit for XOR on one fewer input, with at least 2 fewer gates.

The 2(N-1) Lower Bound

theorem Complexity.Schnorr.xor_lower_bound_2 (N s : ℕ) (hs : 0 < s) (d : CircDesc N s) (comp : Bool) (heval : ∀ (x : BitString N), CircDesc.eval hs d x = (comp ^^ xorBool N x)) (hN : 1 ≤ N) : s + 1 ≥ 2 * N

Any DeMorgan circuit computing XOR_N (or complement) has ≥ 2N - 1 gates.