How to classify $\mathbb N^2$-orbits?

Question

I'm sure the answer to this question is well-known, but I don't know how to search for it. Neither do I know how to tag the question. Feel free to retag it! Or to mark it as a duplicate!

Say that an $\mathbb N$-set is a set $X$ together with an endomap $s:X\to X$. The notion of isomorphism of $\mathbb N$-sets is the obvious one. Given a point $x$ of an $\mathbb N$-set $X$, say that the orbit of $x$ is $$ \{s^n(x)\ |\ n\in\mathbb N\}. $$ This is a sub-$\mathbb N$-set of $X$. Say that the orbits of $x\in X$ and of $y\in Y$ are isomorphic if there is an isomorphism from the first to the second mapping $x$ to $y$.

The $\mathbb N$-orbits are easily classified up to isomorphism, and there is an obvious analog of the above definitions with $\mathbb N^2$ instead of $\mathbb N$.

My question is

How to classify $\mathbb N^2$-orbits?

Edit An $\mathbb N^2$-set is a set equipped with two commuting endomaps.

Here is the classification of $\mathbb N$-orbits up to isomorphism I'd like to generalize to $\mathbb N^2$-orbits:

I'll give examples of $\mathbb N$-orbits, and claim that any $\mathbb N$-orbit is isomorphic to exactly one of the examples.

The first example is $\mathbb N$ itself viewed as the orbit of $0$ under the standard successor map $n\mapsto n+1$.

The other examples are finite, and come as a two parameter family.

Set $X:=\{x_0,\dots,x_n\}$ with $n\ge0$, let $k$ be an integer such that $0\le k\le n$, and define $s:X\to X$ by $s(x_0)=x_1,\dots,s(x_{n-1})=x_n,s(x_n)=x_k$. (Such an orbit resembles the letter P - or the letter O if $k=0$.)

Let $Y$ be an orbit starting with $y\in Y$.

If $Y$ is infinite, $(Y,y)$ is isomorphic to $(\mathbb N,0)$ with the usual successor map.

If $Y$ is finite, there is a unique $(k,n)\in\mathbb N^2$ such that $(Y,y)$ is isomorphic to the orbit $(X,x_0)$ described above.

The verification is left to the reader.

Answer 1

I'll give a partial answer by trying to answer what the "cyclic" part of sorts can look like.

Let $(Y,y)$ be an $\newcommand\NN{\Bbb{N}}\NN^2$-orbit, with $r$ and $s$ the commuting endomaps.

Define a $\newcommand\ZZ{\Bbb{Z}}\ZZ^2$-set $Z$ by $Z=Y\times Y/\sim$, where $(m,0)$ acts by $r^m$ on the first copy for $m > 0$, $(-m,0)$ acts by $r^m$ on the second copy of $Y$, again with $m> 0$, and $(0,n)$ acts by $s$ on the first or second copy according to its sign. Then the $\sim$ relation will be $(y_1,y_2)\sim (y_3,y_4)$ if there exist $a,b\in\NN$ such that $r^as^by_1=r^as^by_3$ and $r^as^by_2=r^as^by_4$. It's not hard to check that $\sim$ forms an equivalence relation that respects the group action.

Essentially, we're forming the Grothendieck group of the image of $\NN^2$ in $\operatorname{End}(X)$.

Note that if $a,b,c,d\in\NN$, then $(a-b,c-d)[(y_1,y_2)]=[(r^as^cy_1,r^bs^dy_2)]$.

This implies that $\ZZ^2$ acts transitively on $Z$, since $Y$ is a $\NN^2$-orbit:

Let $[(y_1,y_2)]\in Z$. Let $y_1 = r^as^b y$ and $y_2 = r^cs^d y$. Then $[(y_1,y_2)] = (a-c,b-d)[(y,y)]$, so every element of $Z$ is in the orbit of $[(y,y)]$.

Thus $Z$ as a $\ZZ^2$-set is isomorphic to $\ZZ^2/K$ for some $K\subseteq \ZZ^2$.

In particular, though, we know that $K$ is free of rank 0, 1, or 2.

If $K$ is free of rank 0, $K=0$, and there are no nontrivial relations in $Z$, so there can't be any nontrivial relations in $Y$ either, since you can think of $Z$ as describing the "eventual" behavior of $Y$. Thus if $K=0$, $Y$ is isomorphic to $(\NN^2,0)$.

If $K$ is free of rank 1, $K=\langle (n,m) \rangle$, then $Y$ looks sort of like what you get by rolling up a piece of paper in one direction, but perhaps at an angle to the actual lines of the paper. The starting part is a bit more difficult to work out, but it's eventually cyclic in one direction, and one direction with no cyclicity.

If $K$ is free of rank 2, $Y$ looks sort of like a (discrete) torus, again, the starting part is a bit difficult to work out, but eventually $Y$ sort of looks like a torus, with two directions of cyclicity.

Hopefully this is helpful, and perhaps this can be turned into a complete answer, but I don't have the time right now to figure out a precise statement of the algebraic relationship between $Z$ and $Y$, or to work out what the beginning behavior can look like.

For example, it seems likely that $Y$ could start by getting one direction of cyclicity, and continuing for a while before getting its second direction of cyclicity, forming a sort of P shape, but with a flat part to the left, and where the $P$ shape is made of tubes.

Edit I found a source calling these trajectories instead of orbits (which makes a lot of sense), but I haven't found anything classifying trajectories for $\NN^2$

Answer 2

Let me augment the answer of @jgon, who produces a coarse classification of $\mathbb N^2$ orbits according to the corresponding subgroup $K < \mathbb Z^2$ and $\mathbb Z^2$ set $Z = \mathbb Z^2 / K$. That answer also shows that if $K$ has rank $0$ then there is just one corresponding $\mathbb N^2$ orbit.

I'll show that if the subgroup $K < \mathbb Z^2$ has rank $1$ or $2$ then there are infinitely many classes of $\mathbb N$-orbits corresponding to $K$. Of course, the group $K$ acts on $\mathbb Z^2$ by addition, $$(k,l) \cdot (i,j) = (k+i,l+j) \quad \text{for each $(k,l) \in K$ and $(i,j) \in \mathbb Z^2$} $$ The $K$-orbit of $(i,j)$ will be denoted $$(i,j) + K = \{(k+i,l+j) \mid (k,l) \in K\} $$ and the $\mathbb Z^2$ set corresponding to $K$ will be denoted $$Z = \mathbb Z^2 / K = \{(i,j) + K \mid (i,j) \in \mathbb Z^2\} $$

Basically the idea is to construct an $\mathbb N^2$ set $Y = A \cup Z$ where $Z$ is the "periodic" part of the action and $A$ is the "preperiodic part" of the action (what @jgon calls the "starting part"). So I have to describe what $A$ can be.

Let $A \subset \mathbb N^2$ be a subset which is complement closed with respect to the addition action of $\mathbb N^2$ on itself, meaning that for all $(a,b) \in \mathbb N^2 - A$ and $(m,n) \in \mathbb N^2$ we have $(a+m,b+n) \in \mathbb N^2 - A$. For example, here are some complement closed sets: $$A = \{(1,j) \mid j \in \mathbb N\} \cup \{(i,1) \mid i \in \mathbb N\} $$ and $$A = \{(i,j) \in \mathbb N^2 \mid ij > 42\} $$ Now define the $\mathbb N^2$ set $Y_A = A \cup (\mathbb Z^2 / K)$, with the following action of $\mathbb N^2$: for each $(m,n) \in \mathbb N^2$ we have:

• If $(i,j) + K \in \mathbb Z^2 / K$ then $(m,n) \cdot \bigl( (i,j) + K \bigr) = (m+i,n+j) + K$
• If $(i,j) \in A$ and $(m+i,n+j) \in \mathbb N^2 - A$ then $(m,n) \cdot (i,j) = \bigl( (m+i,n+j) + K \bigr)$
• If $(i,j) \in A$ and $(m+i,n+j) \in A$ then $(m,n) \cdot (i,j) = (m+i,n+j)$

There are infinitely many complement closed subsets $A \subset \mathbb N^2$ (at first I thought there were uncountably many different $A$, but now I'm thinking there's only countably many). It's pretty clear that if $K$ is fixed, and if $A_1 \ne A_2$ are distinct complement closed sets, then the $\mathbb N^2$ sets $Y_{A_1}$ and $Y_{A_2}$ are inequivalent.

Answer 3

Edit. In fact every congruence on $\mathbb N^n$ is finitely generated. In the book Finitely Generated Commutative Monoids by J. C. Rosales and P. A. García-Sánchez this is stated as Theorem 5.12 page 52, and is called "Rédei's Theorem". This result is sometimes formulated as "Finitely generated commutative monoids are finitely presented". It implies in particular that there are only countably many isomorphism classes of such monoids.

See also this MathOverflow question by John Baez.

End of Edit.

---

In his answer Lee Mosher asked the question:

Is the set of all isomorphism classes of $\mathbb N^2$ orbits countable?

I must confess that I hadn't thought of this crucial question. The argument below shows that the answer is Yes.

Say that an equivalence relation $\sim$ on $\mathbb N^2$ is a congruence if $$ \alpha\sim\beta\implies \alpha+\gamma\sim\beta+\gamma. $$ for all $\alpha,\beta,\gamma\in\mathbb N^2$. There is an obvious notion of congruence generated by a relation on $\mathbb N^2$.

If $\sim$ is a congruence, $(\mathbb N^2/\sim,[(0,0)])$ is an $\mathbb N^2$-orbit.

Conversely, if $(X,x_0)$ is an $\mathbb N^2$-orbit, and if $f:\mathbb N^2\to X$ is the unique morphism of $\mathbb N^2$-orbits from $(\mathbb N^2,(0,0))$ to $(X,x_0)$, then the relation "$f(\alpha )=f(\beta)$" is a congruence on $\mathbb N^2$, and $f$ induces an isomorphism $$ (\mathbb N^2/\sim,[(0,0)])\simeq(X,x_0). $$ The idea behind the following lines is that, if $f(\alpha)=f(\beta)$, then the behavior of $f$ on the orbit of $\beta$ is "the same" as its behavior on the orbit of $\alpha$, so that, to know $f$ it suffices to know how it behaves on a single orbit by nonempty fiber.

Write $\text{Orb}(x)$ for the orbit of $x$.

Lemma. If $\alpha_0,\alpha_1,\dots$ is a sequence of points of $\mathbb N^2$, then the ascending chain $$ U_j:=\bigcup_{i=0}^j\text{Orb}(\alpha_i) $$ stabilizes.

Proof. Let $m_1$ be the minimum (over $i$) of the $\alpha_{i1}$ (with the notation $\alpha_i=(\alpha_{i1},\alpha_{i2})$), define $m_2$ similarly, let $k$ and $\ell$ be such that $\alpha_{k1}=m_1$ and $\alpha_{\ell2}=m_2$. Then for $j$ larger than $k$ and $\ell$ we have $$ \text{Orb}(\alpha_k)\cup\text{Orb}(\alpha_\ell)\subset U_j\subset\text{Orb}(m_1,m_2). $$ (Here and in the sequel $\subset$ means "subset" - not necessarily proper.) As there are only finitely many subsets of $\mathbb N^2$ which satisfy the two above inclusions, we are done. $\square$

Claim. Any congruence on $\mathbb N^2$ is finitely generated.

This will answer (in a positive way) Lee Mosher's question.

Proof. Let $(X,x_0)$ be an $\mathbb N^2$-orbit, let $f:\mathbb N^2\to X$ be the morphism defined above, and let $c:\mathbb N\to\mathbb N^2$ be the inverse of Cantor's pairing function, so that we have $$ \mathbb N\xrightarrow c\mathbb N^2\xrightarrow fX. $$ We will firstly specify a finite subset $G$ of $(\mathbb N^2)^2$ such that $f(\alpha)=f(\beta)$ for all $(\alpha,\beta)\in G$, and secondly we will define the congruence $\sim$ on $\mathbb N^2$ as the least congruence such that $\alpha\sim \beta$ for all $(\alpha,\beta)\in G$. We'll obviously have $\alpha\sim\beta\implies f(\alpha)=f(\beta)$, and we'll try to prove the converse implication.

If $S$ is a subset of $\mathbb N$ and if $s:I\to S$ be the only map such that $I$ is an initial segment of $\mathbb N$, and $s$ is increasing and surjective, we call $s$ the parametrization of $S$.

Let $P(\mathbb N)$ be the set of subsets of $\mathbb N$. We define a map $$ g:P(\mathbb N)\to(P(\mathbb N))^2,\quad S\mapsto(g_1(S),g_2(S)) $$ as follows:

Let $s:I\to S$ be the parametrization of $S$, so that we have $$ I\xrightarrow sS\xrightarrow c\mathbb N^2\xrightarrow fX;\ I,S\subset\mathbb N. $$

If $f\circ c\circ s$ is injective we set $g(S):=(S,\varnothing)$.

Assume $f\circ c\circ s$ is not injective.

Write $F_i\subset I$ for the fiber of $f\circ c\circ s$ containing $i\in I$. Let $i\in I$ be such that $F_i$ has at least two elements and $i$ is minimum for this condition. Set $$ U:=\bigcup_{k\in F_i\setminus\{i\}}\text{Orb}(c(s(k))).\qquad(1) $$ Let $t:J\to F_i\subset I$ be the parametrization of $F_i$, so that we have $$ J\xrightarrow tF_i\xrightarrow sS\xrightarrow c\mathbb N^2\xrightarrow fX,\ J\subset\mathbb N,\ F_i\subset I\subset\mathbb N,\ S\subset\mathbb N, $$ and the lemma implies $$ U=\bigcup_{j=1}^m\text{Orb}(c(s(t(j))))\qquad(2) $$ for some $m\in J\subset\mathbb N$. Then we set $$ g_1(S):=c^{-1}(c(S)\setminus U), $$ $$ g_2(S):=\{s(t(1)),\dots,s(t(m))\}. $$ Then ends the definition of $$ g:P(\mathbb N)\to(P(\mathbb N))^2,\quad S\mapsto(g_1(S),g_2(S)). $$ Now we define the subsets $$ \mathbb N_0\supset\mathbb N_1\supset\mathbb N_2\supset\cdots $$ inductively by $\mathbb N_0:=\mathbb N$ and $\mathbb N_i:=g_1(\mathbb N_{i-1})$ for $i\ge1$.

As we remove from $\mathbb N^2$ at least one orbit at each stage, the descending chain stabilizes by the lemma, and the union of the $g_2(\mathbb N_i)$ is a finite set $K$: $$ K:=\bigcup_{i\in\mathbb N}g_2(\mathbb N_i). $$ We define the finite subset $$ G\subset(\mathbb N^2)^2 $$ by decreeing that the couple $(\alpha,\beta)\in(\mathbb N^2)^2$ is in $G$ if and only if $$ c^{-1}(\alpha),c^{-1}(\beta)\in g_2(\mathbb N_i) $$ for some $i\in\mathbb N$.

As indicated above, we define the congruence $\sim$ on $\mathbb N^2$ as the least congruence such that $\alpha\sim\beta$ for all $(\alpha,\beta)\in G$. We obviously have $\alpha\sim\beta\implies f(\alpha)=f(\beta)$.

Let us prove $f(\alpha)=f(\beta)\implies\alpha\sim\beta$.

We assume by contradiction that there are $i,j\in\mathbb N$ such that $c(i)\not\sim c(j)$ but $f(c(i))=f(c(j))$. We also assume that $i+j$ is minimum for this condition.

As $f\circ c$ is injective on $\mathbb N_\infty$ (we write $\mathbb N_\infty$ for the eventual value of the $\mathbb N_k$), the integers $i$ and $j$ cannot be both in $\mathbb N_\infty$. Say that $i$ is not in $\mathbb N_\infty$. This means that $c(i)$ is in $\text{Orb}(c(k))$ for some $k\in K$, that is $k\in g_2(\mathbb N_n)$ for some $n\in\mathbb N$. Let $m$ be the minimum of $g_2(\mathbb N_n)$. We get $$ m<k $$ (this is because we have $k\ne i$ in $(1)$, or, equivalently, $j\ge1$ in $(2)$) and $c(m)\sim c(k)$ by definition of $\sim$. As $c(i)\in\text{Orb}(c(k))$, we can write $$ c(i)=c(k)+\alpha $$ with $\alpha\in\mathbb N^2$. Define $i'\in\mathbb N$ by $$ c(i')=c(m)+\alpha. $$ It is easy to see, using the definition of Cantor's pairing function, that the last three displays imply $i'<i$.

We get $c(i')\sim c(i)\not\sim c(j)$, so that we can replace $(i,j)$ with $(i',j)$, which yields the contradiction $i'+j<i+j$ (recall that $i+j$ was assumed to be minimum).

This shows that there are no $i,j\in\mathbb N$ such that $c(i)\not\sim c(j)$ but $f(c(i))=f(c(j))$, and thus that $f(\alpha)=f(\beta)\iff\alpha\sim\beta$. Therefore $\sim$ is an arbitrary congruence, and we proved that it is finitely generated. $\square$