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

Proof of `Rigidification`

groundedproofs/Lax461425Proofs/Rigidification.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

Given a matrix-symmetric circuit CC, the circuit C′:=RigidConstruction.reducedCC' := RigidConstruction.reduced C is obtained by merging gates that are equivalent under a height-indexed recursive equivalence relation (RigidEquiv.EquivRigidEquiv.Equiv): input gates are equivalent iff they share a label, and internal gates of matching height and label are equivalent iff they send the same total wire weight, aggregated by equivalence class (RigidWeight.WRigidWeight.W), into every class of smaller height. C′C' keeps only the classes (canonical representatives chosen via RigidRep.repRigidRep.rep) from which the class of the output gate can still be reached. C′C' is reduced because distinct classes are never merged (RigidReduced.isReducedreducedRigidReduced.isReduced_reduced); it computes the same polynomial because every gate computes what its class computes (RigidComputes.computestransferRigidComputes.computes_transfer, via a determinism lemma for ComputesAtComputesAt); it has size and depth at most those of CC because classes are collapsed gates/wires (RigidSize.sizereducedleRigidSize.size_reduced_le) and every path of C′C' lifts to a same-length path of CC (RigidDepth.depthreducedleRigidDepth.depth_reduced_le); it is matrix-symmetric because every automorphism of CC preserves the equivalence relation and height (RigidSymmetricRigidSymmetric), hence induces an automorphism of C′C' extending the same renaming; and since C′C' is reduced and matrix-symmetric it is rigid (Lax461425.ReducedRigid.isRigidLax461425.ReducedRigid.isRigid), which forces every automorphism of C′C' to be induced this way, so orbits of C′C' are images of orbits of CC and hence no larger (RigidOrbit.orbitSizereducedleRigidOrbit.orbitSize_reduced_le).