Deterministic factorization of constant-depth algebraic circuits in subexponential time Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf Abstract While efficient randomized algorithms for factorization of polynomials given by algebraic circuits have been known for decades, obtaining an even slightly non-trivial deterministic algorithm for this problem has remained an open question of great interest. This is true even when the input algebraic circuit has additional structure, for instance, when it is a constant-depth circuit. Indeed, no efficient deterministic algorithms are known even for the seemingly easier problem of factoring sparse polynomials or even the problem of testing the irreducibility of sparse polynomials. In this work, we make progress on these questions: we design a deterministic algorithm that runs in subexponential time, and when given as input a constant-depth algebraic circuit C C over the field of rational numbers, it outputs algebraic circuits (of potentially unbounded depth) for all the irreducible factors of C C , together with their multiplicities. In particular, we give the first subexponential time deterministic algorithm for factoring sparse polynomials. For our proofs, we rely on a finer understanding of the structure of power series roots of constant-depth circuits and the analysis of the Kabanets-Impagliazzo generator. In particular, we show that the Kabanets-Impagliazzo generator constructed using low-degree hard polynomials (explicitly constructed in the work of Limaye, Srinivasan & Tavenas) preserves not only the non-zeroness of small constant-depth circuits (as shown by Chou, Kumar & Solomon), but also their irreducibility and the irreducibility of their factors. 1 Introduction The main problem of interest in this work is that of polynomial factorization — given a polynomial as input, output its decomposition into a product of irreducible polynomials. For this paper, we work in the setting where the input is a multivariate polynomial which is specified by a (small) algebraic circuit computing it, and we are over the field \mathbb{Q} of rational numbers. This problem saw significant progress starting in the 1980s where a sequence of results culminating in the works of Kaltofen [ Kal89 ] and Kaltofen & Trager [ KT90 ] gave a randomized algorithm that when given a size s algebraic circuit C computing an n variate degree d polynomial over \mathbb{Q} , terminated in \operatorname{poly}(s,d,n) time and output algebraic circuits for all the irreducible factors of C (together with their multiplicities). A surprising fact that is implicit in these results is a closure result for polynomials computable by small circuits - all irreducible factors of C have algebraic circuits of size \operatorname{poly}(s,d,n) . This is necessary for us to be able to entertain any hopes of having a polynomial time algorithm for this problem since a priori it is not even clear if there is a description of the output (namely, the irreducible factors of C ) that is polynomially bounded in the input parameters s,d,n . These polynomial factorization algorithms represent a significant landmark in our understanding of a fundamental problem in computational algebra on their own. However, in hindsight, the impact of this line of research seems to go far beyond this original context - these results and the techniques discovered in the course of their proofs have since found many diverse applications in algorithm design, pseudorandomness, coding theory and complexity theory, e.g. [ Sud97 , GS99 , Ale05 , Bog05 , DGV24 ] . Among the most important problems in this broad area of polynomial factorization that continue to be open is that of derandomizing the results of Kaltofen [ Kal89 ] and Kaltofen & Trager [ KT90 ] . In fact, even before randomized factoring algorithms were studied for general circuits, they were studied in the setting of sparse polynomials. A beautiful work by von zur Gathen and Kaltofen [ GK85 ] gave the first randomized factoring algorithm for sparse polynomials 1 1 1 The running time obtained was polynomial in the sparsity of the factors . Even for sparse polynomials, the problem of derandomizing these factoring algorithms is of great interest and has received considerable attention over the last decade or two. We now know from the work of Shpilka & Volkovich [ SV10 ] that efficient deterministic polynomial factorization is at least as hard as efficient deterministic polynomial identity testing- the reduction simply being that to check whether a multivariate f(\mathbf{x}) is non-zero, we check if the polynomial (f(\mathbf{x})+yz) is irreducible. This connection clearly continues to hold for structured sub-classes for algebraic circuits like formulas, branching programs, sparse polynomials and constant-depth circuits. Thus, the task of derandomizing polynomial factorization for any such subclass of circuits must necessarily be preceded by a non-trivial deterministic polynomial identity testing algorithm for the subclass. Perhaps a bit surprisingly, Kopparty, Saraf & Shpilka [ KSS15 ] also showed a reduction in the other direction - efficient deterministic polynomial identity testing for algebraic circuits implies efficient deterministic polynomial factorization for algebraic circuits. This reduction between the problems of polynomial factorization and polynomial identity testing continue to hold in both the black box model (where we only have query access to the input algebraic circuits) and the white box model (where we can look inside the given circuits). An important aspect of the reduction in [ KSS15 ] is that even for the task of factorizing polynomials computed by very structured circuits like formulas, constant-depth circuits or even sparse polynomials, the PIT instances that we encounter on the way are for seemingly much more powerful circuit classes like algebraic branching programs. Thus, non-trivial PIT algorithms for a structured circuit class do not immediately yield a non-trivial deterministic algorithm for factorization of polynomials computed in this class. A very natural example of this phenomenon is that of sparse polynomials (which are depth 2 circuits) and even general constant-depth circuits. For the case of sparse polynomials, we have known polynomial-time PIT algorithms for a while from the work of Klivans & Spielman [ KS01 ] , and for arbitrary constant-depth circuits, we also now have non-trivial deterministic algorithms for polynomial identity testing of constant-depth circuits. These follow from the lower bounds for constant-depth circuits in the recent work of Limaye, Srinivasan and Tavenas [ LST21 ] and the connections between hardness and derandomization for such circuits in the work of Chou, Kumar and Solomon [ CKS19 ] 2 2 2 An alternative deterministic subexponential time algorithm for PIT for constant-depth circuits was given by Andrews and Forbes [ AF22 ] in a subsequent work. . However, these deterministic polynomial identity tests do not seem to immediately imply non-trivial deterministic factorization results for either sparse polynomials or polynomials computed by constant-depth circuits. In fact, the following seemingly simpler question also appears to be open. 1.1 . Design a subexponential-time deterministic algorithm that when given a sparse polynomial as input, decides if it is irreducible. More generally, as Forbes & Shpilka mention (Questions 1.4 and 4.1 in [ FS15 ] ) in their survey on polynomial factorization, very natural questions around derandomization of polynomial factorization algorithms are wide open. 1.1 Our results Our main result in this paper addresses this question and more generally, the question of deterministic polynomial factorization for constant-depth circuits. More precisely, we prove the following. 1.2 Informal version of Theorem 5.2 . For every constant \varepsilon>0 , constant \Delta\in\mathbb{N} and sufficiently large n , the following statement is true. There is a deterministic algorithm that takes as input an algebraic circuit C over the field \mathbb{Q} on n variables with depth \Delta , and size and degree \operatorname{poly}(n) , runs in time \exp(O(n^{\varepsilon})) and outputs algebraic circuits (of potentially unbounded depth) for all irreducible factors of C , together with their multiplicities. This result in particular also gives the first subexponential deterministic factoring algorithm for sparse polynomials (which is the case when \Delta=2 ). At the heart of our proof is the deterministic construction of a variable reduction map that reduces the number of variables in a constant-depth circuit substantially, while preserving its factorization profile . The following theorem is our main technical result. 3 3 3 The theorem follows immediately from Theorem 5.1 and our deterministic implementation of some (fairly standard) preprocessing steps in the factorization algorithm. In fact, by a slight modification of our proofs, a stronger version of this theorem can be shown to be true where the time complexity of constructing the map \Gamma_{\varepsilon,\Delta} is quasipolynomially bounded in n . However, this does not improve the overall time complexity of the algorithm in Theorem 1.2 since some steps in the algorithm, for instance, that of deterministic factorization of n^{\varepsilon} variate polynomials of degree \operatorname{poly}(n) , still run in time \exp(O(n^{\varepsilon})) . 1.3 Informal version of Theorem 5.1 . For every \varepsilon>0 , every constant \Delta\in\mathbb{N} and all sufficiently large n , there is a polynomial map \Gamma_{\varepsilon,\Delta}:\mathbb{Q}^{n^{\varepsilon}}\to\mathbb{Q}^{n} of degree o(\log n) with the following properties. • Given \varepsilon,\Delta , the map \Gamma_{\varepsilon,\Delta} can be constructed deterministically in time \exp(O(n^{\varepsilon})) . • \Gamma_{\varepsilon,\Delta} is a variable reduction map that preserves the irreducibility of n -variate polynomials that can be computed by depth \Delta circuits of size and degree \operatorname{poly}(n) . In other words, an n -variate algebraic circuit C of size and degree \operatorname{poly}(n) is irreducible if and only if the n^{\varepsilon} -variate polynomial \hat{C} obtained from C by composing it with \Gamma_{\varepsilon,\Delta} is irreducible. • More generally, \Gamma_{\varepsilon,\Delta} is a variable reduction map that preserves the irreducibility of the factors of n -variate polynomials that can be computed by depth \Delta circuits of size and degree \operatorname{poly}(n) . Obtaining Theorem 1.2 from Theorem 1.3 . The second item of the above theorem, when combined with known deterministic factorization algorithms for n^{\varepsilon} -variate polynomials of degree at most \operatorname{poly}(n) that run in time n^{O(n^{\varepsilon})} (polynomial in the size of the dense representation of such polynomials), essentially gives us a subexponential time deterministic irreducibility testing algorithm for sparse polynomials, and more generally for constant-depth circuits. Similarly, the third item of Theorem 1.3 can be combined with known ideas in algorithms for polynomial factorization (with some effort) to give Theorem 1.2 . We end this section with a brief discussion of some quantitative and qualitative aspects of the main theorems. Improvements in time complexity. Given the reduction from polynomial identity testing to polynomial factorization in [ SV10 ] , we know that one cannot hope to improve the running time of the algorithm in Theorem 1.2 significantly for general constant-depth circuits, unless we have significantly better deterministic polynomial identity testing algorithms for these problems. However, for the case of sparse polynomials, we have known polynomial time PIT algorithms for more than two decades [ KS01 ] , and thus we can, in principle, expect faster factorization or irreducibility testing algorithms for sparse polynomials. It is a very natural question to explore further. Closure results for constant-depth circuits. We do not know if irreducible factors of polynomials with small constant-depth circuits (or even the more restricted class of sparse polynomials) must be computable by small constant-depth circuits, and Theorem 1.2 does not appear to shine any light on such a closure result. As a consequence, the outputs of the algorithm in Theorem 1.2 are general unbounded depth circuits of polynomial size. In fact, we do not even know of non-trivial upper bounds on the size of constant-depth circuits for irreducible factors of sparse polynomials. It would be very interesting to obtain such closure results or to gather some evidence that points towards such a statement being false. Field dependence in Theorem 1.2 . Our results in Theorem 1.2 are stated over the field of rational numbers. However, the results hold a little more generally - our proofs continue to work over any underlying field over which we have an efficient deterministic algorithm for factoring univariate polynomials, over which the lower bounds of Limaye, Srinivasan & Tavenas [ LST21 ] for constant-depth circuits, the results of Andrews & Wigderson [ AW24 ] , and the Taylor-expansion-based techniques of Chou, Kumar & Solomon [ CKS19 ] continue to work. The field of rational numbers satisfies all these properties. The results also continue to hold over finite fields of moderately large characteristic (polynomially large in the degree and number of variables) since they satisfy all the properties stated above. However, for our presentation in this paper, we just work over the field of rational numbers and skip the minor technical changes needed to see the extension of the results to finite fields of moderately large characteristic. 1.2 Related prior work Following the subexponential time deterministic PIT algorithms for constant-depth algebraic circuits that follow from the lower bounds in the work of Limaye, Srinivasan & Tavenas [ LST21 ] , there has been a renewed interest in obtaining deterministic algorithms for factorization of constant-depth circuits. This includes the results of Kumar, Ramanathan & Saptharishi [ KRS23 ] , who gave a subexponential time deterministic algorithm to compute all constant-degree factors of polynomials computed by constant-depth circuits and an alternative proof as well as a generalization of this result by Dutta, Sinhababu & Thierauf [ DST24 ] . However, these results do not appear to give anything non-trivial for factors that are not low-degree. Another result that is very relevant here is a work of Kumar, Ramanathan, Saptharishi & Volk [ KRSV24 ] that gave a deterministic subexponential time algorithm that on input a constant-depth circuit outputs a list of circuits, of unbounded depth and with division gates, such that every irreducible factor of the input polynomial is computed by some circuit in this list. However, a significant drawback of this result is that the output list could contain circuits that do not correspond to any factor of the input, or aren’t even valid circuits in the sense that they involve division by a circuit that computes an identically zero polynomial. In particular, their algorithm does not imply a deterministic subexponential time algorithm for testing irreducibility of a sparse polynomial since even when the input is irreducible, the algorithm could output a collection of circuits of tentative factors. However, in this case, none of the output circuits correspond to a true factor of the input polynomial. Unfortunately, since the depth of these output circuits is potentially large (and they contain division gates), we have no deterministic way of checking if there is a polynomial in the output list that corresponds to a true factor of the input. Thus, the question of pruning the output list deterministically in [ KRSV24 ] to identify true factors is non-trivial and is essentially open. A recent work of Andrews & Wigderson [ AW24 ] gives efficient parallel algorithms (essentially constant-depth circuits) for a variety of problems related to polynomial factorization, such as GCD and LCM computation of polynomials. As a consequence of their techniques, they show that the resultant and the discriminant polynomials can be computed by constant-depth circuits of polynomial size, and the squarefree part of a polynomial with small constant-depth circuits is a small constant-depth circuit. The techniques of Andrews & Wigderson also give an alternative proof of the results in [ KRSV24 ] . However, it suffers from the same drawback as [ KRSV24 ] - some of the circuits in the output list might not correspond to any valid factors of the input, and might not even be valid circuits since they might have a division by an identically zero circuit built inside. Even though the aforementioned results represent some interesting progress towards the question of obtaining deterministic factorization of constant-depth circuits continues, it seems fair to say that the original problem has largely remained open. In particular, these results do not say anything at all about even the question of sparse irreducibility testing ( 1.1 ), which seems like a natural and possibly simpler intermediate step on the way to obtaining deterministic factorization of constant-depth circuits. Factoring of sparse polynomials has been studied for a long time and it was initiated by the work of von zur Gathen and Kaltofen almost four decades ago [ GK85 ] . This work gave the first randomized factoring algorithm for sparse polynomials, and the running time obtained was polynomial in the sparsity of the factors. Ever since this work, it has been an interesting question to obtain deterministic factoring algorithms for sparse polynomials, especially since we have known how to derandomize PIT for this class for a while. There are special cases of sparse polynomials for which we do know some results on irreducibility testing and factoring. The work of Bhargava, Saraf & Volkovich [ BSV18 ] gave a quasipolynomial time deterministic factoring algorithm for sparse polynomials where each variable has bounded degree. This extends prior works by Shpilka & Volkovich [ SV10 ] which gave deterministic factoring algorithms for multilinear sparse polynomials and Volkovich [ Vol17 ] which deterministic factoring algorithms for multiquadratic sparse polynomials. As the main result of this paper ( Theorem 1.2 ), we give a subexponential time deterministic algorithm for factorizing polynomials computable by small constant-depth circuits and, in particular, sparse polynomials (which are equivalent to depth-2 circuits). On the way to the proof, we obtain a deterministic subexponential time algorithm for testing the irreducibility of polynomials computable by small constant-depth circuits. In terms of techniques, we rely on some of the insights from prior work, e.g. [ CKS19 , KRS23 , KRSV24 , AW24 ] and introduce some new ideas on the way that might have further applications for problems of this nature. In particular, for our proofs, we crucially rely on technical observations about the structure of power series roots of polynomials with small constant-depth circuits, and their interaction with tools from hardness-vs-randomness for algebraic circuits, e.g. the Kabanets-Impagliazzo generator. As our main technical statement, we show that this generator, when invoked with a low-degree polynomial that is hard for constant-depth circuits (as constructed in [ LST21 ] ) not only preserves the non-zeroness of constant-depth circuits 4 4 4 For this, we need to assume that the circuit has undergone some initial preprocessing, which again is done using a similar generator. (as was already known), but also preserves their irreducibility (and the irreducibility of their factors). In the next section, we discuss these techniques in greater detail and give an overview of the proof of Theorem 1.2 . 2 Overview of proofs Almost all factorization algorithms proceed with some initial pre-processing to guarantee the following requirements: • P(\mathbf{x},z) is squarefree and monic in z . • We have that P({\bm{0}},0)=0 and \partial_{z}(P)({\bm{0}},0)\neq 0 . The above non-degeneracy conditions can typically be guaranteed relatively easily via a randomized algorithm. To do this deterministically, we use a recent result of Andrews & Wigderson [ AW24 ] (see Theorem 4.4 ) to get a squarefree decomposition of P . In fact, their theorem says something more that is useful for us: the squarefree parts of P are computable by a small constant-depth circuit since P is computable by a small constant-depth circuit. Moreover, we can obtain this decomposition via a deterministic subexponential time algorithm that uses the now known deterministic PIT algorithms for constant-depth circuits [ LST21 , AF22 ] . We also translate the \mathbf{x} variables appropriately (again using deterministic PIT for constant-depth circuits) to ensure that we are working with polynomials that are monic in z and each of the squarefree parts remains squarefree even when all the \mathbf{x} variables are set to zero. We then invoke a univariate factorization algorithm to find a root of P({\bm{0}},z) , which for this discussion we assume is zero. Furthermore, we replace each x_{i} with x_{i}T , for a fresh variable T , to work with a polynomial of the form P(T,\mathbf{x},z) . Note that P(0,\mathbf{x},z)\in\mathbb{F}[z] ; we will refer to such polynomials as T -regularized. 5 5 5 More generally, we say that a polynomial in \mathbb{F}[T,\mathbf{x},z] is T -regularized if every monomial with \mathbf{x} -degree at least one in the polynomial has T -degree at least one. The general plan is to use Newton iteration, starting with \varphi_{0}(T,\mathbf{x})=0 , to get “approximate roots” \varphi_{k-1}(T,\mathbf{x}) satisfying \deg_{T}(\varphi_{k-1})\deg_{T}(P) , with \deg_{T}(\varphi_{k-1})0 ) that allows us to preserve the factorization pattern of any constant-depth circuit. From this, recovering circuits (although not necessarily constant-depth) for the factors is relatively straightforward, given the known algorithms for polynomial factorization. Organization The rest of the paper is organized as follows. We begin by recalling some standard notations and preliminaries in Section 3 , and some preliminaries related to polynomial factorization in Section 4 . We describe the details of our algorithms in Section 5 , and discuss their analysis, assuming some technical results in Section 9 . We discuss the proof of these technical results in detail in Section 6 , Section 7 and Section 8 . For readers familiar with the general area of algebraic circuit complexity and some familiarity with polynomial factorization algorithms, we recommend skipping the preliminaries and going to Section 5 , and then referring to Section 3 and Section 4 as and when needed. 3 Standard preliminaries 3.1 Notation • Throughout the paper \mathbb{F} denotes a field and \mathbb{Q} denotes the field of rational numbers. • We use letters like x,y,z to refer to formal variables and letters like a,b,c as constants, as would be clear from the context. Boldface letters \mathbf{x},\mathbf{y},\mathbf{z},\mathbf{a},\mathbf{b} etc. refer to tuples of such objects. The arity of the tuple is generally specified unless it is clear from the context. • We say that a multivariate polynomial P is monic in a specific variable y if the coefficient of the highest degree monomial in y in P is a non-zero field constant. • An algebraic circuit over a field \mathbb{F} on variables \mathbf{x} is a directed acyclic graph with internal nodes being labeled by product (\times) or sum (+) , and the leaves (nodes of in-degree zero) being labeled by variables in \mathbf{x} or constants from \mathbb{F} . All the fan-ins are unbounded. Such a circuit computes a polynomial in a natural sense - a leaf computes the polynomial that is equal to its label, a sum gate computes the sums of its inputs and a product gate computes the product of its inputs. The size of an algebraic circuit equals the number of edges in it and the depth equals the length of the longest path from a leaf to an output node (a node of out-degree zero). We refer to the surveys [ SY10 , Sap15 ] for detailed discussions on algebraic circuits. • Polynomial identity testing or PIT refers to the decision problem where the input is an algebraic circuit, and the goal is to decide if the polynomial computed by the circuit is identically zero. • For a polynomial P and a variable y , \deg_{y}(P) refers to the degree of P with respect to y . Similarly, for a tuple \mathbf{x} of variables, \deg_{\mathbf{x}}(P) refers to the total degree of P with respect to variables in \mathbf{x} . 3.2 Truncation We start with the important, although non-standard definitions that are helpful in succinctly expressing our technical statements in the paper. 3.1 Polynomial truncation. For a polynomial Q(\mathbf{x})\in R[\mathbf{x}] and a positive integer k , Q\;\mathrm{trunc}\;\left\langle\mathbf{x}\right\rangle^{k} denotes the unique polynomial \tilde{Q} with \mathbf{x} -degree less than k such that \tilde{Q}\equiv Q\bmod\left\langle\mathbf{x}\right\rangle^{k} . We extend this notation to Q(T,\mathbf{x})\in\mathbb{F}[\mathbf{x}][T] (as well as power-series in \mathbb{F}[\mathbf{x}]\llbracket T\rrbracket ) and use Q\;\mathrm{trunc}\;T^{k} to denote the truncation interpreting Q(T,\mathbf{x})\in R[T] (or R\llbracket T\rrbracket ) for R=\mathbb{F}[\mathbf{x}] . While it is common to slightly overload notation and use \bmod\left\langle\mathbf{x}\right\rangle^{k} to also denote \;\mathrm{trunc}\;\left\langle\mathbf{x}\right\rangle^{k} , we choose to separate these notations for reasons of clarity. 3.3 Polynomial Identity Lemma We now recall the statement of the polynomial identity lemma. 3.2 Polynomial Identity Lemma [ Ore22 , DL78 , Sch80 , Zip79 ] . Let P be an n -variate non-zero polynomial of degree at most d over a field \mathbb{F} . And, let S be any subset of \mathbb{F} . Then, the number of zeroes of P on the product set S\times S\times\cdots\times S is at most d|S|^{n-1} . In particular, if |S|>d , then P is non-zero on at least one point on S\times S\times\cdots\times S . 3.4 Interpolation We now recall the standard interpolation lemma for extracting coefficients of univariates from their evaluations. 3.3 Interpolation (cf. [ Sap15 , Lemma 5.3] ). Let R be a commutative ring that contains a field \mathbb{F} of at least d+1 elements, and let \alpha_{0},\ldots,\alpha_{d} be distinct field elements in \mathbb{F} . Then, for each i\in\left\{0,\ldots,d\right\} , there are constants \beta_{i0},\ldots,\beta_{id}\in\mathbb{F} such that for every f(x)=f_{0}+f_{1}x+\cdots+f_{d}x^{d}\in R[x] we have f_{i}=\sum_{j=0}^{d}\beta_{ij}\cdot f(\alpha_{j}). The following corollary invokes this lemma in some of the contexts that appear in our proof. The proof is immediate from the lemma. 3.4 Standard consequences of interpolation. Let \alpha_{0},\ldots,\alpha_{d} be distinct elements in \mathbb{F} . Then, 1. [Partial derivatives] If C(\mathbf{x},y) has degree d in the variable y , then the i -th order partial derivative of C with respect to y can be expressed as an \mathbb{F}[y] -linear combination of \left\{C(\mathbf{x},\alpha_{j})\ :\ j\in\left\{0,\ldots,d\right\}\right\} . That is, there are polynomials \mu_{0}(y),\ldots,\mu_{d}(y) (not depending on C ) of degree at most d such that \partial_{y^{i}}C(\mathbf{x},y)=\mu_{0}(y)\cdot C(\mathbf{x},\alpha_{0})+\cdots+\mu_{d}(\mathbf{y})\cdot C(\mathbf{x},\alpha_{d}). 2. [Homogeneous components] Let C(\mathbf{x}) be a degree d polynomial. Then, for any subset \mathbf{x}_{S}\subseteq\mathbf{x} and any i\in[d] , the degree i homogeneous part of C with respect to \mathbf{x}_{S} , denoted by \operatorname{Hom}_{\mathbf{x}_{S},i}(C) , can be expressed as \operatorname{Hom}_{\mathbf{x}_{S},i}(C)=\sum_{j=0}^{d}\beta_{i,j}\cdot C(\alpha_{j}\cdot\mathbf{x}_{S},\mathbf{x}_{\overline{S}}) for some constants \beta_{i,j}\in\mathbb{F} (not depending on C ). 3. [Truncation] Let C(\mathbf{x}) be a degree d polynomial and let \mathbf{x}_{S}\subseteq\mathbf{x} be a subset of variables. Then, for any \ell\in[d] , the truncation C(\mathbf{x})\;\mathrm{trunc}\;\left\langle\mathbf{x}_{S}\right\rangle^{\ell+1} can be expressed as C(\mathbf{x})\;\mathrm{trunc}\;\left\langle\mathbf{x}_{S}\right\rangle^{\ell+1}=\sum_{j=0}^{d}\gamma_{\ell,j}\cdot C(\alpha_{j}\cdot\mathbf{x}_{S},\mathbf{x}_{\overline{S}}) for some constants \gamma_{\ell,j}\in\mathbb{F} (not depending on C ). In particular, if C is computable by a size s , depth \Delta circuit, then all of the above operations yield a circuit of size \operatorname{poly}(d,s) and depth \Delta+O(1) . 3.5 Strassen’s division elimination We recall a classical theorem of Strassen for division elimination in algebraic circuits. 3.5 Division elimination in algebraic circuits [ Str73 ] . Let C be an algebraic circuit of size s with division gates that computes a multivariate polynomial P of degree d over any sufficiently large field \mathbb{F} . Then, there is an algebraic circuit \hat{C} of size at most \operatorname{poly}(s,d) that computes the polynomial P and does not have any division gates. As a matter of notation, algebraic circuits throughout this paper do not have division gates. We explicitly mention if we have to deal with circuits with division gates at any point in our proof. In our proofs, we rely on the following consequence of the above theorem. The proof easily follows from the standard proof of Theorem 3.5 , for instance in [ SY10 ] . 3.6 Algorithmic division elimination. Let \mathbb{F} be any field. There is a deterministic algorithm that takes as input algebraic circuits of size at most s computing n variate polynomials A,B over \mathbb{F} , a point \mathbf{u}\in\mathbb{F}^{n} and a degree parameter d such that (a) B divides A , (b) the quotient A/B has degree at most d , and (c) B(\mathbf{u})\neq 0 , and outputs a (division free) algebraic circuit for the quotient A/B . Moreover, the algorithm runs in time \operatorname{poly}(s,d) . 3.6 Resultant and Discriminant The notion of resultant and its close connection to GCD of two univariate polynomials plays an important role in our proof (and in most polynomial factorization algorithms). We start by recalling the definition. 3.7 Sylvester Matrix and Resultant. Let \mathbb{F} be any field, and let P and Q be univariates over \mathbb{F} of degree equal to a\geq 1 and b\geq 1 respectively. Let \Gamma_{P,Q}:\mathbb{F}^{b}\times\mathbb{F}^{a}\to\mathbb{F}^{a+b} be the \mathbb{F} linear map that maps a pair (U,V) of univariates over \mathbb{F} with degree of U at most (b-1) and degree of V at most (a-1) to the polynomial (UP+VQ) of degree at most (a+b-1) . Then, the Sylvester matrix of P and Q is the (a+b)\times(a+b) matrix for the \mathbb{F} -linear map \Gamma_{P,Q} , when the inputs and the outputs are represented as their coefficient vectors. And, the Resultant of P,Q is defined as the determinant of the Sylvester Matrix of P and Q . Clearly, the entries of the Sylvester matrix as defined above are the coefficients of P and Q . In some applications in this paper, we end up invoking the notion of the resultant while working with multivariates P , Q . In these applications, we think of these multivariates as univariates in one of the variables, with the coefficients coming from the field of rational functions in the other variables. Unless otherwise clear from the context, we indicate the variable with respect to which these definitions are invoked. The resultant has a deep and extremely useful connection to the GCD of two polynomials as the following classical theorem indicates. We refer to Chapter 6 in the book [ vzGG13 ] for a proof. 3.8 Resultants and GCD [ vzGG13 , Corollary 6.20] . Let \mathcal{R} be a unique factorization domain, and let P,Q\in\mathcal{R}[z] be non-zero polynomials. Then, \deg_{z}(\gcd(P,Q))\geq 1 if and only if \operatorname{Res}_{y}(P,Q)=0 , where \gcd(P,Q)\in\mathcal{R}[z] and \operatorname{Res}_{z}(P,Q)\in\mathcal{R} . Moreover, there exist polynomials A,B\in\mathcal{R}[z] satisfying \operatorname{Res}_{z}(P,Q)=AP+BQ . A special case of the resultant that is very natural to study is when we consider the resultant of a polynomial P(z) and its derivative \frac{dP}{dz} . This resultant is referred to as the discriminant of P , and unless the derivative vanishes for trivial reasons (for instance over fields of small characteristic), the discriminant captures the squarefreeness of P . More precisely, we have the following theorem. 3.9 Discriminant and squarefreeness [ DSS22 , Lemma 12] . Let \mathbb{F} be any field of characteristic zero, and let P(z) be a univariate over \mathbb{F} of degree at least one. Then, P(z) is squarefree if and only if its discriminant \operatorname{Res}_{z}(P,\frac{\partial P}{\partial z}) is non-zero. A beautiful result of Andrews and Wigderson shows that the resultant can be computed by a constant-depth circuit. 3.10 Computing resultants via constant-depth circuits [ AW24 , Theorem 6.1] . Let \mathbb{F} be a field of characteristic zero. For a fixed \Delta\in\mathbb{N} , there is a family of depth- \Delta circuits \{C_{n}\}_{n\in\mathbb{N}} with size \leq\operatorname{poly}(n) such that the following is true. If f,g\in\mathbb{F}[z] are degree- n univariate polynomials given by their coefficients, then C_{n} takes the coefficients of f and g as input, and computes the resultant \operatorname{Res}_{z}(f,g) . 3.7 Gauss’ lemma The following basic lemma of Gauss is useful for us in our proof. 3.11 Gauss’ lemma [ vzGG13 , Section 6.2, Corollary 6.10] . Let \mathcal{R} be a unique factorization domain with the field of fractions \mathcal{K} . Then, a monic polynomial P(z) is irreducible in \mathcal{R}[z] if and only if it is irreducible in \mathcal{K}[z] . In particular, for any monic P(z) , the factorization of P(z) into its irreducible factors in \mathcal{R}[z] is identical to the factorization of P(z) into its irreducible factors in \mathcal{K}[z] . Moreover, for a monic P(z)\in\mathcal{K}[z] , its factors can also be assumed to be monic in z without loss of generality. 3.8 The Kabanets-Impagliazzo generator The Kabanets-Impagliazzo hitting set generator [ KI04 ] for algebraic circuits is an adaptation of the Nisan-Wigderson generator in classical complexity to the algebraic setting. It allows us to obtain non-trivial derandomization for PIT for algebraic circuits from sufficiently hard explicit polynomial families. More precisely, Kabanets & Impagliazzo showed in [ KI04 ] that given an explicit polynomial family that requires exponential size algebraic circuits, there is a deterministic algorithm for PIT for algebraic circuits (with size and degree polynomially bounded in the number of variables) that runs in quasipolynomial time. This generator and the details of its analysis play an important role in the proofs in this paper. We start by recalling the notion of combinatorial designs, and then define the generator. 3.12 Combinatorial designs. Let n,\sigma,\mu,\rho\in\mathbb{N} . A family of subsets \mathcal{S}=(S_{1},\dots,S_{n}) is a (n,\sigma,\mu,\rho) design if: • \forall i\in[n]:\,S_{i}\subseteq[\mu] • \forall i\in[n]:\,|S_{i}|=\sigma • For any i,j\in[n] s.t. i\neq j: |S_{i}\cap S_{j}|<\rho The following theorem gives an explicit construction of such designs. 3.13 Explicit construction of designs [ NW94 ] . For any positive integers n,\sigma with n<2^{\sigma} , there exists an explicit (n,\sigma,\mu,\rho) -design with \mu=\displaystyle\frac{\sigma^{2}}{\log n} and \rho=\log n . Moreover, each subset inside the design can be computed in \operatorname{poly}(n,2^{\mu}) time deterministically. 3.14 KI-generator \mathbf{KI}_{g,\mathcal{S}} [ KI04 ] . Let \mathbb{F} be a field, n,\sigma be positive integers with n<2^{\sigma} and g(\mathbf{x}) be a \sigma -variate polynomial. Let \mathcal{S}=(S_{1},\dots,S_{n}) be an explicit (n,\sigma,\mu,\rho) -design from Lemma 3.13 . The Kabanets-Impagliazzo generator given by g and \mathcal{S} is a polynomial map \mathbf{KI}_{g,\mathcal{S}}:\mathbb{F}^{\mu}\to\mathbb{F}^{n} defined by \mathbf{w}\mapsto(g_{1}(\mathbf{w}),\dots,g_{n}(\mathbf{w})) , where for each i\in[n] , g_{i}(\mathbf{w}):=g(\mathbf{w}_{S_{i}}) for \mathbf{w}_{S_{i}}:=\{w_{j}:j\in S_{i}\} . Thus, \mathbf{KI}_{g,\mathcal{S}} also defines a homomorphism from \mathbb{F}[x_{1},\dots,x_{n}] to \mathbb{F}[w_{1},\dots,w_{\mu}] that maps each x_{i} to g_{i}(\mathbf{w}) . 3.9 Lower bounds and PIT for constant-depth circuits We now recall the results of [ LST21 ] that prove superpolynomial lower bounds for constant-depth circuits. 3.15 Lower bounds for constant-depth circuits [ LST21 , Corollary 4] . Suppose n,d\in\mathbb{N} with d\leq\log n/100 and \mathbb{F} is a field with \operatorname{char}(\mathbb{F})=0 or greater than d . Then, for any product-depth \Delta\in\mathbb{N} , there exists an explicit n -variate polynomial P(x_{1},\dots,x_{n})\in\mathbb{F}[x_{1},\dots,x_{n}] of degree d such that any algebraic circuit of product-depth at most \Delta must have size at least n^{d^{\exp(-O(\Delta))}} . In [ CKS19 ] , it was shown that explicit low degree hard polynomials for constant-depth circuits as shown in the above theorem imply non-trivial deterministic PIT algorithms for constant-depth algebraic circuits. An alternative route to achieving the same result was shown later by Andrews & Forbes. We recall this theorem below. 3.16 Subexponential time deterministic PIT for constant-depth circuits [ LST21 , AF22 ] . Let \varepsilon>0 be a real number and \mathbb{F} a field of characteristic 0. Let C be an algebraic circuit of size s\leq\operatorname{poly}(n) and depth \Delta=o(\log\log\log n) , computing an n -variate polynomial . Then, there is a deterministic algorithm that can decide whether the polynomial computed by C is identically zero or not, in time {(s^{\Delta+1}\cdot n)^{O(n^{\varepsilon})}} . 4 Preliminaries for polynomial factorization 4.1 Regularized polynomials 4.1 T -regularized polynomials and non-degenerate, truncated, approximate z -roots of order k . Let P(T,\mathbf{x},z) be a polynomial in \mathbb{F}[T,\mathbf{x},z] that is monic in the variable z , and \Phi(T,\mathbf{x})\in\mathbb{F}[\mathbf{x}]\llbracket T\rrbracket be a power series. • \Phi(T,\mathbf{x}) is said to be an approximate z -root of order k with respect to T if P(T,\mathbf{x},\Phi(T,\mathbf{x}))\equiv 0\bmod{T^{k}}. Moreover, an approximate z -root \Phi of order k is truncated if \deg_{T}\PhiC , a(n)\leq b(n) ; the C_{\Delta,\varepsilon} in our statement is for this purpose. The precise value of C_{\Delta,\varepsilon} depends on the exact hardness of the polynomial in \mathcal{G} and the upper bounds obtained in our proofs. C_{\Delta,\varepsilon}\in\mathbb{N} , let n\in\mathbb{N},n\geq C_{\Delta,\varepsilon} and \mathbf{x}:=(x_{1},\dots,x_{n}) . Let P(T,\mathbf{x},z) be a nonzero polynomial with the following properties. • P(T,\mathbf{x},z) is computable by a size s\leq\operatorname{poly}(n) and depth \Delta circuit. • P(T,\mathbf{x},z) is monic in z and T -regularized, with \deg(P)=D\leq\operatorname{poly}(n) . • P(T,\mathbf{x},z) and P(0,\mathbf{x},z)=P(0,{\bm{0}},z) are squarefree. Let \sigma=O(n^{\varepsilon}),\mu=O(\frac{n^{2\varepsilon}}{\log(n)}),\rho=O(\log(n)) , and let \mathcal{S} be an (n,\sigma,\mu,\rho) -design. Let \mathbf{KI}_{g_{\sigma},\mathcal{S}}:\mathbb{F}^{\mu}\to\mathbb{F}^{n} be the polynomial map in 3.14 defined using the design \mathcal{S} and the polynomial g_{\sigma} from the family of hard polynomials \mathcal{G} . Then, the following is true. A polynomial F(T,\mathbf{x},z) is an irreducible factor of P(T,\mathbf{x},z) if and only if F(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}),z) is an irreducible factor of P(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}),z) . A few remarks regarding the choice of parameters in Theorem 5.1 : • The family \mathcal{G} has degree d_{m}\leq O(\log\log(m)) so that (\log(m))^{\operatorname{poly}(d_{m})} is \operatorname{poly}(m) . We can work with any d_{m}\leq O((\log m)^{\alpha}) for some small enough \alpha depending on the exponent in \operatorname{poly}(d_{m}) , but \log\log(m) works in every case and makes it simpler to state the theorems. • The design \mathcal{S} has \sigma=O(n^{\varepsilon}) because \mathcal{G} is guaranteed to be superpolynomially hard for constant-depth circuits. Stronger hardness guarantees can be used with smaller \sigma to get algorithms with better time complexity, as is usually the case in hardness-vs-randomness results. We now describe our main algorithmic result. Informally, the result states that for every choice of depth \Delta\in\mathbb{N} , there is a deterministic algorithm \mathcal{A}_{\Delta} such that \mathcal{A}_{\Delta} takes a depth- \Delta circuit for a polynomial P as input, and outputs small (but unbounded depth) circuits along with multiplicity information for each irreducible factor of P . Moreover, \mathcal{A}_{\Delta} runs in time subexponential in the input size. 5.2 Deterministic subexponential time algorithm for factorization of constant-depth circuits. Fix any \Delta\in\mathbb{N} and \varepsilon\in(0,0.5) . There exists an algorithm \mathcal{A}_{\Delta,\varepsilon} which, for all sufficiently large n , • takes as input a polynomial P(\mathbf{x})\in\mathbb{Q}[x_{1},\dots,x_{n}] of degree D\leq\operatorname{poly}(n) with a depth- \Delta , size s\leq\operatorname{poly}(n) circuit; • outputs \operatorname{poly}(s,D) -sized circuits for each irreducible factor of P , along with the multiplicity of each such factor; and • runs in time \operatorname{poly}(s,D)^{O(n^{2\varepsilon})} . 5.1.1 High-level overview of the algorithm 1. Suppose P(\mathbf{x}) is the polynomial that we would like to factor. We first use the algorithm by Andrews and Wigderson ( Theorem 4.4 ) to compute the squarefree decomposition of P . Now, we deal with each squarefree part separately. 2. For a specific squarefree part P_{r}(\mathbf{x}) , we perform some of the standard transformations ( x_{i}\mapsto T\cdot x_{i}+a_{i}\cdot z+b_{i} ) so that the polynomial P_{r}(T,\mathbf{x},z) is monic in z variable, T -regularized, and P_{r}(0,\mathbf{x},z)=P_{r}(0,{\bm{0}},z) is squarefree. 3. We apply \mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}) on P_{r}(T,\mathbf{x},z) (instantiated with an appropriately chosen low-degree hard polynomial g and a design \mathcal{S}) . This maintains the irreducibility of each factor ( Theorem 5.1 ). At this point, we are working with an n^{\varepsilon} -variate polynomial for some \varepsilon\in(0,1) . Thus, we can use a brute-force / dense-representation factorization algorithm to factorize P_{r}(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) in subexponential time ( Theorem 4.12 ). 4. Since P_{r}(0,\mathbf{x},z)=P_{r}(0,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z)=P_{r}(0,{\bm{0}},z) , taking an irreducible factor of P_{r}(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) and setting T to 0 precisely tells us G(0,\mathbf{x},z) for each irreducible factor G(T,\mathbf{x},z) of P_{r}(T,\mathbf{x},z) . Thus, we now have G(0,\mathbf{x},z)=G(0,{\bm{0}},z) for each G that is an irreducible factor of P , and we can deal with each G separately. 7 7 7 At this point, with the right univariate projections G(0,{\bm{0}},z) for each irreducible factor G(T,\mathbf{x},z) , one way to get the irreducible factors is to perform Hensel lifting (for instance, see [ Sud98 , Lecture 7] or [ ST20 ] ). While Hensel lifting usually ends with a reconstruction step that involves solving a linear system, the clean-up for us would just be a truncation since Hensel lifting guarantees that if we start off with the right univariate projection, we will retrieve the right factor, modulo higher degree terms that might have accumulated in the process. 5. Suppose G(T,\mathbf{x},z) is an irreducible factor, and we have access to the univariate G(0,\mathbf{x},z)=G(0,{\bm{0}},z) . We factorize G(0,{\bm{0}},z) using Theorem 4.11 . G(0,{\bm{0}},z) could have a linear factor of the form (z-\alpha) ; in this case, we use Newton iteration ( Corollary 4.6 ) to lift the root \alpha to a truncated, approximate z -root \varphi(T,\mathbf{x}) of P(T,\mathbf{x},z) of sufficiently high accuracy. But all the factors of G(0,{\bm{0}},z) might be non-linear. In this situation, we artificially add a root u of G(0,{\bm{0}},z) to the field; more precisely, if H(z) is an arbitrary irreducible factor of G(0,{\bm{0}},z) , we work over the field \frac{\mathbb{Q}[u]}{H(u)} so that u is now a root of G(0,{\bm{0}},z) . We can efficiently simulate arithmetic in this field. Thus, we can lift the root u to a truncated, approximate z -root \varphi(T,\mathbf{x}) of P(T,\mathbf{x},z) of sufficiently high accuracy. 6. ( Lemma 9.1 ) Given a truncated, approximate z -root \varphi of P(T,\mathbf{x},z) , we set up a linear system whose solution will give us a minimal polynomial of the root \varphi . Since we know G(0,\mathbf{x},z) , we know the z -degree of G ; this is essentially the information we need to set up the linear system in a way that ensures that the solution is the same as the irreducible factor G . 7. ( Theorem 9.2 ) The solution to the linear system can be represented as a small circuit using Cramer’s rule, but this involves a division by a determinant. We shall now use Strassen’s division elimination to represent the solution as an arithmetic circuit without division gates; this requires a point where the denominator evaluates to a nonzero value. To this end, we again compose the denominator with \mathbf{KI}_{g,\mathcal{S}} to get an n^{\varepsilon} -variate polynomial; since this denominator essentially captures the uniqueness of the minimal polynomial, we can prove that \mathbf{KI}_{g,\mathcal{S}} , by maintaining irreducibility of factors, also maintains the non-zeroness of the denominator. We can now use a brute-force derandomization of the Polynomial Identity Lemma to find a point where the denominator evaluates to a nonzero value, and hence, carry out Strassen’s division elimination. Thus, we have division-free circuits for each irreducible factor G(T,\mathbf{x},z) of P(T,\mathbf{x},z) . 8. Finally, we can undo our initial transformations and output circuits for the irreducible factors of the input polynomial P(\mathbf{x}) , along with their multiplicities. 5.2 The algorithm Fix any \Delta\in\mathbb{N} and \varepsilon\in(0,0.5) . The following algorithm is the “outermost” wrapper for our complete algorithm, and it can be thought of as the algorithm \mathcal{A}_{\Delta,\varepsilon} in Theorem 5.2 . The algorithm computes the squarefree decomposition of the input polynomial, and then uses Algorithm 2 on each squarefree part of the decomposition. Algorithm 1 All factors of depth- \Delta circuits, parameter \varepsilon\in(0,0.5) Input : A depth- \Delta circuit C_{P}(\mathbf{x}) of size s\in\mathbb{N} , computing a degree- D polynomial P(\mathbf{x})=\prod_{i=1}^{m}G_{i}(\mathbf{x})^{e_{i}}\in\mathbb{Q}[\mathbf{x}] , where \mathbf{x}=(x_{1},\dots,x_{n}) . Output : A list L=\{(C_{G_{1}}(\mathbf{x}),e_{1}),\dots,(C_{G_{m}}(\mathbf{x}),e_{m})\} , such that each C_{G_{i}}(\mathbf{x}) is a circuit of size \operatorname{poly}(s,D) and depth \operatorname{poly}(D) , which computes the irreducible factor G_{i}(\mathbf{x}) , and e_{i} is the multiplicity of G_{i} in P . 1 Run Andrews-Wigderson ( Theorem 4.4 ) on C_{P}(\mathbf{x}) to get circuits C_{P_{1}}(\mathbf{x}),\dots,C_{P_{r}}(\mathbf{x}) of depth \Delta^{\prime}=\Delta+O(1) , computing P_{1}(\mathbf{x}),\dots,P_{r}(\mathbf{x}) where r=\max_{i\in[m]}e_{i} and P_{i}(\mathbf{x})=\prod_{j\in S_{i}}G_{j}(\mathbf{x}) for S_{i}=\{j\in[m]:e_{j}=i\} 2 Initialize L\leftarrow\emptyset 3 forall i\in[r] do 4 Run Algorithm 2 for parameters \Delta^{\prime} and \varepsilon on C_{P_{i}}(\mathbf{x}) to get a list L_{i}:=\{C_{G_{j}}(\mathbf{x}):j\in S_{i}\} 5 For each C_{G_{j}}(\mathbf{x})\in L_{i} , add (C_{G_{j}}(\mathbf{x}),i) to L . 6 return L . 5.3 Algorithm for factors of squarefree polynomials In this section, we will describe the algorithm for steps 3 and 4 of the overview in Section 5.1.1 . Fix any \Delta\in\mathbb{N} . Let \mathcal{G}=\{g_{m}\}_{m\in\mathbb{N}} be a family of polynomials such that for every m\in\mathbb{N} , g_{m}\in\mathbb{F}[x_{1},\dots,x_{m}] , d_{m}:=\deg(g_{m})\leq O(\log\log(m)) . Further, \mathcal{G} has the property that for any depth \Delta\in\mathbb{N} , if \mathcal{C}=\{C_{m}\}_{m\in\mathbb{N}} is a family of depth- \Delta circuits computing \mathcal{G} , then \mathcal{C} requires size m^{d_{m}^{\exp(-O(\Delta))}} , which is m^{\omega(1)} . Theorem 3.15 gives us such a family of explicit low-degree polynomials that are hard for constant-depth circuits. Let \varepsilon\in(0,0.5) . Let \sigma=O(n^{\varepsilon}),\mu=O(\frac{n^{2\varepsilon}}{\log(n)}),\rho=O(\log(n)) , and let \mathcal{S} be an (n,\sigma,\mu,\rho) -design. Let \mathbf{KI}_{g_{\sigma},\mathcal{S}}:\mathbb{F}^{\mu}\to\mathbb{F}^{n} be the polynomial map in 3.14 defined using the design \mathcal{S} and the polynomial g_{\sigma} from the family of hard polynomials \mathcal{G} . Algorithm 2 Factors of squarefree polynomial with depth- \Delta circuits, parameter \varepsilon\in(0,0.5) Input : A depth- \Delta size- s circuit C_{P} computing the squarefree degree- D polynomial P(\mathbf{x})=\prod_{j\in[m]}G_{j}(\mathbf{x}) , where the G_{j} s are the irreducible factors of P . Output : A list L=\{C_{G_{1}}(\mathbf{x}),\dots,C_{G_{m}}(\mathbf{x})\} , such that each C_{G_{j}}(\mathbf{x}) is a circuit of size \operatorname{poly}(s,D) and depth \operatorname{poly}(D) , which computes the irreducible factor G_{j}(\mathbf{x}) . 1 Compute \mathbf{a}\in\mathbb{Q}^{n} such that \delta=\operatorname{Hom}_{D}[P](\mathbf{a})\neq 0 using Theorem 3.16 . Let \hat{P}(\mathbf{x},z):=P(\mathbf{x}+(\mathbf{a}\cdot z))/\delta and for each j\in[m] , \hat{G_{j}}(T,\mathbf{x},z):={G_{j}}(\mathbf{x}+(\mathbf{a}\cdot z))/\operatorname{Hom}_{\deg(G_{j})}[G_{j}](\mathbf{a}) // Ensures that \hat{P} is monic in z 2 Compute \mathbf{b}\in\mathbb{Q}^{n} such that \operatorname{Disc}_{z}(\hat{P})(\mathbf{b})\neq 0 using Theorem 3.16 . Let \tilde{P}(T,\mathbf{x},z):=\hat{P}((T\cdot\mathbf{x})+\mathbf{b},z) and for each j\in[m] , \tilde{G_{j}}(T,\mathbf{x},z):=\hat{G_{j}}((T\cdot\mathbf{x})+\mathbf{b},z) // Ensures that \tilde{P}(T,\mathbf{x},z) is T -regularised, and P(0,{\bm{0}},z) is squarefree. 3 Construct the map \mathbf{KI}_{g_{\sigma},\mathcal{S}} using Lemma 3.13 and g_{\sigma}\in\mathcal{G} as given by Theorem 3.15 . 4 Factorize C_{\tilde{P}}(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) so that for each j\in[m] , C_{\tilde{G}_{j}}(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) is a circuit that computes \tilde{G}_{j}(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) , satisfying the property that \tilde{G}_{j}(0,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z)=\tilde{G}_{j}(0,{\bm{0}},z) . 5 Run Algorithm 3 with parameters \Delta+2 and \varepsilon on C_{\tilde{P}}(T,\mathbf{x},z) and \{\tilde{G}_{j}(0,{\bm{0}},z):j\in[m]\} to get a list L^{\prime}=\{C_{\tilde{G}_{1}}(T,\mathbf{x},z),\dots,C_{\tilde{G}_{m}}(T,\mathbf{x},z)\} . 6 For each C_{\tilde{G}_{j}}(T,\mathbf{x},z)\in L^{\prime} , compute C_{G_{j}}(\mathbf{x}):=C_{\tilde{G}_{j}}(1,\mathbf{x}-\mathbf{b},0) . 7 Output L=\{C_{G_{1}}(\mathbf{x}),\dots,C_{G_{m}}(\mathbf{x})\} 5.4 Algorithm for obtaining irreducible factors from the right univariate projections In this section, we describe the algorithm for steps 5-7 of the overview in Section 5.1.1 . Fix any \Delta\in\mathbb{N} and \varepsilon\in(0,0.5) . Algorithm 3 Factors of monic, T -regularized, squarefree polynomial with depth- \Delta circuit, parameter \varepsilon\in(0,0.5) Input : • A depth- \Delta size- s circuit C_{\tilde{P}} computing a squarefree degree- D polynomial \tilde{P}(T,\mathbf{x},z)=\prod_{j\in[m]}\tilde{G}_{j}(T,\mathbf{x},z) , where the \tilde{G}_{i} s are the irreducible factors of \tilde{P} . Further, \tilde{P}(T,\mathbf{x},z) is monic in z , T -regularized with respect to \mathbf{x} and C_{\tilde{P}}(0,\mathbf{x},z)=C_{\tilde{P}}(0,{\bm{0}},z) is squarefree. • For each j\in[m] , the univariate polynomial \tilde{G}_{j}(0,\mathbf{x},z)=\tilde{G}_{j}(0,{\bm{0}},z) . Output : A list L=\{C_{\tilde{G}_{1}}(T,\mathbf{x},z),\dots,C_{\tilde{G}_{m}}(T,\mathbf{x},z)\} , such that each C_{\tilde{G}_{i}}(T,\mathbf{x},z) is a circuit of size \operatorname{poly}(s,D) and depth \operatorname{poly}(D) , which computes the irreducible factor \tilde{G}_{i}(T,\mathbf{x},z) of \tilde{P}(T,\mathbf{x},z) . Prerequisites : \mathbf{KI}_{g_{\sigma},\mathcal{G}} constructed in Algorithm 2 using Lemma 3.13 and Theorem 3.15 1 Initialize L\leftarrow\emptyset 2 forall j\in[m] do 3 Factorize the degree- D_{z} polynomial \tilde{G}_{j}(0,{\bm{0}},z) ( Theorem 4.11 ) to get \tilde{G}_{j}(0,{\bm{0}},z)=\prod_{l=1}^{r_{j}}H_{l}(z) , where every H_{l}(z) is distinct, monic and irreducible. 4 Let H(z) be an arbitrary irreducible factor of \tilde{G}_{j}(0,{\bm{0}},z) . Let \mathbb{K} be the field \frac{\mathbb{Q}[u]}{H(u)} . 5 Use Newton iteration ( Lemma 4.5 ) to compute a truncated, non-degenerate, approximate z -root \varphi(T,\mathbf{x})\in\mathbb{K}[T,\mathbf{x}] of \tilde{G}_{j}(T,\mathbf{x},z) of order 2D\cdot D_{z}+1 such that \varphi(0,\mathbf{x})=\varphi(0,{\bm{0}})=u\in\mathbb{K} . 6 Use the algorithm from Theorem 9.2 (with \mathbf{KI}_{g_{\sigma},\mathcal{G}} ) on \varphi(T,\mathbf{x}) to compute a circuit C_{\tilde{G_{j}}} for \tilde{G_{j}} . 7 Add C_{\tilde{G_{j}}} to L . 8 return L 6 Technical building blocks 6.1 Properties of roots modulo T^{k} The following lemma observes that certain homomorphisms defined by polynomial maps preserve approximate roots for a polynomial. This will be used to argue that an approximate root remains an approximate root (with some nice properties) even after we plug in the Kabanets-Impagliazzo generator. 6.1 Preserving root properties under homomorphisms. Let k>1 be any natural number and let P(T,\mathbf{x},z)\in\mathbb{F}[T,\mathbf{x},z] and R(T,\mathbf{x})\in\mathbb{F}[T,\mathbf{x}] be polynomials satisfying the following properties. • P(T,\mathbf{x},z) is T -regularized and it is monic in z . • R(T,\mathbf{x}) is a truncated, non-degenerate, approximate z -root of P(T,\mathbf{x},y) of order k . For a new tuple \mathbf{w} of \mu variables distinct from T,\mathbf{x},z , polynomials h_{1},h_{2},\ldots,h_{n}\in\mathbb{F}[\mathbf{w}] and a non-zero field constant \gamma\in\mathbb{F} , let \Lambda:\mathbb{F}[T,\mathbf{x},z]\to\mathbb{F}[T,\mathbf{w},z] be the ring homomorphism defined by T\mapsto\gamma T , x_{i}\mapsto h_{i}(\mathbf{w}) and z\mapsto z . Then, the following are true. • \Lambda(R)(0,\mathbf{w})=R(0,\mathbf{x})\in\mathbb{F} • \Lambda(P)(T,\mathbf{w},z) is T -regularized, and it is monic in z . • \Lambda(R)(T,\mathbf{w}) is a truncated, non-degenerate, approximate z -root of \Lambda(P)(T,\mathbf{w},y) of order k Proof. The lemma follows essentially because \Lambda is a homomorphism. 1. By 4.2 , R(0,\mathbf{x})\in\mathbb{F} . Since \Lambda is a homomorphism with the property that \deg_{T}(f)=\deg_{T}(\Lambda(f)) for any f\in\mathbb{F}[T,\mathbf{x},z] , it follows that \Lambda(R)(0,\mathbf{w})=R(0,\mathbf{x}) . 2. If a monomial \mathbf{m}\in\mathbb{F}[T,\mathbf{x},z] , is T -regularized, then so is \Lambda(\mathbf{m}) . Since \Lambda is a homomorphism, this property extends to all polynomials. Similarly, since \Lambda(z)=z , \Lambda(P) remains monic in z . 3. P(T,\mathbf{x},R(T,\mathbf{x}))\equiv 0\mod T^{k} , or equivalently, every monomial in P(T,\mathbf{x},R(T,\mathbf{x})) has T -degree at least k . As observed in the first point, \Lambda is a homomorphism with the property that \deg_{T}(f)=\deg_{T}(\Lambda(f)) for any f\in\mathbb{F}[T,\mathbf{x},z] . Thus, \Lambda(P)(T,\mathbf{w},\Lambda(R)(T,\mathbf{w}))\equiv 0\mod T^{k} . ∎ The following lemma observes that truncated, non-degenerate, approximate roots of a polynomial are unique once the value of the root at T=0 is decided; it follows almost immediately from the uniqueness of approximate roots computed via Newton iteration. 6.2 Uniqueness of truncated, non-degenerate, approximate roots. Let k\in\mathbb{N} . Suppose \Psi_{1}(T,\mathbf{x}) and \Psi_{2}(T,\mathbf{x}) are truncated, non-degenerate, approximate z -roots of order k with respect to T for a T -regularized polynomial P(T,\mathbf{x},z) . If \Psi_{1}(0,\mathbf{x})=\Psi_{2}(0,\mathbf{x})=\alpha\in\mathbb{F} , then \Psi_{1}(T,\mathbf{x})\equiv\Psi_{2}(T,\mathbf{x}) . Proof. Since \Psi_{1}(T,\mathbf{x}) is a non-degenerate root of P(T,\mathbf{x},z) which is T -regularized, \frac{\partial P}{\partial z}(0,\mathbf{x},\Psi_{1}(0,\mathbf{x}))=\frac{\partial P}{\partial z}(0,\mathbf{x},\Psi_{1}(0,\mathbf{x}))=\frac{\partial P}{\partial z}(0,{\bm{0}},\alpha)=\beta\in\mathbb{F} is nonzero. Similarly, \frac{\partial P}{\partial z}(0,\mathbf{x},\Psi_{2}(0,\mathbf{x}))=\frac{\partial P}{\partial z}(0,\mathbf{x},\Psi_{2}(0,\mathbf{x}))=\frac{\partial P}{\partial z}(0,{\bm{0}},\alpha)=\beta . Since \alpha satisfies P(T,\mathbf{x},\alpha)\equiv 0\bmod T and \frac{\partial P}{\partial z}(0,\mathbf{x},\alpha)=\beta\in\mathbb{F} for \beta\neq 0 , Lemma 4.5 tells us that there is a unique truncated, approximate z -root \Phi(T,\mathbf{x}) of order k for P(T,\mathbf{x},z) , satisfying \Phi(0,\mathbf{x})=\alpha . Thus, \Phi(T,\mathbf{x})\equiv\Psi_{1}(T,\mathbf{x})\equiv\Psi_{2}(T,\mathbf{x}) . ∎ 6.2 Complexity of low degree homogeneous components of roots The following is our main technical lemma where we argue that the low-degree homogeneous components of an approximate root for a constant-depth circuit can be computed by a small constant-depth circuit. 6.3 . Let k>1 be any natural number and let P(T,\mathbf{w},z)\in\mathbb{F}[T,\mathbf{w},z] and R(T,\mathbf{w})\in\mathbb{F}[T,\mathbf{w}] be polynomials satisfying the following properties. • P(T,\mathbf{w},z) is computable by a depth \Delta circuit of size s . • P(T,\mathbf{w},z) is T -regularized and monic in z . • R(T,\mathbf{w}) is a truncated, non-degenerate, approximate z -root of P(T,\mathbf{x},z) of order k with respect to T . Then, for every \ell\in\mathbb{N} , there is an algebraic circuit C_{\ell}\in\mathbb{F}[T,\mathbf{w}] of depth at most (\Delta+O(1)) , size at most \left(\operatorname{poly}(s,\deg(P))\cdot(\log k)^{\operatorname{poly}(\ell)}\right) C_{\ell}(T,\mathbf{w})=R(T,\mathbf{w})\;\mathrm{trunc}\;\langle\mathbf{w}\rangle^{\ell}\,. Proof. As seen in 4.2 , R(0,\mathbf{w}) is a root of P(0,\mathbf{0},z) , and hence must be a field element \alpha (possibly from an extension of \mathbb{F} ) and does not depend on \mathbf{w} . Similarly, we also get that \frac{\partial P}{\partial z}\left(0,\mathbf{w},R(0,\mathbf{w})\right) is a non-zero field element that we denote by \beta . Thus, R(T,\mathbf{w}) is the unique lift of the root \alpha of P(T,\mathbf{w},z) modulo T to a root modulo the ideal T^{k} ( Lemma 6.2 ). In particular, we can view R as an outcome of Newton Iteration (and then eventual truncation modulo T^{k} ). We prove the lemma by induction on this iteration, and maintaining the following inductive claim. Let 2^{m}\in[k,2k] be the smallest power of 2 greater than k . From 4.8 , we get that the sequence of polynomials \varphi_{0},\varphi_{1},\ldots,\varphi_{m},\psi_{0},\psi_{1},\ldots,\psi_{m}\in\mathbb{F}[T,\mathbf{w}] defined as \displaystyle\varphi_{0} \displaystyle=\alpha, \displaystyle\psi_{0} \displaystyle=(1/\beta), \displaystyle\text{For $i\geq 0$,}\quad\varphi_{i+1} \displaystyle=\varphi_{i}-P(T,\mathbf{w},\varphi_{i})\cdot\psi_{i}, \displaystyle\psi_{i+1} \displaystyle=2\psi_{i}-\psi_{i}^{2}\cdot\frac{\partial P}{\partial z}(T,\mathbf{w},\varphi_{i+1}). satisfy R(T,\mathbf{w})=\varphi_{m}(T,\mathbf{w})\;\mathrm{trunc}\;T^{k}\,. We note that while we are dealing with polynomials in both T and \mathbf{w} variables, the lifting is happening only with respect to T . In this sense, we are really viewing the polynomial P(T,\mathbf{w},z) as a polynomial in \mathbb{F}[\mathbf{w}][T,z] for the purpose of this lifting. We now use the following claim, whose proof we defer to the end of this section, to complete the proof of the lemma. 6.4 . For every i\geq 0 , there exists a set \mathcal{G}_{i} of at most \tau_{i}\leq 2(\ell+1)i polynomials \{g_{1},g_{2},\ldots,g_{\tau_{i}}\} in \mathbb{F}[T,\mathbf{w}] and two (\tau_{i}+1) -variate polynomials Q_{i}(T,u_{1},\ldots,u_{\tau_{i}}),\hat{Q}_{i}(T,u_{1},\ldots,u_{\tau_{i}})\in\mathbb{F}[T,\mathbf{u}] such that \varphi_{i}\equiv Q_{i}(T,g_{1},\ldots,g_{\tau_{i}})\mod\langle\mathbf{w}\rangle^{\ell}\,, and \psi_{i}\equiv\hat{Q}_{i}(T,g_{1},\ldots,g_{\tau_{i}})\mod\langle\mathbf{w}\rangle^{\ell}\,. Moreover, each polynomial g in \mathcal{G}_{i} is of the form \frac{\partial P}{\partial z^{j}}(T,\mathbf{w},\gamma) for some j\leq(\ell+1) and \gamma\in\mathbb{F}[T] . From the fact that R(T,\mathbf{w})=\varphi_{m}(T,\mathbf{w})\;\mathrm{trunc}\;T^{k} , we get that R(T,\mathbf{w})\;\mathrm{trunc}\;\left\langle\mathbf{w}\right\rangle^{\ell}=\left(\varphi_{m}(T,\mathbf{w})\;\mathrm{trunc}\;T^{k}\right)\;\mathrm{trunc}\;\langle\mathbf{w}\rangle^{\ell}\,. Now, since T and \mathbf{w} are disjoint variables, we can exchange the order of the operations of truncating modulo T and truncating modulo \langle\mathbf{w}\rangle^{\ell} . So, we have that R(T,\mathbf{w})\;\mathrm{trunc}\;\left\langle\mathbf{w}\right\rangle^{\ell}=\left(\varphi_{m}(T,\mathbf{w})\;\mathrm{trunc}\;\langle\mathbf{w}\rangle^{\ell}\right)\;\mathrm{trunc}\;T^{k}\,. From 6.4 , we get that R(T,\mathbf{w})\;\mathrm{trunc}\;\left\langle\mathbf{w}\right\rangle^{\ell}=\left(Q_{m}(T,g_{1},g_{2},\ldots,g_{\tau_{m}})\;\mathrm{trunc}\;\langle\mathbf{w}\rangle^{\ell}\right)\;\mathrm{trunc}\;T^{k}\,. We would like to show that the RHS of the above equation has a small constant-depth circuit. Since we eventually truncate to T -degree k-1 , we can assume without loss of generality that the T -degree of Q_{m} and each g_{i} is at most k-1 . In particular, if g_{i} equals \frac{\partial P}{\partial z^{j}}(T,\mathbf{w},\gamma) for some j\in\mathbb{N} and \gamma\in\mathbb{F}[T] , this \gamma can be assumed to be of T -degree at most (k-1) . Moreover, since P(T,\mathbf{w},z) is a polynomial with a depth- \Delta circuit of size s , we get, from Corollary 3.4 that \frac{\partial P}{\partial z^{j}}(T,\mathbf{w},z) has a depth (\Delta+O(1)) circuit of size at most s\cdot\operatorname{poly}(\deg(P)) . From the bound on the degree of \gamma\in\mathbb{F}[T] , we get that each g_{i}(T,\mathbf{w}) has a depth (\Delta+O(1)) circuit of size at most s\cdot\operatorname{poly}(\deg(P)) . Finally, we note that we can view Q_{m}(T,g_{1},g_{2},\ldots,g_{\tau_{m}}) as \tilde{Q}_{m}(T,g_{1}(T,\mathbf{w})-g_{1}(T,\mathbf{0}),g_{2}(T,\mathbf{w})-g_{2}(T,\mathbf{0}),\ldots,g_{\tau_{m}}(T,\mathbf{w})-g_{\tau_{m}}(T,\mathbf{0})), for some polynomial \tilde{Q}_{m} . Since we are only interested in working with the above polynomial modulo \langle\mathbf{w}\rangle^{\ell} and every monomial in each of the polynomials g_{j}(T,\mathbf{w})-g_{j}(T,\mathbf{0}) has \mathbf{w} -degree at least one, we get that \tilde{Q}_{m}(T,u_{1},\ldots,u_{\tau_{m}}) can be assumed to have degree at most \ell in the \mathbf{u} variables. Thus, \tilde{Q}_{m}(T,u_{1},\ldots,u_{\tau_{m}}) can be computed by a depth- 2 circuit of size at most k\cdot\binom{\tau_{m}+\ell}{\ell}\leq k\cdot(\log k)^{\operatorname{poly}(\ell)} . Combining this circuit with the constant-depth circuits for g_{j}(T,\mathbf{w}) (and hence g_{j}(T,\mathbf{w})-g_{j}(T,\mathbf{0}) ) gives us a depth- (\Delta+O(1)) circuit \tilde{C} of size at most \operatorname{poly}(s,\deg(P))\cdot(\log k)^{\operatorname{poly}(\ell)} satisfying \tilde{C}(T,\mathbf{w})\equiv Q_{m}(T,g_{1},\dots,g_{\tau_{m}})\bmod T^{k}\bmod\left\langle\mathbf{w}\right\rangle^{\ell+1}. The T -degree of this circuit is at most \deg_{T}(\tilde{Q}_{m})\cdot\ell\cdot k\leq\operatorname{poly}(k,\ell) . The \mathbf{w} -degree of this circuit is at most \ell\cdot\deg(P) . Thus, we can apply the operations \;\mathrm{trunc}\;\left\langle\mathbf{w}\right\rangle^{\ell+1} and \;\mathrm{trunc}\;T^{k} by an application of Corollary 3.4 to get the circuit C_{\ell}(T,\mathbf{w}) in the conclusion of the lemma. ∎ We now discuss the proof of 6.4 . Proof of 6.4 . We prove the claim via an induction on i . For i=0 , we already know that \varphi_{0}=\alpha and \psi_{0}=\frac{1}{\beta} are polynomials in \mathbb{F}[T] and hence the claim immediately holds. We now assume that the claim holds for \varphi_{i} and \psi_{i} i.e. \varphi_{i}\equiv Q_{i}(T,g_{1},\ldots,g_{\tau_{i}})\mod\langle\mathbf{w}\rangle^{\ell}\,, and \psi_{i}\equiv\hat{Q}_{i}(T,g_{1},\ldots,g_{\tau_{i}})\mod\langle\mathbf{w}\rangle^{\ell} and show that it must hold for \varphi_{i+1} and \psi_{i+1} . From the inductive definitions of \varphi_{i+1} and \psi_{i+1} , we get that \varphi_{i+1}\equiv\varphi_{i}-P(T,\mathbf{w},\varphi_{i})\cdot\psi_{i} and \psi_{i+1}\equiv 2\psi_{i}-\psi_{i}^{2}\cdot\frac{\partial P}{\partial z}(T,\mathbf{w},\varphi_{i+1}) If \gamma_{i}:=\varphi_{i}(T,\mathbf{0}) , i.e. \gamma_{i} is the \mathbf{w} -free part of \varphi_{i} , we get via a Taylor expansion that P(T,\mathbf{w},{\varphi}_{i})=P(T,\mathbf{w},\gamma_{i}+({\varphi}_{i}-\gamma_{i}))=\sum_{j=0}^{\deg(P)}\frac{1}{j!}\cdot\frac{\partial P}{\partial z^{j}}(T,\mathbf{w},\gamma_{i})\cdot({\varphi}_{i}-\gamma_{i})^{j}\,. (6.5) From the definition of \gamma_{i} , we have that every monomial in ({\varphi}_{i}-\gamma_{i}) has \mathbf{w} -degree at least one. Thus, for every j\geq\ell , we have that ({\varphi}_{i}-\gamma_{i})^{j}\equiv 0 modulo \langle\mathbf{w}\rangle^{\ell} . Thus, we have that P(T,\mathbf{w},{\varphi}_{i})\equiv\sum_{j=0}^{\ell}\frac{1}{j!}\cdot\frac{\partial P}{\partial z^{j}}(T,\mathbf{w},\gamma_{i})\cdot({\varphi}_{i}-\gamma_{i})^{j}\mod\langle\mathbf{w}\rangle^{\ell}\,. Similarly, \frac{\partial{P}}{\partial z}(T,\mathbf{w},{\varphi}_{i+1})\equiv\sum_{j=0}^{\ell}\frac{1}{j!}\cdot\frac{\partial P}{\partial z^{j+1}}(T,\mathbf{w},\gamma_{i+1})\cdot({\varphi}_{i+1}-\gamma_{i+1})^{j}\mod\langle\mathbf{w}\rangle^{\ell}\,. Thus, \varphi_{i+1} can be written as a polynomial in Q_{i},\hat{Q}_{i} and polynomials in the set \{\frac{\partial P}{\partial z^{j}}(T,\mathbf{w},\gamma_{i}):j\in\{0,1,\ldots,\ell\}\} , where the coefficients of this polynomial are from the ring \mathbb{F}[T] and all equalities hold modulo \langle\mathbf{w}\rangle^{\ell} . Similarly, \psi_{i+1} can be written as a polynomial in Q_{i+1},\hat{Q}_{i} and polynomials in the set \{\frac{\partial P}{\partial z^{j}}(T,\mathbf{w},\gamma_{i+1}):j\in\{1,2,\ldots,\ell+1\}\} , where the coefficients of this polynomial are from the ring \mathbb{F}[T] and all equalities hold modulo \langle\mathbf{w}\rangle^{\ell} . Moreover, in going from i to (i+1) , we have increased the size of the generating set additively by at most 2(\ell+1) . Furthermore, each of the new elements of this generating set is again of the form \frac{\partial P}{\partial z^{j}}(T,\mathbf{w},\gamma) for some j\leq(\ell+1) and \gamma\in\mathbb{F}[T] . ∎ An immediate consequence of 6.3 is the following corollary. 6.6 . Let k\in\mathbb{N} , P(T,\mathbf{w},z)\in\mathbb{F}[T,\mathbf{w},z] and R(T,\mathbf{w})\in\mathbb{F}[T,\mathbf{w}] be polynomials that satisfy the hypothesis of 6.3 . Then, for every \ell\in\mathbb{N} , there is an algebraic circuit {C}_{\ell}\in\mathbb{F}[T,\mathbf{w}] of depth at most 2\Delta+O(1) and size at most \left(\operatorname{poly}(s,\deg(P))\cdot(\log k)^{\operatorname{poly}(\ell)}\right) such that {C}_{\ell}(T,\mathbf{w})\equiv P\left(T,\mathbf{w},R(T,\mathbf{w})\right)\;\mathrm{trunc}\;\langle\mathbf{w}\rangle^{\ell}\,. 6.2.1 Why do we need the quadratic convergence version of Newton iteration? It would be instructive to step back and see why Newton iteration with quadratic convergence was required in the above argument. A slight modification of Lemma 4.9 will let us argue that low-degree components of approximate roots of a polynomial have small constant-depth circuits. However, there are subtle differences in the statement of Lemma 4.9 and the statement of Lemma 6.3 . The key difference is that the approximate root \varphi_{k} is with respect to the variable T , whereas we are extracting homogeneous components of degree up to \ell with respect to a different set of variables . Therefore, we may have contributions of \mathbf{w} -degree at most \ell from terms with T -degree up to k . So, we cannot replace \varphi_{k} by a root of lower accuracy such as \varphi_{\ell} . In the above proof of Lemma 6.3 , each level of the iteration adds to the number of “generators” used in the composition. Using the standard Newton iteration of k steps for \varphi_{k} would result in O(k) generators and would not yield the required size bounds needed for our proof. The version of Newton iteration with quadratic convergence ensures that we obtain \varphi_{k} from \log k iterations, and results in the eventual number of “generators” as O(\log k) instead (which was crucial for the final circuit size bound). 7 Warm-up: preserving true roots under variable reduction In this section, we use the techniques of Section 6 to show a variable reduction map that will help us identify whether a given truncated power series root of a constant-depth circuit is a true root (and not just a sufficiently good truncation of a power series root). As described in the proof overview, the idea is to work with a PIT instance formed by plugging-in a candidate root into the input polynomial. In Lemma 7.1 , we show that low-degree roots of such PIT instances have relatively small constant-depth circuits when the input polynomial has a small constant-depth circuit. 7.1 . Let k>1 be any natural number and let P(T,\mathbf{w},y,z)\in\mathbb{F}[T,\mathbf{w},z] and R(T,\mathbf{w},y)\in\mathbb{F}[T,\mathbf{w},y] be polynomials satisfying the following properties. • P(T,\mathbf{w},y,z) is computable by a depth \Delta circuit of size s . • P(T,\mathbf{w},y,z) is T -regularized and monic in z . • R(T,\mathbf{w},y) is a truncated, non-degenerate, approximate z -root of P(T,\mathbf{w},y,z) of order k . Let F(\mathbf{w})\in\mathbb{F}[\mathbf{w}] be a polynomial of degree at most \ell such that (y-F(\mathbf{w})) divides P\left(T,\mathbf{w},y,R(T,\mathbf{w},y)\right) . Then, F can be computed by an algebraic circuit of depth (\Delta+O(1)) and size at most \operatorname{poly}(s,\deg(P))\cdot(\log k)^{\operatorname{poly}(\ell)}\,. Proof of 7.1 . We start by setting ourselves up to invoke Lemma 4.10 , a version of 4.9 from [ CKS19 ] . To do this, we first need to ensure that the hypothesis of the lemma holds in our case. Setting up to invoke 4.10 : The first issue is that F(\mathbf{w}) could be a y -root of high multiplicity of P\left(T,\mathbf{w},y,R(T,\mathbf{w},y)\right) . To work around this, we work with an appropriately high order derivative of P with respect to y . To this end, we start by viewing P\left(T,\mathbf{w},y,R(T,\mathbf{w},y)\right) as a univariate polynomial in y with coefficients from the ring \mathbb{F}[T,\mathbf{w}] . Thus, P\left(T,\mathbf{w},y,R(T,\mathbf{w},y)\right) can be decomposed as P\left(T,\mathbf{w},y,R(T,\mathbf{w},y)\right)=\sum_{i=0}^{D}P_{i}(T,\mathbf{w})y^{i}\,, where each P_{i} is a polynomial in only T and \mathbf{w} variables. Let (m+1) be the largest integer such that (Y-F(\mathbf{w}))^{m+1} divides P\left(T,\mathbf{w},y,R(T,\mathbf{w},y)\right) . So, to reduce the multiplicity of the y -root F(\mathbf{w}) to 1 , we consider the polynomial \hat{P} defined as \hat{P}(T,\mathbf{w},y):=\frac{\partial P\left(T,\mathbf{w},y,R(T,\mathbf{w},y)\right)}{\partial y^{m}}\,. Thus, we have that (y-F(\mathbf{w})) divides \hat{P} and does not divide \frac{\partial\hat{P}}{\partial y} . As a consequence, we get that \frac{\partial\hat{P}}{\partial y}(T,\mathbf{w},F(\mathbf{w})) is a non-zero polynomial in \mathbb{F}[T,\mathbf{w}] . By shifting the \mathbf{w} variables if needed to \mathbf{a}+\mathbf{w} for some \mathbf{a}\in\mathbb{F}^{|\mathbf{w}|} , we get that \frac{\partial\hat{P}}{\partial y}(T,{\bm{0}},F({\bm{0}}))\not\equiv 0\,. We are now in a position to invoke Lemma 4.10 , which tells us that there exists a \kappa\in\mathbb{F} and a (\ell+1) -variate polynomial Q(\mathbf{u})\in\mathbb{F}[\mathbf{u}] of degree at most \ell such that \displaystyle F(\mathbf{w})\equiv Q(h_{0}(\kappa,\mathbf{w}),h_{1}(\kappa,\mathbf{w}),\ldots,h_{\ell}(\kappa,\mathbf{w}))\mod\langle\mathbf{w}\rangle^{\ell+1}\,, (7.2) where for every i\in\{0,1,\ldots,\ell\} , h_{i}(T,\mathbf{w}) is defined as h_{j}(T,\mathbf{w}):=\left(\frac{\partial\hat{P}}{\partial y^{j}}(T,\mathbf{w},F(\mathbf{0}))-\frac{\partial\hat{P}}{\partial y^{j}}(T,\mathbf{0},F(\mathbf{0}))\right)\;\mathrm{trunc}\;\langle\mathbf{w}\rangle^{\ell+1}\,. Given the bounds on the number of variables and \mathbf{u} -degree of Q(\mathbf{u}) , we get that Q(\mathbf{u}) is computable by an algebraic circuit of depth- 2 and size at most \exp(O(\ell)) . At this point, if we can somehow replace each h_{i}(T,\mathbf{w}) by a small constant-depth circuit, we can obtain a small constant-depth circuit for F(\mathbf{w}) by combining these with the depth- 2 circuit for Q , and then extracting certain homogeneous components of interest. Constant-depth circuits for h_{i}(T,\mathbf{w}) : Recall that \hat{P}(T,\mathbf{w},y) is a derivative of P(T,\mathbf{w},y,R(T,\mathbf{w},y)) with respect to y^{m} . Thus, from Corollary 3.4 , we get that \hat{P} can be written as an \mathbb{F}[y] -weighted linear combination of the polynomials in the set \{P(T,\mathbf{w},\beta_{i},R(T,\mathbf{w},\beta_{i})):i\in\{0,1,\ldots,\deg(P)\}\}\, where \beta_{i} ’s are distinct field constants and every weight in the linear combination has y -degree at most \deg(P) . \displaystyle h_{j}(T,\mathbf{w}) \displaystyle=\left(\frac{\partial\hat{P}}{\partial y^{j}}(T,\mathbf{w},F(\mathbf{0}))-\frac{\partial\hat{P}}{\partial y^{j}}(T,\mathbf{0},F(\mathbf{0}))\right)\;\mathrm{trunc}\;\langle\mathbf{w}\rangle^{\ell+1} \displaystyle=\left(\left(\frac{\partial}{\partial y^{j+m}}P(T,\mathbf{w},y,R(T,\mathbf{w},y))\right)\middle|_{y=F({\bm{0}})}-\frac{\partial\hat{P}}{\partial y^{j}}(T,\mathbf{0},F(\mathbf{0}))\right)\;\mathrm{trunc}\;\langle\mathbf{w}\rangle^{\ell+1} \displaystyle=\left(\left(\sum_{i=0}^{D}\Lambda_{i}(F({\bm{0}}))P(T,\mathbf{w},\beta_{i},R(T,\mathbf{w},\beta_{i}))\right)-\frac{\partial\hat{P}}{\partial y^{j}}(T,\mathbf{0},F(\mathbf{0}))\right)\;\mathrm{trunc}\;\langle\mathbf{w}\rangle^{\ell+1} \displaystyle=\left(\sum_{i=0}^{D}\Lambda_{i}(F({\bm{0}}))P(T,\mathbf{w},\beta_{i},R(T,\mathbf{w},\beta_{i}))\;\mathrm{trunc}\;\left\langle\mathbf{w}\right\rangle^{\ell+1}\right)-\frac{\partial\hat{P}}{\partial y^{j}}(T,\mathbf{0},F(\mathbf{0})) Thus, to show that h_{i}(T,\mathbf{w}) have small constant-depth circuits, it suffices (up to multiplicative factors of \operatorname{poly}(\deg(P)) ) to show that the polynomials (P(T,\mathbf{w},\beta_{i},R(T,\mathbf{w},\beta_{i}))\;\mathrm{trunc}\;\langle\mathbf{w}\rangle^{\ell+1}) have small constant-depth circuits. But, this is exactly the content of 6.6 8 8 8 There is a slight subtlety here: P(T,\mathbf{w},y,R(T,\mathbf{w},y)) must still satisfy the hypothesis of Lemma 6.3 / Corollary 6.6 after replacing each y by a field constant \beta_{i} . But this is true because of Lemma 6.1 . , which shows that (P(T,\mathbf{w},\beta_{i},R(T,\mathbf{w},\beta_{i}))\;\mathrm{trunc}\;\langle\mathbf{w}\rangle^{\ell+1}) has a circuit of depth \Delta+O(1) and size \left(\operatorname{poly}(s,\deg(P))\cdot(\log k)^{\operatorname{poly}(\ell)}\right)\,. This gives a circuit C_{i}(T,\mathbf{w}) of roughly the same size with a constant additive increase in depth for each h_{i}(T,\mathbf{w}) , and thus a circuit \tilde{C}_{i}(\mathbf{w}):=C_{i}(\kappa,\mathbf{w}) for each h_{i}(\kappa,\mathbf{w}) , where \kappa is the field constant in Equation 7.2 . Putting things together: Plugging in these circuits as inputs to the depth- 2 circuit for Q(\mathbf{u}) , we get that there is a circuit C(\mathbf{w})=Q(\tilde{C}_{0}(\mathbf{w}),\dots,\tilde{C}_{\ell}(\mathbf{w})) of size \left(\operatorname{poly}(s,\deg(P))\cdot(\log k)^{\operatorname{poly}(\ell)}\right) and depth (\Delta+O(1)) such that F(\mathbf{w})\equiv C(\mathbf{w})\bmod\langle\mathbf{w}\rangle^{\ell+1}\,. The \mathbf{w} -degree of C(\mathbf{w}) is at most \ell\cdot\deg(Q) , which is at most \ell^{2} . By using 3.4 to compute the truncation C(\mathbf{w})\;\mathrm{trunc}\;\left\langle\mathbf{w}\right\rangle^{\ell+1} , we get a depth- (\Delta+O(1)) circuit for F(\mathbf{w}) , of size at most \left(\operatorname{poly}(s,\deg(P))\cdot(\log k)^{\operatorname{poly}(\ell)}\right). ∎ Now, we will use Lemma 7.1 to prove the main theorem of this section: the Kabanets-Impagliazzo generator, instantiated with an appropriate design and a low-degree polynomial, preserves the roots of constant-depth circuits, while ensuring that no new roots are created. This is a special case of Theorem 5.1 . 7.3 Checking validity of a root. Let k>1 be any natural number and let A(T,\mathbf{x},z)\in\mathbb{F}[T,\mathbf{x},z] and \Phi(T,\mathbf{x})\in\mathbb{F}[T,\mathbf{x}] be polynomials satisfying the following properties. • A(T,\mathbf{x},z) is computable by a depth \Delta circuit of size s . • A(T,\mathbf{x},z) is T -regularized and monic in z . • \Phi(T,\mathbf{x}) is a truncated, non-degenerate, approximate z -root of A(T,\mathbf{x},z) of order k • A(T,\mathbf{x},\Phi(T,\mathbf{x})) is not identically zero in \mathbb{F}[T,\mathbf{x}] . Let \mathcal{S} be a (n,\sigma,\mu,\rho) -design and let g be a \sigma -variate polynomial of degree d . For a new tuple \mathbf{w} of \mu variables distinct from T,\mathbf{x},z , let us define the polynomial map \mathbf{KI}_{g,\mathcal{S}}:\mathbb{F}^{\mu}\to\mathbb{F}^{n} using Definition 3.14 . Then, the following statement is true. If A(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),\Phi(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}))) is identically zero, then g can be computed by an algebraic circuit of depth \Delta^{\prime}=(\Delta+O(1)) and size s^{\prime} which is at most \operatorname{poly}(s,\deg(A),k)\cdot(\rho\log k)^{\operatorname{poly}(d)}\,. In particular, if g cannot be computed by a size s^{\prime} depth \Delta^{\prime} circuit, then A(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),\Phi(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}))) is identically zero if and only if A(T,\mathbf{x},\Phi(T,\mathbf{x})) is identically zero. The proof of this theorem is based on some of the same principles as that of the proof of Theorem 5.1 . However, the underlying technical details are considerably shorter and cleaner. We now discuss the proof. Proof of Theorem 7.3 . Let \hat{B}_{j}(T,\mathbf{x},\mathbf{w}) be the polynomial obtained by replacing the variables x_{1},\ldots,x_{j-1} in the polynomial A(T,\mathbf{x},\Phi(T,\mathbf{x})) by the polynomials g_{1},\ldots,g_{j-1}\in\mathbb{F}[\mathbf{w}] respectively. From the hypothesis of the theorem, we know that \hat{B}_{0} is not identically zero and \hat{B}_{n} is identically zero. Thus, there must be a j such that \hat{B}_{j} is not identically zero but \hat{B}_{j+1} is identically zero. We focus on this j for the rest of the proof. Note that \hat{B}_{j} depends on the variables T,\mathbf{w} and x_{j},x_{j+1},\ldots,x_{n} but does not depend on the variables x_{1},x_{2},\ldots,x_{j-1} . Moreover, \hat{B}_{j+1} is obtained from \hat{B}_{j} by substituting x_{j} by g_{j} . For ease of notation, we refer to the variable x_{j} as y for the rest of this argument. Let B_{j} be the polynomial obtained from \hat{B}_{j} by setting the variables x_{j+1},\ldots,x_{n} and \{w_{i}:w_{i}\notin S_{j}\} to constants from \mathbb{F} such that B_{j} remains non-zero. Since \hat{B}_{j} is a non-zero polynomial, a random substitution of these variables from \mathbb{F} (assuming it is large enough) has this property. Thus, B_{j} only depends on the variables T,y,\{w_{i}:w_{i}\in S_{j}\} . For ease of notation, we continue to refer to the tuple \mathbf{w}_{S_{j}} as \mathbf{w} . We know that when we substitute y by g_{j} in B_{j} , we end up with the identically zero polynomial. In other words, (y-g_{j}) divides B_{j} . At this point, we would like to invoke 7.1 to conclude the proof. In order to do that, we need to make sure that the hypothesis of the lemma holds, which we do now. From its definition, we know that \hat{B}_{j}(T,\mathbf{x},\mathbf{w}):=A(T,g_{1}(\mathbf{w}),\ldots,g_{j-1}(\mathbf{w}),x_{j},x_{j+1},\ldots,x_{n})\,. Now, to obtain B_{j} from \hat{B_{j}} , we set the variables x_{j+1},\ldots,x_{n} and the \mathbf{w} variables outside the set S_{j} to field constants, and rename x_{j} as y . For every i\deg_{T}(P) . For any G(T,\mathbf{x},y)\in\overline{\mathbb{F}}(T,\mathbf{x},z) that divides P(T,\mathbf{x},z) , there is some subset U\subseteq[D] such that G(T,\mathbf{x},y)=\prod_{i\in U}(z-\varphi_{i}(T,\mathbf{x}))\;\mathrm{trunc}\;T^{k}. and \prod_{i\in U}(z-\varphi_{i}(T,\mathbf{x})) is in fact a polynomial (and not just a power series) that equals G(T,\mathbf{x},y) . Proof. Since P(T,\mathbf{x},z) is squarefree and we have the factorisation P(T,\mathbf{x},z)=\prod_{i\in[D]}(z-\varphi_{i}(T,\mathbf{x})) in \mathbb{F}[\mathbf{x},z]\llbracket T\rrbracket and hence any polynomial factor G(T,\mathbf{x},z) must be \prod_{i\in U}(z-\varphi_{i}(T,\mathbf{x})) for some U\subseteq[D] . Since \deg_{T}G\leq\deg_{T}P0$}. Note that \Gamma^{(i)}(\alpha) is in fact a polynomial in T,\mathbf{x} for every \alpha such that \partial_{z}P(0,{\bm{0}},\alpha)\neq 0 . By Lemma 4.5 , for any \alpha_{i}\in\mathcal{Z} , we have that \Gamma^{(k)}(\alpha_{i})=\varphi_{i}\bmod{T^{k}} and therefore Q_{S}(T,\mathbf{x},z)=\prod_{i\in S}(z-\Gamma^{(k)}(\alpha_{i}))\;\mathrm{trunc}\;T^{k} Therefore, every coefficient of Q_{S}(T,\mathbf{x},z) is a symmetric function of the set \left\{\alpha_{i}\ :\ i\in S\right\} . Since g(z)=\prod_{i\in S}(z-\alpha_{i}) is assumed to have coefficients in the base field \mathbb{F} , this implies that every elementary symmetric function of the set \left\{\alpha_{i}\ :\ i\in S\right\} is in \mathbb{F} . By the fundamental theorem of symmetric polynomials, this implies that every coefficient of Q_{S}(T,\mathbf{x},z) is also in \mathbb{F} . ∎ With the above two lemmas, we can now characterise the factors (over \mathbb{F} ) of P(T,\mathbf{x},z) using the polynomials Q_{S}(T,\mathbf{x},z) defined above. 8.3 . Let P(T,\mathbf{x},z) and \varphi_{1}(T,\mathbf{x}),\ldots,\varphi_{D}(T,\mathbf{x}) be defined as above, and let k>\deg_{T}P . Let \alpha_{i}=\varphi_{i}(0,{\bm{0}}) for each i\in[D] . For a subset S\subseteq[D] , define the polynomial Q_{S}(T,\mathbf{x},z)=\prod_{i\in S}(z-\varphi_{i}(T,\mathbf{x}))\;\mathrm{trunc}\;T^{k}. Then, the set of factors of P over the base field \mathbb{F} is the same as \left\{Q_{U}(T,\mathbf{x},z)\in\overline{\mathbb{F}}[T,\mathbf{x},z]\ :\ \begin{array}[]{c}U\subseteq[D]\text{ with }Q_{U}(T,\mathbf{x},z)\text{ dividing }P\\ \text{and }Q_{U}(0,\mathbf{x},z)=Q_{U}(0,{\bm{0}},z)\in\mathbb{F}[z]\end{array}\right\} Proof. Any G(T,\mathbf{x},z)\in\mathbb{F}[T,\mathbf{x},z] that is a factor of P(T,\mathbf{x},z) , by Lemma 8.1 , is equal to Q_{U}(T,\mathbf{x},z)=\prod_{i\in U}(z-\varphi_{i}(T,\mathbf{x})) for some U\subseteq[D] . Additionally, if G(T,\mathbf{x},z)\in\mathbb{F}[T,\mathbf{x},z] , then G(0,\mathbf{x},z)=Q_{U}(0,\mathbf{x},z)\in\mathbb{F}[z] . For the other direction, consider any Q_{U}(T,\mathbf{x},z)\in\overline{\mathbb{F}}[T,\mathbf{x},z] that divides P(T,\mathbf{x},z) and also satisfies that Q_{U}(0,{\bm{0}},z)=\prod_{i\in U}(z-\alpha_{i}) is a polynomial with coefficients in \mathbb{F} . By Lemma 8.2 , we have that Q_{U}(T,\mathbf{x},z) must also be a polynomial in \mathbb{F}[T,\mathbf{x},z] and hence is a factor of P(T,\mathbf{x},z) over \mathbb{F} . ∎ This immediately implies the following certificate for irreducibility. 8.4 . Let P(T,\mathbf{x},z)\in\mathbb{F}[T,\mathbf{x},z] and \varphi_{1}(T,\mathbf{x}),\ldots,\varphi_{D}(T,\mathbf{x}) be defined as above, and let k>\deg_{T}(P) . Then P(T,\mathbf{x},z) is irreducible over \mathbb{F} if and only if for every \emptyset\neq S\subsetneq[D] such that \prod_{i\in S}(z-\alpha_{i}) has all coefficients in \mathbb{F} , we have that Q_{S}(T,\mathbf{x},z)\in\mathbb{F}[T,\mathbf{x},z] does not divide P(T,\mathbf{x},z) where Q_{S}(T,\mathbf{x},z)=\prod_{i\in S}(z-\varphi_{i}(T,\mathbf{x}))\;\mathrm{trunc}\;T^{k}. 8.5 . Essentially the same proof as Lemma 8.3 also characterizes the set of factors of P(T,\mathbf{x},z) over the algebraic closure \overline{\mathbb{F}} , and thus gives a certificate for absolute irreducibility using divisibility tests over \overline{\mathbb{F}} . 8.6 . Let P(T,\mathbf{x},z)\in\mathbb{F}[T,\mathbf{x},z] and \varphi_{1}(T,\mathbf{x}),\ldots,\varphi_{D}(T,\mathbf{x}) be defined as above, and let k>\deg_{T}(P) . Then P(T,\mathbf{x},z) is absolutely irreducible if and only if for every \emptyset\neq S\subsetneq[D] , we have that Q_{S}(T,\mathbf{x},z)\in\overline{\mathbb{F}}[T,\mathbf{x},z] does not divide P(T,\mathbf{x},z) where Q_{S}(T,\mathbf{x},z)=\prod_{i\in S}(z-\varphi_{i}(T,\mathbf{x}))\;\mathrm{trunc}\;T^{k}. 8.4 together with the reduction from divisibility testing to PIT in the next section gives us a reduction from irreducibility testing to PIT. However, we note that gives exponentially many (in degree D ) divisibility testing instances, and thus it isn’t immediately clear if this reduction can be useful for obtaining subexponential time irreducible testing algorithms. It is for this reason that our algorithm for factorization does not proceed directly using this reduction and only uses the corollary (and the previous lemmas) in its analysis. 8.2 From divisibility testing to polynomial identity tests Let us recall the standard definitions of the power sum symmetric polynomials and the elementary symmetric polynomials, particularly in the context of roots of a univariate polynomial. 8.7 . For any monic univariate polynomial P=\prod_{j\in[d]}(z-\alpha_{j})\in\mathbb{F}[z] and natural number i , \mathbf{Psym}_{i}(P) and \mathbf{Esym}_{i}(P) are the power sum symmetric polynomial \sum_{j}\alpha_{j}^{i} and the elementary symmetric polynomial \sum_{S\subseteq[d]:|S|=i}\prod_{j\in S}\alpha_{j} of degree i respectively in the multiset of roots of P . The following important lemma from a recent beautiful work of Andrews and Wigderson [ AW24 ] (but also present in earlier works such as [ SW01 ] ) shows that there is a constant-depth circuit that computes the power sum symmetric polynomials of a multiset from the elementary symmetric polynomials of the multiset; similarly, there is a constant-depth circuit that computes the elementary symmetric polynomials of a multiset from the power sum symmetric polynomials of the multiset. 8.8 [ AW24 , Lemma 3.4, Lemma 3.6] . Let \mathbb{F} be any field of characteristic zero and n\in\mathbb{N} be any natural number. Then, there is a constant-depth circuit of size and degree \operatorname{poly}(n) that takes the n -variate polynomials \{\mathbf{Esym}_{i}(\mathbf{x}):i\in[n]\} as inputs and outputs the polynomials \{\mathbf{Psym}_{i}(\mathbf{x}):i\in[n]\} . Similarly, there is a constant-depth circuit of size and degree \operatorname{poly}(n) that takes the n -variate polynomials \{\mathbf{Psym}_{i}(\mathbf{x}):i\in[n]\} as inputs and outputs the polynomials \{\mathbf{Esym}_{i}(\mathbf{x}):i\in[n]\} . In [ For15 , Section 7.2] , Forbes showed that the question of deterministic divisibility testing for polynomials from a certain complexity class can be reduced to deterministic PIT for polynomials from a related complexity class. This reduction was extensively used in [ KRS23 ] and [ KRSV24 ] . The following version offers a different approach for reducing divisibility testing to PIT, using Lemma 8.8 . 8.9 . Let D\geq t\geq 0 be integer parameters. Let \mathbb{F} be any field of characteristic zero. Then, there is a constant-depth \operatorname{poly}(D,t) -sized circuit \operatorname{DivTest}_{D,t} on D+t+1 variables, that takes (D+t) inputs labelled f_{0},\ldots,f_{D-1}\in\mathbb{F} and g_{0},\ldots,g_{t-1}\in\mathbb{F} respectively, such that \operatorname{DivTest}_{D,t}(z,f_{0},\ldots,f_{D-1},g_{0},\ldots,g_{t-1})=0 if and only if the polynomial f(z)=f_{0}+f_{1}z+\cdots+f_{t-1}z^{t-1}+z^{t} divides the polynomial g(z)=g_{0}+g_{1}z+\cdots+g_{D-1}z^{D-1}+z^{D} . Proof. By Lemma 8.8 , we can construct multi-output circuits \operatorname{PSymToESym}_{n} and \operatorname{ESymToPSym}_{n} of size \operatorname{poly}(n) and depth O(1) such that for every choice of \alpha_{1},\ldots,\alpha_{n} we have \displaystyle\operatorname{ESymToPSym}_{n}(E_{1},\ldots,E_{n}) \displaystyle=(P_{1},\ldots,P_{n}) \displaystyle\operatorname{PSymToESym}_{n}(P_{1},\ldots,P_{n}) \displaystyle=(E_{1},\ldots,E_{n}) \displaystyle\text{ where }E_{i} \displaystyle=\mathbf{Esym}_{i}(\alpha_{1},\ldots,\alpha_{n}) \displaystyle\text{ and }P_{i} \displaystyle=\mathbf{Psym}_{i}(\alpha_{1},\ldots,\alpha_{n}). Let f(z)=\prod_{i=1}^{D}(z-\alpha_{i}) where S_{f}=\left\{\alpha_{1},\ldots,\alpha_{D}\right\} is the multiset of roots of f (in the algebraic closure of \mathbb{F} ), and let S_{g} be the multiset of roots of g(z) . Note that e^{(f)}_{i}:=\mathbf{Esym}_{i}(S_{f})=(-1)^{i}f_{D-i} for i=1,\ldots,D and e^{(g)}_{i}=\mathbf{Esym}_{i}(S_{g})=(-1)^{i}g_{t-i} for i=1\ldots,t . Define the pseudo-quotient of f and g , referred to by \tilde{h} as follows: \displaystyle\tilde{h}(z) \displaystyle=z^{D-t}-z^{D-t-1}e_{1}^{(h)}+\cdots+(-1)^{D-t}e_{D-t}^{(h)} \displaystyle\text{where }e^{(h)}_{i} \displaystyle=\operatorname{PSymToESym}_{D-t}\left(r_{1},\ldots,r_{D-t}\right) \displaystyle\text{where }r_{j} \displaystyle=\left(\operatorname{ESymToPSym}_{D}\left(e_{1}^{(f)},\ldots,e^{(f)}_{D}\right)-\operatorname{ESymToPSym}_{t}\left(e_{1}^{(g)},\ldots,e^{(g)}_{t}\right)\right)_{j} If g\mid f , then the multiset S_{f} is the union of the multiset S_{g} and the multiset S_{h} of roots of h=f/g . In that case, for each i=1,\ldots,D-t , we have \displaystyle\mathbf{Psym}_{i}(S_{f}) \displaystyle=\mathbf{Psym}_{i}(S_{g})+\mathbf{Psym}_{i}(S_{h}) \displaystyle\implies\mathbf{Psym}_{i}(S_{h}) \displaystyle=\mathbf{Psym}_{i}(S_{f})-\mathbf{Psym}_{i}(S_{g}). Therefore, \tilde{h}(z)=h(z) if g\mid f . The circuit \operatorname{DivTest}_{D,t}(f_{0},\ldots,f_{D-1},g_{0},\ldots,g_{t-1}) outputs the polynomial f(z)-\tilde{h}(z)\cdot g(z) where \tilde{h}(z) is computed as stated above. By construction, this is a circuit of size \operatorname{poly}(D,t) and depth O(1) . Furthermore, as argued above, if g\mid h then \tilde{h}(z)=h(z)=f(z)/g(z) and hence the above computes the zero polynomial. If g(z)\nmid f(z) , then f(z)-\tilde{h}(z)g(z) is nonzero for every choice of \tilde{h}(z) and hence the above is nonzero polynomial. ∎ The following lemma uses Lemma 8.9 to show that we can reduce the question of checking whether a candidate factor (constructed using various approximate roots from Newton iteration) is an actual factor, to a PIT instance. 8.10 . Let \mathbb{F} be a field of characteristic zero. Let P(T,\mathbf{x},z)\in\mathbb{F}[T,\mathbf{x},z] be a polynomial that is monic in z . Let R_{1}(T,\mathbf{x}),R_{2}(T,\mathbf{x}),\ldots,R_{\ell}(T,\mathbf{x})\in\mathbb{F}[T,\mathbf{x}] be polynomials of T -degree at most (k-1) . Then, there exists a circuit \operatorname{DivTest}_{\deg_{z}(P),\ell} on at most (\deg_{z}(P)+\ell+1) -variables and size and degree at most \operatorname{poly}(\deg(P),\ell,k) that is computable by a depth- (\Delta+O(1)) such that Q(T,\mathbf{x},z):=\left(\prod_{i\in[\ell]}(z-R_{i}(T,\mathbf{x}))\right)\;\mathrm{trunc}\;T^{k} divides P(T,\mathbf{x},z) if and only if \operatorname{DivTest}_{\deg_{z}(P),\ell}\left(z,P_{0}(T,\mathbf{x}),\ldots,P_{\deg_{z}(P)}(T,\mathbf{x}),(\mathbf{Esym}_{1}(\mathcal{R})\;\mathrm{trunc}\;T^{k}),\ldots,(\mathbf{Esym}_{\ell}(\mathcal{R})\;\mathrm{trunc}\;T^{k})\right)\equiv 0\,, where, for every i , P_{i}(T,\mathbf{x}) is the coefficient of z^{i} in P , when viewing it as a univariate in z with coefficients in the ring \mathbb{F}[T,\mathbf{x}] and \mathcal{R}=\{R_{1},R_{2},\ldots,R_{\ell}\} . Proof. This almost immediately follows from 8.9 since each of the polynomials \mathbf{Esym}_{1}(\mathcal{R})\;\mathrm{trunc}\;T^{k},\dots,\mathbf{Esym}_{\ell}(\mathcal{R})\;\mathrm{trunc}\;T^{k} are the coefficients of \left(\prod_{i\in[\ell]}(z-R_{i}(T,\mathbf{x}))\right)\;\mathrm{trunc}\;T^{k} . As it is, the \operatorname{DivTest} circuit would capture divisibility when the coefficients of the input (univariate) polynomials (in the variable z ) are from a field, but since we are dealing with monic polynomials, Gauss’ Lemma ( Lemma 3.11 ) ensures that Q(T,\mathbf{x},z) divides P(T,\mathbf{x},z) in \mathbb{F}(T,\mathbf{x})[z] if and only if Q(T,\mathbf{x},z) divides P(T,\mathbf{x},z) in \mathbb{F}(T,\mathbf{x})[z] . The theorem now follows. ∎ 8.11 . Let \mathbb{F} be a field of characteristic zero. Let R_{1}(T,\mathbf{x}),R_{2}(T,\mathbf{x}),\ldots,R_{\ell}(T,\mathbf{x})\in\mathbb{F}[T,\mathbf{x}] be polynomials of T -degree at most (k-1) . Then, there is a multi-output algebraic circuit \hat{C} with depth (\Delta+O(1)) and size \operatorname{poly}(\ell,k,\deg(P)) that takes as input the polynomials of the form \{R_{i}(\alpha_{j}T,\mathbf{x}):i\in[\ell],j\in[\operatorname{poly}(\ell,k,\deg(P))]\} and outputs \left(\mathbf{Esym}_{i}(R_{1},R_{2},\ldots,R_{\ell})\;\mathrm{trunc}\;T^{k}\right) for every i\in[\ell] . Here \{\alpha_{j}:j\in[\operatorname{poly}(\ell,k,\deg(P))]\} are elements of \mathbb{F} . Proof. From 8.8 , we get that there is a multi-output constant-depth circuit C on \ell variables that can be computed by a constant-depth circuit of size and degree \operatorname{poly}(\ell) such that C(\mathbf{Psym}_{1}(\mathcal{R}),\ldots,\mathbf{Psym}_{n}(\mathcal{R}))=(\mathbf{Esym}_{1}(\mathcal{R}),\ldots,\mathbf{Esym}_{n}(\mathcal{R}))\,, where, \mathcal{R}=(R_{1},R_{2},\ldots,R_{\ell}) . For ease of notation, we just focus on the computation of one of the \mathbf{Esym}_{j}(\mathcal{R}) and consider the equality \mathbf{Esym}_{j}(\mathcal{R})=C(\mathbf{Psym}_{1}(\mathcal{R}),\ldots,\mathbf{Psym}_{n}(\mathcal{R}))\,. The above equality immediately gives us a constant-depth circuit that takes \mathcal{R} as input and outputs their elementary symmetric polynomials. However, the goal is to compute these things modulo T^{k} . To recover \mathbf{Esym}_{j}(\mathcal{R})\;\mathrm{trunc}\;T^{k} from the above equality, we think of each R_{i}(T,\mathbf{x}) as a polynomial in \mathbb{F}[\mathbf{x}][T] and apply 3.4 with respect to the variable T since we want to extract all the monomials that have T -degree at most k . This only incurs a polynomial blow up in size and an additive constant increase in depth. Moreover, the new circuit can be seen to be taking as inputs polynomials of the form \{R_{i}(\alpha_{j}T,\mathbf{x}):i\in[\ell],j\in[\operatorname{poly}(\ell,k,\deg(P))]\} . ∎ The following is an immediate consequence of 8.11 and 8.10 . 8.12 . Let \mathbb{F} be a field of characteristic zero. Let P(T,\mathbf{x},z)\in\mathbb{F}[T,\mathbf{x},z] be a polynomial that is monic in z . Let R_{1}(T,\mathbf{x}),R_{2}(T,\mathbf{x}),\ldots,R_{\ell}(T,\mathbf{x})\in\mathbb{F}[T,\mathbf{x}] be polynomials of T -degree at most (k-1) . Then, there exists a circuit C on at most (\operatorname{poly}(\ell,k,\deg(P))) -variables and size and degree at most \operatorname{poly}(\deg(P),\ell,k) that is computable by a depth (\Delta+O(1)) circuit such that \left(\prod_{i\in[\ell]}(z-R_{i}(T,\mathbf{x}))\right)\;\mathrm{trunc}\;T^{k} divides P(T,\mathbf{x},z) if and only if C\left(z,P_{0}(T,\mathbf{x}),\ldots,P_{\deg_{z}(P)}(T,\mathbf{x}),\mathcal{R}\right)\equiv 0\,, where, for every i , P_{i}(T,\mathbf{x}) is the coefficient of z^{i} in P , when viewing it as a univariate in z with coefficients in the ring \mathbb{F}[T,\mathbf{x}] and \mathcal{R}=\left(R_{i}(\alpha_{j}T,\mathbf{x}):i\in[\ell],j\in[\operatorname{poly}(\ell,k,\deg(P))]\right) , with each \alpha_{j} being an element of \mathbb{F} . 8.3 Building up to the proof of Theorem 5.1 Theorem 8.13 is our main technical theorem building up to Theorem 5.1 . It shows that for the kind of circuits that show up when testing the divisibility of candidate factors, if composing such a circuit, say C , with the KI generator – instantiated with a polynomial g and a design \mathcal{S} – breaks the nonzeroness of C , then the polynomial g must be “easy”. 8.13 . Let k>1 be any natural number and for every i\in[\ell] , let A_{i}(T,\mathbf{x},z)\in\mathbb{F}[T,\mathbf{x},z] and \Phi_{i}(T,\mathbf{x})\in\mathbb{F}[T,\mathbf{x}] be polynomials satisfying the following properties. • Each A_{i}(T,\mathbf{x},z) is computable by a depth \Delta circuit of size s • Each A_{i}(T,\mathbf{x},z) is T -regularized and is monic in z . • For every i\in[\ell] , \Phi_{i}(T,\mathbf{x}) is a truncated, non-degenerate, approximate z -root of A_{i}(T,\mathbf{x},z) of order k . Let \mathcal{S} be a (n,\sigma,\mu,\rho) -design and let g be a \sigma -variate polynomial of degree d . For a new tuple \mathbf{w} of \mu variables distinct from T,\mathbf{x},z , let us define the polynomial map \mathbf{KI}_{g,\mathcal{S}} using Definition 3.14 . Then the following is true. For any circuit C of depth \Delta and size s such that the polynomial C^{\prime}(T,\mathbf{x}):=C(T,\mathbf{x},\Phi_{1},\Phi_{2},\ldots,\Phi_{\ell}) is non-zero, if C^{\prime}(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w})) is identically zero, then g can be computed by an algebraic circuit of depth O(\Delta) and size \operatorname{poly}(s,\deg(C^{\prime}),k)\cdot(\rho\log k)^{\operatorname{poly}(d)}\,. Proof. The proof proceeds along the lines of the proof of Theorem 7.3 . In particular, we again apply the hybrid argument to the sequence of substitutions for x_{i} by g_{i} and arrive at the point j where the substituted polynomial becomes identically zero for the first time. We again rename the variable x_{j} as y and set any remaining \mathbf{x} variables and \mathbf{w} variables outside the set S_{j} to field constants while preserving the non-zeroness of the polynomial before the j^{th} substitution. We use \hat{C} to denote the result of applying the sequence of substitutions to the circuit C . We use \hat{C^{\prime}} to denote the result of applying the sequence of substitutions to the circuit C^{\prime} . Clearly, it is of the form \hat{C^{\prime}}(T,\mathbf{w},y)=C(T,\hat{g}_{1}(T,\mathbf{w}),\ldots,\hat{g}_{j-1}(T,\mathbf{w}),y,\mathbf{b},\hat{\Phi}_{1},\ldots,\hat{\Phi}_{\ell})=\hat{C}(T,\mathbf{w},y,\hat{\Phi}_{1},\ldots,\hat{\Phi}_{\ell})\,, where each \hat{\Phi}_{i}(T,\mathbf{w},y) is a polynomial in \mathbb{F}[T,\mathbf{w}_{S_{j}},y] that satisfies \hat{\Phi}_{i}(T,\mathbf{w},y)=\Phi_{i}(T,\hat{g}_{1}(T,\mathbf{w}),\ldots,\hat{g}_{j-1}(T,\mathbf{w}),y,\mathbf{b})\, for field constants \mathbf{b} and each \hat{g}_{i} is obtained from g_{i} by setting the \mathbf{w} variables outside the set S_{j} to field constants according to \mathbf{b} and hence depends on only |S_{i}\cap S_{j}|\leq\rho variables. Thus, each \hat{g_{i}} has a depth- 2 circuit of size at most \rho^{O(d)} . We also know that y-g_{j}(\mathbf{w}) divides \hat{C^{\prime}} . From this, we would like to conclude that g_{j} has a small constant-depth circuit. We again follow the proof of Theorem 7.3 , and reduce to the case that (y-g_{j}) is a factor of multiplicity one. To this end, we will have to work with an appropriately high enough order derivative of \hat{C^{\prime}} with respect to y (depending on the multiplicity). From Corollary 3.4 , we get that this derivative is in the \mathbb{F}[y] -span of polynomials of the form \hat{C^{\prime}}(T,\mathbf{w},\beta_{i}) with \beta_{i}\in\mathbb{F} and i\in[\deg_{y}(\hat{C^{\prime}})] , and the y -degree of the weights in this linear combination is at most \deg_{y}(\hat{C^{\prime}}) . Let us denote the derivative by B . Thus, we have that B(T,\mathbf{w},y)=\sum_{i=0}^{\deg_{y}(\hat{C^{\prime}})}\hat{C^{\prime}}(T,\mathbf{w},\beta_{i})\times\Lambda_{i}(y)\,, for univariate polynomials \Lambda_{i}(y) of degree at most \deg_{y}(\hat{C^{\prime}}) , B is non-zero and satisfies B(T,\mathbf{w},g_{j}(\mathbf{w}))\equiv 0\,, and \frac{\partial B}{\partial y}(T,\mathbf{w},g_{j}(\mathbf{w}))\neq 0\,. By shifting the \mathbf{w} variables if needed, we can assume without loss of generality that \frac{\partial B}{\partial y}(T,\mathbf{0},g_{j}(\mathbf{0}))\not\equiv 0\,. Thus, from 4.10 , we get that there is a \kappa\in\mathbb{F} and a polynomial Q of degree at most d on (d+1) variables, that satisfies g_{j}(\mathbf{w})\equiv Q(h_{0}(\kappa,\mathbf{w}),h_{1}(\kappa,\mathbf{w}),\ldots,h_{d}(\kappa,\mathbf{w}))\mod\langle\mathbf{w}\rangle^{d+1}\,, where for every i , h_{i}(T,\mathbf{w})=\frac{\partial B}{\partial y^{i}}(T,\mathbf{w},g_{j}(\mathbf{0}))-\frac{\partial B}{\partial y^{i}}(T,{\bm{0}},g_{j}(\mathbf{0}))\;\mathrm{trunc}\;\langle\mathbf{w}\rangle^{d+1}\,. Given the degree of Q and the number of variables, we get that it has a depth- 2 circuit of size at most \exp(O(d)) . The next claim shows that each h_{i} has a constant-depth circuit of small size. 8.14 . Each h_{i} can be computed by a circuit of depth O(\Delta) and size s^{\prime}\leq\operatorname{poly}(s,\deg(C^{\prime}),k)\cdot(\rho\log k)^{\operatorname{poly}(d)} We first use the claim to complete the proof of the lemma, and discuss the proof of the claim. We take the circuits for h_{i}(T,\mathbf{w}) — given by 8.14 , denoted by V_{i}(T,\mathbf{w}) — and consider the circuit Q(V_{0}(\kappa,\mathbf{w}),V_{1}(\kappa,\mathbf{w}),\dots,V_{d}(\kappa,\mathbf{w})) . Clearly, it is of depth O(\Delta) and size s^{\prime}\leq\operatorname{poly}(s,\deg(C^{\prime}),k)\cdot(\rho\log k)^{\operatorname{poly}(d)} and satisfies g_{j}(\mathbf{w})\equiv Q(V_{0}(\kappa,\mathbf{w}),V_{1}(\kappa,\mathbf{w}),\dots,V_{d}(\kappa,\mathbf{w}))\mod\langle\mathbf{w}\rangle^{d+1}\,. We can now apply 3.4 to obtain the constant-depth circuit for g_{j}(\mathbf{w}) with only an additive increase in depth and a polynomial blow up in the size, thereby giving us the theorem. ∎ Proof of 8.14 . From 6.1 , we know that for any \beta\in\mathbb{F} , the polynomials \hat{A}_{i}(T,\mathbf{w},\beta) and \hat{\Phi}_{i}(T,\mathbf{w},\beta) , obtained from A and \Phi using the substitutions in the above discussion and setting y=\beta , continue to satisfy that properties satisfied by A_{i},\Phi_{i} in the hypothesis of the lemma. Thus, for any field constant \beta , we can invoke 6.3 for each \hat{A}_{i}(T,\mathbf{w},\beta) and \hat{\Phi}_{i}(T,\mathbf{w},\beta) to get that (\hat{\Phi}_{i}(T,\mathbf{w},\beta)\;\mathrm{trunc}\;\langle\mathbf{w}\rangle^{d+1}) can be computed by a circuit of depth (\Delta+O(1)) and size s^{\prime} . We now plug these circuits into the input gates of the constant-depth circuit \hat{C} to get a circuit of depth at most O(\Delta) and size O(s^{\prime}) that computes the polynomial \hat{C}(T,\mathbf{w},\beta,(\hat{\Phi}_{1}(T,\mathbf{w},\beta)\;\mathrm{trunc}\;\langle\mathbf{w}\rangle^{d+1}),\ldots,(\hat{\Phi}_{\ell}(T,\mathbf{w},\beta)\;\mathrm{trunc}\;\langle\mathbf{w}\rangle^{d+1}))\,. Now, applying 3.4 with respect to the \mathbf{w} variables gives us a circuit of depth O(\Delta) and size \operatorname{poly}(s^{\prime}) that computes \left(\hat{C^{\prime}}(T,\mathbf{w},\beta)\;\mathrm{trunc}\;\langle\mathbf{w}\rangle^{d+1}\right) , since by definition \hat{C^{\prime}}(T,\mathbf{w},y) equals \hat{C}(T,\mathbf{w},y,\hat{\Phi}_{1},\ldots,\hat{\Phi}_{\ell}) . Similar to 7.1 10 10 10 Refer to the part of the proof where we show that h_{i}(T,\mathbf{w}) can be computed by constant-depth circuits. , the claim now follows from the definition of B , Corollary 3.4 and the fact that the degree of B in T is at most \deg(C^{\prime}) . ∎ We now combine the machinery in Section 8.2 with Theorem 8.13 to get the following theorem that is directly used in the proof of Theorem 5.1 . 8.15 . Let n\in\mathbb{N} be sufficiently large, and let \mathbf{x}=(x_{1},\dots,x_{n}) . Let \mathbb{F} be a field of characteristic zero. Let k>1 be any natural number. Let P(T,\mathbf{x},z)\in\mathbb{F}[T,\mathbf{x},z] and R_{1}(T,\mathbf{x}),R_{2}(T,\mathbf{x}),\ldots,R_{\ell}(T,\mathbf{x})\in\mathbb{F}[T,\mathbf{x}] be polynomials with the following properties. • P(T,\mathbf{x},z) is computable by a depth \Delta circuit of size s\leq\operatorname{poly}(n) • P(T,\mathbf{x},z) is T -regularized and is monic in z . • For every i\in[\ell] , R_{i}(T,\mathbf{x}) is a truncated, non-degenerate, approximate z -root of P(T,\mathbf{x},z) of order k . Let Q(T,\mathbf{x},z):=\left(\prod_{i\in[\ell]}(z-R_{i}(T,\mathbf{x}))\right)\;\mathrm{trunc}\;T^{k} . Let g be a \sigma -variate degree d polynomial and \mathcal{S} be a (n,\sigma,\mu,\rho) -design. Let \mathbf{KI}_{g,\mathcal{S}}:\mathbb{F}^{\mu}\to\mathbb{F}^{n} be the polynomial map in 3.14 defined using g and \mathcal{S} . Then, the following is true. If Q(T,\mathbf{x},z) does not divide P(T,\mathbf{x},z) but Q(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) divides P(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) , then g can be computed by an algebraic circuit of depth \Delta^{\prime}=O(\Delta) and size at most s^{\prime}=\operatorname{poly}(s,\ell,k,\deg(P))\cdot(\rho\log k)^{\operatorname{poly}(d)}\,. In particular, if any depth- \Delta^{\prime} circuit for g requires size greater than s^{\prime} , then Q(T,\mathbf{x},z) divides P(T,\mathbf{x},z) if and only if Q(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) divides P(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) Proof. If Q(T,\mathbf{x},z) divides P(T,\mathbf{x},z) , then Q(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) certainly divides P(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) . Suppose Q(T,\mathbf{x},z) does not divide P(T,\mathbf{x},z) . Corollary 8.12 tells us that equivalently, there exists a circuit C on at most \operatorname{poly}(\ell,k,\deg(P)) variables, and size and degree at most \operatorname{poly}(\ell,k,\deg(P)) , that is computable by a depth (\Delta+O(1)) circuit such that C\left(z,P_{0}(T,\mathbf{x}),\ldots,P_{\deg_{z}(P)}(T,\mathbf{x}),\mathcal{R}\right)\not\equiv 0\,, where, for every i , P_{i}(T,\mathbf{x}) is the coefficient of z^{i} in P when viewing it as a univariate in z with coefficients in the ring \mathbb{F}[T,\mathbf{x}] , and \mathcal{R}=\left(R_{i}(\alpha_{j}T,\mathbf{x}):i\in[\ell],j\in[\operatorname{poly}(s,k,\deg(P))]\right) , with each \alpha_{j} being an element of \mathbb{F} . If Q(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) divides P(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) , then C\left(z,P_{0}(T,\mathbf{x})\circ\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),\ldots,P_{\deg_{z}(P)}(T,\mathbf{x})\circ\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),\mathcal{R}\circ\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w})\right)\equiv 0\,, where \mathcal{R}\circ\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}):=\{R\circ\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}):R\in\mathcal{R}\} . Observe that C\left(z,P_{0}(T,\mathbf{x})\circ\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),\ldots,P_{\deg_{z}(P)}(T,\mathbf{x})\circ\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),\mathcal{R}\circ\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w})\right) is the same as C\left(z,P_{0}(T,\mathbf{x}),\ldots,P_{\deg_{z}(P)}(T,\mathbf{x}),\mathcal{R}\right)\circ\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}). Moreover, Lemma 6.1 tells us that each R_{i}(\alpha_{j}T,\mathbf{x}) is a truncated, non-degenerate, approximate z -root of P(\alpha_{j}T,\mathbf{x},z) of order k , where P(\alpha_{j}T,\mathbf{x},z) is T -regularized and monic in z . Thus, we can apply Theorem 8.13 to C\left(z,P_{0}(T,\mathbf{x}),\ldots,P_{\deg_{z}(P)}(T,\mathbf{x}),\mathcal{R}\right) to conclude that g can be computed by an algebraic circuit of depth \Delta^{\prime}=O(\Delta) and size s^{\prime} which is at most s^{\prime}:=\operatorname{poly}(s,\ell,k,\deg(P))\cdot(\rho\log k)^{\operatorname{poly}(d)}\,. The contrapositive tells us that if every depth- \Delta^{\prime} circuit for g requires size greater than s^{\prime} obtained as an upper bound above, then Q(T,\mathbf{x},z) divides P(T,\mathbf{x},z) if and only if Q(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) divides P(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) . ∎ 8.4 Proof of Theorem 5.1 We are now ready to prove Theorem 5.1 . We start by recalling some notation that we use. Let \mathcal{G}=\{g_{m}\}_{m\in\mathbb{N}} be a family of polynomials such that for every m\in\mathbb{N} , g_{m}\in\mathbb{F}[x_{1},\dots,x_{m}] , d_{m}:=\deg(g_{m})\leq O(\log\log(m)) . Further, \mathcal{G} has the property that for any depth \Delta\in\mathbb{N} , if \mathcal{C}=\{C_{m}\}_{m\in\mathbb{N}} is a family of depth- \Delta circuits computing \mathcal{G} , then \mathcal{C} requires size m^{d_{m}^{\exp(-O(\Delta))}} , which is m^{\omega(1)} . Theorem 3.15 gives us such a family of explicit low-degree polynomials that are hard for constant-depth circuits. See 5.1 Proof. Suppose P(T,\mathbf{x},z)=\prod_{i=1}^{D}(z-\varphi_{i}(T,\mathbf{x})) , where each \varphi_{i}(T,\mathbf{x}) is a power series root from \mathbb{F}[\mathbf{x}]\llbracket T\rrbracket . Then, by 8.4 , we have that for any subset S\subseteq[D] , F_{S}(T,\mathbf{x},z):=\prod_{i\in S}(z-\varphi_{i}(T,\mathbf{x})) is an irreducible factor of P(T,\mathbf{x},z) in \mathbb{F}[T,\mathbf{x},z] if and only if • Q_{S}(T,\mathbf{x},z) divides P(T,\mathbf{x},z) , where Q_{S}=F_{S}\;\mathrm{trunc}\;T^{k} and • for every \emptyset\neq U\subsetneq S such that \prod_{i\in U}(z-\alpha_{i}) has all coefficients in \mathbb{F} , we have that Q_{U}(T,\mathbf{x},z)\in\mathbb{F}[T,\mathbf{x},z] does not divide P(T,\mathbf{x},z) For the given parameters, one can verify that the upper bound s^{\prime} given in Theorem 8.15 is at most \operatorname{poly}(n) , whereas g_{\sigma} requires size n^{\omega(1)} for any constant-depth circuit 11 11 11 We chose n sufficiently large enough in the theorem statement ( n>C ), which implies that for this particular \sigma , g_{\sigma} requires constant-depth circuits larger than s^{\prime} . . Thus, we can apply Theorem 8.15 on both the conditions above, to equivalently state that for any subset S\subseteq[D] , F_{S}(T,\mathbf{x},z)=\prod_{i\in S}(z-\varphi_{i}(T,\mathbf{x})) is an irreducible polynomial factor of P(T,\mathbf{x},z) if and only if • Q_{S}(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}),z) divides P(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}),z) , and • for every \emptyset\neq U\subsetneq S such that \prod_{i\in U}(z-\alpha_{i}) has all coefficients in \mathbb{F} , we have that Q_{U}(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}),z) does not divide P(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}),z) 6.1 tells us that P(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}),z) will remain a nonzero squarefree 12 12 12 Squarefreeness is equivalent to each root being non-degenerate, which is maintained by 6.1 . polynomial that is monic in z and T -regularized, with \deg_{z}P=D . Furthermore, P(0,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}),z)=P(0,\mathbf{0},z) will be squarefree. Thus, we can apply 8.4 to the above two conditions to get that for any subset S\subseteq[D] , F_{S}(T,\mathbf{x},z)=\prod_{i\in S}(z-\varphi_{i}(T,\mathbf{x})) is an irreducible polynomial factor of P(T,\mathbf{x},z) if and only if • \prod_{i\in S}(z-\varphi_{i}(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w})))\in Q[T,\mathbf{w},z] , and • for every \emptyset\neq U\subsetneq S such that \prod_{i\in U}(z-\alpha_{i}) has all coefficients in \mathbb{F} , we have that \prod_{i\in T}(z-\varphi_{i}(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w})))\not\in\mathbb{Q}[T,\mathbf{w},z] These conditions are true if and only if F_{S}(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}),z)=\prod_{i\in S}(z-\varphi_{i}(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}))) is an irreducible factor of P(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}),z) ; this concludes the theorem. ∎ 9 Proof of correctness of the algorithm We will analyze the correctness of our algorithms in a bottom-up fashion, starting with Algorithm 3 and ending with Algorithm 1 , which will prove Theorem 5.2 . 9.1 Analysis of Algorithm 3 Suppose P(T,\mathbf{x},z)=\prod_{i\in[m]}G_{i}(T,\mathbf{x},z) , where P(T,\mathbf{x},z) is monic in z , T -regularized with \deg_{T}(P)\leq\deg(P):=D and \deg_{z}(P)=D_{z} . P is squarefree and P(0,{\bm{0}},z) is squarefree as well. The G_{i} s are the irreducible factors of P . Let G(T,\mathbf{x},z) denote an arbitrary G_{i} . Suppose G(0,{\bm{0}},z)=\prod_{j\in[r]}H_{j}(z) is the factorization of G(0,{\bm{0}},z) into its irreducible factors. Since P(0,{\bm{0}},z) is squarefree, each H_{j} is distinct. If any of the H_{j}(z) had degree 1, we could’ve lifted that root via Newton iteration and proceeded with the rest of the algorithm. We will now describe how we deal with the absence of roots of G(0,{\bm{0}},z) in \mathbb{Q} using ideas that are standard in the literature (for instance, see [ DSS22 , Section 6.2] ). Let H(z) be an arbitrary irreducible factor of G(0,{\bm{0}},z) and define the field \mathbb{K}:=\frac{\mathbb{Q}[u]}{H(u)} for a new variable u . Thus, we are artificially adding a root of H(u) to our field. Every operation in this field is polynomial addition or multiplication over \mathbb{Q} with the variable u , followed by taking the reminder \mod H(u) . We can now use Newton iteration ( Lemma 4.5 ) to compute a truncated, non-degenerate, approximate z -root \varphi(T,\mathbf{x})\in\mathbb{K}[T,\mathbf{x}] satisfying G(T,\mathbf{x},\varphi(T,\mathbf{x}))\equiv 0\mod\left\langle T\right\rangle^{2D\cdot D_{z}+1} and \varphi(0,\mathbf{x})=u\in\mathbb{K} . The following lemma, standard in the factorization literature (see [ Bü04 , Lemma 3.6] ), tells us that G is the unique minimal polynomial of \varphi with the above constraints. 9.1 . Let G(T,\mathbf{x},z)\in\mathbb{Q}[T,\mathbf{x},z] be an irreducible polynomial, monic in z with T -degree at most D and z -degree exactly D_{z} . Let \varphi(T,x)\in\mathbb{K}[T,\mathbf{x}] be an approximate root of G of order 2D\cdot D_{z}+1 , satisfying G(T,\mathbf{x},\varphi(T,\mathbf{x}))\equiv 0\mod\left\langle T\right\rangle^{2D\cdot D_{z}+1} . Now, suppose B(T,z)\in\mathbb{Q}(\mathbf{x})[T,z] is monic in z with T -degree at most D and z -degree exactly D_{z} satisfying: B(T,\varphi(T,\mathbf{x}))\equiv 0\mod\left\langle T\right\rangle^{2D\cdot D_{z}+1} Then B\equiv G . Proof. Consider R(T):=\operatorname{Res}_{z}(B(T,z),G(T,z))\in\mathbb{Q}(\mathbf{x})[T] . By Theorem 3.8 , there exist polynomials A_{B}(T,z),A_{G}(T,z)\in\mathbb{Q}(\mathbf{x})[T,z] such that R(T)\equiv A_{B}(T,z)B(T,z)+A_{G}(T,z)G(T,z)\,. If we plug in z=\varphi , both B(T,\varphi) and G(T,\varphi) vanish \bmod\left\langle T\right\rangle^{2D\cdot D_{z}+1} . Thus, R(T)\equiv 0\mod\left\langle T\right\rangle^{2D\cdot D_{z}+1} . But the definition of the Resultant tells us that R(T) has T -degree at most 2D\cdot D_{z} , which means that R(T) must be identically zero. By Theorem 3.8 , this implies that \gcd(B,G) is non-trivial in \mathbb{Q}(T,\mathbf{x})[z] , but since both B and G are monic in z , Lemma 3.11 tells us that \gcd(B,G) is non-trivial in \mathbb{Q}[T,\mathbf{x},z] . Since G is irreducible, G must divide B . Moreover, \deg_{z}(B)=\deg_{z}(G) , which implies that B\equiv G . ∎ 9.1.1 Linear system for computing the unique minimal polynomial Let \mathcal{G}=\{g_{m}\}_{m\in\mathbb{N}} be a family of polynomials such that for every m\in\mathbb{N} , g_{m}\in\mathbb{F}[x_{1},\dots,x_{m}] , d_{m}:=\deg(g_{m})\leq O(\log\log(m)) . Further, \mathcal{G} has the property that for any depth \Delta\in\mathbb{N} , if \mathcal{C}=\{C_{m}\}_{m\in\mathbb{N}} is a family of depth- \Delta circuits computing \mathcal{G} , then \mathcal{C} requires size m^{d_{m}^{\exp(-O(\Delta))}} , which is m^{\omega(1)} . Theorem 3.15 gives us such a family of explicit low-degree polynomials that are hard for constant-depth circuits. 9.2 Small division-free circuit for the minimal polynomial of an approximate root. Fix any \Delta\in\mathbb{N} and \varepsilon\in(0,0.5) . For an absolute constant C_{\Delta,\varepsilon}\in\mathbb{N} , let n>C_{\Delta,\varepsilon} and \mathbf{x}=(x_{1},\dots,x_{n}) . Let P(T,\mathbf{x},z) be a polynomial with the following properties. • P is T -regularized and monic in z with total degree D . • G(T,\mathbf{x},z) is an irreducible factor of P with z -degree D_{z} . • H(z) is an irreducible factor of G(0,\mathbf{x},z) , and \mathbb{K} is the field \frac{\mathbb{Q}[u]}{H(u)} . Then, there is a deterministic algorithm \mathcal{A}_{\Delta,\varepsilon} (with access to H(z) ) which • takes as input a size s circuit computing \varphi(T,\mathbf{x})\in\mathbb{K}[T,\mathbf{x}] , a truncated, approximate z -root of P(T,\mathbf{x},z) of order (2D\cdot D_{z}+1) such that \varphi(0,\mathbf{x})=u is a root of G(0,\mathbf{x},z) over \mathbb{K} ; • outputs a division-free circuit over \mathbb{Q} for G(T,\mathbf{x},z) with size \operatorname{poly}(s,D) ; • and runs in time \operatorname{poly}(s,D)^{O(n^{2\varepsilon})} . Proof. We would like to compute a polynomial B(T,z)\in\mathbb{Q}(\mathbf{x})[T,z] that is monic in z with T -degree at most D and z -degree exactly D_{z} satisfying: B(T,\varphi(T,\mathbf{x}))\equiv 0\mod\left\langle T\right\rangle^{2D\cdot D_{z}+1}\, where \varphi(T,\mathbf{x})\in\mathbb{K}[T,\mathbf{x}] is computed by a circuit with constants from \mathbb{K} . Lemma 9.1 guarantees that such a polynomial B has to be the irreducible factor G . We can separate B into its bihomogeneous components with respect to T and z as B(T,z)=\sum_{i=0}^{d}\sum_{j=0}^{D}B_{i,j}z^{i}T^{j}\, where each B_{i,j} can take a value in the field \mathbb{Q}(\mathbf{x}) . Since B is monic in z , B_{d,0}=1 and B_{d,j}=0 for all j>0 . The minimal polynomial satisfies B(T,\varphi(T,\mathbf{x}))=\sum_{i=0}^{d}\sum_{j=0}^{D}B_{i,j}(\varphi(T,\mathbf{x}))^{i}T^{j}\equiv 0\mod\left\langle T\right\rangle^{2D\cdot D_{z}+1} which can equivalently be written as 2D\cdot D_{z}+1 many linear constraints, where each constraint expresses that the coefficient of T^{l} in B(T,\varphi(T,\mathbf{x})) is zero, for some l\in\{0,1,\dots,2D\cdot D_{z}\} . Let \varphi^{(i,j)} denote the coefficient of T^{j} in \varphi^{i} . Thus, we have the following linear system in the variables B_{i,j} for i\in\{0,\dots,D\} and j\in\{0,\dots,D_{z}\} . \displaystyle B_{d,0}=1 (9.3) \displaystyle\forall j\in\{1,\dots,D\}:\, \displaystyle B_{d,j}=0 (9.4) \displaystyle\forall l\in\{0,1,\dots,2D\cdot D_{z}+1\}:\, \displaystyle\sum_{i=0}^{d}\sum_{j=0}^{l}B_{i,j}(\varphi)^{(i,l-j)}=0 (9.5) At this point, the coefficients of each constraint come from \mathbb{K}[\mathbf{x}] , which means that we can interpret each constraint as a degree (\deg(H)-1) polynomial in the variable u , with coefficients from \mathbb{Q}[\mathbf{x}] . Since the minimal polynomial of u is H , it follows that 1,u,\dots,u^{\deg(H)-1} are linearly independent over \mathbb{Q} and, in fact, over 13 13 13 If \sum_{i}p_{i}(\mathbf{x})u^{i}\equiv 0 , then \sum_{i}p_{i}({\bm{0}})u^{i}=0 . \mathbb{Q}[\mathbf{x}] . Thus, for a constraint to be equal to zero, the coefficient of each u^{r} (for r\in\{0,1,\dots,\deg(H)-1\}) must be identically zero in \mathbb{Q}[\mathbf{x}] . To compute the coefficient of u^{r} in (\varphi)^{(i,j)} , we can apply Corollary 3.4 and get a circuit of size \operatorname{poly}(s) ; we will denote this circuit by (\varphi)^{(i,j,r)} . Thus, we can express the constraints of the form Eq. 9.5 using equivalent constraints of the form: \sum_{i=0}^{d}\sum_{j=0}^{l}B_{i,j}(\varphi)^{(i,l-j,r)}=0 for every r\in\{0,\dots,(\deg(H)-1)D_{z}\} and for every l\in\{0,1,\dots,2D\cdot D_{z}+1\} . The linear system is now over \mathbb{Q}[\mathbf{x}] , and thus, any solution to the linear system is going to be over \mathbb{Q}(\mathbf{x}) . We can express the linear system as M_{\varphi}\bm{B}=\bm{c_{\varphi}} for a matrix M_{\varphi} with entries in \mathbb{Q}[\mathbf{x}] , the vector of variables \bm{B}=(B_{i,j}) and a vector \bm{c_{\varphi}}\in(\mathbb{Q}[\mathbf{x}])^{n} . Since the linear system has a unique solution ( Lemma 9.1 ), M_{\varphi} has full column rank. Using some basic linear algebra (for instance, see [ KRSV24 , Lemma B.6] ), we can rewrite the linear system as M_{\varphi}^{T}M_{\varphi}\bm{B}=M_{\varphi}^{T}\bm{c_{\varphi}} , where M_{\varphi}^{T}M_{\varphi} is an invertible square matrix. Thus, we can express the solution to this linear system as \bm{B}=(M_{\varphi}^{T}M_{\varphi})^{-1}(M_{\varphi}^{T}\bm{c_{\varphi}}) . In particular, each B_{i,j} can be expressed as \frac{N_{i,j}(\mathbf{x})}{\det(M_{\varphi}^{T}M_{\varphi})} , where both the numerator and the denominator have circuits of size \operatorname{poly}(s,D) . 14 14 14 Here, we use the well-known fact that the Determinant can be computed efficiently. At this point, we would like to use Strassen’s division elimination ( Lemma 3.6 ) to write each B_{i,j} as a circuit without division. Strassen’s method requires that we find a point \bm{\gamma}\in\mathbb{Q}^{n} such that \det(M_{\varphi}^{T}M_{\varphi}) is non-zero at \bm{\gamma} , but this seems to require a hitting set for circuits since the naive upper bound that we can give for \det(M_{\varphi}^{T}M_{\varphi}) is a small circuit. We will now show that the variable reduction map from Theorem 5.1 also preserves the nonzeroness of \det(M_{\varphi}^{T}M_{\varphi}) . Let \sigma=O(n^{\varepsilon}),\mu=O(\frac{n^{2\varepsilon}}{\log(n)}),\rho=O(\log(n)) , and let \mathcal{S} be an (n,\sigma,\mu,\rho) -design. Let \mathbf{KI}_{g_{\sigma},\mathcal{S}}:\mathbb{F}^{\mu}\to\mathbb{F}^{n} be the polynomial map in 3.14 defined using the design \mathcal{S} and the polynomial g_{\sigma} from the family of hard polynomials \mathcal{G} . 9.6 . \det(M_{\varphi}^{T}M_{\varphi})\circ\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w})\not\equiv 0 Proof. Recall that \det(M_{\varphi}^{T}M_{\varphi}) is non-zero precisely because the irreducible factor G(T,\mathbf{x},z) is the unique solution for the linear system. Lemma 6.1 tells us that \varphi(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w})) is the unique truncated, non-degenerate, approximate z -root of P(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}),z) of order 2D\cdot D_{z}+1 , satisfying \varphi(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}))=u=\varphi(0,\mathbf{x}) . By Theorem 5.1 , we now know that \mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}) preserves the irreducibility of factors, so G(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}),z) is irreducible. Thus, if we had first applied \mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}) to the polynomial P(T,\mathbf{x},z) and computed the truncated, non-degenerate, approximate root \varphi(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w})) of order 2D\cdot D_{z}+1 starting from the same point u\in\mathbb{K} , Lemma 9.1 tells us that we would’ve still maintained uniqueness of solution for the linear system that computes a monic minimal polynomial of \varphi(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w})) of T -degree at most D and z -degree exactly D_{z} . Moreover, the new linear system is going to be the same as the old linear system, except each (\varphi)^{(i,l-j,r)} will be replaced by (\varphi\circ\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}))^{(i,l-j,r)} ; this follows because the transformation \mathbf{x}\mapsto\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}) preserves the (T,z) -degree and the u -degree of every monomial; in other words, the matrix M_{\varphi\circ\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w})} will be equal to M_{\varphi}\circ\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}) . Thus, uniqueness of the linear system’s solution implies that \det(M_{\varphi}^{T}M_{\varphi})(\mathbf{x})\circ\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w})\equiv\det(M_{\varphi\circ\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w})}^{T}M_{\varphi\circ\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w})})\not\equiv 0 . ∎ Thus, to find a point \bm{\gamma}\in\mathbb{Q}^{n} satisfying \det(M_{\varphi}^{T}M_{\varphi})(\bm{\gamma})\neq 0 , we can first compose it with \mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}) to get a degree \operatorname{poly}(n) polynomial on \mu=O(n^{2\varepsilon}) variables. For this low-variate polynomial, we can use the brute force derandomization of the Polynomial Identity Lemma ( Lemma 3.2 ) to find a point \hat{\bm{\gamma}}\in\mathbb{Q}^{\mu} such that \det(M_{\varphi}^{T}M_{\varphi})\circ\mathbf{KI}_{g_{\sigma},\mathcal{S}} is nonzero at \hat{\bm{\gamma}} ; this takes time \operatorname{poly}(s,D)^{O(n^{2\varepsilon})} . Thus, \bm{\gamma}:=\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\hat{\bm{\gamma}})\in\mathbb{Q}^{n} will be a point where \det(M_{\varphi}^{T}M_{\varphi})(\bm{\gamma})\neq 0 . We can then use Lemma 3.6 to give a circuit of size \operatorname{poly}(s,D) for each B_{i,j} , which implies that G(T,\mathbf{x},z)=B(T,z)=\sum_{i=0}^{d}\sum_{j=0}^{D}B_{i,j}z^{i}T^{j} has a circuit of size \operatorname{poly}(s,D) . ∎ 9.7 Correctness of Algorithm 3 . For any \Delta\in\mathbb{N} and \varepsilon\in(0,0.5) , Algorithm 3 , for sufficiently large n , satisfies the following. • It takes as input a depth- \Delta size- s circuit C_{\tilde{P}} computing a squarefree degree- D polynomial \tilde{P}(T,\mathbf{x},z)=\prod_{j\in[m]}\tilde{G}_{j}(T,\mathbf{x},z) , where the \tilde{G}_{i} s are the irreducible factors of \tilde{P} . Further, \tilde{P}(T,\mathbf{x},z) is monic in z , T -regularized with respect to \mathbf{x} and C_{\tilde{P}}(0,\mathbf{x},z)=C_{\tilde{P}}(0,{\bm{0}},z) is squarefree. • It also takes as input the univariate polynomial \tilde{G}_{j}(0,\mathbf{x},z)=\tilde{G}_{j}(0,{\bm{0}},z) for each j\in[m] . • It outputs a list L=\{C_{\tilde{G}_{1}}(T,\mathbf{x},z),\dots,C_{\tilde{G}_{m}}(T,\mathbf{x},z)\} , such that each C_{\tilde{G}_{i}}(T,\mathbf{x},z) is a circuit of size \operatorname{poly}(s,D) and depth \operatorname{poly}(D) , which computes the irreducible factor \tilde{G}_{i}(T,\mathbf{x},z) of \tilde{P}(T,\mathbf{x},z) . • It runs in time \operatorname{poly}(s,D)^{O(n^{2\varepsilon})} . Proof. The algorithm iterates over each \tilde{G}_{j} , so let us focus on one such \tilde{G}_{j} . By Theorem 4.11 , Algorithm 3 of the algorithm gives the correct factorization of \tilde{G_{j}}(0,{\bm{0}},z) into its irreducible factors, and it runs in time \operatorname{poly}(\deg(\tilde{G_{j}}(0,{\bm{0}},z))) . By Corollary 4.6 , Algorithm 3 will correctly compute a truncated, non-degenerate, approximate z -root \varphi(T,\mathbf{x})\in\mathbb{K}[T,\mathbf{x}] of \tilde{G}_{j}(T,\mathbf{x},z) of order 2D\cdot D_{z}+1 such that \varphi(0,\mathbf{x})=\varphi(0,{\bm{0}})=u\in\mathbb{K} . Moreover, it runs in time \operatorname{poly}(s,D) and outputs a circuit for \varphi(T,\mathbf{x}) of size \operatorname{poly}(s,D) . Finally, by Theorem 9.2 , Algorithm 3 will correctly compute a circuit C_{\tilde{G_{j}}} for \tilde{G_{j}} , of size \operatorname{poly}(s,D) , in time \operatorname{poly}(s,D)^{O(n^{2\varepsilon})} . ∎ 9.2 Analysis of Algorithm 2 9.8 Correctness of Algorithm 2 . For any \Delta\in\mathbb{N} and \varepsilon\in(0,0.5) , Algorithm 2 , for sufficiently large n , satisfies the following. • The input to the algorithm is a depth- \Delta size- s circuit C_{P} computing the squarefree polynomial P(\mathbf{x})=\prod_{j\in[m]}G_{j}(\mathbf{x}) , where the G_{j} s are the irreducible factors of P . • The output of the algorithm is a list L=\{C_{G_{1}}(\mathbf{x}),\dots,C_{G_{m}}(\mathbf{x})\} , such that each C_{G_{j}}(\mathbf{x}) is a circuit of size \operatorname{poly}(s,D) and depth \operatorname{poly}(D) , which computes the irreducible factor G_{j}(\mathbf{x}) . • The algorithm runs in time \operatorname{poly}(s,D)^{O(n^{2\varepsilon})} . Proof. The coefficient of z^{D} in \hat{P}(\mathbf{x},z):=P(\mathbf{x}+(\mathbf{a}\cdot z))/\delta is \operatorname{Hom}_{D}[P]/\delta=1 , thus \hat{P} is monic in z , and \hat{P} retains the squarefreeness of P . Moreover, Corollary 3.4 tells us that \operatorname{Hom}_{D}[P] has a size \operatorname{poly}(s,D) and depth (\Delta+O(1)) circuit, so Theorem 3.16 outputs \mathbf{a} satisfying \operatorname{Hom}_{D}[P](\mathbf{a})\neq 0 , in time \operatorname{poly}(s,D)^{O(n^{\varepsilon})} . Since \hat{P} is monic in z and squarefree, Theorem 3.9 along with Lemma 3.11 tells us that \operatorname{Disc}_{z}(\hat{P})(\mathbf{x})\not\equiv 0 . In Algorithm 2 , \mathbf{b} is chosen to ensure that \operatorname{Disc}_{z}(\hat{P})(\mathbf{b})\neq 0 . For \tilde{P}(T,\mathbf{x},z):=\hat{P}((T\cdot\mathbf{x})+\mathbf{b},z) , \operatorname{Disc}_{z}(\tilde{P}(0,\mathbf{x},z))=\operatorname{Disc}_{z}(\tilde{P}(0,{\bm{0}},z))=\operatorname{Disc}_{z}(\hat{P})(\mathbf{b})\neq 0 , which implies that \tilde{P}(0,\mathbf{x},z)\in\mathbb{Q}[z] is squarefree. Moreover, Theorem 3.10 (along with an application of Corollary 3.4 for the complexity of \frac{\partial\hat{P}}{\partial z} ) tells us that \operatorname{Disc}_{z}(\hat{P})=\operatorname{Res}_{z}(\hat{P},\frac{\partial\hat{P}}{\partial z}) has a size \operatorname{poly}(s,D) and depth (\Delta+O(1)) circuit. Thus, we can again use Theorem 3.16 to find \mathbf{b} in time \operatorname{poly}(s,D)^{O(n^{\varepsilon})} . In Algorithm 2 , the map \mathbf{KI}_{g_{\sigma},\mathcal{S}} can be constructed in time \exp(O(n^{\varepsilon})) by using Lemma 3.13 . In Algorithm 2 , \tilde{P}(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}),z) is an O(n^{2\varepsilon}) -variate polynomial. Using Theorem 4.12 , we can factorize C_{\tilde{P}}(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) in time \operatorname{poly}(s,D)^{O(n^{2\varepsilon})} . For each j\in[m] , let \tilde{G}_{j}(T,\mathbf{x},z) denote G_{j}((T\cdot\mathbf{x})+(\mathbf{a}\cdot z)+\mathbf{b}) ; \tilde{G_{j}} must be irreducible (this is standard in the literature; for a proof, see [ KRSV24 , Lemma B.7] ). By Theorem 5.1 , for each j\in[m] , \tilde{G}_{j}(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) is an irreducible factor of \tilde{P}(T,\mathbf{KI}_{g_{\sigma},\mathcal{S}}(\mathbf{w}),z) . Thus, for j\in[m] , the factorization in Algorithm 2 will compute a circuit C_{\tilde{G}_{j}}(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) that computes \tilde{G}_{j}(T,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z) , satisfying the property that \tilde{G}_{j}(0,\mathbf{KI}_{g,\mathcal{S}}(\mathbf{w}),z)=\tilde{G}_{j}(0,{\bm{0}},z) . By Theorem 9.7 , Algorithm 3 correctly computes the list L^{\prime}=\{C_{\tilde{G}_{1}}(T,\mathbf{x},z),\dots,C_{\tilde{G}_{m}}(T,\mathbf{x},z)\} in time \operatorname{poly}(s,D)^{O(n^{\varepsilon})} . Algorithm 2 computes C_{G_{j}}(\mathbf{x})=C_{\tilde{G}_{1}}(1,\mathbf{x}-\mathbf{b},0) for each G_{j}(\mathbf{x}) correctly. Overall, the algorithm takes time \operatorname{poly}(s,D)^{O(n^{\varepsilon})} and outputs circuits of size \operatorname{poly}(s,D) for each irreducible factor G_{j}(\mathbf{x}) of P(\mathbf{x}) . ∎ 9.3 Analysis of Algorithm 1 See 5.2 Proof. Algorithm 1 , instantiated with parameters \Delta and \varepsilon , is the algorithm \mathcal{A}_{\Delta,\varepsilon} claimed in the theorem statement. Theorem 4.4 ensures the correctness of Algorithm 1 so that for each i\in[r] , P_{i}(\mathbf{x}) corresponds to the product of irreducible factors of P that have multiplicity i in the factorization (and r is the maximum multiplicity of an irreducible factor). The algorithm from Theorem 4.4 runs in time \operatorname{poly}(s,D) with oracle access to a PIT algorithm for constant-depth circuits; replacing each oracle access by the algorithm in Theorem 3.16 results in a running time of \operatorname{poly}(s,D)^{O(n^{\varepsilon})} . For each P_{i}(\mathbf{x}) , Theorem 9.8 guarantees that the list L_{i} output by Algorithm 2 in Algorithm 1 is exactly a list of circuits computing the irreducible factors of P_{i} ; moreover, it runs in time \operatorname{poly}(s,n^{D})^{O(n^{2\varepsilon})} . Since factors of P_{i} have multiplicity i in P , Algorithm 1 adds the right multiplicity information along with each circuit for factors of P_{i} . Every irreducible factor of P(\mathbf{x}) must occur as an irreducible factor in P_{i}(\mathbf{x}) for some i\in[r] ; thus, every irreducible factor along with its multiplicity will be included in the output list. ∎ Acknowledgements: The discussions leading to this work started when a subset of the authors were at the workshop on Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 24381) at Schloss Dagstuhl. We are thankful to the organisers of the workshop and to the staff at Schloss Dagstuhl for the wonderful collaborative atmosphere that facilitated these discussions. † † footnotetext: git info: 9b2482a , (2025-06-09 05:16:08 +0000)   Easter-egg? Didn’t factor that in…