ON DEFINING INTEGERS AND PROVING ARITHMETIC CIRCUIT LOWER BOUNDS
Let tau (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 of size polynomial in n for computing the permanent of n by n matrices, then tau (n!) is polynomially bounded in log n. Under the same assumption on the permanent, we conclude that the Pochhammer-Wilkinson polynomials Pi(n)(k=1) (X - k) and the Taylor approximations Sigma(n)(k= 0) 1/k! X(k) and Sigma(n)(k=1) 1/k X(k) of exp and log, respectively, can be computed by arithmetic circuits of size polynomial in log n (allowing divisions). This connects several so far unrelated conjectures in algebraic complexity.
permanent algebraic complexity factorials integer roots of univariate polynomials