__
TR06-113 | 25th August 2006 00:00
__

#### On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity

**Abstract:**
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 for computing the permanent of $n$ by $n$ matrices having size polynomial in $n$, then $\tau(n!)$ is polynomially bounded in $\log n$. Under the same assumption on the permanent, we conclude that the Pochhammer-Wilkinson polynomials

$\prod_{k=1}^n (X-k)$ and the Taylor approximations $\sum_{k=0}^n \frac1{k!} X^k$ and $\sum_{k=1}^n \frac1{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.