Sparsity is a basis-dependent notion: a polynomial with many monomials may become sparse after an invertible affine change of variables. We study polynomial identity testing (PIT) and lower bounds for sparse polynomials under arbitrary invertible affine changes of coordinates, that is, for affine orbits of sparse polynomials. For PIT, the goal is a small explicit set that is not contained in the zero set of any nonzero polynomial that is sparse in some affine coordinate system. For lower bounds, the goal is an explicit polynomial that has many monomials in every affine coordinate system.
Over fields of characteristic zero, we give an explicit hitting set of size $O(n^3 s^2 d)$ for affine orbits of $n$-variate, degree-$d$, $s$-sparse polynomials, improving the quasipolynomial bound $(nd)^{O(\log s)}$ of Medini and Shpilka [CCC 2021]. Over $\mathbb{R}$, we give a hitting set of size $O(n^4 s^5)$, consisting of integer points with $poly(n,s)$ bits, that works for every degree. We also give explicit polynomials of degree $d$ that have at least ${n-1+d/3 \choose n-1}$ monomials in every affine coordinate system. This bound grows with the degree even when $n$ is fixed, and gives $n^n$ at degree $3n^2$. The previous best lower bound, $2^{\Omega(n)}$, comes from lower bounds of Nisan and Wigderson [Comput. Complexity 1997] and of Kayal, Saha, and Tavenas [ICALP 2016] for homogeneous depth-three circuits, and does not grow with the degree.
Our hitting set combines one structural lemma with the recent hitting sets of Bhardwaj and Saptharishi for polynomials with small partial derivative spaces, and our lower bound follows from the lemma directly. The lemma says that if $f$ is $s$-sparse in some affine coordinate system, then after a shift by a generic point $(\beta, \beta^2, \ldots, \beta^n)$, the lowest-degree homogeneous component of $f$ has partial derivative space of dimension at most $s$.
Just as sparse PIT is a building block for PIT of many circuit classes, sparse-orbit PIT is a building block for PIT of many orbit classes. As direct applications, we obtain polynomial-size hitting sets for affine orbits of constant-depth, constant-occur formulas and of circuits over sparse polynomials of bounded transcendence degree, improving the quasipolynomial bounds of Saha and Thankey [ToCT 2024].
