# arithmetic circuits for polynomials (updated)

I am concerned about the following question, consider $P_n(x)= \sum_{i=0}^n \frac{x^n}{n!}$

Is there a straight line program (or arithmetic circuits) of polynomial size (wrt $n$) for the polynomial $P_{2^n}(x)$? The difficulty seems to lie in the factorial, as for example the polynomial $x^{2^n}$ has a polynomial size arithmetic circuit (by repeated squaring).

Sorry in my previous post I did not make the question clear, as it would become a very simple question.

• 1) You might want to specify "constant-free straight line program," since otherwise a standard assumption is that constants are free. 2) What is your motivation? I could see this being a homework question, though I could also see this being a non-homework question. Feb 10, 2014 at 15:21
• yes, it is constant-free. Thanks for comments. Feb 10, 2014 at 15:24
• To make the question even clearer you could just define $P_n(x) = \sum_{i=0}^{2^n} x^i/i!$ in the first place, and point out that the summation goes all the way up to $2^n$. Feb 10, 2014 at 15:35
• @JoshuaGrochow The coefficients of the polynomial are not integers, therefore I do not know what it means for a circuit computing $P_n$ to be constant-free. Usually, constant-free circuits have no division... Of course it is not possible here to be constant-free and division-free! Feb 11, 2014 at 7:03
• Where in the world is this homework? ;-) Feb 11, 2014 at 9:47

I assume that you mean $P_n(x)= \sum_{i=0}^n \frac{x^i}{i!}$.