Polynomial identity testing (PIT) problem is a fundamental problem in the area of algebraic circuit complexity. PIT is the problem of deciding whether a given multivariate polynomial is identically zero, where the input is given as an algebraic formula, circuit or other computational models like algebraic branching program. One way of testing zeroness of a polynomial is to check whether the coefficients of all the monomials are zero. However, the polynomial computed by a circuit or a branching program may have, in the worst-case, an exponential number of monomials compared to its size. Hence, by computing the explicit polynomial from the input, we cannot solve PIT problem in polynomial time. However, evaluating the polynomial at a point can be done in polynomial time of the input size. This helps us to get a polynomial time randomized algorithm for PIT by evaluating the input circuit at a random point, since any nonzero polynomial evaluated at a random point gives a nonzero value with high probability [10,57,49]. However, finding a deterministic polynomial time algorithm for PIT is a long-standing open question in algebraic complexity theory.
PIT captures several problems in algebra and combinatorics. For example, parallel algorithms for perfect matching [55, 35,14,54], primality testing [2], multivariate polynomial factorization [31], and many other problems [50,11,22]. PIT also has strong connection to circuit lower bounds [25,26,13,7,21]. See [45,53,48] for surveys on PIT.
PIT problem is studied in two different settings: 1) whitebox, where we are allowed to access the internal structure of the circuit, and 2) blackbox, where only evaluation of the circuit at points is allowed. Deterministic blackbox PIT for an n-variate circuit class is equivalent to efficiently finding a set of points H ⊆ F n , called a hitting-set, such that for any nonzero P in that circuit class, the set H contains a point at which P ̸ = 0 1 . In this work, we only focus on the blackbox model.
Despite a lot of effort, little progress has been made on the PIT problem in general. However, efficient deterministic PIT algorithms are known for many special circuit models. For example, blackbox PIT for depth-2 circuits (or sparse polynomials) [6,30,34], PIT algorithms for depth-3 circuits with bounded top fan-in [12,29,28,27,46,47,48], depth-3 diagonal circuits [44,17,16] and various other subclasses of depth-3 circuits [42,1,9], PIT for the subclasses of depth-4 circuits [3,5,15,32,40] and certain types of symbolic determinants [14,54,24].
The focus of this work is on the model of read-once oblivious algebraic branching programs (ROABPs). An ROABP is a product of matrices
where a, c ∈ F w×1 and for some permutation π on [n] for each i ∈ [n], M i (x π(i) ) ∈ F w×w [x π(i) ] can be viewed as a polynomial over the matrix algebra. The permutation π is called the variable order of the ROABP. One reason to be interested in ROABP is that derandomizing blackbox PIT for ROABP can be viewed as an algebraic analogue of the RL vs. L question. Besides that, the ROABP model is surprisingly rich and powerful. It captures several other interesting circuit classes such as sparse polynomials or depth-two circuits, depth-three powering circuits (symmetric tensors), set-multilinear depth-three circuits (tensors), and semi-diagonal depth-3 circuits [19]. Some notable polynomials such as the iterated matrix multiplication polynomial, the elementary and the power symmetric polynomials, and the sum-product polynomials can be computed by linear size ROABPs. Hitting sets for ROABPs have also led to the derandomization of an interesting case of the Noether Normalization Lemma [38,18], and to hitting sets for non-commutative algebraic branching programs [19].
PIT question for ROABPs and its variants has been widely studied. There are three parameters associated with an ROABP: the number of variables n, the size of the matrices w called width and the individual degree d which is the maximum possible degree of any variable. First, [41] gave a polynomial time whitebox PIT algorithm for this model. [19] first gave (ndw) O(log n) size hitting set for ROABPs when the variable order is known. Later, [17] gave an (ndw) O(d log w•log n) size hitting for ROABPs with unknown variable order, and subsequently, [1] gave an improved hitting set of size (ndw) O(log n) for this model. For zero or large characteristic fields, [22] gave an ndw log n size hitting sets for the known order ROABPs and the size becomes polynomially large when the width is constant. Better hitting set is known for a special class of ROABPs, called any-order ROABP. A polynomial f is computable by a w-width any-order ROABP, if for every permutation π on [n], f is computable by a w-width ROABP. The notion of any-order ROABP subsumes the notion of commutative ROABP. An ROABP is called commutative ROABP if the polynomial computed by it remains unchanged under any permutation of the matrices involved in the product. [17] gave two different constructions of hitting sets of size (ndw) O(log w) and d O(log w) • (nw) O(log log w) for any-order ROABPsfoot_0 . Later, [22] gives an improved hitting set of size (ndw) O(log log w) for this model. Recently, [20] gives improved hitting sets for both ROABPs and any-order ROABPs. Compared to the previous constructions, the size of hitting sets in [20] have finer dependence on the parameters of ROABPs. However, the construction of polynomial size hitting sets for ROABPs and its variants is still open.
In this work, we study the PIT question for the orbit of ROABPs. The orbit of an nvariate polynomial f (x) over a field F, denoted by orbit(f ), is the set of polynomials obtained by applying invertible affine transformations on the variables of f , that is, orbit(f ) = {f (Ax + b) | A ∈ GL(n, F), and b ∈ F n }. The orbit of a polynomial class C, denoted by orbit(C), is the union of the orbits of the polynomials in the class. Apart from being a natural question to study the sturdiness of the known techniques (and improving them), designing hitting sets for the orbits of polynomial families and circuit classes is interesting for the following reasons:
As observed by [43], the affine projections of "simple" polynomials have great expressive power. The set of affine projections of an n-variate polynomial f (x) over a field
Formally, they show that if the characteristic of F is zero, the set of affine projections of an n-variate polynomial f (x) over a field F lies inside the Zariski closure of the orbit of f (denoted by orbit(f )), that is aproj(f ) ⊆ orbit(f ). This observation has some interesting implications. For instance, using the above observation one can show that, the entire class of depth-3 circuits ΣΠΣ with top fan-in s and degree d is contained in aproj(SP s,d ), where SP s,d := i∈[s] j∈ [d] x i,j is a very structured s-sparse polynomial. The orbit closure of ROABPs is also very powerful, in fact they are as powerful as general ABPs. This can be seen by observing, the iterated matrix multiplication polynomial IMM w,d is computable by a linear-size ROABP, yet every polynomial computable by a size-s general algebraic branching program is in aproj(IMM s,s ). For more polynomial families whose orbit closures contain interesting circuit classes, see [36].
For an n-variate polynomial f over a field F, let V(f ) denotes the variety (that is, zero locus) of f . Hitting set construction for an n-variate polynomial class C is the problem of picking a set of points H such that for each polynomial f ∈ C, H is not entirely contained in V(f ). On the other hand, Constructing hitting sets for the orbits of a polynomial class C is the task of finding a small set of points H such that for every f ∈ C, H is not entirely contained in the set {Aa
This ensures that H will be independent to the choice of coordinate system, making it mathematically and geometrically robust. For a more detailed discussion on the reasons for studying hitting set of orbits, see [43].
Hitting set construction for orbits of circuit classes is very recent, somewhat simultaneously Medini and Shpilka [36] and Saha and Thankey [43] started exploring PIT for the orbit of various polynomial classes. Medini and Shpilka [36] gave a quasi-polynomial size hitting set for the orbits of sparse polynomials ( circuits) and read-once formulas (ROFs). Saha and Thankey [43] gave hitting sets for the orbits of ROABPs and constant-read (more generally, constant-occur) formulas. Concretely, [43] gave an (ndw) d log w size hitting set for the orbit of n-variate individual degree d width w commutative ROABPs. They also gave an (nw) O(w 6 log n) size hitting set for the orbit of n-variate multilinear polynomials computed by width w ROABPs. Building on this, they also gave quasi-polynomial size hitting set for constant-depth constant-occur formulas whose leaves are labeled by s-sparse polynomials with constant individual degree. In this work, we design hitting sets for the orbit of ROABPs and any-order ROABPs. Our results significantly improve the dependence on individual degree in the size of hitting sets in comparison to [43], from exponential to polynomial.
First, we define the models studied in this paper. Algebraic branching programs (ABPs) were defined by Nisan in [39]. In this paper, we study a variant of ABPs known as read-once oblivious ABPs (ROABPs). While Nisan defined ABPs using directed graphs, we use a more conventional definition using product of matrices. Let f (x 1 , . . . , x n ) be an n-variate individual degree d polynomial over a field F. Let π be a permutation on [n]. We say f is computed by a width w ROABP with variable order π, if f can be written as
where a, c ∈ F w×1 and for all i
] can be viewed as a polynomial in x π(i) over the matrix algebra with degree at most d. We say f is computable by a w-width any order ROABP, if for every permutation π on [n], f is computable by a width w ROABP. We say f is computed by a width w commutative ROABP, if all M i (x π(i) )'s are polynomials over a commutative sub-algebra of the matrix algebra. For example, consider the coefficients of each M i are diagonal matrices. One can observe that the set of polynomials computed by w-width commutative ROABPs are also computable by w-width any-order ROABPs. However, the converse direction is unknown to us. All PIT algorithms for ROABPs are designed by analyzing the coefficient space of
In this paper, we design hitting sets for the orbits of ROABPs and any-order ROABPs. Let f (x) be an n-variate polynomial over a field F. The orbit of f , denoted by orbit(f ), is the set {f (Ax + b) | A ∈ GL(n, F) and b ∈ F n }. For a polynomial class C, the orbit of C, denoted by orbit(C), is the union of orbits of all the polynomials in C. Now, we describe our result for the orbit of any-order ROABPs.
▶ Theorem 1. Let F be a field of characteristic zero or greater than d. Let C be the set of n-variate polynomials over F with individual degree at most d and computable by a width w any-order ROABP. Then, there exists a hitting set for orbit(C) computable in time (ndw) O(ℓ) where ℓ = min{w 2 , 2d log w}.
As far as we know, this is the first result addressing the orbit of any-order ROABPs, and it subsumes the commutative ROABP result of Saha and Thankey [43]. They gave an (ndw) O(d log w) size hitting set for the orbit of commutative ROABPs. In fact, our result strengthens [43] in "low width" setting. Concretely, if the individual degree is poly(log n), [43] gives quasi-polynomial time PIT for the orbit of commutative ROABPs. However, when d ≥ n, their algorithm does not give any non-trivial PIT for the orbit of commutative ROABPs. On the other hand, our result gives quasi-polynomial time PIT for the orbit of any-order ROABPs when min{d, w} = poly(log n). Also, for constant width any-order ROABPs with unbounded individual degree, our result gives a polynomial time PIT for its orbit. However, [43] gives polynomial time PIT for the orbit commutative ROABPs when both d and w are constants. Thus, our result has much better dependence on the individual degree in comparison with [43]. Now, we describe our result regarding the orbit of ROABPs.
Saha and Thankey [43] gave an (nw) O(w 6 log n) time PIT for the orbit of multilinear polynomials computed by ROABPs. Therefore, our result can be seen as the first one which gives PIT for the orbit of ROABPs with unbounded individual degree. Irrespective of the value of the individual degree, our result gives a quasi-polynomial time PIT for the orbit of ROABPs when the width w = poly(log n). Also, the time complexity of our algorithm has better dependence on the width of ROABPs in comparison with [43].
Our results in this paper continue to hold even if we consider a more generalized definition for the orbit of an n-variate
with rank n and b ∈ F n } where y = (y 1 , . . . , y m ). However, we work with the conventional definition of the orbit of polynomials for the simplicity of exposition, and because the proofs of the results with the generalized definition of orbit is almost the same as the proofs given in this paper.
First, we briefly sketch the abstract framework followed by the proofs of our results. Let C be a set of n-variate polynomials in y = (y 1 , . . . , y n ) with individual degree at most d.
Then orbit(C) is the set of n-variate polynomials in x = (x 1 , . . . , x n ) is defined as follows: for all f (x) ∈ orbit(C) there exists a polynomial h(y) ∈ C, an invertible linear transformation
In this paper, we design hitting sets for the orbits of ROABPs and any-order ROABPs. Hitting sets for ROABPs are constructed by designing a "smartly" chosen shift g(t) (a low variate polynomial map) such that when we shift any polynomial h(y) computable by a small size ROABP, then there exists a "low-support" monomial (with nonzero coefficient) in h(x + g). Note that, it is straightforward to construct hitting sets when such a low-support monomial (with nonzero coefficient) exists. However, this approach does not directly work for a polynomial f (x) = h(L(x) + b) in the orbit of ROABPs as shifting f has a slightly different effect. Note,
That is, the shift gets composed with the affine transformation L(x)+b. The main idea in our construction is to choose a shift such that the transformed shift (for any affine transformation) is also "smart". That is, for any invertible linear transformation L(x) and b ∈ F n , there exists a "low-support" monomial (with nonzero coefficient) in
Let g(t) = (g 1 , . . . , g n ) be a polynomial map from F m to F n and h ′ (y) = h(y
Our abstract format to design hitting sets for the orbits of ROABPs and any-order ROABPs has the following two steps.
Step 1: First we find some suitable low degree polynomial map g in few variables (compare to n) such that for all invertible linear transformation L(x) and b ∈ F n , after shifting
has the following property: for some small positive integer k, hom ≤k (h ′ (y)) is a nonzero polynomial in y over the field F(t), where hom ≤k (•) denotes the degree up to k part of the input polynomial. This step, more specifically the construction of g(t), heavily relies on the structure of C.
Step 2: Since L(x) is an invertible linear transformation, all ℓ i 's are algebraically independent.
Also, hom ≤k (f ′ ) = hom ≤k (h ′ )(L(x)). Therefore, hom ≤k (f ′ ) is a nonzero polynomial in x over the field F(t). This implies that there exists a monomial
x ei i such that the support of e is at most k and the coefficient of x e in f ′ is a nonzero polynomial in t. There are well known constructions of hitting sets for polynomials like f ′ (x). For example, combining Lemma 23 and Observation 17 we get a hitting set for f ′ of size around (nd) O(m+k) . Thus, we design a hitting set for orbit(C). This step is independent of the polynomial class C.
For instance, assume that C is the set of n-variate polynomials with individual degree and sparsity are at most d and s, respectively. Then, from [15], after shifting any polynomial h(y) ∈ C by an α α α = (α 1 , . . . , α n ) with all α i 's are nonzero the following holds: there exists a monomial y e such that the support of e is at most log s and its coefficient in h(y + α α α) is nonzero. Let g(t) be the polynomial map from F to F n defined as (t, t 2 , . . . , t n ) and b = (b 1 , . . . , b n ). Then, each ℓ i (g) + b i is a nonzero polynomial. Therefore, there exists a monomial y e of support-size at most log s such that its coefficient in h ′ (y) is a nonzero polynomial in t. Since the individual degree is at most d, the degree of y e is at most ≤ d log s. Now from the step 2, there exists a monomial in x of support-size at most d log s such that its coefficient in f ′ is a nonzero polynomial in t. Thus, we have a hitting set for orbit(C) of size (nd) O(d log s) . This gives a different (and much simpler) hitting set construction than [43,Theorem 7] for the orbit of sparse polynomials with low individual degree.
We describe some stronger rank concentration results, which will be very useful in designing our hitting sets for the orbits of ROABPs and any-order ROABPs. Let G(x) be an n-variate polynomial over the vector space F k . The coefficient space of G is the vector space spanned by the coefficients (from F k ) in G. In general, the coefficient space of G can be spanned by the coefficients of any arbitrary set of monomials. In rank concentration, our goal is to construct a polynomial map g(t) such that after shifting G(x) by g(t), the coefficient space of the new polynomial G ′ (x) = G(x + g) is spanned the coefficients of a "small" set of monomials S. For example, 1. if S is the set of monomials whose support-size is ≤ ℓ, we say G ′ has ℓ-support concentration.
The support-size of a monomial is the number of variables appearing in it.
2. if S is the set of monomials whose cone-size is ≤ ℓ, we say G ′ has ℓ-cone concentration.
The cone-size of a monomial is the number of monomials dividing it. 3. if S is the set of monomials which is closed under sub-monomials, we say G ′ has a cone-closed basis.
The notion of rank-concentration was introduced in [4]. Subsequently, many PIT results are obtained based on "low-support" rank concentration [4,17,23,22,43]. Later, [16] introduced the notion of cone concentration and cone-closed basis. Among the three notions of rank concentrations, cone-closed basis is stronger than the other two, then comes cone concentration and after that support concentration. More specifically, cone-closed basis of G ′ implies that it has also k-cone concentration, and k-concentration for G ′ implies it has also log k-support concentration. For more details about the relation between these three notions of rank concentrations see Lemma 26. The notion of cone concentration is important for designing our improved hitting sets over [43]. Although the notion of cone concentration was first introduced in [16] and they showed some low-cone concentration result, we are not are aware of any "non-trivial" application of them in designing PIT algorithms. Therefore, to the best of our knowledge, this is the first time when the notion of cone concentration is used in designing PIT algorithms.
In this work, we strengthen some of the rank concentration results shown in [17,16]. [17] showed that if G(x) is shifted by t = (t 1 , . . . , t n ), the new polynomial G(x + t) has log k-support concentration over the field F(t). Moreover, they showed that if G is shifted by a n-wise independent monomial map g ′ (s, t), then the new shifted polynomial has log k-support concentration. A polynomial map g ′ (s, t) from F m × F m ′ to F n is called ℓ-wise independent monomial map if for every S ⊆ [n] of size ≤ ℓ there exists an α α α ∈ F m such that polynomials {g ′ (α α α, t) e } supp(e)⊆S are distinct monomials in t. Later, [16] showed that G(x + t) has a cone-closed basis. Their result can also be extended to show that G(x + g ′ ) has a cone-closed basis when g ′ is an n-wise independent monomial map. However, when we take composition of g ′ with an invertible affine transformation, that is b + L • g ′ where b ∈ F n and L(x) is an invertible linear transformation from F n to F n , the n-wise independence property of g ′ breaks down. Therefore, the previous rank concentration results are not helpful in designing hitting sets for the orbits of circuit classes. We strengthen the rank concentration results of [17,16] in the following way: After shifting G by a polynomial map g ′ = (g 1 , . . . , g n ) such that all g i 's are algebraically independent, the new polynomial has a cone-closed basis, hence k-cone concentration. Observe that the n-wise independence property implies the algebraic independence property needed in our hypothesis. Therefore, our hypothesis is weaker than the hypothesis used in [17,16]. Also, algebraic independence property of g ′ preserves even after composing it with invertible affine transformations. For details see Lemma 4. This rank concentration result will be helpful in designing the hitting sets for the orbit of any-order ROABPs.
We show one more rank concentration result which will help in designing PIT algorithms for the orbit of ROABPs. Assume that the coefficients of the monomials of total degree up to D spans the coefficient space of G. Let g ′ (s, t) be a total degree D independent monomial map from F m × F m ′ to F n , that is, there exists an α α α ∈ F m such that the polynomials {g ′ (α α α, t) e } |e|1≤D are distinct monomials in t. Then [17] showed that if G(x) is shifted by ug ′ , then the new shifted polynomial has log k-support concentration over the field F(u, s, t). Our rank concentration result differs from [17] in the following ways: 1. Our hypothesis is slightly stronger than [17]. Instead of total degree D independent monomial map, we assume that g ′ (s, t) is a total degree Dk independent monomial map.
On the other hand, we strengthen the conclusion as follows: for every invertible linear transformation L(x) from F n to F n , if we shift G by uL • g ′ , then the new shifted polynomial has a cone-closed basis over the field F(u, s, t). For details see Lemma 5.
Suppose that C is the set of all n-variate polynomials in y with individual degree at most d and computed by width w any-order ROABPs. Let f (x) be an n-variate polynomial in orbit(C). Then there exists a polynomial h(y) ∈ C, an invertible linear transformation L(x) and a point b ∈ F n such that
Since h(y) ∈ C, there exists a polynomial G(y) ∈ F[y] w×w with individual degree at most d and computed by a width w any-order ROABP such that
where a, c ∈ F w . Now we will describe the first step of aforementioned abstract format. First, we show how to achieve w 2 -cone concentration in G(y). Let g(t) = (g 1 , . . . , g n ) be a polynomial map from F m to F n such that for any S ⊆ [n] of size k := ⌈2 log w + 1⌉, the set of polynomials {g i | i ∈ S} are algebraically independent. Then, in Lemma 6, we prove that G(y + g) has w 2 -cone concentration over the field F (t). It strengthens the rank-concentration result for any-order ROABPs shown in [17,Theorem 4.1]. They showed that if we shift G by a k-wise independent monomial map, then the new polynomial has 2 log w-support concentration. Next, in Lemma 7, we show that for any invertible linear transformation L(x) and b ∈ F n , the polynomial map defined as the composition of L(x) + b and Shpilka-Volkovich generator G SV n,k (see Definition 21, or [51]), that is L • G SV n,k + b, satisfies the property required for achieving w 2 -cone concentration in G(y). Therefore, G(y + L • G SV n,k + b) has w 2 -cone concentration. This implies that there exists a monomial y e of cone-size ≤ w 2 such that the coefficient of
For any monomial of cone-size ≤ w 2 , its degree is less than w 2 and the support set is of size at most 2 log w. Since the individual degree is at most d, the degree of y e is at most ℓ where ℓ := min{w 2 , d log w}. Therefore, hom ≤ℓ (h ′ ) is nonzero. Now we apply the step two of the abstract format, which is independent of C, and get our desired hitting set for orbit(C).
Suppose that C is the set of all n-variate polynomials in y with individual degree at most d and computed by width w ROABPs. Let f (x) be an n-variate polynomial in orbit(C). Then there exists a polynomial h(y) ∈ C, an invertible linear transformation L(x) and b ∈ F n such that
Since h(y) ∈ C, there exists a polynomial G(y) ∈ F[y] w×w and a permutation π on [n] such that
where a, c ∈ F w and for all i
Now like any-order ROABPs, we want to achieve w 2 -cone concentration in G(y). However, our approach here will be different from any-order ROABPs. Here, we strengthen the "mergeand-reduce" approach of [17] in the following ways: 1. In [17], the polynomial maps h j (for j = 0, 1, . . . , ⌈log n⌉) were inductively constructed such that after shifting G by h j , in the new polynomial G(x + h j ), the product of any 2 j consecutive matrices have 2 log w-support concentration. We strengthen this result by showing w 2 -cone concentration at each inductive step. 2. At each induction step, since we are dealing with polynomials in orbit (of ROABPs), we not only need to construct a polynomial map which helps to achieve w 2 -cone concentration, but its composition with any invertible affine transformation also helps to achieve the same property.
In [17], h j was constructed as follows: h 0 = 0 and for all j ∈ [⌈log n⌉], h j = h j-1 + u j g(s j , t j ) where g(s j , t j ) is a total degree 4d log w independent monomial map from F m ×F m ′ to F n . They showed that the product of any 2 j consecutive matrices in G(y + h j ) has 2 log wsupport concentration over the field F((u k , s k , t k ) k∈ [j] ).
Our definition of h j is very close to the definition used in [17]. For j = 0, h j = (t, t 2 , . . . , t n ) and for all j ∈ [⌈log n⌉], h j = h j-1 +u j g(s j , t j ) where g(s j , t j ) is a total degree D independent monomial map from F m × F m ′ to F n where D = 2w 2 • min{w 2 , 2d log w}. We show that for every invertible linear transformation L(x) from F n to F n and b ∈ F n , the product of any 2 j consecutive matrices in G(y + L • h j + b) has a cone-closed basis, hence has w 2 -cone concentration, over the field F(t, (u k , s k , t k ) k∈[j] ). Our rank concentration results play an important role in proving this property of h j . For more details see Lemma 9 and 10. There are many known constructions of total degree D independent monomial map with m = m ′ = O(D). For example see Lemma 20. After constructing a polynomial map which gives w 2 -cone concentration in G(y), the rest of the proof will be similar to what we did for the any-order ROABP case.
By N we denote the set of natural numbers. For any positive integer n, [n] denotes the set {1, 2, . . . , n}. For a variable tuple x = (x 1 , . . . , x n ) and a tuple e = (e 1 , . . . , e n ) ∈ N n , x e denotes the monomial n i=1 x ei i . The degree, or total degree, of x e is |e| 1 = n i=1 e i and the individual degree of x e is |e| ∞ = max i∈[n] e i . The support of x e is the subset S of [n] such that i ∈ S if and only if e i > 0, and the support-size denotes the cardinality of S. The cone of x e is the set of monomials which divide it and the cone-size is the cardinality of that set, that is
every monomial in B all its sub-monomials are also in B. For a polynomial f in x and a monomial x e , coef f (x e ) denotes the coefficient of x e in f .
In this section, we show our rank concentration results for polynomials over the vector space Let G(x) be an n-variate polynomial over F k with individual degree at most d. After shifting G(x) by z, the coefficients of the shifted polynomial G ′ (x) = G(x + z) can be written as follows: for all e ∈ M n,d ,
The above equation can be written in matrix form as follows:
where F and F ′ (z) are the matrices with entries from F and F[z], respectively. The rows of both the matrices are indexed by the elements of M n,d , and for any monomial e ∈ M n,d , the rows indexed by e in F and F ′ are coef x e (G) and coef x e (G ′ ), respectively. W (z) be the diagonal matrix whose rows and columns are indexed by the elements of M n,d and for all e ∈ M n,d , W (z) e,e = z e . T is a square matrix such that the rows and columns are indexed by M n,d and for all e, f ∈ M n,d , T e,f = f e . In the literature, T is known as transfer matrix.
In the following lemma, we recall a property of transfer matrix from [16].
▶ Lemma 3 (Lemma 17 [16]). Let F be a field of characteristic 0 or greater than d. Then, for every B ⊆ M n,d , there exists a cone-closed set
Next, we show our first rank concentration result. Informally, we prove that if G(x) is shifted by algebraically independent polynomials, the new polynomial has a cone-closed basis.
▶ Lemma 4. Let F be a field of characteristic 0 or greater than d. Let G(x) ∈ F k [x] be an n-variate polynomial with individual degree at most d. Let g(z) = (g 1 , . . . , g n ) be a polynomial map from F n to F n such that all g i 's are algebraically independent. Then G(x + g) has a cone-closed basis over F(z).
Proof. First we show that G ′ (x) = G(x + z) has a cone-closed basis over F(z). This part of our proof closely follows the proof outline of [16,Theorem 2]. From Equation 1, we know that the shifted polynomial G(x + z) yields the following matrix equation:
Let k ′ be the rank of the matrix F . Then we divide our proof in two cases:
and G ′ S (x) be the projections of G(x) and G ′ (x) on the coordinates indexed by S. Then G ′ S (x) = G S (x + z). One can observe that for any set of monomials A, if their coefficients in G S (x) forms a basis for its coefficient space, then their coefficients in G(x) also forms a basis for the coefficients space of G(x). Similarly, this is also true between G ′ S (x) and G ′ (x). Now from the case 2, G ′ S (x) has a cone-closed basis over F(z), that is, there exists a cone-closed set of monomials A such that their coefficients in G ′ S (x) forms a basis for its coefficient space. This implies that G ′ (x) also has a cone-closed basis over F(z). Using Lemma 3, we have a cone-closed subset A of M n,d such that T A,B has full rank. Now
Applying Lemma 14, we get that
For every
is a full rank matrix, the following holds:
e∈B z e ≺ e ′ ∈C z e ′ . Therefore, the coefficient of e∈B z e in the above polynomial does not get cancelled by other monomials. Also, the coefficient of e∈B z e , det(T
Now we show that G(x + g) has a cone-closed basis over F(z). In Equation 2, since both det(W (z) A,A ) and det((T W (z)F ) A, [k] ) are nonzero polynomials in z. Therefore, after evaluating them on any n algebraically independent polynomials, they will remain nonzero. Thus, det(F ′ (g) A, [k] ) remains nonzero. This implies that for the polynomial G(x + g), the coefficients of the monomials in A form a cone-closed basis (over F(z)) for its coefficient space.
◀
The above lemma combined Lemma 26 implies that the polynomial G(x + g) also has k-cone concentration over F(t). Here, we would like to mention that although the above rank concentration result is described in terms of cone-closed basis, to design our hitting sets, proving k-cone concentration property of G(x + g) is sufficient. The similar thing is also true for our next rank concentration result.
▶ Lemma 5. Let F be a field of characteristic zero or greater than d. Let G(x) be an n-variate individual degree ≤ d polynomial over F k such that the coefficients of all the monomials of total degree up to D spans the coefficient space of G. For some N ≥ n, let L(y) = (ℓ 1 , . . . , ℓ n ) be a linear transformation from F N to F n such that all ℓ i 's are linearly independent. Let g(s, t) be a total degree Dk independent monomial map from F m ×F m ′ to F N . Then G(x+g ′ ), where g ′ = uL • g, has a cone-closed basis over F (u, s, t).
For proof of the above lemma see Section B.
In this section, we describe our hitting set for the orbit of any-order ROABPs. As mentioned earlier, the notion of low-cone concentration plays an important role is designing our hitting sets. We begin by showing that for w-width n-variate any-order ROABPs, w 2 -cone concentration can be established by showing w 2 -cone concentration for every Ω(log w)-size subset of variables.
▶ Lemma 6. Let F be a field of characteristic 0 or greater than d. Let G(x) ∈ F[x] w×w be an n-variate polynomial over F with individual degree at most d and computed by a w-width any-order ROABP. Let ℓ = ⌊2 log w⌋ + 1. Let g(t) = (g 1 , . . . , g n ) be a polynomial map such that for all S ⊆ [n] of size ℓ, the polynomials {g i | i ∈ S} are algebraically independent. Then G(x + g) has w 2 -cone concentration over F(t).
For proof of the above lemma see the full version. Our next lemma, using Shpilka-Volkovich generator (Definition 21), gives the construction of a polynomial map which satisfies the condition of the above lemma. ▶ Lemma 7. Let L(x) = (ℓ 1 , . . . , ℓ n ) be an invertible linear transformation from F n to F n . Let b be a point in F n . For some k ≤ n, let g(s, t) = (g 1 , . . . , g n ) be the polynomial map from
For proof of the above lemma the full version. Combining the above two lemmas, we get the following.
▶ Corollary 8. Let F be a field of characteristic 0 or greater than d. Let G(x) ∈ F[x] w×w be an n-variate polynomial with individual degree at most d and computed by a width w any-order ROABP. Let L(x) be an invertible linear transformation from F n to F n and b be a point in
Proof. Let g(s, t) = (g 1 , . . . , g n ). From Lemma 7, for every subset S ⊆ [n] of size k, the polynomials {g i | i ∈ S} are algebraically independent. Therefore, using Lemma 6, we get that G(x + g) has w 2 -cone concentration over F(s, t). ◀ Now we describe the construction of our hitting set for the orbit of any-order ROABPs.
Proof of Theorem 1. Let f (x) be an n-variate individual degree ≤ d polynomial which is in the orbit of width w any-order ROABPs. Then, there exists an n-variate individual degree ≤ d polynomial G(y) ∈ F w×w [y] computed by a width w any-order ROABP, an invertible linear transformation L(x) from F n to F n and a point b ∈ F n such that
where k = ⌊2 log w⌋ + 1, and let
This implies that
From Corollary 8, G(y + g) has w 2 -cone concentration over F(s, t). This implies that there exists a monomial y e in h with cone-size ≤ w 2 such that coef y e (h) is nonzero. For a monomial of cone-size ≤ w 2 , its total degree is less than w 2 and the support-size is ≤ log w 2 . Since the individual degree of each variable in G(y) is at most d, Therefore, the degree of y e is ≤ ℓ where ℓ = min{w 2 , 2d log w}. Hence, hom ≤ℓ (h(y)) is a nonzero polynomial in y. Since
from Lemma 24, hom ≤ℓ (h(L(x))) is a nonzero polynomial. Therefore, from Equation 4, hom ≤ℓ (f ′ (x)) is a nonzero polynomial over F(s, t). This implies that there exists a monomial x e of support-size ≤ ℓ such that its coefficient in f ′ is nonzero. Thus, from Lemma 23,
) is a k + ℓ-variate nonzero polynomial over F. The total degree of f is at most nd, and from Observation 22, the individual degree of each coordinate of G SV n,k+ℓ is at most n. Also, G SV n,k+ℓ is poly(ndw)-explicit. Thus, from Observation 17, f has a hitting set computable in time (ndw) O(ℓ) . ◀
Here, we discuss the construction of our hitting set for the orbit of ROABPs. Towards that, first we need to construct some polynomial map which helps us in achieving low-cone concentration for ROABPs. At this step, we also have to be more careful as we are dealing with the orbit of ROABPs. Lemma 10 describes inductive construction of a polynomial map, by taking sum of logarithmically many variable disjoint copies of total degree D independent monomial maps (Definition 19) for some small D, such that the following holds: by shifting its composition with any invertible affine transformation we can achieve low-cone concentration for ROABPs. We begin by showing how to achieve cone-closed basis for the product of two polynomials in a disjoint set of variables, with the property that each polynomial also has a cone-closed basis. For proof of the above lemma see the full version. Applying the above lemma repeatedly, the next one gives the construction of a polynomial map which helps us to achieve low-cone concentration for ROABPs. ▶ Lemma 10. Let n ≥ 0, N = 2 n and d, w ≥ 1. Let D = 2w 2 • min{w 2 , 2d log w}. Let g(s, t) be a total degree D independent monomial map from
where all s i 's and t i 's are disjoint set of variables.
Let π be permutation on
with individual degree at most d. Then for every invertible linear transformation L(x) from
Proof. Let L(x) = (ℓ 1 , . . . , ℓ N ). Let h 0 = b + L(t 0 ), and for all k ∈ [n],
APPROX/RANDOM 2021 30:14 Improved Hitting Set for Orbit of ROABPs Using induction, we show that for all k ∈ {0, 1, . . . , n} and i, j
For k = 0. Let b = (b 1 , . . . , b N ). We need to show that for all i ∈ [N ], M i (x π(i) + ℓ π(i) (t 0 ) + b π(i) ) has a cone-closed basis over F(t). Since L(x) is an invertible linear transformation, each ℓ i is a nonzero linear polynomial over x. Therefore, ℓ i (t 0 ) is a non-contant polynomial in t. Hence, using Lemma 3, for all i ∈ [N ], M i (x π(i) + ℓ π(i) (t 0 ) + b π(i) ) has a cone-closed basis over F(t).
For k > 0. Let i, j ∈ [N ] such that j -i + 1 = 2 k . Let y and z be a partition of the variables (x π(i) , . . . , x π(j) ) into two equal halves such that they respect the permutation π. Then F ij [x] can be written as G(y)H(z) where G(y) ∈ F[y] w×w and H(z) ∈ F[z] w×w . From the induction hypothesis, we know that both
Then, using Lemma 9,
has a cone-closed basis over F(t, (u i , s i , t i ) i∈ [k] ). This completes our proof. ◀
From Lemma 20, using Klivans-Spielman generator (Lemma 18), we can construct a total degree D independent monomial map. Therefore, Klivans-Spielman generator combined with the above lemma we get the following corollary.
Let π be permutation on
) is a polynomial in F[x π(i) ] w×w with individual degree at most d. Then, 1. for every invertible linear transformation L(x) from F N to F N and b ∈ F N , the polynomial
) has a cone-closed basis over the field F(t, (u i , s i ,
where t 0 = (t, t 2 , . . . , t n ). Then, G ′ ⌈log n⌉,d,w is a polynomial map from F×(F×F m ×F m ) ⌈log n⌉ to F n where m = O(D). This implies that the number of variables used in
From Corollary 11,
has a cone-closed basis over F(t, (u i , s i , t i ) i∈[⌈log n⌉] ). Therefore, from Lemma 26, G ′ (y) has also w 2 -cone concentration. This implies that g(y) has a monomial of nonzero coefficient and its cone-size is at most w 2 . For every monomial of cone-size at most w 2 , its degree is also at most w 2 and its support-size is at most 2 log w. Therefore, for every monomial of cone-size ≤ w 2 and individual degree ≤ d, its degree is at most k = min{w 2 , 2d log w}. Therefore, hom ≤k (g(y)) is a nonzero polynomial in y over F(t,
from Lemma 24, hom ≤k (g(L(x))) is also nonzero polynomial. Therefore, from Equation 6, hom ≤k (f ′ (x)) is also a nonzero polynomial. This implies that there exists a monomial x e of support-size at most k such that coef x e (f ′ ) is nonzero. Thus, from Lemma 23,
Then, G is a polynomial map in O(kw 2 log n) many variables and the individual degree of each coordinate is at most poly(ndw). Since both G SV n,k and G ′ ⌈log n⌉,d,w both are poly(ndw)-explicit, G is also poly(ndw)-explicit. Thus, applying Observation 17, we have a hitting set for f computable in time (ndw) O(ℓ) where ℓ = (w 2 log n) • min{w 2 , d log w 2 }. ◀
In this paper, we studied the hitting set problem for the orbits of ROABPs and any-order ROABPs. We have designed improved hitting sets for these two polynomial classes. In low-width but high-individual-degree setting, our hitting sets are more efficient than the previous ones given by Saha and Thankey. On the technical front, we have shown some stronger rank concentration results by establishing low-cone concentration for polynomials over vector spaces. These new rank concentration results have played a significant role in designing our hitting sets. However, our hitting sets for the orbits of ROABPs and any-order
ROABPs are yet to match the time complexity of hitting sets known for ROABPs and its variants. Therefore, it is an interesting open question to close this gap.
▶ Lemma 18 (Klivans-Spielman generator [30]). The above generator is a slight variation of the construction given in [30], but it can be constructed from their techniques. For a proof-sketch see [17,Theorem 2.3]. Next, we define total degree D independent monomial map from [17].
▶ Definition 19. For some positive integers n and D, a polynomial map g(s, t) from F m ×F m ′ to F n is called total degree D independent monomial map if there exists an α α α ∈ F m such that the polynomials {g(α α α, t) e } |e|1≤D are nonzero, distinct monomials in t.
In the following lemma, we describe a construction of total degree D independent monomial map using Klivans-Spielman generator. For proof see [17,Lemma 6.4]. Next, we describe a polynomial map introduced by Shpilka and Volkovich [51]. It is a widely used tool in PIT and other related results [51,17,52,37,33,36,43], and also crucial for proving our results.
▶ Definition 21 (Shpilka-Volkovich generator [51]). Fix a positive integer n and a set of n distinct elements A = {α 1 , . . . , α n } ⊆ F. Let L i (t) be the ith Lagrange interpolation polynomial for the set A. That is, L i (t) is a univariate polynomial of degree n -1 such that L i (α j ) = δ ij . Let s = (s 1 , . . . , s k ) and t = (t 1 , . . . , t k ). Then G SV n,k (s, t) is the polynomial map from F k × F k to F n defined as follows: for all i ∈ Using Shpilka-Volkovich generator, the following lemma describes a nonzeroness preserving variable reduction for polynomials having a "low-support" monomial with nonzero coefficient. ▶ Lemma 23. Let f (x) be an n-variate polynomial over F such that there exists a monomial x e with nonzero coefficient in f and the support-size of e is at most ℓ. Then f • G SV n,ℓ ̸ = 0.
Proof. Let {x i1 , . . . , x i ℓ } be the support set of the monomial x e . Then, from Observation 22, there exists an α α α ∈ F α such that for all j ∈ [ℓ], (G SV n,ℓ (α α α, t)) ij = t j and the other coordinates of G SV n,ℓ (α α α, t) are zero. This implies that f (G SV n,ℓ (α α α, t)) ̸ = 0, and therefore f • G SV n,ℓ ̸ = 0. ◀
Proof of Lemma 5. First we study the shifted polynomial G ′ (x) = G(x + uz). To do so, we revisit the proof of our Lemma 4. There we considered the lexicographic monomial ordering over the monomials in z. Here we consider the deg-lex monomial ordering, that is, first order the monomials from lower degree to higher degree and then within each degree arrange them in lexicographic order. Like Equation 1, the matrix equation for the shifted polynomial G ′ (x) will be
that is scaling of each variable in Equation 1 Since all ℓ i 's are linearly independent, from Lemma 24, they are also algebraically independent. Therefore, the coefficient of u deg(B) in det((T W (uL)F ) A, [k] ) is also a nonzero degree deg(B) homogeneous polynomial in y. Also, deg(B) ≤ Dk. Therefore, after substituting z by L • g in Equation 9, we get det((T W (g ′ )F ) A, [k] ) which is a nonzero polynomial in (u, s, t). Since det(W (g ′ )) is also a nonzero polynoimal in (u, s, t), det(F ′ (g ′ ) A, [k] ) is nonzero in F(u, s, t). This implies that G(x + g ′ ) has a cone-closed basis over F(u, s, t). ◀
In[17], any-order ROABPs are referred by "commutative ROABPs".