Case $k=1$ The set $A_n(1)$ has $4n+5$ elements, the integers from $-2n-2$ to $2n+2$. Case $k=2,3$ The set $A_n(2)$ has $1+2(2\cdot 2^0+2\cdot 2^1+...+2\cdot 2^n)$ elements. Using only zeroes and ones for the $a_i$ we see $B=\{0,1,2,...,2^{n+1}-1\}\subset A_n(2)$, also $B+2^{n+1}-1=\{2^{n+1}-1,2^{n+1},...,2(2^{n+1}-1)\}\subset A_n(2)$ (note that $2(2^{n+1}-1)$ is the largest integer in $A_n(2)$). So we have all integers from $0$ to $2(2^{n+1}-1)$ in $A_n(2)$, along with their negatives and no one else. The same for $A_n(3)$. We have all intergers from $0$ to $3^{n+1}-1$ using standard basis representation and their negatives inversing the sign of the $a_i$. Since $3^{n+1}-1$ is the largest number in $A_n(3)$, there are no more integers in that set, $|A_n(3)|=1+2(3^{n+1}-1)$ Case $k=4$ We need to know every integer is $f(4)$ for some $f\in\mathcal{P}_n$, for some $n$. So we prove a basis theorem with digits $-2,-1,0,1$ and base $4$. With that done, we conclude as the cases $k=2,3$ where $|A_n(k)|=2\max{A_n(k)}+1$ since we can write every integer from $0$ to $1+4+4^2+...+4^n$ using the basis representation, and from $1+4+4^2+...+4^n$ to $2+2\cdot 4+2\cdot 4^2+...+2\cdot 4^n$ we add an adecuate number to $1+4+4^2+...+4^n$. Again, the corresponding negative numbers are in $A_n(4)$ and no one else. Case $k>4$ Note that disctint polynomials in $\mathcal{P}_n$ have disctint values at $k$. If $a_0+a_1k+...+a_nk^n=b_0+b_1k+...+b_nk^n$ then $(a_0-b_0)+(a_1-b_1)k+...+(a_n-b_n)k^n=0$. Taking mod $k$ we conclude $a_0=b_0$, since $-4\le a_0-b_0\le 4$. Cancel a factor $k$ and get $(a_1-b_1)+...+(a_n-b_n)k^{n-1}=0$, mod $k$ yields $a_1=b_1$. Continouing this process we see $a_i=b_i$ for all $i$. Then $|A_n(k)|=|\mathcal{P}_n|=5^{n+1}$.