Conference version appeared in the proceedings of FOCS 2013.

[15]
Ankit Garg, Neeraj Kayal, and Chandan Saha.
Learning sums of powers of low-degree polynomials in the
non-degenerate case.
In Sandy Irani, editor, 61st IEEE Annual Symposium on
Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November
16-19, 2020, pages 889–899. IEEE, 2020.

[16]
Fulvio Gesmundo and Joseph M. Landsberg.
Explicit polynomial sequences with maximal spaces of partial
derivatives and a question of k. mulmuley.
Theory Comput., 15:1–24, 2019.

[17]
Nikhil Gupta, Chandan Saha, and Bhargav Thankey.
A super-quadratic lower bound for depth four arithmetic circuits.
In Shubhangi Saraf, editor, 35th Computational Complexity
Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual
Conference), volume 169 of LIPIcs, pages 23:1–23:31. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2020.

[18]
Pavel Hrubes and Amir Yehudayoff.
Homogeneous formulas and symmetric polynomials.
Comput. Complex., 20(3):559–578, 2011.

[19]
K. Kalorkoti.
A Lower Bound for the Formula Size of Rational Functions.
SIAM J. Comput., 14(3):678–687, 1985.

[20]
Neeraj Kayal.
An exponential lower bound for the sum of powers of bounded degree
Electronic Colloquium on Computational Complexity (ECCC),
19:81, 2012.

[21]
Neeraj Kayal, Nutan Limaye, Chandan Saha, and Srikanth Srinivasan.
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic
SIAM J. Comput., 46(1):307–335, 2017.
Conference version appeared in the proceedings of FOCS 2014.

[22]
Neeraj Kayal, Vineet Nair, and Chandan Saha.
Separation Between Read-once Oblivious Algebraic Branching Programs
(ROABPs) and Multilinear Depth-three Circuits.
ACM Trans. Comput. Theory, 12(1):2:1–2:27, 2020.
Conference version appeared in the proceedings of STACS 2016.

[23]
Pascal Koiran.
Arithmetic circuits: The chasm at depth four gets wider.
Theor. Comput. Sci., 448:56–65, 2012.

[24]
Mrinal Kumar and Shubhangi Saraf.
The limits of depth reduction for arithmetic formulas: it's all about
the top fan-in.
In Symposium on Theory of Computing, STOC 2014, New York, NY,
USA, May 31 - June 03, 2014, pages 136–145, 2014.

[25]
Mrinal Kumar and Shubhangi Saraf.
Superpolynomial lower bounds for general homogeneous depth 4
arithmetic circuits.
In Automata, Languages, and Programming - 41st International
Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings,
Part I, pages 751–762, 2014.

[26]
Neeraj Kayal and Chandan Saha.
Lower Bounds for Depth-Three Arithmetic Circuits with small bottom
Computational Complexity, 25(2):419–454, 2016.
Conference version appeared in the proceedings of CCC 2015.

[27]
Neeraj Kayal and Chandan Saha.
Multi-k-ic depth three circuit lower bound.
Theory Comput. Syst., 61(4):1237–1251, 2017.
The conference version appeared in the proceedings of STACS, 2015.

[28]
Mrinal Kumar and Shubhangi Saraf.
On the Power of Homogeneous Depth 4 Arithmetic Circuits.
SIAM J. Comput., 46(1):336–387, 2017.
Conference version appeared in the proceedings of FOCS 2014.

[29]
Neeraj Kayal and Chandan Saha.
Reconstruction of non-degenerate homogeneous depth three circuits.
In Moses Charikar and Edith Cohen, editors, Proceedings of the
51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019,
Phoenix, AZ, USA, June 23-26, 2019, pages 413–424. ACM, 2019.

[30]
Mrinal Kumar and Ramprasad Saptharishi.
The computational power of depth five arithmetic circuits.
SIAM J. Comput., 48(1):144–180, 2019.

[31]
Deepanshu Kush and Shubhangi Saraf.
Improved low-depth set-multilinear circuit lower bounds.
In Shachar Lovett, editor, 37th Computational Complexity
Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA, volume
234 of LIPIcs, pages 38:1–38:16. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2022.

[32]
Neeraj Kayal, Chandan Saha, and Ramprasad Saptharishi.
A super-polynomial lower bound for regular arithmetic formulas.
In Symposium on Theory of Computing, STOC 2014, New York, NY,
USA, May 31 - June 03, 2014, pages 146–153, 2014.

[33]
Neeraj Kayal, Chandan Saha, and Sébastien Tavenas.
An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits.
In 43rd International Colloquium on Automata, Languages, and
Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 33:1–33:15,

[34]
Neeraj Kayal, Chandan Saha, and Sébastien Tavenas.
On the size of homogeneous and of depth four formulas with low
individual degree.
In Proceedings of the 48th Annual ACM SIGACT Symposium on
Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016,
pages 626–632, 2016.

[35]
Guillaume Lagarde, Nutan Limaye, and Srikanth Srinivasan.
Lower Bounds and PIT for Non-commutative Arithmetic Circuits with
Restricted Parse Trees.
Computational Complexity, 28(3):471–542, 2019.

[36]
Guillaume Lagarde, Guillaume Malod, and Sylvain Perifel.
Non-commutative computations: lower bounds and polynomial identity
Chicago Journal of Theoretical Computer Science, (2):1–19,

[37]
Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas.
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits.
In 62nd IEEE Annual Symposium on Foundations of Computer
Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 804–814.
IEEE, 2021.
A full version of the paper can be found at

[38]
Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas.
On the partial derivative method applied to lopsided set-multilinear
In Shachar Lovett, editor, 37th Computational Complexity
Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA, volume
234 of LIPIcs, pages 32:1–32:23. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2022.

[39]
Noam Nisan.
Lower Bounds for Non-Commutative Computation (Extended Abstract).
In Cris Koutsougeras and Jeffrey Scott Vitter, editors, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May
5-8, 1991, New Orleans, Louisiana, USA, pages 410–418. ACM, 1991.

[40]
Noam Nisan and Avi Wigderson.
Lower Bounds on Arithmetic Circuits Via Partial Derivatives.
Computational Complexity, 6(3):217–234, 1997.
Conference version appeared in the proceedings of FOCS 1995.

[41]
Ran Raz.
On the Complexity of Matrix Product.
SIAM J. Comput., 32(5):1356–1369, 2003.
Conference version appeared in the proceedings of STOC 2002.

[42]
Ran Raz.
Separation of Multilinear Circuit and Formula Size.
Theory of Computing, 2(6):121–135, 2006.
Conference version appeared in the proceedings of FOCS 2004.

[43]
Ran Raz.
Elusive Functions and Lower Bounds for Arithmetic Circuits.
Theory of Computing, 6(1):135–177, 2010.
Conference version appeared in the proceedings of STOC 2008.

[44]
Ran Raz.
Tensor-Rank and Lower Bounds for Arithmetic Formulas.
J. ACM, 60(6):40:1–40:15, 2013.
Conference version appeared in the proceedings of STOC 2010.

[45]
Bruce Reznick.
Sums of even powers of real linear forms.
Memoirs of the AMS, 96:463, 1992.

[46]
Ran Raz, Amir Shpilka, and Amir Yehudayoff.
A Lower Bound for the Size of Syntactically Multilinear Arithmetic
SIAM J. Comput., 38(4):1624–1647, 2008.
Conference version appeared in the proceedings of FOCS 2007.

[47]
Ran Raz and Amir Yehudayoff.
Balancing Syntactically Multilinear Arithmetic Circuits.
Computational Complexity, 17(4):515–535, 2008.

[48]
Ran Raz and Amir Yehudayoff.
Lower Bounds and Separations for Constant Depth Multilinear
Computational Complexity, 18(2):171–207, 2009.
Conference version appeared in the proceedings of CCC 2008.

[49]
Victor Shoup and Roman Smolensky.
Lower Bounds for Polynomial Evaluation and Interpolation Problems.
Computational Complexity, 6(4):301–311, 1997.
Conference version appeared in the proceedings of FOCS 1991.

[50]
Volker Strassen.
Die berechnungskomplexiät von elementarysymmetrischen funktionen
und von iterpolationskoeffizienten.
Numerische Mathematik, 20:238–251, 1973.

[51]
Volker Strassen.
Vermeidung von divisionen.
The Journal für die Reine und Angewandte Mathematik,
264:182–202, 1973.

[52]
Amir Shpilka and Avi Wigderson.
Depth-3 arithmetic circuits over fields of characteristic zero.
Computational Complexity, 10(1):1–27, 2001.
Conference version appeared in the proceedings of CCC 1999.

[53]
Sébastien Tavenas.
Improved bounds for reduction to depth 4 and depth 3.
Inf. Comput., 240:2–11, 2015.
Conference version appeared in the proceedings of MFCS 2013.

[54]
Sébastien Tavenas, Nutan Limaye, and Srikanth Srinivasan.
Set-multilinear and non-commutative formula lower bounds for iterated
matrix multiplication.
In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th
Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20
- 24, 2022, pages 416–425. ACM, 2022.

[55]
Leslie G. Valiant.
Completeness Classes in Algebra.
In Proceedings of the 11h Annual ACM Symposium on Theory of
Computing, April 30 - May 2, 1979, Atlanta, Georgia, USA, pages 249–261,

[56]
Ilya Volkovich.
A Guide to Learning Arithmetic Circuits.
In Proceedings of the 29th Conference on Learning Theory, COLT
2016, New York, USA, June 23-26, 2016, pages 1540–1561, 2016.

[57]
Leslie G. Valiant, Sven Skyum, S. Berkowitz, and Charles Rackoff.
Fast Parallel Computation of Polynomials Using Few Processors.
SIAM J. Comput., 12(4):641–644, 1983.

[58]
Morris Yau.
Almost cubic bound for depth three circuits in VP.
Electronic Colloquium on Computational Complexity (ECCC),
23:187, 2016.

§ PROOFS FROM SECTION <REF>

§.§ Proof of Lemma <ref>

\begin{align*}
M(a,b) = \frac{(a+b-1)\cdots(a)}{b!} \ge \frac{a^b}{b^b} \text{~, and}
\end{align*}

\begin{align*}
M(a,b) & \le \frac{(a+b-1)^b}{\paren{\frac{b}{e}}^b} \tag{using $b! \ge \paren{b/e}^b$}\\
& \le \frac{(2a)^b\!\cdot\!e^b}{b^b} \le \paren{\frac{6a}{b}}^b.
\end{align*}

\begin{align*}
\frac{M(a,b+c)}{M(a,b)} = \paren{\frac{a+b+c-1}{b+c}}\cdots\paren{\frac{a+b}{b+1}}.
\end{align*}

The bounds follow from the fact that each of the above $c$ many fractions lies between $\frac{a}{2b}$ and $\frac{2a}{b}$.

\begin{align*}
\frac{M(c,d)}{M(b,d)} = \paren{\frac{c+d-1}{b+d-1}}\cdots\paren{\frac{c}{b}}.
\end{align*}

The lower bound follows from the fact that each of the above $d$ many fractions is at least $\frac{c}{b}$.

Canonical tree of a binary tree

[1]
$\cT$ is an empty tree $\cT$.
$v \gets \textnormal{root node of $\cT$}$.
If $v$ has no left (or right) child, $v_L$ (resp. $v_R$) defined below is treated as an empty node and the corresponding subtree is considered empty.
$v_{L} \gets \textnormal{left child of } v$.
$v_{R} \gets \textnormal{right child of } v$.
Recursively “canonizing” the left and right subtrees.
$\cT_{v_L} \gets \canon(\cT_{v_L})$.
$\cT_{v_R} \gets \canon(\cT_{v_R})$.
encoding is any fixed 1-1 map from binary trees to positive integers.
$\leaves(v_L)  > \leaves(v_R)$ or ($\leaves(v_L) = \leaves(v_R)$ and $\encoding(\cT_{v_L}) > \encoding(\cT_{v_R})$)
The left and right subtrees at the root are swapped.

§.§ Proof of Proposition <ref>

The lemma is trivially true for empty trees, so we will assume that $\cT$ has at least one leaf.

* In Algorithm <ref>, we swap the left and right subtrees of a node when the left-subtree has more leaves than the right-subtree and do not swap if the right-subtree has more nodes than the left-subtree. Because of this, it follows from a simple inductive argument that $\canon(\cT)$ is right-heavy and is isomorphic to $\cT$.

* Suppose $\canon(\cT) = \canon(\widetilde{\cT})$. Using Item 1, we get that $\cT$ and $\widetilde{\cT}$ are isomorphic as both of them are isomorphic to $\canon(\cT)$. Conversely, suppose that $\cT$ is isomorphic to $\widetilde{\cT}$ via a bijection $\phi$. We shall use induction on the number of leaves of $\cT$ and $\widetilde{\cT}$; if both of them have just one leaf, then we trivially have that $\canon(\cT) = \canon(\widetilde{\cT})$.  Denoting the left and right children of the root $v$ of $\cT$ by $v_L$ and $v_R$, we get that $\cT_{v_L}$ and $\widetilde{\cT}_{\phi(v_L)}$ are isomorphic under $\phi$ and so are $\cT_{v_R}$ and $\widetilde{\cT}_{\phi(v_R)}$. As these trees have fewer leaves than $\cT$ and $\widetilde{\cT}$, we have $\canon(\cT_{v_L}) = \canon(\widetilde{\cT}_{\phi(v_L)})$ and $\canon(\cT_{v_R}) = \canon(\widetilde{\cT}_{\phi(v_R)})$ by induction. Hence, after line <ref> in the execution of Algorithm <ref> on inputs $\cT$ and $\widetilde{\cT}$, either $\canon(\cT_{v_L})$ and $\canon(\widetilde{\cT}_{\phi(v_L)})$ are both the left child of $v$ and $\phi(v)$ respectively, or both are the right child. The same is true for $\canon(\cT_{v_R})$ and $\canon(\widetilde{\cT}_{\phi(v_R)})$. Thus $\canon(\cT) = \canon(\widetilde{\cT})$.

* Note that $\phi$ also induces an isomorphism from $\cT_v$ to $\canon(\cT)_{\phi(v)}$. Hence from Item 2, $\canon(\cT_v) = \canon(\canon(\cT)_{\phi(v)})$. By our design of the function (), note that all subtrees of a canonical tree are themselves canonical trees i.e., there exists a binary tree $\cT'$ such that $\canon(\cT') = \canon(\cT)_{\phi(v)}$. Thus, $\canon(\cT_v) = \canon(\canon(\cT)_{\phi(v)})=\canon(\canon(\cT'))=\canon(\cT')=\canon(\cT)_{\phi(v)}$.

§.§ $\APP$ vs skewed partials

In this section, we show that there are some lower bounds that can be proved using $\APP$ but not with the skewed partials measure ($\SkewP$). Consider circuits of the form $C = Q_1^{e_1} + \cdots + Q_s^{e_s}$, where $Q_1, \ldots, Q_{s}$ are arbitrary polynomials of degree at most $d \leq \frac{n}{2e}$. How large an $s$ do we need for $C$ to compute the monomial $P := x_1\cdots x_n$? [20] introduced the $\SP$ measure to show that $s = 2^{\Omega\paren{\frac{n}{d}}}$. Here, we prove the same using the $\APP$ measure. However, this lower bound cannot be proved using $\SkewP$.
Let $\F$ be a field of size greater than $n$. [This restriction on $\F$ is not required. If $|\F| < n$, we take any extension $\K$ of size more than $n$, consider $C$ and $P$ over $\K$, and prove the lower bound on $s$. Observe that the bound will continue to hold over $\F$.]

Analysing $\SkewP(P)$. The $\SkewP$ measure is defined in [22]. If $\vecx = \vecy \uplus \vecz$, then
$$\SkewP_{\vecy,k}(P) := \dim\spacespanned{\brac{\der{P}{m}}_{\vecy = 0}: m \text{ is a monomial of degree } k \text{ in } \vecy}.$$
Observe that $\SkewP_{\vecy, k}(P) \leq 1$ for all $\vecy \subseteq \vecx$ and $k$. Hence, we cannot hope to get a lower bound on $s$ using skewed partials.

Analysing $\APP$ of $C$ and $P$.  Let $k = \floor{\frac{n}{2ed}}$ and $n_0 = k+1$. We begin by proving an upper bound on $\APP_{n_0,k}(C)$.

$\APP_{n_0,k}(C) \leq s\cdot \binom{n_0 + dk - k}{n_0}$.

Observe that for all $i \in [s]$,

$$\partialf^k\paren{Q_i^{e_i}} \subseteq \set{\vecx^{\leq d(k - 1)}Q_i^{\max\set{e_i - k,0}}}.\footnote{Here $\vecx^{\leq d(k-1)}$ denotes the set of all monomials of degree at most $d(k-1)$.}$$

Thus, $\APP_{k, n_0}\paren{Q_i^{e_i}} \leq \binom{n_0 + dk - k}{n_0}$. The claim follows from the sub-additivity of $\APP$.

We now compute  $\APP_{k,n_0}(P)$.

$\APP_{k,n_0}(P) = \binom{n}{k}$.

Fix distinct $\alpha_1, \ldots, \alpha_n \in \F$ and let $\vecz = \set{z_1, \ldots, z_{n_0}}$ be a fresh set of variables. Let $L$ map $x_i$ to $\ell_i(\vecz) := z_1 + \alpha_i\cdot z_2 + \alpha_i^2 \cdot z_3 + \cdots + \alpha_i^{n_0 - 1}z_{n_0}$ for all $i \in [n]$. Observe that any $n_0 = k+1$ many linear forms in $\set{\ell_1, \ldots, \ell_{n}}$ are linearly independent. Now,

$$\partialf^k(P) = \set{\prod_{i \in S}x_i : S \subseteq [n], |S| = n-k}.$$

We now argue that the polynomials of the set $\pi_{L}\paren{\partialf^k (P)} = \set{\pi_L(\prod_{i \in S}x_i): S \subseteq [n], |S| = n-k} = \set{\prod_{i \in S}\ell_i: S \subseteq [n], |S| = n-k}$ are linearly independent; this would prove the claim.

Consider any $\F$-linear combination

$$\sum_{|S| = n-k} \beta_S \cdot \prod_{i \in S}\ell_i = 0$$
and fix an arbitrary $S'$ of size $n-k$. Observe that for every $S \neq S'$, at least one of the linear forms $\set{\ell_j : j \notin S'}$ divides $\prod_{i \in S}\ell_i$. Thus, if $I$ is the ideal generated by $\set{\ell_j : j \notin S'}$, then

$$\beta_{S'}\prod_{i \in S'}\ell_i = 0 \mod I.$$
Since $I$ is an ideal generated by  linear forms, $\F[\vecz]/I$ is a polynomial ring. This implies that $\beta_{S'} = 0$ or $\prod_{i \in S'}\ell_i = 0 \mod I$. The latter is not true: It implies that there exists an $i \in S'$ such that $\ell_i = 0 \mod I$, i.e., $\ell_i$ is an $\F$-linear combination of $\set{\ell_j : j \notin S'}$. However, as $|[n] \setminus S'| = k$, this contradicts the fact that every $k+1$ linear forms in $\set{\ell_1, \ldots, \ell_n}$ are linearly independent. Thus, $\beta_{S'} = 0$.  Repeating this argument for all $S' \subset [n]$ such that $|S'| = n-k$, we get that the elements of $\set{\prod_{i \in S}\ell_i: S \subseteq [n], |S| = n-k}$ are linearly independent.

From the above two claims, and using $k = \floor{\frac{n}{2ed}}$, $n_0 = k+1$, we get,

$$s \geq \frac{\binom{n}{k}}{\binom{n_0 + dk - k}{n_0}} \geq  \frac{\paren{\frac{n}{k}}^k}{\paren{\frac{e(n_0 + kd-k))}{n_0}}^{n_0}} \geq \frac{\paren{\frac{n}{k}}^k}{\paren{\frac{e(kd + 1)}{k+1}}^{k+1}} \geq \frac{\paren{\frac{n}{k}}^k}{n^{O(1)}\paren{\frac{n/2}{n/2ed}}^{k}} \geq \frac{1}{n^{O(1)}}\paren{\frac{n}{ked}}^k \geq \frac{2^k}{n^{O(1)}} \geq 2^{\Omega\paren{\frac{n}{d}}}.$$

§ PROOFS FROM SECTION <REF>

§.§ Proof of Claim <ref>

∂_μ([k]) ∏_i∈[t] Q_i
= ∑_κ:[t]→2^[k] s.t.
⊔_i ∈[t] κ_i = [k] ∏_i ∈[t] ∂_μ(κ_i) Q_i

= ∑_S ⊆[t] ∑_κ:[t]→2^[k] s.t.
⊔_i ∈[t] κ_i = [k]
i ∈[t]: |κ_i| ≤k/d.d_i = S ∏_i ∈[t] ∂_μ(κ_i) Q_i

= ∑_S ⊆[t] ∑_κ:S→2^[k] s.t.
∀i ∈S, |κ_i|>k/d.d_i  ∑_κ' : S →2^[k]  s.t.
κ= κ' ⊔κ
⊔_i ∈[t] κ_i = [k]
∀i ∈S, |κ'_i| ≤k/d.d_i ∏_i ∈[t] ∂_μ(κ_i) Q_i

= ∑_S ⊆[t] ∑_κ:S→2^[k] s.t.
∀i ∈S, |κ_i|>k/d.d_i  ∑_κ: [t] →2^[k]  s.t.
κ extends  κ
⊔_i ∈[t] κ_i = [k]
∀i ∈S, |κ_i| ≤k/d.d_i ∏_i ∈[t] ∂_μ(κ_i) Q_i

= ∑_S ⊆[t] ∑_κ:S→2^[k] s.t.
∀i ∈S, |κ_i|>k/d.d_i R_S,κ.          (by the definition of $R_{S,\widetilde{\kappa}}$ in (<ref>))

§.§ Proof of Claim <ref>

U_S,κ    = ∂_μ(P_S) ∏_i ∈SQ_i ·∏_i ∈S ∂_μ(κ_i) Q_i

= ∑_κ':S →2^P_S s.t.
⊔_i ∈S κ'_i = P_S ∏_i ∈S ∂_μ(κ'_i) Q_i·∏_i ∈S ∂_μ(κ_i) Q_i

= ∑_T ⊆S  ∑_κ':S →2^P_S s.t.
⊔_i ∈S κ'_i = P_S
i ∈S : |κ'_i| ≤k/d.d_i = T∏_i ∈S ∂_μ(κ'_i) Q_i·∏_i ∈S ∂_μ(κ_i) Q_i        (reordering the summation based on $T$)

= ∑_T ⊆S  ∑_κ”:S ∖T →2^P_S  and  κ”':T →2^P_S s.t.
κ' = κ” ⊔κ”'
⊔_i ∈S κ'_i = P_S
∀i ∈S ∖T, |κ”_i| > k/d ·d_i
∀i∈T, |κ”'_i| ≤k/d·d_i
∏_i ∈S ∂_μ(κ'_i) Q_i·∏_i ∈S ∂_μ(κ_i) Q_i

= ∑_T ⊆S  ∑_κ”:S∖T →2^P_S  s.t.
∀i ∈S ∖T, |κ”_i| > k/d·d_i  ∑_κ”':T →2^P_S  s.t.
κ^* = κ” ⊔κ”' ⊔κ
∀i ∈T, |κ^*_i| ≤k/d·d_i
⊔_i ∈T κ”'_i ⊔⊔_i ∈S ∖T κ”_i = P_S ∏_i ∈[t] ∂_μ(κ^*_i) Q_i

(as $\kappa^*$ extends $\kappa'=\kappa'' \sqcup \kappa'''$ and $\kappa$ extends $\widetilde{\kappa}$ )

= ∑_T ⊆S  ∑_κ”:S∖T →2^P_S  s.t.
∀i ∈S ∖T, |κ”_i| > k/d·d_i  ∑_κ^*:[t] →2^[k]  s.t.
κ^* = κ” ⊔κ”' ⊔κ
∀i ∈T, |κ^*_i| ≤k/d·d_i
⊔_i ∈[t] κ^*_i = [k] ∏_i ∈[t] ∂_μ(κ^*_i) Q_i

(because $\sqcup_{i \in [t]} \kappa^*_i = \paren{\sqcup_{i \in S\setminus T} \kappa''_i \sqcup \sqcup_{i \in T} \kappa'''_i} \sqcup \sqcup_{i \in \overline{S} } \widetilde{\kappa}_i = P_S \sqcup \sqcup_{i \in \overline{S}} \kappa_i = \sqcup_{i \in [t]} \kappa_i = [k]$ from (<ref>))

= ∑_T ⊆S  ∑_κ”:S∖T →2^P_S  s.t.
∀i ∈S ∖T, |κ”_i| > k/d·d_i R_T,κ” ⊔κ
($R_{T,\kappa'' \sqcup \widetilde{\kappa}}$ is well-defined because $\kappa^*$ extends $\kappa'' \sqcup \widetilde{\kappa}$ and (<ref>))

= R_S,κ + ∑_T ⊊S  and  κ”:S∖T →2^P_S  s.t.
∀i ∈S ∖T, |κ”_i| > k/d.d_i R_T,κ” ⊔κ.        (separating out the case $T=S$)

§.§ Proof of Lemma <ref> (continued)

\begin{align*}
\APP_{k,n_0}(Q) & = \max \limits_{L : \vecx \to \spacespanned{\vecz}} \dim \spacespanned{\pi_L\paren{\partialf^k(Q_1\cdots Q_t)}}\\
& \le \max \limits_{L : \vecx \to \spacespanned{\vecz}} \dim \spacespanned{\pi_L \paren{\sum \limits_{\substack{S \subseteq [t]; ~k_0, \ell_0 \ge 0 \\ k_0 + \frac{k}{d-k}\cdot \ell_0 \le k - \entropy_k(d_1,\dots,d_t)}} \spacespanned{\vecx^{\ell_0}\cdot \partialf^{k_0}\paren{ \prod \limits_{i \in S} Q_i}}} }  \tag{from Lemma ~\ref{lem:der-structure}} \\
& \le \max \limits_{L : \vecx \to \spacespanned{\vecz}} \dim \spacespanned{ \sum \limits_{\substack{S \subseteq [t]; ~k_0, \ell_0 \ge 0 \\ k_0 + \frac{k}{d-k}\cdot \ell_0 \le k - \entropy_k(d_1,\dots,d_t)}} \spacespanned{\pi_L\paren{\vecx^{\ell_0}\cdot \partialf^{k_0}\paren{ \prod \limits_{i \in S} Q_i}}} } \tag{as $\pi_L$ distributes over addition} \\
& \le \max \limits_{L : \vecx \to \spacespanned{\vecz}} \sum \limits_{\substack{S \subseteq [t]; ~k_0, \ell_0 \ge 0 \\ k_0 + \frac{k}{d-k}\cdot \ell_0 \le k - \entropy_k(d_1,\dots,d_t)}} \dim  \spacespanned{\pi_L\paren{\vecx^{\ell_0}}\cdot\pi_L\paren{\partialf^{k_0}\paren{ \prod \limits_{i \in S} Q_i}}} \tag{using Proposition~\ref{prop:sub} (Item 4) and $\pi_L$ distributes over multiplication}\\
& \le \max \limits_{L : \vecx \to \spacespanned{\vecz}} \sum \limits_{\substack{S \subseteq [t]; ~k_0, \ell_0 \ge 0 \\ k_0 + \frac{k}{d-k}\cdot \ell_0 \le k - \entropy_k(d_1,\dots,d_t)}} \dim  \spacespanned{\pi_L\paren{\vecx^{\ell_0}}}\cdot \dim \spacespanned{\pi_L\paren{\partialf^{k_0}\paren{ \prod \limits_{i \in S} Q_i}}} \tag{from Proposition~\ref{prop:sub} (Item 5)}\\
& \le \max \limits_{L : \vecx \to \spacespanned{\vecz}} \sum \limits_{\substack{S \subseteq [t]; ~k_0, \ell_0 \ge 0 \\ k_0 + \frac{k}{d-k}\cdot \ell_0 \le k - \entropy_k(d_1,\dots,d_t)}} \abs{\pi_L\paren{\vecx^{\ell_0}}}\cdot \abs{\pi_L\paren{\partialf^{k_0}\paren{ \prod \limits_{i \in S} Q_i}}} \\
& \le \max \limits_{L : \vecx \to \spacespanned{\vecz}} \sum \limits_{\substack{S \subseteq [t]; ~k_0, \ell_0 \ge 0\\ k_0 + \frac{k}{d-k}\cdot \ell_0 \le k - \entropy_k(d_1,\dots,d_t)}} \abs{ \vecz^{\ell_0}}\cdot \abs{ \pi_L\paren{\partialf^{k_0}\paren{ \prod \limits_{i \in S} Q_i}}} \tag{as $L$ is a map from $\vecx$ to $\spacespanned{\vecz}$, $\pi_L(m) \in \vecz^{\ell_0}$ for any monomial $m$ over $\vecx$ of degree $\ell_0$} \\
& \le 2^t\!\cdot\!d^2\!\cdot\!\max \limits_{\substack{k_0, \ell_0 \ge 0 \\ k_0 + \frac{k}{d-k}\cdot \ell_0 \le k - {\entropy_k(d_1,\dots,d_t)}}} M(n_0, \ell_0)\!\cdot\!M(n,k_0).
\end{align*}

§ PROOFS FROM SECTION <REF>

§.§ Proof of Claim <ref>

We prove the claim by analysing the following three sub-cases.

Case (i): $m_j < k_j$. Then, $\eta \ge \abs{k_j - \alpha\!\cdot\!m_j} = k_j - \alpha\!\cdot\! m_j \ge k_j - m_j \ge 1$.

Now, let $\alpha_1:= \sum\limits_{\nu=0}^{\delta}  \frac{(-1)^\nu}{\tau^{2^\nu-1}}$, $\alpha_2:= \frac{(-1)^{\delta+1}}{\tau^{2^{\delta+1}-1}}$ and $\alpha_3 := \sum\limits_{\nu=\delta+2}^{\Delta-1}  \frac{(-1)^\nu}{\tau^{2^\nu-1}}$. Then, let $\alpha_4:= \tau^{2^\delta-1}\!\cdot\! \paren{k_j - m_j\!\cdot\! \alpha_1}$. Noting that $\alpha = \alpha_1 + \alpha_2 + \alpha_3$ we have,

\begin{align*}
\eta = \tau^{2^\delta-1}\!\cdot\! \abs{k_j - \alpha\!\cdot\! m_j} & = \abs{\tau^{2^\delta-1}\!\cdot\! k_j - \tau^{2^{\delta}-1}\!\cdot\! m_j\!\cdot\! (\alpha_1+\alpha_2+\alpha_3)} \tag{as $\alpha = \alpha_1 + \alpha_2 + \alpha_3$ by definition}\\
& \ge \abs{\alpha_4 - \tau^{2^\delta-1}\!\cdot\! m_j\!\cdot\! \frac{(-1)^{\delta+1}}{\tau^{2^{\delta+1}-1}} - \tau^{2^{\delta}-1}\!\cdot\! m_j\!\cdot\! \alpha_3 } \\
& \ge \abs{\alpha_4 - \tau^{2^\delta-1}\!\cdot\! m_j\!\cdot\! \frac{(-1)^{\delta+1}}{\tau^{2^{\delta+1}-1}}} - \abs{\tau^{2^{\delta}-1}\!\cdot\! m_j\!\cdot\! \alpha_3}\\
& \ge \abs{\abs{\alpha_4} - \frac{m_j}{\tau^{2^\delta}}} - \abs{\tau^{2^{\delta}-1}\!\cdot\! m_j\!\cdot\! \alpha_3} \\
& = \abs{\abs{\alpha_4} - \frac{m_j}{\tau^{2^\delta}}} - \abs{\sum\limits_{\nu=\delta+2}^{\Delta-1}\!\cdot\! \frac{(-1)^\nu\!\cdot\! \tau^{2^\delta-1}\!\cdot\! m_j}{\tau^{2^\nu-1}}}\\
& \ge \abs{\abs{\alpha_4} - \frac{m_j}{\tau^{2^\delta}}} - \abs{\frac{\tau^{2^\delta-1}\!\cdot\! m_j}{\tau^{2^{\delta+2}-1}}} \tag{taking only the leading term of the summation}\\
& \ge \abs{\abs{\alpha_4} - \frac{m_j}{\tau^{2^\delta}}} - \abs{\frac{\tau^{2^\delta-1}\!\cdot\! \tau^{2^\delta}}{\tau^{2^{\delta+2}-1}}} \tag{since $m_j \le d_j \approx_2 \tau^{2^{\delta}}$}\\
& \ge \abs{\abs{\alpha_4} - \frac{m_j}{\tau^{2^\delta}}} - \frac{1}{\tau^2} \\
& = \abs{\abs{\alpha_4} - \frac{m_j}{\tau^{2^\delta}}} - o(1).
\end{align*}

Notice that, as $m_j \leq d_j \approx_2 \tau^{2^\delta}$, $\frac{m_j}{\tau^{2^\delta}} \leq 1$.

Case (ii): $k_j \le m_j \le 6\!\cdot\! k_j$. Note that
$$m_j = \frac{6\!\cdot\! m_j + m_j}{7} \le \frac{6\!\cdot\! m_j + 6\!\cdot\! k_j}{7} = \frac{6}{7}\!\cdot\! d_j \le \frac{6}{7}\!\cdot\! \tau^{2^\delta},\text{~and}$$

$$m_j \ge \frac{m_j + k_j}{2} = \frac{d_j}{2} \ge \frac{1}{4}\!\cdot\! \tau^{2^\delta}.$$

Thus $\frac{m_j}{\tau^{2^\delta}} \in \brac{\frac{1}{4}, \frac{6}{7}}$. On the other hand, $\alpha_4= \tau^{2^\delta-1}\!\cdot\! k_j - \tau^{2^\delta-1}\!\cdot\! m_j\!\cdot\! \alpha_1$ is an integer since the denominators of all the terms in $\alpha_1$ divide $\tau^{2^\delta-1}$. Therefore $\frac{m_j}{\tau^{2^\delta}}$ is at least $\min\set{1/4,3/4, 6/7,1/7}=1/7$ distance from any integer, and from $\abs{\alpha_4}$ in particular. That is, $\abs{\abs{\alpha_4} - \frac{m_j}{\tau^{2^\delta}}} \ge 1/7$ and $\eta \ge \abs{\abs{\alpha_4} - \frac{m_j}{\tau^{2^{\delta}}}} - o(1) \ge \Omega(1)$.

Case (iii): $m_j > 6\!\cdot\! k_j$. Then,

\begin{align*}
-k_j + m_j\!\cdot\! \alpha_1
& = -k_j + m_j\!\cdot\! \paren{\sum\limits_{\nu=0}^\delta \frac{(-1)^\nu}{\tau^{2^\nu-1}}}\\
& = -k_j + m_j -  m_j  \!\cdot\! \paren{\sum\limits_{\nu=1}^\delta \frac{(-1)^{\nu-1}}{\tau^{2^\nu-1}}}\\
& \ge -k_j+m_j - \frac{m_j}{\tau}\\
& \ge \frac{m_j}{2} - k_j \tag{as $\tau = \omega(1)$}\\
& \ge \frac{m_j}{2} - \frac{m_j}{6}
= \frac{m_j}{3}
\ge \frac{2}{7}\cdot \paren{m_j + k_j} = \frac{2\cdot d_j}{7}
\ge \frac{\tau}{7}
\ge 2.
\end{align*}

Hence, $ \abs{\abs{\alpha_4} - \frac{m_j}{\tau^{2^\delta}}} = \abs{\tau^{2^\delta-1}\!\cdot\! \paren{-k_j + m_j\!\cdot\! \alpha_1} - \frac{m_j}{\tau^{2^\delta}}} \ge 2 - 1 =1$ and $\eta \ge \Omega(1)$.

§.§ Proof of Lemma <ref>

Using Lemma <ref> (Item 2) and the fact that $\APP$ is sub-additive (Proposition <ref>), we get

$$\APP_{k,n_0}(P) \le \sum \limits_{i=1}^s \APP_{k,n_0}(Q_{i,1}\cdots Q_{i,t_i}) \le s\cdot 2^t\cdot d^2 \cdot \max \limits_{\substack{k_0,\ell_0 \ge 0 \\ k_0 + \frac{k}{d-k}\cdot\ell_0~\le~k - \gamma}} M(n,k_0)\!\cdot\!M(n_0,\ell_0).$$

On the other hand, we have $\APP_{k,n_0}(P) \ge 2^{-O(d)}\!\cdot\!M(n,k)$.
Putting these two together, we get for some integers $k_0,\ell_0 \ge 0$ satisfying

\begin{align*}
k_0 + \frac{k}{d-k}\cdot \ell_0 \le k - \gamma,
\label{eqn:d1-d2-upper}
\end{align*}

\begin{align*}
s \ge   2^{-O(d)}\!\cdot\!2^{-t}\!\cdot\!d^{-2}\!\cdot\!\frac{M(n,k)}{M(n,k_0)\!\cdot\!M(n_0,\ell_0)}
\ge 2^{-O(d)}\!\cdot\!\paren{\frac{n}{d}}^{\Omega(\gamma)}. \tag{Using Lemma \ref{lem:binomial-coeffs} (item 1), absorbing $6^{\ell_0}$ in $2^{-O(d)}$, and borrowing calculations beginning from \eqref{eqn:calcs}}\\
\end{align*}

§.§ Proof of Lemma <ref>

We construct the word $\vecw$ as follows. Let $h' = \frac{h\cdot k}{d-k}\in \brac{\frac{h}{29},h}$. The word $\vecw$ shall consist of the following elements (the ordering of these elements shall be fixed shortly): $h,\dots,h$ ($k$ times), $-\floor{h'},\dots,-\floor{h'}$ ($k_1$ times), $-\ceil{h'},\dots,-\ceil{h'}$ ($k_2$ times), where $k_1:=(d-k)\ceil{h'}-kh$ and $k_2:=d-k-k_1$. We note that $k_1,k_2 \in \Z_{\ge 0}$ and $k+k_1+k_2=d$. Assuming $\floor{h'} = \ceil{h'}-1$ (even if $h'\in \Z$, the calculations are similar), the total sum of the weights is

\begin{align}
\sum_{i\in[d]} w_i & = kh-k_1\floor{h'}-k_2\ceil{h'} = kh-k_1(\ceil{h'}-1)-k_2\ceil{h'} = kh - k_1\ceil{h'}+k_1 - k_2\ceil{h'} \nonumber \\
& =kh-k_1\ceil{h'}+(d-k)\ceil{h'}-kh-k_2\ceil{h'}=0.
\label{eqn:zero-sum}
\end{align}

Now we fix the ordering of the above weights. For $i=1$ to $d$ in this order, if the sum $\sum_{j \in [i-1]} w_j$ is non-negative (for example, this happens for $i=1$), set $w_i$ to be an arbitrary negative weight that is available, otherwise set it to be the positive weight $h$ (if available).

If the above procedure never runs out of positive or negative weights at any step $i\in[d]$, then for all $i\in [d]$, $\abs{w_1 + \dots + w_i} \le h$. In other words, $\vecw$ is $h$. Now suppose the procedure runs out of negative weights at an index $i \in [d]$. This means that the sum $\sum_{j \in [i-1]} w_j$ is non-negative but there are no negative weights available among the unused weights. But then, the total sum of the weights would be equal to $\sum_{j \in [i-1]} w_j$ plus the sum of unused weights, which is greater than $0$, contradicting (<ref>). We get a similar contradiction if there are insufficient positive weights at any point.
For the rest of the proof, we fix $\vecw$ to be the above word. Then,
\begin{equation}
k\!\cdot\! 2^h \le n \le d\!\cdot\! 2^h, \text{~so~} 2^h \approx_{30} \paren{\frac{n}{k}}.
\label{eqn:k-n-d}
\end{equation}

Denoting the variables of $P_{\vecw}$ by $\vecx=\vecy \sqcup \vecz$, where $\vecy$ are the positive variables and $\vecz$ are the negative variables, we take
$$n_0:=\abs{\vecz} \approx_2 (d-k)\!\cdot\! 2^{\ceil{h'}}.$$
Note that $n_0  \approx_2 (d-k)\!\cdot\! 2^{\ceil{h'}} \approx 2(d-k)\!\cdot\!2^{h'} = 2(d-k)\!\cdot\! 2^{\frac{hk}{d-k}} \le 2k\!\cdot\! 2^{h} = 2(n-n_0)$ where the last inequality follows from the fact that $\frac{d-k}{k}\cdot 2^{\frac{hk}{d-k}}$ is an increasing function of $k$ when $k\in \brac{\frac{d}{30},\frac{d}{2}}$ and $h > 100$. That is, $n_0 \le 2n/3$ and $n_0 \approx 2(d-k)\!\cdot\! \paren{\frac{n}{k}}^{\frac{k}{d-k}}$ by (<ref>) and $k \leq \frac{d}{2}$. Also, $n_0 \geq \frac{d-k}{2}\cdot 2^{\ceil{h'}} \geq \frac{d-k}{2}\cdot 2^{h'} \geq \frac{d-k}{2}\cdot 2^{\frac{h}{29}} \geq \frac{d-k}{2}\cdot 2^3 \geq 2d$ as $h > 100$ and $k \leq \frac{d}{2}$. Define a map $L:\vecx \to \spacespanned{\vecz}$ as follows:

\begin{equation*}
L(x) = \begin{cases}
0, \text{~if~} x \in \vecy,\\
x, \text{~if~} x \in \vecz.
\end{cases}
\end{equation*}

We can lower bound the $\APP$ measure by using $L$ and considering only the derivatives with respect to the set-multilinear monomials over all the positive sets, i.e.,  $\cM_+(\vecw)$. By the definition of the polynomial $P_{\vecw}$ and because $\sum_{i\in [d]} w_i =0$, for every $m_+ \in \cM_+$, there exists a unique $m_- \in \cM_-$ such that $m_+\cdot m_-$ is a monomial in $P_\vecw$ and vice versa.[Recall the definition of $P_{\vecw}$ from Section <ref>. Because $|\cM_+| = |\cM_-|$, the bit representations of $m_+$ and $m_-$ are the same. However, they can have different degrees.] Hence the set of all derivatives of $P_\vecw$ with respect to monomials in $\cM_+$ is exactly $\cM_-$, yielding

\begin{equation}\partialf^k \paren{P_{\vecw}} \supseteq \cM_-(\vecw). \label{eqn:some-ders} \end{equation}

Using the fact that $\sum_{i \in [d]} w_i =0$ and (<ref>), the size of $\cM_-(\vecw)$ is

\begin{align}
\abs{\cM_-(\vecw)} = 2^{\sum_{i\in [d]: w_i < 0} \abs{w_i}} = 2^{hk} \ge 2^{-O(k)}\!\cdot\! \paren{\frac{n}{k}}^k \ge 2^{-O(d)}\!\cdot\! M(n,k).
\label{eqn:neg-monomials}
\end{align}

The last bound follows from Lemma <ref> (Item 1), as $n \ge n_0 \ge d \ge k$. As the substitution $\pi_L$ does not affect negative variables, thus,

\begin{align*}
\APP_{k,n_0}(P_{\vecw}) & \ge \dim{\spacespanned{\pi_L\paren{\partialf^k \paren{ P_{\vecw}}}}}
\ge \dim \spacespanned{\pi_L(\cM_-(\vecw))}  = \dim \spacespanned{\cM_-(\vecw)} \ge 2^{-O(d)}\!\cdot\! M(n,k).
\end{align*}

We now analyze the shifted partials of the same polynomial with $\ell := \floor{\frac{n\cdot d}{n_0}}$. Recall that $n_0 \leq 2n/3$.

\begin{align*}
\SP_{k,\ell}(P_{\vecw}) & \ge \dim \spacespanned{\vecx^\ell\cdot  \partialf^k \paren{P_{\vecw}}}\\
& \ge \dim \spacespanned{\vecy^\ell\cdot \cM_-(\vecw) } \tag{as $\vecx \supseteq \vecy$ and \eqref{eqn:some-ders}}\\
& \ge \abs{\vecy^\ell\cdot \cM_-(\vecw)}\\
& = \abs{\vecy^\ell}\cdot \abs{\cM_-(\vecw)} \tag{since $\cM_-(\vecw) \subseteq \vecz^{d-k}$ and $\vecy \cap \vecz = \Phi$}\\
& = M(n-n_0,\ell)\!\cdot\! 2^{-O(d)}\!\cdot\! M(n,k) \tag{using $\abs{\vecy} = \abs{\vecx} - \abs{\vecz}$ and \eqref{eqn:neg-monomials}}\\
& \ge M(n, \ell)\!\cdot\! \paren{1-\frac{n_0}{n}}^\ell\!\cdot\! 2^{-O(d)}\!\cdot\! M(n,k) \tag{using Lemma~\ref{lem:binomial-coeffs} (Item 3)}\\
& \ge M(n, \ell)\!\cdot\! \paren{1-\frac{n_0}{n}}^{\frac{n}{n_0}\cdot d}\!\cdot\!2^{-O(d)}\!\cdot\! M(n,k)\\
& \ge 2^{-O(d)}\!\cdot\! M(n,k)\!\cdot\! M(n,\ell) \tag{since $(1-x)^{1/x} \ge 1/3\sqrt{3}$ for $x:=n_0/n \le 2/3$}.
\end{align*}

§.§ Proof of Lemma <ref>

We begin by obtaining bounds on the value of $\ell$.

$n_0 = o(qd)$, $d^2 = o(\ell)$ and $\ell = o(qd)$.

n_0     = 2(d-k)qd/k^k/d-k

≤2(d-k)qd/k^d/2 - √(d)/8/d/2 + √(d)/8       because $k = o(qd)$ and $k\leq \frac{d}{2} - \frac{\sqrt{d}}{8}$

= 2(d-k)·qd/k·k/qd^2/4√(d)+1

≤2d·qd ·1/(qd)^1/2.5√(d)

≤2d·qd ·1/2^logqd/2.5√(d).

As $d \leq \frac{1}{150}\paren{\frac{\log n}{\log \log n}}^{2}$ and $qd \geq \frac{n}{4}$, $\frac{\log qd}{2.5\sqrt{d}} \geq \frac{12\log\log n}{3} = 4 \log \log n$. As $\log d^2 \leq 4 \log \log n - \omega(1)$, $\frac{\log qd}{2.5\sqrt{d}} = \log d^2 + \omega(1)$ and $2^{\frac{\log qd}{2.5\sqrt{d}}} = \omega(d^2)$. Thus, $n_0 = o(q) = o(qd)$.[In this proof, we need $n_0 = o(q)$. However, we require $n_0 = o(n)$, in Section <ref> and so we have mentioned $n_0 = o(qd)$ in the statement of the claim.] Now,
$\ell \geq \frac{qd^2}{n_0} - 1 \geq \frac{qd^2}{o(q)} - 1 = \omega(d^2)$. Thus, $d^2 = o(\ell)$. Also,

ℓ   ≤qd^2/n_0

= qd^2/2(d-k)k/qd^k/d-k

≤qd^2/2(d-k)k/qd^1/29        because $k = o(qd)$ and $\frac{d}{30} \leq k$

≤k·(qd)^28/29        as $k \leq \frac{d}{2}$

= o(n)        because $k \leq \log^2 n$ and $qd \leq n$.

\[S = \set{\prod\limits_{i \in [k+1\ldots d]} x_{i, h(i)}: h \in \F_q[z], \deg(h) < k}\]

\[T = \set{m : \exists \text{ monomials } m_1, \ m_2, \ \deg(m_1) = \ell, m_2 \in S \text{ and } m = m_1m_2}.\]

Observe that $T \subseteq \spacespanned{\vecx^{\ell}\partialf^{k}NW_{q,d,k}}$ and so, $\SP_{k, \ell}(NW_{q,d,k}) \geq |T|$. We obtain a lower bound on $|T|$. For $h\in \F_q[z]$ such that $\deg(h) < k$, let

\[T_h = \set{m_1\prod\limits_{i \in [k+1\ldots d]} x_{i, h(i)} : \deg(m_1) = \ell}.\]

Then, $T = \cup_{\substack{h(z) \in \F_q[z]:\\ \deg(h) < k}} T_h$. Thus, from the inclusion-exclusion principle,

\begin{align}\label{eqn:lb_size_T}
|T| \geq \sum_{\substack{h \in \F_q[z]:\\ \deg(h) < k}}|T_h| - \sum_{\substack{h_1 \neq h_2 \in \F_q[z]:\\ \deg(h_1), \deg(h_2) < k}} \abs{T_{h_1}\cap T_{h_2}}.
\end{align}

Lower bound on $\sum_{h} |T_h|$. Fix an $h \in \F_q[z]$ such that $\deg(h) < k$. Then, since for monomials $m_1 \neq m_2$, $m_1\cdot \prod\limits_{i \in [k+1\ldots d]} x_{i, h(i)} \neq m_2 \cdot \prod\limits_{i \in [k+1\ldots d]} x_{i, h(i)}$, $|T_h| = {qd + \ell - 1 \choose qd - 1}$. Hence,

\begin{align}\label{eqn:lb_qty_1_ie}
\sum_{\substack{h \in \F_q[z]:\\ \deg(h) < k}}|T_h| = |S|^k\cdot {qd + \ell - 1 \choose qd - 1} = q^k\cdot {qd + \ell - 1 \choose qd - 1}.
\end{align}

Upper bound on $\sum_{h_1 \neq h_2} |T_{h_1}\cap T_{h_2}|$. For $h_1, h_2 \in \F[z]$ such that $\deg(h_1), \deg(h_2) < k$, we say that $|h_1 \cap h_2| = r$ if $|\set{h_1(k+1), \ldots, h_1(d)} \cap \set{h_2(k+1), \ldots, h_2(d)}| = r$. Now

\begin{align}\label{eqn:ub_size_T_1_T_2}
\sum_{h_1 \neq h_2} |T_{h_1}\cap T_{h_2}| = \sum_{r = 0}^{k-1}\sum_{\substack{h_1\neq h_2: \\ |h_1 \cap h_2| = r}} |T_{h_1} \cap T_{h_2}|.
\end{align}

Fix $h_1$ and $h_2$ such that $|h_1 \cap h_2| = r$. Let $m_1 = \prod_{i \in [k+1..d]} x_{i, h_1(i)}$ and  $m_2 = \prod_{i \in [k+1..d]} x_{i, h_2(i)}$. A monomial $m \in T_{h_1} \cap T_{h_2}$ if and only if there exist degree $\ell$ monomials $m_1'$ and $m_2'$ such that $m = m_1'm_1 = m_2'm_2$.  Thus $\frac{m_2}{\gcd(m_1, m_2)}$ must divide $m_1'$. As $|h_1 \cap h_2| = r$, $\gcd(m_1, m_2)$ has degree $r$, and so $\frac{m_2}{\gcd(m_1, m_2)}$ has degree $d - k - r$. Hence the number of possible monomials $m_1'$, and thus the number of possible monomials $m$ is at most $\binom{qd+\ell-d+k+r-1}{qd-1}$. Now, the number of possible polynomials $h_1$ and $h_2$ such that $|h_1 \cap h_2| = r$ is at most $\binom{d-k}{r}q^{k-r} q^k = q^{2k-r}\binom{d-k}{r}$.[This is so because $|h_1 \cap h_2| = r$ implies that $h_1 - h_2 = (z-\alpha_1)\cdots(z-\alpha_r)\cdot g(z)$, where $\alpha_1, \ldots, \alpha_r$ are distinct elements in $[k+1..d]$ and $g(z)$ is a polynomial of degree at most $d-k$.] Hence,

\begin{align}\label{eqn:ub_T_1_T_2_r}
\sum_{\substack{h_1\neq h_2: \\ |h_1 \cap h_2| = r}} |T_{h_1} \cap T_{h_2}| \leq q^{2k-r}\cdot \binom{d-k}{r}\binom{qd+\ell-d+k+r-1}{qd-1}.
\end{align}

For $r \in [0..k-1]$, let $\chi(r) = q^{2k-r}\cdot \binom{d-k}{r}\binom{qd+\ell-d+k+r-1}{qd-1}$. Then $\chi(0) \geq \chi(r)$ for all $r \in [k-1]$.

We shall show that for all $r \in [0..k-2]$, $\frac{\chi(r+1)}{\chi(r)} < 1$; this will prove the claim. Fix any $r \in [0..k-2]$.

\begin{align*}
\frac{\chi(r+1)}{\chi(r)} &= \frac{q^{2k-r-1}\cdot\binom{d-k}{r+1}\binom{qd+\ell-d+k+r}{qd-1}}{q^{2k-r}\cdot\binom{d-k}{r}\binom{qd+\ell-d+k+r-1}{qd-1}} \\
&= \frac{1}{q}\cdot\frac{\frac{(d-k)!}{(r+1)!(d-k-r-1)!}}{\frac{(d-k)!}{r!(d-k-r)!}}\cdot \frac{\frac{(qd+\ell-d+k+r)!}{(qd-1)!(\ell-d+k+r+1)!}}{\frac{(qd+\ell-d+k+r-1)!}{(qd-1)!(\ell-d+k+r)!}}\\
&= \frac{1}{q}\cdot\frac{d-k-r}{r+1}\cdot\frac{qd+\ell-d+k+r}{\ell-d+k+r+1}\\
&\leq \frac{d}{q}\cdot \frac{(1+o(1))qd}{(1-o(1))\ell} \tag{by Claim \ref{clm: bounds on ell}}\\
&= (1 + o(1))\frac{d^2}{\ell} \\
&= o(1), \tag{by Claim \ref{clm: bounds on ell}}
\end{align*}

where the second to last inequality follows from $k, r \geq 0$, $\ell, d, k, r = o(n)$ and $d, k, r = o(\ell)$ (Claim <ref>), and the last equality from the fact that $d^2 = o(\ell)$ (Claim <ref>).

From Equations (<ref>), (<ref>), and the above claim, we get

\begin{align}\label{eqn:ub_qty_2_ie}
\sum_{h_1\neq h_2}|T_{h_1} \cap T_{h_2}| \leq k\cdot q^{2k}\cdot \binom{qd+\ell-d+k-1}{qd-1}.
\end{align}

Thus from Equations (<ref>), (<ref>), and (<ref>),

\begin{align*}\label{eqn:lb_T}
|T| &\geq q^k\cdot {qd + \ell - 1 \choose qd - 1} - k\cdot q^{2k}\cdot\binom{qd+\ell-d+k-1}{qd-1}\\
&= q^k\cdot {qd + \ell - 1 \choose qd - 1} \paren{1 - \frac{k\cdot q^{2k}\cdot\binom{qd+\ell-d+k-1}{qd-1}}{q^k\cdot {qd + \ell - 1 \choose qd - 1}}}. \numberthis
\end{align*}

$\frac{k\cdot q^{2k}\cdot\binom{qd+\ell-d+k-1}{qd-1}}{q^k\cdot {qd + \ell - 1 \choose qd - 1}}\leq \frac{1}{2}$.

k·q^2k·qd+ℓ-d+k-1qd-1/q^k·qd + ℓ- 1 qd - 1    = k ·q^k ·(qd+ℓ-d+k-1)!/(qd-1)!(ℓ-d+k)!/(qd+ℓ-1)!/(qd-1)!ℓ!

= k ·q^k ·ℓ·(ℓ-1)·(ℓ-2)⋯(ℓ-d+k+1)/(qd+ℓ-1)·(qd+ℓ-2)·(qd+ℓ-3)⋯(qd+ℓ-d+k)

= k ·q^k ·1/qd-1/ℓ + 1·qd-1/ℓ-1 + 1·qd-1/ℓ-2 + 1⋯qd-1/ℓ-d+k+1 + 1

≤k ·q^k ·1/qd-1/ℓ^d-k

≤k ·q^k ·ℓ/qd^d-ke^2(d-k)/qd             (as $1-x \geq e^{-2x}$ for $x \in [0,1/2]$)

= (1 + o(1))·k ·q^k ·d/n_0^d-k         (as $d-k = o(qd)$ and $\ell \leq \frac{qd^2}{n_0}$)

= (1 + o(1))·k ·q^k ·d/2(d-k)^d-k·k/qd^k

≤(1 + o(1))·k ·1/2^k                           (as $k \leq \frac{d}{2}$)

when $d \geq 120$.

Thus, from Equation (<ref>) and $k = \Theta(d)$, we get

$$|T| \geq \frac{1}{2}\cdot q^k \cdot \binom{qd + \ell - 1}{qd - 1} \geq 2^{-O(d)} \cdot \paren{\frac{qd}{k}}^k\cdot\binom{qd + \ell - 1}{qd - 1} \geq 2^{-O(d)} \cdot \binom{qd + k - 1}{qd - 1}\cdot\binom{qd + \ell - 1}{qd - 1},$$

where the last inequality follows from Lemma <ref>. Recall that $\SP_{k,\ell}(NW_{q,d,k}) \geq |T|.$ Hence, $\SP_{k,\ell}(NW_{q,d,k}) \geq 2^{-O(d)}\cdot M(qd,k)\cdot M(qd, \ell)$.

§.§ Details about the non-set-multilinear hard polynomial

Using an analysis similar to the one in the proof of Claim <ref>, it can be shown that $n_0 = o(n)$. Also, from the proof of Lemma <ref>, $k \in \brac{\frac{d}{4}, \frac{d}{2}}$. Let us assume that $\Delta \geq 2$; the case of $\Delta = 1$ is simple and can be handled separately. Then, as $\frac{k}{d-k} \leq \alpha \leq 1 - \frac{1}{2\tau} \leq 1 - \frac{1}{2\sqrt{d}}$, $k \leq d - \frac{\sqrt{d}}{2} - k +\frac{k}{2\sqrt{d}}$, and hence $k \leq \frac{d}{2} - \frac{\sqrt{d}}{4} + \frac{k}{4\sqrt{d}} \leq \frac{d}{2} - \frac{\sqrt{d}}{4} + \frac{d}{8\sqrt{d}}  = \frac{d}{2} - \frac{\sqrt{d}}{8}$.

$|\cM_y| \leq |\cM_z|$.

$|\cM_y| = \binom{n_1 + k - 1}{n_1 - 1}$ and $\cM_z = \binom{n_0 + d - k - 1}{n_0-1}$. Thus,

\begin{align*}
\frac{|\cM_z|}{|\cM_y|} &= \frac{(n_0+d-k-1)(n_0+d-k-2)\cdots n_0}{(n_1+k-1)(n_1+k-2)\cdots n_1}\cdot \frac{k!}{(d-k)!} \\
&\geq \frac{k!}{(d-k)!}\cdot \frac{n_0^{d-k}}{n_1^k}\cdot \frac{1}{\paren{1 + \frac{k-1}{n_1}}^k} \\
&\geq (1 - o(1))\cdot \frac{k!}{(d-k)!}\cdot \paren{(2-o(1))(d-k)}^{d-k}\paren{\frac{n}{k}}^k\cdot \frac{1}{n^k} \\
\intertext{\raggedleft{(replacing $n_0$ by its value and as $n_0 = o(n), n_1 = \Theta(n) = \omega(k^2)$)}}
&\geq (1.9)^{d-k} \frac{(1-o(1))\sqrt{2\pi k} \paren{\frac{k}{e}}^k}{(1+o(1))\sqrt{2\pi (d-k)} \paren{\frac{d-k}{e}}^{d-k}}\cdot \frac{(d-k)^{d-k}}{k^k} \\
\intertext{\raggedleft{(using Sterling's approximation)}}
&\geq (1.8)^{d-k} \cdot e^{d-2k}\cdot \sqrt{\frac{k}{d-k}} \\
&\geq 1,
\end{align*}

for $d \geq 120$.

$M(n_1,k) \geq 2^{-O(k)}M(n,k)$.

As $n_1 = \Theta(n) \geq k$, from Lemma <ref>, we get

$$M(n_1,k) \geq \paren{\frac{n_1}{k}}^k = \paren{\frac{n}{k}}^k\paren{1-\frac{n_0}{n}}^k \geq \paren{\frac{n}{k}}^k\cdot e^{-\frac{2kn_0}{n}} \geq 2^{-O(k)}\cdot \paren{\frac{6n}{k}}^k \geq 2^{-O(k)}\cdot M(n,k),$$

where the third to last inequality follows from $n_0 = o(n)$ and the last inequality follows from $n \geq k$ and Lemma <ref>.

§.§ Can we avoid the $2^{-O(k)}$ factor loss in our lower bounds?

In this section, we will work with the shifted partials measure, but the conclusion also holds for $\APP$. For any homogeneous polynomial $P\in \F[x_1,\dots,x_n]$ of degree $d$ and any choice of parameters $k < d$ and $\ell$, note that
$$\SP(P) \le \min \set{M(n,k)\!\cdot\! M(n,\ell),  M(n,\ell+d-k)}.$$
Hence, the best possible lower bound with our current estimates for the measure (from Lemma <ref>), for fixed values of $n,d,k,\gamma$, is at most

\begin{align}
\Lambda := \max_{\ell}\set{\frac{\min\set{M(n,k)\!\cdot\! M(n,\ell),  M(n,\ell+d-k)}}{\max\limits_{\substack{k_0,\ell_0\geq 0: \\ k_0 + \frac{k}{d-k}\cdot\ell_0 \le k - \gamma}}M(n,k_0)\!\cdot\! M(n,\ell+\ell_0)}}.
\label{eqn:best-lb-1}
\end{align}

We claim that the above quantity is at most $2^{-\Omega\paren{k}}\cdot n^{O(\gamma)}$ as long as $d \le {n}^{1/4}$.
We will assume that $k \le d/2$ as the other case simply reduces to this case. Also, we assume that $\gamma = o(k)$ as otherwise the multiplicative factor of $2^{-\Omega\paren{k}}$ is irrelevant.
The maximum of the R.H.S. in  (<ref>) is attained for the choice of $\ell$ when $M(n,k) \!\cdot\! M(n,\ell)$ and $M(n,\ell+d-k)$ are the closest. Notice that $\frac{M(n,k)\cdot M(n, \ell)}{M(n, \ell + d - k)}$ increases along with $\ell$. Also, as $k \leq d/2$, there are values of $\ell$ for which the ratio is less than 1 and greater than 1. Thus we can fix $\ell$ (for a given $k$) such that $M(n,k) \!\cdot\! M(n,\ell) = M(n,\ell+d-k)$ (we use an exact equality here for brevity).

\begin{align*}
\Lambda &\leq \frac{M(n,k)\!\cdot\! M(n,\ell)}{\max\limits_{\substack{k_0,\ell_0\geq 0: \\ k_0 + \frac{k}{d-k}\cdot\ell_0 \le k - \gamma}}M(n,k_0)\!\cdot\! M(n,\ell+\ell_0)} \\ &= \min\limits_{\substack{k_0,\ell_0\geq 0: \\ k_0 + \frac{k}{d-k}\cdot\ell_0 \le k - \gamma}}\frac{M(n,k)\!\cdot\! M(n,\ell)}{M(n,k_0)\!\cdot\! M(n,\ell+\ell_0)} \numberthis
\label{eqn:best-lb-2}
\end{align*}

We have two cases depending on how large the value of $\ell$ is.

Case 1: $\ell \ge d^2$.

\begin{align*}
\frac{M(n,k) \!\cdot\! M(n,\ell)}{M(n,k_0)\!\cdot\! M(n,\ell+\ell_0)}
& \le \frac{M(n,k)}{M(n,k_0)\!\cdot\! \paren{1+\frac{n-1}{\ell+\ell_0}}^{\ell_0}} \\
& \le \frac{4\!\cdot\!M(n,k)}{M(n,k_0)\!\cdot\! \paren{1+\frac{n-1}{\ell+1}}^{\ell_0}}
\tag{$\ell_0 \leq d$ and $\ell \geq d^2$ implies that $\paren{\frac{\ell + \ell_0}{\ell + 1}}^{\ell_0} \leq 4$}\\
& \le \frac{4\!\cdot\! M(n,k)}{M(n,k_0)\!\cdot\!M(n,k)^{\ell_0/\paren{d-k}}} \\
\intertext{\raggedleft{(using $\paren{1+\frac{n-1}{\ell+1}}^{d-k} \geq \frac{M(n,\ell+d-k)}{M(n,\ell)}$ and $M(n,k)\!\cdot\!M(n,\ell) = M(n,\ell+d-k)$}}
& \le \frac{4e\sqrt{2\pi k_0}\!\cdot\!\paren{1+o(1)}^k\!\cdot\! {\paren{en/k}^{k-\frac{k}{d-k}\cdot \ell_0}}}{ \paren{en/k_0}^{k_0}}. \tag{using Sterling's approximation and $k_0 = o(n)$}\\
\end{align*}

Case 2: $\ell \le d^2 \le \sqrt{n}$. In this regime, ignoring some polynomial factors, $M(n,k) = \paren{\frac{en}{k}}^k$, $M(n,\ell)=\paren{\frac{en}{\ell}}^\ell$ (unless $\ell$ is 0, in which case we may take $\ell=1$ as this does not alter the quantities we are considering by more than linear factors) and $M(n,\ell+d-k)=\paren{\frac{en}{\ell+d-k}}^{\ell+d-k}$. Similarly, $M(n,k_0) =  \paren{\frac{en}{k_0}}^{k_0}$ and $M(n,\ell+\ell_0) = \paren{\frac{en}{\ell+\ell_0}}^{\ell+\ell_0}$. These approximations follow as we can upper bound $\paren{1+\frac{x}{y}}^x$, and upper and lower bound $\paren{1-\frac{x}{y}}^x$ by a constant when $x^2 = O(y)$. Note that the real valued function defined by $f(x):= x\!\cdot\! \ln (en/x)$ over $x \in [1,\ell+d-k]$ is concave. Hence applying Jensen's inequality we obtain that $f(\ell+\ell_0) - f(\ell) \ge \frac{\ell_0}{d-k} \cdot \paren{f(\ell+d-k) -f(\ell)}$ or equivalently, $\frac{\paren{\frac{en}{\ell+\ell_0}}^{\ell+\ell_0}}{\paren{\frac{en}{\ell}}^\ell} \ge \paren{\frac{\paren{\frac{en}{\ell+d-k}}^{\ell+d-k}}{\paren{\frac{en}{\ell}}^\ell}}^{\frac{\ell_0}{d-k}} = \poly(n,d)\cdot \paren{\frac{en}{k}}^{\frac{k}{d-k}\cdot \ell_0}$ as $M(n,k)M(n,\ell) = M(n,\ell+d-k)$ and $\ell_0 \leq d-k$. Therefore,

\begin{align*}
\frac{M(n,k)\!\cdot\!M(n,\ell)}{M(n,k_0)\!\cdot\!M(n,\ell+\ell_0)} & \le \poly(n,d) \cdot \frac{\paren{\frac{en}{k}}^k\!\cdot\!\paren{\frac{en}{\ell}}^\ell}{\paren{\frac{en}{k_0}}^{k_0}\!\cdot\!\paren{\frac{en}{\ell+\ell_0}}^{\ell+\ell_0}}\\
& \le \poly(n,d) \cdot \frac{\paren{en/k}^{k-\frac{k}{d-k}\cdot \ell_0}}{\paren{en/k_0}^{k_0}}.
\end{align*}

Thus, in both cases, ignoring some polynomial factors and $\paren{1+o(1)}^k \le 2^{o(k)}$ because they are asymptotically smaller than the $2^{\Omega(k)}$ factor, we get that

\begin{align*}
\Lambda &\leq \min\limits_{\substack{k_0,\ell_0\geq 0: \\ k_0 + \frac{k}{d-k}\cdot\ell_0 \le k - \gamma}} \frac{\paren{en/k}^{k-\frac{k}{d-k}\cdot \ell_0}}{\paren{en/k_0}^{k_0}} \\
&= \min\limits_{\substack{k_0,\ell_0\geq 0: \\ k_0 + \frac{k}{d-k}\cdot\ell_0 \le k - \gamma}} \frac{\paren{en/k}^{k-k_0-\frac{k}{d-k}\cdot \ell_0}}{\paren{k/k_0}^{k_0}}, \numberthis
\label{eqn:lambda-final}
\end{align*}

Thus to show that $\Lambda \leq 2^{-\Omega\paren{k}}\!\cdot\! n^{O(\gamma)}$, we only need to show that there exist values of $k_0$ and $\ell_0$ for which the fraction in the R.H.S. of (<ref>) is at most $2^{-\Omega\paren{k}}\!\cdot\! n^{O(\gamma)}$. To find such $k_0, \ell_0$, we let $k_0$ be a function of $\ell_0$ defined as $k_0 = \floor{k-\gamma- \frac{k}{d-k}\cdot \ell_0}$. As we keep adding 1 to $\ell_0$ starting from $\floor{\frac{d-k}{3}}$ to $\floor{\frac{d-k}{2}}$, note that $k_0$ decreases from nearly $\floor{2k/3-\gamma}$ to nearly $\floor{k/2 -\gamma}$, with the decrease being at most  1 at a time (as $k \le d-k$). Therefore, as $\gamma = o(k)$, there must be a choice of $\ell_0 \in [0..(d-k)]$ such that $k_0 \approx_2 {2k/3}$. Further, for this value of $\ell_0$ and $k_0$, we also have $k-\gamma-1 \leq k_0 + \frac{k}{d-k}\cdot \ell_0 \leq k - \gamma$. Thus, (<ref>) yields $\Lambda \le 2^{-\Omega\paren{k}}\!\cdot\! n^{O(\gamma)}$.

§ PROOFS FROM SECTION <REF>

§.§ Proof of Lemma <ref>

By induction on $d$. If $d=1$, then $\degseq(\cT)=(d_1)=(1)$, so all the conditions are trivially met. For $d\ge 2$, consider the node $v$ of $\cT$ defined at line <ref> of Algorithm <ref>. Suppose the left and right children of $v$ are $v_L$ and $v_R$ respectively.
We have
$$\leaves(v)= \leaves(v_L) + \leaves(v_R) \le 2\cdot \leaves(v_R) \le \frac{2d}{3}.$$
Then by line <ref>,
$$e_1 = d - d_1 = \leaves(v) \in \bigg (\frac{d}{3}, \frac{2d}{3}\bigg] = \bigg (\frac{e_0}{3}, \frac{2e_0}{3}\bigg].$$
Note that if $v$ itself was a leaf, then $\leaves(v) \le \frac{2d}{3}$ still holds as $d\ge 2$. From line <ref>, it is evident that $(d_2,\dots,d_t) = \degseq(\cT_v)$. As the number of leaves in $\cT_v$ is $\leaves(v) < d$, by induction, we have that for all $i \in [t-2]$,
$$f_i \in \bigg(\frac{f_{i-1}}{3}, \frac{2 f_{i-1}}{3}\bigg ]$$
where $f_i:= \leaves(v)-\sum \limits_{j=2}^{i+1} d_j$. But, notice that $f_i = d-d_1-\sum \limits_{j=2}^{i+1} d_j = e_{i+1}$. Hence, we have, for $i \in [t-1]$,
$$e_i=f_{i-1} \in \bigg(\frac{f_{i-2}}{3}, \frac{2f_{i-2}}{3} \bigg] = \bigg(\frac{e_{i-1}}{3}, \frac{2e_{i-1}}{3} \bigg].$$

Also, by induction, we trivially get $d_t=1$ and $e_t=d-d_1-\sum \limits_{j=2}^{t} d_j= \leaves(v) - \sum \limits_{j=2}^{t} d_j=0$. Using $e_i \in \bigg(\frac{e_{i-1}}{3},\frac{2e_{i-1}}{3} \bigg]$ and $e_0=d$, we get $e_i \in \bigg( \frac{d}{3^i}, \frac{2^i\cdot d}{3^i}\bigg]$, so $1=d_t=e_{t-1}-e_t = e_{t-1}$. Hence, $\frac{d}{3^{t-1}} \leq 1 \leq \frac{2^{t-1}\cdot d}{3^{t-1}}$ and $\log_3 d + 1 \leq t \leq \log_{3/2} d  + 1$.

§.§ Proof of Lemma <ref>

The proof is by induction on the size of the formula $C$. In the base case, $C$ computes a variable, say $x_1$. Then, we have $d=s=\size(C)=t=d_1=1$ and $f=x_1$, all consistent with the lemma statement.

Let $v$ be the node in the canonical parse tree $\cT:=\cT(C)$ at line <ref> in Algorithm <ref> – that is, it is the last node in the rightmost path of $\cT$ which has more than $\frac{d}{3}$ leaves in its subtree. Now, let $\cP$ be an arbitrary parse tree of $C$ and let $\phi$ denote an isomorphism from $\cP$ to $\cT$ – we know such an isomorphism exists from Proposition <ref>. Let $u$ be the node in $\cP$ such that $\phi(u) = v$. Let $g$ be the multiplication gate in $C$ that corresponds to $u$.

Recall that $C_g$ and $C_{g \leftarrow y}$, respectively, denote the sub-formula at $g$ and the formula obtained by replacing the gate $g$ with $y$, where $y$ could be a new variable or a constant from the field. Due to homogeneity, $\deg(C_g) = \leaves(u) = \leaves(v)$. Also, note that $C_g$ is a UPT formula as it is a sub-formula of $C$. However, the formula $C_{g\leftarrow 0}$ need not be homogeneous, as we require all the leaves of homogeneous formulas to be labelled by variables. Nevertheless, one can easily eliminate the zero gates by simplifying the formula using the rules $g' \times 0 = 0$ and $g' + 0 = g'$; this ultimately results in a homogeneous formula. In fact, we argue below that it would be a UPT formula.

Let $h$ be the first addition gate on the path from $g$ to the root of $C$. If no such gate exists, then $C_{g\leftarrow 0} = 0$ and thus can be considered to be a UPT formula with its canonical parse tree being the empty tree. Otherwise, let $h'$ be the child of $h$ such that $g$ is in the subformula rooted at $h'$. Then, $C_{g\leftarrow 0} = 0$ is equivalent to the formula obtained by removing the edge from $h'$ to $h$ in $C$ and the entire sub-formula at $h'$. Now, a parse tree is constructed by picking only one child of every addition gate. Since $C_{g\leftarrow 0} = 0$ is equivalent to the formula obtained by removing a child of an addition gate from $C$, every parse tree of $C_{g\leftarrow 0}$ is also a parse tree of $C$. Thus, $C_{g \gets 0}$ is a UPT formula. We will make use of the fact that $C_g$ and $C_{g\leftarrow 0}$ are UPT formulas later.

For a new variable $y$, the formula $C_{ g \leftarrow y}$ uses exactly one copy of $y$, so $C_{ g \leftarrow y}$ computes a polynomial in $\F[x_1,\dots,x_n,y]$ of the form $A_g\cdot y + B_g$, where $A_g$ and $B_g$ are polynomials in $\F[x_1,\dots,x_n]$. Substituting the variable $y$ to 0 in $C_{g\leftarrow y} = A_g\cdot y + B_g$, we see that $B_g$ is computed by the formula $C_{g\leftarrow 0}$. Plugging in $y$ to be the polynomial computed by $C_g$ results in the original formula $C$. Therefore,

\begin{equation}
C = C_{g \leftarrow y} | _{ y = C_g} = A_g\cdot C_g + B_g = A_g\cdot C_g + C_{g \leftarrow 0}.
\label{eqn:1}
\end{equation}

It is easy that $A_g$ is a homogeneous polynomial of degree $d-\leaves(v)$.

As $C_g$ and $C_{g\leftarrow 0}$ are smaller formulas compared to $C$, by induction, we have the expressions:

$$C_g = \sum \limits_{i=1}^{s_1} Q^{(1)}_{i,1}\dots Q^{(1)}_{i,t_1},$$

$$C_{g\leftarrow 0} = \sum \limits_{i=1}^{s_2} Q^{(2)}_{i,1}\dots Q^{(2)}_{i,t_2},$$

for some homogeneous polynomials $\set{Q^{(1)}_{i,j}}_{i,j}$ and $\set{Q^{(2)}_{i,j}}_{i,j}$, $t_1\ge 1,t_2 \ge 1$, $s_1 \in [0..\size(C_g)]$, and $s_2 \in [0..\size(C_{g \leftarrow 0})]$. Plugging these expressions in (<ref>), we get

\begin{equation}
C = A_g\cdot C_g + C_{g\leftarrow 0} =  A_g\cdot \sum \limits_{i=1}^{s_1} Q^{(1)}_{i,1}\dots Q^{(1)}_{i,t_1} + \sum \limits_{i=1}^{s_2} Q^{(2)}_{i,1}\dots Q^{(2)}_{i,t_2}
\label{eqn:2}
\end{equation}

Since the canonical parse tree of $C_g$ is

\begin{align}
\cT(C_g) & = \canon(\cP_u) \tag{as $\cP$ is a parse tree of $C$, $\cP_{u}$ is a parse tree of $C_g$}\\
& = \canon(\cP)_{\phi(u)} \tag{from~Proposition~\ref{clm:prelim}}\\
& = \canon(\cP)_v \tag{as $\phi(u) = v$}\\
& = \cT(C)_{v} \tag{as $\cT(C) = \canon(\cP)$}
\end{align}

and that of $C_{g \leftarrow 0}$ is $\cT(C)$, we have $\degseq({\cT(C)}_v) = (d_1^{(1)},\dots,d_{t_1}^{(1)})$ and $\degseq(\cT(C)) = (d_1^{(2)},\dots,d_{t_2}^{(2)})$, where $d^{(\kappa)}_{j}:= \deg\paren{Q^{(\kappa)}_{i,j}}$ for any $\kappa\in[2], i \in [s_\kappa], j\in [t_\kappa]$. From line <ref> of the function $\degseq$ for input $\cT(C)$, we have $\degseq(\cT(C)) = (d - \leaves(v), \degseq(\cT(C)_v))$; comparing these two sequences element-wise, we get, $d^{(2)}_1 = d-\leaves(v)$, and $d^{(2)}_{j+1}=d^{(1)}_j$ for $j$ in $[t_1]$, and $t_2=1+t_1$. From (<ref>), we have

\begin{equation*}
C =  \sum \limits_{i=1}^{s} Q_{i,1}\dots Q_{i,{t}}~,
\end{equation*}

where $s:=s_1+s_2$, $t:=t_2$, and

A_g & \text{ for }i \in [s_1] \text{ and } j=1\\
Q^{(1)}_{i,j-1} & \text{ for }i \in [s_1] \text{ and } j \in [2, t_2]\\
Q^{(2)}_{i-s_1,j} & \text{ for }i \in [s_1+1, s_1+s_2] \text{ and } j \in [t_2]
\end{cases}$$

All that remains to be checked now is that the degrees of $Q_{i,j}$ for different $j$'s matches the degree sequence $\degseq(\cT(C))=(d^{(2)}_1,\dots,d^{(2)}_{t_2})$.

For $i > s_1$, clearly $\deg(Q_{i,j})= \deg(Q^{(2)}_{i-s_1,j})= d^{(2)}_j$. For $i \le s_1$, we have $\deg(Q_{i,1}) = \deg(A_g) = d - \leaves(v) =  d^{(2)}_1$, and for $j\in [2, t_2]$, $\deg(Q_{i,j})=\deg(Q^{(1)}_{i,j-1})=d^{(1)}_{j-1}=d^{(2)}_{j}$. As desired, $s=s_1+s_2\le \size(C_g) + \size(C_{g\leftarrow0}) \le \size(C)$.

§.§ Proof of Claim <ref>

First, the function $\funJ:[3m] \to [t-2]$ is well-defined: Consider any $i \in [3m]$. Then the set $\set{j\in[0..t]:e_j \le 3^i}$ is not empty; it contains $t-2$, as $e_{t-2} < 3\cdot e_{t-1} = 3 \le 3^i$.[$e_{t-1} = 1$ is shown in the proof of Lemma <ref>.] And, $0$ is not contained in this set as
$$e_0 = d > 3^{3\floor{\frac{\log_3 d - 1}{3}}} = 3^{3m} \ge 3^i.$$

Let $j:=\funJ(i)\in[t-2]$. We show that $3^{i-1} < e_j$ by contradiction. Suppose that $e_j \le 3^{i-1}$. From the minimality condition in the definition of $\funJ$, we have $e_{j-1} > 3^i$. Hence, $e_{j} \le 3^{i-1} < \frac{e_{j-1}}{3}$, which contradicts Equation (<ref>).
It follows that $\funJ$ is injective because an integer cannot lie between two different pairs of consecutive powers of 3.

§.§ Proof of Claim <ref>

As $b_0$ and $b_1$ are close to each other, so are their integer parts. Indeed, $|\floor{b_1} - \floor{b_0}|$ is 0 or 1. We will only analyse the former case as the latter case can be easily reduced to the former. Hence we have, $|\fract{b_1} - \fract{b_0}| = |\paren{b_1-\floor{b_1}} - \paren{b_0-\floor{b_0}}| = |b_1 - b_0| \in \brac{\frac{1}{9}, \frac{8}{9}}$. As $\fract{b_0}$ and $\fract{b_1}$ are in the range $\brac{0,1}$, if neither of them lies in $\brac{\frac{1}{18}, \frac{17}{18}}$, the difference between them cannot be in the range $\brac{\frac{1}{9}, \frac{8}{9}}$. Therefore, at least one of $\fract{b_0}$ or $\fract{b_1}$ lies in $\brac{\frac{1}{18}, \frac{17}{18}}$.

§ LARGE-DEGREE SET-MULTILINEAR LOWER BOUND (USING [37])

One of the primary motivations for our alternate approach of the lower bounds of [37] is based on a hope that we can achieve exponential constant-depth homogeneous formula lower bounds (rather than simply superpolynomial) and resolve Open Problem 1.2 from Section <ref>. A necessary condition for us to be able to achieve this is to at least get such lower bounds for set-multilinear constant-depth formulas. Although exponential set-multilinear (or even multilinear) constant-depth lower bounds already follow from [48, 8, 6], these techniques do not give non-FPT lower bounds, unlike [37].

In this section, we show how to obtain an exponential non-FPT lower bound against constant-depth set-multilinear formulas by making a small adjustment to the lower bound proof in [37]. However, we note that this change does not allow us to retain the iterated matrix multiplication as the hard polynomial, instead we are only able get the lower bound for some polynomial in $\VNP$. For the sake of simplicity, we shall present the idea only for depth-5 set-multilinear formulas; the parameters that work for larger depths are similar to the parameters we use in Section <ref>. We will assume that the reader is familiar with the original paper [37], where the authors  handle degree at most $O(\log^2 n)$ (Lemma 13 in [37]), whereas the following claim handles the full range of degrees up to $n$.

For any integers $d \le n$, there is a set-multilinear polynomial (family) $P \in \VNP$ of degree $d$ over at most $N=nd$ variables such that any set-multilinear formula of product-depth 2 computing it has size $n^{\Omega(\sqrt{d})}$. In particular, this gives a $N^{\Omega(N^{1/4})}$ lower bound.

The main idea to handle a larger degree is that the set sizes need not be powers of 2 if we are content with proving the lower bound for some polynomial in $\VNP$, and not necessarily for the $IMM$ polynomial (or its projection).

Let $\vecx = \vecx_1 \sqcup \dots \sqcup \vecx_d$ be the variable sets; of which some are “positive” and the rest are “negative” sets; in particular, let $\vecw=(w_1,\dots,w_d)$ be a tuple of (not necessarily integers) formed by $h$ and $-h_0$ such that all the prefix sums are at most $h$ in absolute value. According to the signs of the $w_i$'s, we classify the variable sets as positive or negative, and fix the sizes of the positive sets to be $n=2^h$, and that of negative sets to be $n_0 = 2^{h_0}$. We set $h=\log n$ and $h_0 = h-c\cdot h/\sqrt{d}$ for an appropriate constant $c \in [0.9,1]$ that we fix later so that $n_0$ is an integer.

Let $\cM_+$ be the set-multilinear monomials over the positive sets and similarly $\cM_-$ be the “negative monomials”, both sets ordered in lexicographical order, where we express a monomial in a canonical way by ordering the variables in increasing order of the corresponding variable set indices. Then we define

\[P := \sum_{\substack{{m_+ \in \cM_+},~{m_- \in \cM_-}\\ \rank(m_+) = \rank(m_-)}} m_+ \cdot m_{-},\]

where $\rank(m)$ is the position of the positive or negative monomial $m$ in the corresponding monomial set. It is not hard to show that $P \in \VNP$ and $\relrk(P) \ge 2^{-O(h)}=n^{-O(1)}$. By following the same proof of Claim 14 in [37], we conclude that any product-depth 2 set-multilinear formula $C$ must satisfy $\relrk(C) \le \frac{\size(C)}{n^{\Omega(\sqrt{d})}}$. Hence, $\size(C) \ge n^{\Omega(\sqrt{d})}$ if $C$ computes $P$.

All that remains to show is that there exists a value of $c\in [0.9,1]$ such that $n_0 = 2^{h_0} = 2^{h-c\cdot h/\sqrt{d}}$ is an integer. This is true because $n_0$ is a monotonous real function of $c$ with range

\begin{align*}2^{h-0.9 h/\sqrt{d}} - 2^{h-h/\sqrt{d}}
& = 2^{h\paren{1-1/\sqrt{d}}}\paren{2^{\frac{0.1 h}{\sqrt{d}}}-1}\\
& \ge 2^{h\paren{1-1/\sqrt{d}}}\paren{\frac{0.1 h}{\log e\sqrt{d}}} \\
& \ge n^{1-1/\sqrt{d}}/\sqrt{d} \tag{assuming $h$ is large enough} \\
& \ge n^{1-1/\sqrt{d}}/\sqrt{n} \\
& \ge 1.\end{align*}

As the range of $n_0$ is at least 1, it must take an integral value for some setting of $c$.

§ GEOMETRIC INTUITION BEHIND $\SP$ AND $\APP$ MEASURES

In this section, we give the geometric intuition which led to the development of the shifted partials measure $\SP_{k,\ell}$ and the affine projection of partials measure $\APP_{k,n_0}$. We will see, however, that this intuition breaks down when $k$ is large and prior lower bounds did indeed only use small values of $k$. By using higher values of $k$ here, we depart from this geometric intuition.

Preliminaries: the algebra-geometry dictionary.
Let $\mathbb{V} \subseteq \mathbb{F}^n$ be the zero set of polynomials $\inbrace{g_1(\vecx), g_2(\vecx), \ldots, g_s(\vecx)} \subseteq \FF[\vecx]^{=d}$. Let $P_{\ell}(\mathbb{V}) \subseteq \FF[\vecx]^{=\ell}$ be the vector space of polynomials of degree $\ell$ which vanish at every point in $\mathbb{V}$. Now, if $\V$ has a small codimension, then $\mathbb{V}$ contains a lot of points which in turn imposes a lot of (linear) constraints on $P_{\ell}(\mathbb{V})$ and so intuitively we should have that:

If codimension of $\mathbb{V}$ is small then dimension of $P_{\ell}(\mathbb{V})$ is also small.

Now notice that for all $\ell \geq d$, the set of polynomials $\vecx^{(\ell-d)} \cdot \inbrace{g_1(\vecx), g_2(\vecx), \ldots, g_s(\vecx)}$ is contained in $P_{\ell}(\mathbb{V})$ and so intuitively we should have:

If codimension of $\mathbb{V}$ is small then dimension of $\vecx^{(\ell-d)} \cdot \inbrace{g_1(\vecx), g_2(\vecx), \ldots, g_s(\vecx)}$ is also small[
An asymptotic statement that captures this qualitative intuition is obtained through the notion of the Hilbert polynomial of the variety $\mathbb{V}$.

We also have that

If $L \subseteq \FF^n$ is a random linear subspace, then the codimension of $\VV \cap L$ inside $L$ is the same as the codimension of $\VV$ inside $\FF^n$.

We can use the above intuition to formulate the shifted partials measure $\SP_{k,\ell}$ and the affine projection of partials measure $\APP_{k,n_0}$ as follows.

Formulating the measures.
Arithmetic circuits and formulas admit various depth reductions and in particular, can be reduced to depth $4$ without increasing the size too much. Consider a term $T$ of such a depth $4$ formula. Specifically, let $T(\vecx) \in \F[\vecx]$ be a product of $t$ polynomials, i.e. $T = Q_{1}(\vecx) \cdot Q_{2}(\vecx) \cdot \ldots \cdot Q_{t}(\vecx) $. First observe that for any $k<t$, the zero set of $k$-th partials of $T$, denoted $\VV(\partialf^k T)$ is of codimension $(k+1)$. The above intuition then suggests that

$$ \SP_{k,\ell} := \dim \spacespanned{\vecx^{\ell} \cdot \partialf^{k} T} $$

should also be small. Also notice that for a subspace $L \subseteq \FF^n$, $\pi_L\paren{\partialf^k T}$ is the set of polynomials whose zero set is $L \cap \VV(\partialf^k T) $
and so for such a $T$

$$ \APP_{k,n_0}(P) := \max \limits_{L : \vecx \to \spacespanned{\vecz} } \dim \spacespanned{ \pi_L\paren{\partialf^k P} } $$

should be small as well. Prior work [13, 32, 15] showed that when the degree of the factors of $T$ are also small, then these measures are indeed significantly small for such a $T$ (as compared to a random polynomial), thereby leading to lower bounds for certain classes of depth $4$ formulas (and also for some subclasses of higher depth formulas via appropriate depth reductions). But notice that the geometric intuition behind these measures holds only when $k$ is less than the number of factors $t$. In particular when $k \geq t$ then $\VV(\partialf^k T)$ could be empty[
For example when $T = (x_1^3 + x_2^3 + \ldots + x_n^3)^t$, then $\VV(\partialf^k T)$ is empty for all $k \geq t$.
] and so its no longer clear why either $\SP_{k, \ell}(T) $ or $\APP_{k, n_0}(T)$ should be small in this regime. Our conceptual contribution is that even when $k>t$ then $\SP_{k, \ell}(T)$ and $\APP_{k, n_0}(T)$ can be small (this depends on $\gamma(k)$) and this can be used to more directly obtain the lower bounds in [37].