So I was wondering whether you could always have a multivariate polynomial $P$ over $\mathbb{Z}$ that ...
- can be represented by arithmetic circuits of size $s$
- has polynomial degree and exponentially bounded coefficients (so $P$ is computable in polynomial time on some input)
- which is not computable by circuits of size $s-1$?
- is not a constant
for any $s$.
I do not need to be able to find such polynomials quickly, I guess this would be very hard task. Actually, I would just like to know if these exist.