Polynomial and Hyperplane Avoidance over the Integers with Applications to Integer-Point Counting

Abstract

We study the \emph{Polynomial Avoidance Problem}: given a finite collection $F\subseteq Z[x_1,\dots ,x_n]$ of nonzero polynomials, find a vector $x\in Z^n$ of minimum ${\ell }_p$-norm such that $f(x)\ne 0$ for every $f\in F$. Each polynomial is given sparsely as a list of its nonzero terms. The affine special case is the \emph{Hyperplane Avoidance Problem}. This special case arises in Barvinok-type algorithms for counting integer points in polyhedra, when certain rational generating functions must be evaluated at a removable singularity. Our main results are as follows: 1) Let $D:={\sum }_{f\in F}\text{deg}f$. Every instance admits a feasible vector $x$ satisfying \[ \|x\|_1 \leq \min\left\{D,\frac{D+n}{2}\right\}. \] This bound is tight. Such a vector can be found by a deterministic algorithm whose bit complexity is polynomial in $D$ and the sparse encoding length of the input. Our proof uses a new algorithmic variant of the \emph{Combinatorial Nullstellensatz}; 2) In the affine case, with $m$ input polynomials, such a vector can be constructed by a fast deterministic polynomial-time algorithm using $O(nm)$ arithmetic operations. For the homogeneous case, Barvinok's original approach provides only the weaker guarantee $\Vert x{\Vert }_1=O((nm{)}^{n-1})$; 3) The problem is NP-hard for every $p\in R_{\ge 1}\cup \{\infty \}$, even for homogeneous linear forms; 4) As an application, we improve the complexity bound for counting integer points in general rational polytopes. We also improve the bound for polyhedra of bounded codimension; this includes the counting version of the \emph{Unbounded Subset-Sum} problem as a special case.

arXiv commentThis version is an improved version of the previous variant of the work, in which the case of a system consisting of polynomials is also considered. The overview part of the work has also been substantially expanded