# Intersections of algebraic surfaces with hypercubes of a $d$-dimensional grid

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

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.