Deterministic Linear-Factor Extraction for Depth-3 Circuits over Any Field

Randomness is the standard way to check whether a large algebraic expression is secretly zero. Plug in random numbers; if the answer is zero every time, the expression almost certainly is zero. Randomness is also the standard way to break a polynomial into its factors. Removing the randomness from the first task, called polynomial identity testing (PIT), is tied to proving lower bounds on circuit size. Removing it from the second task depends on a structural question: when a polynomial is computed by a small circuit of some restricted shape, are its factors computed by small circuits of a similar shape? This is the closure under factorization question. For general circuits the closure answer is known to be yes. For shallow circuits it is largely open, and almost every closure proof breaks over fields of small characteristic such as $\mathbb{F}_2$ or $\mathbb{F}_3$.

This note proposes a narrow target. Take a depth-3 circuit with top fan-in $k$, a sum of $k$ products of linear forms written $\Sigma\Pi\Sigma(k)$. Given only the ability to evaluate it, the goal is a deterministic algorithm that finds all of its linear factors with multiplicities, over the rationals and over finite fields of small characteristic. The method never lifts a factorization, which is the step that fails in small characteristic. It proposes candidate factors from low-dimensional slices of the polynomial and certifies each one with a deterministic identity test. That certification works because depth-3 circuits remain depth-3 circuits when restricted to a hyperplane. If the method works, it removes the one randomized factoring call in the known reconstruction algorithm for fan-in-2 depth-3 circuits. It would also give the first field-independent constructive closure statement for a class below VP.

Core Claim

The key observation is that, for this class, divisibility by a linear form is an identity test. A linear form $\ell$ divides $f$ exactly when $f$ vanishes on the hyperplane $\ell = 0$. Substituting a parametrization of that hyperplane into a $\Sigma\Pi\Sigma(k)$ circuit with $n$ variables and degree $d$ gives a $\Sigma\Pi\Sigma(k)$ circuit with $n-1$ variables and the same degree. So the explicit hitting set of Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter decides "$\ell \mid f$?" deterministically, over any field, in time $\mathrm{poly}(nd^k)$. A hitting set is a fixed list of evaluation points on which every nonzero circuit in the class is nonzero somewhere.

That paper builds the hitting set from Chinese-remaindering over ideals and a Vandermonde-style map that reduces the number of variables. It solves only the decision problem. We use it as a certifier inside a search procedure.

The search procedure needs candidates, and here we depart from the reduction in Derandomizing Multivariate Polynomial Factoring for Low Degree Factors. That reduction projects to few variables using projections that preserve irreducibility, justified by Hilbert's irreducibility theorem, plus a transformation that makes the polynomial monic. We instead project carelessly and verify afterwards. A linear factor of $f$ always restricts to a linear factor of $f$ on any plane. Spurious linear factors created by the restriction are rejected by the hyperplane test. Correctness therefore never depends on the projection preserving irreducibility. It only requires that, for at least one plane in an explicit family, distinct true factors stay distinguishable.

If $N$ candidates survive slicing, the total cost is

$$ T(n,d,k) \;=\; \mathrm{poly}(n,d)\cdot T_{\mathrm{slice}} \;+\; N \cdot \mathrm{poly}(n d^k), $$

where $T_{\mathrm{slice}}$ is the cost of deterministically factoring one trivariate restriction and $N \le \mathrm{poly}(n,d)$. The second term is the cost of one identity test per candidate, using the bound from Saxena and Seshadhri.

The field regime is chosen deliberately. Deterministic low-variate factoring is available over $\mathbb{Q}$, and over $\mathbb{F}_q$ in time polynomial in the characteristic $p$. That covers exactly the small-characteristic fields where Hensel lifting and Newton iteration degenerate. Large-$p$ finite fields are excluded on purpose. A Guide to Learning Arithmetic Circuits shows that proper reconstruction of multilinear depth-3 circuits over finite fields must compute square roots of field elements, and our algorithm does not escape that barrier. The proposal is consistent with that negative result rather than contradicting it.

Research Program

The first component is the candidate generator. Fix an explicit family of affine planes $P_\beta$, indexed by a parameter $\beta$ drawn from a set of size $\mathrm{poly}(n,d)$, for example a moment-curve construction of the kind used in the variable reduction above. For each plane and each coordinate $i$, restrict $f$ to the three-dimensional space spanned by $P_\beta$ and the $i$-th coordinate direction. Factor that trivariate polynomial deterministically and keep its linear factors.

Because the plane part is shared across all $i$, a factor's restriction to $P_\beta$ acts as a label. Factors with the same label are glued across coordinates, and the coefficient of the $i$-th direction gives $\ell_i$. This is how a full $n$-variate linear form is assembled.

The theorem to prove is completeness. Some $\beta$ in the family keeps all at most $d$ true linear factors pairwise non-proportional on $P_\beta$. The algorithm cannot know the factors, so it does not choose this $\beta$. It runs on every $\beta$, and the certification step makes the union of verified outputs exactly the true set. Each "two factors collide" event is a nonzero low-degree polynomial condition in $\beta$, which is why a polynomial-size parameter set should suffice.

The second component handles multiplicities, which is where small characteristic bites. The usual test asks whether $f$ and its derivatives vanish on the hyperplane. Over $\mathbb{F}_p$ that test fails, because $\ell^p$ has zero derivative. Interpolating Hasse derivatives instead blows the top fan-in up from $k$ to roughly $dk$, which is unaffordable.

Our plan is to test membership of $f$ in the ideal generated by $\ell^e$ directly. The Saxena–Seshadhri machinery already decides whether a circuit is zero modulo ideals built from powers of linear forms, so the work is to verify that their analysis covers this case without inflating $k$. This is the main technical risk. If it fails, the fallback is the weaker result: the set of distinct linear factors, together with multiplicity upper bounds read off the slices.

The third component addresses the closure question. Once $\ell \mid f$ is certified, how complex is the cofactor $f/\ell$? Black-box evaluation of $f/\ell$ off the hyperplane is free. The open question is whether $f/\ell$ again has a small depth-3 circuit, which is an instance of the "classes below VP" problem raised in Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring.

The certification gives structure to work with. When $\ell \mid f$, the restriction of $f$ to $\ell = 0$ is a depth-3 identity. Over $\mathbb{Q}$, the rank bound of From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits says the simple part of such an identity spans only $O(k^2)$ dimensions. We aim to convert this into a depth-3 representation of $f/\ell$ whose top fan-in depends only on $k$ and that rank. That would be a closure-under-linear-division theorem with no Hensel lifting. Over other fields the rank bounds are weaker, and we will report whatever dependence results.

The fourth component is the application. Reconstruction of Real depth-3 Circuits with top fan-in 2 writes $f = G\cdot(T_0+T_1)$ and calls Kaltofen's randomized factoring to isolate the common factor $G$. Our extractor returns every linear factor. These must then be split between $G$ and any linear factors of $T_0+T_1$. We will check deterministically whether a candidate split is consistent using the same restriction-based tests. We will also audit the rest of Sinha's pipeline for hidden randomness, and report honestly whether the whole reconstruction becomes deterministic or only its factoring step.

Baselines

The naive reference is exhaustive search over a small finite field. Enumerate every linear form over $\mathbb{F}_q$ up to scaling, about $q^n$ candidates, and certify each with the same hitting-set test. It is trivially correct, so it serves as ground truth where it is feasible ($q \le 5$, $n \le 8$). Its cost is the curve our method must beat.

The strongest practical competitor is randomized factoring of the black-box polynomial (Kaltofen-style, as used by Sinha) run with the same evaluation oracle and a matched query budget. It is the method our algorithm would replace. Beating it does not mean being faster. It means matching its output exactly while using no random bits, and continuing to work on the small-characteristic, high-multiplicity instances where its lifting step must be specially patched.

The strongest existing deterministic method is the reduction in Derandomizing Multivariate Polynomial Factoring for Low Degree Factors, instantiated with the depth-3 hitting set. That paper reports polynomial time for polynomials whose factors all have constant degree and subexponential time for constant-depth circuits. The file gives no explicit exponents and no empirical runtimes: no reported result found on Lacuna for an instantiation on $\Sigma\Pi\Sigma(k)$ circuits. We will implement it with the same oracle and the same deterministic low-variate factoring routine, so that any difference comes from the projection-plus-lifting strategy and not from the subroutines. Our method beats it if it is correct on instance families where its irreducibility-preserving projections or monic transformation need field extensions or fail over $\mathbb{F}_2$ and $\mathbb{F}_3$, or if it does the same with fewer queries.

The ablation that isolates our key ingredient removes certification. It outputs every linear factor found on a single plane, as if the projection preserved factor structure. Counting the false factors it reports shows how much of the method's correctness comes from the restriction-closure test rather than from a lucky choice of projection.

Why not just…?

Why not just use randomized factoring, since it already works? For computation, randomized factoring is fine and remains our ground-truth oracle. The motivation is structural. Deterministic algorithms of this kind are the route by which closure results feed lower bounds and derandomization: Closure Results for Polynomial Factorization turns closure for bounded-depth circuits into deterministic PIT. A deterministic reconstruction for fan-in-2 depth-3 circuits is also a concrete gap that Sinha's paper leaves open. A randomized algorithm cannot certify that a factor's structure stays inside the class, which is what the closure statement in the third component of the research program needs.

Why not just instantiate the Dutta–Sinhababu–Thierauf reduction with the depth-3 hitting set? This is the real threat. If every operation their reduction applies to $f$ keeps it inside $\Sigma\Pi\Sigma(k)$ with the original $k$, and their projections work over small finite fields without large extensions, then our first component is a corollary of their work. The first deliverable of the project is therefore a written check of exactly this. If the instantiation goes through, we drop the first component as a contribution. The proposal then rests on the small-characteristic multiplicity test and the cofactor closure theorem, which that reduction does not supply. The file notes that it leaves deterministic divisibility testing open.

Why not just use Hensel lifting or Newton iteration, as the closure literature does? The papers that built this machinery state that it requires characteristic zero or characteristic larger than $d$. These include Some Closure Results for Polynomial Factorization and Applications and the all-roots Newton iteration in the "Discovering the Roots" paper. Below that threshold derivatives vanish and multiplicities degenerate. Our design avoids lifting entirely, so this failure mode does not arise. The experiments include $\ell^p$-type instances specifically to show where lifting-based baselines need repair and ours does not.

Why not just use Sylvester–Gallai rank bounds directly? Those incidence-geometry arguments are field-dependent. Saxena and Seshadhri abandoned them for ideal theory in order to work over every field, and Sinha reports that they become unmanageable for $k \ge 3$. We use rank bounds only in the cofactor analysis over $\mathbb{Q}$, never in the algorithm.

Proposed Experiments

This work is primarily theoretical, and the decisive outputs are proofs. They are the completeness lemma for the plane family, the multiplicity test modulo $\ell^e$, and the cofactor bound. The empirical component exists to falsify these claims early.

We will implement the method in a computer algebra system. No benchmark in the file targets arithmetic circuits. ASyMOB (ASyMOB) measures symbolic calculus by language models, so we will build synthetic suites instead.

The suites are random $\Sigma\Pi\Sigma(k)$ circuits for $k \in \{2,3,4\}$ over $\mathbb{Q}$, $\mathbb{F}_2$, $\mathbb{F}_3$ and $\mathbb{F}_7$, with planted linear factors. They also include adversarial families. One plants many near-proportional factors to stress the plane family. One plants $p$-th powers $\ell^p$ to stress the multiplicity test. One builds $T_0+T_1$ with linear factors outside $G$, which mimics the ambiguity in Sinha's setting.

The metrics are exact agreement of the factor set and multiplicities with the randomized ground truth and with exhaustive search where feasible, the number of evaluations of $f$, and runtime as $n$, $d$ and $k$ grow.

The decisive checks are as follows. The union over planes must never miss a planted factor. If it does, the completeness lemma is false as stated. The single-plane ablation must report false factors at a measurable rate, which would show that certification matters. Over $\mathbb{F}_2$ and $\mathbb{F}_3$, the method must recover multiplicities on the $\ell^p$ family, the case where derivative-based tests fail. Query counts should grow like $d^k$ times a polynomial, matching the cost formula above, rather than like $q^n$.