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.
Description
Given a matrix-symmetric circuit , the circuit is obtained by merging gates that are equivalent under a height-indexed recursive equivalence relation (): 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 (), into every class of smaller height. keeps only the classes (canonical representatives chosen via ) from which the class of the output gate can still be reached. is reduced because distinct classes are never merged (); it computes the same polynomial because every gate computes what its class computes (, via a determinism lemma for ); it has size and depth at most those of because classes are collapsed gates/wires () and every path of lifts to a same-length path of (); it is matrix-symmetric because every automorphism of preserves the equivalence relation and height (), hence induces an automorphism of extending the same renaming; and since is reduced and matrix-symmetric it is rigid (), which forces every automorphism of to be induced this way, so orbits of are images of orbits of and hence no larger ().