Polynomial injection between: $\mathbb{N}^{2n}/\phi$ and $\mathbb{N}$.

Question

Let $\phi$ an involution defined as follows:

$$\phi:\mathbb{N}^{2n}\longrightarrow \mathbb{N}^{2n}$$ $$(a_1,b_1,a_2,b_2,\dots,a_n,b_n)\longrightarrow (b_1,a_1,b_2,a_2,\dots,b_n,a_n).$$

Is there any polynomial injection between: $\mathbb{N}^{2n}/\phi$ and $\mathbb{N}$, where $\mathbb{N}^{2n}/\phi$ is the quotient space that identifies $x$ with $\phi(x)$?

Answer 1

In order to make the explanation simpler, let's rearrange the terms a little. Instead of alternating $a$'s and $b$'s, the involution $\phi$ will be defined as $\phi(\underline{a},\underline{b})=(\underline{b},\underline{a})$ where $\underline{a}$ is abbreviation for $a_1,\ldots,a_n$ (and likewise for other letters).

We'll use two ingredients:

• A polynomial $f:\mathbb{N}^2\to \mathbb{N}$ which satisfies $f(x,y)=f(a,b)\iff (x,y)\in\{(a,b),(b,a)\}$.
• An injective polynomial $g:\mathbb{N}^n\to \mathbb{N}$.

We can then define $$h(\underline{a},\underline{b}):=f(g(\underline{a}),g(\underline{b}))$$

Then:

• $h$ is clearly polynomial.
• $h(\underline{a},\underline{b})=h(\phi(\underline{b},\underline{a}))$ so $h$ is well-defined on $\mathbb{N}^{2n}/\phi$
• $h(\underline{x},\underline{y})=h(\underline{a},\underline{b})$ implies, due to properties of $f$, that $$(g(\underline{x}),g(\underline{y})) \in \{(g(\underline{a}),g(\underline{b})), (g(\underline{b}),g(\underline{a}))\}$$ Injectivity of $g$ then implies $(\underline{x},\underline{y})\in \{(\underline{a},\underline{b}),(\underline{b},\underline{a})\}$ so $h$ is injective-up-to-$\phi$.

Thus, $h$ satisfies the required conditions.

A particular example of $h$ can be obtained by considering any injective polynomial $p:\mathbb{N}^2\to \mathbb{N}$ and setting:

• $f(x,y)=p(x+y,x\cdot y)$
• $g(x_1,\ldots,x_n)=p(x_1,p(\ldots,p(x_{n-1},x_n)))$