<p>You do not cite the part of the survey that is actually relevant for getting the <span class="math-container">$s/3$</span> lower bound:</p>
<blockquote>
<p>Starting from the root, walk down to the leaves by always taking the child with a larger sub-tree under it. Consider the first node in this path <span class="math-container">$v$</span> such that the size of the formula rooted at v is smaller than <span class="math-container">$2s/3$</span>.</p>
</blockquote>
<p><span class="math-container">$v$</span> cannot be the root since the subtree rooted at the root has size <span class="math-container">$s$</span>. Let <span class="math-container">$w$</span> be the predecessor of <span class="math-container">$v$</span>. By definition, the subtree rooted at <span class="math-container">$w$</span> contains more than <span class="math-container">$2s/3$</span> nodes. Since it has most two children and <span class="math-container">$v$</span> is the child with the largest subtree under it, it has more than half the nodes under <span class="math-container">$w$</span>, that is, more than <span class="math-container">$s/3$</span>.</p>

CC BY-SA 4.0
2022-11-08T08:53:57.453Z
See also Emil's linked thread since indeed, you may not only have a value precisely between $s/3$ and $2s/3$ but between $\lceil s/3 \rceil$ and $\lceil 2s/3 \rceil$.
holf
CC BY-SA 4.0
2022-11-08T06:47:09.257Z
2022-11-08T06:47:09.257Z
holf
<p>I am reading Depth Reduction of Arithmetic Formula form <a href="https://github.com/dasarpmar/lowerbounds-survey/releases/download/v9.0.3/fancymain.pdf" rel="nofollow noreferrer">the survey of Ramprasad Saptharishi</a>. Now in the proof of depth reduction due to <a href="https://dl.acm.org/doi/pdf/10.1145/321812.321815" rel="nofollow noreferrer">Brent, 74</a> that</p>
<blockquote>
<p>Let <span class="math-container">$f$</span> be an n-variate degree d polynomial computed by an arithmetic formula <span class="math-container">$\Phi$</span> of size s. Then, <span class="math-container">$f$</span> can also be computed by a formula <span class="math-container">$\Phi^{\prime}$</span> of size <span class="math-container">$s^{\prime}=\operatorname{poly}(s, n, d)$</span> and depth <span class="math-container">$O(\log s)$</span></p>
</blockquote>
<p>In the proof they have written that</p>
<blockquote>
<p>Consider the first node in this path <span class="math-container">$V$</span> such that the size of the formula rooted at <span class="math-container">$v$</span> is smaller than <span class="math-container">$\frac{2s}{3}$</span>. Let <span class="math-container">$\Phi_v$</span> refer to the sub-formula rooted at <span class="math-container">$V$</span>. By the choice of the path from the root, we have <span class="math-container">$$\frac{s}3\leq |\Phi_v|\leq \frac{2s}{3}$$</span></p>
</blockquote>
<p>Now how are we getting the <span class="math-container">$\frac{s}3\leq |\Phi_v|$</span> inequality?</p>

CC BY-SA 4.0
2022-11-08T07:03:54.617Z
https://cs.stackexchange.com/questions/133521/for-a-binary-tree-of-n-nodes-there-is-a-subtree-with-n-3-to-2n-3-nodes/133995#133995
Emil Jeřábek
<algebraic-complexity><arithmetic-circuits><circuit-depth><formulas>
In depth reduction of arithmetic formula why we get a $v$ st $\frac{s}3\leq |\Phi_v|\leq \frac{2s}{3}$
Sassy Math
# In depth reduction of arithmetic formula why we get a $v$ st $\frac{s}3\leq |\Phi_v|\leq \frac{2s}{3}$

(Asked by: username_0 on 2022-11-07)

I am reading Depth Reduction of Arithmetic Formula form [the survey of Ramprasad Saptharishi](https://github.com/dasarpmar/lowerbounds-survey/releases/download/v9.0.3/fancymain.pdf). Now in the proof of depth reduction due to [Brent, 74](https://dl.acm.org/doi/pdf/10.1145/321812.321815) that

> Let $f$ be an n-variate degree d polynomial computed by an arithmetic formula $\Phi$ of size s. Then, $f$ can also be computed by a formula $\Phi^{\prime}$ of size $s^{\prime}=\operatorname{poly}(s, n, d)$ and depth $O(\log s)$

In the proof they have written that

> Consider the first node in this path $V$ such that the size of the formula rooted at $v$ is smaller than $\frac{2s}{3}$. Let $\Phi\_v$ refer to the sub-formula rooted at $V$. By the choice of the path from the root, we have $$\frac{s}3\leq |\Phi\_v|\leq \frac{2s}{3}$$

Now how are we getting the $\frac{s}3\leq |\Phi\_v|$ inequality?

**Tags:** algebraic-complexity, arithmetic-circuits, circuit-depth, formulas

> **Comments:**
> **username_1**: https://cs.stackexchange.com/questions/133521/for-a-binary-tree-of-n-nodes-there-is-a-subtree-with-n-3-to-2n-3-nodes/133995#133995  

---

## 1 answers

### Answer by username_2 on 2022-11-08. Score: 3 | Accepted answer

You do not cite the part of the survey that is actually relevant for getting the $s/3$ lower bound:

> Starting from the root, walk down to the leaves by always taking the child with a larger sub-tree under it. Consider the first node in this path $v$ such that the size of the formula rooted at v is smaller than $2s/3$.

$v$ cannot be the root since the subtree rooted at the root has size $s$. Let $w$ be the predecessor of $v$. By definition, the subtree rooted at $w$ contains more than $2s/3$ nodes. Since it has most two children and $v$ is the child with the largest subtree under it, it has more than half the nodes under $w$, that is, more than $s/3$.

> **Comments:**
> **username_2**: See also Emil's linked thread since indeed, you may not only have a value precisely between $s/3$ and $2s/3$ but between $\lceil s/3 \rceil$ and $\lceil 2s/3 \rceil$.  

---

