@article{B-On-Defining-Integers-And-Proving-Arithmetic-Circuit-Lower-Bounds,
Title = {On defining integers and proving arithmetic circuit lower bounds},
Author = {Peter Bürgisser},
Pages = {81-103},
Year = {2009},
Journal = {Computational Complexity},
Volume = {18},
Note = {Preliminary version in Proc. of STACS 2007, 133-144, February 2007, Aachen},
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\times 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.},
Url = {http://www3.math.tu-berlin.de/algebra/work/6dich.pdf},
Url2 = {http://link.springer.com/article/10.1007/s00037-009-0260-x}
}