I want to find a description for the ideal $Z \subseteq k[\underline{x}]$ where $Z = \{f \in k[\underline{x}] | f(\mathbb{A}^n_k) = \{ 0 \}\}$.
I can show that for an infinite field $k$, the polynomials in $k[\underline{x}]$ inject into the set of functions from $\mathbb{A}^n_k$ to $k$, but I'm struggling to find all polynomials which are zero functions when $k$ is finite.
For $\mathbb{A}^1_k$, we have that all such polynomials lie in the ideal $(x^q - x)$ since being zero at a point gives a linear factor at that point and $x^q - x$ is the product of these linear factors where $q = |k|$. Now I think $Z = (x_1^q - x_1, ... , x_n^q - x_n)$ since I haven't found any polynomials not of this form (even with an extensive computer search!), but I'm having trouble proving it. Any reference requests are greatly appreciated!
Yes, the ideal $I=(x_1^q-x_1,\cdots,x_n^q-x_n)$ is exactly the collection of polynomials which vanish on $\Bbb F_q^n$.
Lemma. If $p(x_1,\cdots,x_n)\in\Bbb F_q[x_1,\cdots,x_n]$ is a nonzero polynomial which satisfies $\deg_{x_i} p < q$ for all $i$, then there exists an $n$-tuple $(\alpha_1,\cdots,\alpha_n)\in\Bbb F_q^n$ such that $p(\alpha_1,\cdots,\alpha_n)\neq 0$.
Proof. We proceed by induction. When $n=1$, the claim follows from the fact that a degree-$d$ polynomial in one variable can have at most $d$ roots. When $n>1$, there must be some $i$ such that $\deg_{x_i} p >0$. WLOG suppose $i=1$ and write $p=\sum_{j=0}^d p_j(x_2,\cdots,x_n)x_1^j$. By the inductive hypothesis, there is some $(\alpha_2,\cdots,\alpha_n)\in \Bbb F_q^{n-1}$ so that $p_j(\alpha_2,\cdots,\alpha_n)\neq 0$; then as $p(x_1,\alpha_2,\cdots,\alpha_n)$ is a nonzero polynomial in $x_1$ of degree $d<q$, there must be some choice of $\alpha_1$ so that $p(\alpha_1,\alpha_2,\cdots,\alpha_n)\neq 0$. $\blacksquare$
To prove the original claim, observe that any polynomial $a\in\Bbb F_q[x_1,\cdots,x_n]$ can be written as $a=b+c$ for $b\in (x_1^q-x_1,\cdots,x_n^q-x_n)$ and $c$ of degree less than $q$ in each $x_i$. If $c\neq 0$, then the above lemma shows that $c$ and hence $a$ are not the zero function from $\Bbb F_q^n\to\Bbb F_q$. Therefore the polynomials which are zero on all of $\Bbb F_q^n$ are exactly those you've found.