First we can remove the condition that $P(n)=0$ (it's superfluous). Let $d = 2000$. Clearly $0,1$-independent polynomials of degree $d$ exist, so suppose $n\ne 0,1$ and an $n$-independent $P$of degree $d$ exists, with coefficients $a_0<a_1<\cdots<a_d$. Case 1: $|n| \ge 2$. Call a permutation $\pi$ good if $\sum_{k=0}^{d} a_{\pi(k)} n^k = 0$, and bad otherwise. By rational approximation, we can find pairwise distinct integers $b_0<b_1<\cdots<b_d$ with $\sum b_{\pi(k)} n^k = 0$ if and only if $\sum a_{\pi(k)} n^k = 0$. Indeed, by $d+1$-dimensional Kronecker's theorem, we can find, for any $\epsilon>0$, arbitrarily large positive integers $N$ with $\| N a_i \| \le \epsilon$ for all $i$. Then we can take $b_i = [Na_i]$ (where $[x] = x - \|x\|$) if $\epsilon |1+n+\cdots+n^d| < 1$, $N>\frac{2}{\min|a_i - a_j|\setminus\{0\}}$, and $N>\frac{1}{\min|\sum a_{\pi(k)} n^k| \setminus\{0\}}$. (The second guarantees the $b_i$ are pairwise distinct, while the first and third guarantee $\sum b_{\pi(k)} n^k$, which is an integer, vanishes only when $\pi$ is good---this follows from the triangle inequality.) Lemma. Suppose there are $r_i$ indices $j$ with $b_j \equiv i \pmod{n}$. Then $\sum_{k=0}^{d} b_{\pi(k)} n^k = C$ has at most $r_0!\cdots r_{n-1}!$ solutions $\pi$. Furthermore, if equality holds, then for each $j$ with $b_j \equiv C \pmod{n}$, $\sum_{k=0}^{d-1} b_{\sigma(k)} n^k = \frac{C-b_j}{n}$ must have exactly $r_0!\cdots (r_C-1)! \cdots r_{n-1}!$ solutions $\sigma$ (with $\sigma$ restricted to the indices $k\ne j$); in particular, there must be at least one index $k\ne j$ with $b_k \equiv \frac{C-b_j}{n} \pmod{n}$. Proof. Induct on $r_0 + \cdots + r_{n-1} = d+1 \ge 1$ using the requirement $a_{\pi(0)} \equiv C \pmod{n}$. $\blacksquare$ WLOG assume $\gcd(b_0,b_1,\ldots,b_d) = 1$, so $0<r_0<d+1$, and there exists $1\le t\le n-1$ with $r_t>0$; WLOG $b_d \equiv t \pmod{n}$. Now focus on the $\pi$ with $\pi(0) = d$: they must all be bad. On the other hand, any good $\pi$ "saves" (via a single transposition) exactly one bad $\pi'$ with $\pi'(0) = d$. But each bad $\pi'$ (with $\pi'(0) = d$) is saved by at least one good $\pi$, so we must have at least $d!$ good $\pi$. Yet by the lemma and the fact that $a! b! < (a+1)! (b-1)!$ whenever $a\ge b\ge 1$, we have at most $d! 1!$ good $\pi$, with equality only when $\{r_0,r_t\} = \{1,d\}$. Now we will invoke the equality clause of the lemma to derive a contradiction. If $r_0 = 1$, then WLOG $b_0 \equiv 0\pmod{n}$ and $b_1,\ldots,b_d \equiv t\pmod{n}$. It follows that $\sum_{k=0}^{d-1} b_{\pi(k)} n^k = \frac{-b_0}{n}$ for all $\pi$, from which we easily obtain $b_1 = \cdots = b_d$ (e.g. consider the effect of a transposition), contradiction. Otherwise, $r_t = 1$, so $b_0,\ldots,b_{d-1}\equiv0\pmod{n}$. Take a good $\pi$ and suppose $\pi(M) = d$. If $M\le d-2$, let $\{u,v\} = \{0,1,\ldots,d\}\setminus\{\pi(0),\ldots,\pi(d-2)\}$. Then by repeated application of the equality clause, $b_{\sigma(d-1)}+nb_{\sigma(d)} = -\frac{\sum_{k=0}^{d-2} b_{\pi(k)} n^k}{n^{d-1}}$ has $2!$ solutions $\sigma$ (where $\{\sigma(d-1),\sigma(d)\} = \{u,v\}$), since $b_u,b_v \equiv 0\pmod{n}$; hence $b_u = b_v$, which is impossible. Thus $M\ge d-1$ for any $\pi$, whence the equality clause gives us $n^k \mid b_0,\ldots,b_{d-1}$ for $k=1,2,\ldots,d-2$ (just induct on $k$). Now fix some $\pi$; the equality clause tells us there exists $\pi' \ne \pi$ with $\pi'(i) = \pi(i)$ for $i=0,1,\ldots,d-3$. We cannot have $\pi'(d-2) = d$ (by the previous paragraph) or $\pi'(M) = \pi(M) = d$ ($\pi',\pi$ can't agree in any more places), so WLOG $M = d-1\implies \pi(d-1) = d$ and $\pi'(d) = d$. Thus \begin{align*} 0 &= \sum (b_{\pi(k)} - b_{\pi'(k)}) n^k \\ &= (b_{\pi(d-2)} - b_{\pi'(d-2)})n^{d-2} + (b_d - b_{\pi'(d-1)})n^{d-1} + (b_{\pi(d)} - b_d)n^d, \end{align*}which is impossible mod $n^d$ (we have $n^2\mid n^{d-2} \mid b_{\pi(d-2)},b_{\pi'(d-2)},b_{\pi'(d-1)}$, but $n\nmid b_d$). Comment: The official solution uses $|n|^d > |n|^{d-1}+\cdots+1$ instead to show $a_d n^d + \cdots \ne a_0 n^d + \cdots$, whence one finds an inductive bound of $|\{\sum a_{\pi(k)} n^k\}| \ge 2^{d-1}$ (to finish, we have $\{\sum a_{\pi(k)} n^k\} \subseteq \{(a_{\pi(j)} - a_{\pi(i)})(n^j - n^i)\}$, and the latter is too small). However, only the above method generalizes if we replace the "polynomial basis" $(n^0,\ldots,n^d)$ with $(n_0,\ldots,n_d)$, where for each $k$, $\frac{n_k}{n^k}$ is an integer relatively prime to $n$. Case 2: $n=-1$. Then for any indices $i_1<i_2<\cdots<i_{1000}$, there exist indices $j,k$ with \[ a_{i_1}+\cdots+a_{i_{1000}} = C + (a_{i_j} - a_k), \]where $2C = a_0+\cdots+a_{2000}$. This already tells us that \[ (a_{1001}+\cdots+a_{2000}) - (a_0+\cdots+a_{999}) \le 2(a_{2000}-a_0), \]which although "unlikely," still needs a small improvement. Now note that $\{a_0+a_1+a_{i_3}+\cdots+a_{i_{1000}}\}_{1< i_3<\cdots<i_{1000}<1999}$ has at least $1+998\cdot999$ elements, one of which must, by pigeonhole, take the form $C+a_u - a_v$ for $u,v\ne 0,1,1999,2000$. But for this choice of $(i_j)$, we then have \begin{align*} (a_{i_3}+\cdots+a_{i_{1000}}+a_{1999}+a_{2000}) - (a_0+a_1+a_{i_3}+\cdots+a_{i_{1000}}) &\le (C+a_{2000}-a_0) - (C+a_u-a_v) \\ &\le (a_{2000}-a_0) + (a_{1998} - a_2), \end{align*}which is absurd.