<p>Replacing <span class="math-container">$P(X_1, \ldots, X_n)$</span> by <span class="math-container">$Q(X_1, \ldots, X_n) := P(X_1 + a_1, \ldots, X_n+a_n)$</span>, we can assume that <span class="math-container">$a = (0,\ldots,0)$</span>. The <span class="math-container">$t$</span>-th truncation of <span class="math-container">$Q(X_1,\ldots,X_n)$</span> about <span class="math-container">$0$</span> is the sum of the homogeneous components of <span class="math-container">$Q$</span> of degree strictly less than <span class="math-container">$t$</span>. It is a well-known result (see, e.g., Theorem 2.2 in Shpilka &amp; Yehudayoff) that if <span class="math-container">$Q$</span> has a circuit of size <span class="math-container">$s$</span>, then the homogeneous components of <span class="math-container">$Q$</span> up to degree <span class="math-container">$t$</span> can be computed by a circuit of size <span class="math-container">$O(s t^2)$</span>.</p>
<p>Since the shift to go from <span class="math-container">$P$</span> to <span class="math-container">$Q$</span> at most doubles the size of the circuit for <span class="math-container">$P$</span>, if <span class="math-container">$P$</span> has a circuit of size <span class="math-container">$s$</span>, then by shifting and homogenizing, you get a circuit of size <span class="math-container">$O(s t^2)$</span> for the <span class="math-container">$t$</span>-th truncation about <span class="math-container">$a$</span>. This argument works over any field <span class="math-container">$\mathbb{F}$</span>.</p>
<p><em>Shpilka, Amir; Yehudayoff, Amir</em>, <a href="https://doi.org/10.1561/0400000039" rel="noreferrer"><strong>Arithmetic circuits: a survey of recent results and open questions</strong></a>, Found. Trends Theor. Comput. Sci. 5, No. 3-4, 207-388 (2009). <a href="https://zbmath.org/?q=an:1205.68175" rel="noreferrer">ZBL1205.68175</a>.</p>

CC BY-SA 4.0
2024-11-04T16:53:35.217Z
2024-11-04T16:53:35.217Z
Robert Andrews
<p>For any multivariate polynomial <span class="math-container">$P(\mathbb{X})\in\mathbb{F}[\mathbb{X}]$</span>, with <span class="math-container">$\mathbb{X}=(X_1,\ldots,X_n)$</span>, and any <span class="math-container">$a\in\mathbb{F}^n$</span>, define the <span class="math-container">$t$</span>-th truncation about <span class="math-container">$a$</span> to be the unique reduced polynomial</p>
<p><span class="math-container">$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).$</span></p>
<p>Here, <span class="math-container">$\big(\prod_{i=1}^n(X_i-a_i)^{e_i}:e_1+\cdots+e_n=t\big)$</span> denotes the ideal generated by all polynomials <span class="math-container">$\prod_{i=1}^n(X_i-a_i)^{e_i}$</span> as we vary over all tuples <span class="math-container">$(e_1,\ldots,e_n)$</span> satisfying <span class="math-container">$e_1+\cdots+e_n=t$</span>.</p>
<p>Is there any result in the literature towards showing that if a polynomial <span class="math-container">$P(\mathbb{X})$</span> has a small circuit, then for any <span class="math-container">$a,t$</span>, the truncation <span class="math-container">$P_{a,t}(\mathbb{X})$</span> has a small circuit?  I am taking <span class="math-container">$\mathbb{F}$</span> to be an arbitrary field, but we could assume it is either <span class="math-container">$\mathbb{C}$</span> or anything algebraically closed, or any function field.</p>

CC BY-SA 4.0
2024-11-06T06:39:42.010Z
I don't understand what the notation $( \cdots : \cdots )$ represents.  Is it a product?  Something else?  Can you explain it?
D.W.
CC BY-SA 4.0
2024-11-08T13:10:05.477Z
It is simply the ideal generated by a set of polynomials.  the braces denote the ideal, and the colon is as in the set notation.  So here, I refer to the ideal generated by all polynomials $\prod_{i=1}^n(X_i-a_i)^{e_i}$ as we vary over tuples $(e_1,\ldots,e_n)$ satisfying $e_1+\cdots+e_n=t$.
The Discrete Guy
CC BY-SA 4.0
2024-11-08T20:49:16.117Z
Thank you!  Can I encourage you to [edit] the question to define that notation, so people don't have to read the comments to understand what is being asked?
D.W.
<arithmetic-circuits>
Arithmetic circuit complexity of Taylor approximation
The Discrete Guy
# Arithmetic circuit complexity of Taylor approximation

(Asked by: username_0 on 2024-11-04)

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.

**Tags:** arithmetic-circuits

> **Comments:**
> **username_1**: I don't understand what the notation $( \cdots : \cdots )$ represents.  Is it a product?  Something else?  Can you explain it?  
> **username_0**: It is simply the ideal generated by a set of polynomials.  the braces denote the ideal, and the colon is as in the set notation.  So here, I refer to the ideal generated by all polynomials $\prod_{i=1}^n(X_i-a_i)^{e_i}$ as we vary over tuples $(e_1,\ldots,e_n)$ satisfying $e_1+\cdots+e_n=t$.  
> **username_1**: Thank you!  Can I encourage you to [edit] the question to define that notation, so people don't have to read the comments to understand what is being asked?  

---

## 1 answers

### Answer by username_2 on 2024-11-04. Score: 7 | Accepted answer

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**](https://doi.org/10.1561/0400000039), Found. Trends Theor. Comput. Sci. 5, No. 3-4, 207-388 (2009). [ZBL1205.68175](https://zbmath.org/?q=an:1205.68175).


---

