This is a follow-up question, to a question I asked earlier.

See Algebraic curve intersecting square-grid.

Consider $n^d$ unit hypercubes in $d$-dimensional Euclidean space tightly packed in the canonical way.

Let $f \in \mathbb{Z}^d$ be a vector, then we define the hypercube $c_f$ as $$ c_f = \{ f + x \in \mathbb{R}^d : 0\leq x_i \leq 1, \forall i =1,\ldots,d\} $$ We consider all hypercubes with $1\leq f_i\leq n$.

Let us now consider a polynomial $p$ in $d$ variables with maximum degree $\Delta$.

How many hypercubes can $p$ intersect, in terms of $\Delta$, $n$ and $d$?

(We say $p$ intersects a set $S$ if $\exists \ x \in S : p(x) = 0$.)


Let us start with the case $d = 1$. In this case, we have a univariate polynomial $p(x)$ and we ask how many unit intervals it can hit at most. The answer $\Delta$ is well known.

Now we tackle the case $d = 2$, for pedagogical purposes. Let us assume that $c = \{ x\in \mathbb{R}^2: p(x) = 0\}$ has only one connected component. (Here is a gap in the argument, that we don't want to fill for the moment.) Note that $c$ is a one-dimensional object and we can think of $c$ as going in and out of a component. So whenever $c$ does this, we visited one more component. In two dimensions, our cubes are bounded by $n+1$ horizontal and vertical lines. It is sufficient to count the number of times such a line is hit. Now the set $c \cap \ell$, for a line $\ell$ can be described by a univariate polynomial of max degree $\Delta$. Thus by the case $d=1$, each line is intersected at most $\Delta$ times. This gives an upper bound of $(2n+2)(\Delta) \leq 3n\Delta$. (We assume $n\geq 2$.) See also the answer of Dmitri Panov (Algebraic curve intersecting square-grid)

Now let us go to the general induction step $(d-1) \rightarrow d$. Again, let us assume that $c = \{ x\in \mathbb{R}^2: p(x) = 0\}$ has only one connected component. All the hypercubes are bounded by $dn+d$ hyperplanes. Every intersection of $c$ to a hypercube is witnessed by an intersection of $c$ to at least one of the hyperplanes. Now consider one of the hyperplanes $H$ and consider the induced grid arrangement $A$ on $H$. By induction, at most $(d-1)!(n+1)^{d-2}\Delta$ of the cells of $A$ are visited by $c$. Thus in total among all the hyperplanes at most $(dn+d) \cdot (d-1)!(n+1)^{d-2}\Delta \leq d!(n+1)^{d-1}\Delta$ of the induced cells are touched by $c$. (We assume $n\geq 2$.) Thus also at most $3n^{d-1}\Delta$ full dimensional cubes are visited by $c$.

Additionally, if $c$ has more components, some of the components are completely contained in some of the hypercubes. But the number of components is bounded by a function of $\Delta$ and $d$ and independent of $n$.

So the answer will be $d!(n+1)^{d-1}\Delta + f(d,\Delta)$.

Remark: We have to take care of the $f(d,\Delta)$ also in the induction step. :(. This proof is not complete yet. It would be nice to absorb it somehow in the first term.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.