\documentclass[11pt,a4paper]{article} \usepackage[T1]{fontenc} \usepackage{lmodern,amsmath,amssymb,amsthm} \usepackage[a4paper,margin=28mm]{geometry} \usepackage{microtype,xcolor} \usepackage[unicode,colorlinks=true,linkcolor=blue!55!black,citecolor=blue!55!black,urlcolor=blue!55!black]{hyperref} \hypersetup{pdftitle={Black-box identity testing for affine orbits of read-once oblivious algebraic branching programs},pdfauthor={Yilin Liu},pdfkeywords={polynomial identity testing, algebraic branching programs, hitting sets, affine orbits}} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newcommand{\F}{\mathbb F} \newcommand{\wt}{\operatorname{wt}} \newcommand{\Coeff}{\operatorname{Coeff}} \newcommand{\Span}{\operatorname{span}} \newcommand{\rank}{\operatorname{rank}} \newcommand{\rowspan}{\operatorname{rowspan}} \setlength{\emergencystretch}{1em} \clubpenalty=10000 \widowpenalty=10000 \displaywidowpenalty=10000 \allowdisplaybreaks[1] \title{Black-box identity testing for affine orbits of read-once oblivious algebraic branching programs} \author{Yilin Liu} \date{19 November 2026} \begin{document} \makeatletter \begin{center} {\LARGE\bfseries\parbox{.99\linewidth}{\centering\@title}\par} \vspace{.8em} {\large\@author\par} \vspace{.4em} {\small\@date\par} \end{center} \makeatother \begin{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. \end{abstract} \section{Introduction}\label{sec:main} We have black-box access over a field $E\supseteq\F$ to $f(X)=F(AX+c)$, where $A\in\mathrm{GL}_n(\F)$ and $c\in\F^n$ are unknown. In the hidden coordinates the polynomial is computed by a width-$w$ read-once oblivious algebraic branching program (ROABP), \[ F(Y)=uA_1(Y_{\pi(1)})\cdots A_n(Y_{\pi(n)})v, \] with univariate polynomial matrices of width at most $w$, a constant row $u$, a constant column $v$, and an unknown variable order $\pi$. A hitting set is a finite subset of $E^n$ on which every nonzero polynomial in the class has a nonzero value. Write $D\ge1$ for a total-degree bound and $p=\operatorname{char}\F$. We may use any upper bound $1\le d\le D$ on the individual degree of $F$, including $d=D$. We count field operations and oracle queries, given distinct field elements for the evaluation grids. \begin{theorem}[One unknown order, arbitrary width]\label{thm:general} For $n,w,D\ge1$ and $|E|>D$, the affine orbit of width-$w$ ROABPs in one unknown order admits an explicit hitting set of size \[ (nD+1)^{2^{O(w^2)}}. \] In characteristic zero, or in characteristic $p>d$, there is a hitting set of size \begin{equation}\label{eq:linear} (D+1)(n+1)^{2^{O(w\log(w+1))}}. \end{equation} \end{theorem} Section~\ref{sec:base} proves the arbitrary-characteristic bound by two generators. The first uses $w$ scalar parameters. The second uses a moment curve and $2^{O(w^2)}$ interpolation pairs. Section~\ref{sec:frobenius} derives \eqref{eq:linear} from the exponent sets of the top homogeneous component. \begin{theorem}[Every variable order]\label{cor:anyorder} Suppose $F$ admits width at most $w$ in every variable order, with matrices depending on the order. For $|E|>D$, a hitting set of size $(D+1)(n+1)^{O(w)}$ suffices if $p=0$, $p>D$, or $p>\max\{d,2w-2\}$. In positive characteristic let $L=\lceil\log_p(D+1)\rceil$. With no restriction on $d$ the size is \begin{equation}\label{eq:graded-anyorder} (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} \end{equation} \end{theorem} 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 (Section~\ref{sec:anyorder}). At width two, the singleton and pair cuts alone determine the form of this coefficient. Theorem~\ref{thm:transfer} extends the construction to multivariate layers through the intersections of prefix and suffix spans. For independent blocks of at most $b$ variables the degree exponent is $b$ in characteristic zero or above $D$, sharp already at width one. In two variables, $15(D+1)$ queries suffice at width two whenever $|E|>D$ (Theorem~\ref{thm:widthtwo-oneorder}). \paragraph{Related work.} Saha and Thankey~\cite{ST} studied affine orbits of circuit classes including multilinear ROABPs. In characteristic zero or greater than $d$, Bhargava and Ghosh~\cite{BG} obtained bounds of $(ndw)^{O(w^2\log n\min\{w^2,d\log w\})}$ for one unknown order and $(ndw)^{O(\min\{w^2,d\log w\})}$ for every order. For a single unknown order, Theorem~\ref{thm:general} gives a polynomial bound at each fixed width in every characteristic. Theorem~\ref{cor:anyorder} separates the dependence on total degree from the dimension. For ROABPs in the original coordinates see Gurjar, Korwar and Saxena~\cite{GKS}, Singh and Singh~\cite{SS}, and Shpilka~\cite{AS}. The rank descent and image-cone arguments build on the source manuscripts~\cite{AF}. \section{Cut ranks, leading coefficients, and interpolation}\label{sec:tools} \begin{lemma}[Cut ranks]\label{lem:flattening} Let $r(I)$ denote the rank of the coefficient matrix with rows indexed by monomials on $I$ and columns by monomials on $I^c$. A polynomial admits width at most $w$ in an order precisely when $r(I)\le w$ at every prefix~\cite[Lemma~8.2]{HVM}. A cut of a width-$w$ product gives $w$ 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. \end{lemma} \begin{lemma}[Leading coefficients]\label{lem:leading}\label{lem:weighted-leading} The lexicographically leading amplitude coefficient of $F(Y+\sum_j z_jv_j)$ is invariant along $\Span\{v_j\}$ and inherits all cut-rank bounds of the translated polynomial in the coordinates under consideration. For a direction $a$ and an integer $M\ge1$, the lowest nonzero coefficient $J(X)$ in \begin{equation}\label{eq:weighted-leading} R(t,X)=t^{Me}f\bigl((a+tX)/t^M\bigr),\qquad e=\deg f, \end{equation} is invariant along $a$, inherits the latent cut-rank bounds and has all degrees in one residue class modulo $M$. Here $\deg_t R\le MD$. For $M=1$, $J$ is the leading coefficient in $r$ of $f(ra+X)$. \end{lemma} \begin{proof} Translating the amplitudes preserves their leading coefficient, which therefore descends to the quotient by the directions. Weights that are successive powers of $D+1$ realize lexicographic order on the amplitude monomials. Lemma~\ref{lem:flattening} then gives the cut-rank bounds. For each nonzero homogeneous part $P_k$ of $f$, write $J_k=\operatorname{in}_0 P_k(a+X)$ for its lowest nonzero homogeneous component and $j_k=\deg J_k$. Then $J_k$ is the highest radial coefficient of $P_k(ra+X)$, hence invariant along $a$. In \eqref{eq:weighted-leading} its order is $M(e-k)+j_k$. At the minimum the contributing $J_k$ have distinct degrees in one residue class, so their sum is nonzero. The substitution acts separately on latent variables over $E(t)$, and division by the lowest power followed by specialization gives the rank bound. The terms from $P_k$ have $t$-degree at most $M(e-k)+k\le MD$. \end{proof} \begin{samepage} \begin{lemma}[Interpolation in bounded digit degree]\label{lem:digit-grid} Let $\wt(j)$ be the base-$p$ digit sum, with $\wt(j)=j$ in characteristic zero. Write $H_p(n,D,K)$ for the number of monomials $X^\alpha$ with $|\alpha|\le D$ and $\sum_i\wt(\alpha_i)\le K$. Their span is affine-stable and, over $|E|>D$, admits an explicit interpolation set of this size. For $p>0$, $H_p(n,D,K)\le\binom{nL+K}{K}$ with $L=\lceil\log_p(D+1)\rceil$. For ordinary total degree at most $D$ in $m$ variables the interpolation set has size $\Delta_m(D)=\binom{D+m}{m}$, including $\Delta_0(D)=1$. \end{lemma} \end{samepage} \begin{proof} In positive characteristic choose $L$ prime-field independent $v_e$ from $D+1$ nodes (the smaller spans have size at most $D$). Order the nodes $x_j=\sum_e j_ev_e$, $0\le j\le D$, by their digit labels. The first $j$ split into $\wt(j)$ cosets of initial basis spans, by aligned base-$p$ blocks. The vanishing polynomial $S$ of a span is additive, since adjoining $v$ replaces $S$ by $S^p-S(v)^{p-1}S$. Hence the Newton polynomial $N_j(T)=\prod_{h