On the smallest integer vector at which a multivariable polynomial does not vanish

We prove that for any polynomial $P$ of degree $d$ in $\C[x_1,\dots,x_n]$ there exists a vector $(u_1,\dots,u_n) \in \Z^n$ such that $P(u_1,\dots,u_n) \ne 0$ and $\sum_{i=1}^n |u_i| \leq \min\{d, \lfloor (d+n)/2 \rfloor\}$. We also show that this bound is best possible. Similarly, for any $P \in \C[x_1,\dots,x_n]$ of degree $d$ and any real number $p \geq \log 3/\log 2$ there is a vector $(u_1,\dots,u_n) \in \Z^n$ such that $P(u_1,\dots,u_n) \ne 0$ and $\sum_{i=1}^n |u_i|^p \leq \max\{1+\lfloor d/2 \rfloor^p, \lfloor (d+1)/2 \rfloor^p\}$. The latter bound is also best possible for every $n \geq 2$.