Hitting sets From Derivations: Waring Rank and Noncommutative ABPs

arXiv:2609.34436 · cs.CC · Submitted 2026-09-28 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Hitting sets From Derivations".

Jane: Here's the gist of the paper. We give an explicit hitting set of size poly(n, d,r) for the class of n-variate degree-d polynomials whose partial derivative space is bounded by r, over any field F of characteristic zero <ref:2609.34436#pg11>.

Tom: In particular, this yields a polynomial sized hitting set for the class of depth-3 powering circuits <ref:2609.34436#pg12>.

Jane: The Core Result The main result of this paper is an explicit polynomial-sized hitting set for this class of polynomials over a characteristic zero field <ref:2609.34436#pg13>.

Tom: Theorem 1.1 states that there is an explicit polynomial map (G1(t),..., Gn(t)) in F

t: n with deg Gi ≤ O(nr2) such that if f(x1,..., xn) is a polynomial such that dim ∂∗ f ≤ r, then f(x1,..., xn) = 0 ⇔ f(G1(t),..., Gn(t)) = 0 <ref:2609.34436#pg14>.

Title and authors: Tom: So Jane, this paper "Hitting sets From Derivations: Waring Rank and Noncommutative ABPs" gives us a way to find these hitting sets for polynomials whose partial derivative space is small.

Jane: Right, so the main thing here is that they give us an explicit polynomial sized hitting set for any n-variate degree d polynomials where the partial derivative space is bounded by some number r, over any field with characteristic zero.

Lu: What's interesting about this specific result is that it shows this construction works even for a particular class called depth-three powering circuits, which the paper links directly to polynomial sized hitting sets <ref:2609.34436#pg1>.

Meng: I want to know what the practical implications are for something like training models at scale. If we can find these small hitting sets, does that mean we can effectively control or test these complex polynomial structures in a way that keeps things manageable?

Lalam: I'm looking at how they construct this hitting set, and it seems to rely on building a specific type of formal derivation and then using the properties of an associated Wronskian with respect to that derivation.

Tom: A Wronskian argument sounds complicated, but I see they are using this Wronskian to prove a final contradiction that shows the polynomial isn't zero modulo some number B.

Jane: So they use this derivation and the Wronskian to show that if the original polynomial is zero, then a certain related function has some property modulo B, but they show it doesn't because of how big B is compared to r and d.

Lu: The trick there seems to be relating the derivative of the composed function back to this formal derivation using a specific map defined by power series.

Meng: And this map they use is related to those power series we see in other works, like the one with ln(one minus it) <ref:2609.34436#pg1>. It seems like they are building a test that scales nicely with n, d, and r.

Lalam: The structure of this map is defined by Pi t equals negative log of one minus i t for each index i from one to n. This gives us a set of algebraically independent power series that are key to the construction.

Tom: Okay, so what's the actual improvement they suggest over previous work? I remember something about how this new approach simplifies things compared to older methods in circuit complexity.

Jane: They suggest an explicit hitting set construction based on this formal derivation, which is different from the randomized PIT algorithms they mention earlier, providing a deterministic path.

Lu: The paper notes that the proofs for this result are elementary and completely self-contained, which means you don't need to be an expert in those very specific contexts to follow the logic.

Meng: That’s helpful for production because it means we can actually trust the mechanics without needing a deep dive into specialized literature just to verify the construction itself.

Lalam: And they state that this explicit hitting set yields a poly(n, d,s) sized hitting set for depth-three powering circuits, which is what we were aiming for in terms of circuit analysis <ref:2609.34436#pg1>.

Tom: So the main takeaway is that by using this formal derivation and Wronskian argument, they get a concrete polynomial size hitting set for these polynomial classes.

Jane: It means we have a better tool to check if these complex polynomial structures are zero without having to evaluate them everywhere, relying instead on this specific transformation.

Lu: For the future work, the paper points toward how this relates to lower bounds and deterministic PITs, suggesting that strong circuit lower bounds can lead to efficient tests.

Meng: If we can use these hitting sets effectively for testing, it could mean we can build more robust methods for verifying model properties at scale, even when the underlying structure is complex.

Lalam: The paper also touches on how this relates to the idea that lower bounds and PITs are intimately connected, which is a big piece of context for anyone studying circuit complexity.

Tom: To wrap up, "Hitting sets From Derivations: Waring Rank and Noncommutative ABPs" gives us an explicit way to find a polynomial sized hitting set for degree d polynomials with bounded partial derivative spaces.

Jane: It's a significant step because it provides an explicit construction using a formal derivation and Wronskian that connects the polynomial structure directly to this hitting set size bound.

Lu: And this method is elementary, which makes it much more accessible for researchers looking to apply these ideas in other areas of algebraic circuit analysis.

Meng: From an engineering standpoint, having a constructive proof like this means we have a reliable way to handle the complexity without relying on probabilistic methods that might not hold up in real deployment scenarios.

Lalam: The paper also connects this result to how lower bounds and deterministic polynomial identity tests are related, which is crucial context for understanding the connection between circuit size and test efficiency.

The paper's summary: Tom: So what we’re looking at here is this paper about finding explicit hitting sets for polynomials, specifically for these depth-three powering circuits where the partial derivative space is bounded by some number r over a field with no characteristic zero.

Jane: Right, so it seems they took this idea of a formal derivation and built a specific map—a transformation—that lets you check if that polynomial equals zero by just looking at something else.

Tom: Exactly. The big result is that they build an explicit hitting set for the class of size s, degree d depth-three powering circuits where the size s is bounded by something like n times r squared plus r cubed.

Lu: What I find really interesting is how they use this formal derivation and an associated Wronskian—which is a bunch of derivatives used to check independence—to show that if the original polynomial isn't zero, then a certain related function has some property modulo B.

Meng: So instead of just testing the whole massive polynomial, you’re looking at this derived function and seeing how it behaves with respect to this specific operator D.

Jane: And they prove that because of how big the number B is compared to n, d, and r, that function can't be zero modulo B unless the original polynomial actually was zero.

Tom: It’s a really neat contradiction based on the growth rates—the error term in their analysis doesn't let anything sneak through.

Jane: It means we get a concrete way to test these complex algebraic structures without having to search the entire space, which is something we always want when dealing with these massive polynomial expressions.

Lu: This method is completely self-contained; they don't rely on some huge external machinery, just their derivation and Wronskian properties.

Meng: That’s good for us because if it's explicit and elementary, we can actually try to use it to build a production system rather than just relying on theoretical guarantees.

Tom: So the main thing here is that we have this constructive tool—this polynomial sized hitting set—that works for these specific circuit classes, which is a big deal for understanding the limits of polynomial representation.

Jane: And this sets us up nicely because we’re going to talk next about how these kinds of explicit tests can actually be used to generate deterministic identity tests for polynomials where the partial derivative space is small.

The paper's improvements: Tom: So we just covered how they build an explicit hitting set for these depth-three powering circuits using this formal derivation and Wronskian argument over a field with no characteristic zero.

Jane: That was a lot of math, but essentially, they showed you can use this transformation to create a polynomial sized test for these complex structures.

Tom: Exactly. The improvement they’re highlighting is that this method is deterministic; it gives you a concrete construction instead of relying on some randomized tests or probabilistic guarantees.

Lu: What's really important here is the connection they draw between this hitting set size and lower bounds on certain circuit classes, which links polynomial testing to fundamental complexity questions.

Meng: For us in engineering, that’s huge because it means if we can prove a lower bound on how complex a model structure needs to be, this paper gives us a tool to actually check if it’s there efficiently.

Jane: They also point out that this framework is very general; the same idea works for any class of polynomials whose partial derivative space is bounded by some number r, over any field with no characteristic zero.

Tom: So the implication is that we don't need to worry about the specific structure of the polynomial as much as we do about how constrained its derivative space is.

Lu: They are also touching on how this relates to lower bounds and deterministic polynomial identity tests, suggesting that if you have a strong lower bound on a circuit, you can get an efficient test for it.

Meng: I’m interested in the practical application here; if we know something about the complexity of a model structure, this paper suggests we might be able to build tests that scale well with n and d.

Jane: It means that for someone just listening, the big idea is that these advanced mathematical tools can give us a reliable way to verify complicated polynomial relationships in a manageable time frame.

Tom: They’re essentially saying we have moved from maybe having some randomized identification tests to having an explicit, constructive way to find the right polynomials that are zero.

Lu: And this moves the needle on understanding how deep these circuit classes actually are, by providing a concrete method for checking their zero property.

Meng: It’s good because it’s not just theoretical; it’s about having a reliable mechanism to check things at scale, even if we don't know the absolute best complexity bounds yet.

Conclusion: Tom: So to wrap up, this paper "Hitting sets From Derivations: Waring Rank and Noncommutative ABPs" gives us an explicit, polynomial sized hitting set for these depth-three powering circuits when the partial derivative space is bounded by some number r over a field with no characteristic zero.

Jane: It means we have a reliable construction, not just a theoretical idea, to check if these kinds of complex polynomials are actually zero without having to test every single point in the space.

Tom: Exactly. This explicit hitting set construction using the formal derivation and Wronskian argument is pretty clean for someone who wants to see how the mechanics work on paper.

Lu: I think it’s important because it ties these polynomial properties directly into lower bounds on circuit complexity, which is a big piece of context for where we are in this field.

Meng: For production, having an explicit construction means we can actually try to deploy tests based on these bounds, even if the size scales with n and r squared.

Lalam: I’m confident in this result because the proof is self-contained, and it connects directly to how we think about testing things at a fundamental level.

Jane: It's a significant step because it provides an explicit construction using a formal derivation and Wronskian that connects the polynomial structure directly to this hitting set size bound.

Tom: Yeah, so the main thing here is that we have moved from maybe having some randomized identification tests to having an explicit, constructive way to find the right polynomials that are zero.

Lu: This method is elementary, which makes it much more accessible for researchers looking to apply these ideas in other areas of algebraic circuit analysis.

Meng: From an engineering standpoint, having a constructive proof like this means we have a reliable way to handle the complexity without relying on probabilistic methods that might not hold up in real deployment scenarios.

Jane: And this sets us up nicely because we’re going to talk next about how these kinds of explicit tests can actually be used to generate deterministic identity tests for polynomials where the partial derivative space is small.

Shubham Bhardwaj, Ramprasad Saptharishi

Tata Institute of Fundamental Research · Department of Atomic Energy, Government of India · Google · SERB Research Grants

cs.CC

Submitted: 2026-09-28

Updated: 2026-11-08

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: We give an explicit hitting set of size poly(n, d,r) for the class of n-variate degree-d polynomials whose partial derivative space is bounded by r…

Key concepts

Partial Derivative Space Dimension
This refers to the dimension of the space spanned by all possible partial derivatives of a polynomial. The paper shows that for certain polynomial classes, this space is bounded by $r$. This bound is crucial because it allows for the construction of a hitting set whose size depends polynomially on $n$, $d$, and this bound $r$.
Formal Derivation D
This is a specific differential operator defined as $D := Q(t) rac{d}{dt} + ext{terms involving } rac{ ext{bi}(t)}{1-it}$. It has the property that its kernel is the base field $F$, meaning it acts non-trivially on functions. This derivation is used to analyze the structure of polynomials related to the hitting set.
D-Wronskian
The D-Wronskian, denoted WD($g_1, ext{...}, g_r$), is a determinant constructed using a basis of partial derivatives ($g_i$) and the formal derivation $D$. If the derivation has a trivial field of constants, this Wronskian being non-zero guarantees that the chosen set of derivatives is linearly independent.
Depth-3 Powering Circuits
These circuits are a computational analogue to Waring rank. They involve expressing a polynomial as a sum of powers of linear forms, where the depth constraint limits how complex these expressions can be. The paper provides an explicit hitting set for this class, which is important for understanding the complexity of these circuits.

Terminology

Summary

We give an explicit hitting set of size poly(n, d,r) for the class of n-variate degree-d polynomials whose partial derivative space is bounded by r, over any field F of characteristic zero <ref:2609. p. 0

Where the paper says it

Hitting Sets for Polynomials with Small Partial Derivative Spaces Shubham Bhardwaj* Ramprasad Saptharishi* 28 September 2026 Abstract We give an explicit hitting set of size poly(n, d,r) for the class of n-variate degree-d polynomials whose partial derivative space is bounded by r, over any field F of characteristic zero. In particular, this yields a polynomial sized hitting set for the class of depth-3 powering circuits.

34436#pg11>. In particular, this yields a polynomial sized hitting set for the class of depth-3 powering circuits <ref:2609. p. 0
Where the paper says it

Hitting Sets for Polynomials with Small Partial Derivative Spaces Shubham Bhardwaj* Ramprasad Saptharishi* 28 September 2026 Abstract We give an explicit hitting set of size poly(n, d,r) for the class of n-variate degree-d polynomials whose partial derivative space is bounded by r, over any field F of characteristic zero. In particular, this yields a polynomial sized hitting set for the class of depth-3 powering circuits.

34436#pg12>.

The Core Result

The main result of this paper is an explicit polynomial-sized hitting set for this class of polynomials over a characteristic zero field <ref:2609. p. 1

Where the paper says it

It continues to remain open if such polynomials with low-dimensional space of partial derivatives admit a not-too-large representation as a depth-3 powering circuit. The main result of this paper is an explicit polynomial-sized hitting set for this class of polynomials over a characteristic zero field.

p. 1
Where the paper says it

It continues to remain open if such polynomials with low-dimensional space of partial derivatives admit a not-too-large representation as a depth-3 powering circuit. The main result of this paper is an explicit polynomial-sized hitting set for this class of polynomials over a characteristic zero field.

p. 1
Where the paper says it

It continues to remain open if such polynomials with low-dimensional space of partial derivatives admit a not-too-large representation as a depth-3 powering circuit. The main result of this paper is an explicit polynomial-sized hitting set for this class of polynomials over a characteristic zero field.

34436#pg13>. Theorem 1.1 states that there is an explicit polynomial map (G1(t),. p. 1
Where the paper says it

Let F be a field of characteristic zero. For any n,r ≥ 0, there is an explicit polynomial map (G1(t), .

.., Gn(t)) in F[t]n with deg Gi ≤ O(nr2) such that if f(x1,. p. 1
Where the paper says it

For any n,r ≥ 0, there is an explicit polynomial map (G1(t), . , Gn(t)) ∈ F[t] n with deg Gi ≤ O(nr2 ) such that if f(x1, .

.., xn) is a polynomial such that dim ∂∗ f ≤ r, then f(x1,. p. 2
Where the paper says it

dim ∂ ∗ f ≤ r, then f(x1, . , xn) = 0 ⇔ f(G1(t), .

.., xn) = 0 ⇔ f(G1(t),..., Gn(t)) = 0 <ref:2609. p. 0
Where the paper says it

Research supported by the Department of Atomic Energy, Government of India, under project number RTI400112, and Google and SERB Research Grants. 1 arXiv:2609.

34436#pg14>. This construction yields a poly(n, d,s)-sized hitting set for the class of size s, degree d depth-3 powering circuits. p. 0
Where the paper says it

Hitting Sets for Polynomials with Small Partial Derivative Spaces Shubham Bhardwaj* Ramprasad Saptharishi* 28 September 2026 Abstract We give an explicit hitting set of size poly(n, d,r) for the class of n-variate degree-d polynomials whose partial derivative space is bounded by r, over any field F of characteristic zero. In particular, this yields a polynomial sized hitting set for the class of depth-3 powering circuits.

The Technical Insight

The main technical insight is the construction of a “formal derivation” and properties of the associated Wronskian with respect to this derivation, which was previously studied by Moura [Mou04] in a very different context <ref:2609.34436#pg12>. The proofs in this paper are elementary and completely self-contained <ref:2609. p. 0

Where the paper says it

The main technical insight is the construction of a “formal derivation” and properties of the associated Wronskian with respect to this derivation, which was previously studied by Moura [Mou04] in a very different context. The proofs in this paper are elementary and completely self-contained.

34436#pg12>.

The Derivation Machinery

The construction relies on a specific derivative operator D˜:= ∂t + n∑i=1 i(i-t) · ∂xi which indeed has the property that ker D˜ = F. This derivation is then extended to a derivation D:= Q(t) · D˜ = Q(t) · ∂t + n∑i=1 bi(t) · ∂xi (2. p. 0

Where the paper says it

In particular, this yields a polynomial sized hitting set for the class of depth-3 powering circuits. The main technical insight is the construction of a “formal derivation” and properties of the associated Wronskian with respect to this derivation, which was previously studied by Moura [Mou04] in a very different context.

p. 0
Where the paper says it

In particular, this yields a polynomial sized hitting set for the class of depth-3 powering circuits. The main technical insight is the construction of a “formal derivation” and properties of the associated Wronskian with respect to this derivation, which was previously studied by Moura [Mou04] in a very different context.

p. 0
Where the paper says it

In particular, this yields a polynomial sized hitting set for the class of depth-3 powering circuits. The main technical insight is the construction of a “formal derivation” and properties of the associated Wronskian with respect to this derivation, which was previously studied by Moura [Mou04] in a very different context.

4), where Q(t) = ∏ n i=1 (1 − it) and bi(t) = i · Q(t)/(1 − it), which has a trivial field of constants. p. 5
Where the paper says it

For a derivation D, we define its field1 of constants to be the set ker D = {h ∈ K : D(h) = 0}. We shall say that D has a trivial field of constants if ker D = F.

p. 5
Where the paper says it

For a derivation D, we define its field1 of constants to be the set ker D = {h ∈ K : D(h) = 0}. We shall say that D has a trivial field of constants if ker D = F.

p. 5
Where the paper says it

For a derivation D, we define its field1 of constants to be the set ker D = {h ∈ K : D(h) = 0}. We shall say that D has a trivial field of constants if ker D = F.

Lemma 2.6 establishes that D has a trivial field of constants. p. 5
Where the paper says it

For a derivation D, we define its field1 of constants to be the set ker D = {h ∈ K : D(h) = 0}. We shall say that D has a trivial field of constants if ker D = F.

The Wronskian Argument

The proof proceeds by considering the D-Wronskian WD(g1,..., gr) of a basis g1,. p. 3

Where the paper says it

, xn) is a nonzero polynomial with low dimensional partial derivative space, and say g1, . , gr is a basis of ∂ =∗ (f) with gr = f .

.., gr of ∂=∗(f). Lemma 2.2 asserts that if D has a trivial field of constants, then g1,. p. 5
Where the paper says it

For a derivation D, we define its field1 of constants to be the set ker D = {h ∈ K : D(h) = 0}. We shall say that D has a trivial field of constants if ker D = F.

.., gm are F-linearly independent if and only if the D-Wronskian (denoted by WD(g1,. p. 5
Where the paper says it

, gm ∈ R, we have that g1, . , gm are F-linearly independent if and only if the D-Wronskian (denoted by WD(g1, .

.., gm)) is nonzero. p. 2
Where the paper says it

They show that if f(x1, . , xn) is a nonzero polynomial, then f(± √ p1,1 ± · · · ± √ p1,ℓ , · · · , ± √ pn,1 ± · · · ± √ pn,ℓ) ̸= 0 where pi,j ’s are distinct primes with ℓ = O(log deg(f)).

Lemma 2.9 shows that for a derivative-closed set, WD(g1,. p. 9
Where the paper says it

That completes the inductive step, and thus the proof of the corollary. 3 D-Wronskian of a derivative-closed set The following is a simple yet important observation that makes the above machinary applicable to the setting of polynomials of low dimensional partial derivative space.

.., gm) is a rational function in t and is independent of the xi’s. p. 9
Where the paper says it

Then, the D-Wronskian WD(g1, . , gm) is a rational function in t and is independent of the xi ’s.

The Final Contradiction

By observing that WD(g1,..., gr) ◦ P = w(t), where w is a nonzero polynomial in t, and using Corollary 2. p. 2

Where the paper says it

Using power series for constructing hitting-set generators: The general structure of constructing a hitting-set generator via power series is reminiscent of the randomised PIT algorithms of Chen and Kow [CK97], or Lewin and Vadhan [LV98]. We describe the setting of [CK97] (the setting of [LV98] is very similar with irreducible polynomial playing the role of primes).

8, it is shown that f ◦ P is not divisible by tB for B = nr2 + r <ref:2609. p. 0
Where the paper says it

Research supported by the Department of Atomic Energy, Government of India, under project number RTI400112, and Google and SERB Research Grants. 1 arXiv:2609.

34436#pg12>. This leads to the conclusion that f(P1(t), · · ·, Pn(t)) ≠ 0 mod tB. p. 2
Where the paper says it

For the class of polynomials with lowdimensional partial derivative space, we show that 0 ̸= f =⇒ f(P1(t), . , Pn(t)) ̸= 0 mod t B for a not-too-large B.

How the training signal is built

The map (P1,..., Pn) is defined as Pi(t) = ∑j≥1 (it) j j = − ln(1 − it). p. 6

Where the paper says it

There appears to be a rich literature on the study of derivation fields with numerous examples of derivations that have a trivial field of constants. The derivation defined above appears to be a special case of a broader class of derivations called Shamsuddin derivations.

The proof uses Lemma 2. p. 9
Where the paper says it

, xn], if f ◦ P = 0 mod t B then Di (f) ◦ P = 0 mod t B−i . The proof follows by induction on i via applications of Lemma 2.

7 to relate the derivative of the composition f ◦ P to D(f) ◦ P, showing that Q(t) · d/dt (f ◦ P) = D(f) ◦ P as elements of FJtK <ref:2609. p. 8
Where the paper says it

, xn], the composition f ◦ P = f(P1, . , Pn) is a well-defined element of FJtK.

34436#pg11>.

Where the gains come from

The final contradiction arises because if f ◦ P were divisible by tB, then w(t), which is a polynomial of degree at most nr2, would have to be divisible by tB−(r-1). This is impossible when B ≥ nr2 + r. p. 1

Where the paper says it

For any n,r ≥ 0, there is an explicit polynomial map (G1(t), . , Gn(t)) ∈ F[t] n with deg Gi ≤ O(nr2 ) such that if f(x1, .

p. 1
Where the paper says it

For any n,r ≥ 0, there is an explicit polynomial map (G1(t), . , Gn(t)) ∈ F[t] n with deg Gi ≤ O(nr2 ) such that if f(x1, .

Pruning redundant reasoning tokens

The authors note that the proofs in this paper are elementary and completely self-contained <ref:2609.34436#pg12>. The AI disclosure states that the proof of this result was obtained during conversations [Ast26] with OpenAI GPT-6 Astra <ref:2609. p. 0

Where the paper says it

The proofs in this paper are elementary and completely self-contained. AI disclosure: The proof of this result was obtained during conversations [Ast26] with OpenAI GPT-6 Astra.

34436#pg12>.

The key weakness of the above model that enabled all the lower bounds and PITs was the observation that any k-th order partial derivative of f = c1l d 1 + · · · + csl d s is a linear combination of l(d-k) 1,..., l(d-k) s and thus the space of all possible partial derivatives of f (which we shall denote by ∂=∗(f)) is only O(sd)-dimensional. p. 1

Where the paper says it

The key weakness of the above model that enabled all the lower bounds and PITs was the observation that any k-th order partial derivative of f = c1ℓ d 1 + · · · + csℓ d s is a linear combination of ℓ d−k 1 , . , ℓ d−k s and thus the space of all possible partial derivatives of f (which we shall denote by ∂ =∗ (f)) is only O(sd)-dimensional.

p. 1
Where the paper says it

The key weakness of the above model that enabled all the lower bounds and PITs was the observation that any k-th order partial derivative of f = c1ℓ d 1 + · · · + csℓ d s is a linear combination of ℓ d−k 1 , . , ℓ d−k s and thus the space of all possible partial derivatives of f (which we shall denote by ∂ =∗ (f)) is only O(sd)-dimensional.

The key weakness of the above model that enabled all the lower bounds and PITs was the observation that any k-th order partial derivative of f = c1l d 1 + · · · + csl d s is a linear combination of l(d-k) 1,..., l(d-k) s and thus the space of all possible partial derivatives of f (which we shall denote by ∂=∗(f)) is only O(sd)-dimensional.

The class of depth-3 powering circuits is the circuit analogue of the classical notion of Waring rank, where the Waring rank of a polynomial f is the smallest s such that f can be written as sum of s powers of linear forms.

The class of depth-3 powering circuits is the circuit analogue of the classical notion of Waring rank, where the Waring rank of a polynomial f is the smallest s such that f can be written as sum of s powers of linear forms.

The class of depth-3 powering circuits has been just shy of a full resolution. The main result of this paper is an explicit polynomial-sized hitting set for this class of polynomials over a characteristic zero field <ref:2609.34436#pg13>.

The class of depth-3 powering circuits has been just shy of a full resolution. The main result of this paper is an explicit polynomial-sized hitting set for this class of polynomials over a characteristic zero field <ref:2609.34436#pg13>.

The authors thank several members in the community (especially Robert Andrews, Umang Bhaskar, Prerona Chatterjee, Prahladh Harsha, Mrinal Kumar, Anamay Tengse) for numerous philophical discussions on whether to not to publish this <ref:2609.34436#pg12>. The authors also thank the Simons Institute for the Theory of Computing for providing access to ChatGPT Astra to a friend of ours <ref:2609. p. 0

Where the paper says it

AI disclosure: The proof of this result was obtained during conversations [Ast26] with OpenAI GPT-6 Astra. The proof presented in this writeup is a rewriting (in the authors’ words) of the proof obtained by the AI model in a form that we believe is understandable to researchers.

p. 0
Where the paper says it

AI disclosure: The proof of this result was obtained during conversations [Ast26] with OpenAI GPT-6 Astra. The proof presented in this writeup is a rewriting (in the authors’ words) of the proof obtained by the AI model in a form that we believe is understandable to researchers.

34436#pg12>.

The authors thank several members in the community (especially Robert Andrews, Umang Bhaskar, Prerona Chatterjee, Prahladh Harsha, Mrinal Kumar, Anamay Tengse) for numerous philophical discussions on whether to not to publish this <ref:2609.34436#pg12>. The authors also thank the Simons Institute for the Theory of Computing for providing access to ChatGPT Astra to a friend of ours <ref:2609.34436#pg12>.

The paper discusses lower bounds and PITs, noting that they are intimately connected <ref:2609.34436#pg11>. Several classical results show that a strong enough lower bound for circuits can be used to obtain efficient deterministic polynomial identity tests, and vice-versa <ref:2609. p. 1

Where the paper says it

Although the questions of proving lower bounds and constructing deterministic PITs appear to be of very different flavours, they are intimately connected to each other. Several classical results [HS80, Agr05, KI04, CKS19, GKSS19] show that a strong enough lower bound for circuits can be used to obtain efficient deterministic polynomial identity tests, and vice-versa.

34436#pg11>.

The class of depth-3 powering circuits has been just shy of a full resolution. The main result of this paper is an explicit polynomial-sized hitting set for this class of polynomials over a characteristic zero field <ref:2609.34436#pg13>.

The authors describe the PIT in this paper as similar in the sense that the generator is a set of algebraically independent power series (Pi(t):= − log(1 − it): i ∈ [n]) <ref:2609.34436#pg11>.

The authors describe the PIT in this paper as similar in the sense that the generator is a set of algebraically independent power series (Pi(t):= − log(1 − it): i ∈ [n]) <ref:2609.34436#pg11>.

The authors use a specific derivative operator D˜:= ∂t + n∑i=1 i(i-t) · ∂xi which indeed has the property that ker D˜ = F. This derivation is then extended to a derivation D:= Q(t) · D˜ = Q(t) · ∂t + n∑i=1 bi(t) · ∂xi (2.4), where Q(t) = ∏ n i=1 (1 − it) and bi(t) = i · Q(t)/(1 − it), which has a trivial field of constants.

The authors use a specific derivative operator D˜:= ∂t + n∑i=1 i(i-t) · ∂xi which indeed has the property that ker D˜ = F. This derivation is then extended to a derivation D:= Q(t) · D˜ = Q(t) · ∂t + n∑i=1 bi(t) · ∂xi (2.4), where Q(t) = ∏ n i=1 (1 − it) and bi(t) = i · Q(t)/(1 − it), which has a trivial field of constants.

The paper connects the derivation to the map P with Pi = ∑j≥1 (it) j j = − ln(1 − it). Lemma 2.7 shows that for any f(t, x1,. p. 5

Where the paper says it

♢ The notion of D-Wronskian, which is a generalisation of standard Wronskians in the context of a derivation, was studied by Moura [Mou04] in the context of hyperelliptic integrals. The following lemma shows that D-Wronskians also capture linear independence, provided D has a trivial field of constants.

p. 5
Where the paper says it

♢ The notion of D-Wronskian, which is a generalisation of standard Wronskians in the context of a derivation, was studied by Moura [Mou04] in the context of hyperelliptic integrals. The following lemma shows that D-Wronskians also capture linear independence, provided D has a trivial field of constants.

.., xn) ∈ F[t][x1,..., xn], Q(t) · d/dt (f ◦ P) = D(f) ◦ P as elements of FJtK. p. 8
Where the paper says it

, xn) ∈ F[t][x1, . , xn], we have Q(t) · d dt (f ◦ P) = D(f) ◦ P as elements of FJtK.

p. 8
Where the paper says it

, xn) ∈ F[t][x1, . , xn], we have Q(t) · d dt (f ◦ P) = D(f) ◦ P as elements of FJtK.

The paper connects the derivation to the map P with Pi = ∑j≥1 (it) j j = − ln(1 − it). Lemma 2.7 shows that for any f(t, x1,..., xn) ∈ F[t][x1,..., xn], Q(t) · d/dt (f ◦ P) = D(f) ◦ P as elements of FJtK.

The proof uses induction on i via applications of Lemma 2.7 to prove Corollary 2. p. 9

Where the paper says it

Corollary 2. For any B ≥ i ≥ 0 and f(t, x1, .

p. 9
Where the paper says it

Corollary 2. For any B ≥ i ≥ 0 and f(t, x1, .

p. 9
Where the paper says it

Corollary 2. For any B ≥ i ≥ 0 and f(t, x1, .

p. 9
Where the paper says it

Corollary 2. For any B ≥ i ≥ 0 and f(t, x1, .

8, which states that if f ◦ P = 0 mod tB then Di(f) ◦ P = 0 mod tB−i <ref:2609. p. 2
Where the paper says it

For the class of polynomials with lowdimensional partial derivative space, we show that 0 ̸= f =⇒ f(P1(t), . , Pn(t)) ̸= 0 mod t B for a not-too-large B.

p. 2
Where the paper says it

For the class of polynomials with lowdimensional partial derivative space, we show that 0 ̸= f =⇒ f(P1(t), . , Pn(t)) ̸= 0 mod t B for a not-too-large B.

p. 2
Where the paper says it

For the class of polynomials with lowdimensional partial derivative space, we show that 0 ̸= f =⇒ f(P1(t), . , Pn(t)) ̸= 0 mod t B for a not-too-large B.

34436#pg12>.

The proof uses induction on i via applications of Lemma 2.7 to prove Corollary 2.8, which states that if f ◦ P = 0 mod tB then Di(f) ◦ P = 0 mod tB−i <ref:2609.34436#pg12>.

The proof uses induction on i via applications of Lemma 2.7 to prove Corollary 2.8, which states that if f ◦ P = 0 mod tB then Di(f) ◦ P = 0 mod tB−i <ref:2609.34436#pg12>.

The final contradiction arises because if f ◦ P were divisible by tB, then w(t), which is a polynomial of degree at most nr2, would have to be divisible by tB−(r-1). This is impossible when B ≥ nr2 + r.

The authors describe the PIT in this paper as similar in the sense that the generator is a set of algebraically independent power series (Pi(t):= − log(1 − it): i ∈ [n]) <ref:2609.34436#pg11>.

The proof uses induction on i via applications of Lemma 2.7 to prove Corollary 2.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Polynomial Hitting Set Construction for Low Dimensional Partial Derivatives: The system can construct an explicit polynomial sized hitting set for any class of polynomials whose partial derivative space is bounded by r, over any field F of characteristic zero.

  2. Depth-3 Powering Circuit Analysis: The improved system can utilize the derived result to provide a poly(n, d,s)-sized hitting set for the class of size s, degree d depth-3 powering circuits.

  3. PIT Algorithm Generation: The system can generate an efficient deterministic polynomial identity test for polynomials whose space of all possible partial derivatives is low-dimensional.

Abstract

We give an explicit hitting set of size poly(n,d,r) for the class of n-variate degree- d polynomials whose partial derivative space is bounded by r, over any field F of characteristic zero (or large enough). In particular, this yields a polynomial sized hitting set for the class of depth- 3 powering circuits. The proof extends to the setting of noncommutative ABPs and provides a polynomial sized hitting set (of matrices) for the class of noncommututive polynomials that can be computed by polynomial sized noncommutative ABPs (this was also one of the results reported by Open AI in their release on 6 Oct 2026). The main technical insight is the construction of a ``formal derivation'' and properties of the associated Wronskian with respect to this derivation, which was previously studied by Moura in a very different context. The proofs in this paper are elementary and completely self-contained. AI disclosure: A subset of the stewards obtained a weaker statement (hitting sets for polynomials with bounded partial derivative space) during conversations with OpenAI GPT-6 Astra. Extensions of this idea to the broader class of noncommutative ABPs were obtained by the other stewards (via further conversations with Astra), prior to OpenAI's dump on 6 Oct 2026. The proofs presented in this writeup is a rewriting (in the authors' words) of the proofs for both settings obtained by the models in a form that we believe is understandable to researchers. Although the proof is technically identical to OpenAI's release, we believe this exposition is self-contained, simpler, and more valuable to the community. The absurdity of the situation is not lost on us.

Sources

Related papers