{"id":"ae6a3200-6e19-47b1-a5bd-78d2fce92c36","arxiv_id":"2506.23214","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Factors of polynomials computed by small constant-depth circuits or formulas are themselves computable by small constant-depth circuits or formulas in characteristic zero and large positive characteristic.","lead":"The paper proves that any factor of a polynomial with a small constant-depth arithmetic circuit or small formula has a small constant-depth circuit or formula. The proof rests on a 1960s theorem of Furstenberg that writes power series roots of a polynomial as an explicit diagonal of a rational function.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central proof's only non-elementary step is the use of [AW24, Thm I.8] to recover base-field factors from algebraic-closure roots; if that theorem does not compose uniformly with depth-Δ coefficient circuits (or its degree bound is exceeded), Theorem 4.3 has a gap.","rationale":"The paper's main claim is a major closure theorem, and its proof is remarkably simple: Section 3 supplies a self-contained proof of Furstenberg's identity, and Section 4.1 derives the power-series-root complexity in an elementary way. I checked the truncation arguments and the diagonal manipulations in Corollary 3.3 and Theorem 4.1; they are internally consistent. The small-characteristic appendix also appears coherent, including the Frobenius-based step in Theorem A.3. The point where the argument stops being self-contained is exactly Theorem 4.3's use of the external Andrews-Wigderson theorem to convert symmetric functions of algebraic-closure roots into base-field circuits. If Theorem 4.2 behaves exactly as needed, the closure result follows; if its guarantees are only for field coefficients, or if its construction introduces divisions whose denominators can vanish on the coefficient tuples produced by Rnum and Rdenom, then the proof of the central theorem has a genuine gap. This is not a criticism of [AW24]—the theorem may well be true in the needed form—but the paper does not verify the four details listed above, and the central claim depends on them. The proposed concrete test resolves the question by inspecting the [AW24] proof and testing the simplest nontrivial example. Since the concern is about an external dependency rather than an internal contradiction, the appropriate verdict is conditional acceptance pending that check; if the check passes, the reader's original ACCEPT verdict is justified.","tokens_in":26910,"tokens_out":25027,"duration_ms":275022,"concrete_test":"Read the proof of [AW24, Theorem I.8] and verify: (i) it works for a degree bound D=O(d^2), so it accepts deg h=O(d^2); (ii) after substituting the coefficient circuits for Rnum and Rdenom it yields a circuit over F computing a polynomial in F[x,t]; and (iii) any division gates it uses have denominators that are powers of Res(f,h) or Disc(f), hence are nonzero for f=g(0,y), h=Rdenom, where f is squarefree and h(α_i)≠0. As a sanity check, apply the construction to P̃(t,y)=y^2−t with factor g=y^2−t and confirm it outputs the coefficients of y^2−t over Q(t).","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Furstenberg's identity in Section 3 and the deductions in Section 4.1 are elementary and check out. The load-bearing point is the transition in Theorem 4.3 from power-series roots over the algebraic closure to a factor over the base field: the coefficients of g'(t,y)=∏_{α∈S}(y−R(α)) are recovered by applying Theorem 4.2 to f=g(0,y), g=Rnum, h=Rdenom. Three concrete conditions must hold for that step. First, Theorem 4.2 as quoted bounds deg(f), deg(g), deg(h) ≤ d, but deg_z(Rdenom)=(2d+3)·deg_z(∂yP̃(0,z))=O(d^2); this is fixable by enlarging the degree parameter, but it is not stated. Second, Rnum and Rdenom have coefficients in F[x,t], so the theorem's circuit over 'the coefficients' must be regarded as a uniform circuit in those coefficient variables; after composing with the depth-Δ circuits for Rnum and Rdenom, the result must be a circuit over F computing a polynomial. Third, the elementary symmetric functions of g(α)/h(α) are rational in the coefficients of f, g and h, so the [AW24] circuit apparently uses divisions or explicitly clears denominators; the paper needs those denominators to be nonzero (or the circuit to be division-free) on all coefficient tuples arising from the construction. The only denominator guaranteed nonzero by the hypotheses is Res(f,h) (since h(α_i)≠0), and squarefreeness makes Disc(f) nonzero. If the [AW24] construction involves additional intermediate divisions, the composed circuit may fail to be defined at the relevant coefficients even though the desired polynomial exists. No verification of this uniformity is supplied, making this the single weakest link in the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that constant-depth algebraic circuits and algebraic formulas over characteristic zero (and, with the same proof, sufficiently large characteristic) are closed under taking factors: if an n-variate degree-d polynomial f has a circuit of size s and depth Δ (resp. a formula of size s), then every factor g of f has a circuit of size poly(s,d,n) and depth Δ+O(1) (resp. a formula of size poly(s,d,n)). The main technical engine is a result of Furstenberg expressing power-series roots of a bivariate polynomial as the diagonal of a rational function; the paper gives a self-contained proof of this identity and uses it to show that truncations of power-series roots are computable by small constant-depth circuits and formulas. General factors are then recovered by combining power-series roots, using elementary symmetric functions and a theorem of Andrews and Wigderson. The paper also derives applications to deterministic factorization of constant-depth circuits, hardness-randomness trade-offs, and a border version of the factor conjecture.","tokens_in":27228,"tokens_out":14352,"duration_ms":159670,"significance":"If the proof is completed at the one black-box point identified below, this is a significant result: it resolves long-standing open questions about closure under factorization for formulas and constant-depth circuits, provides a unified proof of several known closure results, and yields clean quantitative improvements for deterministic factorization and hardness-randomness trade-offs. The paper is particularly valuable for giving an elementary, self-contained proof of Furstenberg's identity and for showing how a classical result can replace the iterative Newton/Hensel lifting that previously seemed essential. The applications in Sections 5--6 are natural and strengthen prior work. The main caveat is that the transition from power-series roots over the algebraic closure to factors over the base field relies on an external theorem whose uniformity and denominator behavior are not stated; this point is load-bearing but appears fixable.","major_comments":[{"comment":"The recovery of the factor g(t,y) from the algebraic-closure roots applies Theorem 4.2 with f = g(0,y), g = Rnum, h = Rdenom, but this application is not covered by the quoted statement of that theorem. The quoted theorem assumes f,g,h ∈ F[z] with degree at most d and inputs 'coefficients from the base field'; here Rnum and Rdenom have coefficients in F[x,t] and deg_z(Rdenom) = (2d+3)·deg_z(∂_y P̃(0,z)) is O(d^2), exceeding the stated degree bound. The proof must state explicitly that Theorem 4.2 is uniform in the coefficients, so that the coefficient inputs may themselves be outputs of depth-Δ circuits; that the degree parameter is enlarged to O(d^2); and that the resulting circuit is either division-free or that all denominators are nonzero at the relevant coefficient tuples, or are explicitly cleared. As written, this is the only non-elementary step in the proof of the main closure theorem and it is load-bearing.","section":"§4.2, Theorem 4.3"},{"comment":"The equalities g(t,y) = Hom_{≤d}(g'(t,y)) and g'(t,y) = ∏_{α∈S}(y−R(α)) initially define an object over the algebraic closure or over F(x,t). The argument that the coefficients of g' lie in F[x,t] and coincide with those of the original factor g is only implicit in the sentence that the elementary symmetric polynomials of {α : α∈S} are elements of the field. Base-field membership is exactly what makes Theorem 1.1 a statement over F rather than over an extension, so the proof should spell out why the symmetric-function circuit obtained from Theorem 4.2, after composing with the circuits for Rnum and Rdenom, computes a polynomial with coefficients in F[x,t] and why this polynomial agrees with g in all degrees up to the stated truncation.","section":"§4.2, display for g'(t,y)"},{"comment":"The circuit C(x,t,y) used for the divisibility test is asserted to be a size-poly(s), depth-Δ+O(1) circuit because Q_U'(x,t,y) has that complexity. The construction of Q_U' uses the same symmetric-function step as Theorem 4.3, so the correctness of the deterministic algorithm in Theorem 5.2 inherits the same uniformity and denominator caveat. Since the algorithm's running time also depends on the time needed to construct the circuit from the coefficients, the paper should state whether the [AW24] theorem is constructive in the relevant sense; otherwise the algorithmic claim has the same gap.","section":"§5.1, Lemma 5.1"}],"minor_comments":[{"comment":"The 'git info: 0c48f73...' line in the reference list appears to be a stray submission artifact and should be removed.","section":"References"},{"comment":"There is a typo: 'demystefy' should be 'demystify'.","section":"§1.1.1"},{"comment":"The definition of a valid pre-processing map says K = F(x) and Ψ_{a,b} : F[x,y] → K[t,y], but the displayed substitution xi ↦ t·xi + a_i y + b_i produces an element of F[x,t,y]. The role of K and the precise coefficient field should be clarified, since the later proof uses P̃(t,y) ∈ F[x][t,y] and P̃(0,y) ∈ F[y].","section":"Definition 2.10"},{"comment":"The phrase 'zero or sufficiently large characteristic' is not quantified; the paper should state a concrete threshold, such as characteristic larger than d, so that the use of coefficients like 1/m in Corollary 3.3 is justified.","section":"Theorem 1.1 / Theorem 4.2"},{"comment":"The sentence 'distinct elements of F have distinct set of roots' appears to be a typo; it should refer to distinct roots of the squarefree polynomial F(0,0,y).","section":"§5.1, proof of Lemma 5.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is a strong fit for the journal and the central idea is attractive and likely correct. The main risk is the black-box use of [AW24, Thm I.8] in a regime not stated in the paper. I would ask the authors to state and prove (or cite precisely) the uniform, degree-enlarged, denominator-free version of that theorem and to make the base-field membership argument in Theorem 4.3 explicit. If those points are addressed, I would expect the paper to be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe headline: this paper proves that formulas and constant-depth circuits are closed under taking factors, over characteristic zero (and large characteristic), with polynomial size and constant-depth overhead. That's a clean resolution of a long-standing open problem, and the proof is genuinely novel: instead of Newton iteration, they use Furstenberg's diagonal identity to write power series roots in closed form. Section 3 is elementary and self-contained, and Theorem 4.1 (power series roots) is solid. The deduction to general factors in Theorem 4.3 is the right way to go, using symmetric functions to pass from algebraic-closure roots back to the base field. The applications—unified closure proofs, improved hardness-randomness tradeoffs, and a cleaner deterministic factorization algorithm—are real and follow from the main theorem.\n\nThe soft spots are all in the transition of Theorem 4.3. The paper applies Andrews-Wigderson's Theorem I.8 to the rational function R(z) = Rnum/Rdenom. Two things are off in the write-up. First, deg_z(Rdenom) = O(d^2), not d, so the degree bound in the quoted theorem is exceeded; this is fixable by enlarging the degree parameter, but it's not stated. Second, the cited theorem computes elementary symmetric polynomials of ratios g(alpha_i)/h(alpha_i), which are rational functions in the coefficients of f,g,h. The theorem's circuit likely uses divisions (or clears denominators), and the paper does not show that the composed circuit is division-free or that all intermediate denominators are nonzero on the coefficient tuples that arise. The only guaranteed nonzero denominator is Res(f,h). If AW24's construction has additional divisions, the composed circuit might not be defined at the relevant coefficients. This is the one real gap, and it's a presentation gap rather than a fatal one—presumably the AW24 result can be stated in division-free form after multiplying by Res(f,h), and the degree bound can be absorbed. But the authors need to address it explicitly.\n\nSo the central claim holds up, and the proof strategy is sound. The paper is worth a serious referee, and I'd accept it conditionally on fixing the Theorem 4.3 application and checking the uniformity of the AW24 circuit. The intended audience is algebraic complexity folks working on factorization and hardness-randomness; they'll want to read Section 3 and Theorem 4.3 carefully. I'd bring it to the reading group.","headline":"Solves the closure-under-factors problem for formulas and constant-depth circuits with a genuinely novel proof; the main risk is a gap in how the Andrews-Wigderson theorem is applied in Theorem 4.3, but it's fixable.","tokens_in":27846,"tokens_out":7243,"would_cite":true,"duration_ms":73552,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","12D05","13P05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Constant-depth algebraic circuits and algebraic formulas are closed under taking factors.","keywords":["algebraic circuits","polynomial factorization","constant-depth circuits","algebraic formulas","power series roots","diagonal operator","polynomial identity testing","hardness-randomness trade-offs"],"falsifier":"Check the theorem on which the lifting step rests at the precise instantiation used here: take $f(z)=z^d-1$ and let $g,h$ be polynomials produced by poly-size constant-depth circuits, then verify that the asserted constant-depth circuit for the elementary symmetric polynomials of $g(\\alpha_i)/h(\\alpha_i)$ exists over the base field without division gates or a PIT oracle. A concrete counterexample at this step, or any explicit family of constant-depth circuits whose irreducible factor can be shown to require super-polynomial size, would refute the main theorem.","tokens_in":26683,"feed_emoji":"🧮","tokens_out":14609,"duration_ms":134148,"temperature":0.7,"pith_summary":"This paper aims to settle a long-standing closure question: if a multivariate polynomial is computed by a small algebraic formula or a small constant-depth algebraic circuit, are all of its factors computed in the same model? The answer, over fields of characteristic zero (and sufficiently large characteristic), is yes. For a degree-$d$ polynomial on $n$ variables computed by a size-$s$ depth-$\\Delta$ circuit, every factor is computed by a circuit of size $\\mathrm{poly}(s,d,n)$ and depth $\\Delta+O(1)$; for a size-$s$ formula, every factor is computed by a formula of size $\\mathrm{poly}(s,d,n)$. The proof is driven by a 1960s identity that gives a non-iterative, closed-form expression for power-series roots of a bivariate polynomial, turning a sequential lifting process into one finite formula whose truncations inherit constant depth and polynomial size.","feed_headline":"Every factor of a constant-depth circuit is constant-depth","feed_subtitle":"A 1960s power-series identity turns iterative root-finding into one formula, keeping factors small and enabling new derandomization.","key_machinery":"The load-bearing object is the diagonal operator on bivariate power series, $D(\\sum_{i,j} F_{i,j}t^i y^j)=\\sum_i F_{i,i}t^i$, which extracts the terms whose $t$-degree and $y$-degree are equal. A 1960s result expresses a power-series root $\\varphi$ of $P(t,y)$, of multiplicity $e$, as the diagonal $\\varphi=D\\bigl(y^2\\,\\partial_y P(ty,y)/(e\\,P(ty,y))\\bigr)$. Over characteristic zero this becomes a closed coefficient-extraction sum, $\\varphi(t)=\\sum_{m\\ge 1}\\frac{1}{m}\\,[y^{m-1}](y-P(t,y))^m$, which replaces iterative power-series lifting by a single finite expression: because every monomial of $y-P(t,y)$ is divisible by $t$ or by $y^2$, only $m\\le 2d$ terms can affect the degree-$d$ truncation. That is what transfers size and depth bounds from $P$ to its roots. A second ingredient, a recent theorem on constant-depth circuits for elementary symmetric polynomials of values $g(\\alpha_i)/h(\\alpha_i)$ at the roots $\\alpha_i$ of a degree-$d$ polynomial, is what converts a product of power-series roots over the algebraic closure into a factor with coefficients in the base field.","core_discovery":"The central claim is Theorem 1.1: over a field of characteristic zero, constant-depth algebraic circuits and algebraic formulas are closed under taking factors. If $f$ has degree $d$ and is computed by a circuit of size $s$ and depth $\\Delta$, then every factor $g$ of $f$ is computed by a circuit of size $\\mathrm{poly}(s,d,n)$ and depth $\\Delta+O(1)$; if $f$ is computed by a formula of size $s$, then $g$ is computed by a formula of size $\\mathrm{poly}(s,d,n)$. The proof first shows that truncations of a power-series root $\\varphi(t)$ of $P(t,y)$, with $\\varphi(0)=0$ and $\\partial_y P(0,0)\\ne 0$, are computable by the same kind of small circuit as $P$, using $\\varphi(t)=\\sum_{m\\ge 1}\\frac{1}{m}\\,[y^{m-1}](y-P(t,y))^m$. It then combines these algebraic-closure roots into a factor over the base field with small constant-depth circuits for elementary symmetric polynomials of root evaluations. For finite fields the paper proves a weaker statement: if $g$ divides $f$ with multiplicity $p^\\ell e$ and $\\gcd(p,e)=1$, then $g^{p^\\ell}$ has a poly-size constant-depth circuit over the algebraic closure.","pith_inferences":["Because the root formula only needs coefficient extraction, interpolation, and homogenization, the same closure argument should transfer to any further algebraic model closed under these operations, such as read-once oblivious branching programs; this is an extension the paper does not work out.","The finite-field statement's restriction to $p^{\\ell}$-th powers suggests that genuine closure failures, if any, live in the operation of taking $p$-th roots; the paper explicitly leaves open whether $f^p$ having a small constant-depth circuit forces $f$ to have one.","The proof's dependence on the factor degree $d$, rather than on the degree of $f$, is what yields the border bound for low-degree factors of high-degree circuits; pushing this direction may give a new route to the factor conjecture for general circuits.","The previous subexponential factoring algorithm for constant-depth circuits is now explained by the closure property itself: factors are constant-depth, so any explicit hitting set for constant-depth circuits preserves factorization; plugging in a better hitting set would immediately speed up deterministic factoring."],"forward_implications":["Every factor of an $n$-variate degree-$d$ polynomial computed by a size-$s$, depth-$\\Delta$ constant-depth circuit is computed by a $\\mathrm{poly}(s,d,n)$-size, depth-$\\Delta+O(1)$ circuit.","Every factor of a size-$s$ algebraic formula is computed by a $\\mathrm{poly}(s,d,n)$-size formula.","The standard hardness-randomness trade-off now applies to formulas and constant-depth circuits: sufficiently strong explicit lower bounds imply quasipolynomial-time deterministic identity testing for these classes.","Deterministic factorization of constant-depth circuits reduces to blackbox PIT for the same class, giving a deterministic subexponential-time factoring algorithm whose output circuits are also constant-depth, and a randomized polynomial-time factoring algorithm by random sampling.","The same proof yields a single argument covering closure for general circuits, formulas, branching programs, and VNP, and a border-complexity bound on low-degree factors of arbitrary circuits."],"supporting_citations":[{"why":"Supplies the diagonal identity expressing a power-series root as a diagonal of a rational function; this is the non-iterative root formula that drives Theorem 4.1.","marker":"[Fur67]"},{"why":"Provides the constant-depth circuits for elementary symmetric polynomials of root evaluations and for squarefree decomposition; these lift power-series roots over the algebraic closure to factors over the base field.","marker":"[AW24]"},{"why":"Supplies the standard reduction of multivariate factorization to a monic bivariate polynomial and the power-series factorization lemma used in the preprocessing step.","marker":"[DSS22]"},{"why":"Gives the prior deterministic subexponential factoring algorithm for constant-depth circuits whose correctness proof is replaced and whose output is strengthened to constant-depth factor circuits.","marker":"[BKR+25]"},{"why":"Establishes the hardness-randomness trade-off whose transfer to formulas and constant-depth circuits requires exactly the closure property proved here.","marker":"[KI04]"},{"why":"Shows the reduction from deterministic factorization to PIT for general circuits; the paper extends the blackbox version of this connection to formulas and constant-depth circuits.","marker":"[KSS15]"}],"fun_headline_variants":["Furstenberg's 1960s theorem proves closure under factors for circuits","All factors of constant-depth circuits stay constant-depth","A 1960s power-series trick keeps factors of circuits small","Factor closure for constant-depth circuits and formulas via Furstenberg"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof leans on a recent external theorem asserting that, from the coefficients of $f,g,h$, one can build a $\\mathrm{poly}(d)$-size, $O(1)$-depth circuit over the base field for every elementary symmetric polynomial of the values $g(\\alpha_i)/h(\\alpha_i)$ at the roots $\\alpha_i$ of $f$; the closure argument needs this to remain true when $g$ and $h$ are themselves given by constant-depth circuits, and if that uniformity fails the lifting step has a gap.","fun_headline_variants_meta":{"raw":{"variants":["Furstenberg's 1960s theorem proves closure under factors for circuits","All factors of constant-depth circuits stay constant-depth","A 1960s power-series trick keeps factors of circuits small","Factor closure for constant-depth circuits and formulas via Furstenberg"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00087,"raw_usage":{"total_tokens":3827,"prompt_tokens":1062,"completion_tokens":2765,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":678,"completion_tokens_details":{"reasoning_tokens":2692}},"tokens_in":678,"tokens_out":2765,"duration_ms":26488,"temperature":1.0,"reasoning_tokens":2692,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:50:01.040565+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check the theorem on which the lifting step rests at the precise instantiation used here: take $f(z)=z^d-1$ and let $g,h$ be polynomials produced by poly-size constant-depth circuits, then verify that the asserted constant-depth circuit for the elementary symmetric polynomials of $g(\\alpha_i)/h(\\alpha_i)$ exists over the base field without division gates or a PIT oracle. A concrete counterexample at this step, or any explicit family of constant-depth circuits whose irreducible factor can be shown to require super-polynomial size, would refute the main theorem.","supporting_citations":[],"review_version":1}