Powering requires threshold depth 3

We study the circuit complexity of the powering function, defined as POWm(Z)=Zm for an n-bit integer input Z and an integer exponent m⩽poly(n). Let denote the class of functions computable by a depth-d polynomial-size circuit of majority gates. We give a simple proof that for any m⩾2. Specifically, we prove a 2Ω(n/logn) lower bound on the size of any depth-2 majority circuit that computes POWm. This work generalizes Wegener's earlier result that the squaring function (i.e., POWm for the special case m=2) is not in . Our depth lower bound is optimal due to Siu and Roychowdhury's matching upper bound: .The second part of this research note presents several counterintuitive findings about the membership of arithmetic functions in the circuit classes and . For example, we construct a function f(Z) such that but . We obtain similar findings for . This apparent brittleness of and highlights a difficulty in proving lower bounds for arithmetic functions.