Exponential-Scale Complexity of Fully Determinant-Symmetric Arithmetic Circuits: Oriented Minors, Residual Alternating Cores, and a Point-Anchor Threshold

Abstract

Symmetric arithmetic circuits require specified symmetries of the input variables to extend to automorphisms of the computation. For the determinant, polynomial-size symmetric circuits are known under simultaneous row and column permutations, whereas exponential lower bounds are known when even row and column permutations act independently. This preprint studies the natural determinant-preserving variable-permutation group generated by independent row and column permutations of equal parity together with transposition. Over fields of characteristic zero, we construct a homogeneous skew symmetric arithmetic circuit based on oriented minors. Its size is O(n^2 binom(2n,n)) = O(n^(3/2) 4^n). Combined with the known 2^{Omega(n)} lower bound for the alternating row-column subgroup, this determines the size of fully determinant-symmetric arithmetic circuits as 2^{Theta(n)} on the exponential scale. We then introduce the independent alternating residual rank of a partially anchored symmetry group and derive a lower bound exponential in this residual rank. For the balanced point-anchor model with q unanchored rows and q unanchored columns in an N x N matrix, we prove 2^{Omega(q)} <= s_F(N,q)<= N^{O(1)} q^2 binom(2q,q)<= N^{O(1)} 4^q. Consequently, polynomial-size residual-symmetric circuits exist exactly when q = O(log N). The results apply to symmetry-constrained arithmetic circuits over fields of characteristic zero in the circuit model stated in the manuscript. They do not imply lower bounds for unrestricted arithmetic circuits and do not resolve VP versus VNP or P versus NP.