betaFeedback

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 E⊇FE \supseteq F to f(X)=F(AX+c)f(X) = F(AX + c), where A∈GL⁡n(F)A \in\operatorname{GL}_n(F) and c∈Fnc \in F^n are unknown. In the hidden coordinates the polynomial is computed by a width-ww read-once oblivious algebraic branching program (ROABP),

F(Y)=uA1(Yπ(1))⋯An(Yπ(n))v,F(Y) = uA_1(Y_{\pi(1)}) \cdots A_n(Y_{\pi(n)})v,

with univariate polynomial matrices of width at most ww, a constant row uu, a constant column vv, and an unknown variable order π\pi. A hitting set is a finite subset of EnE^n on which every nonzero polynomial in the class has a nonzero value. Write D≥1D \ge1 for a total-degree bound and p=char⁡Fp = \operatorname{char} F. We may use any upper bound 1≤d≤D1 \le d \le D on the individual degree of FF, including d=Dd = D. We count field operations and oracle queries, given distinct field elements for the evaluation grids.

Theorem 1.1 (One unknown order, arbitrary width). For nn, ww, D≥1D \ge1 and ∣E∣>D|E| > D, the affine orbit of width-ww ROABPs in one unknown order admits an explicit hitting set of size

(nD+1)2O(w2).(nD + 1)2^{O(w^2)}.

In characteristic zero, or in characteristic p>dp > d, there is a hitting set of size

(D+1)(n+1)2O(wlog⁡(w+1)).(1)(D + 1)(n + 1)^{2^{O(w\log(w+1))}}. \tag*{(1)}

§ 3 proves the arbitrary-characteristic bound by two generators. The first uses ww scalar parameters. The second uses a moment curve and 2O(w2)2^{O(w^2)} interpolation pairs. § 4 derives (1) from the exponent sets of the top homogeneous component.

Theorem 1.2 (Every variable order). Suppose FF admits width at most ww in every variable order, with matrices depending on the order. For ∣E∣>D|E| > D, a hitting set of size (D+1)(n+1)O(w)(D+1)(n+1)^{O(w)} suffices if p=0p=0, p>Dp>D, or p>max⁡{d,2w−2}p>\max\{d,2w-2\}. In positive characteristic let L=⌈log⁡p(D+1)⌉L=\lceil\log_p(D+1)\rceil. With no restriction on dd the size is

(D+1)(nL+1)κ,κ={O(w2log⁡(w+1))uniformly in p,Op(wlog⁡(w+1))at fixed p,O(wlog⁡(w+1))uniformly for p>2w−2.(2)(D + 1)(nL + 1)^\kappa,\qquad \kappa= \begin{cases} O(w^2\log(w+1)) & \text{uniformly in }p,\\ O_p(w\log(w+1)) & \text{at fixed }p,\\ O(w\log(w+1)) & \text{uniformly for }p > 2w-2. \end{cases} \tag*{(2)}

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 bb variables the degree exponent is bb in characteristic zero or above DD, sharp already at width one. In two variables, 15(D+1)15(D+1) queries suffice at width two whenever ∣E∣>D|E| > D (Theorem 7.1).

Related work. Saha and Thankey [12] studied affine orbits of circuit classes including multilinear ROABPs. In characteristic zero or greater than dd, Bhargava and Ghosh [1] obtained bounds of (ndw)O(w2log⁡nmin⁡{w2,dlog⁡w})(ndw)^{O(w^{2}\log n\min\{w^{2},d\log w\})} for one unknown order and (ndw)O(min⁡{w2,dlog⁡w})(ndw)^{O(\min\{w^{2},d\log w\})} 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 r(I)r(I) denote the rank of the coefficient matrix with rows indexed by monomials on II and columns by monomials on IcI^{c}. A polynomial admits width at most ww in an order precisely when r(I)≤wr(I) \le w at every prefix [7 Lemma 8.2]. A cut of a width-ww product gives ww 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 F(Y+∑jzjvj)F(Y+\sum_j z_jv_j) is invariant along span⁡{vj}\operatorname{span}\{v_j\} and inherits all cut-rank bounds of the translated polynomial in the coordinates under consideration. For a direction aa and an integer M≥1M \ge1, the lowest nonzero coefficient J(X)J(X) in

R(t,X)=tMef(a+tXtM),e=deg⁡f,(3)R(t,X) = t^{Me} f\left(\frac{a+tX}{t^M}\right), \qquad e = \deg f, \tag*{(3)}

is invariant along aa, inherits the latent cut-rank bounds and has all degrees in one residue class modulo MM. Here deg⁡tR≤MD\deg_t R \le MD. For M=1M=1, JJ is the leading coefficient in rr of f(ra+X)f(ra+X).

Proof. Translating the amplitudes preserves their leading coefficient, which therefore descends to the quotient by the directions. Weights that are successive powers of D+1D+1 realize lexicographic order on the amplitude monomials. Lemma 2.1 then gives the cut-rank bounds.

For each nonzero homogeneous part PkP_k of ff, write Jk=in⁡0Pk(a+X)J_k=\operatorname{in}_0 P_k(a+X) for its lowest nonzero homogeneous component and jk=deg⁡Jkj_k=\deg J_k. Then JkJ_k is the highest radial coefficient of Pk(ra+X)P_k(ra+X), hence invariant along aa. In (3) its order is M(e−k)+jkM(e-k)+j_k. At the minimum the contributing JkJ_k have distinct degrees in one residue class, so their sum is nonzero. The substitution acts separately on latent variables over E(t)E(t), and division by the lowest power followed by specialization gives the rank bound. The terms from PkP_k have tt-degree at most M(e−k)+k≤MDM(e-k)+k \le MD. □\square

Lemma 2.3 (Interpolation in bounded digit degree). Let wt⁡(j)\operatorname{wt}(j) be the base-pp digit sum, with wt⁡(j)=j\operatorname{wt}(j)=j in characteristic zero. Write Hp(n,D,K)H_p(n,D,K) for the number of monomials XαX^\alpha with ∣α∣≤D|\alpha|\le D and ∑iwt⁡(αi)≤K\sum_i\operatorname{wt}(\alpha_i)\le K. Their span is affine-stable and, over ∣E∣>D|E|>D, admits an explicit interpolation set of this size. For p>0p>0, Hp(n,D,K)≤(nL+KK)H_p(n,D,K)\le\binom{nL+K}{K} with L=⌈log⁡p(D+1)⌉L=\lceil\log_p(D+1)\rceil. For ordinary total degree at most DD in mm variables the interpolation set has size Δm(D)=(D+mm)\Delta_m(D)=\binom{D+m}{m}, including Δ0(D)=1\Delta_0(D)=1.

Proof. In positive characteristic choose LL prime-field independent vev_e from D+1D+1 nodes (the smaller spans have size at most DD). Order the nodes xj=∑ejevex_j=\sum_e j_ev_e, 0≤j≤D0\le j\le D, by their digit labels. The first jj split into wt⁡(j)\operatorname{wt}(j) cosets of initial basis spans, by aligned base-pp blocks. The vanishing polynomial SS of a span is additive, since adjoining vv replaces SS by Sp−S(v)p−1SS^p-S(v)^{p-1}S. Hence the Newton polynomial Nj(T)=∏h<j(T−xh)N_j(T)=\prod_{h<j}(T-x_h) has digit degree at most wt⁡(j)\operatorname{wt}(j). For the ordinary degree bound, take any D+1D+1 distinct nodes in any characteristic.

The products ∏iNαi(Xi)\prod_iN_{\alpha_i}(X_i) on the indicated indices form a basis by their leading monomials [11]. Evaluation on (xβi)i(x_{\beta_i})_i is triangular with nonzero diagonal, since an entry vanishes unless βi≥αi\beta_i\ge\alpha_i for all ii. For ordinary degree the indices are simply ∣α∣≤D|\alpha|\le D. Dimension gives optimality over a common coefficient and working field. Counting at most KK digit copies among nLnL 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 Q=n(n−1)+1Q=n(n-1)+1 and a(u)=(1,u,…,un−1)a(u)=(1,u,\ldots,u^{n-1}). Among QQ distinct values of uu, some a(u)a(u) is a good anchor, where every hidden linear form is nonzero, since their product on the curve has degree at most Q−1Q-1. Rescaling the latent coordinates then turns invariance along the anchor into H(Y+t1)=H(Y)H(Y+t\mathbf{1})=H(Y).

For D<q=∣E∣<UD<q=|E|<U, let ss be least with qs≥Uq^s\ge U. In a power basis write an extension point as x=∑j=0s−1θjxjx=\sum_{j=0}^{s-1}\theta^jx_j. The restriction f(x0+∑j=1s−1tjxj)f(x_0+\sum_{j=1}^{s-1}t^jx_j) has total degree at most DD, so Lemma 2.3 uses Δs−1(D)≤(D+1)s−1≤qs−1<U\Delta_{s-1}(D)\le(D+1)^{s-1}\le q^{s-1}<U base-field queries. When (s−1)D<q(s-1)D<q, the curve ∑jTjxj\sum_jT^jx_j uses only (s−1)D+1(s-1)D+1 nodes. Since qs<U2q^s<U^2, enumeration finds a defining irreducible. For coefficients in an overfield take the compositum.

Suppose a common HH-point set over the anchor field hits the leading coefficient in rr of f(ra+X)f(ra+X) at each good anchor. Testing these points with all anchors and D+1D+1 radial values detects a nonzero restriction. Including descent, the cost is QδQ(D+1)HQ\delta_Q(D+1)H, where δQ=1\delta_Q=1 if ∣E∣≥Q|E|\ge Q and δQ=Q\delta_Q=Q otherwise.

Translation in adjacent differences

Put b0(r)=r−1b_0(r)=r-1 and bp(r)=max⁡{∑de:0≤de<p, ∏(de+1)≤r}b_p(r)=\max\{\sum d_e:0\le d_e<p,\ \prod(d_e+1)\le r\} for p>0p>0, over finite digit vectors. Then bp(r)≤r−1b_p(r)\le r-1 and b2(r)=⌊log⁡2r⌋b_2(r)=\lfloor\log_2r\rfloor.

Lemma 2.5 (Translation and ordered cuts). For an rr-dimensional polynomial representation ρ(t)=∑jDjtj\rho(t)=\sum_jD_jt^j of the additive group, Dj≠0D_j\ne0 implies wt⁡(j)≤bp(r)\operatorname{wt}(j)\le b_p(r). If H≠0H\ne0 and H(Y+t1)=H(Y)H(Y+t\mathbf{1})=H(Y), its ordered cut ranks rir_i give a factorization

H(Y)=B1ρ1(Y1−Y2)B2⋯ρn−1(Yn−1−Yn)Bn(4)H(Y)=B_1\rho_1(Y_1-Y_2)B_2\cdots\rho_{n-1}(Y_{n-1}-Y_n)B_n \tag*{(4)}

with constant ri−1×rir_{i-1}\times r_i matrices BiB_i, r0=rn=1r_0=r_n=1, and rir_i-dimensional representations of degree at most deg⁡H\deg H. The total digit degree is at most ∑i<nbp(ri)\sum_{i<n}b_p(r_i) and the weight at coordinate ii is at most bp(ri−1)+bp(ri)b_p(r_{i-1})+b_p(r_i). For a total-degree or residue-class grading in which HH is homogeneous, the BiB_i are grade-preserving.

Proof. Coefficient comparison gives DaDb=(a+ba)Da+bD_aD_b=\binom{a+b}{a}D_{a+b}. In characteristic zero Dj=D1j/j!D_j=D_1^j/j! with D1D_1 nilpotent. In positive characteristic Ne=DpeN_e=D_{p^e} satisfy Nep=0N_e^p=0 and Dj=∏eNeje/je!D_j=\prod_eN_e^{j_e}/j_e!

by Lucas’s identity. For Djv≠0D_jv \ne0 take the graded-lexicographically largest α\alpha with Nαv≠0N^\alpha v \ne0. Multiplying a relation among NβvN^\beta v, β≤α\beta\le\alpha, by Nα−β0N^{\alpha-\beta_0} for its least index β0\beta_0 leaves only that term. Thus ∏i(αi+1)≤r\prod_i(\alpha_i+1) \le r and wt⁡(j)≤∣α∣≤bp(r)\operatorname{wt}(j) \le|\alpha| \le b_p(r).

Let PiP_i be a basis row of prefix polynomials obtained from suffix coefficients, P0=(1)P_0=(1) and Pn=(H)P_n=(H). A prefix shift equals the opposite suffix shift on HH. Thus Pi(Y+t1)=Pi(Y)ρi(t)P_i(Y+t1)=P_i(Y)\rho_i(t). Writing Pi=Pi−1Ai(Yi)P_i=P_{i-1}A_i(Y_i) gives ρi−1(t)Ai(y+t)=Ai(y)ρi(t)\rho_{i-1}(t)A_i(y+t)=A_i(y)\rho_i(t) and Ai(y)=ρi−1(−y)Biρi(y)A_i(y)=\rho_{i-1}(-y)B_i\rho_i(y) with Bi=Ai(0)B_i=A_i(0). The endpoint representations are trivial, giving (4). Graded bases make each BiB_i grade-preserving and an order-jj row-state transition raises grade by jj. Only adjacent factors contribute to a coordinate, and expanding differences cannot increase digit weight.

The arbitrary-width construction

Proposition 3.1 (Two generators). For n,w,D≥1n,w,D \ge1 one can compute integers K,MK,M satisfying

K≤2O(w2),M≤CwnK(1+log⁡(d+1))2K,K \le2^{O(w^2)}, \qquad M \le C_w n^K(1+\log(d+1))^{2K},

where CwC_w depends only on ww. They give the following hitting sets for Theorem 1.1.

  1. Over a working field of size at least nDM+1nDM+1, a polynomial map in ww scalar parameters gives a hitting set of size at most

(nDM+1)Δw−1(D).(5)(nDM+1)\Delta_{w-1}(D). \tag*{(5)}

In characteristic zero or greater than (w−1)d(w-1)d, one may take M≤CwnKM \le C_w n^K.

  1. Over any working field of size at least nD+1nD+1, a moment curve and KK Shpilka–Volkovich pairs give a hitting set of size at most

(nD+1)ΔK(D)min⁡{(n−1)D+1,n(n−1)+1}K.(6)(nD+1)\Delta_K(D)\min\{(n-1)D+1,n(n-1)+1\}^K. \tag*{(6)}

Moreover, K≤2O(wlog⁡w)K \le2^{O(w\log w)} in characteristic zero or characteristic greater than (w−1)d(w-1)d. In every characteristic the same bound holds when d≤wcwd \le w^{cw} for a fixed cc, with the implicit constant allowed to depend on cc.

For D<∣E∣<nD+1D<|E|<nD+1, Lemma 2.4 descends (6) at cost below nD+1nD+1 per query. This proves the first bound of Theorem 1.1. From (5) the all-field count is (nDM+1)2Δw−1(D)(nDM+1)^2\Delta_{w-1}(D). For finite nD<q<nDM+1nD<q<nDM+1, the required extension degree ss is Ow(1)O_w(1). If s−1≤ns-1\le n, the univariate descent costs Ow(D+1)O_w(D+1) per point. Otherwise the whole nn-variable simplex has at most qn<nDM+1q^n<nDM+1 points. At w=1w=1 take K=0K=0, M=1M=1. For n=1n=1 use D+1D+1 nodes. Given the field nodes, both constructions take polynomial time in n,Dn,D for fixed ww.

For 1≤r<w1\le r<w put

Wr=(wr),hr=(r+2)∏s=r+2w(1+(s−1r−1))−2,W_r=\binom{w}{r}, \qquad h_r=(r+2)\prod_{s=r+2}^{w}\left(1+\binom{s-1}{r-1}\right)-2,
kra=hrbp(Wr2)+2bp(Wr).(7)k_r^a=h_rb_p(W_r^2)+2b_p(W_r). \tag*{(7)}

One may always take kr=krak_r=k_r^a and K=∑r=1w−1krK=\sum_{r=1}^{w-1}k_r. Section 3.3 supplies a second bound, and the smaller choice is valid at each rank. Section 3.4 constructs MM from these integers.

Coefficient spaces over truncated rings

Over a field LL, position ii carries Ri=L[Yi]/(Yiei+1)R_i = L[Y_i]/(Y_i^{e_i+1}), ei≥0e_i \ge0. 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 Coeff⁡(P)\operatorname{Coeff}(P) be the LL-span of the rows of the coefficient matrices of PP, and put Coeff⁡(SP)=∑s∈SCoeff⁡(sP)\operatorname{Coeff}(SP) = \sum_{s \in S} \operatorname{Coeff}(sP) for a constant row space SS. Multiplication gives Coeff⁡(QP)⊆Coeff⁡(P)\operatorname{Coeff}(QP) \subseteq\operatorname{Coeff}(P). For disjoint positions each coefficient is a single product of local coefficients, so Coeff⁡(QP)=Coeff⁡(Coeff⁡(Q)P)\operatorname{Coeff}(QP) = \operatorname{Coeff}(\operatorname{Coeff}(Q)P) and supports add.

A matrix PP has unit rank aa if its constant rank is aa and its (a+1)(a+1)-minors vanish. Given a top left a×aa \times a block UU with invertible constant part and top right block VV, every row (x,y)(x,y) in the row module satisfies y=xU−1Vy = xU^{-1}V. The bordered minors are the entries of the Schur complement times det⁡U\det U. Unit rank zero means P=0P = 0.

Theorem 3.2. Let Ai∈RiW×WA_i \in R_i^{W \times W}, with every nonempty interval of unit rank in P={0=p0<p1<⋯<pm=W}\mathcal{P} = \{0 = p_0 < p_1 < \cdots< p_m = W\}. For any constant row uu, coefficients of support at most

h(P)=∏j=1m(pj−pj−1+1)−2(8)h(\mathcal{P}) = \prod_{j=1}^{m}(p_j-p_{j-1}+1)-2 \tag*{(8)}

span Coeff⁡(uA1⋯An)\operatorname{Coeff}(uA_1 \cdots A_n).

For a=pja = p_j set G(a)+1=∏ℓ>j(pℓ−pℓ−1+1)G(a) + 1 = \prod_{\ell>j}(p_\ell-p_{\ell-1}+1). If b>ab > a in P\mathcal{P}, then

(b−a+1)(G(b)+1)≤G(a)+1(9)(b-a+1)(G(b)+1) \le G(a)+1 \tag*{(9)}

by (1+x)(1+y)≥1+x+y(1+x)(1+y) \ge1+x+y. Suppose Ai(0)=diag⁡(Ia,Qi)A_i(0) = \operatorname{diag}(I_a,Q_i) and let π\pi project onto the first aa coordinates. From a constant space S0S_0, propagate Si=Coeff⁡(Si−1Ai)S_i = \operatorname{Coeff}(S_{i-1}A_i). Choose basis lifts B0B_0 for πS0\pi S_0 and a basis for ker⁡(π∣S0)\ker(\pi|_{S_0}). 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 a=0a = 0 and S0=span⁡(u)S_0 = \operatorname{span}(u), leaving support G(0)−1=h(P)G(0)-1 = h(\mathcal{P}).

Lemma 3.3. Under the interval hypothesis of Theorem 3.2, if πSi=πS0\pi S_i = \pi S_0 at every cut, coefficients of cost at most G(a)G(a) span SnS_n.

Proof. Induct downwards on a∈Pa \in\mathcal{P}. Put Bi=B0A1(0)⋯Ai(0)B_i = B_0A_1(0)\cdots A_i(0), H=πB0H = \pi B_0, and T=rowspan⁡HT = \operatorname{rowspan} H. The rows of BiB_i cost zero and project to HH. This proves the case a=Wa = W. For a<Wa < W, G(a)≥1G(a) \ge1 handles the empty word.

If q=rank⁡(Q1⋯Qn)>0q = \operatorname{rank}(Q_1 \cdots Q_n) > 0, the full word has constant rank b=a+q∈Pb = a+q \in\mathcal{P}. In the passive coordinates choose a complement U0U_0 of the left kernel of the full constant product. Its transported spaces UiU_i map isomorphically under the suffix to UnU_n. Pull back a complement of UnU_n along each suffix to obtain complements of UiU_i respected by the transitions. Transport bases of UiU_i to normalize each constant to diag⁡(Ib,Qi′)\operatorname{diag}(I_b,Q_i'). These cut basis changes preserve interval unit ranks and supports.

The first-bb projections are nested under constant propagation. If the old kernel projects onto β\beta extra dimensions, they start in dimension Tˉ+β\bar{T}+\beta and grow strictly at most q−βq-\beta times. Put δ=1{β>0}\delta= 1_{\{\beta>0\}}. Initially one can choose lifts of cost at most δ\delta and kernel rows of cost at most δ+1\delta+1. On a stable subword, lifts of cost L0L_0 and kernel rows of cost at most L0+1L_0+1 yield spanning rows of cost at most L0+G(b)L_0+G(b) by induction and disjointness of supports. One growth factor adds at most one to this common cost. After t≤q−βt \le q-\beta growth factors, δ≤β\delta\le\beta and (9) give the final cost bound

δ+(t+1)G(b)+t≤(q+1)(G(b)+1)−1≤G(a).(10)\delta+ (t+1)G(b) + t \le(q+1)(G(b)+1)-1 \le G(a). \tag*{(10)}

If Q1⋯Qn=0Q_1\cdots Q_n=0, take cc maximal with Qc⋯Qn=0Q_c\cdots Q_n=0, and write P=Ac⋯AnP=A_c\cdots A_n and B=Bc−1B=B_{c-1}. We claim that Sn=Coeff⁡(BP)S_n=\operatorname{Coeff}(BP). The suffix PP has unit rank aa and Sn=Coeff⁡(Sc−1P)S_n=\operatorname{Coeff}(S_{c-1}P). For s∈Sc−1s\in S_{c-1}, all coefficients of π(sP)\pi(sP) lie in TT. If T=0T=0, the row-module identity gives sP=0sP=0. Otherwise write π(BP)=RH\pi(BP)=RH and π(sP)=λH\pi(sP)=\lambda H. Since R(0)=IR(0)=I, the row-module identity yields sP=λR−1BPsP=\lambda R^{-1}BP, so Coeff⁡(sP)⊆Coeff⁡(BP)\operatorname{Coeff}(sP)\subseteq\operatorname{Coeff}(BP). Conversely every row of BB belongs to Sc−1S_{c-1}.

Restart after cc from Coeff⁡(BAc)\operatorname{Coeff}(BA_c) with lifts BcB_c of cost zero and kernel basis of cost at most one. Every restarted space lies in SiS_i and contains BiB_i, hence projects onto TT. If c<nc<n, the passive suffix product is nonzero by maximality, so the preceding case applies at the same aa. For c=nc=n the restart already spans at cost one. In both cases its final span equals Coeff⁡(BP)=Sn\operatorname{Coeff}(BP)=S_n.

Local minors in the rank descent

For a nonzero polynomial PP, write in⁡0P\operatorname{in}_0 P for its lowest nonzero homogeneous component.

Lemma 3.4. Suppose every interval of A1(Y1)⋯Am(Ym)A_1(Y_1)\cdots A_m(Y_m) has the same rank over L(Y)L(Y) as at zero, in PP. For constant endpoints u,vu,v, if P=u∏iAiv≠0P=u\prod_i A_i v\ne0, each monomial of in⁡0P\operatorname{in}_0 P has support at most h(P)h(P).

Proof. For a chosen YαY^\alpha, reduce modulo Yiαi+1Y_i^{\alpha_i+1} at each position. Only divisors of YαY^\alpha survive, so minimality leaves a nonzero multiple of YαY^\alpha. The intervals have unit rank in the quotient. If the support exceeded h(P)h(P), Theorem 3.2 would force vv to annihilate every coefficient row, including the chosen one.

Lemma 3.5. Let V(T)V(T) be a vector of qq univariate polynomials over F0F_0, let C∈LC\in L be transcendental over F0F_0, and let Λ:Lq→L\Lambda:L^q\to L be linear. If g(Y)=Λ(V(C+Y))g(Y)=\Lambda(V(C+Y)) has first nonzero order aa, then wt⁡(a)≤bp(q)\operatorname{wt}(a)\le b_p(q).

Proof. We use Schmidt’s order-sequence criterion [4 Prop. 1.1]. Put Vj(T)=[Zj]V(T+Z)V_j(T)=[Z^j]V(T+Z). For μ≤a\mu\le a with (aμ)≠0(a_\mu)\ne0 in F0F_0, VμV_\mu lies outside the F0(T)F_0(T)-span of earlier VjV_j. Indeed Λ(Vj(C+U))=[Zj]g(U+Z)\Lambda(V_j(C+U))=[Z^j]g(U+Z) has order at least a−ja-j in UU, with equality at j=μj=\mu. Transcendence makes the coefficients of any rational dependence regular at CC, so earlier vectors cannot produce that order. Thus there are at most qq such indices. There are a+1a+1 in characteristic zero and ∏e(de+1)\prod_e(d_e+1) for a=∑edepea=\sum_e d_ep^e by expanding (1+Z)a=∏e(1+Zpe)de(1+Z)^a=\prod_e(1+Z^{p^e})^{d_e}.

Fix a monomial YαY^\alpha 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 αi\alpha_i. For a width-WW matrix at Ci+YiC_i+Y_i with CiC_i individually transcendental, Lemma 3.5 gives wt⁡(αi)≤bp(W2)\operatorname{wt}(\alpha_i)\le b_p(W^2), or bp(W)b_p(W) 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 w×ww\times w with zero states. Affine invertibility gives the latent scalar total degree at most DD. Truncate each factor at degree dd. Each scalar coefficient was a single product of local coefficients, so deleting exponents above dd preserves the scalar. Use the resulting generic ranks and augment the word by e1e_1 and e1Te_1^{\mathsf T}, leaving just the scalar in entry (1,1)(1,1).

At latent centers Ci=ci+ℓi(G)C_i=c_i+\ell_i(G), all individually transcendental over FF, translation to independent residual variables YiY_i preserves generic ranks. Call an interval preserved if its rank at Y=0Y=0 equals its generic rank. The moment curve γ(t)=(t,t2,…,tn)\gamma(t)=(t,t^2,\ldots,t^n) preserves full-rank intervals since each relevant univariate determinant is nonzero at its center. This holds for any transcendental tt.

Lemma 3.6. Suppose every interval of generic rank greater than rr is preserved. There are rank-rr tests whose preservation suffices for all rank-rr intervals. Each test has one possibly empty chunk of generic rank greater than rr, with at most one factor on either end. The lowest homogeneous component of every nonzero test minor of order rr has digit degree at most krak_{r}^{a} and ordinary degree at most (hr+2)rd(h_{r}+2)rd.

Proof. In a target [l,h][l,h] of rank rr, test its first rank-rr prefix [l,i0][l,i_{0}]. All later prefixes still have rank rr. For i0≤i<hi_{0} \le i < h, let [j,i][j,i] be the shortest rank-rr suffix of [l,i][l,i] and test [j,i+1][j,i+1]. This has rank rr by containment between [j,i][j,i] and [l,h][l,h]. Minimality makes the first test’s prefix before i0i_{0} and each later test’s interior [j+1,i][j+1,i] empty or of rank greater than rr. If [l,i][l,i] is preserved, its specialized row space equals that of [j,i][j,i] by inclusion and the generic rank bound. Appending the next factor and using the test proves preservation of [l,i+1][l,i+1].

By Cauchy–Binet, each minor is an entry of a word of rrth compounds, of width WrW_{r} and local degree at most rdrd. Rank ss becomes (sr)\binom{s}{r} by a change of bases. All chunk intervals are preserved and have compound ranks in the set

{0,(r+1r),(r+2r),…,(wr)}.\left\{0,\binom{r+1}{r},\binom{r+2}{r},\ldots,\binom{w}{r}\right\}.

Its positive gaps after the first are (s−1r−1)\binom{s-1}{r-1}, so (8) gives hrh_{r}. For any monomial of lowest degree, extract the exponents outside the chunk and apply Lemma 3.4. The at most hrh_{r} selected chunk positions contribute at most bp(Wr2)b_{p}(W_{r}^{2}) each, and the boundary factors at most bp(Wr)b_{p}(W_{r}) each. The local degree bound gives the ordinary estimate. □

Substitution Y=AX=(ℓi(X))iY=AX=(\ell_{i}(X))_{i} preserves the nonzero first homogeneous part and its degree. In characteristic p>0p>0, expand each power in base pp 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 ff, so descending to r=1r=1 suffices. In (7), Wr≤2wW_{r}\le2^{w} and 1+(wr−1)≤2w1+\binom{w}{r-1}\le2^{w} give K≤2O(w2)K\le2^{O(w^{2})}.

Factorial width dependence from image cones

Set dw(w)=w2−1d_{w}(w)=w^{2}-1 and dw(s)=2s2(2max⁡s<t≤wdw(t)+1)d_{w}(s)=2s^{2}(2\max_{s<t\le w}d_{w}(t)+1) for s<ws<w. We prove the alternative budget

krc=ηr(br+2),br=max⁡r<s≤wdw(s),ηr={min⁡{rd,Wr2−1},p=0 or p>rd,rd,otherwise.(11)k_{r}^{c}=\eta_{r}(b_{r}+2),\qquad b_{r}=\max_{r<s\le w}d_{w}(s),\qquad\eta_{r}= \begin{cases} \min\{rd,W_{r}^{2}-1\}, & p=0\ \text{or}\ p>rd,\\ rd, & \text{otherwise}. \end{cases} \tag*{(11)}

Take kr=min⁡{kra,krc}k_{r}=\min\{k_{r}^{a},k_{r}^{c}\} in Proposition 3.1. Let C(M)C(M) be the Zariski closure, over an algebraic closure, of scalar multiples of the values of MM. 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 s>0s>0. We prove that dw(s)d_{w}(s) retained blocks suffice. For s=ws=w, 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 IwI_w in dimension w2w^2, allowing at most w2−1w^2-1 strict steps.

First consider rank-ss factors BiB_i with Bi(0)=P=diag⁡(Is,0)B_i(0)=P=\operatorname{diag}(I_s,0). For constant RR of size a×wa \times w put Mi=RB1⋯BiM_i=RB_1\cdots B_i and Vi=C(πMi)V_i=C(\pi M_i), where π\pi takes the first ss columns. These cones are nested since π(HP)=π(H)\pi(HP)=\pi(H). If Vj−1=Vj=Vj+1=VV_{j-1}=V_j=V_{j+1}=V, fix Bj=PB_j=P. At any value of Bj+1B_{j+1} with invertible top left block EE and top right block FF, every output with first columns QQ equals Q[Is,E−1F]Q[I_s,E^{-1}F] by rank ss. The restricted projected cone at that value is VEVE, a closed irreducible subset of VV with the same dimension, so VE=VVE=V. The graph formula then places each original output at this value in the restricted cone. Such values are dense since E(0)=IsE(0)=I_s. The restriction keeps Vj=Vj−1V_j=V_{j-1} and preserves the cone of Mj+1M_{j+1}, hence also every later prefix cone.

Retain strict-growth blocks and the last block of each stable run. When πR≠0\pi R\ne0, the projected cones start at a line in dimension asas, giving at most 2as−12as-1 retained blocks. For B1⋯BmB_1\cdots B_m, keep B1B_1 and pass to its function field. Factor B1=U1[Is,C1]B_1=U_1[I_s,C_1] using its first ss columns. Apply the rectangular bound to R=[Is,C1]R=[I_s,C_1] and multiply by U1U_1. 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 2s22s^2 blocks.

For s<ws<w, greedily cut at shortest rank-ss prefixes CiAeiC_iA_{e_i} and absorb the final tail into the last block. Each nonempty CiC_i and tail, and all their subintervals, have rank greater than ss. Induction and composition reduce each selected block to at most 2max⁡t>sdw(t)+12\max_{t>s}d_w(t)+1 positions. At each internal cut the image of the right constant block complements the kernel of the left, since their product has rank ss. 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 PP. Selecting at most 2s22s^2 such blocks gives the stated bound on dw(s)d_w(s).

Degree of a test. Local compounds have degree at most rdrd. If p=0p=0 or p>rdp>rd, order equals digit weight on this range. Lemma 3.5 bounds the first order of every nonzero linear contraction by Wr2−1W_r^2-1. Thus the local coefficients of degrees at most ηr\eta_r span the full coefficient space by duality.

The chunk cone of each test is preserved on at most brb_r positions. Expand the retained compounds using their spanning coefficients of degree at most ηr\eta_r, and do the same at the at most two boundary factors. Disjoint variables make the resulting products actual coefficients of degree at most ηr(br+2)\eta_r(b_r+2). They span the coefficient space of the test compound by cone equality, giving (10) for ordinary and digit degree.

The recurrence is decreasing in ss, with dw(s)+1≤4s2(dw(s+1)+1)d_w(s)+1\le4s^2(d_w(s+1)+1). Thus br+2≤2⋅4w−r−1(w!/r!)2b_r+2\le2\cdot4^{w-r-1}(w!/r!)^2. Summing gives 2O(wlog⁡w)2^{O(w\log w)}, with a factor at most 4w4^w from rr if p=0p=0 or p>rdp>rd, and at most wdwd otherwise.

Construction of the generators

An exponent digit ded_e on XiX_i represents ded_e copies of (i,pe)(i,p^e) in positive characteristic. In characteristic zero an exponent aa gives aa copies of (i,1)(i,1). Under Xi=∑jZj,iX_i=\sum_j Z_{j,i}, Frobenius or ordinary expansion assigns each copy to a summand. For a monomial of maximum digit degree hh, assign its copies to hh 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 w≥2w\ge2 put R=max⁡1≤r<wmin⁡{(hr+2)rd,krc}R=\max_{1\le r<w}\min\{(h_r+2)rd,k_r^c\}. By Lemma 3.6 and § 3.3, each lowest homogeneous component has ordinary degree at most RR. This bound is Ow(d)O_w(d), and Ow(1)O_w(1) if p=0p = 0 or p>(w−1)dp > (w-1)d. For p>0p > 0 set L=⌊log⁡pR⌋L = \lfloor\log_p R \rfloor and Q={1,p,…,pL}Q = \{1,p,\ldots,p^L\}. For p=0p = 0 set L=0L = 0 and Q={1}Q = \{1\}.

Take the first KK primes mm with m−1>n(2L+1)m - 1 > n(2L + 1), excluding divisors of p∏j=1L(pj−1)p\prod_{j=1}^{L}(p^j - 1) when L>0L > 0. At each prime choose nonzero residues am,ia_{m,i} so that

(i,q)⟼am,iq(modm)(i,q) \longmapsto a_{m,i}q \pmod m

is injective on [n]×Q[n] \times Q. (11)

The exclusions distinguish the powers at each coordinate. The ratios of two powers forbid at most 2L+12L + 1 new residues per previous choice, leaving an admissible residue at each step.

The excluded primes have total logarithm at most B0=(1+L(L+1)/2)log⁡pB_0 = (1+L(L+1)/2)\log p for L>0L > 0, and B0=0B_0 = 0 otherwise. Set x=100(n(2L+1)+K2+B0+1)x = 100(n(2L + 1) + K^2 + B_0 + 1). The estimates 0.82x≤ϑ(x)≤1.2x0.82x \le\vartheta(x) \le1.2x for x≥97x \ge97 give ϑ(4x)−ϑ(x)>2x\vartheta(4x) - \vartheta(x) > 2x for the prime sum ϑ(x)=∑m≤x, m primelog⁡m\vartheta(x) = \sum_{m \le x,\ m\ \mathrm{prime}} \log m [3]. Since B0+Klog⁡(4x)<2xB_0 + K\log(4x) < 2x, the interval (x,4x](x,4x] contains at least KK admissible primes. Their product MM satisfies the stated bound, using L=O(1+log⁡R)L = O(1+\log R) and B0=O((1+log⁡R)2)B_0 = O((1+\log R)^2). For R=Ow(1)R = O_w(1) we have x=Ow(n)x = O_w(n).

Partition the chosen primes into sets JrJ_r of size krk_r and put Nr=∏m∈JrmN_r = \prod_{m\in J_r}m. Define

Vr,i(s)=∑m∈Jrs(M/m)am,i,1≤am,i<m,V_{r,i}(s) = \sum_{m\in J_r} s^{(M/m)a_{m,i}}, \qquad1 \le a_{m,i} < m,
Gi(s,ϵ)=siM+∑r=1w−1ϵrVr,i(s).(12)G_i(s,\epsilon) = s^{iM} + \sum_{r=1}^{w-1} \epsilon_r V_{r,i}(s). \tag*{(12)}

Before stage rr the earlier exponents are divisible by NrN_r, so the coordinates lie in L0=E(ϵ>r,sNr)L_0 = E(\epsilon_{>r},s^{N_r}). The distinct leading powers siMs^{iM} dominate all corrections of degree below MM, keeping each latent center individually transcendental over F\mathbb{F}.

Lemma 3.7. If 0≠H∈L0[X]0 \ne H \in L_0[X] has digit degree at most krk_r and ordinary degree at most RR, then H(Vr(s))≠0H(V_r(s)) \ne0.

Proof. Distinct exponent classes modulo NrN_r are independent over L0L_0 by clearing denominators. Assign the hh copies of a maximum-digit monomial to distinct primes in JrJ_r. Its exponent has nonzero residue at each chosen mm, where only that prime’s summand contributes and M/mM/m is a unit. Thus every assignment in this class uses all hh 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 h=0h = 0.

The translated minors are over L0L_0, and field extension preserves ranks. For each required minor with lowest homogeneous component HH in observed coordinates, the coefficient of ϵrdeg⁡H\epsilon_r^{\deg H} after adding ϵrVr(s)\epsilon_rV_r(s) is H(Vr(s))H(V_r(s)). Earlier ranks persist by setting ϵr=0\epsilon_r = 0. Rank descent gives f(G)≠0f(G) \ne0, with degree at most nDMnDM in ss. For fixed ss, the map is affine in the entire amplitude vector ϵ\epsilon, so Lemma 2.3 uses Δw−1(D)\Delta_{w-1}(D) amplitude nodes. This gives (5), including the moment curve at w=1w = 1.

Interpolation over the smaller field

Take distinct nodes a1,…,an∈Ea_1,\ldots,a_n \in E with degree-(n−1)(n-1) Lagrange polynomials λi\lambda_i, and put v(y)=(λ1(y),…,λn(y))v(y) = (\lambda_1(y),\ldots,\lambda_n(y)). Starting at γ(t)\gamma(t) add ∑j=1krzjrv(yj)\sum_{j=1}^{k_r} z_j^r v(y_j) at stage rr with fresh pairs [14]. For a lowest homogeneous component HH assign the hh copies of a maximum-digit monomial to the first hh pairs, with powers q1,…,qhq_1,\ldots,q_h. For formal vectors vjv_j, the coefficient of ∏j=1hzjqj\prod_{j=1}^{h}z_j^{q_j} is a nonzero linear combination of the products ∏j=1hvj,jqj\prod_{j=1}^{h}v_{j,j}^{q_j} by the copy argument. Higher homogeneous components have larger amplitude degree. Substituting vj=v(yj)v_j = v(y_j) 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 tt and each yjy_j are at most nDnD and (n−1)D(n-1)D, respectively. For fixed t,yt,y the map is affine in the KK amplitudes, giving ΔK(D)\Delta_K(D) 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 rr and at most its generic rank rr. The retained intervals have distinct left endpoints, at most nn including the left boundary. For one nonzero minor per retained interval, its selected coefficient has degree at most n−1n-1 in each occurring yjqjy_j^{q_j}. After partial specialization, at most n−1n-1 values of the next yjy_j can kill a surviving coefficient, since yj↦yjqjy_j \mapsto y_j^{q_j} is the identity or an injective Frobenius power. Thus any grids of size n(n−1)+1n(n-1)+1 let us fix the directions one at a time while preserving all chosen minors. The moment curve keeps later centers transcendental. Interpolate in tt and the amplitudes to obtain (6) with the smaller of the two direction grids.

Degree bounds for one hidden order

In this section f(X)=F(AX)f(X)=F(AX) after absorbing constants. Complete the independent forms to a basis using identity layers. Let rir_i be the cut ranks of FF in its hidden order. For a finite, nonempty exponent set SS, write b(S)b(S) for the largest vanishing order at 11 of a nonzero polynomial supported on SS.

Proposition 4.1 (Exponent sets and cut ranks). Assume ∣E∣>D|E|>D.

  1. The degree-linear bound (1) holds if the exponent sets SiS_i of the top homogeneous component in the latent variables satisfy b(Si)≤wcb(S_i)\le w^c for a fixed cc. This includes characteristic zero and p>dp>d. In positive characteristic, distinct residues modulo pp, or modulo pu≤wcwp^u\le w^{cw}, also suffice.

  1. In positive characteristic put L=⌈log⁡p(D+1)⌉L=\lceil\log_p(D+1)\rceil. For a supplied bound MM on min⁡{D,∑i<nbp(ri)}\min\{D,\sum_{i<n}b_p(r_i)\} the counts are

QδQ(D+1)Hp(n,D,M),(D+1)(nL+1)2O(wlog⁡(w+1))(M<p).(13)Q_{\delta}Q(D+1)H_p(n,D,M),\qquad(D+1)(nL+1)^{2^{O(w\log(w+1))}}\quad(M<p). \tag*{(13)}

In particular the second bound holds whenever p>∑i<nbp(ri)p>\sum_{i<n}b_p(r_i), using M=min⁡{D,p−1,(n−1)bp(w)}M=\min\{D,p-1,(n-1)b_p(w)\}.

Proof. Write PP for the top homogeneous latent component. Scaling all variables and taking the leading term gives PP the same cut-rank upper bounds as FF. In homogeneous bases of the prefix spaces, each transfer entry is a monomial whose exponent is a difference of basis degrees, so ∣Si∣≤w2|S_i|\le w^2.

In characteristic zero, or when the exponents are distinct modulo pp, the determinant of the first m=∣S∣m=|S| binomial rows is the Vandermonde determinant on SS divided by ∏0≤j<mj!\prod_{0\le j<m}j!. Thus b(S)=m−1b(S)=m-1. In positive characteristic group the exponents of SS by residue, writing Sr={(j−r)/p:j∈S, j≡r(modp)}S_r=\{(j-r)/p:j\in S,\ j\equiv r\pmod p\}. With empty classes omitted and b(S)=0b(S)=0 for a singleton, the exact recursion is

b(S)=ph+#{r:b(Sr)=h}−1,h=max⁡rb(Sr).(14)b(S)=ph+\#\{r:b(S_r)=h\}-1,\qquad h=\max_r b(S_r). \tag*{(14)}

At 1+Y1+Y the polynomial is ∑r(1+Y)rPr(1+Yp)\sum_r(1+Y)^rP_r(1+Y^p). The independent polynomials (1+Y)r(1+Y)^r separate the residue classes in each block of pp consecutive orders. Vanishing below phph forces each nonzero PrP_r to attain order hh. In the next block the leading scalars of precisely those classes with b(Sr)=hb(S_r)=h vary freely. The same Vandermonde calculation gives (14). Iteration bounds b(S)b(S) by pu−1p^u-1 for distinct residues modulo pup^u. The substitution T↦aTT\mapsto aT gives the same result at any a≠0a\ne0.

Choose a good anchor aa and put J(X)=in⁡0P(Aa+AX)J(X)=\operatorname{in}_0 P(Aa+AX). To bound an exponent of a monomial of JJ 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 Si\mathcal{S}_i. We may bound all b(Si)b(S_i) by the known value B=w2−1B=w^2-1 if p=0p=0 or p>dp>d, and by B=⌊wcw⌋B=\lfloor w^{c_w}\rfloor under the exponent-set promise. Thus JJ has latent width at most ww, latent individual degree at most BB and total degree at most T=min⁡(D,nB)T=\min(D,nB).

Use (6) with total degree TT and individual degree at most min⁡(B,T)\min(B,T) to find hh with J(h)≠0J(h)\ne0, taking h=0h=0 when T=0T=0. Write e=deg⁡fe=\deg f and j=deg⁡Jj=\deg J. In [re−j]f(ra+th)[r^{e-j}]f(ra+th) the top homogeneous part contributes tjJ(h)t^jJ(h), while each lower homogeneous part contributes a smaller power of tt. Hence T+1T+1 choices for tt and D+1D+1 for rr suffice. Work over a field supplying U=max⁡{Q,nT+1,D+1}U=\max\{Q,nT+1,D+1\} nodes and descend the final query points together by Lemma 2.4. If ∣E∣<U|E|<U, then U=max⁡{Q,nT+1}U=\max\{Q,nT+1\} since ∣E∣>D|E|>D. All factors other than D+1D+1 are therefore bounded by (n+1)2O(cwlog⁡(w+1))(n+1)^{2^{O(c_w\log(w+1))}}.

For the rank-profile bounds, use the entire highest radial coefficient C(X)C(X) of f(ra+X)f(ra+X). 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 MM. For M<pM<p, give each factor ρi\rho_i of (4) its own digit variables Zi,eZ_{i,e}, 0≤e<L0\le e<L. Replacing tpet^{p^e} in the divided-power expansion by Zi,eZ_{i,e} factors the lift into univariate matrices ∑j<pNi,ejZi,ej/j!\sum_{j<p}N_{i,e}^jZ_{i,e}^j/j! of the original width, where Ni,e=[tpe]ρi(t)N_{i,e}=[t^{p^e}]\rho_i(t). Passing to independent difference coordinates preserves the digit bound by affine stability. In the lift each digit variable of an edge has exponent below pp, so distinct monomials encode distinct exponent vectors. The lifted polynomial therefore has ordinary degree at most MM.

Complete the difference forms to a frame li(X)=∑jcijXjl_i(X)=\sum_j c_{ij}X_j with an identity layer. For the prime-field basis vav_a in Lemma 2.3, set Xj=∑avazjaX_j=\sum_a v_az_{ja} with zja∈Fpz_{ja}\in\mathbb{F}_p. The powers of the forms become ∑j,acijpevapezja\sum_{j,a}c_{ij}^{p^e}v_a^{p^e}z_{ja}. To see that these nLnL linear forms are independent, observe that the Moore matrix (vape)e,a(v_a^{p^e})_{e,a} is invertible by the root bound for an additive polynomial of degree at most pL−1p^{L-1} on a span of size pLp^L, and each coefficient matrix (cijpe)(c_{ij}^{p^e}) is invertible. The lift agrees with CC on the prime grid and is nonzero by interpolation on that span. Apply (1) at degree M<pM<p in nLnL variables. The construction can take its nodes in a finite extension of Fp\mathbb{F}_p in a compositum with the coefficient field. Descend its points to Fp\mathbb{F}_p by power-basis interpolation at degree MM. We may cap MM at (n−1)bp(w)(n-1)b_p(w), so these grid and descent thresholds are polynomial in nL,wnL,w (here the individual degree is below pp). Basis summation returns physical directions. The outer D+1D+1 radial nodes and any anchor descent give the second bound. □

The ordinary rank-profile estimate is sharp on radial coefficients. In characteristic zero, ∏i<n(Yi+1−Yi)w−1\prod_{i<n}(Y_{i+1}-Y_i)^{w-1} at 11 attains total degree (n−1)(w−1)(n-1)(w-1) and, for n≥3n\ge3, individual degree 2w−22w-2. Each cut crosses just one factor. In characteristic pp, (Y2−Y1)pe(Y_2-Y_1)^{p^e} already has ordinary vanishing order pep^e at width two.

Digit degree across all variable orders

Write rˉ(H)=2−n∑I⊆[n]r(I)\bar r(H)=2^{-n}\sum_{I\subseteq[n]}r(I) for the mean cut rank and deg⁡pH\deg_p H for the largest total digit weight of a monomial. For an invariant HH, shifting II is equivalent to shifting IcI^c oppositely, so every cut coefficient space is translation-stable.

Lemma 5.1 (Ordinary degree from all cuts). If H≠0H\ne0 is homogeneous of degree mm, invariant under common translation, and p=0p=0 or p>mp>m, then

m≤2(rˉ(H)−1)≤2(1−21−n)(w−1)if all r(I)≤w.(15)m\le2(\bar r(H)-1)\le2(1-2^{1-n})(w-1)\qquad\text{if all }r(I)\le w. \tag*{(15)}

Proof. Lemma 2.5 bounds deg⁡TH(Y+t1I)\deg_T H(Y+t_1I) by r(I)−1r(I)-1. By homogeneity its multiplicity at 1I\mathbf{1}_I is at least m−r(I)+1m-r(I)+1. The multiplicity Schwartz–Zippel bound gives mean multiplicity at most m/2m/2 on {0,1}n\{0,1\}^n [2]. Use r(∅)=r([n])=1r(\varnothing)=r([n])=1 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 TT be a nonzero tensor supported on permutations of [a][a], with all cut ranks at most ww. Suppose each supported permutation has, for every kk-set of positions, a distinct supported permutation agreeing outside that set. If 2≤k≤a2\leq k\leq a, then

2(a−k+1)/2≤rˉ(T)≤w.(16)2^{(a-k+1)/2}\leq\bar r(T)\leq w. \tag*{(16)}

Proof. Build a binary tree of depth a−k+1a-k+1. At each internal node at least kk 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 B⊆[a]B\subseteq[a], let Nv(B)N_v(B) count the distinct preimages π−1(B)\pi^{-1}(B) at leaves below node vv. At a branch the two families are disjoint if exactly one of its two values belongs to BB, an event of probability 1/21/2. Thus NvN_v 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 Elog⁡2Nroot≥(a−k+1)/2\mathbb{E}\log_2N_{\mathrm{root}}\geq(a-k+1)/2.

For fixed II, distinct images π(I)\pi(I) index disjoint nonzero blocks of the cut matrix. Counting pairs (I,π(I))(I,\pi(I)) therefore gives ENroot≤2−a∑IrT(I)=rˉ(T)\mathbb{E}N_{\mathrm{root}}\leq2^{-a}\sum_I r_T(I)=\bar r(T). Jensen’s inequality gives (16).

Lemma 5.3 (Digit degree from layer capacities). Let H≠0H\ne0 be invariant under common translation in characteristic p>0p>0, with every cut rank at most w≥2w\geq2. Put b=bp(w)b=b_p(w) and k=⌊log⁡2w⌋+1k=\lfloor\log_2w\rfloor+1. In a maximum-digit-degree monomial, chosen with lexicographically largest digit counts from the highest layer down, let aa be the maximum matching size between coordinates and occupied layers. If each layer contains at most CC copies, then

deg⁡pH≤amax⁡{b,C},a≤k−1+⌊2log⁡2rˉ(H)⌋.(17)\deg_p H\leq a\max\{b,C\},\qquad a\leq k-1+\lfloor2\log_2\bar r(H)\rfloor. \tag*{(17)}

Put j=⌊log⁡pw⌋j=\lfloor\log_pw\rfloor, c=⌊w/pj⌋c=\lfloor w/p^j\rfloor, and a0=(c+1)pj−1≤2w−1a_0=(c+1)p^j-1\leq2w-1. One may always use

C=min⁡{n,a0−1}min⁡{p−1,b}.(18)C=\min\{n,a_0-1\}\min\{p-1,b\}. \tag*{(18)}

If p>2w−2p>2w-2, one may also use C=2w−3C=2w-3.

Proof. By Lemma 2.5, a singleton shift followed by setting the shifted variable to zero bounds every exponent’s digit weight by bb, and every subset shift has zero coefficient at orders of weight greater than bb. Inclusion–exclusion on shifts by subsets of SS retains precisely the Taylor increments with support SS.

Write YαY^\alpha for the chosen monomial. Packing digits toward p−1p-1 minimizes the product of one plus each digit at fixed digit sum, so b=(p−1)j+c−1b=(p-1)j+c-1 and wt⁡(a0)=b+1\operatorname{wt}(a_0)=b+1. If a power q=peq=p^e occupied a0a_0 coordinates SS, use inclusion–exclusion on SS at order a0qa_0q and extract Yα−q1SY^{\alpha-q1_S}. Lucas’ identity and maximal digit degree force exactly one translated copy per coordinate in SS. The descending-layer tie excludes powers above qq, so their sum forces all copies to equal qq. The unique source YαY^\alpha contributes nontrivially, contradicting the shift-order bound. This proves (18).

For the matching bound, encode each power YipeY_i^{p^e} by Zi,eZ_{i,e} and use the truncated algebra Zi,ep=Tep=0Z_{i,e}^p=T_e^p=0. In the physical shift Yi↦Yi+tY_i\mapsto Y_i+t, Frobenius sends Zi,eZ_{i,e} to Zi,e+tpeZ_{i,e}+t^{p^e}. A carry in tt lowers the combined digit degree. The terms of highest digit degree are therefore invariant under the truncated shifts Zi,e↦Zi,e+TeZ_{i,e} \mapsto Z_{i,e} + T_e. That identity respects the combined layer counts in ZZ and TT. Keep the lexicographically largest layer-count component GG, which contains the encoding of YαY^\alpha. 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 Zi,eZ_{i,e} grouped by ii.

At each cut the coefficient space of GG 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 DδD_\delta for the coefficient operator of TδT^\delta. The shifts compose in the truncated algebra, giving Dδ−βDβ=(δβ)DδD_{\delta-\beta}D_\beta= \binom{\delta}{\beta}D_\delta for β≤δ<p\beta\le\delta< p coordinatewise. If Dδv≠0D_\delta v \ne0 for a homogeneous vv, then the DβvD_\beta v are nonzero of distinct multidegrees. Thus ∏i(1+δi)≤w\prod_i(1+\delta_i) \le w, and the coefficient of every squarefree TT-monomial of degree kk vanishes at every subset shift.

For a maximum matching with coordinates SS, differentiate GG by the Hasse multiorder that leaves one copy of each matched layer in its matched coordinate of YαY^\alpha. Set variables outside SS to zero and retain terms using all coordinates of SS. Exactly one copy of each matched layer remains, giving a nonzero permutation tensor TT. Each cut of TT has rank at most that of any extension of the cut to the omitted coordinates, since all operations are local. Averaging gives rˉ(T)≤rˉ(H)\bar r(T) \le\bar r(H). For a supported assignment and a kk-set J⊆SJ \subseteq S, work before deleting terms missing coordinates. Apply inclusion–exclusion over shifts of subsets of JJ at the squarefree multiorder given by its layers on JJ. The Hasse derivative is coefficient extraction after an independent truncated shift, so it commutes with these shifts. Evaluation outside SS commutes with them as well. Setting the groups in JJ to zero and extracting the assignment off JJ sums exactly the coefficients of permutations agreeing off JJ, since inclusion–exclusion enforces support on all of JJ. The sum vanishes, so a distinct alternative exists. For a≥ka \ge k Lemma 5.2 bounds aa as claimed. For a<ka < k the bound follows from rˉ(H)≥1\bar r(H) \ge1. Kőnig’s theorem gives a vertex cover of size aa, accounting for all digit copies at cost at most bb per coordinate and CC per layer.

For p>2w−2p > 2w - 2, suppose a layer has at least m=2w−2m = 2w - 2 copies. Differentiate GG to retain mm of them. The resulting degree-mm 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 ww. The shift in this layer is now a formal identity since m<pm < p, contradicting (15).

Proof of Theorem 1.2. Choose a good anchor aa by Lemma 2.4. The highest coefficient of f(ra+X)f(ra + X) becomes an invariant HH after rescaling the latent coordinates, and inherits all cut-rank upper bounds by Lemma 2.2. For w=1w = 1 the coefficient is constant by Lemma 2.5, so at each anchor the direction set is {0}\{0\}. If p=0p = 0 or p>Dp > D, apply Lemma 5.1 to the highest homogeneous component. If p>max⁡{d,2w−2}p > \max\{d, 2w - 2\}, all latent exponents of HH lie below pp, so the sharper layer capacity bounds ordinary degree. Thus the ordinary interpolation grid of degree at most 2w−22w - 2 supplies the directions.

For w≥2w \ge2 put u=min⁡{n,L,⌊2log⁡2w⌋+⌈log⁡2w⌉}u = \min\{n, L, \lfloor2\log_2 w\rfloor+ \lceil\log_2 w\rceil\}. By (17) the digit budget is K=min⁡{D,umax⁡(b,C)}K = \min\{D, u_{\max}(b,C)\}, using the maximal available capacity. Here b≤w−1b \le w - 1 and C≤(2w−2)min⁡{p−1,w−1}C \le(2w - 2)\min\{p - 1, w - 1\}, with C≤2w−3C \le2w - 3 when p>2w−2p > 2w - 2.

Affine substitution preserves the digit budget, so Lemmas 2.3 and 2.4 give QδQ(D+1)Hp(n,D,K)Q\delta_Q(D + 1)H_p(n,D,K) queries. A padded list of digit positions gives Hp(n,D,K)≤(nL+1)KH_p(n,D,K) \le(nL + 1)^K, proving (2). The ordinary grid has at most (n+1)2w−2(n + 1)^{2w-2} nodes.

Proposition 5.4 (Singleton and pair cuts at width two). Let H(Y+1)=H(Y)H(Y + 1) = H(Y) as a polynomial identity. Its singleton and pair cut ranks are at most two if and only if

H(Y)=c+∑iAi(Yi),Ai(U+V)=Ai(U)+Ai(V),∑iAi(T)=0.H(Y) = c + \sum_i A_i(Y_i), \qquad A_i(U + V) = A_i(U) + A_i(V), \qquad\sum_i A_i(T) = 0.

Consequently the affine orbit of an input with these cut ranks admits a hitting set of size QδQ(D+1)(1+nL)Q_{\delta_Q}(D+1)(1+nL), with Q,δQQ,\delta_Q as in Lemma 2.4. Take L=1L=1 in characteristic zero and L=⌈log⁡p(D+1)⌉L=\lceil\log_p(D+1)\rceil 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 11, by taking the highest translation coefficient of a nonconstant member. Its other basis vector AiA_i, normalized by Ai(0)=0A_i(0)=0, is additive, since every positive-order coefficient in Ai(Yi+t)A_i(Y_i+t) has smaller YiY_i-degree and is therefore constant. Thus HH is multilinear in the separate variables zi=Ai(Yi)z_i=A_i(Y_i).

If two such variables occur together, some coefficient on their side of the cut is V=azizj+bzi+czj+dV=az_iz_j+bz_i+cz_j+d with a≠0a\ne0. Under simultaneous translation the coefficient of tdeg⁡Ai+deg⁡Ajt^{\deg A_i+\deg A_j} in VV is a nonzero constant. Another positive-order coefficient has a nonzero linear part, since that part of the increment is a(Aj(t)zi+Ai(t)zj)a(A_j(t)z_i+A_i(t)z_j). Together with VV, these coefficients give three independent vectors in the pair space. Hence HH 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 Hp(n,D,1)=1+nLH_p(n,D,1)=1+nL.

The invariant (Y1−Y2)(Y3−Y4)(Y_1-Y_2)(Y_3-Y_4) has singleton ranks two and rank four at {1,3}∣{2,4}\{1,3\}\mid\{2,4\}.

Transfer for dependent forms and multivariate layers

Consider the more general model

f(X)=uA1(L1X+c1)⋯Am(LmX+cm)v(19)f(X)=uA_1(L_1X+c_1)\cdots A_m(L_mX+c_m)v \tag*{(19)}

with matrices of width at most ww. Their arguments can be tuples, with repeated or dependent forms. Let UiU_i be the row span of LiL_i, Pi=∑j≤iUjP_i=\sum_{j\le i}U_j, Si=∑j≥iUjS_i=\sum_{j\ge i}U_j, and P0=Sm+1=0P_0=S_{m+1}=0. On the effective space W=(∑iUi)∗W=(\sum_i U_i)^*, of dimension ρ\rho, put

λi=dim⁡(Pi∩Si+1),γi=dim⁡(Pi∩Si),σ=max⁡{λi,γi−1,0}.(20)\lambda_i=\dim(P_i\cap S_{i+1}),\qquad\gamma_i=\dim(P_i\cap S_i),\qquad\sigma=\max\{\lambda_i,\gamma_i-1,0\}. \tag*{(20)}

The matroid cut connectivity is λi\lambda_i [8]. For univariate layers its maximum equals σ\sigma.

Theorem 6.1 (Transfer to independent forms). If σ≤s≤n\sigma\le s\le n, model (19) has a polynomial-size hitting set over every field EE with ∣E∣>D|E|>D for fixed s,ws,w, independently of the number of layers and their local degrees. In characteristic zero or p>Dp>D, and in any characteristic at w=1w=1, its size is at most

(D+1)min⁡(n,s+1)(n+1)2O(wlog⁡(w+1))(21)(D+1)^{\min(n,s+1)}(n+1)^{2^{O(w\log(w+1))}} \tag*{(21)}

Over ∣E∣≥nD+1|E|\ge nD+1 the reduction preserves width and uses an independent-form set Hw,n,D\mathcal{H}_{w,n,D} from Proposition 3.1, with query count

∣Hw,n,D∣Δs(D)min⁡{(n−1)D+1,(2n+1)s(n−1)+1}.(22)|\mathcal{H}_{w,n,D}|\Delta_s(D)\min\{(n-1)D+1,(2n+1)^s(n-1)+1\}. \tag*{(22)}

For independent blocks of size at most bb, λi=0\lambda_i=0 and σ≤b−1\sigma\le b-1. A single width-one layer contains all degree-DD polynomials in bb variables, which require at least (D+bb)\binom{D+b}{b} evaluations over a common coefficient and working field. This proves sharpness of the degree exponent for fixed bb, and for fixed ss by taking b=min⁡(n,s+1)b=\min(n,s+1). In a univariate word λi≤m−ρ\lambda_i\le m-\rho. If the forms are drawn from a basis, λi\lambda_i counts the basis directions used on both sides.

Proof. Write f=F∘πf=F\circ\pi with π\pi onto WW and deg⁡F=deg⁡f\deg F=\deg f. Set Ai=ann⁡(Si+1)\mathcal{A}_i=\operatorname{ann}(S_{i+1}), Bi=ann⁡(Pi)\mathcal{B}_i=\operatorname{ann}(P_i). The first flag increases and the second decreases. The codimensions of Ai+Bi\mathcal{A}_i+\mathcal{B}_i and Ai−1+Bi\mathcal{A}_{i-1}+\mathcal{B}_i are λi\lambda_i and γi\gamma_i, respectively. The interleaved sequence of pairs changes at most 2ρ2\rho times.

At s=0s=0 put C=0C=0 and Q0=1Q_0=1. For s>0s>0 choose ω∈E∗\omega\in E^* of order at least nn and set C(t,z)=∑j=1szja(ωj−1t)C(t,z)=\sum_{j=1}^{s}z^ja(\omega^{j-1}t) for the curve aa of Lemma 2.4. Testing the first n−1n-1 powers excludes at most (n2)\binom{n}{2} candidates. If needed, enumerate E∗E^*, which is then finite and cyclic. For each flag pair (A,B)(A,B) take h=min⁡(s,codim⁡(A+B))h=\min(s,\operatorname{codim}(A+B)) independent forms on W/(A+B)W/(A+B). Their pullbacks evaluated on a(t)a(t) give independent polynomials of degrees at most n−1n-1. Row reduction gives distinct leading degrees eie_i. The first hh folded directions have a minor of degree at most h(n−1)h(n-1) with leading coefficient proportional to the nonzero Vandermonde in ωei\omega^{e_i} [6 Lemma 12]. The product of the selected minors has degree below Q0=(2n+1)s(n−1)+1Q_0=(2n+1)s(n-1)+1.

Work first over E(t)E(t). Quotient by the span of the projected directions, writing primes for images in W′W'. The minors give Ai′+Bi′=W′\mathcal{A}'_i+\mathcal{B}'_i=W' and codim⁡W′(Ai−1′+Bi′)≤1\operatorname{codim}_{W'}(\mathcal{A}'_{i-1}+\mathcal{B}'_i)\le1. At s=0s=0 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 Ai′\mathcal{A}'_i. Since Ai′+Bi′=W′\mathcal{A}'_i+\mathcal{B}'_i=W', every later group lies in Bi′\mathcal{B}'_i. Group ii has precisely codim⁡(Ai−1′+Bi′)≤1\operatorname{codim}(\mathcal{A}'_{i-1}+\mathcal{B}'_i)\le1 vectors outside Bi′\mathcal{B}'_i. Put the exceptional vector first when it exists. At every cut after a vector of group ii, the prefix thus lifts to Ai\mathcal{A}_i and the suffix to Bi\mathcal{B}_i.

The leading amplitude coefficient of F(Y+πC(t,z))F(Y+\pi C(t,z)) descends to W′W' by Lemma 2.2. With these lifts at a given cut, layers through ii ignore the suffix, and later layers ignore the prefix. The word splits into ww terms across the cut, and taking the leading coefficient preserves its rank bound. By Lemma 2.1 the quotient polynomial has width ww in this basis. Pullback to the observed coordinates uses independent forms, completed by identity layers. Some x∈Hw,n,Dx\in H_{w,n,D} therefore makes f(x+C(t,z))f(x+C(t,z)) nonzero over E(t)E(t), since the construction works with grid nodes in EE and coefficients in E(t)E(t).

The same argument works at any tt where the selected minors survive, so Q0Q_0 nodes suffice. Alternatively, for the xx just obtained the degree in tt is at most (n−1)D(n-1)D, giving the other grid in (22). At a surviving value of tt the restriction is affine in zz before applying ff, and Δs(D)\Delta_s(D) nodes suffice by Lemma 2.3.

For (21) use numerical tt and (1). Apart from D+1D+1, the field thresholds in its proof are polynomial in n,wn,w here since b(Si)≤w2−1b(S_i)\le w^2-1. 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 s+1≥ns+1\ge n. For unrestricted characteristic descend (22) from a field supplying nD+1nD+1 nodes.

Width two in hidden coordinates

Theorem 7.1 (Width two in one order). In two variables, 15(D+1)15(D+1) queries suffice over every field EE with ∣E∣>D|E|>D. In nn variables put Q=n(n−1)+1Q=n(n-1)+1. For ∣E∣>D|E|>D the counts are Q2(D+1)Q^2(D+1) for affine translates of homogeneous inputs and Q2Δ2(D)Q^2\Delta_2(D) for arbitrary inputs, with an extra factor of at most QQ when ∣E∣<Q|E|<Q.

For arbitrary inputs there is also a set of size 1+Q2NM1+Q^2N_M over ∣E∣≥max⁡{Q,NM+1}|E|\ge\max\{Q,N_M+1\}, where NM=M(D−1)+2N_M=M(D-1)+2 and M=O((1+log⁡(D+1))2)M=O((1+\log(D+1))^2) uniformly in the characteristic.

Lemma 7.2 (Factorization at width two). Let H≠0H\ne0 of degree at most DD be invariant under common translation and have width at most two in one order. Suppose HH is homogeneous, or homogeneous modulo MM with the signed powers ±pe\pm p^e (pe≤Dp^e\le D) distinct and nonzero modulo MM. In characteristic zero use ±1\pm1. Up to a scalar over the algebraic closure, HH is a product of at most n−1n-1 powers of linear forms on disjoint intervals of adjacent differences. The powers are pep^e 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 pep^{e} (one in characteristic zero), by bp(2)=1b_{p}(2)=1. 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 nn-variable bounds. Choose QQ anchors on the curve aa of Lemma 2.4. Choose another QQ points on h(s)=(s,…,sn)h(s)=(s,\ldots,s^{n}). These hit every product of powers of at most n−1n-1 nonzero affine linear forms, since the product of their distinct underlying forms restricts to a nonzero polynomial of degree at most Q−1Q-1.

For the homogeneous top part PP of degree ee, the lowest homogeneous component J=in⁡0P(a+X)J=\operatorname{in}_{0}P(a+X) has the factorization of Lemma 7.2 after latent rescaling. Write j=deg⁡Jj=\deg J. For a translate f(X)=P(X−b)f(X)=P(X-b), some hh has J(h−b)≠0J(h-b)\ne0, and [re−j]f(ra+h)=J(h−b)[r^{e-j}]f(ra+h)=J(h-b). For arbitrary ff, some hh has [re−j]f(ra+th)=J(h)≠0[r^{e-j}]f(ra+th)=J(h)\ne0. Interpolation uses D+1D+1 radial nodes in the first case and Δ2(D)\Delta_{2}(D) nodes in the second. Lemma 2.4 handles the anchor threshold.

For the weighted construction take M=3M=3 if p=0p=0 or p>Dp>D. Otherwise set l=⌊log⁡pD⌋l=\lfloor\log_{p}D\rfloor and choose an odd prime M∤p∏j=1l(pj−1)M\nmid p\prod_{j=1}^{l}(p^{j}-1). All signed powers are then distinct nonzero residues. The excluded primes have total logarithm O(1+l2log⁡p)O(1+l^{2}\log p), so the prime estimate in § 3.4 gives M=O((1+log⁡(D+1))2)M=O((1+\log(D+1))^{2}). Some hh hits the factored leading coefficient in (3). Query the origin once. If f(0)=0f(0)=0, a term of degree k≥1k\ge1 contributes tt-degree at most M(e−k)+k≤NM−1M(e-k)+k\le NM-1. Evaluating at NMNM nonzero scales per pair (a,h)(a,h) suffices.

Width two in every order

Corollary 7.3. If the latent width is at most two in every order, (2n+1)(nD+1)(2n+1)(nD+1) queries suffice for ∣E∣≥nD+1|E|\ge nD+1. For ∣E∣≥max⁡{Q,2D+1}|E|\ge\max\{Q,2D+1\} the same construction with quadratic curves gives Q(2n+1)(2D+1)Q(2n+1)(2D+1) queries. Over a common coefficient and working field, sums of univariates give the lower bound nD+1nD+1 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 2×22\times2 matrices. Indeed, if the pair cut had rank one, the tensor would be A12⊗BA_{12}\otimes B with A12A_{12} of rank two. Every remaining mode of BB 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 C\mathbb{C}, the classification also follows from the secant equations of Landsberg and Manivel [9], Theorem 5.1.

Two distinct determinant roots give the form e00⊗U+e11⊗Ve_{00}\otimes U+e_{11}\otimes V. Cuts separating the first pair are block diagonal, so U,VU,V are products. At a double root normalize an invertible member to II. For the singular member NN, the double root of det⁡(N+zI)\det(N+zI) gives tr⁡N=0\operatorname{tr}N=0, so NN is rank-one nilpotent. A change of bases gives e00⊗U+(e01+e10)⊗Ve_{00}\otimes U+(e_{01}+e_{10})\otimes V. The same cuts have block matrix (UVV0)\begin{pmatrix} U&V\\ V&0\end{pmatrix} of rank at least 2rank⁡V2\operatorname{rank}V, so VV is a product. Write n′n' for the number of remaining modes and choose bases with V=e0⊗(n′−2)V=e_{0}^{\otimes(n'-2)}. A minor bordering the two off-diagonal pivots forces any entry of UU with deviations on both sides of the cut to vanish. Thus UU is a sum of products with at most one factor replaced.

Apart from pure products, vanishing on a curve with nonconstant latent coordinates Li(s)L_i(s) therefore gives ∑iRi(Li)=λ\sum_i R_i(L_i)=\lambda or ∏iRi(Li)=λ≠0\prod_i R_i(L_i)=\lambda\ne0 for univariate rational functions, at least one nonconstant. In positive characteristic remove common Frobenius powers until some Ri′≠0R_i' \ne0 (over a perfect field ker⁡(d/dT)=K(Tp)\operatorname{ker}(\mathrm{d}/\mathrm{d}T) = K(T^p)). Differentiation gives

∑iSi(Li)Li′=0,Si=Ri′ or Ri′/Ri,(23)\sum_i S_i(L_i)L_i' = 0,\qquad S_i = R_i' \text{ or } R_i'/R_i, \tag*{(23)}

with some Si≠0S_i \ne0 in every characteristic. Pure products already survive on such a curve.

For n≥2n \ge2 use Γ=(s,s2,…,sn)\Gamma= (s,s^2,\ldots,s^n) and its perturbations Γ+skej\Gamma+ s^k e_j, k=0,1k = 0,1. Write LiL_i for a latent coordinate on Γ\Gamma and ℓi\ell_i for its linear part in the observed variables. Each LiL_i is nonconstant. A degree-one LiL_i requires ℓi\ell_i proportional to X1X_1, so there is at most one. In that case use j≥2j \ge2, on which the other linear forms remain independent.

For qi=deg⁡Li≥2q_i = \deg L_i \ge2 and Si≠0S_i \ne0, let ciTdic_iT^{d_i} be the leading Laurent term of SiS_i and AiA_i the leading coefficient of LiL_i. Put h=max⁡qidih = \max q_i d_i over these indices if any exist. Subtract (23) on Γ\Gamma from the perturbed identity. The coefficient at sh+k−1s^{h+k-1} is

(h+k)∑qidi=hciAidiℓi(ej).(h+k)\sum_{q_i d_i=h} c_i A_i^{d_i}\ell_i(e_j).

Indeed the first variation in δ=skℓi(ej)\delta= s^k\ell_i(e_j) is (Si(Li)δ)′(S_i(L_i)\delta)'. Each remaining term contains at least two perturbation factors δ\delta or δ′\delta'. Its Laurent degree is at most qidi+2k−qi−1<qidi+k−1q_i d_i + 2k - q_i - 1 < q_i d_i + k - 1, since k<qik < q_i. One of k=0,1k = 0,1 makes h+kh+k nonzero, contradicting independence. If only a degree-one term survives, (23) already fails on Γ\Gamma. The 2n+12n+1 curves have degree at most nn, giving the first count. For the second take Γ=s2b\Gamma= s^2b for each of the QQ anchors. At a good bb every qi=2q_i = 2, so the same argument applies with 2D+12D+1 nodes per curve. For n=1n = 1 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 5(2D+1)5(2D+1) queries for ∣E∣≥2D+1|E| \ge2D+1. For D<q=∣E∣≤2DD < q = |E| \le2D, test D+1D+1 points per line. Absorb the translations into the univariates so that T1,T2T_1,T_2 are linear. A rank-two polynomial is A1(T1)B1(T2)+A2(T1)B2(T2)A_1(T_1)B_1(T_2) + A_2(T_1)B_2(T_2) with independent pairs. On a line where both latent coordinates vary, vanishing implies R1(T1)=R2(T2)R_1(T_1) = R_2(T_2) with R1=−A1/A2R_1 = -A_1/A_2, R2=B2/B1R_2 = B_2/B_1 nonconstant of degree at most DD. A product already survives there. At most two directions are bad. If the test vanishes on a good origin line T2=mT1T_2 = mT_1 and a distinct parallel T2=mT1+cT_2 = mT_1 + c, then cc is a nonzero period of R2R_2. The period group has at most DD elements. Indeed the numerator of R2(Z)−R2(T)R_2(Z) - R_2(T) over E‾(T)\overline{E}(T) has degree at most DD in ZZ and has a distinct root T+cT+c for each period.

When dE=[E:Fp]≤4d_E = [E:\mathbb{F}_p] \le4, take three origin lines. For each, add its translates by the dEd_E prime-field basis multiples of a transverse vector. A good line gives periods spanning a group of size q>Dq > D. This uses 3(1+dE)≤153(1+d_E) \le15 lines.

For dE≥5d_E \ge5, choose a generator θ\theta of E/FpE/\mathbb{F}_p and three disjoint quartets of directions of cross-ratio θ\theta. Map (∞,0,1,θ)(\infty,0,1,\theta) to a finite quartet SS and take disjoint translates. Each previous quartet excludes at most ∣S−S∣≤13|S-S| \le13 shifts, and q≥32q \ge32. 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 cc, and some quartet is wholly good. Fix a slope m0m_0 in that quartet. For each of its slopes mm, the origin identities give R2(mT)=R2(m0T)R_2(mT) = R_2(m_0T). The period group is additive and stable under multiplication by the ratios m/m0m/m_0, hence by the Fp\mathbb{F}_p-algebra they generate. This finite subalgebra of EE is a field. The change to latent coordinates and the common scaling preserve the cross-ratio, so the field contains θ\theta and equals EE. The period group contains cEcE, of size q>Dq > D. 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. [1]V. Bhargava and S. Ghosh. Improved hitting set for orbit of ROABPs. Computational Complexity 31 (2022), article 15.
  2. [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. [3]M. Eberl. Concrete bounds for Chebyshev’s prime counting functions. Archive of Formal Proofs (2024).
  4. [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. [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. [6]V. Guruswami and S. Kopparty. Explicit subspace designs. Combinatorica 36 (2016), 161–185.
  7. [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. [8]N. Kashyap. Matroid pathwidth and code trellis complexity. SIAM Journal on Discrete Mathematics 22 (2008), 256–272.arxiv.org/abs/0705.1384
  9. [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. [10]Yilin Liu and GPT-6 Astra Pro. Affine-orbit polynomial identity testing. Algorithm Frontier, source snapshot 77140c2 (2026).
  11. [11]R. D. Neidinger. Multivariate polynomial interpolation in Newton forms. SIAM Review 61 (2019), 361–381.DOI
  12. [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. [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. [14]A. Shpilka and I. Volkovich. On reconstruction and testing of read-once formulas. Theory of Computing 10(18) (2014), 465–514.
  15. [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

Paper details

vlnc:W_cu9twvpt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6 Astra Pro

View statement
Looking for related papers…
Contents