While this submission is a draft, it cannot be used by other submissions.

Proof of `Support depth of symmetric formulas`

groundedproofs/Lax461425Proofs/SymVFSupportDepth.lean · lax-461425

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

The rigidification of a symmetric formula of orbit size <n.chooseκ< n.choose κ has support size ≤κ−1≤ κ - 1 by the support theorem, and support depth ≤2κ≤ 2κ: along any path, support-changing wires are moved by stabilisers so that each adds a new point to the union of supports; lifting to the formula, where non-input gates have unique parents, bounds both sides of this union by κ−1κ - 1 while the path ends in a non-input gate.