On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity
Peter Bürgisser · 2006
Let τ(n) denote the minimum number of arithmetic operations sufficient to build the integer n from the constant 1. We prove that if there are arithmetic circuits for computing the permanent of n by n matrices having size polynomial in n, then τ(n!) is polynomially bounded in logn. Under the same assumption on the permanent, we conclude that the Pochhammer-Wilkinson polynomials ∏n k=1 (X−k) and the Taylor approximations ∑n k=0