Polynomial bijections between $\mathbb{N}^{m}$ and $\mathbb{N}$ 
*

*Is it known if a polynomial bijection from $\mathbb{N}^{m}$ to $\mathbb{N}$ must necessarily be a polynomial of degree $m$? 

*Are there two polynomial bijections from $\mathbb{N}^{m}$ to $\mathbb{N}$ that are not obtainable from each other by a polynomial change of variables? 

*I seem to remember polynomial bijections between $\mathbb{Z}^{m}$ and $\mathbb{Z}$ are not know to exist: what would be an up-to-date reference on this subject? Or am I remembering wrong?

 A: Though I don't know of any particular reference, your questions can be answered for $m\geq 3$ by using the existence of a such a polynomial on $m=2$.
First, let $f(x,y)={x+y+1 \choose 2}+x$ be the usual polynomial bijection $\mathbb N^2\rightarrow \mathbb N$. We can make two observations: first, this generalizes to all $m$ in a fairly direct way - the reason this works is that we first divide $\mathbb N^2$ into a series of "shells" based on the value of $x+y$ and then we can count how many points are within the shell via the quadratic term and then how many points on the shell precede the given term via the linear term $x$.
If we divide $\mathbb N^3$ by looking first at the function $x+y+z$. Each shell contains ${x+y+z+2 \choose 3}$ integers inside and, when we project a set of the form $x+y+z=k$ down by removing the third coordinate, we are left with the set $x+y \leq k$ in $\mathbb N^2$ and can use the previous polynomial bijection to assign each element of that set an index within the shell. Combining these gives
$$f(x,y,z)={{x+y+z+2}\choose 3} + {{x+y+1}\choose 2} + x$$
as a bijection. One may continue an argument like this inductively to show that, in $\mathbb N^{m}$ the following is a polynomial bijection:
$$f(x_1,\ldots,x_m)=\sum_{i=1}^{m}{{(k-1)+\sum_{k=1}^ix_k}\choose k}$$
for each $m$.
However, we could also, using the first $f$, simply define
$$f(x,y,z)=f(f(x,y),z)$$ 
to get another polynomial bijection $\mathbb N^3\rightarrow\mathbb N$, this one with total degree $4$. For $m\geq 3$, this shows that there are polynomial bijections of multiple degrees for every $m$.
It seems like these questions are open for $m=2$, however, but the Fueter-Polya theorem mentioned in the comments implies that the questions are equivalent for $m=2$.
