Arithmetic circuit complexity of Taylor approximation

Question

For any multivariate polynomial $P(\mathbb{X})\in\mathbb{F}[\mathbb{X}]$, with $\mathbb{X}=(X_1,\ldots,X_n)$, and any $a\in\mathbb{F}^n$, define the $t$-th truncation about $a$ to be the unique reduced polynomial

$P_{a,t}(\mathbb{X})=P(\mathbb{X})\mod\big(\prod_{i=1}^n(X_i-a_i)^{e_i}:e_1+\cdots+e_n=t\big).$

Here, $\big(\prod_{i=1}^n(X_i-a_i)^{e_i}:e_1+\cdots+e_n=t\big)$ denotes the ideal generated by all polynomials $\prod_{i=1}^n(X_i-a_i)^{e_i}$ as we vary over all tuples $(e_1,\ldots,e_n)$ satisfying $e_1+\cdots+e_n=t$.

Is there any result in the literature towards showing that if a polynomial $P(\mathbb{X})$ has a small circuit, then for any $a,t$, the truncation $P_{a,t}(\mathbb{X})$ has a small circuit? I am taking $\mathbb{F}$ to be an arbitrary field, but we could assume it is either $\mathbb{C}$ or anything algebraically closed, or any function field.

Answer 1

Replacing $P(X_1, \ldots, X_n)$ by $Q(X_1, \ldots, X_n) := P(X_1 + a_1, \ldots, X_n+a_n)$, we can assume that $a = (0,\ldots,0)$. The $t$-th truncation of $Q(X_1,\ldots,X_n)$ about $0$ is the sum of the homogeneous components of $Q$ of degree strictly less than $t$. It is a well-known result (see, e.g., Theorem 2.2 in Shpilka & Yehudayoff) that if $Q$ has a circuit of size $s$, then the homogeneous components of $Q$ up to degree $t$ can be computed by a circuit of size $O(s t^2)$.

Since the shift to go from $P$ to $Q$ at most doubles the size of the circuit for $P$, if $P$ has a circuit of size $s$, then by shifting and homogenizing, you get a circuit of size $O(s t^2)$ for the $t$-th truncation about $a$. This argument works over any field $\mathbb{F}$.

Shpilka, Amir; Yehudayoff, Amir, Arithmetic circuits: a survey of recent results and open questions, Found. Trends Theor. Comput. Sci. 5, No. 3-4, 207-388 (2009). ZBL1205.68175.