Near-Quartic Wire Lower Bounds for SYM∘THR Circuits

We prove that a language in E^NP requires n⁴/polylog n wires to be computed by SYM∘THR circuits. These circuits apply an arbitrary symmetric function to the outputs of arbitrary real-weight threshold gates. The bound holds even when the circuit may err on a sufficiently small constant fraction of inputs, and it holds at every sufficiently large input length. The wire count charges every input of every threshold gate and every connection into the output gate. A circuit with G threshold gates has at most (n+1)G wires. So the theorem also gives the near-cubic gate lower bound for this class, with a slightly smaller logarithmic loss. More generally, it gives about n⁴/f gates when every gate reads at most f inputs. For example, circuits whose gates each read at most √n inputs need about n^{7/2} gates. The proof follows Williams' algorithmic method. We give a certified counting algorithm for pairs of such circuits that runs in time 2ⁿ/n^{Ω(log log n)} below the wire cap. We then transfer it to a lower bound through the almost-everywhere framework of Chen–Lyu–Williams, in the form developed for the near-cubic gate bound. The exponent comes from two earlier ideas: 4 = 3/2 + 5/2. - 3/2: a partition of the cube into products of Hamming-code stars bounds the expected number of gates with a nonzero mixed residual by Õ(W/n^{3/2}). - 5/2: nested subsampling followed by modular discrete tomography recovers exact score distributions for populations up to n^{5/2}/polylog n. The new step joins them. We run a matrix sampler on Fourier characters of the mixed residuals. A cycle-sum identity then shows that the sampler's trace potential depends on the circuits only through one integer per circuit and closed walk: a signed sum of mixed residuals along the walk. That integer is exactly what localization and tomography can count. The masks are exact integer polynomials, built from Newton forward differences, so one mask serves every prime modulus of the tomography.