Hence we may assume that $j \notin I$. To reach a contradiction, assume that $\sum_{i \in I} \beta_i = \sum_{i \in I} \alpha_i > \delta'(I)$. Then we must have $\delta(I) = \delta([l])$ and $\delta'(I) = \delta([l]) - 1$. This implies that $\sum_{i \in I} \alpha_i = \delta([l])$. Since $|\alpha| \le \delta([l])$ also holds, we deduce that $\sum_{i \notin I} \alpha_i = 0$. This contradicts $\alpha_j \ge 1$ and finishes the proof that $\mathcal{P}_T = \mathcal{P}(\delta')$.

The claim $((\mathcal{P}^*)_T)^* = \mathcal{P}^E$ follows from Lemma 5.2 (2) and implies that $\mathcal{P}^E$ is a polymatroid since the dual and the truncation operators preserve being a polymatroid. $\square$

Now we state Proposition 4.4 and Theorem 4.9 in the language of polymatroids.

**Theorem 5.5.** Let $V \subset \mathbb{P}^n$ be an irreducible multiprojective variety and assume that $\text{mdeg}(V, \alpha) \neq 1$ for $\alpha \in \text{supp}(V)$. If $\mathcal{P}$ denotes the polymatroid with basis vectors in $\text{supp}(V)$, then

1. the set of basis vectors of the truncation $\mathcal{P}_T$ of $\mathcal{P}$ equals the set of all formats $\alpha$ such that the associated variety $C\mathcal{Z}_{V,\alpha}$ is a hypersurface, and,

2. the set of basis vectors of the elongation $\mathcal{P}_T^E$ of $\mathcal{P}_T$ equals the set of all formats $\beta$ such that the higher associated variety $H\mathcal{Z}_{V,\beta}$ is a hypersurface.

# 6 Acknowledgments

The authors would like to thank Matías Bender, Kathlén Kohn, Jonathan Leake, and Jorge Alberto Olarte for useful discussions. We also thank the anonymous referee for suggesting improvements. A.E. is supported by NSF CCF 2110075, M.L.D. is supported by ERC Grant 787840, E.T. is supported by ANR JCJC GALOP (ANR-17-CE40-0009), the PGMO grant ALMA, and the PHC GRAPE.

# References

[1] John Abbott, Manuel Bronstein, and Thom Mulders. Fast deterministic computation of determinants of dense matrices. In *Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation*, ISSAC '99, pages 197-204, New York, NY, USA, 1999. Association for Computing Machinery.

[2] Saugata Basu, Richard Pollack, and Marie-Françoise Coste-Roy. *Algorithms in Real Algebraic Geometry*, volume 10 of *Algorithms and Computation in Mathematics*. Springer Berlin / Heidelberg, Berlin, Heidelberg, 2006.

[3] Laurent Bernardin. *Factorization of multivariate polynomials over finite fields*. PhD thesis, ETH Zurich, 1999.

[4] Cornelius Brand and Michael Sagraloff. On the complexity of solving zero-dimensional polynomial systems via projection. In *Proc. ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)*, pages 151–158, 2016.

[5] Leandro Caniglia. How to compute the chow form of an unmixed polynomial ideal in single exponential time. *Applicable Algebra in Engineering, Communication and Computing*, 1(1):25–41, 1990.

[6] John Canny. Generalised characteristic polynomials. *Journal of Symbolic Computation*, 9(3):241–250, March 1990.

[7] Federico Castillo, Yairon Cid-Ruiz, Binglin Li, Jonathan Montaño, and Naizhen Zhang. When are multidegrees positive? *Advances in Mathematics*, 374:107382, 2020.

[8] David Castro, Marc Giusti, Joos Heintz, Guillermo Matera, and Luis Miguel Pardo. The hardness of polynomial equation solving. *Foundations of Computational Mathematics*, 3:347–420, 2003.
Hence we may assume that $j \notin I$. To reach a contradiction, assume that $\sum_{i \in I} \beta_i = \sum_{i \in I} \alpha_i > \delta'(I)$. Then we must have $\delta(I) = \delta([l])$ and $\delta'(I) = \delta([l]) - 1$. This implies that $\sum_{i \in I} \alpha_i = \delta([l])$. Since $|\alpha| \le \delta([l])$ also holds, we deduce that $\sum_{i \notin I} \alpha_i = 0$. This contradicts $\alpha_j \ge 1$ and finishes the proof that $\mathcal{P}_T = \mathcal{P}(\delta')$.

The claim $((\mathcal{P}^*)_T)^* = \mathcal{P}^E$ follows from Lemma 5.2 (2) and implies that $\mathcal{P}^E$ is a polymatroid since the dual and the truncation operators preserve being a polymatroid. $\square$

Now we state Proposition 4.4 and Theorem 4.9 in the language of polymatroids.

**Theorem 5.5.** Let $V \subset \mathbb{P}^n$ be an irreducible multiprojective variety and assume that $\text{mdeg}(V, \alpha) \neq 1$ for $\alpha \in \text{supp}(V)$. If $\mathcal{P}$ denotes the polymatroid with basis vectors in $\text{supp}(V)$, then

1. the set of basis vectors of the truncation $\mathcal{P}_T$ of $\mathcal{P}$ equals the set of all formats $\alpha$ such that the associated variety $C\mathcal{Z}_{V,\alpha}$ is a hypersurface, and,

2. the set of basis vectors of the elongation $\mathcal{P}_T^E$ of $\mathcal{P}_T$ equals the set of all formats $\beta$ such that the higher associated variety $H\mathcal{Z}_{V,\beta}$ is a hypersurface.

# 6 Acknowledgments

The authors would like to thank Matías Bender, Kathlén Kohn, Jonathan Leake, and Jorge Alberto Olarte for useful discussions. We also thank the anonymous referee for suggesting improvements. A.E. is supported by NSF CCF 2110075, M.L.D. is supported by ERC Grant 787840, E.T. is supported by ANR JCJC GALOP (ANR-17-CE40-0009), the PGMO grant ALMA, and the PHC GRAPE.

# References

[1] John Abbott, Manuel Bronstein, and Thom Mulders. Fast deterministic computation of determinants of dense matrices. In *Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation*, ISSAC '99, pages 197-204, New York, NY, USA, 1999. Association for Computing Machinery.

[2] Saugata Basu, Richard Pollack, and Marie-Françoise Coste-Roy. *Algorithms in Real Algebraic Geometry*, volume 10 of *Algorithms and Computation in Mathematics*. Springer Berlin / Heidelberg, Berlin, Heidelberg, 2006.

[3] Laurent Bernardin. *Factorization of multivariate polynomials over finite fields*. PhD thesis, ETH Zurich, 1999.

[4] Cornelius Brand and Michael Sagraloff. On the complexity of solving zero-dimensional polynomial systems via projection. In *Proc. ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)*, pages 151–158, 2016.

[5] Leandro Caniglia. How to compute the chow form of an unmixed polynomial ideal in single exponential time. *Applicable Algebra in Engineering, Communication and Computing*, 1(1):25–41, 1990.

[6] John Canny. Generalised characteristic polynomials. *Journal of Symbolic Computation*, 9(3):241–250, March 1990.

[7] Federico Castillo, Yairon Cid-Ruiz, Binglin Li, Jonathan Montaño, and Naizhen Zhang. When are multidegrees positive? *Advances in Mathematics*, 374:107382, 2020.

[8] David Castro, Marc Giusti, Joos Heintz, Guillermo Matera, and Luis Miguel Pardo. The hardness of polynomial equation solving. *Foundations of Computational Mathematics*, 3:347–420, 2003.
[9] John Canny and Ioannis Emiris. A subdivision-based algorithm for the sparse resultant. *Journal of the ACM (JACM)* 47(3):417–451, 2000.

[10] Arthur Cayley. On a new analytical representation of curves in space. *The Quarterly Journal of Pure and Applied Mathematics*, 3:225–236, 1860.

[11] Alexander L. Chistov. Polynomial-time computation of the dimension of algebraic varieties in zero-characteristic. *Journal of Symbolic Computation*, 22(1):1–25, 1996.

[12] David Cox, John Little, and Donal O’Shea. *Using algebraic geometry*. Graduate texts in mathematics BV000000067 185. Springer, New York u.a., 1998.

[13] John Dalbec. *Geometry and Combinatorics of Chow Forms*. PhD thesis, Cornell University, 1995.

[14] John Dalbec and Bernd Sturmfels. *Introduction to Chow Forms*. In NeilL. White, editor, *Invariant Methods in Discrete and Computational Geometry*, pages 37–58. Springer Netherlands, 1995.

[15] Carlos D’Andrea. Macaulay style formulas for sparse resultants. *Transactions of the American Mathematical Society*, 354(7):2595–2629, 2002.

[16] J. Désarménien. An algorithm for the rota straightening formula. *Discrete Mathematics*, 30(1):51–68, 1980.

[17] Alicia Dickenstein and Ioannis Z Emiris. Solving polynomial equations, volume 14 of. *Algorithms and Computation in Mathematics*, 2005.

[18] M. Levent Dogan, Alperen A. Ergür, Jake D. Mundo, and Elias Tsigaridas. The multivariate Schwartz–Zippel lemma. *SIAM Journal on Discrete Mathematics*, 36(2):888–910, 2022.

[19] David Eisenbud. *Commutative algebra with a view toward algebraic geometry*. Graduate texts in mathematics BV000000067 150. Springer, New York u.a., 1995.

[20] David Eisenbud and Joe Harris. *3264 and all that : a second course in algebraic geometry*. Cambridge University Press, Cambridge, 2016.

[21] Ioannis Emiris, Bernard Mourrain, and Elias Tsigaridas. Separation bounds for polynomial systems. *Journal of Symbolic Computation*, 101:128–151, 2020.

[22] Israel M Gelfand, Mikhail Kapranov, and Andrei Zelevinsky. *Discriminants, Resultants, and Multidimensional Determinants*. Modern Birkhäuser Classics. Birkhäuser Boston, Boston, MA, 1st ed. 1994. edition, 1994.

[23] Nardo Giménez and Guillermo Matera. On the bit complexity of polynomial system solving. *Journal of Complexity*, 51:20–67, 2019.

[24] Marc Giusti, Joos Heintz, and Contre Le Conicet. La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, 1991.

[25] Bruno Grenet, Pascal Koiran, and Natacha Portier. On the complexity of the multivariate resultant. *Journal of Complexity*, 29(2):142–157, 2013.

[26] Joe Harris. *Algebraic geometry : a first course*. Graduate texts in mathematics BV000000067 133. Springer, New York u.a., corr. 2. printing edition, 1993.
[9] John Canny and Ioannis Emiris. A subdivision-based algorithm for the sparse resultant. *Journal of the ACM (JACM)* 47(3):417–451, 2000.

[10] Arthur Cayley. On a new analytical representation of curves in space. *The Quarterly Journal of Pure and Applied Mathematics*, 3:225–236, 1860.

[11] Alexander L. Chistov. Polynomial-time computation of the dimension of algebraic varieties in zero-characteristic. *Journal of Symbolic Computation*, 22(1):1–25, 1996.

[12] David Cox, John Little, and Donal O’Shea. *Using algebraic geometry*. Graduate texts in mathematics BV000000067 185. Springer, New York u.a., 1998.

[13] John Dalbec. *Geometry and Combinatorics of Chow Forms*. PhD thesis, Cornell University, 1995.

[14] John Dalbec and Bernd Sturmfels. *Introduction to Chow Forms*. In NeilL. White, editor, *Invariant Methods in Discrete and Computational Geometry*, pages 37–58. Springer Netherlands, 1995.

[15] Carlos D’Andrea. Macaulay style formulas for sparse resultants. *Transactions of the American Mathematical Society*, 354(7):2595–2629, 2002.

[16] J. Désarménien. An algorithm for the rota straightening formula. *Discrete Mathematics*, 30(1):51–68, 1980.

[17] Alicia Dickenstein and Ioannis Z Emiris. Solving polynomial equations, volume 14 of. *Algorithms and Computation in Mathematics*, 2005.

[18] M. Levent Dogan, Alperen A. Ergür, Jake D. Mundo, and Elias Tsigaridas. The multivariate Schwartz–Zippel lemma. *SIAM Journal on Discrete Mathematics*, 36(2):888–910, 2022.

[19] David Eisenbud. *Commutative algebra with a view toward algebraic geometry*. Graduate texts in mathematics BV000000067 150. Springer, New York u.a., 1995.

[20] David Eisenbud and Joe Harris. *3264 and all that : a second course in algebraic geometry*. Cambridge University Press, Cambridge, 2016.

[21] Ioannis Emiris, Bernard Mourrain, and Elias Tsigaridas. Separation bounds for polynomial systems. *Journal of Symbolic Computation*, 101:128–151, 2020.

[22] Israel M Gelfand, Mikhail Kapranov, and Andrei Zelevinsky. *Discriminants, Resultants, and Multidimensional Determinants*. Modern Birkhäuser Classics. Birkhäuser Boston, Boston, MA, 1st ed. 1994. edition, 1994.

[23] Nardo Giménez and Guillermo Matera. On the bit complexity of polynomial system solving. *Journal of Complexity*, 51:20–67, 2019.

[24] Marc Giusti, Joos Heintz, and Contre Le Conicet. La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial, 1991.

[25] Bruno Grenet, Pascal Koiran, and Natacha Portier. On the complexity of the multivariate resultant. *Journal of Complexity*, 29(2):142–157, 2013.

[26] Joe Harris. *Algebraic geometry : a first course*. Graduate texts in mathematics BV000000067 133. Springer, New York u.a., corr. 2. printing edition, 1993.
[27] Robin Hartshorne. *Algebraic geometry*. Graduate texts in mathematics 52. Springer, New York u.a., 1977.

[28] Dominic Welsh. *Matroid Theory*. London u.a.: Acad. Press, 1976. Print.

[29] Jonathan Hauenstein, Anton Leykin, Jose Rodriguez, and Frank Sottile. A numerical toolkit for multiprojective varieties. *Mathematics of Computation*, 90(327):413–440, 2021.

[30] Joos Heintz, Guillermo Matera, and Ariel Waissbein. On the time–space complexity of geometric elimination procedures. *Applicable Algebra in Engineering, Communication and Computing*, 11:239–296, 2001.

[31] Joos Heintz and Jacques Morgenstern. On the intrinsic complexity of elimination theory. *Journal of Complexity*, 9(4):471–498, 1993.

[32] J. van der Hoeven and G. Lecerf. Sparse polynomial interpolation. Exploring fast heuristic algorithms over finite fields. Technical report, HAL, 2019.

[33] James E Humphreys. *Linear algebraic groups*. Graduate texts in mathematics BV000000067 21. Springer, New York u.a., 1975.

[34] Gabriela Jeronimo, Teresa Krick, Juan Sabia, and Martín Sombra. The computational complexity of the Chow form. *Foundations of Computational Mathematics*, 4(1):41–117, 2004.

[35] Gabriela Jeronimo, Susana Puddu, and Juan Sabia. Computing chow forms and some applications. *Journal of Algorithms*, 41(1):52–68, 2001.

[36] Erich Kaltofen and Gilles Villard. On the complexity of computing determinants. *Computational complexity*, 13(3):91–130, 2005.

[37] Erich Kaltofen and Lakshman Yagati. Improved sparse multivariate polynomial interpolation algorithms. In *International Symposium on Symbolic and Algebraic Computation*, pages 467–474. Springer, 1988.

[38] Mikhail M Kapranov, Bernd Sturmfels, and Andrei V Zelevinsky. Chow polytopes and general results. *Duke Mathematical Journal*, 67(1):189–218, 1992.

[39] Jürgen Klose. Binary segmentation for multivariate polynomials. *Journal of Complexity*, 11(3):330–343, 1995.

[40] Kathlén Kohn. Coisotropic hypersurfaces in Grassmannians. *Journal of Symbolic Computation*, 103:157–177, March 2021.

[41] Pascal Koiran. Randomized and deterministic algorithms for the dimension of algebraic varieties. In *Proceedings of the 38th Annual Symposium on Foundations of Computer Science*, FOCS '97, page 36, USA, 1997. IEEE Computer Society.

[42] Sylvain Lazard, Marc Pouget, and Fabrice Rouillier. Bivariate triangular decompositions in the presence of asymptotes. *Journal of Symbolic Computation*, 82:123–133, 2017.

[43] Richard Lipton. The curious history of the Schwartz-Zippel lemma. https://rjlipton.wpcomstaging.com/2009/11/30/the-curious-history-of-the-schwartz-zippel-lemma.
[27] Robin Hartshorne. *Algebraic geometry*. Graduate texts in mathematics 52. Springer, New York u.a., 1977.

[28] Dominic Welsh. *Matroid Theory*. London u.a.: Acad. Press, 1976. Print.

[29] Jonathan Hauenstein, Anton Leykin, Jose Rodriguez, and Frank Sottile. A numerical toolkit for multiprojective varieties. *Mathematics of Computation*, 90(327):413–440, 2021.

[30] Joos Heintz, Guillermo Matera, and Ariel Waissbein. On the time–space complexity of geometric elimination procedures. *Applicable Algebra in Engineering, Communication and Computing*, 11:239–296, 2001.

[31] Joos Heintz and Jacques Morgenstern. On the intrinsic complexity of elimination theory. *Journal of Complexity*, 9(4):471–498, 1993.

[32] J. van der Hoeven and G. Lecerf. Sparse polynomial interpolation. Exploring fast heuristic algorithms over finite fields. Technical report, HAL, 2019.

[33] James E Humphreys. *Linear algebraic groups*. Graduate texts in mathematics BV000000067 21. Springer, New York u.a., 1975.

[34] Gabriela Jeronimo, Teresa Krick, Juan Sabia, and Martín Sombra. The computational complexity of the Chow form. *Foundations of Computational Mathematics*, 4(1):41–117, 2004.

[35] Gabriela Jeronimo, Susana Puddu, and Juan Sabia. Computing chow forms and some applications. *Journal of Algorithms*, 41(1):52–68, 2001.

[36] Erich Kaltofen and Gilles Villard. On the complexity of computing determinants. *Computational complexity*, 13(3):91–130, 2005.

[37] Erich Kaltofen and Lakshman Yagati. Improved sparse multivariate polynomial interpolation algorithms. In *International Symposium on Symbolic and Algebraic Computation*, pages 467–474. Springer, 1988.

[38] Mikhail M Kapranov, Bernd Sturmfels, and Andrei V Zelevinsky. Chow polytopes and general results. *Duke Mathematical Journal*, 67(1):189–218, 1992.

[39] Jürgen Klose. Binary segmentation for multivariate polynomials. *Journal of Complexity*, 11(3):330–343, 1995.

[40] Kathlén Kohn. Coisotropic hypersurfaces in Grassmannians. *Journal of Symbolic Computation*, 103:157–177, March 2021.

[41] Pascal Koiran. Randomized and deterministic algorithms for the dimension of algebraic varieties. In *Proceedings of the 38th Annual Symposium on Foundations of Computer Science*, FOCS '97, page 36, USA, 1997. IEEE Computer Society.

[42] Sylvain Lazard, Marc Pouget, and Fabrice Rouillier. Bivariate triangular decompositions in the presence of asymptotes. *Journal of Symbolic Computation*, 82:123–133, 2017.

[43] Richard Lipton. The curious history of the Schwartz-Zippel lemma. https://rjlipton.wpcomstaging.com/2009/11/30/the-curious-history-of-the-schwartz-zippel-lemma.
[44] Angelos Mantzaflaris, Éric Schost, and Elias Tsigaridas. Sparse rational univariate representation. In *Proc. ACM on International Symposium on Symbolic and Algebraic Computation (ISSAC)*, pages 301–308, 2017.

[45] Hossein Nassajian Mojarrad, Thang Pham, Claudiu Valculescu, and Frank de Zeeuw. Schwartz-Zippel bounds for two-dimensional products. *arXiv preprint arXiv:1507.08181*, 2015.

[46] Brian Osserman and Matthew Trager. Multigraded Cayley-Chow forms. *Advances in Mathematics*, 348:583–606, May 2019.

[47] Oskar Perron. Beweis und verschärfung eines satzes von Kronecker. *Mathematische Annalen*, 118(1):441–448, Dec 1941.

[48] Franco Preparata and Michael Shamos. Computational geometry: an introduction. Springer Science & Business Media, 2012.

[49] Maurice Rojas. *Solving degenerate sparse polynomial systems faster*. Journal of Symbolic Computation, 28(1-2), 155–186, 1999.

[50] Martin Sombra. The height of the mixed sparse resultant. *American Journal of Mathematics*, 126(6):1253–1260, 2004.

[51] Arne Storjohann. The shifted number system for fast linear algebra on integer matrices. *Journal of Complexity*, 21(4):609–650, 2005.

[52] Bernd Sturmfels. *Algorithms in invariant theory*. Texts and monographs in symbolic computation. Springer, Wien u.a., 2. ed. edition, 2008.

[53] Bernd Sturmfels. The Hurwitz form of a projective variety. *Journal of Symbolic Computation*, 79:186–196, March 2017.

[54] Bartel Leendert Van der Waerden. On Hilberts function, series of composition of ideals and a generalization of the theorem of Bezout. In *Proc. Roy. Acad. Amsterdam*, volume 31, pages 749–770, 1929.

[55] B.L. Van der Waerden. On varieties in multiple-projective spaces. *Indagationes Mathematicae (Proceedings)*, 81(1):303–312, January 1978.

[56] Bartel L. Waerden van der and Wei-Liang Chow. Zur algebraischen geometrie. ix. Über zugeordnete formen und algebraische systeme von algebraischen mannigfaltigkeiten. *Mathematische Annalen*, 113:DCXCII–DCCIV, 1937.

[57] Chee-Keng Yap. *Fundamental problems of algorithmic algebra*. Oxford University Press, New York, 2000.

# A Auxiliary results

The proof of Proposition 3.3 relies on the following that bounds on the bitsize of multivariate polynomial multiplication; see [44].

**Claim A.1 (Polynomial multiplication).** The following bounds holds:
[44] Angelos Mantzaflaris, Éric Schost, and Elias Tsigaridas. Sparse rational univariate representation. In *Proc. ACM on International Symposium on Symbolic and Algebraic Computation (ISSAC)*, pages 301–308, 2017.

[45] Hossein Nassajian Mojarrad, Thang Pham, Claudiu Valculescu, and Frank de Zeeuw. Schwartz-Zippel bounds for two-dimensional products. *arXiv preprint arXiv:1507.08181*, 2015.

[46] Brian Osserman and Matthew Trager. Multigraded Cayley-Chow forms. *Advances in Mathematics*, 348:583–606, May 2019.

[47] Oskar Perron. Beweis und verschärfung eines satzes von Kronecker. *Mathematische Annalen*, 118(1):441–448, Dec 1941.

[48] Franco Preparata and Michael Shamos. Computational geometry: an introduction. Springer Science & Business Media, 2012.

[49] Maurice Rojas. *Solving degenerate sparse polynomial systems faster*. Journal of Symbolic Computation, 28(1-2), 155–186, 1999.

[50] Martin Sombra. The height of the mixed sparse resultant. *American Journal of Mathematics*, 126(6):1253–1260, 2004.

[51] Arne Storjohann. The shifted number system for fast linear algebra on integer matrices. *Journal of Complexity*, 21(4):609–650, 2005.

[52] Bernd Sturmfels. *Algorithms in invariant theory*. Texts and monographs in symbolic computation. Springer, Wien u.a., 2. ed. edition, 2008.

[53] Bernd Sturmfels. The Hurwitz form of a projective variety. *Journal of Symbolic Computation*, 79:186–196, March 2017.

[54] Bartel Leendert Van der Waerden. On Hilberts function, series of composition of ideals and a generalization of the theorem of Bezout. In *Proc. Roy. Acad. Amsterdam*, volume 31, pages 749–770, 1929.

[55] B.L. Van der Waerden. On varieties in multiple-projective spaces. *Indagationes Mathematicae (Proceedings)*, 81(1):303–312, January 1978.

[56] Bartel L. Waerden van der and Wei-Liang Chow. Zur algebraischen geometrie. ix. Über zugeordnete formen und algebraische systeme von algebraischen mannigfaltigkeiten. *Mathematische Annalen*, 113:DCXCII–DCCIV, 1937.

[57] Chee-Keng Yap. *Fundamental problems of algorithmic algebra*. Oxford University Press, New York, 2000.

## A Auxiliary results

The proof of Proposition 3.3 relies on the following that bounds on the bitsize of multivariate polynomial multiplication; see [44].

**Claim A.1 (Polynomial multiplication).** The following bounds holds:
(i) Consider two multivariate polynomials, $f_1$ and $f_2$, in $v$ variables of total degrees $\delta$, having bitsize $\tau_1$ and $\tau_2$, respectively. Then $f = f_1f_2$ is a polynomial in $v$ variables, of total degree $2\delta$ and bitsize $\tau_1 + \tau_2 + 2v \lg(\delta)$.

(ii) Using induction, the product of $m$ polynomials in $v$ variables, $f = \prod_{i=1}^{m} f_i$, each of total degree $\delta_i$ and bitsize $\tau_i$, is a polynomial of total degree $\sum_{i=1}^{m} \delta_i$ and bitsize $\sum_{i=1}^{m} \tau_i + 12vmlg(m) \lg(\sum_{i=1}^{m} \delta_i)$.

(iii) Let $f$ be a polynomial in $v$ variables of total degree $\delta$ and bitsize $\tau$. The $m$-th power of $f$, $f^m$, is a polynomial of total degree $m\delta$ and bitsize $m\tau + 12vmlg(\delta)$.
(i) Consider two multivariate polynomials, $f_1$ and $f_2$, in $v$ variables of total degrees $\delta$, having bitsize $\tau_1$ and $\tau_2$, respectively. Then $f = f_1f_2$ is a polynomial in $v$ variables, of total degree $2\delta$ and bitsize $\tau_1 + \tau_2 + 2v \lg(\delta)$.

(ii) Using induction, the product of $m$ polynomials in $v$ variables, $f = \prod_{i=1}^{m} f_i$, each of total degree $\delta_i$ and bitsize $\tau_i$, is a polynomial of total degree $\sum_{i=1}^{m} \delta_i$ and bitsize $\sum_{i=1}^{m} \tau_i + 12vmlg(m) \lg(\sum_{i=1}^{m} \delta_i)$.

(iii) Let $f$ be a polynomial in $v$ variables of total degree $\delta$ and bitsize $\tau$. The $m$-th power of $f$, $f^m$, is a polynomial of total degree $m\delta$ and bitsize $m\tau + 12vmlg(\delta)$.