Polynomial bijections $\mathbb{Z}^2\to\mathbb{Z}^2$ are almost linear Let $M$ be the monoid of bijections $\phi:\mathbb{Z}^2\to\mathbb{Z}^2$ such that $\phi(x, y)=(P(x, y), Q(x, y))$ for some polynomials $P, Q\in \mathbb{Z}[x, y]$.
Does $\mathrm{GL}_2(\mathbb{Z})\subset M$ together with the maps of the form $(x, y)\to (x+R(y), y)$ where $R\in \mathbb{Z}[y]$ generate $M$?
That would imply that $M$ is secretly a group.
 A: Elements of $M$ have inverses which are integer-valued polynomial maps, so the version with integer-valued polynomial maps forms a group.
In fact, we only need to assume surjectivity to guarantee the existence of a polynomial inverse, so the monoid of surjective integer-valued polynomials from the plane to the plane is also a group.
I don't know if this implies your desired classification result.

$(P,Q)$ defines a map $\mathbb A^2_{\mathbb Q} \to \mathbb A^2_{\mathbb Q}$, which since the source and target have the same dimension must be generically finite. Because the source is irreducible, Hiblert's irreducibility theorem implies that the fibers over most integral points are irreducible, which if the degree is $>1$ contradicts the claim that $(P,Q)$ is surjective.  So this map must have degree $1$, i.e. it is a birational transformation, so there are rational functions $A,B$ with $A( P(x,y), Q(x,y))=x, B(P(x,y), Q(x,y))=y$ for $x$, $y$ on a dense open set.
Because $P,Q$ take every integer value, on a dense open set they take every integral value on a dense open set, so $P$ and $Q$ must take integral values on a dense open set. If $P$ and $Q$ are rational functions but not polynomials this is impossible, so $P$ and $Q$ must be integer-valued polynomial functions.
