WorksComputer Science
Black-box identity testing for affine orbits of read-once oblivious algebraic branching programs
Abstract
For every fixed width, we construct a polynomial-size hitting set for read-once oblivious algebraic branching programs under an unknown invertible affine change of variables. A width bound in a single unknown order suffices. The resulting deterministic black-box identity test runs in time polynomial in the number of variables and the total degree over every field with more elements than the degree. The construction preserves the generic ranks of consecutive matrix products in descending order. At fixed dimension and width, the query count is linear in the total degree in characteristic zero or above the individual degree in the hidden coordinates. When the width bound holds in every order, cut ranks give linear dependence up to logarithmic factors even in small characteristic. We also treat multivariate layers with bounded overlap and obtain a linear query bound for bivariate programs of width two.
Introduction
We have black-box access over a field to , where and are unknown. In the hidden coordinates the polynomial is computed by a width- read-once oblivious algebraic branching program (ROABP),
with univariate polynomial matrices of width at most , a constant row , a constant column , and an unknown variable order . A hitting set is a finite subset of on which every nonzero polynomial in the class has a nonzero value. Write for a total-degree bound and . We may use any upper bound on the individual degree of , including . We count field operations and oracle queries, given distinct field elements for the evaluation grids.
Theorem 1.1 (One unknown order, arbitrary width). For , , and , the affine orbit of width- ROABPs in one unknown order admits an explicit hitting set of size
In characteristic zero, or in characteristic , there is a hitting set of size
§ 3 proves the arbitrary-characteristic bound by two generators. The first uses scalar parameters. The second uses a moment curve and interpolation pairs. § 4 derives (1) from the exponent sets of the top homogeneous component.
Theorem 1.2 (Every variable order). Suppose admits width at most in every variable order, with matrices depending on the order. For , a hitting set of size suffices if , , or . In positive characteristic let . With no restriction on the size is
The width in one order bounds the coefficient ranks of its prefix cuts. Bounded width in every order gives a bound on every cut, which in turn bounds the digit weight of a translation-invariant leading coefficient (§ 5). At width two, the singleton and pair cuts alone determine the form of this coefficient.
Theorem 6.1 extends the construction to multivariate layers through the intersections of prefix and suffix spans. For independent blocks of at most variables the degree exponent is in characteristic zero or above , sharp already at width one. In two variables, queries suffice at width two whenever (Theorem 7.1).
Related work. Saha and Thankey [12] studied affine orbits of circuit classes including multilinear ROABPs. In characteristic zero or greater than , Bhargava and Ghosh [1] obtained bounds of for one unknown order and for every order. For a single unknown order, Theorem 1.1 gives a polynomial bound at each fixed width in every characteristic. Theorem 1.2 separates the dependence on total degree from the dimension. For ROABPs in the original coordinates see Gurjar, Korwar and Saxena [5], Singh and Singh [15], and Shpilka [13]. The rank descent and image-cone arguments build on the source manuscripts [10].
Cut ranks, leading coefficients, and interpolation
Lemma 2.1 (Cut ranks). Let denote the rank of the coefficient matrix with rows indexed by monomials on and columns by monomials on . A polynomial admits width at most in an order precisely when at every prefix [7 Lemma 8.2]. A cut of a width- product gives separated terms, and bases for successive suffix coefficient spaces give the converse. Local linear maps and regular specialization preserve upper bounds on cut ranks, by matrix multiplication and the vanishing of minors.
Lemma 2.2 (Leading coefficients). The lexicographically leading amplitude coefficient of is invariant along and inherits all cut-rank bounds of the translated polynomial in the coordinates under consideration. For a direction and an integer , the lowest nonzero coefficient in
is invariant along , inherits the latent cut-rank bounds and has all degrees in one residue class modulo . Here . For , is the leading coefficient in of .
Proof. Translating the amplitudes preserves their leading coefficient, which therefore descends to the quotient by the directions. Weights that are successive powers of realize lexicographic order on the amplitude monomials. Lemma 2.1 then gives the cut-rank bounds.
For each nonzero homogeneous part of , write for its lowest nonzero homogeneous component and . Then is the highest radial coefficient of , hence invariant along . In (3) its order is . At the minimum the contributing have distinct degrees in one residue class, so their sum is nonzero. The substitution acts separately on latent variables over , and division by the lowest power followed by specialization gives the rank bound. The terms from have -degree at most .
Lemma 2.3 (Interpolation in bounded digit degree). Let be the base- digit sum, with in characteristic zero. Write for the number of monomials with and . Their span is affine-stable and, over , admits an explicit interpolation set of this size. For , with . For ordinary total degree at most in variables the interpolation set has size , including .
Proof. In positive characteristic choose prime-field independent from nodes (the smaller spans have size at most ). Order the nodes , , by their digit labels. The first split into cosets of initial basis spans, by aligned base- blocks. The vanishing polynomial of a span is additive, since adjoining replaces by . Hence the Newton polynomial has digit degree at most . For the ordinary degree bound, take any distinct nodes in any characteristic.
The products on the indicated indices form a basis by their leading monomials [11]. Evaluation on is triangular with nonzero diagonal, since an entry vanishes unless for all . For ordinary degree the indices are simply . Dimension gives optimality over a common coefficient and working field. Counting at most digit copies among positions gives the binomial bound. Under affine substitution each Frobenius power has digit degree at most one, and carries only decrease digit weight.
Lemma 2.4 (Radial evaluation and field descent). Set and . Among distinct values of , some is a good anchor, where every hidden linear form is nonzero, since their product on the curve has degree at most . Rescaling the latent coordinates then turns invariance along the anchor into .
For , let be least with . In a power basis write an extension point as . The restriction has total degree at most , so Lemma 2.3 uses base-field queries. When , the curve uses only nodes. Since , enumeration finds a defining irreducible. For coefficients in an overfield take the compositum.
Suppose a common -point set over the anchor field hits the leading coefficient in of at each good anchor. Testing these points with all anchors and radial values detects a nonzero restriction. Including descent, the cost is , where if and otherwise.
Translation in adjacent differences
Put and for , over finite digit vectors. Then and .
Lemma 2.5 (Translation and ordered cuts). For an -dimensional polynomial representation of the additive group, implies . If and , its ordered cut ranks give a factorization
with constant matrices , , and -dimensional representations of degree at most . The total digit degree is at most and the weight at coordinate is at most . For a total-degree or residue-class grading in which is homogeneous, the are grade-preserving.
Proof. Coefficient comparison gives . In characteristic zero with nilpotent. In positive characteristic satisfy and
by Lucas’s identity. For take the graded-lexicographically largest with . Multiplying a relation among , , by for its least index leaves only that term. Thus and .
Let be a basis row of prefix polynomials obtained from suffix coefficients, and . A prefix shift equals the opposite suffix shift on . Thus . Writing gives and with . The endpoint representations are trivial, giving (4). Graded bases make each grade-preserving and an order- row-state transition raises grade by . Only adjacent factors contribute to a coordinate, and expanding differences cannot increase digit weight.
The arbitrary-width construction
Proposition 3.1 (Two generators). For one can compute integers satisfying
where depends only on . They give the following hitting sets for Theorem 1.1.
Over a working field of size at least , a polynomial map in scalar parameters gives a hitting set of size at most
In characteristic zero or greater than , one may take .
Over any working field of size at least , a moment curve and Shpilka–Volkovich pairs give a hitting set of size at most
Moreover, in characteristic zero or characteristic greater than . In every characteristic the same bound holds when for a fixed , with the implicit constant allowed to depend on .
For , Lemma 2.4 descends (6) at cost below per query. This proves the first bound of Theorem 1.1. From (5) the all-field count is . For finite , the required extension degree is . If , the univariate descent costs per point. Otherwise the whole -variable simplex has at most points. At take , . For use nodes. Given the field nodes, both constructions take polynomial time in for fixed .
For put
One may always take and . Section 3.3 supplies a second bound, and the smaller choice is valid at each rank. Section 3.4 constructs from these integers.
Coefficient spaces over truncated rings
Over a field , position carries , . We multiply over the tensor product of these rings. Its ideal of elements with zero constant term is nilpotent, so a matrix with invertible constant part is invertible. The support size of a monomial is the number of variables with positive exponent.
Let be the -span of the rows of the coefficient matrices of , and put for a constant row space . Multiplication gives . For disjoint positions each coefficient is a single product of local coefficients, so and supports add.
A matrix has unit rank if its constant rank is and its -minors vanish. Given a top left block with invertible constant part and top right block , every row in the row module satisfies . The bordered minors are the entries of the Schur complement times . Unit rank zero means .
Theorem 3.2. Let , with every nonempty interval of unit rank in . For any constant row , coefficients of support at most
span .
For set . If in , then
by . Suppose and let project onto the first coordinates. From a constant space , propagate . Choose basis lifts for and a basis for . Give the lifts initial cost zero and the kernel rows initial cost one. A coefficient’s cost is its initial row cost plus its support size.
The lemma below proves Theorem 3.2 at and , leaving support .
Lemma 3.3. Under the interval hypothesis of Theorem 3.2, if at every cut, coefficients of cost at most span .
Proof. Induct downwards on . Put , , and . The rows of cost zero and project to . This proves the case . For , handles the empty word.
If , the full word has constant rank . In the passive coordinates choose a complement of the left kernel of the full constant product. Its transported spaces map isomorphically under the suffix to . Pull back a complement of along each suffix to obtain complements of respected by the transitions. Transport bases of to normalize each constant to . These cut basis changes preserve interval unit ranks and supports.
The first- projections are nested under constant propagation. If the old kernel projects onto extra dimensions, they start in dimension and grow strictly at most times. Put . Initially one can choose lifts of cost at most and kernel rows of cost at most . On a stable subword, lifts of cost and kernel rows of cost at most yield spanning rows of cost at most by induction and disjointness of supports. One growth factor adds at most one to this common cost. After growth factors, and (9) give the final cost bound
If , take maximal with , and write and . We claim that . The suffix has unit rank and . For , all coefficients of lie in . If , the row-module identity gives . Otherwise write and . Since , the row-module identity yields , so . Conversely every row of belongs to .
Restart after from with lifts of cost zero and kernel basis of cost at most one. Every restarted space lies in and contains , hence projects onto . If , the passive suffix product is nonzero by maximality, so the preceding case applies at the same . For the restart already spans at cost one. In both cases its final span equals .
Local minors in the rank descent
For a nonzero polynomial , write for its lowest nonzero homogeneous component.
Lemma 3.4. Suppose every interval of has the same rank over as at zero, in . For constant endpoints , if , each monomial of has support at most .
Proof. For a chosen , reduce modulo at each position. Only divisors of survive, so minimality leaves a nonzero multiple of . The intervals have unit rank in the quotient. If the support exceeded , Theorem 3.2 would force to annihilate every coefficient row, including the chosen one.
Lemma 3.5. Let be a vector of univariate polynomials over , let be transcendental over , and let be linear. If has first nonzero order , then .
Proof. We use Schmidt’s order-sequence criterion [4 Prop. 1.1]. Put . For with in , lies outside the -span of earlier . Indeed has order at least in , with equality at . Transcendence makes the coefficients of any rational dependence regular at , so earlier vectors cannot produce that order. Thus there are at most such indices. There are in characteristic zero and for by expanding .
Fix a monomial in the lowest homogeneous component of a scalar word. Extracting the coefficient of its prescribed powers outside an interval gives a scalar contraction of that interval with constant endpoints. The retained monomial lies in its lowest homogeneous component by minimality of the original degree. In particular at a single position the first order is . For a width- matrix at with individually transcendental, Lemma 3.5 gives , or for the end row or column of a matrix entry. The contraction coefficients may depend on every center.
Interval tests. Pad the matrices to size with zero states. Affine invertibility gives the latent scalar total degree at most . Truncate each factor at degree . Each scalar coefficient was a single product of local coefficients, so deleting exponents above preserves the scalar. Use the resulting generic ranks and augment the word by and , leaving just the scalar in entry .
At latent centers , all individually transcendental over , translation to independent residual variables preserves generic ranks. Call an interval preserved if its rank at equals its generic rank. The moment curve preserves full-rank intervals since each relevant univariate determinant is nonzero at its center. This holds for any transcendental .
Lemma 3.6. Suppose every interval of generic rank greater than is preserved. There are rank- tests whose preservation suffices for all rank- intervals. Each test has one possibly empty chunk of generic rank greater than , with at most one factor on either end. The lowest homogeneous component of every nonzero test minor of order has digit degree at most and ordinary degree at most .
Proof. In a target of rank , test its first rank- prefix . All later prefixes still have rank . For , let be the shortest rank- suffix of and test . This has rank by containment between and . Minimality makes the first test’s prefix before and each later test’s interior empty or of rank greater than . If is preserved, its specialized row space equals that of by inclusion and the generic rank bound. Appending the next factor and using the test proves preservation of .
By Cauchy–Binet, each minor is an entry of a word of th compounds, of width and local degree at most . Rank becomes by a change of bases. All chunk intervals are preserved and have compound ranks in the set
Its positive gaps after the first are , so (8) gives . For any monomial of lowest degree, extract the exponents outside the chunk and apply Lemma 3.4. The at most selected chunk positions contribute at most each, and the boundary factors at most each. The local degree bound gives the ordinary estimate. □
Substitution preserves the nonzero first homogeneous part and its degree. In characteristic , expand each power in base and apply Frobenius to the linear forms. Adding exponents only decreases digit sums, so digit degree cannot increase. A perturbation detecting these lowest homogeneous components preserves the required minors. Earlier ranks persist if the perturbation can be set to zero. The augmented word has generic rank one for nonzero , so descending to suffices. In (7), and give .
Factorial width dependence from image cones
Set and for . We prove the alternative budget
Take in Proposition 3.1. Let be the Zariski closure, over an algebraic closure, of scalar multiples of the values of . This cone is irreducible. Restrictions set unselected blocks to zero. Cone equality preserves homogeneous identities and thus the annihilator of the coefficient span of each compound, also over the coefficient field. Cone-preserving restrictions compose on disjoint blocks by density under multiplication.
Cone restrictions for a rank profile. Suppose every interval has its generic rank at zero and the full word has rank . We prove that retained blocks suffice. For , normalize the constants to identities. The prefix cones are nested. If a step is stable, fixing its factor to the identity preserves that prefix cone and hence all later cones by composition. The cones start at the line through in dimension , allowing at most strict steps.
First consider rank- factors with . For constant of size put and , where takes the first columns. These cones are nested since . If , fix . At any value of with invertible top left block and top right block , every output with first columns equals by rank . The restricted projected cone at that value is , a closed irreducible subset of with the same dimension, so . The graph formula then places each original output at this value in the restricted cone. Such values are dense since . The restriction keeps and preserves the cone of , hence also every later prefix cone.
Retain strict-growth blocks and the last block of each stable run. When , the projected cones start at a line in dimension , giving at most retained blocks. For , keep and pass to its function field. Factor using its first columns. Apply the rectangular bound to and multiply by . A homogeneous identity on the restriction holds over the function field, hence on the full word as a polynomial identity over the original field. This gives blocks.
For , greedily cut at shortest rank- prefixes and absorb the final tail into the last block. Each nonempty and tail, and all their subintervals, have rank greater than . Induction and composition reduce each selected block to at most positions. At each internal cut the image of the right constant block complements the kernel of the left, since their product has rank . At the ends take the first image and a complement of the last kernel. Transport active bases along the maps and choose passive kernel bases to normalize all block constants to . Selecting at most such blocks gives the stated bound on .
Degree of a test. Local compounds have degree at most . If or , order equals digit weight on this range. Lemma 3.5 bounds the first order of every nonzero linear contraction by . Thus the local coefficients of degrees at most span the full coefficient space by duality.
The chunk cone of each test is preserved on at most positions. Expand the retained compounds using their spanning coefficients of degree at most , and do the same at the at most two boundary factors. Disjoint variables make the resulting products actual coefficients of degree at most . They span the coefficient space of the test compound by cone equality, giving (10) for ordinary and digit degree.
The recurrence is decreasing in , with . Thus . Summing gives , with a factor at most from if or , and at most otherwise.
Construction of the generators
An exponent digit on represents copies of in positive characteristic. In characteristic zero an exponent gives copies of . Under , Frobenius or ordinary expansion assigns each copy to a summand. For a monomial of maximum digit degree , assign its copies to distinct indices. Any term with these indices uses exactly one copy at each. Specifying its coordinate and power at each index then recovers the monomial, with coefficient multiplied by the product of digit factorials (ordinary exponent factorials in characteristic zero). This multiplier is nonzero.
A shared parameter. For put . By Lemma 3.6 and § 3.3, each lowest homogeneous component has ordinary degree at most . This bound is , and if or . For set and . For set and .
Take the first primes with , excluding divisors of when . At each prime choose nonzero residues so that
is injective on . (11)
The exclusions distinguish the powers at each coordinate. The ratios of two powers forbid at most new residues per previous choice, leaving an admissible residue at each step.
The excluded primes have total logarithm at most for , and otherwise. Set . The estimates for give for the prime sum [3]. Since , the interval contains at least admissible primes. Their product satisfies the stated bound, using and . For we have .
Partition the chosen primes into sets of size and put . Define
Before stage the earlier exponents are divisible by , so the coordinates lie in . The distinct leading powers dominate all corrections of degree below , keeping each latent center individually transcendental over .
Lemma 3.7. If has digit degree at most and ordinary degree at most , then .
Proof. Distinct exponent classes modulo are independent over by clearing denominators. Assign the copies of a maximum-digit monomial to distinct primes in . Its exponent has nonzero residue at each chosen , where only that prime’s summand contributes and is a unit. Thus every assignment in this class uses all primes. By maximality it uses one copy per prime, each determined by (11). These assignments yield the same integer exponent, with the nonzero factorial multiplier above. This includes the constant case .
The translated minors are over , and field extension preserves ranks. For each required minor with lowest homogeneous component in observed coordinates, the coefficient of after adding is . Earlier ranks persist by setting . Rank descent gives , with degree at most in . For fixed , the map is affine in the entire amplitude vector , so Lemma 2.3 uses amplitude nodes. This gives (5), including the moment curve at .
Interpolation over the smaller field
Take distinct nodes with degree- Lagrange polynomials , and put . Starting at add at stage with fresh pairs [14]. For a lowest homogeneous component assign the copies of a maximum-digit monomial to the first pairs, with powers . For formal vectors , the coefficient of is a nonzero linear combination of the products by the copy argument. Higher homogeneous components have larger amplitude degree. Substituting keeps the coefficient nonzero, since node tuples recover its individual scalars. A nonzero constant component survives at zero amplitudes. The rank descent leaves a nonzero polynomial. The degrees in and each are at most and , respectively. For fixed the map is affine in the amplitudes, giving nodes by Lemma 2.3.
For the smaller direction grid, keep the inclusion-maximal test intervals with at least two variable factors. Tests with at most one variable are automatic by transcendence. Each other discarded test lies in a retained interval, so its rank is at least the retained rank and at most its generic rank . The retained intervals have distinct left endpoints, at most including the left boundary. For one nonzero minor per retained interval, its selected coefficient has degree at most in each occurring . After partial specialization, at most values of the next can kill a surviving coefficient, since is the identity or an injective Frobenius power. Thus any grids of size let us fix the directions one at a time while preserving all chosen minors. The moment curve keeps later centers transcendental. Interpolate in and the amplitudes to obtain (6) with the smaller of the two direction grids.
Degree bounds for one hidden order
In this section after absorbing constants. Complete the independent forms to a basis using identity layers. Let be the cut ranks of in its hidden order. For a finite, nonempty exponent set , write for the largest vanishing order at of a nonzero polynomial supported on .
Proposition 4.1 (Exponent sets and cut ranks). Assume .
The degree-linear bound (1) holds if the exponent sets of the top homogeneous component in the latent variables satisfy for a fixed . This includes characteristic zero and . In positive characteristic, distinct residues modulo , or modulo , also suffice.
In positive characteristic put . For a supplied bound on the counts are
In particular the second bound holds whenever , using .
Proof. Write for the top homogeneous latent component. Scaling all variables and taking the leading term gives the same cut-rank upper bounds as . In homogeneous bases of the prefix spaces, each transfer entry is a monomial whose exponent is a difference of basis degrees, so .
In characteristic zero, or when the exponents are distinct modulo , the determinant of the first binomial rows is the Vandermonde determinant on divided by . Thus . In positive characteristic group the exponents of by residue, writing . With empty classes omitted and for a singleton, the exact recursion is
At the polynomial is . The independent polynomials separate the residue classes in each block of consecutive orders. Vanishing below forces each nonzero to attain order . In the next block the leading scalars of precisely those classes with vary freely. The same Vandermonde calculation gives (14). Iteration bounds by for distinct residues modulo . The substitution gives the same result at any .
Choose a good anchor and put . To bound an exponent of a monomial of in the latent variables, extract its prescribed powers in the other variables. The exponent is the first surviving order of a shifted univariate polynomial supported on . We may bound all by the known value if or , and by under the exponent-set promise. Thus has latent width at most , latent individual degree at most and total degree at most .
Use (6) with total degree and individual degree at most to find with , taking when . Write and . In the top homogeneous part contributes , while each lower homogeneous part contributes a smaller power of . Hence choices for and for suffice. Work over a field supplying nodes and descend the final query points together by Lemma 2.4. If , then since . All factors other than are therefore bounded by .
For the rank-profile bounds, use the entire highest radial coefficient of . After latent rescaling it is invariant under common translation. Lemmas 2.5, 2.3 and 2.4 give the first count from its digit budget . For , give each factor of (4) its own digit variables , . Replacing in the divided-power expansion by factors the lift into univariate matrices of the original width, where . Passing to independent difference coordinates preserves the digit bound by affine stability. In the lift each digit variable of an edge has exponent below , so distinct monomials encode distinct exponent vectors. The lifted polynomial therefore has ordinary degree at most .
Complete the difference forms to a frame with an identity layer. For the prime-field basis in Lemma 2.3, set with . The powers of the forms become . To see that these linear forms are independent, observe that the Moore matrix is invertible by the root bound for an additive polynomial of degree at most on a span of size , and each coefficient matrix is invertible. The lift agrees with on the prime grid and is nonzero by interpolation on that span. Apply (1) at degree in variables. The construction can take its nodes in a finite extension of in a compositum with the coefficient field. Descend its points to by power-basis interpolation at degree . We may cap at , so these grid and descent thresholds are polynomial in (here the individual degree is below ). Basis summation returns physical directions. The outer radial nodes and any anchor descent give the second bound. □
The ordinary rank-profile estimate is sharp on radial coefficients. In characteristic zero, at attains total degree and, for , individual degree . Each cut crosses just one factor. In characteristic , already has ordinary vanishing order at width two.
Digit degree across all variable orders
Write for the mean cut rank and for the largest total digit weight of a monomial. For an invariant , shifting is equivalent to shifting oppositely, so every cut coefficient space is translation-stable.
Lemma 5.1 (Ordinary degree from all cuts). If is homogeneous of degree , invariant under common translation, and or , then
Proof. Lemma 2.5 bounds by . By homogeneity its multiplicity at is at least . The multiplicity Schwartz–Zippel bound gives mean multiplicity at most on [2]. Use for the last bound.
The three-variable Vandermonde attains equality in characteristic zero, with degree and nontrivial cut ranks all equal to three.
Lemma 5.2 (Permutation support). Let be a nonzero tensor supported on permutations of , with all cut ranks at most . Suppose each supported permutation has, for every -set of positions, a distinct supported permutation agreeing outside that set. If , then
Proof. Build a binary tree of depth . At each internal node at least positions remain unqueried, so two compatible permutations differ at some unqueried position. Branch on two distinct values there. Choose one compatible permutation at each leaf.
For a uniform random subset , let count the distinct preimages at leaves below node . At a branch the two families are disjoint if exactly one of its two values belongs to , an event of probability . Thus is at least the geometric mean of the two child counts, and at least twice that mean on this event. Taking expected base-two logarithms and inducting from the leaves gives .
For fixed , distinct images index disjoint nonzero blocks of the cut matrix. Counting pairs therefore gives . Jensen’s inequality gives (16).
Lemma 5.3 (Digit degree from layer capacities). Let be invariant under common translation in characteristic , with every cut rank at most . Put and . In a maximum-digit-degree monomial, chosen with lexicographically largest digit counts from the highest layer down, let be the maximum matching size between coordinates and occupied layers. If each layer contains at most copies, then
Put , , and . One may always use
If , one may also use .
Proof. By Lemma 2.5, a singleton shift followed by setting the shifted variable to zero bounds every exponent’s digit weight by , and every subset shift has zero coefficient at orders of weight greater than . Inclusion–exclusion on shifts by subsets of retains precisely the Taylor increments with support .
Write for the chosen monomial. Packing digits toward minimizes the product of one plus each digit at fixed digit sum, so and . If a power occupied coordinates , use inclusion–exclusion on at order and extract . Lucas’ identity and maximal digit degree force exactly one translated copy per coordinate in . The descending-layer tie excludes powers above , so their sum forces all copies to equal . The unique source contributes nontrivially, contradicting the shift-order bound. This proves (18).
For the matching bound, encode each power by and use the truncated algebra . In the physical shift , Frobenius sends to . A carry in lowers the combined digit degree. The terms of highest digit degree are therefore invariant under the truncated shifts . That identity respects the combined layer counts in and . Keep the lexicographically largest layer-count component , which contains the encoding of . Relabeling monomials separately by coordinate and taking leading components by digit degree and successive layer degrees preserve every original cut-rank bound, with the variables grouped by .
At each cut the coefficient space of is multigraded by layer counts. A truncated shift on one side equals the opposite shift on the other by simultaneous invariance, so this space is stable under its side’s shifts. Write for the coefficient operator of . The shifts compose in the truncated algebra, giving for coordinatewise. If for a homogeneous , then the are nonzero of distinct multidegrees. Thus , and the coefficient of every squarefree -monomial of degree vanishes at every subset shift.
For a maximum matching with coordinates , differentiate by the Hasse multiorder that leaves one copy of each matched layer in its matched coordinate of . Set variables outside to zero and retain terms using all coordinates of . Exactly one copy of each matched layer remains, giving a nonzero permutation tensor . Each cut of has rank at most that of any extension of the cut to the omitted coordinates, since all operations are local. Averaging gives . For a supported assignment and a -set , work before deleting terms missing coordinates. Apply inclusion–exclusion over shifts of subsets of at the squarefree multiorder given by its layers on . The Hasse derivative is coefficient extraction after an independent truncated shift, so it commutes with these shifts. Evaluation outside commutes with them as well. Setting the groups in to zero and extracting the assignment off sums exactly the coefficients of permutations agreeing off , since inclusion–exclusion enforces support on all of . The sum vanishes, so a distinct alternative exists. For Lemma 5.2 bounds as claimed. For the bound follows from . Kőnig’s theorem gives a vertex cover of size , accounting for all digit copies at cost at most per coordinate and per layer.
For , suppose a layer has at least copies. Differentiate to retain of them. The resulting degree- polynomial remains invariant under truncated shifts. Project onto the selected layer by setting the others to zero. The selected monomial survives, and all cut ranks remain at most . The shift in this layer is now a formal identity since , contradicting (15).
Proof of Theorem 1.2. Choose a good anchor by Lemma 2.4. The highest coefficient of becomes an invariant after rescaling the latent coordinates, and inherits all cut-rank upper bounds by Lemma 2.2. For the coefficient is constant by Lemma 2.5, so at each anchor the direction set is . If or , apply Lemma 5.1 to the highest homogeneous component. If , all latent exponents of lie below , so the sharper layer capacity bounds ordinary degree. Thus the ordinary interpolation grid of degree at most supplies the directions.
For put . By (17) the digit budget is , using the maximal available capacity. Here and , with when .
Affine substitution preserves the digit budget, so Lemmas 2.3 and 2.4 give queries. A padded list of digit positions gives , proving (2). The ordinary grid has at most nodes.
Proposition 5.4 (Singleton and pair cuts at width two). Let as a polynomial identity. Its singleton and pair cut ranks are at most two if and only if
Consequently the affine orbit of an input with these cut ranks admits a hitting set of size , with as in Lemma 2.4. Take in characteristic zero and otherwise.
Proof. The coefficient space on either side of a cut is stable under simultaneous translation of its variables. An active singleton space of dimension at most two contains , by taking the highest translation coefficient of a nonconstant member. Its other basis vector , normalized by , is additive, since every positive-order coefficient in has smaller -degree and is therefore constant. Thus is multilinear in the separate variables .
If two such variables occur together, some coefficient on their side of the cut is with . Under simultaneous translation the coefficient of in is a nonzero constant. Another positive-order coefficient has a nonzero linear part, since that part of the increment is . Together with , these coefficients give three independent vectors in the pair space. Hence is a sum of additive polynomials, and invariance gives the displayed identity. Conversely an additive sum has rank at most two across every cut.
Apply this description to the highest radial coefficient at a good anchor. Its digit degree is at most one, also after the observed affine substitution. Lemmas 2.4 and 2.3 give the stated count since .
The invariant has singleton ranks two and rank four at .
Transfer for dependent forms and multivariate layers
Consider the more general model
with matrices of width at most . Their arguments can be tuples, with repeated or dependent forms. Let be the row span of , , , and . On the effective space , of dimension , put
The matroid cut connectivity is [8]. For univariate layers its maximum equals .
Theorem 6.1 (Transfer to independent forms). If , model (19) has a polynomial-size hitting set over every field with for fixed , independently of the number of layers and their local degrees. In characteristic zero or , and in any characteristic at , its size is at most
Over the reduction preserves width and uses an independent-form set from Proposition 3.1, with query count
For independent blocks of size at most , and . A single width-one layer contains all degree- polynomials in variables, which require at least evaluations over a common coefficient and working field. This proves sharpness of the degree exponent for fixed , and for fixed by taking . In a univariate word . If the forms are drawn from a basis, counts the basis directions used on both sides.
Proof. Write with onto and . Set , . The first flag increases and the second decreases. The codimensions of and are and , respectively. The interleaved sequence of pairs changes at most times.
At put and . For choose of order at least and set for the curve of Lemma 2.4. Testing the first powers excludes at most candidates. If needed, enumerate , which is then finite and cyclic. For each flag pair take independent forms on . Their pullbacks evaluated on give independent polynomials of degrees at most . Row reduction gives distinct leading degrees . The first folded directions have a minor of degree at most with leading coefficient proportional to the nonzero Vandermonde in [6 Lemma 12]. The product of the selected minors has degree below .
Work first over . Quotient by the span of the projected directions, writing primes for images in . The minors give and . At both follow from (20). Refine the ascending flag one dimension at a time. At each step add a vector in the smallest descending space whose intersection grows. It accounts for the growth in every larger space, giving a basis adapted to both flags. Group the vectors by their first . Since , every later group lies in . Group has precisely vectors outside . Put the exceptional vector first when it exists. At every cut after a vector of group , the prefix thus lifts to and the suffix to .
The leading amplitude coefficient of descends to by Lemma 2.2. With these lifts at a given cut, layers through ignore the suffix, and later layers ignore the prefix. The word splits into terms across the cut, and taking the leading coefficient preserves its rank bound. By Lemma 2.1 the quotient polynomial has width in this basis. Pullback to the observed coordinates uses independent forms, completed by identity layers. Some therefore makes nonzero over , since the construction works with grid nodes in and coefficients in .
The same argument works at any where the selected minors survive, so nodes suffice. Alternatively, for the just obtained the degree in is at most , giving the other grid in (22). At a surviving value of the restriction is affine in before applying , and nodes suffice by Lemma 2.3.
For (21) use numerical and (1). Apart from , the field thresholds in its proof are polynomial in here since . At width one all independent univariate factors survive on a good radial line in any characteristic. Lemma 2.4 descends both constructions, and the full grid suffices if . For unrestricted characteristic descend (22) from a field supplying nodes.
Width two in hidden coordinates
Theorem 7.1 (Width two in one order). In two variables, queries suffice over every field with . In variables put . For the counts are for affine translates of homogeneous inputs and for arbitrary inputs, with an extra factor of at most when .
For arbitrary inputs there is also a set of size over , where and uniformly in the characteristic.
Lemma 7.2 (Factorization at width two). Let of degree at most be invariant under common translation and have width at most two in one order. Suppose is homogeneous, or homogeneous modulo with the signed powers () distinct and nonzero modulo . In characteristic zero use . Up to a scalar over the algebraic closure, is a product of at most powers of linear forms on disjoint intervals of adjacent differences. The powers are in positive characteristic and one in characteristic zero.
Proof. Use graded bases in (4). Each constant bridge is nonzero. Split every rank-one bridge through a line in its grade. Between splits the remaining bridges are invertible and identify at most two grades. A nonconstant transition has order (one in characteristic zero), by . Its grade difference is nonzero and uniquely determines its order and orientation. Each path in a factor therefore uses at most one such transition. The endpoint grades make the factor constant or a sum of powers of the same order in separate differences, hence a power of a linear form. The nonconstant factors occupy disjoint nonempty intervals.
Proof of the -variable bounds. Choose anchors on the curve of Lemma 2.4. Choose another points on . These hit every product of powers of at most nonzero affine linear forms, since the product of their distinct underlying forms restricts to a nonzero polynomial of degree at most .
For the homogeneous top part of degree , the lowest homogeneous component has the factorization of Lemma 7.2 after latent rescaling. Write . For a translate , some has , and . For arbitrary , some has . Interpolation uses radial nodes in the first case and nodes in the second. Lemma 2.4 handles the anchor threshold.
For the weighted construction take if or . Otherwise set and choose an odd prime . All signed powers are then distinct nonzero residues. The excluded primes have total logarithm , so the prime estimate in § 3.4 gives . Some hits the factored leading coefficient in (3). Query the origin once. If , a term of degree contributes -degree at most . Evaluating at nonzero scales per pair suffices.
Width two in every order
Corollary 7.3. If the latent width is at most two in every order, queries suffice for . For the same construction with quadratic curves gives queries. Over a common coefficient and working field, sums of univariates give the lower bound by dimension.
Proof. Work over the algebraic closure and split off the rank-one modes from the coefficient tensor. With at most two remaining modes use ordinary matrix rank. Otherwise their singleton ranks are two, and the first pair spans a two-dimensional pencil of matrices. Indeed, if the pair cut had rank one, the tensor would be with of rank two. Every remaining mode of has rank two, so a cut containing mode 1 and one such mode has rank four. An entirely singular pencil has a common left or right factor, which would give singleton rank one. Over , the classification also follows from the secant equations of Landsberg and Manivel [9], Theorem 5.1.
Two distinct determinant roots give the form . Cuts separating the first pair are block diagonal, so are products. At a double root normalize an invertible member to . For the singular member , the double root of gives , so is rank-one nilpotent. A change of bases gives . The same cuts have block matrix of rank at least , so is a product. Write for the number of remaining modes and choose bases with . A minor bordering the two off-diagonal pivots forces any entry of with deviations on both sides of the cut to vanish. Thus is a sum of products with at most one factor replaced.
Apart from pure products, vanishing on a curve with nonconstant latent coordinates therefore gives or for univariate rational functions, at least one nonconstant. In positive characteristic remove common Frobenius powers until some (over a perfect field ). Differentiation gives
with some in every characteristic. Pure products already survive on such a curve.
For use and its perturbations , . Write for a latent coordinate on and for its linear part in the observed variables. Each is nonconstant. A degree-one requires proportional to , so there is at most one. In that case use , on which the other linear forms remain independent.
For and , let be the leading Laurent term of and the leading coefficient of . Put over these indices if any exist. Subtract (23) on from the perturbed identity. The coefficient at is
Indeed the first variation in is . Each remaining term contains at least two perturbation factors or . Its Laurent degree is at most , since . One of makes nonzero, contradicting independence. If only a degree-one term survives, (23) already fails on . The curves have degree at most , giving the first count. For the second take for each of the anchors. At a good every , so the same argument applies with nodes per curve. For use univariate interpolation.
Two variables. The two orders have the same width in two variables, as their coefficient matrices are transposes. The moment curve family gives queries for . For , test points per line. Absorb the translations into the univariates so that are linear. A rank-two polynomial is with independent pairs. On a line where both latent coordinates vary, vanishing implies with , nonconstant of degree at most . A product already survives there. At most two directions are bad. If the test vanishes on a good origin line and a distinct parallel , then is a nonzero period of . The period group has at most elements. Indeed the numerator of over has degree at most in and has a distinct root for each period.
When , take three origin lines. For each, add its translates by the prime-field basis multiples of a transverse vector. A good line gives periods spanning a group of size . This uses lines.
For , choose a generator of and three disjoint quartets of directions of cross-ratio . Map to a finite quartet and take disjoint translates. Each previous quartet excludes at most shifts, and . Use all twelve origin lines and add one distinct parallel for each of three of them. At least one parallel pair is good, giving a nonzero period , and some quartet is wholly good. Fix a slope in that quartet. For each of its slopes , the origin identities give . The period group is additive and stable under multiplication by the ratios , hence by the -algebra they generate. This finite subalgebra of is a field. The change to latent coordinates and the common scaling preserve the cross-ratio, so the field contains and equals . The period group contains , of size . This proves the bivariate bound.
Acknowledgment. The author used OpenAI models to formulate results, develop and review proofs, draft the manuscript, and implement finite checks. The source manuscripts [10] were prepared with GPT-6 Astra Pro.
References
- [1]V. Bhargava and S. Ghosh. Improved hitting set for orbit of ROABPs. Computational Complexity 31 (2022), article 15.
- [2]Z. Dvir, S. Kopparty, S. Saraf and M. Sudan. Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. SIAM Journal on Computing 42 (2013), 2305–2328.
- [3]M. Eberl. Concrete bounds for Chebyshev’s prime counting functions. Archive of Formal Proofs (2024).
- [4]A. Garcia and R. F. Lax. Weierstrass weight of Gorenstein singularities with one or two branches. arXiv:alg-geom/9208003 (1992).arxiv.org/abs/alg-geom/9208003
- [5]R. Gurjar, A. Korwar and N. Saxena. Identity testing for constant-width, and any-order read-once oblivious arithmetic branching programs. Theory of Computing 13(2) (2017), 1–21.DOI
- [6]V. Guruswami and S. Kopparty. Explicit subspace designs. Combinatorica 36 (2016), 161–185.
- [7]I. Hu, D. van Melkebeek and A. Morgan. Polynomial identity testing via evaluation of rational functions. Theory of Computing 20(1) (2024), 1–70.DOI
- [8]N. Kashyap. Matroid pathwidth and code trellis complexity. SIAM Journal on Discrete Mathematics 22 (2008), 256–272.arxiv.org/abs/0705.1384
- [9]J. M. Landsberg and L. Manivel. On the ideals of secant varieties of Segre varieties. Foundations of Computational Mathematics 4 (2004), 397–422.DOI
- [10]Yilin Liu and GPT-6 Astra Pro. Affine-orbit polynomial identity testing. Algorithm Frontier, source snapshot 77140c2 (2026).
- [11]R. D. Neidinger. Multivariate polynomial interpolation in Newton forms. SIAM Review 61 (2019), 361–381.DOI
- [12]C. Saha and B. Thankey. Hitting sets for orbits of circuit classes and polynomial families. ACM Transactions on Computational Theory 16(3) (2024), article 14.
- [13]A. Shpilka. Polynomial-size hitting sets for multilinear any-order read-once algebraic branching programs and for set-multilinear depth-3 circuits with constant-size variable sets. ECCC TR26-314 (2026).
- [14]A. Shpilka and I. Volkovich. On reconstruction and testing of read-once formulas. Theory of Computing 10(18) (2014), 465–514.
- [15]S. Singh and V. Singh. An algebraic rigidity framework for order-oblivious deterministic black-box PIT of ROABPs. arXiv:2602.13449v1 (2026).arxiv.org/abs/2602.13449